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