suggest.cpp revision 4447b14b785652e36adca329f5cddf986bfd14fa
195fe8267955ba5bfcc3cf38383f0d13026287082Satoshi Kataoka/* 295fe8267955ba5bfcc3cf38383f0d13026287082Satoshi Kataoka * Copyright (C) 2012 The Android Open Source Project 395fe8267955ba5bfcc3cf38383f0d13026287082Satoshi Kataoka * 495fe8267955ba5bfcc3cf38383f0d13026287082Satoshi Kataoka * Licensed under the Apache License, Version 2.0 (the "License"); 595fe8267955ba5bfcc3cf38383f0d13026287082Satoshi Kataoka * you may not use this file except in compliance with the License. 695fe8267955ba5bfcc3cf38383f0d13026287082Satoshi Kataoka * You may obtain a copy of the License at 795fe8267955ba5bfcc3cf38383f0d13026287082Satoshi Kataoka * 895fe8267955ba5bfcc3cf38383f0d13026287082Satoshi Kataoka * http://www.apache.org/licenses/LICENSE-2.0 995fe8267955ba5bfcc3cf38383f0d13026287082Satoshi Kataoka * 1095fe8267955ba5bfcc3cf38383f0d13026287082Satoshi Kataoka * Unless required by applicable law or agreed to in writing, software 1195fe8267955ba5bfcc3cf38383f0d13026287082Satoshi Kataoka * distributed under the License is distributed on an "AS IS" BASIS, 1295fe8267955ba5bfcc3cf38383f0d13026287082Satoshi Kataoka * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 1395fe8267955ba5bfcc3cf38383f0d13026287082Satoshi Kataoka * See the License for the specific language governing permissions and 1495fe8267955ba5bfcc3cf38383f0d13026287082Satoshi Kataoka * limitations under the License. 1595fe8267955ba5bfcc3cf38383f0d13026287082Satoshi Kataoka */ 1695fe8267955ba5bfcc3cf38383f0d13026287082Satoshi Kataoka 17b68e73448104714e8f12f89a1e00fb10b5fd14c4Ken Wakasa#include "suggest/core/suggest.h" 18b68e73448104714e8f12f89a1e00fb10b5fd14c4Ken Wakasa 19b68e73448104714e8f12f89a1e00fb10b5fd14c4Ken Wakasa#include "suggest/core/dicnode/dic_node.h" 20b68e73448104714e8f12f89a1e00fb10b5fd14c4Ken Wakasa#include "suggest/core/dicnode/dic_node_priority_queue.h" 21b68e73448104714e8f12f89a1e00fb10b5fd14c4Ken Wakasa#include "suggest/core/dicnode/dic_node_vector.h" 22bd0d1afdb28a28e2ddac1409208c59ba64350399Keisuke Kuroynagi#include "suggest/core/dictionary/binary_dictionary_info.h" 23a65c267b1f1207e54c6f821148c600e3899b7f9cKen Wakasa#include "suggest/core/dictionary/dictionary.h" 24a65c267b1f1207e54c6f821148c600e3899b7f9cKen Wakasa#include "suggest/core/dictionary/digraph_utils.h" 25b68e73448104714e8f12f89a1e00fb10b5fd14c4Ken Wakasa#include "suggest/core/dictionary/shortcut_utils.h" 26a65c267b1f1207e54c6f821148c600e3899b7f9cKen Wakasa#include "suggest/core/dictionary/terminal_attributes.h" 2729432f843a8cd6ffb2be286104964592e80d77c9Ken Wakasa#include "suggest/core/layout/proximity_info.h" 28b68e73448104714e8f12f89a1e00fb10b5fd14c4Ken Wakasa#include "suggest/core/policy/scoring.h" 29b68e73448104714e8f12f89a1e00fb10b5fd14c4Ken Wakasa#include "suggest/core/policy/traversal.h" 30b68e73448104714e8f12f89a1e00fb10b5fd14c4Ken Wakasa#include "suggest/core/policy/weighting.h" 31b68e73448104714e8f12f89a1e00fb10b5fd14c4Ken Wakasa#include "suggest/core/session/dic_traverse_session.h" 3295fe8267955ba5bfcc3cf38383f0d13026287082Satoshi Kataoka 3395fe8267955ba5bfcc3cf38383f0d13026287082Satoshi Kataokanamespace latinime { 3495fe8267955ba5bfcc3cf38383f0d13026287082Satoshi Kataoka 3595fe8267955ba5bfcc3cf38383f0d13026287082Satoshi Kataoka// Initialization of class constants. 3695fe8267955ba5bfcc3cf38383f0d13026287082Satoshi Kataokaconst int Suggest::MIN_LEN_FOR_MULTI_WORD_AUTOCORRECT = 16; 3795fe8267955ba5bfcc3cf38383f0d13026287082Satoshi Kataokaconst int Suggest::MIN_CONTINUOUS_SUGGESTION_INPUT_SIZE = 2; 3895fe8267955ba5bfcc3cf38383f0d13026287082Satoshi Kataokaconst float Suggest::AUTOCORRECT_CLASSIFICATION_THRESHOLD = 0.33f; 3995fe8267955ba5bfcc3cf38383f0d13026287082Satoshi Kataoka 4095fe8267955ba5bfcc3cf38383f0d13026287082Satoshi Kataoka/** 4195fe8267955ba5bfcc3cf38383f0d13026287082Satoshi Kataoka * Returns a set of suggestions for the given input touch points. The commitPoint argument indicates 4295fe8267955ba5bfcc3cf38383f0d13026287082Satoshi Kataoka * whether to prematurely commit the suggested words up to the given point for sentence-level 4395fe8267955ba5bfcc3cf38383f0d13026287082Satoshi Kataoka * suggestion. 4495fe8267955ba5bfcc3cf38383f0d13026287082Satoshi Kataoka * 4595fe8267955ba5bfcc3cf38383f0d13026287082Satoshi Kataoka * Note: Currently does not support concurrent calls across threads. Continuous suggestion is 4695fe8267955ba5bfcc3cf38383f0d13026287082Satoshi Kataoka * automatically activated for sequential calls that share the same starting input. 4795fe8267955ba5bfcc3cf38383f0d13026287082Satoshi Kataoka * TODO: Stop detecting continuous suggestion. Start using traverseSession instead. 4895fe8267955ba5bfcc3cf38383f0d13026287082Satoshi Kataoka */ 4995fe8267955ba5bfcc3cf38383f0d13026287082Satoshi Kataokaint Suggest::getSuggestions(ProximityInfo *pInfo, void *traverseSession, 5095fe8267955ba5bfcc3cf38383f0d13026287082Satoshi Kataoka int *inputXs, int *inputYs, int *times, int *pointerIds, int *inputCodePoints, 5195fe8267955ba5bfcc3cf38383f0d13026287082Satoshi Kataoka int inputSize, int commitPoint, int *outWords, int *frequencies, int *outputIndices, 5295fe8267955ba5bfcc3cf38383f0d13026287082Satoshi Kataoka int *outputTypes) const { 5395fe8267955ba5bfcc3cf38383f0d13026287082Satoshi Kataoka PROF_OPEN; 5495fe8267955ba5bfcc3cf38383f0d13026287082Satoshi Kataoka PROF_START(0); 5595fe8267955ba5bfcc3cf38383f0d13026287082Satoshi Kataoka const float maxSpatialDistance = TRAVERSAL->getMaxSpatialDistance(); 5695fe8267955ba5bfcc3cf38383f0d13026287082Satoshi Kataoka DicTraverseSession *tSession = static_cast<DicTraverseSession *>(traverseSession); 5795fe8267955ba5bfcc3cf38383f0d13026287082Satoshi Kataoka tSession->setupForGetSuggestions(pInfo, inputCodePoints, inputSize, inputXs, inputYs, times, 5895fe8267955ba5bfcc3cf38383f0d13026287082Satoshi Kataoka pointerIds, maxSpatialDistance, TRAVERSAL->getMaxPointerCount()); 5995fe8267955ba5bfcc3cf38383f0d13026287082Satoshi Kataoka // TODO: Add the way to evaluate cache 6095fe8267955ba5bfcc3cf38383f0d13026287082Satoshi Kataoka 6195fe8267955ba5bfcc3cf38383f0d13026287082Satoshi Kataoka initializeSearch(tSession, commitPoint); 6295fe8267955ba5bfcc3cf38383f0d13026287082Satoshi Kataoka PROF_END(0); 6395fe8267955ba5bfcc3cf38383f0d13026287082Satoshi Kataoka PROF_START(1); 6495fe8267955ba5bfcc3cf38383f0d13026287082Satoshi Kataoka 6595fe8267955ba5bfcc3cf38383f0d13026287082Satoshi Kataoka // keep expanding search dicNodes until all have terminated. 6695fe8267955ba5bfcc3cf38383f0d13026287082Satoshi Kataoka while (tSession->getDicTraverseCache()->activeSize() > 0) { 6795fe8267955ba5bfcc3cf38383f0d13026287082Satoshi Kataoka expandCurrentDicNodes(tSession); 6895fe8267955ba5bfcc3cf38383f0d13026287082Satoshi Kataoka tSession->getDicTraverseCache()->advanceActiveDicNodes(); 6995fe8267955ba5bfcc3cf38383f0d13026287082Satoshi Kataoka tSession->getDicTraverseCache()->advanceInputIndex(inputSize); 7095fe8267955ba5bfcc3cf38383f0d13026287082Satoshi Kataoka } 7195fe8267955ba5bfcc3cf38383f0d13026287082Satoshi Kataoka PROF_END(1); 7295fe8267955ba5bfcc3cf38383f0d13026287082Satoshi Kataoka PROF_START(2); 7395fe8267955ba5bfcc3cf38383f0d13026287082Satoshi Kataoka const int size = outputSuggestions(tSession, frequencies, outWords, outputIndices, outputTypes); 7495fe8267955ba5bfcc3cf38383f0d13026287082Satoshi Kataoka PROF_END(2); 7595fe8267955ba5bfcc3cf38383f0d13026287082Satoshi Kataoka PROF_CLOSE; 7695fe8267955ba5bfcc3cf38383f0d13026287082Satoshi Kataoka return size; 7795fe8267955ba5bfcc3cf38383f0d13026287082Satoshi Kataoka} 7895fe8267955ba5bfcc3cf38383f0d13026287082Satoshi Kataoka 7995fe8267955ba5bfcc3cf38383f0d13026287082Satoshi Kataoka/** 8095fe8267955ba5bfcc3cf38383f0d13026287082Satoshi Kataoka * Initializes the search at the root of the lexicon trie. Note that when possible the search will 8195fe8267955ba5bfcc3cf38383f0d13026287082Satoshi Kataoka * continue suggestion from where it left off during the last call. 8295fe8267955ba5bfcc3cf38383f0d13026287082Satoshi Kataoka */ 8395fe8267955ba5bfcc3cf38383f0d13026287082Satoshi Kataokavoid Suggest::initializeSearch(DicTraverseSession *traverseSession, int commitPoint) const { 8495fe8267955ba5bfcc3cf38383f0d13026287082Satoshi Kataoka if (!traverseSession->getProximityInfoState(0)->isUsed()) { 8595fe8267955ba5bfcc3cf38383f0d13026287082Satoshi Kataoka return; 8695fe8267955ba5bfcc3cf38383f0d13026287082Satoshi Kataoka } 87a829188f54c0fd2e26192d98d9e56e033d8f91aaKeisuke Kuroynagi 88a829188f54c0fd2e26192d98d9e56e033d8f91aaKeisuke Kuroynagi // Never auto partial commit for now. 89a829188f54c0fd2e26192d98d9e56e033d8f91aaKeisuke Kuroynagi commitPoint = 0; 9095fe8267955ba5bfcc3cf38383f0d13026287082Satoshi Kataoka 9195fe8267955ba5bfcc3cf38383f0d13026287082Satoshi Kataoka if (traverseSession->getInputSize() > MIN_CONTINUOUS_SUGGESTION_INPUT_SIZE 9295fe8267955ba5bfcc3cf38383f0d13026287082Satoshi Kataoka && traverseSession->isContinuousSuggestionPossible()) { 9395fe8267955ba5bfcc3cf38383f0d13026287082Satoshi Kataoka if (commitPoint == 0) { 9495fe8267955ba5bfcc3cf38383f0d13026287082Satoshi Kataoka // Continue suggestion 9595fe8267955ba5bfcc3cf38383f0d13026287082Satoshi Kataoka traverseSession->getDicTraverseCache()->continueSearch(); 9695fe8267955ba5bfcc3cf38383f0d13026287082Satoshi Kataoka } else { 9795fe8267955ba5bfcc3cf38383f0d13026287082Satoshi Kataoka // Continue suggestion after partial commit. 9895fe8267955ba5bfcc3cf38383f0d13026287082Satoshi Kataoka DicNode *topDicNode = 9995fe8267955ba5bfcc3cf38383f0d13026287082Satoshi Kataoka traverseSession->getDicTraverseCache()->setCommitPoint(commitPoint); 10095fe8267955ba5bfcc3cf38383f0d13026287082Satoshi Kataoka traverseSession->setPrevWordPos(topDicNode->getPrevWordNodePos()); 10195fe8267955ba5bfcc3cf38383f0d13026287082Satoshi Kataoka traverseSession->getDicTraverseCache()->continueSearch(); 10295fe8267955ba5bfcc3cf38383f0d13026287082Satoshi Kataoka traverseSession->setPartiallyCommited(); 10395fe8267955ba5bfcc3cf38383f0d13026287082Satoshi Kataoka } 10495fe8267955ba5bfcc3cf38383f0d13026287082Satoshi Kataoka } else { 10595fe8267955ba5bfcc3cf38383f0d13026287082Satoshi Kataoka // Restart recognition at the root. 1064447b14b785652e36adca329f5cddf986bfd14faKeisuke Kuroynagi traverseSession->resetCache(TRAVERSAL->getMaxCacheSize(traverseSession->getInputSize()), 1074447b14b785652e36adca329f5cddf986bfd14faKeisuke Kuroynagi MAX_RESULTS); 10895fe8267955ba5bfcc3cf38383f0d13026287082Satoshi Kataoka // Create a new dic node here 10995fe8267955ba5bfcc3cf38383f0d13026287082Satoshi Kataoka DicNode rootNode; 1100ecfb9424754341d7ee41557fc1f913cb6ca79c2Keisuke Kuroyanagi DicNodeUtils::initAsRoot(traverseSession->getBinaryDictionaryInfo(), 1110ecfb9424754341d7ee41557fc1f913cb6ca79c2Keisuke Kuroyanagi traverseSession->getPrevWordPos(), &rootNode); 11295fe8267955ba5bfcc3cf38383f0d13026287082Satoshi Kataoka traverseSession->getDicTraverseCache()->copyPushActive(&rootNode); 11395fe8267955ba5bfcc3cf38383f0d13026287082Satoshi Kataoka } 11495fe8267955ba5bfcc3cf38383f0d13026287082Satoshi Kataoka} 11595fe8267955ba5bfcc3cf38383f0d13026287082Satoshi Kataoka 11695fe8267955ba5bfcc3cf38383f0d13026287082Satoshi Kataoka/** 11795fe8267955ba5bfcc3cf38383f0d13026287082Satoshi Kataoka * Outputs the final list of suggestions (i.e., terminal nodes). 11895fe8267955ba5bfcc3cf38383f0d13026287082Satoshi Kataoka */ 11995fe8267955ba5bfcc3cf38383f0d13026287082Satoshi Kataokaint Suggest::outputSuggestions(DicTraverseSession *traverseSession, int *frequencies, 12095fe8267955ba5bfcc3cf38383f0d13026287082Satoshi Kataoka int *outputCodePoints, int *spaceIndices, int *outputTypes) const { 1218b3009ef4875e37cffbc5ccee532e4e77a34fd36Satoshi Kataoka#if DEBUG_EVALUATE_MOST_PROBABLE_STRING 1228b3009ef4875e37cffbc5ccee532e4e77a34fd36Satoshi Kataoka const int terminalSize = 0; 1238b3009ef4875e37cffbc5ccee532e4e77a34fd36Satoshi Kataoka#else 12495fe8267955ba5bfcc3cf38383f0d13026287082Satoshi Kataoka const int terminalSize = min(MAX_RESULTS, 12595fe8267955ba5bfcc3cf38383f0d13026287082Satoshi Kataoka static_cast<int>(traverseSession->getDicTraverseCache()->terminalSize())); 1268b3009ef4875e37cffbc5ccee532e4e77a34fd36Satoshi Kataoka#endif 12795fe8267955ba5bfcc3cf38383f0d13026287082Satoshi Kataoka DicNode terminals[MAX_RESULTS]; // Avoiding non-POD variable length array 12895fe8267955ba5bfcc3cf38383f0d13026287082Satoshi Kataoka 12995fe8267955ba5bfcc3cf38383f0d13026287082Satoshi Kataoka for (int index = terminalSize - 1; index >= 0; --index) { 13095fe8267955ba5bfcc3cf38383f0d13026287082Satoshi Kataoka traverseSession->getDicTraverseCache()->popTerminal(&terminals[index]); 13195fe8267955ba5bfcc3cf38383f0d13026287082Satoshi Kataoka } 13295fe8267955ba5bfcc3cf38383f0d13026287082Satoshi Kataoka 13395fe8267955ba5bfcc3cf38383f0d13026287082Satoshi Kataoka const float languageWeight = SCORING->getAdjustedLanguageWeight( 13495fe8267955ba5bfcc3cf38383f0d13026287082Satoshi Kataoka traverseSession, terminals, terminalSize); 13595fe8267955ba5bfcc3cf38383f0d13026287082Satoshi Kataoka 13695fe8267955ba5bfcc3cf38383f0d13026287082Satoshi Kataoka int outputWordIndex = 0; 13795fe8267955ba5bfcc3cf38383f0d13026287082Satoshi Kataoka // Insert most probable word at index == 0 as long as there is one terminal at least 13895fe8267955ba5bfcc3cf38383f0d13026287082Satoshi Kataoka const bool hasMostProbableString = 13995fe8267955ba5bfcc3cf38383f0d13026287082Satoshi Kataoka SCORING->getMostProbableString(traverseSession, terminalSize, languageWeight, 14095fe8267955ba5bfcc3cf38383f0d13026287082Satoshi Kataoka &outputCodePoints[0], &outputTypes[0], &frequencies[0]); 14195fe8267955ba5bfcc3cf38383f0d13026287082Satoshi Kataoka if (hasMostProbableString) { 14295fe8267955ba5bfcc3cf38383f0d13026287082Satoshi Kataoka ++outputWordIndex; 14395fe8267955ba5bfcc3cf38383f0d13026287082Satoshi Kataoka } 14495fe8267955ba5bfcc3cf38383f0d13026287082Satoshi Kataoka 14595fe8267955ba5bfcc3cf38383f0d13026287082Satoshi Kataoka // Initial value of the loop index for terminal nodes (words) 14695fe8267955ba5bfcc3cf38383f0d13026287082Satoshi Kataoka int doubleLetterTerminalIndex = -1; 14795fe8267955ba5bfcc3cf38383f0d13026287082Satoshi Kataoka DoubleLetterLevel doubleLetterLevel = NOT_A_DOUBLE_LETTER; 14895fe8267955ba5bfcc3cf38383f0d13026287082Satoshi Kataoka SCORING->searchWordWithDoubleLetter(terminals, terminalSize, 14995fe8267955ba5bfcc3cf38383f0d13026287082Satoshi Kataoka &doubleLetterTerminalIndex, &doubleLetterLevel); 15095fe8267955ba5bfcc3cf38383f0d13026287082Satoshi Kataoka 15195fe8267955ba5bfcc3cf38383f0d13026287082Satoshi Kataoka int maxScore = S_INT_MIN; 152a829188f54c0fd2e26192d98d9e56e033d8f91aaKeisuke Kuroynagi // Force autocorrection for obvious long multi-word suggestions when the top suggestion is 153a829188f54c0fd2e26192d98d9e56e033d8f91aaKeisuke Kuroynagi // a long multiple words suggestion. 154a829188f54c0fd2e26192d98d9e56e033d8f91aaKeisuke Kuroynagi // TODO: Implement a smarter auto-commit method for handling multi-word suggestions. 155a829188f54c0fd2e26192d98d9e56e033d8f91aaKeisuke Kuroynagi // traverseSession->isPartiallyCommited() always returns false because we never auto partial 156a829188f54c0fd2e26192d98d9e56e033d8f91aaKeisuke Kuroynagi // commit for now. 157a829188f54c0fd2e26192d98d9e56e033d8f91aaKeisuke Kuroynagi const bool forceCommitMultiWords = (terminalSize > 0) ? 158a829188f54c0fd2e26192d98d9e56e033d8f91aaKeisuke Kuroynagi TRAVERSAL->autoCorrectsToMultiWordSuggestionIfTop() 159a829188f54c0fd2e26192d98d9e56e033d8f91aaKeisuke Kuroynagi && (traverseSession->isPartiallyCommited() 160a829188f54c0fd2e26192d98d9e56e033d8f91aaKeisuke Kuroynagi || (traverseSession->getInputSize() 161a829188f54c0fd2e26192d98d9e56e033d8f91aaKeisuke Kuroynagi >= MIN_LEN_FOR_MULTI_WORD_AUTOCORRECT 162a829188f54c0fd2e26192d98d9e56e033d8f91aaKeisuke Kuroynagi && terminals[0].hasMultipleWords())) : false; 16395fe8267955ba5bfcc3cf38383f0d13026287082Satoshi Kataoka // Output suggestion results here 16495fe8267955ba5bfcc3cf38383f0d13026287082Satoshi Kataoka for (int terminalIndex = 0; terminalIndex < terminalSize && outputWordIndex < MAX_RESULTS; 16595fe8267955ba5bfcc3cf38383f0d13026287082Satoshi Kataoka ++terminalIndex) { 16695fe8267955ba5bfcc3cf38383f0d13026287082Satoshi Kataoka DicNode *terminalDicNode = &terminals[terminalIndex]; 16795fe8267955ba5bfcc3cf38383f0d13026287082Satoshi Kataoka if (DEBUG_GEO_FULL) { 16895fe8267955ba5bfcc3cf38383f0d13026287082Satoshi Kataoka terminalDicNode->dump("OUT:"); 16995fe8267955ba5bfcc3cf38383f0d13026287082Satoshi Kataoka } 17095fe8267955ba5bfcc3cf38383f0d13026287082Satoshi Kataoka const float doubleLetterCost = SCORING->getDoubleLetterDemotionDistanceCost( 17195fe8267955ba5bfcc3cf38383f0d13026287082Satoshi Kataoka terminalIndex, doubleLetterTerminalIndex, doubleLetterLevel); 17295fe8267955ba5bfcc3cf38383f0d13026287082Satoshi Kataoka const float compoundDistance = terminalDicNode->getCompoundDistance(languageWeight) 17395fe8267955ba5bfcc3cf38383f0d13026287082Satoshi Kataoka + doubleLetterCost; 17499e998286d71cf698d0a809a29b15d1a231ebbb1Jean Chalard const bool isPossiblyOffensiveWord = terminalDicNode->getProbability() <= 0; 17599e998286d71cf698d0a809a29b15d1a231ebbb1Jean Chalard const bool isExactMatch = terminalDicNode->isExactMatch(); 1765a346afab96186dc09aeed390b2cc70f8ec439d0Satoshi Kataoka const bool isFirstCharUppercase = terminalDicNode->isFirstCharUppercase(); 1775a346afab96186dc09aeed390b2cc70f8ec439d0Satoshi Kataoka // Heuristic: We exclude freq=0 first-char-uppercase words from exact match. 1785a346afab96186dc09aeed390b2cc70f8ec439d0Satoshi Kataoka // (e.g. "AMD" and "and") 1795a346afab96186dc09aeed390b2cc70f8ec439d0Satoshi Kataoka const bool isSafeExactMatch = isExactMatch 1805a346afab96186dc09aeed390b2cc70f8ec439d0Satoshi Kataoka && !(isPossiblyOffensiveWord && isFirstCharUppercase); 18199e998286d71cf698d0a809a29b15d1a231ebbb1Jean Chalard const int outputTypeFlags = 1825a346afab96186dc09aeed390b2cc70f8ec439d0Satoshi Kataoka (isPossiblyOffensiveWord ? Dictionary::KIND_FLAG_POSSIBLY_OFFENSIVE : 0) 1835a346afab96186dc09aeed390b2cc70f8ec439d0Satoshi Kataoka | (isSafeExactMatch ? Dictionary::KIND_FLAG_EXACT_MATCH : 0); 18499e998286d71cf698d0a809a29b15d1a231ebbb1Jean Chalard 18599e998286d71cf698d0a809a29b15d1a231ebbb1Jean Chalard // Entries that are blacklisted or do not represent a word should not be output. 1865b03213db13c670e37b15b8c813c91ebb232ead9Keisuke Kuroynagi const bool isValidWord = !terminalDicNode->isBlacklistedOrNotAWord(); 18795fe8267955ba5bfcc3cf38383f0d13026287082Satoshi Kataoka 18895fe8267955ba5bfcc3cf38383f0d13026287082Satoshi Kataoka // Increase output score of top typing suggestion to ensure autocorrection. 18995fe8267955ba5bfcc3cf38383f0d13026287082Satoshi Kataoka // TODO: Better integration with java side autocorrection logic. 19095fe8267955ba5bfcc3cf38383f0d13026287082Satoshi Kataoka const int finalScore = SCORING->calculateFinalScore( 19195fe8267955ba5bfcc3cf38383f0d13026287082Satoshi Kataoka compoundDistance, traverseSession->getInputSize(), 19234047d8905fbd2cbe4c99618aab105556ebee9edKeisuke Kuroynagi terminalDicNode->isExactMatch() 19334047d8905fbd2cbe4c99618aab105556ebee9edKeisuke Kuroynagi || (forceCommitMultiWords && terminalDicNode->hasMultipleWords()) 19434047d8905fbd2cbe4c99618aab105556ebee9edKeisuke Kuroynagi || (isValidWord && SCORING->doesAutoCorrectValidWord())); 19595fe8267955ba5bfcc3cf38383f0d13026287082Satoshi Kataoka maxScore = max(maxScore, finalScore); 19695fe8267955ba5bfcc3cf38383f0d13026287082Satoshi Kataoka 197a829188f54c0fd2e26192d98d9e56e033d8f91aaKeisuke Kuroynagi // TODO: Implement a smarter auto-commit method for handling multi-word suggestions. 198a829188f54c0fd2e26192d98d9e56e033d8f91aaKeisuke Kuroynagi // Index for top typing suggestion should be 0. 199a829188f54c0fd2e26192d98d9e56e033d8f91aaKeisuke Kuroynagi if (isValidWord && outputWordIndex == 0) { 200a829188f54c0fd2e26192d98d9e56e033d8f91aaKeisuke Kuroynagi terminalDicNode->outputSpacePositionsResult(spaceIndices); 20195fe8267955ba5bfcc3cf38383f0d13026287082Satoshi Kataoka } 20295fe8267955ba5bfcc3cf38383f0d13026287082Satoshi Kataoka 20399e998286d71cf698d0a809a29b15d1a231ebbb1Jean Chalard // Don't output invalid words. However, we still need to submit their shortcuts if any. 20495fe8267955ba5bfcc3cf38383f0d13026287082Satoshi Kataoka if (isValidWord) { 20599e998286d71cf698d0a809a29b15d1a231ebbb1Jean Chalard outputTypes[outputWordIndex] = Dictionary::KIND_CORRECTION | outputTypeFlags; 20695fe8267955ba5bfcc3cf38383f0d13026287082Satoshi Kataoka frequencies[outputWordIndex] = finalScore; 20795fe8267955ba5bfcc3cf38383f0d13026287082Satoshi Kataoka // Populate the outputChars array with the suggested word. 20895fe8267955ba5bfcc3cf38383f0d13026287082Satoshi Kataoka const int startIndex = outputWordIndex * MAX_WORD_LENGTH; 20995fe8267955ba5bfcc3cf38383f0d13026287082Satoshi Kataoka terminalDicNode->outputResult(&outputCodePoints[startIndex]); 21095fe8267955ba5bfcc3cf38383f0d13026287082Satoshi Kataoka ++outputWordIndex; 21195fe8267955ba5bfcc3cf38383f0d13026287082Satoshi Kataoka } 21295fe8267955ba5bfcc3cf38383f0d13026287082Satoshi Kataoka 2139a4f7a3761684ee2122485c7ae111f6287d105d6Keisuke Kuroynagi if (!terminalDicNode->hasMultipleWords()) { 214c38ec475962ad6b7f14abe35b950545ebcdbe3c5Keisuke Kuroynagi const BinaryDictionaryInfo *const binaryDictionaryInfo = 215c38ec475962ad6b7f14abe35b950545ebcdbe3c5Keisuke Kuroynagi traverseSession->getBinaryDictionaryInfo(); 2165b03213db13c670e37b15b8c813c91ebb232ead9Keisuke Kuroynagi const TerminalAttributes terminalAttributes(traverseSession->getBinaryDictionaryInfo(), 217c38ec475962ad6b7f14abe35b950545ebcdbe3c5Keisuke Kuroynagi binaryDictionaryInfo->getStructurePolicy()->getShortcutPositionOfNode( 218c38ec475962ad6b7f14abe35b950545ebcdbe3c5Keisuke Kuroynagi binaryDictionaryInfo, terminalDicNode->getPos())); 2199a4f7a3761684ee2122485c7ae111f6287d105d6Keisuke Kuroynagi // Shortcut is not supported for multiple words suggestions. 2209a4f7a3761684ee2122485c7ae111f6287d105d6Keisuke Kuroynagi // TODO: Check shortcuts during traversal for multiple words suggestions. 2219a4f7a3761684ee2122485c7ae111f6287d105d6Keisuke Kuroynagi const bool sameAsTyped = TRAVERSAL->sameAsTyped(traverseSession, terminalDicNode); 2229a4f7a3761684ee2122485c7ae111f6287d105d6Keisuke Kuroynagi outputWordIndex = ShortcutUtils::outputShortcuts(&terminalAttributes, outputWordIndex, 2239a4f7a3761684ee2122485c7ae111f6287d105d6Keisuke Kuroynagi finalScore, outputCodePoints, frequencies, outputTypes, sameAsTyped); 2249a4f7a3761684ee2122485c7ae111f6287d105d6Keisuke Kuroynagi } 22595fe8267955ba5bfcc3cf38383f0d13026287082Satoshi Kataoka DicNode::managedDelete(terminalDicNode); 22695fe8267955ba5bfcc3cf38383f0d13026287082Satoshi Kataoka } 22795fe8267955ba5bfcc3cf38383f0d13026287082Satoshi Kataoka 22895fe8267955ba5bfcc3cf38383f0d13026287082Satoshi Kataoka if (hasMostProbableString) { 22995fe8267955ba5bfcc3cf38383f0d13026287082Satoshi Kataoka SCORING->safetyNetForMostProbableString(terminalSize, maxScore, 23095fe8267955ba5bfcc3cf38383f0d13026287082Satoshi Kataoka &outputCodePoints[0], &frequencies[0]); 23195fe8267955ba5bfcc3cf38383f0d13026287082Satoshi Kataoka } 23295fe8267955ba5bfcc3cf38383f0d13026287082Satoshi Kataoka return outputWordIndex; 23395fe8267955ba5bfcc3cf38383f0d13026287082Satoshi Kataoka} 23495fe8267955ba5bfcc3cf38383f0d13026287082Satoshi Kataoka 23595fe8267955ba5bfcc3cf38383f0d13026287082Satoshi Kataoka/** 23695fe8267955ba5bfcc3cf38383f0d13026287082Satoshi Kataoka * Expands the dicNodes in the current search priority queue by advancing to the possible child 23795fe8267955ba5bfcc3cf38383f0d13026287082Satoshi Kataoka * nodes based on the next touch point(s) (or no touch points for lookahead) 23895fe8267955ba5bfcc3cf38383f0d13026287082Satoshi Kataoka */ 23995fe8267955ba5bfcc3cf38383f0d13026287082Satoshi Kataokavoid Suggest::expandCurrentDicNodes(DicTraverseSession *traverseSession) const { 24095fe8267955ba5bfcc3cf38383f0d13026287082Satoshi Kataoka const int inputSize = traverseSession->getInputSize(); 24195fe8267955ba5bfcc3cf38383f0d13026287082Satoshi Kataoka DicNodeVector childDicNodes(TRAVERSAL->getDefaultExpandDicNodeSize()); 242fd9f3d97aee97e9d2e5b9016ec61e120c1265b6aTom Ouyang DicNode correctionDicNode; 24395fe8267955ba5bfcc3cf38383f0d13026287082Satoshi Kataoka 24495fe8267955ba5bfcc3cf38383f0d13026287082Satoshi Kataoka // TODO: Find more efficient caching 24595fe8267955ba5bfcc3cf38383f0d13026287082Satoshi Kataoka const bool shouldDepthLevelCache = TRAVERSAL->shouldDepthLevelCache(traverseSession); 24695fe8267955ba5bfcc3cf38383f0d13026287082Satoshi Kataoka if (shouldDepthLevelCache) { 24795fe8267955ba5bfcc3cf38383f0d13026287082Satoshi Kataoka traverseSession->getDicTraverseCache()->updateLastCachedInputIndex(); 24895fe8267955ba5bfcc3cf38383f0d13026287082Satoshi Kataoka } 24995fe8267955ba5bfcc3cf38383f0d13026287082Satoshi Kataoka if (DEBUG_CACHE) { 25095fe8267955ba5bfcc3cf38383f0d13026287082Satoshi Kataoka AKLOGI("expandCurrentDicNodes depth level cache = %d, inputSize = %d", 25195fe8267955ba5bfcc3cf38383f0d13026287082Satoshi Kataoka shouldDepthLevelCache, inputSize); 25295fe8267955ba5bfcc3cf38383f0d13026287082Satoshi Kataoka } 25395fe8267955ba5bfcc3cf38383f0d13026287082Satoshi Kataoka while (traverseSession->getDicTraverseCache()->activeSize() > 0) { 25495fe8267955ba5bfcc3cf38383f0d13026287082Satoshi Kataoka DicNode dicNode; 25595fe8267955ba5bfcc3cf38383f0d13026287082Satoshi Kataoka traverseSession->getDicTraverseCache()->popActive(&dicNode); 25695fe8267955ba5bfcc3cf38383f0d13026287082Satoshi Kataoka if (dicNode.isTotalInputSizeExceedingLimit()) { 25795fe8267955ba5bfcc3cf38383f0d13026287082Satoshi Kataoka return; 25895fe8267955ba5bfcc3cf38383f0d13026287082Satoshi Kataoka } 25995fe8267955ba5bfcc3cf38383f0d13026287082Satoshi Kataoka childDicNodes.clear(); 26095fe8267955ba5bfcc3cf38383f0d13026287082Satoshi Kataoka const int point0Index = dicNode.getInputIndex(0); 26195fe8267955ba5bfcc3cf38383f0d13026287082Satoshi Kataoka const bool canDoLookAheadCorrection = 26295fe8267955ba5bfcc3cf38383f0d13026287082Satoshi Kataoka TRAVERSAL->canDoLookAheadCorrection(traverseSession, &dicNode); 26395fe8267955ba5bfcc3cf38383f0d13026287082Satoshi Kataoka const bool isLookAheadCorrection = canDoLookAheadCorrection 26495fe8267955ba5bfcc3cf38383f0d13026287082Satoshi Kataoka && traverseSession->getDicTraverseCache()-> 26595fe8267955ba5bfcc3cf38383f0d13026287082Satoshi Kataoka isLookAheadCorrectionInputIndex(static_cast<int>(point0Index)); 26695fe8267955ba5bfcc3cf38383f0d13026287082Satoshi Kataoka const bool isCompletion = dicNode.isCompletion(inputSize); 26795fe8267955ba5bfcc3cf38383f0d13026287082Satoshi Kataoka 26895fe8267955ba5bfcc3cf38383f0d13026287082Satoshi Kataoka const bool shouldNodeLevelCache = 26995fe8267955ba5bfcc3cf38383f0d13026287082Satoshi Kataoka TRAVERSAL->shouldNodeLevelCache(traverseSession, &dicNode); 27095fe8267955ba5bfcc3cf38383f0d13026287082Satoshi Kataoka if (shouldDepthLevelCache || shouldNodeLevelCache) { 27195fe8267955ba5bfcc3cf38383f0d13026287082Satoshi Kataoka if (DEBUG_CACHE) { 27295fe8267955ba5bfcc3cf38383f0d13026287082Satoshi Kataoka dicNode.dump("PUSH_CACHE"); 27395fe8267955ba5bfcc3cf38383f0d13026287082Satoshi Kataoka } 27495fe8267955ba5bfcc3cf38383f0d13026287082Satoshi Kataoka traverseSession->getDicTraverseCache()->copyPushContinue(&dicNode); 27595fe8267955ba5bfcc3cf38383f0d13026287082Satoshi Kataoka dicNode.setCached(); 27695fe8267955ba5bfcc3cf38383f0d13026287082Satoshi Kataoka } 27795fe8267955ba5bfcc3cf38383f0d13026287082Satoshi Kataoka 278fd9f3d97aee97e9d2e5b9016ec61e120c1265b6aTom Ouyang if (dicNode.isInDigraph()) { 279fd9f3d97aee97e9d2e5b9016ec61e120c1265b6aTom Ouyang // Finish digraph handling if the node is in the middle of a digraph expansion. 280fd9f3d97aee97e9d2e5b9016ec61e120c1265b6aTom Ouyang processDicNodeAsDigraph(traverseSession, &dicNode); 281fd9f3d97aee97e9d2e5b9016ec61e120c1265b6aTom Ouyang } else if (isLookAheadCorrection) { 28295fe8267955ba5bfcc3cf38383f0d13026287082Satoshi Kataoka // The algorithm maintains a small set of "deferred" nodes that have not consumed the 28395fe8267955ba5bfcc3cf38383f0d13026287082Satoshi Kataoka // latest touch point yet. These are needed to apply look-ahead correction operations 28495fe8267955ba5bfcc3cf38383f0d13026287082Satoshi Kataoka // that require special handling of the latest touch point. For example, with insertions 28595fe8267955ba5bfcc3cf38383f0d13026287082Satoshi Kataoka // (e.g., "thiis" -> "this") the latest touch point should not be consumed at all. 286252412d7eb4573f91588b06b0fe49ef9f0ac38acSatoshi Kataoka processDicNodeAsTransposition(traverseSession, &dicNode); 287252412d7eb4573f91588b06b0fe49ef9f0ac38acSatoshi Kataoka processDicNodeAsInsertion(traverseSession, &dicNode); 28895fe8267955ba5bfcc3cf38383f0d13026287082Satoshi Kataoka } else { // !isLookAheadCorrection 28995fe8267955ba5bfcc3cf38383f0d13026287082Satoshi Kataoka // Only consider typing error corrections if the normalized compound distance is 29095fe8267955ba5bfcc3cf38383f0d13026287082Satoshi Kataoka // below a spatial distance threshold. 29195fe8267955ba5bfcc3cf38383f0d13026287082Satoshi Kataoka // NOTE: the threshold may need to be updated if scoring model changes. 29295fe8267955ba5bfcc3cf38383f0d13026287082Satoshi Kataoka // TODO: Remove. Do not prune node here. 29395fe8267955ba5bfcc3cf38383f0d13026287082Satoshi Kataoka const bool allowsErrorCorrections = TRAVERSAL->allowsErrorCorrections(&dicNode); 29495fe8267955ba5bfcc3cf38383f0d13026287082Satoshi Kataoka // Process for handling space substitution (e.g., hevis => he is) 29595fe8267955ba5bfcc3cf38383f0d13026287082Satoshi Kataoka if (allowsErrorCorrections 29695fe8267955ba5bfcc3cf38383f0d13026287082Satoshi Kataoka && TRAVERSAL->isSpaceSubstitutionTerminal(traverseSession, &dicNode)) { 29795fe8267955ba5bfcc3cf38383f0d13026287082Satoshi Kataoka createNextWordDicNode(traverseSession, &dicNode, true /* spaceSubstitution */); 29895fe8267955ba5bfcc3cf38383f0d13026287082Satoshi Kataoka } 29995fe8267955ba5bfcc3cf38383f0d13026287082Satoshi Kataoka 30095fe8267955ba5bfcc3cf38383f0d13026287082Satoshi Kataoka DicNodeUtils::getAllChildDicNodes( 3010ecfb9424754341d7ee41557fc1f913cb6ca79c2Keisuke Kuroyanagi &dicNode, traverseSession->getBinaryDictionaryInfo(), &childDicNodes); 30295fe8267955ba5bfcc3cf38383f0d13026287082Satoshi Kataoka 30395fe8267955ba5bfcc3cf38383f0d13026287082Satoshi Kataoka const int childDicNodesSize = childDicNodes.getSizeAndLock(); 30495fe8267955ba5bfcc3cf38383f0d13026287082Satoshi Kataoka for (int i = 0; i < childDicNodesSize; ++i) { 30595fe8267955ba5bfcc3cf38383f0d13026287082Satoshi Kataoka DicNode *const childDicNode = childDicNodes[i]; 30695fe8267955ba5bfcc3cf38383f0d13026287082Satoshi Kataoka if (isCompletion) { 30795fe8267955ba5bfcc3cf38383f0d13026287082Satoshi Kataoka // Handle forward lookahead when the lexicon letter exceeds the input size. 30895fe8267955ba5bfcc3cf38383f0d13026287082Satoshi Kataoka processDicNodeAsMatch(traverseSession, childDicNode); 30995fe8267955ba5bfcc3cf38383f0d13026287082Satoshi Kataoka continue; 31095fe8267955ba5bfcc3cf38383f0d13026287082Satoshi Kataoka } 311bd0d1afdb28a28e2ddac1409208c59ba64350399Keisuke Kuroynagi if (DigraphUtils::hasDigraphForCodePoint( 312bd0d1afdb28a28e2ddac1409208c59ba64350399Keisuke Kuroynagi traverseSession->getBinaryDictionaryInfo()->getHeader(), 313fd9f3d97aee97e9d2e5b9016ec61e120c1265b6aTom Ouyang childDicNode->getNodeCodePoint())) { 314fd9f3d97aee97e9d2e5b9016ec61e120c1265b6aTom Ouyang correctionDicNode.initByCopy(childDicNode); 315fd9f3d97aee97e9d2e5b9016ec61e120c1265b6aTom Ouyang correctionDicNode.advanceDigraphIndex(); 316fd9f3d97aee97e9d2e5b9016ec61e120c1265b6aTom Ouyang processDicNodeAsDigraph(traverseSession, &correctionDicNode); 317fd9f3d97aee97e9d2e5b9016ec61e120c1265b6aTom Ouyang } 318fd02ec10f0a0374096e88fa30a0e126d6ff11c72Tom Ouyang if (TRAVERSAL->isOmission(traverseSession, &dicNode, childDicNode, 319fd02ec10f0a0374096e88fa30a0e126d6ff11c72Tom Ouyang allowsErrorCorrections)) { 32095fe8267955ba5bfcc3cf38383f0d13026287082Satoshi Kataoka // TODO: (Gesture) Change weight between omission and substitution errors 32195fe8267955ba5bfcc3cf38383f0d13026287082Satoshi Kataoka // TODO: (Gesture) Terminal node should not be handled as omission 322fd9f3d97aee97e9d2e5b9016ec61e120c1265b6aTom Ouyang correctionDicNode.initByCopy(childDicNode); 323fd9f3d97aee97e9d2e5b9016ec61e120c1265b6aTom Ouyang processDicNodeAsOmission(traverseSession, &correctionDicNode); 32495fe8267955ba5bfcc3cf38383f0d13026287082Satoshi Kataoka } 32595fe8267955ba5bfcc3cf38383f0d13026287082Satoshi Kataoka const ProximityType proximityType = TRAVERSAL->getProximityType( 32695fe8267955ba5bfcc3cf38383f0d13026287082Satoshi Kataoka traverseSession, &dicNode, childDicNode); 32795fe8267955ba5bfcc3cf38383f0d13026287082Satoshi Kataoka switch (proximityType) { 32895fe8267955ba5bfcc3cf38383f0d13026287082Satoshi Kataoka // TODO: Consider the difference of proximityType here 32995fe8267955ba5bfcc3cf38383f0d13026287082Satoshi Kataoka case MATCH_CHAR: 33095fe8267955ba5bfcc3cf38383f0d13026287082Satoshi Kataoka case PROXIMITY_CHAR: 33195fe8267955ba5bfcc3cf38383f0d13026287082Satoshi Kataoka processDicNodeAsMatch(traverseSession, childDicNode); 33295fe8267955ba5bfcc3cf38383f0d13026287082Satoshi Kataoka break; 33395fe8267955ba5bfcc3cf38383f0d13026287082Satoshi Kataoka case ADDITIONAL_PROXIMITY_CHAR: 33495fe8267955ba5bfcc3cf38383f0d13026287082Satoshi Kataoka if (allowsErrorCorrections) { 33595fe8267955ba5bfcc3cf38383f0d13026287082Satoshi Kataoka processDicNodeAsAdditionalProximityChar(traverseSession, &dicNode, 33695fe8267955ba5bfcc3cf38383f0d13026287082Satoshi Kataoka childDicNode); 33795fe8267955ba5bfcc3cf38383f0d13026287082Satoshi Kataoka } 33895fe8267955ba5bfcc3cf38383f0d13026287082Satoshi Kataoka break; 33995fe8267955ba5bfcc3cf38383f0d13026287082Satoshi Kataoka case SUBSTITUTION_CHAR: 34095fe8267955ba5bfcc3cf38383f0d13026287082Satoshi Kataoka if (allowsErrorCorrections) { 34195fe8267955ba5bfcc3cf38383f0d13026287082Satoshi Kataoka processDicNodeAsSubstitution(traverseSession, &dicNode, childDicNode); 34295fe8267955ba5bfcc3cf38383f0d13026287082Satoshi Kataoka } 34395fe8267955ba5bfcc3cf38383f0d13026287082Satoshi Kataoka break; 34495fe8267955ba5bfcc3cf38383f0d13026287082Satoshi Kataoka case UNRELATED_CHAR: 34595fe8267955ba5bfcc3cf38383f0d13026287082Satoshi Kataoka // Just drop this node and do nothing. 34695fe8267955ba5bfcc3cf38383f0d13026287082Satoshi Kataoka break; 34795fe8267955ba5bfcc3cf38383f0d13026287082Satoshi Kataoka default: 34895fe8267955ba5bfcc3cf38383f0d13026287082Satoshi Kataoka // Just drop this node and do nothing. 34995fe8267955ba5bfcc3cf38383f0d13026287082Satoshi Kataoka break; 35095fe8267955ba5bfcc3cf38383f0d13026287082Satoshi Kataoka } 35195fe8267955ba5bfcc3cf38383f0d13026287082Satoshi Kataoka } 35295fe8267955ba5bfcc3cf38383f0d13026287082Satoshi Kataoka 35395fe8267955ba5bfcc3cf38383f0d13026287082Satoshi Kataoka // Push the node for look-ahead correction 35495fe8267955ba5bfcc3cf38383f0d13026287082Satoshi Kataoka if (allowsErrorCorrections && canDoLookAheadCorrection) { 35595fe8267955ba5bfcc3cf38383f0d13026287082Satoshi Kataoka traverseSession->getDicTraverseCache()->copyPushNextActive(&dicNode); 35695fe8267955ba5bfcc3cf38383f0d13026287082Satoshi Kataoka } 35795fe8267955ba5bfcc3cf38383f0d13026287082Satoshi Kataoka } 35895fe8267955ba5bfcc3cf38383f0d13026287082Satoshi Kataoka } 35995fe8267955ba5bfcc3cf38383f0d13026287082Satoshi Kataoka} 36095fe8267955ba5bfcc3cf38383f0d13026287082Satoshi Kataoka 36195fe8267955ba5bfcc3cf38383f0d13026287082Satoshi Kataokavoid Suggest::processTerminalDicNode( 36295fe8267955ba5bfcc3cf38383f0d13026287082Satoshi Kataoka DicTraverseSession *traverseSession, DicNode *dicNode) const { 36395fe8267955ba5bfcc3cf38383f0d13026287082Satoshi Kataoka if (dicNode->getCompoundDistance() >= static_cast<float>(MAX_VALUE_FOR_WEIGHTING)) { 36495fe8267955ba5bfcc3cf38383f0d13026287082Satoshi Kataoka return; 36595fe8267955ba5bfcc3cf38383f0d13026287082Satoshi Kataoka } 36695fe8267955ba5bfcc3cf38383f0d13026287082Satoshi Kataoka if (!dicNode->isTerminalWordNode()) { 36795fe8267955ba5bfcc3cf38383f0d13026287082Satoshi Kataoka return; 36895fe8267955ba5bfcc3cf38383f0d13026287082Satoshi Kataoka } 36995fe8267955ba5bfcc3cf38383f0d13026287082Satoshi Kataoka if (dicNode->shouldBeFilterdBySafetyNetForBigram()) { 37095fe8267955ba5bfcc3cf38383f0d13026287082Satoshi Kataoka return; 37195fe8267955ba5bfcc3cf38383f0d13026287082Satoshi Kataoka } 37295fe8267955ba5bfcc3cf38383f0d13026287082Satoshi Kataoka // Create a non-cached node here. 37395fe8267955ba5bfcc3cf38383f0d13026287082Satoshi Kataoka DicNode terminalDicNode; 37495fe8267955ba5bfcc3cf38383f0d13026287082Satoshi Kataoka DicNodeUtils::initByCopy(dicNode, &terminalDicNode); 37575322cecb9fe02a0914b65c859cfbc2f4e1f70d9Satoshi Kataoka if (TRAVERSAL->needsToTraverseAllUserInput() 37675322cecb9fe02a0914b65c859cfbc2f4e1f70d9Satoshi Kataoka && dicNode->getInputIndex(0) < traverseSession->getInputSize()) { 37775322cecb9fe02a0914b65c859cfbc2f4e1f70d9Satoshi Kataoka Weighting::addCostAndForwardInputIndex(WEIGHTING, CT_TERMINAL_INSERTION, traverseSession, 0, 37875322cecb9fe02a0914b65c859cfbc2f4e1f70d9Satoshi Kataoka &terminalDicNode, traverseSession->getMultiBigramMap()); 37975322cecb9fe02a0914b65c859cfbc2f4e1f70d9Satoshi Kataoka } 38095fe8267955ba5bfcc3cf38383f0d13026287082Satoshi Kataoka Weighting::addCostAndForwardInputIndex(WEIGHTING, CT_TERMINAL, traverseSession, 0, 3819559dd2e30de288a9ff7069bfc59f8500b949a88Tom Ouyang &terminalDicNode, traverseSession->getMultiBigramMap()); 38295fe8267955ba5bfcc3cf38383f0d13026287082Satoshi Kataoka traverseSession->getDicTraverseCache()->copyPushTerminal(&terminalDicNode); 38395fe8267955ba5bfcc3cf38383f0d13026287082Satoshi Kataoka} 38495fe8267955ba5bfcc3cf38383f0d13026287082Satoshi Kataoka 38595fe8267955ba5bfcc3cf38383f0d13026287082Satoshi Kataoka/** 38695fe8267955ba5bfcc3cf38383f0d13026287082Satoshi Kataoka * Adds the expanded dicNode to the next search priority queue. Also creates an additional next word 38795fe8267955ba5bfcc3cf38383f0d13026287082Satoshi Kataoka * (by the space omission error correction) search path if input dicNode is on a terminal node. 38895fe8267955ba5bfcc3cf38383f0d13026287082Satoshi Kataoka */ 38995fe8267955ba5bfcc3cf38383f0d13026287082Satoshi Kataokavoid Suggest::processExpandedDicNode( 39095fe8267955ba5bfcc3cf38383f0d13026287082Satoshi Kataoka DicTraverseSession *traverseSession, DicNode *dicNode) const { 39195fe8267955ba5bfcc3cf38383f0d13026287082Satoshi Kataoka processTerminalDicNode(traverseSession, dicNode); 39295fe8267955ba5bfcc3cf38383f0d13026287082Satoshi Kataoka if (dicNode->getCompoundDistance() < static_cast<float>(MAX_VALUE_FOR_WEIGHTING)) { 39395fe8267955ba5bfcc3cf38383f0d13026287082Satoshi Kataoka if (TRAVERSAL->isSpaceOmissionTerminal(traverseSession, dicNode)) { 39495fe8267955ba5bfcc3cf38383f0d13026287082Satoshi Kataoka createNextWordDicNode(traverseSession, dicNode, false /* spaceSubstitution */); 39595fe8267955ba5bfcc3cf38383f0d13026287082Satoshi Kataoka } 39695fe8267955ba5bfcc3cf38383f0d13026287082Satoshi Kataoka const int allowsLookAhead = !(dicNode->hasMultipleWords() 39795fe8267955ba5bfcc3cf38383f0d13026287082Satoshi Kataoka && dicNode->isCompletion(traverseSession->getInputSize())); 39895fe8267955ba5bfcc3cf38383f0d13026287082Satoshi Kataoka if (dicNode->hasChildren() && allowsLookAhead) { 39995fe8267955ba5bfcc3cf38383f0d13026287082Satoshi Kataoka traverseSession->getDicTraverseCache()->copyPushNextActive(dicNode); 40095fe8267955ba5bfcc3cf38383f0d13026287082Satoshi Kataoka } 40195fe8267955ba5bfcc3cf38383f0d13026287082Satoshi Kataoka } 40295fe8267955ba5bfcc3cf38383f0d13026287082Satoshi Kataoka DicNode::managedDelete(dicNode); 40395fe8267955ba5bfcc3cf38383f0d13026287082Satoshi Kataoka} 40495fe8267955ba5bfcc3cf38383f0d13026287082Satoshi Kataoka 40595fe8267955ba5bfcc3cf38383f0d13026287082Satoshi Kataokavoid Suggest::processDicNodeAsMatch(DicTraverseSession *traverseSession, 40695fe8267955ba5bfcc3cf38383f0d13026287082Satoshi Kataoka DicNode *childDicNode) const { 40795fe8267955ba5bfcc3cf38383f0d13026287082Satoshi Kataoka weightChildNode(traverseSession, childDicNode); 40895fe8267955ba5bfcc3cf38383f0d13026287082Satoshi Kataoka processExpandedDicNode(traverseSession, childDicNode); 40995fe8267955ba5bfcc3cf38383f0d13026287082Satoshi Kataoka} 41095fe8267955ba5bfcc3cf38383f0d13026287082Satoshi Kataoka 41195fe8267955ba5bfcc3cf38383f0d13026287082Satoshi Kataokavoid Suggest::processDicNodeAsAdditionalProximityChar(DicTraverseSession *traverseSession, 41295fe8267955ba5bfcc3cf38383f0d13026287082Satoshi Kataoka DicNode *dicNode, DicNode *childDicNode) const { 4139559dd2e30de288a9ff7069bfc59f8500b949a88Tom Ouyang // Note: Most types of corrections don't need to look up the bigram information since they do 4149559dd2e30de288a9ff7069bfc59f8500b949a88Tom Ouyang // not treat the node as a terminal. There is no need to pass the bigram map in these cases. 41595fe8267955ba5bfcc3cf38383f0d13026287082Satoshi Kataoka Weighting::addCostAndForwardInputIndex(WEIGHTING, CT_ADDITIONAL_PROXIMITY, 4169559dd2e30de288a9ff7069bfc59f8500b949a88Tom Ouyang traverseSession, dicNode, childDicNode, 0 /* multiBigramMap */); 41795fe8267955ba5bfcc3cf38383f0d13026287082Satoshi Kataoka weightChildNode(traverseSession, childDicNode); 41895fe8267955ba5bfcc3cf38383f0d13026287082Satoshi Kataoka processExpandedDicNode(traverseSession, childDicNode); 41995fe8267955ba5bfcc3cf38383f0d13026287082Satoshi Kataoka} 42095fe8267955ba5bfcc3cf38383f0d13026287082Satoshi Kataoka 42195fe8267955ba5bfcc3cf38383f0d13026287082Satoshi Kataokavoid Suggest::processDicNodeAsSubstitution(DicTraverseSession *traverseSession, 42295fe8267955ba5bfcc3cf38383f0d13026287082Satoshi Kataoka DicNode *dicNode, DicNode *childDicNode) const { 42395fe8267955ba5bfcc3cf38383f0d13026287082Satoshi Kataoka Weighting::addCostAndForwardInputIndex(WEIGHTING, CT_SUBSTITUTION, traverseSession, 4249559dd2e30de288a9ff7069bfc59f8500b949a88Tom Ouyang dicNode, childDicNode, 0 /* multiBigramMap */); 42595fe8267955ba5bfcc3cf38383f0d13026287082Satoshi Kataoka weightChildNode(traverseSession, childDicNode); 42695fe8267955ba5bfcc3cf38383f0d13026287082Satoshi Kataoka processExpandedDicNode(traverseSession, childDicNode); 42795fe8267955ba5bfcc3cf38383f0d13026287082Satoshi Kataoka} 42895fe8267955ba5bfcc3cf38383f0d13026287082Satoshi Kataoka 429fd9f3d97aee97e9d2e5b9016ec61e120c1265b6aTom Ouyang// Process the node codepoint as a digraph. This means that composite glyphs like the German 430fd9f3d97aee97e9d2e5b9016ec61e120c1265b6aTom Ouyang// u-umlaut is expanded to the transliteration "ue". Note that this happens in parallel with 431fd9f3d97aee97e9d2e5b9016ec61e120c1265b6aTom Ouyang// the normal non-digraph traversal, so both "uber" and "ueber" can be corrected to "[u-umlaut]ber". 432fd9f3d97aee97e9d2e5b9016ec61e120c1265b6aTom Ouyangvoid Suggest::processDicNodeAsDigraph(DicTraverseSession *traverseSession, 433fd9f3d97aee97e9d2e5b9016ec61e120c1265b6aTom Ouyang DicNode *childDicNode) const { 434fd9f3d97aee97e9d2e5b9016ec61e120c1265b6aTom Ouyang weightChildNode(traverseSession, childDicNode); 435fd9f3d97aee97e9d2e5b9016ec61e120c1265b6aTom Ouyang childDicNode->advanceDigraphIndex(); 436fd9f3d97aee97e9d2e5b9016ec61e120c1265b6aTom Ouyang processExpandedDicNode(traverseSession, childDicNode); 437fd9f3d97aee97e9d2e5b9016ec61e120c1265b6aTom Ouyang} 438fd9f3d97aee97e9d2e5b9016ec61e120c1265b6aTom Ouyang 43995fe8267955ba5bfcc3cf38383f0d13026287082Satoshi Kataoka/** 44095fe8267955ba5bfcc3cf38383f0d13026287082Satoshi Kataoka * Handle the dicNode as an omission error (e.g., ths => this). Skip the current letter and consider 44195fe8267955ba5bfcc3cf38383f0d13026287082Satoshi Kataoka * matches for all possible next letters. Note that just skipping the current letter without any 44295fe8267955ba5bfcc3cf38383f0d13026287082Satoshi Kataoka * other conditions tends to flood the search dic nodes cache with omission nodes. Instead, check 44395fe8267955ba5bfcc3cf38383f0d13026287082Satoshi Kataoka * the possible *next* letters after the omission to better limit search to plausible omissions. 44495fe8267955ba5bfcc3cf38383f0d13026287082Satoshi Kataoka * Note that apostrophes are handled as omissions. 44595fe8267955ba5bfcc3cf38383f0d13026287082Satoshi Kataoka */ 44695fe8267955ba5bfcc3cf38383f0d13026287082Satoshi Kataokavoid Suggest::processDicNodeAsOmission( 44795fe8267955ba5bfcc3cf38383f0d13026287082Satoshi Kataoka DicTraverseSession *traverseSession, DicNode *dicNode) const { 44895fe8267955ba5bfcc3cf38383f0d13026287082Satoshi Kataoka DicNodeVector childDicNodes; 4490ecfb9424754341d7ee41557fc1f913cb6ca79c2Keisuke Kuroyanagi DicNodeUtils::getAllChildDicNodes( 4500ecfb9424754341d7ee41557fc1f913cb6ca79c2Keisuke Kuroyanagi dicNode, traverseSession->getBinaryDictionaryInfo(), &childDicNodes); 45195fe8267955ba5bfcc3cf38383f0d13026287082Satoshi Kataoka 45295fe8267955ba5bfcc3cf38383f0d13026287082Satoshi Kataoka const int size = childDicNodes.getSizeAndLock(); 45395fe8267955ba5bfcc3cf38383f0d13026287082Satoshi Kataoka for (int i = 0; i < size; i++) { 45495fe8267955ba5bfcc3cf38383f0d13026287082Satoshi Kataoka DicNode *const childDicNode = childDicNodes[i]; 45560a169f0c34bf0da89c420d99bfff5c2556f3fbfKeisuke Kuroynagi // Treat this word as omission 45660a169f0c34bf0da89c420d99bfff5c2556f3fbfKeisuke Kuroynagi Weighting::addCostAndForwardInputIndex(WEIGHTING, CT_OMISSION, traverseSession, 4579559dd2e30de288a9ff7069bfc59f8500b949a88Tom Ouyang dicNode, childDicNode, 0 /* multiBigramMap */); 45895fe8267955ba5bfcc3cf38383f0d13026287082Satoshi Kataoka weightChildNode(traverseSession, childDicNode); 45995fe8267955ba5bfcc3cf38383f0d13026287082Satoshi Kataoka 46095fe8267955ba5bfcc3cf38383f0d13026287082Satoshi Kataoka if (!TRAVERSAL->isPossibleOmissionChildNode(traverseSession, dicNode, childDicNode)) { 46195fe8267955ba5bfcc3cf38383f0d13026287082Satoshi Kataoka continue; 46295fe8267955ba5bfcc3cf38383f0d13026287082Satoshi Kataoka } 46395fe8267955ba5bfcc3cf38383f0d13026287082Satoshi Kataoka processExpandedDicNode(traverseSession, childDicNode); 46495fe8267955ba5bfcc3cf38383f0d13026287082Satoshi Kataoka } 46595fe8267955ba5bfcc3cf38383f0d13026287082Satoshi Kataoka} 46695fe8267955ba5bfcc3cf38383f0d13026287082Satoshi Kataoka 46795fe8267955ba5bfcc3cf38383f0d13026287082Satoshi Kataoka/** 46895fe8267955ba5bfcc3cf38383f0d13026287082Satoshi Kataoka * Handle the dicNode as an insertion error (e.g., thiis => this). Skip the current touch point and 46995fe8267955ba5bfcc3cf38383f0d13026287082Satoshi Kataoka * consider matches for the next touch point. 47095fe8267955ba5bfcc3cf38383f0d13026287082Satoshi Kataoka */ 47195fe8267955ba5bfcc3cf38383f0d13026287082Satoshi Kataokavoid Suggest::processDicNodeAsInsertion(DicTraverseSession *traverseSession, 47295fe8267955ba5bfcc3cf38383f0d13026287082Satoshi Kataoka DicNode *dicNode) const { 47395fe8267955ba5bfcc3cf38383f0d13026287082Satoshi Kataoka const int16_t pointIndex = dicNode->getInputIndex(0); 47495fe8267955ba5bfcc3cf38383f0d13026287082Satoshi Kataoka DicNodeVector childDicNodes; 4750ecfb9424754341d7ee41557fc1f913cb6ca79c2Keisuke Kuroyanagi DicNodeUtils::getProximityChildDicNodes(dicNode, traverseSession->getBinaryDictionaryInfo(), 47695fe8267955ba5bfcc3cf38383f0d13026287082Satoshi Kataoka traverseSession->getProximityInfoState(0), pointIndex + 1, true, &childDicNodes); 47795fe8267955ba5bfcc3cf38383f0d13026287082Satoshi Kataoka const int size = childDicNodes.getSizeAndLock(); 47895fe8267955ba5bfcc3cf38383f0d13026287082Satoshi Kataoka for (int i = 0; i < size; i++) { 47995fe8267955ba5bfcc3cf38383f0d13026287082Satoshi Kataoka DicNode *const childDicNode = childDicNodes[i]; 48095fe8267955ba5bfcc3cf38383f0d13026287082Satoshi Kataoka Weighting::addCostAndForwardInputIndex(WEIGHTING, CT_INSERTION, traverseSession, 4819559dd2e30de288a9ff7069bfc59f8500b949a88Tom Ouyang dicNode, childDicNode, 0 /* multiBigramMap */); 48295fe8267955ba5bfcc3cf38383f0d13026287082Satoshi Kataoka processExpandedDicNode(traverseSession, childDicNode); 48395fe8267955ba5bfcc3cf38383f0d13026287082Satoshi Kataoka } 48495fe8267955ba5bfcc3cf38383f0d13026287082Satoshi Kataoka} 48595fe8267955ba5bfcc3cf38383f0d13026287082Satoshi Kataoka 48695fe8267955ba5bfcc3cf38383f0d13026287082Satoshi Kataoka/** 48795fe8267955ba5bfcc3cf38383f0d13026287082Satoshi Kataoka * Handle the dicNode as a transposition error (e.g., thsi => this). Swap the next two touch points. 48895fe8267955ba5bfcc3cf38383f0d13026287082Satoshi Kataoka */ 48995fe8267955ba5bfcc3cf38383f0d13026287082Satoshi Kataokavoid Suggest::processDicNodeAsTransposition(DicTraverseSession *traverseSession, 49095fe8267955ba5bfcc3cf38383f0d13026287082Satoshi Kataoka DicNode *dicNode) const { 49195fe8267955ba5bfcc3cf38383f0d13026287082Satoshi Kataoka const int16_t pointIndex = dicNode->getInputIndex(0); 49295fe8267955ba5bfcc3cf38383f0d13026287082Satoshi Kataoka DicNodeVector childDicNodes1; 4930ecfb9424754341d7ee41557fc1f913cb6ca79c2Keisuke Kuroyanagi DicNodeUtils::getProximityChildDicNodes(dicNode, traverseSession->getBinaryDictionaryInfo(), 49495fe8267955ba5bfcc3cf38383f0d13026287082Satoshi Kataoka traverseSession->getProximityInfoState(0), pointIndex + 1, false, &childDicNodes1); 49595fe8267955ba5bfcc3cf38383f0d13026287082Satoshi Kataoka const int childSize1 = childDicNodes1.getSizeAndLock(); 49695fe8267955ba5bfcc3cf38383f0d13026287082Satoshi Kataoka for (int i = 0; i < childSize1; i++) { 49795fe8267955ba5bfcc3cf38383f0d13026287082Satoshi Kataoka if (childDicNodes1[i]->hasChildren()) { 49895fe8267955ba5bfcc3cf38383f0d13026287082Satoshi Kataoka DicNodeVector childDicNodes2; 49995fe8267955ba5bfcc3cf38383f0d13026287082Satoshi Kataoka DicNodeUtils::getProximityChildDicNodes( 5000ecfb9424754341d7ee41557fc1f913cb6ca79c2Keisuke Kuroyanagi childDicNodes1[i], traverseSession->getBinaryDictionaryInfo(), 50195fe8267955ba5bfcc3cf38383f0d13026287082Satoshi Kataoka traverseSession->getProximityInfoState(0), pointIndex, false, &childDicNodes2); 50295fe8267955ba5bfcc3cf38383f0d13026287082Satoshi Kataoka const int childSize2 = childDicNodes2.getSizeAndLock(); 50395fe8267955ba5bfcc3cf38383f0d13026287082Satoshi Kataoka for (int j = 0; j < childSize2; j++) { 50495fe8267955ba5bfcc3cf38383f0d13026287082Satoshi Kataoka DicNode *const childDicNode2 = childDicNodes2[j]; 50595fe8267955ba5bfcc3cf38383f0d13026287082Satoshi Kataoka Weighting::addCostAndForwardInputIndex(WEIGHTING, CT_TRANSPOSITION, 5069559dd2e30de288a9ff7069bfc59f8500b949a88Tom Ouyang traverseSession, childDicNodes1[i], childDicNode2, 0 /* multiBigramMap */); 50795fe8267955ba5bfcc3cf38383f0d13026287082Satoshi Kataoka processExpandedDicNode(traverseSession, childDicNode2); 50895fe8267955ba5bfcc3cf38383f0d13026287082Satoshi Kataoka } 50995fe8267955ba5bfcc3cf38383f0d13026287082Satoshi Kataoka } 51095fe8267955ba5bfcc3cf38383f0d13026287082Satoshi Kataoka DicNode::managedDelete(childDicNodes1[i]); 51195fe8267955ba5bfcc3cf38383f0d13026287082Satoshi Kataoka } 51295fe8267955ba5bfcc3cf38383f0d13026287082Satoshi Kataoka} 51395fe8267955ba5bfcc3cf38383f0d13026287082Satoshi Kataoka 51495fe8267955ba5bfcc3cf38383f0d13026287082Satoshi Kataoka/** 51595fe8267955ba5bfcc3cf38383f0d13026287082Satoshi Kataoka * Weight child node by aligning it to the key 51695fe8267955ba5bfcc3cf38383f0d13026287082Satoshi Kataoka */ 51795fe8267955ba5bfcc3cf38383f0d13026287082Satoshi Kataokavoid Suggest::weightChildNode(DicTraverseSession *traverseSession, DicNode *dicNode) const { 51895fe8267955ba5bfcc3cf38383f0d13026287082Satoshi Kataoka const int inputSize = traverseSession->getInputSize(); 51995fe8267955ba5bfcc3cf38383f0d13026287082Satoshi Kataoka if (dicNode->isCompletion(inputSize)) { 52095fe8267955ba5bfcc3cf38383f0d13026287082Satoshi Kataoka Weighting::addCostAndForwardInputIndex(WEIGHTING, CT_COMPLETION, traverseSession, 5219559dd2e30de288a9ff7069bfc59f8500b949a88Tom Ouyang 0 /* parentDicNode */, dicNode, 0 /* multiBigramMap */); 52295fe8267955ba5bfcc3cf38383f0d13026287082Satoshi Kataoka } else { // completion 52395fe8267955ba5bfcc3cf38383f0d13026287082Satoshi Kataoka Weighting::addCostAndForwardInputIndex(WEIGHTING, CT_MATCH, traverseSession, 5249559dd2e30de288a9ff7069bfc59f8500b949a88Tom Ouyang 0 /* parentDicNode */, dicNode, 0 /* multiBigramMap */); 52595fe8267955ba5bfcc3cf38383f0d13026287082Satoshi Kataoka } 52695fe8267955ba5bfcc3cf38383f0d13026287082Satoshi Kataoka} 52795fe8267955ba5bfcc3cf38383f0d13026287082Satoshi Kataoka 52895fe8267955ba5bfcc3cf38383f0d13026287082Satoshi Kataoka/** 52995fe8267955ba5bfcc3cf38383f0d13026287082Satoshi Kataoka * Creates a new dicNode that represents a space insertion at the end of the input dicNode. Also 53095fe8267955ba5bfcc3cf38383f0d13026287082Satoshi Kataoka * incorporates the unigram / bigram score for the ending word into the new dicNode. 53195fe8267955ba5bfcc3cf38383f0d13026287082Satoshi Kataoka */ 53295fe8267955ba5bfcc3cf38383f0d13026287082Satoshi Kataokavoid Suggest::createNextWordDicNode(DicTraverseSession *traverseSession, DicNode *dicNode, 53395fe8267955ba5bfcc3cf38383f0d13026287082Satoshi Kataoka const bool spaceSubstitution) const { 53495fe8267955ba5bfcc3cf38383f0d13026287082Satoshi Kataoka if (!TRAVERSAL->isGoodToTraverseNextWord(dicNode)) { 53595fe8267955ba5bfcc3cf38383f0d13026287082Satoshi Kataoka return; 53695fe8267955ba5bfcc3cf38383f0d13026287082Satoshi Kataoka } 53795fe8267955ba5bfcc3cf38383f0d13026287082Satoshi Kataoka 53895fe8267955ba5bfcc3cf38383f0d13026287082Satoshi Kataoka // Create a non-cached node here. 53995fe8267955ba5bfcc3cf38383f0d13026287082Satoshi Kataoka DicNode newDicNode; 5400ecfb9424754341d7ee41557fc1f913cb6ca79c2Keisuke Kuroyanagi DicNodeUtils::initAsRootWithPreviousWord( 5410ecfb9424754341d7ee41557fc1f913cb6ca79c2Keisuke Kuroyanagi traverseSession->getBinaryDictionaryInfo(), dicNode, &newDicNode); 542252412d7eb4573f91588b06b0fe49ef9f0ac38acSatoshi Kataoka const CorrectionType correctionType = spaceSubstitution ? 543252412d7eb4573f91588b06b0fe49ef9f0ac38acSatoshi Kataoka CT_NEW_WORD_SPACE_SUBSTITUTION : CT_NEW_WORD_SPACE_OMITTION; 544252412d7eb4573f91588b06b0fe49ef9f0ac38acSatoshi Kataoka Weighting::addCostAndForwardInputIndex(WEIGHTING, correctionType, traverseSession, dicNode, 5459559dd2e30de288a9ff7069bfc59f8500b949a88Tom Ouyang &newDicNode, traverseSession->getMultiBigramMap()); 5462d3f2daf12643e57f15fc98c7fd61329513ca0cfKeisuke Kuroynagi if (newDicNode.getCompoundDistance() < static_cast<float>(MAX_VALUE_FOR_WEIGHTING)) { 5472d3f2daf12643e57f15fc98c7fd61329513ca0cfKeisuke Kuroynagi // newDicNode is worth continuing to traverse. 5482d3f2daf12643e57f15fc98c7fd61329513ca0cfKeisuke Kuroynagi // CAVEAT: This pruning is important for speed. Remove this when we can afford not to prune 5492d3f2daf12643e57f15fc98c7fd61329513ca0cfKeisuke Kuroynagi // here because here is not the right place to do pruning. Pruning should take place only 5502d3f2daf12643e57f15fc98c7fd61329513ca0cfKeisuke Kuroynagi // in DicNodePriorityQueue. 5512d3f2daf12643e57f15fc98c7fd61329513ca0cfKeisuke Kuroynagi traverseSession->getDicTraverseCache()->copyPushNextActive(&newDicNode); 5522d3f2daf12643e57f15fc98c7fd61329513ca0cfKeisuke Kuroynagi } 55395fe8267955ba5bfcc3cf38383f0d13026287082Satoshi Kataoka} 55495fe8267955ba5bfcc3cf38383f0d13026287082Satoshi Kataoka} // namespace latinime 555