1 /**
2  * Copyright (C) 2021 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 com.android.car.voicecontrol;
17 
18 import android.util.Log;
19 
20 /**
21  * Utility string comparison methods
22  */
23 public final class StringUtils {
24     private static final String TAG = "Mica.StringUtils";
25 
26     // This is a utility class
StringUtils()27     private StringUtils() {}
28 
29     /**
30      * Returns the minimum edit distance between one source string and a set of possible
31      * target strings
32      */
getMinDistance(String source, String... targets)33     public static int getMinDistance(String source, String... targets) {
34         int d = Integer.MAX_VALUE;
35         for (String t : targets) {
36             if (t != null) {
37                 int newD = getDistance(source, t);
38                 d = Math.min(d, newD);
39                 Log.d(TAG, "Distance between: '" + source + "' and '" + t + "': " + newD);
40             }
41         }
42         return d;
43     }
44 
45     //
46     // Copied from https://commons.apache.org/proper/commons-lang/javadocs/api-2.5/src-html/org/apache/commons/lang/StringUtils.html
47     //
getDistance(String s, String t)48     private static int getDistance(String s, String t) {
49         int n = s.length();
50         int m = t.length();
51 
52         if (n == 0) {
53             return m;
54         } else if (m == 0) {
55             return n;
56         }
57 
58         if (n > m) {
59             String tmp = s;
60             s = t;
61             t = tmp;
62             n = m;
63             m = t.length();
64         }
65 
66         int[] p = new int[n + 1];
67         int[] d = new int[n + 1];
68         int[] _d;
69         int i, j, cost;
70         char t_j;
71 
72         for (i = 0; i <= n; i++) {
73             p[i] = i;
74         }
75 
76         for (j = 1; j <= m; j++) {
77             t_j = t.charAt(j - 1);
78             d[0] = j;
79 
80             for (i = 1; i <= n; i++) {
81                 cost = s.charAt(i - 1) == t_j ? 0 : 1;
82                 d[i] = Math.min(Math.min(d[i - 1] + 1, p[i] + 1), p[i - 1] + cost);
83             }
84 
85             _d = p;
86             p = d;
87             d = _d;
88         }
89 
90         return p[n];
91     }
92     //
93     // end of https://commons.apache.org/proper/commons-lang/javadocs/api-2.5/src-html/org/apache/commons/lang/StringUtils.html
94     //
95 
96     //
97     // The section below has been copied from
98     // http://commons.apache.org/proper/commons-codec/apidocs/src-html/org/apache/commons/codec/language/Soundex.html
99     //
100     private static final char SILENT_MARKER = '-';
101     private static final char[] US_ENGLISH_MAPPING_STRING = "01230120022455012623010202"
102             .toCharArray();
103 
soundexMap(final char ch)104     private static char soundexMap(final char ch) {
105         final int index = ch - 'A';
106         if (index < 0 || index >= US_ENGLISH_MAPPING_STRING.length) {
107             return SILENT_MARKER;
108         }
109         return US_ENGLISH_MAPPING_STRING[index];
110     }
111 
soundexClean(String str)112     private static String soundexClean(String str) {
113         if (str == null || str.length() == 0) {
114             return str;
115         }
116         int len = str.length();
117         char[] chars = new char[len];
118         int count = 0;
119         for (int i = 0; i < len; i++) {
120             if (Character.isLetter(str.charAt(i))) {
121                 chars[count++] = str.charAt(i);
122             }
123         }
124         return new String(chars, 0, count).toUpperCase(java.util.Locale.ENGLISH);
125     }
126 
127     /**
128      * Encodes a string into a Soundex value. Soundex is an encoding used to relate similar names,
129      * but can also be used as a general purpose scheme to find word with similar phonemes.
130      */
soundex(String str)131     public static String soundex(String str) {
132         if (str == null) {
133             return null;
134         }
135         str = soundexClean(str);
136         if (str.length() == 0) {
137             return str;
138         }
139         final char[] out = {'0', '0', '0', '0'};
140         int count = 0;
141         final char first = str.charAt(0);
142         out[count++] = first;
143         char lastDigit = soundexMap(first);
144         for (int i = 1; i < str.length() && count < out.length; i++) {
145             final char ch = str.charAt(i);
146             if (ch == 'H' || ch == 'W') {
147                 continue;
148             }
149             final char digit = soundexMap(ch);
150             if (digit == SILENT_MARKER) {
151                 continue;
152             }
153             if (digit != '0' && digit != lastDigit) {
154                 out[count++] = digit;
155             }
156             lastDigit = digit;
157         }
158         return new String(out);
159     }
160     //
161     // End of
162     // http://commons.apache.org/proper/commons-codec/apidocs/src-html/org/apache/commons/codec/language/Soundex.html
163     //
164 }
165