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