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