diff options
Diffstat (limited to 'android/ext')
4 files changed, 116 insertions, 53 deletions
diff --git a/android/ext/services/autofill/AutofillFieldClassificationServiceImpl.java b/android/ext/services/autofill/AutofillFieldClassificationServiceImpl.java index 4709d350..9ba7e092 100644 --- a/android/ext/services/autofill/AutofillFieldClassificationServiceImpl.java +++ b/android/ext/services/autofill/AutofillFieldClassificationServiceImpl.java @@ -15,6 +15,8 @@ */ package android.ext.services.autofill; +import static android.ext.services.autofill.EditDistanceScorer.DEFAULT_ALGORITHM; + import android.annotation.NonNull; import android.annotation.Nullable; import android.os.Bundle; @@ -29,8 +31,6 @@ import java.util.List; public class AutofillFieldClassificationServiceImpl extends AutofillFieldClassificationService { private static final String TAG = "AutofillFieldClassificationServiceImpl"; - // TODO(b/70291841): set to false before launching - private static final boolean DEBUG = true; @Nullable @Override @@ -40,30 +40,13 @@ public class AutofillFieldClassificationServiceImpl extends AutofillFieldClassif if (ArrayUtils.isEmpty(actualValues) || ArrayUtils.isEmpty(userDataValues)) { Log.w(TAG, "getScores(): empty currentvalues (" + actualValues + ") or userValues (" + userDataValues + ")"); - // TODO(b/70939974): add unit test return null; } - if (algorithmName != null && !algorithmName.equals(EditDistanceScorer.NAME)) { + if (algorithmName != null && !algorithmName.equals(DEFAULT_ALGORITHM)) { Log.w(TAG, "Ignoring invalid algorithm (" + algorithmName + ") and using " - + EditDistanceScorer.NAME + " instead"); - } - - final String actualAlgorithmName = EditDistanceScorer.NAME; - final int actualValuesSize = actualValues.size(); - final int userDataValuesSize = userDataValues.size(); - if (DEBUG) { - Log.d(TAG, "getScores() will return a " + actualValuesSize + "x" - + userDataValuesSize + " matrix for " + actualAlgorithmName); + + DEFAULT_ALGORITHM + " instead"); } - final float[][] scores = new float[actualValuesSize][userDataValuesSize]; - final EditDistanceScorer algorithm = EditDistanceScorer.getInstance(); - for (int i = 0; i < actualValuesSize; i++) { - for (int j = 0; j < userDataValuesSize; j++) { - final float score = algorithm.getScore(actualValues.get(i), userDataValues.get(j)); - scores[i][j] = score; - } - } - return scores; + return EditDistanceScorer.getScores(actualValues, userDataValues); } } diff --git a/android/ext/services/autofill/EditDistanceScorer.java b/android/ext/services/autofill/EditDistanceScorer.java index d2e804af..302b1602 100644 --- a/android/ext/services/autofill/EditDistanceScorer.java +++ b/android/ext/services/autofill/EditDistanceScorer.java @@ -16,53 +16,133 @@ package android.ext.services.autofill; import android.annotation.NonNull; +import android.annotation.Nullable; +import android.util.Log; import android.view.autofill.AutofillValue; -/** - * Helper used to calculate the classification score between an actual {@link AutofillValue} filled - * by the user and the expected value predicted by an autofill service. - */ -// TODO(b/70291841): explain algorithm once it's fully implemented +import com.android.internal.annotations.VisibleForTesting; + +import java.util.List; + final class EditDistanceScorer { - private static final EditDistanceScorer sInstance = new EditDistanceScorer(); + private static final String TAG = "EditDistanceScorer"; + + // TODO(b/70291841): STOPSHIP - set to false before launching + private static final boolean DEBUG = true; - public static final String NAME = "EDIT_DISTANCE"; + static final String DEFAULT_ALGORITHM = "EDIT_DISTANCE"; /** - * Gets the singleton instance. + * Gets the field classification score of 2 values based on the edit distance between them. + * + * <p>The score is defined as: @(max_length - edit_distance) / max_length */ - public static EditDistanceScorer getInstance() { - return sInstance; + @VisibleForTesting + static float getScore(@Nullable AutofillValue actualValue, @Nullable String userDataValue) { + if (actualValue == null || !actualValue.isText() || userDataValue == null) return 0; + + final String actualValueText = actualValue.getTextValue().toString(); + final int actualValueLength = actualValueText.length(); + final int userDatalength = userDataValue.length(); + if (userDatalength == 0) { + return (actualValueLength == 0) ? 1 : 0; + } + + final int distance = editDistance(actualValueText.toLowerCase(), + userDataValue.toLowerCase()); + final int maxLength = Math.max(actualValueLength, userDatalength); + return ((float) maxLength - distance) / maxLength; } - private EditDistanceScorer() { + /** + * Computes the edit distance (number of insertions, deletions or substitutions to edit one + * string into the other) between two strings. In particular, this will compute the Levenshtein + * distance. + * + * <p>See http://en.wikipedia.org/wiki/Levenshtein_distance for details. + * + * @param s the first string to compare + * @param t the second string to compare + * @return the edit distance between the two strings + */ + // Note: copied verbatim from com.android.tools.lint.detector.api.LintUtils.java + public static int editDistance(@NonNull String s, @NonNull String t) { + return editDistance(s, t, Integer.MAX_VALUE); } /** - * Returns the classification score between an actual {@link AutofillValue} filled - * by the user and the expected value predicted by an autofill service. + * Computes the edit distance (number of insertions, deletions or substitutions to edit one + * string into the other) between two strings. In particular, this will compute the Levenshtein + * distance. * - * <p>A full-match is {@code 1.0} (representing 100%), a full mismatch is {@code 0.0} and - * partial mathces are something in between, typically using edit-distance algorithms. + * <p>See http://en.wikipedia.org/wiki/Levenshtein_distance for details. * + * @param s the first string to compare + * @param t the second string to compare + * @param max the maximum edit distance that we care about; if for example the string length + * delta is greater than this we don't bother computing the exact edit distance since the + * caller has indicated they're not interested in the result + * @return the edit distance between the two strings, or some other value greater than that if + * the edit distance is at least as big as the {@code max} parameter */ - public float getScore(@NonNull AutofillValue actualValue, @NonNull String userDataValue) { - if (actualValue == null || !actualValue.isText() || userDataValue == null) return 0; - // TODO(b/70291841): implement edit distance - currently it's returning either 0, 100%, or - // partial match when number of chars match - final String textValue = actualValue.getTextValue().toString(); - final int total = textValue.length(); - if (total != userDataValue.length()) return 0F; - - int matches = 0; - for (int i = 0; i < total; i++) { - if (Character.toLowerCase(textValue.charAt(i)) == Character - .toLowerCase(userDataValue.charAt(i))) { - matches++; + // Note: copied verbatim from com.android.tools.lint.detector.api.LintUtils.java + private static int editDistance(@NonNull String s, @NonNull String t, int max) { + if (s.equals(t)) { + return 0; + } + + if (Math.abs(s.length() - t.length()) > max) { + // The string lengths differ more than the allowed edit distance; + // no point in even attempting to compute the edit distance (requires + // O(n*m) storage and O(n*m) speed, where n and m are the string lengths) + return Integer.MAX_VALUE; + } + + int m = s.length(); + int n = t.length(); + int[][] d = new int[m + 1][n + 1]; + for (int i = 0; i <= m; i++) { + d[i][0] = i; + } + for (int j = 0; j <= n; j++) { + d[0][j] = j; + } + for (int j = 1; j <= n; j++) { + for (int i = 1; i <= m; i++) { + if (s.charAt(i - 1) == t.charAt(j - 1)) { + d[i][j] = d[i - 1][j - 1]; + } else { + int deletion = d[i - 1][j] + 1; + int insertion = d[i][j - 1] + 1; + int substitution = d[i - 1][j - 1] + 1; + d[i][j] = Math.min(deletion, Math.min(insertion, substitution)); + } } } - return ((float) matches) / total; + return d[m][n]; + } + /** + * Gets the scores in a batch. + */ + static float[][] getScores(@NonNull List<AutofillValue> actualValues, + @NonNull List<String> userDataValues) { + final int actualValuesSize = actualValues.size(); + final int userDataValuesSize = userDataValues.size(); + if (DEBUG) { + Log.d(TAG, "getScores() will return a " + actualValuesSize + "x" + + userDataValuesSize + " matrix for " + DEFAULT_ALGORITHM); + } + final float[][] scores = new float[actualValuesSize][userDataValuesSize]; + + for (int i = 0; i < actualValuesSize; i++) { + for (int j = 0; j < userDataValuesSize; j++) { + final float score = getScore(actualValues.get(i), userDataValues.get(j)); + scores[i][j] = score; + } + } + return scores; } + } diff --git a/android/ext/services/notification/Assistant.java b/android/ext/services/notification/Assistant.java index 6fe89755..9a66b07f 100644 --- a/android/ext/services/notification/Assistant.java +++ b/android/ext/services/notification/Assistant.java @@ -94,7 +94,7 @@ public class Assistant extends NotificationAssistantService { infile = mFile.openRead(); readXml(infile); } catch (FileNotFoundException e) { - // No data yet + Log.d(TAG, "File doesn't exist or isn't readable yet"); } catch (IOException e) { Log.e(TAG, "Unable to read channel impressions", e); } catch (NumberFormatException | XmlPullParserException e) { diff --git a/android/ext/services/notification/ChannelImpressions.java b/android/ext/services/notification/ChannelImpressions.java index 4ad4b241..de2659f4 100644 --- a/android/ext/services/notification/ChannelImpressions.java +++ b/android/ext/services/notification/ChannelImpressions.java @@ -30,7 +30,7 @@ public final class ChannelImpressions implements Parcelable { private static final String TAG = "ExtAssistant.CI"; private static final boolean DEBUG = Log.isLoggable(TAG, Log.DEBUG); - static final double DISMISS_TO_VIEW_RATIO_LIMIT = .8; + static final double DISMISS_TO_VIEW_RATIO_LIMIT = .4; static final int STREAK_LIMIT = 2; static final String ATT_DISMISSALS = "dismisses"; static final String ATT_VIEWS = "views"; |