1 /*
2  * Copyright (C) 2010 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 
17 package com.android.quicksearchbox;
18 
19 import com.android.quicksearchbox.util.LevenshteinDistance;
20 import com.android.quicksearchbox.util.LevenshteinDistance.Token;
21 import com.google.common.annotations.VisibleForTesting;
22 
23 import android.text.SpannableString;
24 import android.text.Spanned;
25 import android.util.Log;
26 
27 /**
28  * Suggestion formatter using the Levenshtein distance (minumum edit distance) to calculate the
29  * formatting.
30  */
31 public class LevenshteinSuggestionFormatter extends SuggestionFormatter {
32     private static final boolean DBG = false;
33     private static final String TAG = "QSB.LevenshteinSuggestionFormatter";
34 
LevenshteinSuggestionFormatter(TextAppearanceFactory spanFactory)35     public LevenshteinSuggestionFormatter(TextAppearanceFactory spanFactory) {
36         super(spanFactory);
37     }
38 
39     @Override
formatSuggestion(String query, String suggestion)40     public Spanned formatSuggestion(String query, String suggestion) {
41         if (DBG) Log.d(TAG, "formatSuggestion('" + query + "', '" + suggestion + "')");
42         query = normalizeQuery(query);
43         final Token[] queryTokens = tokenize(query);
44         final Token[] suggestionTokens = tokenize(suggestion);
45         final int[] matches = findMatches(queryTokens, suggestionTokens);
46         if (DBG){
47             Log.d(TAG, "source = " + queryTokens);
48             Log.d(TAG, "target = " + suggestionTokens);
49             Log.d(TAG, "matches = " + matches);
50         }
51         final SpannableString str = new SpannableString(suggestion);
52 
53         final int matchesLen = matches.length;
54         for (int i = 0; i < matchesLen; ++i) {
55             final Token t = suggestionTokens[i];
56             int sourceLen = 0;
57             int thisMatch = matches[i];
58             if (thisMatch >= 0) {
59                 sourceLen = queryTokens[thisMatch].length();
60             }
61             applySuggestedTextStyle(str, t.mStart + sourceLen, t.mEnd);
62             applyQueryTextStyle(str, t.mStart, t.mStart + sourceLen);
63         }
64 
65         return str;
66     }
67 
normalizeQuery(String query)68     private String normalizeQuery(String query) {
69         return query.toLowerCase();
70     }
71 
72     /**
73      * Finds which tokens in the target match tokens in the source.
74      *
75      * @param source List of source tokens (i.e. user query)
76      * @param target List of target tokens (i.e. suggestion)
77      * @return The indices into source which target tokens correspond to. A non-negative value n at
78      *      position i means that target token i matches source token n. A negative value means that
79      *      the target token i does not match any source token.
80      */
81     @VisibleForTesting
findMatches(Token[] source, Token[] target)82     int[] findMatches(Token[] source, Token[] target) {
83         final LevenshteinDistance table = new LevenshteinDistance(source, target);
84         table.calculate();
85         final int targetLen = target.length;
86         final int[] result = new int[targetLen];
87         LevenshteinDistance.EditOperation[] ops = table.getTargetOperations();
88         for (int i = 0; i < targetLen; ++i) {
89             if (ops[i].getType() == LevenshteinDistance.EDIT_UNCHANGED) {
90                 result[i] = ops[i].getPosition();
91             } else {
92                 result[i] = -1;
93             }
94         }
95         return result;
96     }
97 
98     @VisibleForTesting
tokenize(final String seq)99     Token[] tokenize(final String seq) {
100         int pos = 0;
101         final int len = seq.length();
102         final char[] chars = seq.toCharArray();
103         // There can't be more tokens than characters, make an array that is large enough
104         Token[] tokens = new Token[len];
105         int tokenCount = 0;
106         while (pos < len) {
107             while (pos < len && (chars[pos] == ' ' || chars[pos] == '\t')) {
108                 pos++;
109             }
110             int start = pos;
111             while (pos < len && !(chars[pos] == ' ' || chars[pos] == '\t')) {
112                 pos++;
113             }
114             int end = pos;
115             if (start != end) {
116                 tokens[tokenCount++] = new Token(chars, start, end);
117             }
118         }
119         // Create a token array of the right size and return
120         Token[] ret = new Token[tokenCount];
121         System.arraycopy(tokens, 0, ret, 0, tokenCount);
122         return ret;
123     }
124 
125 }
126