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.os.Bundle;
19 import android.view.autofill.AutofillValue;
20 
21 import androidx.annotation.NonNull;
22 import androidx.annotation.Nullable;
23 import androidx.annotation.VisibleForTesting;
24 
25 final class EditDistanceScorer {
26 
27     private static final String TAG = "EditDistanceScorer";
28 
29     private static final boolean DEBUG = false;
30 
31     /**
32      * Gets the field classification score of 2 values based on the edit distance between them.
33      *
34      * <p>The score is defined as: @(max_length - edit_distance) / max_length
35      */
36     @VisibleForTesting
calculateScore(@ullable AutofillValue actualValue, @Nullable String userDataValue, @Nullable Bundle args)37     static float calculateScore(@Nullable AutofillValue actualValue,
38             @Nullable String userDataValue, @Nullable Bundle args) {
39         if (actualValue == null || !actualValue.isText() || userDataValue == null) return 0;
40 
41         final String actualValueText = actualValue.getTextValue().toString();
42         final int actualValueLength = actualValueText.length();
43         final int userDataLength = userDataValue.length();
44         if (userDataLength == 0) {
45             return (actualValueLength == 0) ? 1 : 0;
46         }
47 
48         final int distance = editDistance(actualValueText.toLowerCase(),
49                 userDataValue.toLowerCase());
50         final int maxLength = Math.max(actualValueLength, userDataLength);
51         return ((float) maxLength - distance) / maxLength;
52     }
53 
54     /**
55      * Computes the edit distance (number of insertions, deletions or substitutions to edit one
56      * string into the other) between two strings. In particular, this will compute the Levenshtein
57      * distance.
58      *
59      * <p>See http://en.wikipedia.org/wiki/Levenshtein_distance for details.
60      *
61      * @param s the first string to compare
62      * @param t the second string to compare
63      * @return the edit distance between the two strings
64      */
65     // Note: copied verbatim from com.android.tools.lint.detector.api.LintUtils.java
editDistance(@onNull String s, @NonNull String t)66     public static int editDistance(@NonNull String s, @NonNull String t) {
67         return editDistance(s, t, Integer.MAX_VALUE);
68     }
69 
70     /**
71      * Computes the edit distance (number of insertions, deletions or substitutions to edit one
72      * string into the other) between two strings. In particular, this will compute the Levenshtein
73      * distance.
74      *
75      * <p>See http://en.wikipedia.org/wiki/Levenshtein_distance for details.
76      *
77      * @param s the first string to compare
78      * @param t the second string to compare
79      * @param max the maximum edit distance that we care about; if for example the string length
80      *     delta is greater than this we don't bother computing the exact edit distance since the
81      *     caller has indicated they're not interested in the result
82      * @return the edit distance between the two strings, or some other value greater than that if
83      *     the edit distance is at least as big as the {@code max} parameter
84      */
85     // Note: copied verbatim from com.android.tools.lint.detector.api.LintUtils.java
editDistance(@onNull String s, @NonNull String t, int max)86     public static int editDistance(@NonNull String s, @NonNull String t, int max) {
87         if (s.equals(t)) {
88             return 0;
89         }
90 
91         if (Math.abs(s.length() - t.length()) > max) {
92             // The string lengths differ more than the allowed edit distance;
93             // no point in even attempting to compute the edit distance (requires
94             // O(n*m) storage and O(n*m) speed, where n and m are the string lengths)
95             return Integer.MAX_VALUE;
96         }
97 
98         int m = s.length();
99         int n = t.length();
100         int[][] d = new int[m + 1][n + 1];
101         for (int i = 0; i <= m; i++) {
102             d[i][0] = i;
103         }
104         for (int j = 0; j <= n; j++) {
105             d[0][j] = j;
106         }
107         for (int j = 1; j <= n; j++) {
108             for (int i = 1; i <= m; i++) {
109                 if (s.charAt(i - 1) == t.charAt(j - 1)) {
110                     d[i][j] = d[i - 1][j - 1];
111                 } else {
112                     int deletion = d[i - 1][j] + 1;
113                     int insertion = d[i][j - 1] + 1;
114                     int substitution = d[i - 1][j - 1] + 1;
115                     d[i][j] = Math.min(deletion, Math.min(insertion, substitution));
116                 }
117             }
118         }
119 
120         return d[m][n];
121     }
122 
123 }
124