1 /*
2  * Copyright (C) 2017 The Android Open Source Project
3  *
4  * Licensed under the Apache License, Version 2.0 (the "License");
5  * you may not use this file except in compliance with the License.
6  * You may obtain a copy of the License at
7  *
8  *      http://www.apache.org/licenses/LICENSE-2.0
9  *
10  * Unless required by applicable law or agreed to in writing, software
11  * distributed under the License is distributed on an "AS IS" BASIS,
12  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13  * See the License for the specific language governing permissions and
14  * limitations under the License.
15  */
16 package android.ext.services.autofill;
17 
18 import android.annotation.NonNull;
19 import android.annotation.Nullable;
20 import android.util.Log;
21 import android.view.autofill.AutofillValue;
22 
23 import com.android.internal.annotations.VisibleForTesting;
24 
25 import java.util.List;
26 
27 final class EditDistanceScorer {
28 
29     private static final String TAG = "EditDistanceScorer";
30 
31     // TODO(b/70291841): STOPSHIP - set to false before launching
32     private static final boolean DEBUG = true;
33 
34     static final String DEFAULT_ALGORITHM = "EDIT_DISTANCE";
35 
36     /**
37      * Gets the field classification score of 2 values based on the edit distance between them.
38      *
39      * <p>The score is defined as: @(max_length - edit_distance) / max_length
40      */
41     @VisibleForTesting
getScore(@ullable AutofillValue actualValue, @Nullable String userDataValue)42     static float getScore(@Nullable AutofillValue actualValue, @Nullable String userDataValue) {
43         if (actualValue == null || !actualValue.isText() || userDataValue == null) return 0;
44 
45         final String actualValueText = actualValue.getTextValue().toString();
46         final int actualValueLength = actualValueText.length();
47         final int userDatalength = userDataValue.length();
48         if (userDatalength == 0) {
49             return (actualValueLength == 0) ? 1 : 0;
50         }
51 
52         final int distance = editDistance(actualValueText.toLowerCase(),
53                 userDataValue.toLowerCase());
54         final int maxLength = Math.max(actualValueLength, userDatalength);
55         return ((float) maxLength - distance) / maxLength;
56     }
57 
58     /**
59      * Computes the edit distance (number of insertions, deletions or substitutions to edit one
60      * string into the other) between two strings. In particular, this will compute the Levenshtein
61      * distance.
62      *
63      * <p>See http://en.wikipedia.org/wiki/Levenshtein_distance for details.
64      *
65      * @param s the first string to compare
66      * @param t the second string to compare
67      * @return the edit distance between the two strings
68      */
69     // Note: copied verbatim from com.android.tools.lint.detector.api.LintUtils.java
editDistance(@onNull String s, @NonNull String t)70     public static int editDistance(@NonNull String s, @NonNull String t) {
71         return editDistance(s, t, Integer.MAX_VALUE);
72     }
73 
74     /**
75      * Computes the edit distance (number of insertions, deletions or substitutions to edit one
76      * string into the other) between two strings. In particular, this will compute the Levenshtein
77      * distance.
78      *
79      * <p>See http://en.wikipedia.org/wiki/Levenshtein_distance for details.
80      *
81      * @param s the first string to compare
82      * @param t the second string to compare
83      * @param max the maximum edit distance that we care about; if for example the string length
84      *     delta is greater than this we don't bother computing the exact edit distance since the
85      *     caller has indicated they're not interested in the result
86      * @return the edit distance between the two strings, or some other value greater than that if
87      *     the edit distance is at least as big as the {@code max} parameter
88      */
89     // Note: copied verbatim from com.android.tools.lint.detector.api.LintUtils.java
editDistance(@onNull String s, @NonNull String t, int max)90     private static int editDistance(@NonNull String s, @NonNull String t, int max) {
91         if (s.equals(t)) {
92             return 0;
93         }
94 
95         if (Math.abs(s.length() - t.length()) > max) {
96             // The string lengths differ more than the allowed edit distance;
97             // no point in even attempting to compute the edit distance (requires
98             // O(n*m) storage and O(n*m) speed, where n and m are the string lengths)
99             return Integer.MAX_VALUE;
100         }
101 
102         int m = s.length();
103         int n = t.length();
104         int[][] d = new int[m + 1][n + 1];
105         for (int i = 0; i <= m; i++) {
106             d[i][0] = i;
107         }
108         for (int j = 0; j <= n; j++) {
109             d[0][j] = j;
110         }
111         for (int j = 1; j <= n; j++) {
112             for (int i = 1; i <= m; i++) {
113                 if (s.charAt(i - 1) == t.charAt(j - 1)) {
114                     d[i][j] = d[i - 1][j - 1];
115                 } else {
116                     int deletion = d[i - 1][j] + 1;
117                     int insertion = d[i][j - 1] + 1;
118                     int substitution = d[i - 1][j - 1] + 1;
119                     d[i][j] = Math.min(deletion, Math.min(insertion, substitution));
120                 }
121             }
122         }
123 
124         return d[m][n];
125     }
126     /**
127      * Gets the scores in a batch.
128      */
getScores(@onNull List<AutofillValue> actualValues, @NonNull List<String> userDataValues)129     static float[][] getScores(@NonNull List<AutofillValue> actualValues,
130             @NonNull List<String> userDataValues) {
131         final int actualValuesSize = actualValues.size();
132         final int userDataValuesSize = userDataValues.size();
133         if (DEBUG) {
134             Log.d(TAG, "getScores() will return a " + actualValuesSize + "x"
135                     + userDataValuesSize + " matrix for " + DEFAULT_ALGORITHM);
136         }
137         final float[][] scores = new float[actualValuesSize][userDataValuesSize];
138 
139         for (int i = 0; i < actualValuesSize; i++) {
140             for (int j = 0; j < userDataValuesSize; j++) {
141                 final float score = getScore(actualValues.get(i), userDataValues.get(j));
142                 scores[i][j] = score;
143             }
144         }
145         return scores;
146     }
147 
148 }
149