Home | History | Annotate | Download | only in quicksearchbox 
      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 
     35     public LevenshteinSuggestionFormatter(TextAppearanceFactory spanFactory) {
     36         super(spanFactory);
     37     }
     38 
     39     @Override
     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 
     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
     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
     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