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 #include <cassert> 18 #include <cstring> 19 20 #define LOG_TAG "LatinIME: unigram_dictionary.cpp" 21 22 #include "binary_format.h" 23 #include "char_utils.h" 24 #include "defines.h" 25 #include "dictionary.h" 26 #include "proximity_info.h" 27 #include "terminal_attributes.h" 28 #include "unigram_dictionary.h" 29 #include "words_priority_queue.h" 30 #include "words_priority_queue_pool.h" 31 32 namespace latinime { 33 34 const UnigramDictionary::digraph_t UnigramDictionary::GERMAN_UMLAUT_DIGRAPHS[] = 35 { { 'a', 'e', 0x00E4 }, // U+00E4 : LATIN SMALL LETTER A WITH DIAERESIS 36 { 'o', 'e', 0x00F6 }, // U+00F6 : LATIN SMALL LETTER O WITH DIAERESIS 37 { 'u', 'e', 0x00FC } }; // U+00FC : LATIN SMALL LETTER U WITH DIAERESIS 38 39 const UnigramDictionary::digraph_t UnigramDictionary::FRENCH_LIGATURES_DIGRAPHS[] = 40 { { 'a', 'e', 0x00E6 }, // U+00E6 : LATIN SMALL LETTER AE 41 { 'o', 'e', 0x0153 } }; // U+0153 : LATIN SMALL LIGATURE OE 42 43 // TODO: check the header 44 UnigramDictionary::UnigramDictionary(const uint8_t *const streamStart, int typedLetterMultiplier, 45 int fullWordMultiplier, int maxWordLength, int maxWords, const unsigned int flags) 46 : DICT_ROOT(streamStart), MAX_WORD_LENGTH(maxWordLength), MAX_WORDS(maxWords), 47 TYPED_LETTER_MULTIPLIER(typedLetterMultiplier), FULL_WORD_MULTIPLIER(fullWordMultiplier), 48 // TODO : remove this variable. 49 ROOT_POS(0), 50 BYTES_IN_ONE_CHAR(sizeof(int)), 51 MAX_DIGRAPH_SEARCH_DEPTH(DEFAULT_MAX_DIGRAPH_SEARCH_DEPTH), FLAGS(flags) { 52 if (DEBUG_DICT) { 53 AKLOGI("UnigramDictionary - constructor"); 54 } 55 } 56 57 UnigramDictionary::~UnigramDictionary() { 58 } 59 60 static inline unsigned int getCodesBufferSize(const int *codes, const int codesSize) { 61 return static_cast<unsigned int>(sizeof(*codes)) * codesSize; 62 } 63 64 // TODO: This needs to take a const unsigned short* and not tinker with its contents 65 static inline void addWord(unsigned short *word, int length, int frequency, 66 WordsPriorityQueue *queue, int type) { 67 queue->push(frequency, word, length, type); 68 } 69 70 // Return the replacement code point for a digraph, or 0 if none. 71 int UnigramDictionary::getDigraphReplacement(const int *codes, const int i, const int codesSize, 72 const digraph_t *const digraphs, const unsigned int digraphsSize) const { 73 74 // There can't be a digraph if we don't have at least 2 characters to examine 75 if (i + 2 > codesSize) return false; 76 77 // Search for the first char of some digraph 78 int lastDigraphIndex = -1; 79 const int thisChar = codes[i]; 80 for (lastDigraphIndex = digraphsSize - 1; lastDigraphIndex >= 0; --lastDigraphIndex) { 81 if (thisChar == digraphs[lastDigraphIndex].first) break; 82 } 83 // No match: return early 84 if (lastDigraphIndex < 0) return 0; 85 86 // It's an interesting digraph if the second char matches too. 87 if (digraphs[lastDigraphIndex].second == codes[i + 1]) { 88 return digraphs[lastDigraphIndex].replacement; 89 } else { 90 return 0; 91 } 92 } 93 94 // Mostly the same arguments as the non-recursive version, except: 95 // codes is the original value. It points to the start of the work buffer, and gets passed as is. 96 // codesSize is the size of the user input (thus, it is the size of codesSrc). 97 // codesDest is the current point in the work buffer. 98 // codesSrc is the current point in the user-input, original, content-unmodified buffer. 99 // codesRemain is the remaining size in codesSrc. 100 void UnigramDictionary::getWordWithDigraphSuggestionsRec(ProximityInfo *proximityInfo, 101 const int *xcoordinates, const int *ycoordinates, const int *codesBuffer, 102 int *xCoordinatesBuffer, int *yCoordinatesBuffer, 103 const int codesBufferSize, const std::map<int, int> *bigramMap, const uint8_t *bigramFilter, 104 const bool useFullEditDistance, const int *codesSrc, 105 const int codesRemain, const int currentDepth, int *codesDest, Correction *correction, 106 WordsPriorityQueuePool *queuePool, 107 const digraph_t *const digraphs, const unsigned int digraphsSize) const { 108 109 const int startIndex = static_cast<int>(codesDest - codesBuffer); 110 if (currentDepth < MAX_DIGRAPH_SEARCH_DEPTH) { 111 for (int i = 0; i < codesRemain; ++i) { 112 xCoordinatesBuffer[startIndex + i] = xcoordinates[codesBufferSize - codesRemain + i]; 113 yCoordinatesBuffer[startIndex + i] = ycoordinates[codesBufferSize - codesRemain + i]; 114 const int replacementCodePoint = 115 getDigraphReplacement(codesSrc, i, codesRemain, digraphs, digraphsSize); 116 if (0 != replacementCodePoint) { 117 // Found a digraph. We will try both spellings. eg. the word is "pruefen" 118 119 // Copy the word up to the first char of the digraph, including proximity chars, 120 // and overwrite the primary code with the replacement code point. Then, continue 121 // processing on the remaining part of the word, skipping the second char of the 122 // digraph. 123 // In our example, copy "pru", replace "u" with the version with the diaeresis and 124 // continue running on "fen". 125 // Make i the index of the second char of the digraph for simplicity. Forgetting 126 // to do that results in an infinite recursion so take care! 127 ++i; 128 memcpy(codesDest, codesSrc, i * BYTES_IN_ONE_CHAR); 129 codesDest[(i - 1) * (BYTES_IN_ONE_CHAR / sizeof(codesDest[0]))] = 130 replacementCodePoint; 131 getWordWithDigraphSuggestionsRec(proximityInfo, xcoordinates, ycoordinates, 132 codesBuffer, xCoordinatesBuffer, yCoordinatesBuffer, codesBufferSize, 133 bigramMap, bigramFilter, useFullEditDistance, codesSrc + i + 1, 134 codesRemain - i - 1, currentDepth + 1, codesDest + i, correction, 135 queuePool, digraphs, digraphsSize); 136 137 // Copy the second char of the digraph in place, then continue processing on 138 // the remaining part of the word. 139 // In our example, after "pru" in the buffer copy the "e", and continue on "fen" 140 memcpy(codesDest + i, codesSrc + i, BYTES_IN_ONE_CHAR); 141 getWordWithDigraphSuggestionsRec(proximityInfo, xcoordinates, ycoordinates, 142 codesBuffer, xCoordinatesBuffer, yCoordinatesBuffer, codesBufferSize, 143 bigramMap, bigramFilter, useFullEditDistance, codesSrc + i, codesRemain - i, 144 currentDepth + 1, codesDest + i, correction, queuePool, digraphs, 145 digraphsSize); 146 return; 147 } 148 } 149 } 150 151 // If we come here, we hit the end of the word: let's check it against the dictionary. 152 // In our example, we'll come here once for "prufen" and then once for "pruefen". 153 // If the word contains several digraphs, we'll come it for the product of them. 154 // eg. if the word is "ueberpruefen" we'll test, in order, against 155 // "uberprufen", "uberpruefen", "ueberprufen", "ueberpruefen". 156 const unsigned int remainingBytes = BYTES_IN_ONE_CHAR * codesRemain; 157 if (0 != remainingBytes) { 158 memcpy(codesDest, codesSrc, remainingBytes); 159 memcpy(&xCoordinatesBuffer[startIndex], &xcoordinates[codesBufferSize - codesRemain], 160 sizeof(int) * codesRemain); 161 memcpy(&yCoordinatesBuffer[startIndex], &ycoordinates[codesBufferSize - codesRemain], 162 sizeof(int) * codesRemain); 163 } 164 165 getWordSuggestions(proximityInfo, xCoordinatesBuffer, yCoordinatesBuffer, codesBuffer, 166 startIndex + codesRemain, bigramMap, bigramFilter, useFullEditDistance, correction, 167 queuePool); 168 } 169 170 // bigramMap contains the association <bigram address> -> <bigram frequency> 171 // bigramFilter is a bloom filter for fast rejection: see functions setInFilter and isInFilter 172 // in bigram_dictionary.cpp 173 int UnigramDictionary::getSuggestions(ProximityInfo *proximityInfo, const int *xcoordinates, 174 const int *ycoordinates, const int *codes, const int codesSize, 175 const std::map<int, int> *bigramMap, const uint8_t *bigramFilter, 176 const bool useFullEditDistance, unsigned short *outWords, int *frequencies, 177 int *outputTypes) const { 178 179 WordsPriorityQueuePool queuePool(MAX_WORDS, SUB_QUEUE_MAX_WORDS, MAX_WORD_LENGTH); 180 queuePool.clearAll(); 181 Correction masterCorrection; 182 masterCorrection.resetCorrection(); 183 if (BinaryFormat::REQUIRES_GERMAN_UMLAUT_PROCESSING & FLAGS) 184 { // Incrementally tune the word and try all possibilities 185 int codesBuffer[getCodesBufferSize(codes, codesSize)]; 186 int xCoordinatesBuffer[codesSize]; 187 int yCoordinatesBuffer[codesSize]; 188 getWordWithDigraphSuggestionsRec(proximityInfo, xcoordinates, ycoordinates, codesBuffer, 189 xCoordinatesBuffer, yCoordinatesBuffer, codesSize, bigramMap, bigramFilter, 190 useFullEditDistance, codes, codesSize, 0, codesBuffer, &masterCorrection, 191 &queuePool, GERMAN_UMLAUT_DIGRAPHS, 192 sizeof(GERMAN_UMLAUT_DIGRAPHS) / sizeof(GERMAN_UMLAUT_DIGRAPHS[0])); 193 } else if (BinaryFormat::REQUIRES_FRENCH_LIGATURES_PROCESSING & FLAGS) { 194 int codesBuffer[getCodesBufferSize(codes, codesSize)]; 195 int xCoordinatesBuffer[codesSize]; 196 int yCoordinatesBuffer[codesSize]; 197 getWordWithDigraphSuggestionsRec(proximityInfo, xcoordinates, ycoordinates, codesBuffer, 198 xCoordinatesBuffer, yCoordinatesBuffer, codesSize, bigramMap, bigramFilter, 199 useFullEditDistance, codes, codesSize, 0, codesBuffer, &masterCorrection, 200 &queuePool, FRENCH_LIGATURES_DIGRAPHS, 201 sizeof(FRENCH_LIGATURES_DIGRAPHS) / sizeof(FRENCH_LIGATURES_DIGRAPHS[0])); 202 } else { // Normal processing 203 getWordSuggestions(proximityInfo, xcoordinates, ycoordinates, codes, codesSize, 204 bigramMap, bigramFilter, useFullEditDistance, &masterCorrection, &queuePool); 205 } 206 207 PROF_START(20); 208 if (DEBUG_DICT) { 209 float ns = queuePool.getMasterQueue()->getHighestNormalizedScore( 210 masterCorrection.getPrimaryInputWord(), codesSize, 0, 0, 0); 211 ns += 0; 212 AKLOGI("Max normalized score = %f", ns); 213 } 214 const int suggestedWordsCount = 215 queuePool.getMasterQueue()->outputSuggestions(masterCorrection.getPrimaryInputWord(), 216 codesSize, frequencies, outWords, outputTypes); 217 218 if (DEBUG_DICT) { 219 float ns = queuePool.getMasterQueue()->getHighestNormalizedScore( 220 masterCorrection.getPrimaryInputWord(), codesSize, 0, 0, 0); 221 ns += 0; 222 AKLOGI("Returning %d words", suggestedWordsCount); 223 /// Print the returned words 224 for (int j = 0; j < suggestedWordsCount; ++j) { 225 short unsigned int *w = outWords + j * MAX_WORD_LENGTH; 226 char s[MAX_WORD_LENGTH]; 227 for (int i = 0; i <= MAX_WORD_LENGTH; i++) s[i] = w[i]; 228 (void)s; // To suppress compiler warning 229 AKLOGI("%s %i", s, frequencies[j]); 230 } 231 } 232 PROF_END(20); 233 PROF_CLOSE; 234 return suggestedWordsCount; 235 } 236 237 void UnigramDictionary::getWordSuggestions(ProximityInfo *proximityInfo, 238 const int *xcoordinates, const int *ycoordinates, const int *codes, 239 const int inputSize, const std::map<int, int> *bigramMap, const uint8_t *bigramFilter, 240 const bool useFullEditDistance, Correction *correction, 241 WordsPriorityQueuePool *queuePool) const { 242 243 PROF_OPEN; 244 PROF_START(0); 245 PROF_END(0); 246 247 PROF_START(1); 248 getOneWordSuggestions(proximityInfo, xcoordinates, ycoordinates, codes, bigramMap, bigramFilter, 249 useFullEditDistance, inputSize, correction, queuePool); 250 PROF_END(1); 251 252 PROF_START(2); 253 // Note: This line is intentionally left blank 254 PROF_END(2); 255 256 PROF_START(3); 257 // Note: This line is intentionally left blank 258 PROF_END(3); 259 260 PROF_START(4); 261 bool hasAutoCorrectionCandidate = false; 262 WordsPriorityQueue *masterQueue = queuePool->getMasterQueue(); 263 if (masterQueue->size() > 0) { 264 float nsForMaster = masterQueue->getHighestNormalizedScore( 265 correction->getPrimaryInputWord(), inputSize, 0, 0, 0); 266 hasAutoCorrectionCandidate = (nsForMaster > START_TWO_WORDS_CORRECTION_THRESHOLD); 267 } 268 PROF_END(4); 269 270 PROF_START(5); 271 // Multiple word suggestions 272 if (SUGGEST_MULTIPLE_WORDS 273 && inputSize >= MIN_USER_TYPED_LENGTH_FOR_MULTIPLE_WORD_SUGGESTION) { 274 getSplitMultipleWordsSuggestions(proximityInfo, xcoordinates, ycoordinates, codes, 275 useFullEditDistance, inputSize, correction, queuePool, 276 hasAutoCorrectionCandidate); 277 } 278 PROF_END(5); 279 280 PROF_START(6); 281 // Note: This line is intentionally left blank 282 PROF_END(6); 283 284 if (DEBUG_DICT) { 285 queuePool->dumpSubQueue1TopSuggestions(); 286 for (int i = 0; i < SUB_QUEUE_MAX_COUNT; ++i) { 287 WordsPriorityQueue *queue = queuePool->getSubQueue(FIRST_WORD_INDEX, i); 288 if (queue->size() > 0) { 289 WordsPriorityQueue::SuggestedWord *sw = queue->top(); 290 const int score = sw->mScore; 291 const unsigned short *word = sw->mWord; 292 const int wordLength = sw->mWordLength; 293 float ns = Correction::RankingAlgorithm::calcNormalizedScore( 294 correction->getPrimaryInputWord(), i, word, wordLength, score); 295 ns += 0; 296 AKLOGI("--- TOP SUB WORDS for %d --- %d %f [%d]", i, score, ns, 297 (ns > TWO_WORDS_CORRECTION_WITH_OTHER_ERROR_THRESHOLD)); 298 DUMP_WORD(correction->getPrimaryInputWord(), i); 299 DUMP_WORD(word, wordLength); 300 } 301 } 302 } 303 } 304 305 void UnigramDictionary::initSuggestions(ProximityInfo *proximityInfo, const int *xCoordinates, 306 const int *yCoordinates, const int *codes, const int inputSize, 307 Correction *correction) const { 308 if (DEBUG_DICT) { 309 AKLOGI("initSuggest"); 310 DUMP_WORD_INT(codes, inputSize); 311 } 312 correction->initInputParams(proximityInfo, codes, inputSize, xCoordinates, yCoordinates); 313 const int maxDepth = min(inputSize * MAX_DEPTH_MULTIPLIER, MAX_WORD_LENGTH); 314 correction->initCorrection(proximityInfo, inputSize, maxDepth); 315 } 316 317 static const char SPACE = ' '; 318 319 void UnigramDictionary::getOneWordSuggestions(ProximityInfo *proximityInfo, 320 const int *xcoordinates, const int *ycoordinates, const int *codes, 321 const std::map<int, int> *bigramMap, const uint8_t *bigramFilter, 322 const bool useFullEditDistance, const int inputSize, 323 Correction *correction, WordsPriorityQueuePool *queuePool) const { 324 initSuggestions(proximityInfo, xcoordinates, ycoordinates, codes, inputSize, correction); 325 getSuggestionCandidates(useFullEditDistance, inputSize, bigramMap, bigramFilter, correction, 326 queuePool, true /* doAutoCompletion */, DEFAULT_MAX_ERRORS, FIRST_WORD_INDEX); 327 } 328 329 void UnigramDictionary::getSuggestionCandidates(const bool useFullEditDistance, 330 const int inputSize, const std::map<int, int> *bigramMap, const uint8_t *bigramFilter, 331 Correction *correction, WordsPriorityQueuePool *queuePool, 332 const bool doAutoCompletion, const int maxErrors, const int currentWordIndex) const { 333 uint8_t totalTraverseCount = correction->pushAndGetTotalTraverseCount(); 334 if (DEBUG_DICT) { 335 AKLOGI("Traverse count %d", totalTraverseCount); 336 } 337 if (totalTraverseCount > MULTIPLE_WORDS_SUGGESTION_MAX_TOTAL_TRAVERSE_COUNT) { 338 if (DEBUG_DICT) { 339 AKLOGI("Abort traversing %d", totalTraverseCount); 340 } 341 return; 342 } 343 // TODO: Remove setCorrectionParams 344 correction->setCorrectionParams(0, 0, 0, 345 -1 /* spaceProximityPos */, -1 /* missingSpacePos */, useFullEditDistance, 346 doAutoCompletion, maxErrors); 347 int rootPosition = ROOT_POS; 348 // Get the number of children of root, then increment the position 349 int childCount = BinaryFormat::getGroupCountAndForwardPointer(DICT_ROOT, &rootPosition); 350 int outputIndex = 0; 351 352 correction->initCorrectionState(rootPosition, childCount, (inputSize <= 0)); 353 354 // Depth first search 355 while (outputIndex >= 0) { 356 if (correction->initProcessState(outputIndex)) { 357 int siblingPos = correction->getTreeSiblingPos(outputIndex); 358 int firstChildPos; 359 360 const bool needsToTraverseChildrenNodes = processCurrentNode(siblingPos, 361 bigramMap, bigramFilter, correction, &childCount, &firstChildPos, &siblingPos, 362 queuePool, currentWordIndex); 363 // Update next sibling pos 364 correction->setTreeSiblingPos(outputIndex, siblingPos); 365 366 if (needsToTraverseChildrenNodes) { 367 // Goes to child node 368 outputIndex = correction->goDownTree(outputIndex, childCount, firstChildPos); 369 } 370 } else { 371 // Goes to parent sibling node 372 outputIndex = correction->getTreeParentIndex(outputIndex); 373 } 374 } 375 } 376 377 inline void UnigramDictionary::onTerminal(const int probability, 378 const TerminalAttributes& terminalAttributes, Correction *correction, 379 WordsPriorityQueuePool *queuePool, const bool addToMasterQueue, 380 const int currentWordIndex) const { 381 const int inputIndex = correction->getInputIndex(); 382 const bool addToSubQueue = inputIndex < SUB_QUEUE_MAX_COUNT; 383 384 int wordLength; 385 unsigned short *wordPointer; 386 387 if ((currentWordIndex == FIRST_WORD_INDEX) && addToMasterQueue) { 388 WordsPriorityQueue *masterQueue = queuePool->getMasterQueue(); 389 const int finalProbability = 390 correction->getFinalProbability(probability, &wordPointer, &wordLength); 391 392 if (0 != finalProbability && !terminalAttributes.isBlacklistedOrNotAWord()) { 393 // If the probability is 0, we don't want to add this word. However we still 394 // want to add its shortcuts (including a possible whitelist entry) if any. 395 // Furthermore, if this is not a word (shortcut only for example) or a blacklisted 396 // entry then we never want to suggest this. 397 addWord(wordPointer, wordLength, finalProbability, masterQueue, 398 Dictionary::KIND_CORRECTION); 399 } 400 401 const int shortcutProbability = finalProbability > 0 ? finalProbability - 1 : 0; 402 // Please note that the shortcut candidates will be added to the master queue only. 403 TerminalAttributes::ShortcutIterator iterator = 404 terminalAttributes.getShortcutIterator(); 405 while (iterator.hasNextShortcutTarget()) { 406 // TODO: addWord only supports weak ordering, meaning we have no means 407 // to control the order of the shortcuts relative to one another or to the word. 408 // We need to either modulate the probability of each shortcut according 409 // to its own shortcut probability or to make the queue 410 // so that the insert order is protected inside the queue for words 411 // with the same score. For the moment we use -1 to make sure the shortcut will 412 // never be in front of the word. 413 uint16_t shortcutTarget[MAX_WORD_LENGTH_INTERNAL]; 414 int shortcutFrequency; 415 const int shortcutTargetStringLength = iterator.getNextShortcutTarget( 416 MAX_WORD_LENGTH_INTERNAL, shortcutTarget, &shortcutFrequency); 417 int shortcutScore; 418 int kind; 419 if (shortcutFrequency == BinaryFormat::WHITELIST_SHORTCUT_FREQUENCY 420 && correction->sameAsTyped()) { 421 shortcutScore = S_INT_MAX; 422 kind = Dictionary::KIND_WHITELIST; 423 } else { 424 shortcutScore = shortcutProbability; 425 kind = Dictionary::KIND_CORRECTION; 426 } 427 addWord(shortcutTarget, shortcutTargetStringLength, shortcutScore, 428 masterQueue, kind); 429 } 430 } 431 432 // We only allow two words + other error correction for words with SUB_QUEUE_MIN_WORD_LENGTH 433 // or more length. 434 if (inputIndex >= SUB_QUEUE_MIN_WORD_LENGTH && addToSubQueue) { 435 WordsPriorityQueue *subQueue; 436 subQueue = queuePool->getSubQueue(currentWordIndex, inputIndex); 437 if (!subQueue) { 438 return; 439 } 440 const int finalProbability = correction->getFinalProbabilityForSubQueue( 441 probability, &wordPointer, &wordLength, inputIndex); 442 addWord(wordPointer, wordLength, finalProbability, subQueue, Dictionary::KIND_CORRECTION); 443 } 444 } 445 446 int UnigramDictionary::getSubStringSuggestion( 447 ProximityInfo *proximityInfo, const int *xcoordinates, const int *ycoordinates, 448 const int *codes, const bool useFullEditDistance, Correction *correction, 449 WordsPriorityQueuePool *queuePool, const int inputSize, 450 const bool hasAutoCorrectionCandidate, const int currentWordIndex, 451 const int inputWordStartPos, const int inputWordLength, 452 const int outputWordStartPos, const bool isSpaceProximity, int *freqArray, 453 int *wordLengthArray, unsigned short *outputWord, int *outputWordLength) const { 454 if (inputWordLength > MULTIPLE_WORDS_SUGGESTION_MAX_WORD_LENGTH) { 455 return FLAG_MULTIPLE_SUGGEST_ABORT; 456 } 457 458 ///////////////////////////////////////////// 459 // safety net for multiple word suggestion // 460 // TODO: Remove this safety net // 461 ///////////////////////////////////////////// 462 int smallWordCount = 0; 463 int singleLetterWordCount = 0; 464 if (inputWordLength == 1) { 465 ++singleLetterWordCount; 466 } 467 if (inputWordLength <= 2) { 468 // small word == single letter or 2-letter word 469 ++smallWordCount; 470 } 471 for (int i = 0; i < currentWordIndex; ++i) { 472 const int length = wordLengthArray[i]; 473 if (length == 1) { 474 ++singleLetterWordCount; 475 // Safety net to avoid suggesting sequential single letter words 476 if (i < (currentWordIndex - 1)) { 477 if (wordLengthArray[i + 1] == 1) { 478 return FLAG_MULTIPLE_SUGGEST_ABORT; 479 } 480 } else if (inputWordLength == 1) { 481 return FLAG_MULTIPLE_SUGGEST_ABORT; 482 } 483 } 484 if (length <= 2) { 485 ++smallWordCount; 486 } 487 // Safety net to avoid suggesting multiple words with many (4 or more, for now) small words 488 if (singleLetterWordCount >= 3 || smallWordCount >= 4) { 489 return FLAG_MULTIPLE_SUGGEST_ABORT; 490 } 491 } 492 ////////////////////////////////////////////// 493 // TODO: Remove the safety net above // 494 ////////////////////////////////////////////// 495 496 unsigned short *tempOutputWord = 0; 497 int nextWordLength = 0; 498 // TODO: Optimize init suggestion 499 initSuggestions(proximityInfo, xcoordinates, ycoordinates, codes, 500 inputSize, correction); 501 502 unsigned short word[MAX_WORD_LENGTH_INTERNAL]; 503 int freq = getMostFrequentWordLike( 504 inputWordStartPos, inputWordLength, correction, word); 505 if (freq > 0) { 506 nextWordLength = inputWordLength; 507 tempOutputWord = word; 508 } else if (!hasAutoCorrectionCandidate) { 509 if (inputWordStartPos > 0) { 510 const int offset = inputWordStartPos; 511 initSuggestions(proximityInfo, &xcoordinates[offset], &ycoordinates[offset], 512 codes + offset, inputWordLength, correction); 513 queuePool->clearSubQueue(currentWordIndex); 514 // TODO: pass the bigram list for substring suggestion 515 getSuggestionCandidates(useFullEditDistance, inputWordLength, 516 0 /* bigramMap */, 0 /* bigramFilter */, correction, queuePool, 517 false /* doAutoCompletion */, MAX_ERRORS_FOR_TWO_WORDS, currentWordIndex); 518 if (DEBUG_DICT) { 519 if (currentWordIndex < MULTIPLE_WORDS_SUGGESTION_MAX_WORDS) { 520 AKLOGI("Dump word candidates(%d) %d", currentWordIndex, inputWordLength); 521 for (int i = 0; i < SUB_QUEUE_MAX_COUNT; ++i) { 522 queuePool->getSubQueue(currentWordIndex, i)->dumpTopWord(); 523 } 524 } 525 } 526 } 527 WordsPriorityQueue *queue = queuePool->getSubQueue(currentWordIndex, inputWordLength); 528 // TODO: Return the correct value depending on doAutoCompletion 529 if (!queue || queue->size() <= 0) { 530 return FLAG_MULTIPLE_SUGGEST_ABORT; 531 } 532 int score = 0; 533 const float ns = queue->getHighestNormalizedScore( 534 correction->getPrimaryInputWord(), inputWordLength, 535 &tempOutputWord, &score, &nextWordLength); 536 if (DEBUG_DICT) { 537 AKLOGI("NS(%d) = %f, Score = %d", currentWordIndex, ns, score); 538 } 539 // Two words correction won't be done if the score of the first word doesn't exceed the 540 // threshold. 541 if (ns < TWO_WORDS_CORRECTION_WITH_OTHER_ERROR_THRESHOLD 542 || nextWordLength < SUB_QUEUE_MIN_WORD_LENGTH) { 543 return FLAG_MULTIPLE_SUGGEST_SKIP; 544 } 545 freq = score >> (nextWordLength + TWO_WORDS_PLUS_OTHER_ERROR_CORRECTION_DEMOTION_DIVIDER); 546 } 547 if (DEBUG_DICT) { 548 AKLOGI("Freq(%d): %d, length: %d, input length: %d, input start: %d (%d)", 549 currentWordIndex, freq, nextWordLength, inputWordLength, inputWordStartPos, 550 (currentWordIndex > 0) ? wordLengthArray[0] : 0); 551 } 552 if (freq <= 0 || nextWordLength <= 0 553 || MAX_WORD_LENGTH <= (outputWordStartPos + nextWordLength)) { 554 return FLAG_MULTIPLE_SUGGEST_SKIP; 555 } 556 for (int i = 0; i < nextWordLength; ++i) { 557 outputWord[outputWordStartPos + i] = tempOutputWord[i]; 558 } 559 560 // Put output values 561 freqArray[currentWordIndex] = freq; 562 // TODO: put output length instead of input length 563 wordLengthArray[currentWordIndex] = inputWordLength; 564 const int tempOutputWordLength = outputWordStartPos + nextWordLength; 565 if (outputWordLength) { 566 *outputWordLength = tempOutputWordLength; 567 } 568 569 if ((inputWordStartPos + inputWordLength) < inputSize) { 570 if (outputWordStartPos + nextWordLength >= MAX_WORD_LENGTH) { 571 return FLAG_MULTIPLE_SUGGEST_SKIP; 572 } 573 outputWord[tempOutputWordLength] = SPACE; 574 if (outputWordLength) { 575 ++*outputWordLength; 576 } 577 } else if (currentWordIndex >= 1) { 578 // TODO: Handle 3 or more words 579 const int pairFreq = correction->getFreqForSplitMultipleWords( 580 freqArray, wordLengthArray, currentWordIndex + 1, isSpaceProximity, outputWord); 581 if (DEBUG_DICT) { 582 DUMP_WORD(outputWord, tempOutputWordLength); 583 for (int i = 0; i < currentWordIndex + 1; ++i) { 584 AKLOGI("Split %d,%d words: freq = %d, length = %d", i, currentWordIndex + 1, 585 freqArray[i], wordLengthArray[i]); 586 } 587 AKLOGI("Split two words: freq = %d, length = %d, %d, isSpace ? %d", pairFreq, 588 inputSize, tempOutputWordLength, isSpaceProximity); 589 } 590 addWord(outputWord, tempOutputWordLength, pairFreq, queuePool->getMasterQueue(), 591 Dictionary::KIND_CORRECTION); 592 } 593 return FLAG_MULTIPLE_SUGGEST_CONTINUE; 594 } 595 596 void UnigramDictionary::getMultiWordsSuggestionRec(ProximityInfo *proximityInfo, 597 const int *xcoordinates, const int *ycoordinates, const int *codes, 598 const bool useFullEditDistance, const int inputSize, Correction *correction, 599 WordsPriorityQueuePool *queuePool, const bool hasAutoCorrectionCandidate, 600 const int startInputPos, const int startWordIndex, const int outputWordLength, 601 int *freqArray, int *wordLengthArray, unsigned short *outputWord) const { 602 if (startWordIndex >= (MULTIPLE_WORDS_SUGGESTION_MAX_WORDS - 1)) { 603 // Return if the last word index 604 return; 605 } 606 if (startWordIndex >= 1 607 && (hasAutoCorrectionCandidate 608 || inputSize < MIN_INPUT_LENGTH_FOR_THREE_OR_MORE_WORDS_CORRECTION)) { 609 // Do not suggest 3+ words if already has auto correction candidate 610 return; 611 } 612 for (int i = startInputPos + 1; i < inputSize; ++i) { 613 if (DEBUG_CORRECTION_FREQ) { 614 AKLOGI("Multi words(%d), start in %d sep %d start out %d", 615 startWordIndex, startInputPos, i, outputWordLength); 616 DUMP_WORD(outputWord, outputWordLength); 617 } 618 int tempOutputWordLength = 0; 619 // Current word 620 int inputWordStartPos = startInputPos; 621 int inputWordLength = i - startInputPos; 622 const int suggestionFlag = getSubStringSuggestion(proximityInfo, xcoordinates, ycoordinates, 623 codes, useFullEditDistance, correction, queuePool, inputSize, 624 hasAutoCorrectionCandidate, startWordIndex, inputWordStartPos, inputWordLength, 625 outputWordLength, true /* not used */, freqArray, wordLengthArray, outputWord, 626 &tempOutputWordLength); 627 if (suggestionFlag == FLAG_MULTIPLE_SUGGEST_ABORT) { 628 // TODO: break here 629 continue; 630 } else if (suggestionFlag == FLAG_MULTIPLE_SUGGEST_SKIP) { 631 continue; 632 } 633 634 if (DEBUG_CORRECTION_FREQ) { 635 AKLOGI("Do missing space correction"); 636 } 637 // Next word 638 // Missing space 639 inputWordStartPos = i; 640 inputWordLength = inputSize - i; 641 if (getSubStringSuggestion(proximityInfo, xcoordinates, ycoordinates, codes, 642 useFullEditDistance, correction, queuePool, inputSize, hasAutoCorrectionCandidate, 643 startWordIndex + 1, inputWordStartPos, inputWordLength, tempOutputWordLength, 644 false /* missing space */, freqArray, wordLengthArray, outputWord, 0) 645 != FLAG_MULTIPLE_SUGGEST_CONTINUE) { 646 getMultiWordsSuggestionRec(proximityInfo, xcoordinates, ycoordinates, codes, 647 useFullEditDistance, inputSize, correction, queuePool, 648 hasAutoCorrectionCandidate, inputWordStartPos, startWordIndex + 1, 649 tempOutputWordLength, freqArray, wordLengthArray, outputWord); 650 } 651 652 // Mistyped space 653 ++inputWordStartPos; 654 --inputWordLength; 655 656 if (inputWordLength <= 0) { 657 continue; 658 } 659 660 const int x = xcoordinates[inputWordStartPos - 1]; 661 const int y = ycoordinates[inputWordStartPos - 1]; 662 if (!proximityInfo->hasSpaceProximity(x, y)) { 663 continue; 664 } 665 666 if (DEBUG_CORRECTION_FREQ) { 667 AKLOGI("Do mistyped space correction"); 668 } 669 getSubStringSuggestion(proximityInfo, xcoordinates, ycoordinates, codes, 670 useFullEditDistance, correction, queuePool, inputSize, hasAutoCorrectionCandidate, 671 startWordIndex + 1, inputWordStartPos, inputWordLength, tempOutputWordLength, 672 true /* mistyped space */, freqArray, wordLengthArray, outputWord, 0); 673 } 674 } 675 676 void UnigramDictionary::getSplitMultipleWordsSuggestions(ProximityInfo *proximityInfo, 677 const int *xcoordinates, const int *ycoordinates, const int *codes, 678 const bool useFullEditDistance, const int inputSize, 679 Correction *correction, WordsPriorityQueuePool *queuePool, 680 const bool hasAutoCorrectionCandidate) const { 681 if (inputSize >= MAX_WORD_LENGTH) return; 682 if (DEBUG_DICT) { 683 AKLOGI("--- Suggest multiple words"); 684 } 685 686 // Allocating fixed length array on stack 687 unsigned short outputWord[MAX_WORD_LENGTH]; 688 int freqArray[MULTIPLE_WORDS_SUGGESTION_MAX_WORDS]; 689 int wordLengthArray[MULTIPLE_WORDS_SUGGESTION_MAX_WORDS]; 690 const int outputWordLength = 0; 691 const int startInputPos = 0; 692 const int startWordIndex = 0; 693 getMultiWordsSuggestionRec(proximityInfo, xcoordinates, ycoordinates, codes, 694 useFullEditDistance, inputSize, correction, queuePool, hasAutoCorrectionCandidate, 695 startInputPos, startWordIndex, outputWordLength, freqArray, wordLengthArray, 696 outputWord); 697 } 698 699 // Wrapper for getMostFrequentWordLikeInner, which matches it to the previous 700 // interface. 701 inline int UnigramDictionary::getMostFrequentWordLike(const int startInputIndex, 702 const int inputSize, Correction *correction, unsigned short *word) const { 703 uint16_t inWord[inputSize]; 704 705 for (int i = 0; i < inputSize; ++i) { 706 inWord[i] = (uint16_t)correction->getPrimaryCharAt(startInputIndex + i); 707 } 708 return getMostFrequentWordLikeInner(inWord, inputSize, word); 709 } 710 711 // This function will take the position of a character array within a CharGroup, 712 // and check it actually like-matches the word in inWord starting at startInputIndex, 713 // that is, it matches it with case and accents squashed. 714 // The function returns true if there was a full match, false otherwise. 715 // The function will copy on-the-fly the characters in the CharGroup to outNewWord. 716 // It will also place the end position of the array in outPos; in outInputIndex, 717 // it will place the index of the first char AFTER the match if there was a match, 718 // and the initial position if there was not. It makes sense because if there was 719 // a match we want to continue searching, but if there was not, we want to go to 720 // the next CharGroup. 721 // In and out parameters may point to the same location. This function takes care 722 // not to use any input parameters after it wrote into its outputs. 723 static inline bool testCharGroupForContinuedLikeness(const uint8_t flags, 724 const uint8_t *const root, const int startPos, const uint16_t *const inWord, 725 const int startInputIndex, const int inputSize, int32_t *outNewWord, int *outInputIndex, 726 int *outPos) { 727 const bool hasMultipleChars = (0 != (BinaryFormat::FLAG_HAS_MULTIPLE_CHARS & flags)); 728 int pos = startPos; 729 int32_t codePoint = BinaryFormat::getCodePointAndForwardPointer(root, &pos); 730 int32_t baseChar = toBaseLowerCase(codePoint); 731 const uint16_t wChar = toBaseLowerCase(inWord[startInputIndex]); 732 733 if (baseChar != wChar) { 734 *outPos = hasMultipleChars ? BinaryFormat::skipOtherCharacters(root, pos) : pos; 735 *outInputIndex = startInputIndex; 736 return false; 737 } 738 int inputIndex = startInputIndex; 739 outNewWord[inputIndex] = codePoint; 740 if (hasMultipleChars) { 741 codePoint = BinaryFormat::getCodePointAndForwardPointer(root, &pos); 742 while (NOT_A_CODE_POINT != codePoint) { 743 baseChar = toBaseLowerCase(codePoint); 744 if (inputIndex + 1 >= inputSize || toBaseLowerCase(inWord[++inputIndex]) != baseChar) { 745 *outPos = BinaryFormat::skipOtherCharacters(root, pos); 746 *outInputIndex = startInputIndex; 747 return false; 748 } 749 outNewWord[inputIndex] = codePoint; 750 codePoint = BinaryFormat::getCodePointAndForwardPointer(root, &pos); 751 } 752 } 753 *outInputIndex = inputIndex + 1; 754 *outPos = pos; 755 return true; 756 } 757 758 // This function is invoked when a word like the word searched for is found. 759 // It will compare the frequency to the max frequency, and if greater, will 760 // copy the word into the output buffer. In output value maxFreq, it will 761 // write the new maximum frequency if it changed. 762 static inline void onTerminalWordLike(const int freq, int32_t *newWord, const int length, 763 short unsigned int *outWord, int *maxFreq) { 764 if (freq > *maxFreq) { 765 for (int q = 0; q < length; ++q) { 766 outWord[q] = newWord[q]; 767 } 768 outWord[length] = 0; 769 *maxFreq = freq; 770 } 771 } 772 773 // Will find the highest frequency of the words like the one passed as an argument, 774 // that is, everything that only differs by case/accents. 775 int UnigramDictionary::getMostFrequentWordLikeInner(const uint16_t *const inWord, 776 const int inputSize, short unsigned int *outWord) const { 777 int32_t newWord[MAX_WORD_LENGTH_INTERNAL]; 778 int depth = 0; 779 int maxFreq = -1; 780 const uint8_t *const root = DICT_ROOT; 781 int stackChildCount[MAX_WORD_LENGTH_INTERNAL]; 782 int stackInputIndex[MAX_WORD_LENGTH_INTERNAL]; 783 int stackSiblingPos[MAX_WORD_LENGTH_INTERNAL]; 784 785 int startPos = 0; 786 stackChildCount[0] = BinaryFormat::getGroupCountAndForwardPointer(root, &startPos); 787 stackInputIndex[0] = 0; 788 stackSiblingPos[0] = startPos; 789 while (depth >= 0) { 790 const int charGroupCount = stackChildCount[depth]; 791 int pos = stackSiblingPos[depth]; 792 for (int charGroupIndex = charGroupCount - 1; charGroupIndex >= 0; --charGroupIndex) { 793 int inputIndex = stackInputIndex[depth]; 794 const uint8_t flags = BinaryFormat::getFlagsAndForwardPointer(root, &pos); 795 // Test whether all chars in this group match with the word we are searching for. If so, 796 // we want to traverse its children (or if the inputSize match, evaluate its frequency). 797 // Note that this function will output the position regardless, but will only write 798 // into inputIndex if there is a match. 799 const bool isAlike = testCharGroupForContinuedLikeness(flags, root, pos, inWord, 800 inputIndex, inputSize, newWord, &inputIndex, &pos); 801 if (isAlike && (!(BinaryFormat::FLAG_IS_NOT_A_WORD & flags)) 802 && (BinaryFormat::FLAG_IS_TERMINAL & flags) && (inputIndex == inputSize)) { 803 const int frequency = BinaryFormat::readFrequencyWithoutMovingPointer(root, pos); 804 onTerminalWordLike(frequency, newWord, inputIndex, outWord, &maxFreq); 805 } 806 pos = BinaryFormat::skipFrequency(flags, pos); 807 const int siblingPos = BinaryFormat::skipChildrenPosAndAttributes(root, flags, pos); 808 const int childrenNodePos = BinaryFormat::readChildrenPosition(root, flags, pos); 809 // If we had a match and the word has children, we want to traverse them. We don't have 810 // to traverse words longer than the one we are searching for, since they will not match 811 // anyway, so don't traverse unless inputIndex < inputSize. 812 if (isAlike && (-1 != childrenNodePos) && (inputIndex < inputSize)) { 813 // Save position for this depth, to get back to this once children are done 814 stackChildCount[depth] = charGroupIndex; 815 stackSiblingPos[depth] = siblingPos; 816 // Prepare stack values for next depth 817 ++depth; 818 int childrenPos = childrenNodePos; 819 stackChildCount[depth] = 820 BinaryFormat::getGroupCountAndForwardPointer(root, &childrenPos); 821 stackSiblingPos[depth] = childrenPos; 822 stackInputIndex[depth] = inputIndex; 823 pos = childrenPos; 824 // Go to the next depth level. 825 ++depth; 826 break; 827 } else { 828 // No match, or no children, or word too long to ever match: go the next sibling. 829 pos = siblingPos; 830 } 831 } 832 --depth; 833 } 834 return maxFreq; 835 } 836 837 int UnigramDictionary::getFrequency(const int32_t *const inWord, const int length) const { 838 const uint8_t *const root = DICT_ROOT; 839 int pos = BinaryFormat::getTerminalPosition(root, inWord, length, 840 false /* forceLowerCaseSearch */); 841 if (NOT_VALID_WORD == pos) { 842 return NOT_A_PROBABILITY; 843 } 844 const uint8_t flags = BinaryFormat::getFlagsAndForwardPointer(root, &pos); 845 if (flags & (BinaryFormat::FLAG_IS_BLACKLISTED | BinaryFormat::FLAG_IS_NOT_A_WORD)) { 846 // If this is not a word, or if it's a blacklisted entry, it should behave as 847 // having no frequency outside of the suggestion process (where it should be used 848 // for shortcuts). 849 return NOT_A_PROBABILITY; 850 } 851 const bool hasMultipleChars = (0 != (BinaryFormat::FLAG_HAS_MULTIPLE_CHARS & flags)); 852 if (hasMultipleChars) { 853 pos = BinaryFormat::skipOtherCharacters(root, pos); 854 } else { 855 BinaryFormat::getCodePointAndForwardPointer(DICT_ROOT, &pos); 856 } 857 const int unigramFreq = BinaryFormat::readFrequencyWithoutMovingPointer(root, pos); 858 return unigramFreq; 859 } 860 861 // TODO: remove this function. 862 int UnigramDictionary::getBigramPosition(int pos, unsigned short *word, int offset, 863 int length) const { 864 return -1; 865 } 866 867 // ProcessCurrentNode returns a boolean telling whether to traverse children nodes or not. 868 // If the return value is false, then the caller should read in the output "nextSiblingPosition" 869 // to find out the address of the next sibling node and pass it to a new call of processCurrentNode. 870 // It is worthy to note that when false is returned, the output values other than 871 // nextSiblingPosition are undefined. 872 // If the return value is true, then the caller must proceed to traverse the children of this 873 // node. processCurrentNode will output the information about the children: their count in 874 // newCount, their position in newChildrenPosition, the traverseAllNodes flag in 875 // newTraverseAllNodes, the match weight into newMatchRate, the input index into newInputIndex, the 876 // diffs into newDiffs, the sibling position in nextSiblingPosition, and the output index into 877 // newOutputIndex. Please also note the following caveat: processCurrentNode does not know when 878 // there aren't any more nodes at this level, it merely returns the address of the first byte after 879 // the current node in nextSiblingPosition. Thus, the caller must keep count of the nodes at any 880 // given level, as output into newCount when traversing this level's parent. 881 inline bool UnigramDictionary::processCurrentNode(const int initialPos, 882 const std::map<int, int> *bigramMap, const uint8_t *bigramFilter, Correction *correction, 883 int *newCount, int *newChildrenPosition, int *nextSiblingPosition, 884 WordsPriorityQueuePool *queuePool, const int currentWordIndex) const { 885 if (DEBUG_DICT) { 886 correction->checkState(); 887 } 888 int pos = initialPos; 889 890 // Flags contain the following information: 891 // - Address type (MASK_GROUP_ADDRESS_TYPE) on two bits: 892 // - FLAG_GROUP_ADDRESS_TYPE_{ONE,TWO,THREE}_BYTES means there are children and their address 893 // is on the specified number of bytes. 894 // - FLAG_GROUP_ADDRESS_TYPE_NOADDRESS means there are no children, and therefore no address. 895 // - FLAG_HAS_MULTIPLE_CHARS: whether this node has multiple char or not. 896 // - FLAG_IS_TERMINAL: whether this node is a terminal or not (it may still have children) 897 // - FLAG_HAS_BIGRAMS: whether this node has bigrams or not 898 const uint8_t flags = BinaryFormat::getFlagsAndForwardPointer(DICT_ROOT, &pos); 899 const bool hasMultipleChars = (0 != (BinaryFormat::FLAG_HAS_MULTIPLE_CHARS & flags)); 900 const bool isTerminalNode = (0 != (BinaryFormat::FLAG_IS_TERMINAL & flags)); 901 902 bool needsToInvokeOnTerminal = false; 903 904 // This gets only ONE character from the stream. Next there will be: 905 // if FLAG_HAS_MULTIPLE CHARS: the other characters of the same node 906 // else if FLAG_IS_TERMINAL: the frequency 907 // else if MASK_GROUP_ADDRESS_TYPE is not NONE: the children address 908 // Note that you can't have a node that both is not a terminal and has no children. 909 int32_t c = BinaryFormat::getCodePointAndForwardPointer(DICT_ROOT, &pos); 910 assert(NOT_A_CODE_POINT != c); 911 912 // We are going to loop through each character and make it look like it's a different 913 // node each time. To do that, we will process characters in this node in order until 914 // we find the character terminator. This is signalled by getCodePoint* returning 915 // NOT_A_CODE_POINT. 916 // As a special case, if there is only one character in this node, we must not read the 917 // next bytes so we will simulate the NOT_A_CODE_POINT return by testing the flags. 918 // This way, each loop run will look like a "virtual node". 919 do { 920 // We prefetch the next char. If 'c' is the last char of this node, we will have 921 // NOT_A_CODE_POINT in the next char. From this we can decide whether this virtual node 922 // should behave as a terminal or not and whether we have children. 923 const int32_t nextc = hasMultipleChars 924 ? BinaryFormat::getCodePointAndForwardPointer(DICT_ROOT, &pos) : NOT_A_CODE_POINT; 925 const bool isLastChar = (NOT_A_CODE_POINT == nextc); 926 // If there are more chars in this nodes, then this virtual node is not a terminal. 927 // If we are on the last char, this virtual node is a terminal if this node is. 928 const bool isTerminal = isLastChar && isTerminalNode; 929 930 Correction::CorrectionType stateType = correction->processCharAndCalcState( 931 c, isTerminal); 932 if (stateType == Correction::TRAVERSE_ALL_ON_TERMINAL 933 || stateType == Correction::ON_TERMINAL) { 934 needsToInvokeOnTerminal = true; 935 } else if (stateType == Correction::UNRELATED || correction->needsToPrune()) { 936 // We found that this is an unrelated character, so we should give up traversing 937 // this node and its children entirely. 938 // However we may not be on the last virtual node yet so we skip the remaining 939 // characters in this node, the frequency if it's there, read the next sibling 940 // position to output it, then return false. 941 // We don't have to output other values because we return false, as in 942 // "don't traverse children". 943 if (!isLastChar) { 944 pos = BinaryFormat::skipOtherCharacters(DICT_ROOT, pos); 945 } 946 pos = BinaryFormat::skipFrequency(flags, pos); 947 *nextSiblingPosition = 948 BinaryFormat::skipChildrenPosAndAttributes(DICT_ROOT, flags, pos); 949 return false; 950 } 951 952 // Prepare for the next character. Promote the prefetched char to current char - the loop 953 // will take care of prefetching the next. If we finally found our last char, nextc will 954 // contain NOT_A_CODE_POINT. 955 c = nextc; 956 } while (NOT_A_CODE_POINT != c); 957 958 if (isTerminalNode) { 959 // The frequency should be here, because we come here only if this is actually 960 // a terminal node, and we are on its last char. 961 const int unigramFreq = BinaryFormat::readFrequencyWithoutMovingPointer(DICT_ROOT, pos); 962 const int childrenAddressPos = BinaryFormat::skipFrequency(flags, pos); 963 const int attributesPos = BinaryFormat::skipChildrenPosition(flags, childrenAddressPos); 964 TerminalAttributes terminalAttributes(DICT_ROOT, flags, attributesPos); 965 // bigramMap contains the bigram frequencies indexed by addresses for fast lookup. 966 // bigramFilter is a bloom filter of said frequencies for even faster rejection. 967 const int probability = BinaryFormat::getProbability(initialPos, bigramMap, bigramFilter, 968 unigramFreq); 969 onTerminal(probability, terminalAttributes, correction, queuePool, needsToInvokeOnTerminal, 970 currentWordIndex); 971 972 // If there are more chars in this node, then this virtual node has children. 973 // If we are on the last char, this virtual node has children if this node has. 974 const bool hasChildren = BinaryFormat::hasChildrenInFlags(flags); 975 976 // This character matched the typed character (enough to traverse the node at least) 977 // so we just evaluated it. Now we should evaluate this virtual node's children - that 978 // is, if it has any. If it has no children, we're done here - so we skip the end of 979 // the node, output the siblings position, and return false "don't traverse children". 980 // Note that !hasChildren implies isLastChar, so we know we don't have to skip any 981 // remaining char in this group for there can't be any. 982 if (!hasChildren) { 983 pos = BinaryFormat::skipFrequency(flags, pos); 984 *nextSiblingPosition = 985 BinaryFormat::skipChildrenPosAndAttributes(DICT_ROOT, flags, pos); 986 return false; 987 } 988 989 // Optimization: Prune out words that are too long compared to how much was typed. 990 if (correction->needsToPrune()) { 991 pos = BinaryFormat::skipFrequency(flags, pos); 992 *nextSiblingPosition = 993 BinaryFormat::skipChildrenPosAndAttributes(DICT_ROOT, flags, pos); 994 if (DEBUG_DICT_FULL) { 995 AKLOGI("Traversing was pruned."); 996 } 997 return false; 998 } 999 } 1000 1001 // Now we finished processing this node, and we want to traverse children. If there are no 1002 // children, we can't come here. 1003 assert(BinaryFormat::hasChildrenInFlags(flags)); 1004 1005 // If this node was a terminal it still has the frequency under the pointer (it may have been 1006 // read, but not skipped - see readFrequencyWithoutMovingPointer). 1007 // Next come the children position, then possibly attributes (attributes are bigrams only for 1008 // now, maybe something related to shortcuts in the future). 1009 // Once this is read, we still need to output the number of nodes in the immediate children of 1010 // this node, so we read and output it before returning true, as in "please traverse children". 1011 pos = BinaryFormat::skipFrequency(flags, pos); 1012 int childrenPos = BinaryFormat::readChildrenPosition(DICT_ROOT, flags, pos); 1013 *nextSiblingPosition = BinaryFormat::skipChildrenPosAndAttributes(DICT_ROOT, flags, pos); 1014 *newCount = BinaryFormat::getGroupCountAndForwardPointer(DICT_ROOT, &childrenPos); 1015 *newChildrenPosition = childrenPos; 1016 return true; 1017 } 1018 } // namespace latinime 1019
