Suggest.java revision b1abda8d62d654e876c4f781a07d724922c736e4
1/* 2 * Copyright (C) 2008 The Android Open Source Project 3 * 4 * Licensed under the Apache License, Version 2.0 (the "License"); you may not 5 * use this file except in compliance with the License. You may obtain a copy of 6 * 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, WITHOUT 12 * WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. See the 13 * License for the specific language governing permissions and limitations under 14 * the License. 15 */ 16 17package com.android.inputmethod.latin; 18 19import java.nio.ByteBuffer; 20import java.util.ArrayList; 21import java.util.Arrays; 22import java.util.List; 23 24import android.content.Context; 25import android.text.AutoText; 26import android.text.TextUtils; 27import android.util.Log; 28import android.view.View; 29 30/** 31 * This class loads a dictionary and provides a list of suggestions for a given sequence of 32 * characters. This includes corrections and completions. 33 * @hide pending API Council Approval 34 */ 35public class Suggest implements Dictionary.WordCallback { 36 37 public static final int APPROX_MAX_WORD_LENGTH = 32; 38 39 public static final int CORRECTION_NONE = 0; 40 public static final int CORRECTION_BASIC = 1; 41 public static final int CORRECTION_FULL = 2; 42 public static final int CORRECTION_FULL_BIGRAM = 3; 43 44 /** 45 * Words that appear in both bigram and unigram data gets multiplier ranging from 46 * BIGRAM_MULTIPLIER_MIN to BIGRAM_MULTIPLIER_MAX depending on the frequency score from 47 * bigram data. 48 */ 49 public static final double BIGRAM_MULTIPLIER_MIN = 1.2; 50 public static final double BIGRAM_MULTIPLIER_MAX = 1.5; 51 52 /** 53 * Maximum possible bigram frequency. Will depend on how many bits are being used in data 54 * structure. Maximum bigram freqeuncy will get the BIGRAM_MULTIPLIER_MAX as the multiplier. 55 */ 56 public static final int MAXIMUM_BIGRAM_FREQUENCY = 127; 57 58 public static final int DIC_USER_TYPED = 0; 59 public static final int DIC_MAIN = 1; 60 public static final int DIC_USER = 2; 61 public static final int DIC_AUTO = 3; 62 public static final int DIC_CONTACTS = 4; 63 // If you add a type of dictionary, increment DIC_TYPE_LAST_ID 64 public static final int DIC_TYPE_LAST_ID = 4; 65 66 static final int LARGE_DICTIONARY_THRESHOLD = 200 * 1000; 67 68 private BinaryDictionary mMainDict; 69 70 private Dictionary mUserDictionary; 71 72 private Dictionary mAutoDictionary; 73 74 private Dictionary mContactsDictionary; 75 76 private Dictionary mUserBigramDictionary; 77 78 private int mPrefMaxSuggestions = 12; 79 80 private static final int PREF_MAX_BIGRAMS = 60; 81 82 private boolean mAutoTextEnabled; 83 84 private double mAutoCompleteThreshold; 85 private int[] mPriorities = new int[mPrefMaxSuggestions]; 86 private int[] mBigramPriorities = new int[PREF_MAX_BIGRAMS]; 87 88 // Handle predictive correction for only the first 1280 characters for performance reasons 89 // If we support scripts that need latin characters beyond that, we should probably use some 90 // kind of a sparse array or language specific list with a mapping lookup table. 91 // 1280 is the size of the BASE_CHARS array in ExpandableDictionary, which is a basic set of 92 // latin characters. 93 private int[] mNextLettersFrequencies = new int[1280]; 94 private ArrayList<CharSequence> mSuggestions = new ArrayList<CharSequence>(); 95 ArrayList<CharSequence> mBigramSuggestions = new ArrayList<CharSequence>(); 96 private ArrayList<CharSequence> mStringPool = new ArrayList<CharSequence>(); 97 private boolean mHaveCorrection; 98 private CharSequence mOriginalWord; 99 private String mLowerOriginalWord; 100 101 // TODO: Remove these member variables by passing more context to addWord() callback method 102 private boolean mIsFirstCharCapitalized; 103 private boolean mIsAllUpperCase; 104 105 private int mCorrectionMode = CORRECTION_BASIC; 106 107 public Suggest(Context context, int[] dictionaryResId) { 108 mMainDict = new BinaryDictionary(context, dictionaryResId, DIC_MAIN); 109 initPool(); 110 } 111 112 public Suggest(Context context, ByteBuffer byteBuffer) { 113 mMainDict = new BinaryDictionary(context, byteBuffer, DIC_MAIN); 114 initPool(); 115 } 116 117 private void initPool() { 118 for (int i = 0; i < mPrefMaxSuggestions; i++) { 119 StringBuilder sb = new StringBuilder(getApproxMaxWordLength()); 120 mStringPool.add(sb); 121 } 122 } 123 124 public void setAutoTextEnabled(boolean enabled) { 125 mAutoTextEnabled = enabled; 126 } 127 128 public int getCorrectionMode() { 129 return mCorrectionMode; 130 } 131 132 public void setCorrectionMode(int mode) { 133 mCorrectionMode = mode; 134 } 135 136 public boolean hasMainDictionary() { 137 return mMainDict.getSize() > LARGE_DICTIONARY_THRESHOLD; 138 } 139 140 public int getApproxMaxWordLength() { 141 return APPROX_MAX_WORD_LENGTH; 142 } 143 144 /** 145 * Sets an optional user dictionary resource to be loaded. The user dictionary is consulted 146 * before the main dictionary, if set. 147 */ 148 public void setUserDictionary(Dictionary userDictionary) { 149 mUserDictionary = userDictionary; 150 } 151 152 /** 153 * Sets an optional contacts dictionary resource to be loaded. 154 */ 155 public void setContactsDictionary(Dictionary userDictionary) { 156 mContactsDictionary = userDictionary; 157 } 158 159 public void setAutoDictionary(Dictionary autoDictionary) { 160 mAutoDictionary = autoDictionary; 161 } 162 163 public void setUserBigramDictionary(Dictionary userBigramDictionary) { 164 mUserBigramDictionary = userBigramDictionary; 165 } 166 167 public void setAutoCompleteThreshold(double threshold) { 168 mAutoCompleteThreshold = threshold; 169 } 170 171 /** 172 * Number of suggestions to generate from the input key sequence. This has 173 * to be a number between 1 and 100 (inclusive). 174 * @param maxSuggestions 175 * @throws IllegalArgumentException if the number is out of range 176 */ 177 public void setMaxSuggestions(int maxSuggestions) { 178 if (maxSuggestions < 1 || maxSuggestions > 100) { 179 throw new IllegalArgumentException("maxSuggestions must be between 1 and 100"); 180 } 181 mPrefMaxSuggestions = maxSuggestions; 182 mPriorities = new int[mPrefMaxSuggestions]; 183 mBigramPriorities = new int[PREF_MAX_BIGRAMS]; 184 collectGarbage(mSuggestions, mPrefMaxSuggestions); 185 while (mStringPool.size() < mPrefMaxSuggestions) { 186 StringBuilder sb = new StringBuilder(getApproxMaxWordLength()); 187 mStringPool.add(sb); 188 } 189 } 190 191 private boolean haveSufficientCommonality(String original, CharSequence suggestion) { 192 final int originalLength = original.length(); 193 final int suggestionLength = suggestion.length(); 194 final int minLength = Math.min(originalLength, suggestionLength); 195 if (minLength <= 2) return true; 196 int matching = 0; 197 int lessMatching = 0; // Count matches if we skip one character 198 int i; 199 for (i = 0; i < minLength; i++) { 200 final char origChar = ExpandableDictionary.toLowerCase(original.charAt(i)); 201 if (origChar == ExpandableDictionary.toLowerCase(suggestion.charAt(i))) { 202 matching++; 203 lessMatching++; 204 } else if (i + 1 < suggestionLength 205 && origChar == ExpandableDictionary.toLowerCase(suggestion.charAt(i + 1))) { 206 lessMatching++; 207 } 208 } 209 matching = Math.max(matching, lessMatching); 210 211 if (minLength <= 4) { 212 return matching >= 2; 213 } else { 214 return matching > minLength / 2; 215 } 216 } 217 218 /** 219 * Returns a list of words that match the list of character codes passed in. 220 * This list will be overwritten the next time this function is called. 221 * @param view a view for retrieving the context for AutoText 222 * @param wordComposer contains what is currently being typed 223 * @param prevWordForBigram previous word (used only for bigram) 224 * @return list of suggestions. 225 */ 226 public List<CharSequence> getSuggestions(View view, WordComposer wordComposer, 227 boolean includeTypedWordIfValid, CharSequence prevWordForBigram) { 228 LatinImeLogger.onStartSuggestion(prevWordForBigram); 229 mHaveCorrection = false; 230 mIsFirstCharCapitalized = wordComposer.isFirstCharCapitalized(); 231 mIsAllUpperCase = wordComposer.isAllUpperCase(); 232 collectGarbage(mSuggestions, mPrefMaxSuggestions); 233 Arrays.fill(mPriorities, 0); 234 Arrays.fill(mNextLettersFrequencies, 0); 235 236 // Save a lowercase version of the original word 237 mOriginalWord = wordComposer.getTypedWord(); 238 if (mOriginalWord != null) { 239 final String mOriginalWordString = mOriginalWord.toString(); 240 mOriginalWord = mOriginalWordString; 241 mLowerOriginalWord = mOriginalWordString.toLowerCase(); 242 // Treating USER_TYPED as UNIGRAM suggestion for logging now. 243 LatinImeLogger.onAddSuggestedWord(mOriginalWordString, Suggest.DIC_USER_TYPED, 244 Dictionary.DataType.UNIGRAM); 245 } else { 246 mLowerOriginalWord = ""; 247 } 248 249 if (wordComposer.size() == 1 && (mCorrectionMode == CORRECTION_FULL_BIGRAM 250 || mCorrectionMode == CORRECTION_BASIC)) { 251 // At first character typed, search only the bigrams 252 Arrays.fill(mBigramPriorities, 0); 253 collectGarbage(mBigramSuggestions, PREF_MAX_BIGRAMS); 254 255 if (!TextUtils.isEmpty(prevWordForBigram)) { 256 CharSequence lowerPrevWord = prevWordForBigram.toString().toLowerCase(); 257 if (mMainDict.isValidWord(lowerPrevWord)) { 258 prevWordForBigram = lowerPrevWord; 259 } 260 if (mUserBigramDictionary != null) { 261 mUserBigramDictionary.getBigrams(wordComposer, prevWordForBigram, this, 262 mNextLettersFrequencies); 263 } 264 if (mContactsDictionary != null) { 265 mContactsDictionary.getBigrams(wordComposer, prevWordForBigram, this, 266 mNextLettersFrequencies); 267 } 268 if (mMainDict != null) { 269 mMainDict.getBigrams(wordComposer, prevWordForBigram, this, 270 mNextLettersFrequencies); 271 } 272 char currentChar = wordComposer.getTypedWord().charAt(0); 273 char currentCharUpper = Character.toUpperCase(currentChar); 274 int count = 0; 275 int bigramSuggestionSize = mBigramSuggestions.size(); 276 for (int i = 0; i < bigramSuggestionSize; i++) { 277 if (mBigramSuggestions.get(i).charAt(0) == currentChar 278 || mBigramSuggestions.get(i).charAt(0) == currentCharUpper) { 279 int poolSize = mStringPool.size(); 280 StringBuilder sb = poolSize > 0 ? 281 (StringBuilder) mStringPool.remove(poolSize - 1) 282 : new StringBuilder(getApproxMaxWordLength()); 283 sb.setLength(0); 284 sb.append(mBigramSuggestions.get(i)); 285 mSuggestions.add(count++, sb); 286 if (count > mPrefMaxSuggestions) break; 287 } 288 } 289 } 290 291 } else if (wordComposer.size() > 1) { 292 // At second character typed, search the unigrams (scores being affected by bigrams) 293 if (mUserDictionary != null || mContactsDictionary != null) { 294 if (mUserDictionary != null) { 295 mUserDictionary.getWords(wordComposer, this, mNextLettersFrequencies); 296 } 297 if (mContactsDictionary != null) { 298 mContactsDictionary.getWords(wordComposer, this, mNextLettersFrequencies); 299 } 300 301 if (mSuggestions.size() > 0 && isValidWord(mOriginalWord) 302 && (mCorrectionMode == CORRECTION_FULL 303 || mCorrectionMode == CORRECTION_FULL_BIGRAM)) { 304 mHaveCorrection = true; 305 } 306 } 307 mMainDict.getWords(wordComposer, this, mNextLettersFrequencies); 308 if ((mCorrectionMode == CORRECTION_FULL || mCorrectionMode == CORRECTION_FULL_BIGRAM) 309 && mSuggestions.size() > 0 && mPriorities.length > 0) { 310 // TODO: when the normalized score of the first suggestion is nearly equals to 311 // the normalized score of the second suggestion, behave less aggressive. 312 final double normalizedScore = LatinIMEUtil.calcNormalizedScore( 313 mOriginalWord, mSuggestions.get(0), mPriorities[0]); 314 if (normalizedScore >= mAutoCompleteThreshold) { 315 mHaveCorrection = true; 316 } 317 } 318 } 319 if (mOriginalWord != null) { 320 mSuggestions.add(0, mOriginalWord.toString()); 321 } 322 323 // Check if the first suggestion has a minimum number of characters in common 324 if (wordComposer.size() > 1 && mSuggestions.size() > 1 325 && (mCorrectionMode == CORRECTION_FULL 326 || mCorrectionMode == CORRECTION_FULL_BIGRAM)) { 327 if (!haveSufficientCommonality(mLowerOriginalWord, mSuggestions.get(1))) { 328 mHaveCorrection = false; 329 } 330 } 331 if (mAutoTextEnabled) { 332 int i = 0; 333 int max = 6; 334 // Don't autotext the suggestions from the dictionaries 335 if (mCorrectionMode == CORRECTION_BASIC) max = 1; 336 while (i < mSuggestions.size() && i < max) { 337 String suggestedWord = mSuggestions.get(i).toString().toLowerCase(); 338 CharSequence autoText = 339 AutoText.get(suggestedWord, 0, suggestedWord.length(), view); 340 // Is there an AutoText correction? 341 boolean canAdd = autoText != null; 342 // Is that correction already the current prediction (or original word)? 343 canAdd &= !TextUtils.equals(autoText, mSuggestions.get(i)); 344 // Is that correction already the next predicted word? 345 if (canAdd && i + 1 < mSuggestions.size() && mCorrectionMode != CORRECTION_BASIC) { 346 canAdd &= !TextUtils.equals(autoText, mSuggestions.get(i + 1)); 347 } 348 if (canAdd) { 349 mHaveCorrection = true; 350 mSuggestions.add(i + 1, autoText); 351 i++; 352 } 353 i++; 354 } 355 } 356 removeDupes(); 357 return mSuggestions; 358 } 359 360 public int[] getNextLettersFrequencies() { 361 return mNextLettersFrequencies; 362 } 363 364 private void removeDupes() { 365 final ArrayList<CharSequence> suggestions = mSuggestions; 366 if (suggestions.size() < 2) return; 367 int i = 1; 368 // Don't cache suggestions.size(), since we may be removing items 369 while (i < suggestions.size()) { 370 final CharSequence cur = suggestions.get(i); 371 // Compare each candidate with each previous candidate 372 for (int j = 0; j < i; j++) { 373 CharSequence previous = suggestions.get(j); 374 if (TextUtils.equals(cur, previous)) { 375 removeFromSuggestions(i); 376 i--; 377 break; 378 } 379 } 380 i++; 381 } 382 } 383 384 private void removeFromSuggestions(int index) { 385 CharSequence garbage = mSuggestions.remove(index); 386 if (garbage != null && garbage instanceof StringBuilder) { 387 mStringPool.add(garbage); 388 } 389 } 390 391 public boolean hasMinimalCorrection() { 392 return mHaveCorrection; 393 } 394 395 private boolean compareCaseInsensitive(final String mLowerOriginalWord, 396 final char[] word, final int offset, final int length) { 397 final int originalLength = mLowerOriginalWord.length(); 398 if (originalLength == length && Character.isUpperCase(word[offset])) { 399 for (int i = 0; i < originalLength; i++) { 400 if (mLowerOriginalWord.charAt(i) != Character.toLowerCase(word[offset+i])) { 401 return false; 402 } 403 } 404 return true; 405 } 406 return false; 407 } 408 409 public boolean addWord(final char[] word, final int offset, final int length, int freq, 410 final int dicTypeId, final Dictionary.DataType dataType) { 411 Dictionary.DataType dataTypeForLog = dataType; 412 ArrayList<CharSequence> suggestions; 413 int[] priorities; 414 int prefMaxSuggestions; 415 if(dataType == Dictionary.DataType.BIGRAM) { 416 suggestions = mBigramSuggestions; 417 priorities = mBigramPriorities; 418 prefMaxSuggestions = PREF_MAX_BIGRAMS; 419 } else { 420 suggestions = mSuggestions; 421 priorities = mPriorities; 422 prefMaxSuggestions = mPrefMaxSuggestions; 423 } 424 425 int pos = 0; 426 427 // Check if it's the same word, only caps are different 428 if (compareCaseInsensitive(mLowerOriginalWord, word, offset, length)) { 429 pos = 0; 430 } else { 431 if (dataType == Dictionary.DataType.UNIGRAM) { 432 // Check if the word was already added before (by bigram data) 433 int bigramSuggestion = searchBigramSuggestion(word,offset,length); 434 if(bigramSuggestion >= 0) { 435 dataTypeForLog = Dictionary.DataType.BIGRAM; 436 // turn freq from bigram into multiplier specified above 437 double multiplier = (((double) mBigramPriorities[bigramSuggestion]) 438 / MAXIMUM_BIGRAM_FREQUENCY) 439 * (BIGRAM_MULTIPLIER_MAX - BIGRAM_MULTIPLIER_MIN) 440 + BIGRAM_MULTIPLIER_MIN; 441 /* Log.d(TAG,"bigram num: " + bigramSuggestion 442 + " wordB: " + mBigramSuggestions.get(bigramSuggestion).toString() 443 + " currentPriority: " + freq + " bigramPriority: " 444 + mBigramPriorities[bigramSuggestion] 445 + " multiplier: " + multiplier); */ 446 freq = (int)Math.round((freq * multiplier)); 447 } 448 } 449 450 // Check the last one's priority and bail 451 if (priorities[prefMaxSuggestions - 1] >= freq) return true; 452 while (pos < prefMaxSuggestions) { 453 if (priorities[pos] < freq 454 || (priorities[pos] == freq && length < suggestions.get(pos).length())) { 455 break; 456 } 457 pos++; 458 } 459 } 460 if (pos >= prefMaxSuggestions) { 461 return true; 462 } 463 464 System.arraycopy(priorities, pos, priorities, pos + 1, 465 prefMaxSuggestions - pos - 1); 466 priorities[pos] = freq; 467 int poolSize = mStringPool.size(); 468 StringBuilder sb = poolSize > 0 ? (StringBuilder) mStringPool.remove(poolSize - 1) 469 : new StringBuilder(getApproxMaxWordLength()); 470 sb.setLength(0); 471 if (mIsAllUpperCase) { 472 sb.append(new String(word, offset, length).toUpperCase()); 473 } else if (mIsFirstCharCapitalized) { 474 sb.append(Character.toUpperCase(word[offset])); 475 if (length > 1) { 476 sb.append(word, offset + 1, length - 1); 477 } 478 } else { 479 sb.append(word, offset, length); 480 } 481 suggestions.add(pos, sb); 482 if (suggestions.size() > prefMaxSuggestions) { 483 CharSequence garbage = suggestions.remove(prefMaxSuggestions); 484 if (garbage instanceof StringBuilder) { 485 mStringPool.add(garbage); 486 } 487 } else { 488 LatinImeLogger.onAddSuggestedWord(sb.toString(), dicTypeId, dataTypeForLog); 489 } 490 return true; 491 } 492 493 private int searchBigramSuggestion(final char[] word, final int offset, final int length) { 494 // TODO This is almost O(n^2). Might need fix. 495 // search whether the word appeared in bigram data 496 int bigramSuggestSize = mBigramSuggestions.size(); 497 for(int i = 0; i < bigramSuggestSize; i++) { 498 if(mBigramSuggestions.get(i).length() == length) { 499 boolean chk = true; 500 for(int j = 0; j < length; j++) { 501 if(mBigramSuggestions.get(i).charAt(j) != word[offset+j]) { 502 chk = false; 503 break; 504 } 505 } 506 if(chk) return i; 507 } 508 } 509 510 return -1; 511 } 512 513 public boolean isValidWord(final CharSequence word) { 514 if (word == null || word.length() == 0) { 515 return false; 516 } 517 return mMainDict.isValidWord(word) 518 || (mUserDictionary != null && mUserDictionary.isValidWord(word)) 519 || (mAutoDictionary != null && mAutoDictionary.isValidWord(word)) 520 || (mContactsDictionary != null && mContactsDictionary.isValidWord(word)); 521 } 522 523 private void collectGarbage(ArrayList<CharSequence> suggestions, int prefMaxSuggestions) { 524 int poolSize = mStringPool.size(); 525 int garbageSize = suggestions.size(); 526 while (poolSize < prefMaxSuggestions && garbageSize > 0) { 527 CharSequence garbage = suggestions.get(garbageSize - 1); 528 if (garbage != null && garbage instanceof StringBuilder) { 529 mStringPool.add(garbage); 530 poolSize++; 531 } 532 garbageSize--; 533 } 534 if (poolSize == prefMaxSuggestions + 1) { 535 Log.w("Suggest", "String pool got too big: " + poolSize); 536 } 537 suggestions.clear(); 538 } 539 540 public void close() { 541 if (mMainDict != null) { 542 mMainDict.close(); 543 } 544 } 545} 546