blob: e523b2f2c98eb18841e0c324b0922502fe9913f8 [file] [log] [blame]
satok30088252010-12-01 21:22:15 +09001/*
2**
3** Copyright 2010, The Android Open Source Project
4**
5** Licensed under the Apache License, Version 2.0 (the "License");
6** you may not use this file except in compliance with the License.
7** You may obtain a copy of the License at
8**
9** http://www.apache.org/licenses/LICENSE-2.0
10**
11** Unless required by applicable law or agreed to in writing, software
12** distributed under the License is distributed on an "AS IS" BASIS,
13** WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
14** See the License for the specific language governing permissions and
15** limitations under the License.
16*/
17
satok48e432c2010-12-06 17:38:58 +090018#include <assert.h>
satok30088252010-12-01 21:22:15 +090019#include <string.h>
20
satoke808e432010-12-02 14:53:24 +090021#define LOG_TAG "LatinIME: unigram_dictionary.cpp"
satok30088252010-12-01 21:22:15 +090022
satok30088252010-12-01 21:22:15 +090023#include "char_utils.h"
Ken Wakasa3b088a22012-05-16 23:05:32 +090024#include "defines.h"
satoke808e432010-12-02 14:53:24 +090025#include "dictionary.h"
26#include "unigram_dictionary.h"
satok30088252010-12-01 21:22:15 +090027
Jean Chalard1059f272011-06-28 20:45:05 +090028#include "binary_format.h"
Jean Chalardcf9dbbd2011-12-26 15:16:59 +090029#include "terminal_attributes.h"
Jean Chalard1059f272011-06-28 20:45:05 +090030
satok30088252010-12-01 21:22:15 +090031namespace latinime {
32
Jean Chalardc2bbc6a2011-02-25 17:56:53 +090033const UnigramDictionary::digraph_t UnigramDictionary::GERMAN_UMLAUT_DIGRAPHS[] =
Jean Chalardd3043382012-03-21 18:38:25 +090034 { { 'a', 'e', 0x00E4 }, // U+00E4 : LATIN SMALL LETTER A WITH DIAERESIS
35 { 'o', 'e', 0x00F6 }, // U+00F6 : LATIN SMALL LETTER O WITH DIAERESIS
36 { 'u', 'e', 0x00FC } }; // U+00FC : LATIN SMALL LETTER U WITH DIAERESIS
Jean Chalardc2bbc6a2011-02-25 17:56:53 +090037
Jean Chalardcc78d032012-03-23 16:48:49 +090038const UnigramDictionary::digraph_t UnigramDictionary::FRENCH_LIGATURES_DIGRAPHS[] =
39 { { 'a', 'e', 0x00E6 }, // U+00E6 : LATIN SMALL LETTER AE
40 { 'o', 'e', 0x0153 } }; // U+0153 : LATIN SMALL LIGATURE OE
41
Jean Chalard293ece02011-06-16 20:55:16 +090042// TODO: check the header
43UnigramDictionary::UnigramDictionary(const uint8_t* const streamStart, int typedLetterMultiplier,
Jean Chalardcd274b12012-04-06 18:26:00 +090044 int fullWordMultiplier, int maxWordLength, int maxWords, const unsigned int flags)
Jean Chalard46a1eec2012-02-27 19:48:47 +090045 : DICT_ROOT(streamStart), MAX_WORD_LENGTH(maxWordLength), MAX_WORDS(maxWords),
satok662fe692010-12-08 17:05:39 +090046 TYPED_LETTER_MULTIPLIER(typedLetterMultiplier), FULL_WORD_MULTIPLIER(fullWordMultiplier),
Jean Chalard1059f272011-06-28 20:45:05 +090047 // TODO : remove this variable.
48 ROOT_POS(0),
satok9df4a452012-03-23 16:05:18 +090049 BYTES_IN_ONE_CHAR(sizeof(int)),
Jean Chalardcd274b12012-04-06 18:26:00 +090050 MAX_DIGRAPH_SEARCH_DEPTH(DEFAULT_MAX_DIGRAPH_SEARCH_DEPTH), FLAGS(flags) {
Ken Wakasade3070a2011-03-19 09:16:42 +090051 if (DEBUG_DICT) {
satok9fb6f472012-01-13 18:01:22 +090052 AKLOGI("UnigramDictionary - constructor");
Ken Wakasade3070a2011-03-19 09:16:42 +090053 }
satok30088252010-12-01 21:22:15 +090054}
55
satok2df30602011-07-15 13:49:00 +090056UnigramDictionary::~UnigramDictionary() {
satok2df30602011-07-15 13:49:00 +090057}
satok30088252010-12-01 21:22:15 +090058
satok9df4a452012-03-23 16:05:18 +090059static inline unsigned int getCodesBufferSize(const int *codes, const int codesSize) {
60 return sizeof(*codes) * codesSize;
Jean Chalardc2bbc6a2011-02-25 17:56:53 +090061}
62
Ken Wakasa951ab9d2012-03-09 19:18:59 +090063// TODO: This needs to take a const unsigned short* and not tinker with its contents
satok1147c7b2011-12-14 15:04:58 +090064static inline void addWord(
65 unsigned short *word, int length, int frequency, WordsPriorityQueue *queue) {
66 queue->push(frequency, word, length);
67}
68
Jean Chalardd3043382012-03-21 18:38:25 +090069// Return the replacement code point for a digraph, or 0 if none.
70int UnigramDictionary::getDigraphReplacement(const int *codes, const int i, const int codesSize,
Jean Chalard6c300612012-03-06 19:54:03 +090071 const digraph_t* const digraphs, const unsigned int digraphsSize) const {
Jean Chalardc2bbc6a2011-02-25 17:56:53 +090072
73 // There can't be a digraph if we don't have at least 2 characters to examine
74 if (i + 2 > codesSize) return false;
75
76 // Search for the first char of some digraph
77 int lastDigraphIndex = -1;
satok9df4a452012-03-23 16:05:18 +090078 const int thisChar = codes[i];
Jean Chalard6c300612012-03-06 19:54:03 +090079 for (lastDigraphIndex = digraphsSize - 1; lastDigraphIndex >= 0; --lastDigraphIndex) {
80 if (thisChar == digraphs[lastDigraphIndex].first) break;
Jean Chalardc2bbc6a2011-02-25 17:56:53 +090081 }
82 // No match: return early
Jean Chalardd3043382012-03-21 18:38:25 +090083 if (lastDigraphIndex < 0) return 0;
Jean Chalardc2bbc6a2011-02-25 17:56:53 +090084
85 // It's an interesting digraph if the second char matches too.
satok9df4a452012-03-23 16:05:18 +090086 if (digraphs[lastDigraphIndex].second == codes[i + 1]) {
Jean Chalardd3043382012-03-21 18:38:25 +090087 return digraphs[lastDigraphIndex].replacement;
88 } else {
89 return 0;
90 }
Jean Chalardc2bbc6a2011-02-25 17:56:53 +090091}
92
93// Mostly the same arguments as the non-recursive version, except:
94// codes is the original value. It points to the start of the work buffer, and gets passed as is.
95// codesSize is the size of the user input (thus, it is the size of codesSrc).
96// codesDest is the current point in the work buffer.
97// codesSrc is the current point in the user-input, original, content-unmodified buffer.
98// codesRemain is the remaining size in codesSrc.
satok1d7eaf82011-07-13 10:32:02 +090099void UnigramDictionary::getWordWithDigraphSuggestionsRec(ProximityInfo *proximityInfo,
satok1147c7b2011-12-14 15:04:58 +0900100 const int *xcoordinates, const int *ycoordinates, const int *codesBuffer,
satok219a5142012-03-08 11:53:18 +0900101 int *xCoordinatesBuffer, int *yCoordinatesBuffer,
Jean Chalard8950ce62012-05-07 16:28:30 +0900102 const int codesBufferSize, const std::map<int, int> *bigramMap, const uint8_t *bigramFilter,
Jean Chalard4d9b2022012-04-23 19:25:28 +0900103 const bool useFullEditDistance, const int *codesSrc,
satok1147c7b2011-12-14 15:04:58 +0900104 const int codesRemain, const int currentDepth, int *codesDest, Correction *correction,
Jean Chalard6c300612012-03-06 19:54:03 +0900105 WordsPriorityQueuePool *queuePool,
106 const digraph_t* const digraphs, const unsigned int digraphsSize) {
Jean Chalardc2bbc6a2011-02-25 17:56:53 +0900107
satok9df4a452012-03-23 16:05:18 +0900108 const int startIndex = codesDest - codesBuffer;
Jean Chalard6c300612012-03-06 19:54:03 +0900109 if (currentDepth < MAX_DIGRAPH_SEARCH_DEPTH) {
Jean Chalarda787dba2011-03-04 12:17:48 +0900110 for (int i = 0; i < codesRemain; ++i) {
satok219a5142012-03-08 11:53:18 +0900111 xCoordinatesBuffer[startIndex + i] = xcoordinates[codesBufferSize - codesRemain + i];
112 yCoordinatesBuffer[startIndex + i] = ycoordinates[codesBufferSize - codesRemain + i];
Jean Chalardd3043382012-03-21 18:38:25 +0900113 const int replacementCodePoint =
114 getDigraphReplacement(codesSrc, i, codesRemain, digraphs, digraphsSize);
115 if (0 != replacementCodePoint) {
Jean Chalarda787dba2011-03-04 12:17:48 +0900116 // Found a digraph. We will try both spellings. eg. the word is "pruefen"
Jean Chalardc2bbc6a2011-02-25 17:56:53 +0900117
Jean Chalardd3043382012-03-21 18:38:25 +0900118 // Copy the word up to the first char of the digraph, including proximity chars,
119 // and overwrite the primary code with the replacement code point. Then, continue
120 // processing on the remaining part of the word, skipping the second char of the
121 // digraph.
122 // In our example, copy "pru", replace "u" with the version with the diaeresis and
123 // continue running on "fen".
Jean Chalarda787dba2011-03-04 12:17:48 +0900124 // Make i the index of the second char of the digraph for simplicity. Forgetting
125 // to do that results in an infinite recursion so take care!
126 ++i;
127 memcpy(codesDest, codesSrc, i * BYTES_IN_ONE_CHAR);
Jean Chalardd3043382012-03-21 18:38:25 +0900128 codesDest[(i - 1) * (BYTES_IN_ONE_CHAR / sizeof(codesDest[0]))] =
129 replacementCodePoint;
Jean Chalarda787dba2011-03-04 12:17:48 +0900130 getWordWithDigraphSuggestionsRec(proximityInfo, xcoordinates, ycoordinates,
Jean Chalard338d3ec2012-04-06 19:28:34 +0900131 codesBuffer, xCoordinatesBuffer, yCoordinatesBuffer, codesBufferSize,
Jean Chalard8950ce62012-05-07 16:28:30 +0900132 bigramMap, bigramFilter, useFullEditDistance, codesSrc + i + 1,
Jean Chalard4d9b2022012-04-23 19:25:28 +0900133 codesRemain - i - 1, currentDepth + 1, codesDest + i, correction,
Jean Chalard6c300612012-03-06 19:54:03 +0900134 queuePool, digraphs, digraphsSize);
Jean Chalardc2bbc6a2011-02-25 17:56:53 +0900135
Jean Chalarda787dba2011-03-04 12:17:48 +0900136 // Copy the second char of the digraph in place, then continue processing on
137 // the remaining part of the word.
138 // In our example, after "pru" in the buffer copy the "e", and continue on "fen"
satok9df4a452012-03-23 16:05:18 +0900139 memcpy(codesDest + i, codesSrc + i, BYTES_IN_ONE_CHAR);
Jean Chalarda787dba2011-03-04 12:17:48 +0900140 getWordWithDigraphSuggestionsRec(proximityInfo, xcoordinates, ycoordinates,
Jean Chalard338d3ec2012-04-06 19:28:34 +0900141 codesBuffer, xCoordinatesBuffer, yCoordinatesBuffer, codesBufferSize,
Jean Chalard8950ce62012-05-07 16:28:30 +0900142 bigramMap, bigramFilter, useFullEditDistance, codesSrc + i, codesRemain - i,
Jean Chalard4d9b2022012-04-23 19:25:28 +0900143 currentDepth + 1, codesDest + i, correction, queuePool, digraphs,
144 digraphsSize);
Jean Chalarda787dba2011-03-04 12:17:48 +0900145 return;
146 }
Jean Chalardc2bbc6a2011-02-25 17:56:53 +0900147 }
148 }
149
150 // If we come here, we hit the end of the word: let's check it against the dictionary.
151 // In our example, we'll come here once for "prufen" and then once for "pruefen".
152 // If the word contains several digraphs, we'll come it for the product of them.
153 // eg. if the word is "ueberpruefen" we'll test, in order, against
154 // "uberprufen", "uberpruefen", "ueberprufen", "ueberpruefen".
155 const unsigned int remainingBytes = BYTES_IN_ONE_CHAR * codesRemain;
satok219a5142012-03-08 11:53:18 +0900156 if (0 != remainingBytes) {
Jean Chalardc2bbc6a2011-02-25 17:56:53 +0900157 memcpy(codesDest, codesSrc, remainingBytes);
satok219a5142012-03-08 11:53:18 +0900158 memcpy(&xCoordinatesBuffer[startIndex], &xcoordinates[codesBufferSize - codesRemain],
159 sizeof(int) * codesRemain);
160 memcpy(&yCoordinatesBuffer[startIndex], &ycoordinates[codesBufferSize - codesRemain],
161 sizeof(int) * codesRemain);
162 }
Jean Chalardc2bbc6a2011-02-25 17:56:53 +0900163
satok219a5142012-03-08 11:53:18 +0900164 getWordSuggestions(proximityInfo, xCoordinatesBuffer, yCoordinatesBuffer, codesBuffer,
Jean Chalard8950ce62012-05-07 16:28:30 +0900165 startIndex + codesRemain, bigramMap, bigramFilter, useFullEditDistance, correction,
satoka7e5a5a2011-12-15 16:49:12 +0900166 queuePool);
Jean Chalardc2bbc6a2011-02-25 17:56:53 +0900167}
168
Jean Chalard8950ce62012-05-07 16:28:30 +0900169// bigramMap contains the association <bigram address> -> <bigram frequency>
170// bigramFilter is a bloom filter for fast rejection: see functions setInFilter and isInFilter
171// in bigram_dictionary.cpp
satoka7e5a5a2011-12-15 16:49:12 +0900172int UnigramDictionary::getSuggestions(ProximityInfo *proximityInfo,
173 WordsPriorityQueuePool *queuePool, Correction *correction, const int *xcoordinates,
Jean Chalard338d3ec2012-04-06 19:28:34 +0900174 const int *ycoordinates, const int *codes, const int codesSize,
Jean Chalard8950ce62012-05-07 16:28:30 +0900175 const std::map<int, int> *bigramMap, const uint8_t *bigramFilter,
176 const bool useFullEditDistance, unsigned short *outWords, int *frequencies) {
Jean Chalardc2bbc6a2011-02-25 17:56:53 +0900177
satok219a5142012-03-08 11:53:18 +0900178 queuePool->clearAll();
satok1147c7b2011-12-14 15:04:58 +0900179 Correction* masterCorrection = correction;
Satoshi Kataoka6cbe2042012-05-30 17:28:34 +0900180 correction->resetCorrection();
Jean Chalardaa8df592012-04-06 18:54:20 +0900181 if (BinaryFormat::REQUIRES_GERMAN_UMLAUT_PROCESSING & FLAGS)
Jean Chalardc2bbc6a2011-02-25 17:56:53 +0900182 { // Incrementally tune the word and try all possibilities
satok9df4a452012-03-23 16:05:18 +0900183 int codesBuffer[getCodesBufferSize(codes, codesSize)];
satok219a5142012-03-08 11:53:18 +0900184 int xCoordinatesBuffer[codesSize];
185 int yCoordinatesBuffer[codesSize];
Jean Chalardc2bbc6a2011-02-25 17:56:53 +0900186 getWordWithDigraphSuggestionsRec(proximityInfo, xcoordinates, ycoordinates, codesBuffer,
Jean Chalard8950ce62012-05-07 16:28:30 +0900187 xCoordinatesBuffer, yCoordinatesBuffer, codesSize, bigramMap, bigramFilter,
Jean Chalard4d9b2022012-04-23 19:25:28 +0900188 useFullEditDistance, codes, codesSize, 0, codesBuffer, masterCorrection,
Jean Chalard338d3ec2012-04-06 19:28:34 +0900189 queuePool, GERMAN_UMLAUT_DIGRAPHS,
Jean Chalard6c300612012-03-06 19:54:03 +0900190 sizeof(GERMAN_UMLAUT_DIGRAPHS) / sizeof(GERMAN_UMLAUT_DIGRAPHS[0]));
Jean Chalardaa8df592012-04-06 18:54:20 +0900191 } else if (BinaryFormat::REQUIRES_FRENCH_LIGATURES_PROCESSING & FLAGS) {
satokacb6c542012-03-23 20:58:18 +0900192 int codesBuffer[getCodesBufferSize(codes, codesSize)];
Jean Chalardcc78d032012-03-23 16:48:49 +0900193 int xCoordinatesBuffer[codesSize];
194 int yCoordinatesBuffer[codesSize];
195 getWordWithDigraphSuggestionsRec(proximityInfo, xcoordinates, ycoordinates, codesBuffer,
Jean Chalard8950ce62012-05-07 16:28:30 +0900196 xCoordinatesBuffer, yCoordinatesBuffer, codesSize, bigramMap, bigramFilter,
Jean Chalard4d9b2022012-04-23 19:25:28 +0900197 useFullEditDistance, codes, codesSize, 0, codesBuffer, masterCorrection,
Jean Chalard338d3ec2012-04-06 19:28:34 +0900198 queuePool, FRENCH_LIGATURES_DIGRAPHS,
Jean Chalardcc78d032012-03-23 16:48:49 +0900199 sizeof(FRENCH_LIGATURES_DIGRAPHS) / sizeof(FRENCH_LIGATURES_DIGRAPHS[0]));
Jean Chalardc2bbc6a2011-02-25 17:56:53 +0900200 } else { // Normal processing
Jean Chalard338d3ec2012-04-06 19:28:34 +0900201 getWordSuggestions(proximityInfo, xcoordinates, ycoordinates, codes, codesSize,
Jean Chalard8950ce62012-05-07 16:28:30 +0900202 bigramMap, bigramFilter, useFullEditDistance, masterCorrection, queuePool);
Jean Chalardc2bbc6a2011-02-25 17:56:53 +0900203 }
204
satok817e5172011-03-04 06:06:45 -0800205 PROF_START(20);
satok8330b482012-01-23 16:52:37 +0900206 if (DEBUG_DICT) {
satok0028ed32012-05-16 20:42:12 +0900207 float ns = queuePool->getMasterQueue()->getHighestNormalizedScore(
satok8330b482012-01-23 16:52:37 +0900208 proximityInfo->getPrimaryInputWord(), codesSize, 0, 0, 0);
209 ns += 0;
210 AKLOGI("Max normalized score = %f", ns);
211 }
satoka7e5a5a2011-12-15 16:49:12 +0900212 const int suggestedWordsCount =
satokdb1939d2012-05-15 17:43:31 +0900213 queuePool->getMasterQueue()->outputSuggestions(
214 proximityInfo->getPrimaryInputWord(), codesSize, frequencies, outWords);
Jean Chalardc2bbc6a2011-02-25 17:56:53 +0900215
216 if (DEBUG_DICT) {
satok0028ed32012-05-16 20:42:12 +0900217 float ns = queuePool->getMasterQueue()->getHighestNormalizedScore(
satok8330b482012-01-23 16:52:37 +0900218 proximityInfo->getPrimaryInputWord(), codesSize, 0, 0, 0);
219 ns += 0;
satok9fb6f472012-01-13 18:01:22 +0900220 AKLOGI("Returning %d words", suggestedWordsCount);
Jean Chalard980d6b62011-06-30 17:02:23 +0900221 /// Print the returned words
222 for (int j = 0; j < suggestedWordsCount; ++j) {
satok16379df2011-12-12 20:53:22 +0900223 short unsigned int* w = outWords + j * MAX_WORD_LENGTH;
Jean Chalard980d6b62011-06-30 17:02:23 +0900224 char s[MAX_WORD_LENGTH];
225 for (int i = 0; i <= MAX_WORD_LENGTH; i++) s[i] = w[i];
satok9fb6f472012-01-13 18:01:22 +0900226 AKLOGI("%s %i", s, frequencies[j]);
Jean Chalard980d6b62011-06-30 17:02:23 +0900227 }
Jean Chalardc2bbc6a2011-02-25 17:56:53 +0900228 }
satok817e5172011-03-04 06:06:45 -0800229 PROF_END(20);
Jean Chalardc2bbc6a2011-02-25 17:56:53 +0900230 PROF_CLOSE;
231 return suggestedWordsCount;
232}
233
satok1d7eaf82011-07-13 10:32:02 +0900234void UnigramDictionary::getWordSuggestions(ProximityInfo *proximityInfo,
satok1147c7b2011-12-14 15:04:58 +0900235 const int *xcoordinates, const int *ycoordinates, const int *codes,
Jean Chalard8950ce62012-05-07 16:28:30 +0900236 const int inputLength, const std::map<int, int> *bigramMap, const uint8_t *bigramFilter,
237 const bool useFullEditDistance, Correction *correction, WordsPriorityQueuePool *queuePool) {
Jean Chalardc2bbc6a2011-02-25 17:56:53 +0900238
satok61e2f852011-01-05 14:13:07 +0900239 PROF_OPEN;
240 PROF_START(0);
satok61e2f852011-01-05 14:13:07 +0900241 PROF_END(0);
satok30088252010-12-01 21:22:15 +0900242
satok61e2f852011-01-05 14:13:07 +0900243 PROF_START(1);
Jean Chalard8950ce62012-05-07 16:28:30 +0900244 getOneWordSuggestions(proximityInfo, xcoordinates, ycoordinates, codes, bigramMap, bigramFilter,
Jean Chalard4d9b2022012-04-23 19:25:28 +0900245 useFullEditDistance, inputLength, correction, queuePool);
satok61e2f852011-01-05 14:13:07 +0900246 PROF_END(1);
247
248 PROF_START(2);
satok10266c02011-08-19 22:05:59 +0900249 // Note: This line is intentionally left blank
satok61e2f852011-01-05 14:13:07 +0900250 PROF_END(2);
satokcdbbea72010-12-08 16:04:16 +0900251
satok61e2f852011-01-05 14:13:07 +0900252 PROF_START(3);
satok10266c02011-08-19 22:05:59 +0900253 // Note: This line is intentionally left blank
satok61e2f852011-01-05 14:13:07 +0900254 PROF_END(3);
satok30088252010-12-01 21:22:15 +0900255
satok61e2f852011-01-05 14:13:07 +0900256 PROF_START(4);
satok8330b482012-01-23 16:52:37 +0900257 bool hasAutoCorrectionCandidate = false;
258 WordsPriorityQueue* masterQueue = queuePool->getMasterQueue();
259 if (masterQueue->size() > 0) {
satok0028ed32012-05-16 20:42:12 +0900260 float nsForMaster = masterQueue->getHighestNormalizedScore(
satok8330b482012-01-23 16:52:37 +0900261 proximityInfo->getPrimaryInputWord(), inputLength, 0, 0, 0);
262 hasAutoCorrectionCandidate = (nsForMaster > START_TWO_WORDS_CORRECTION_THRESHOLD);
263 }
satok61e2f852011-01-05 14:13:07 +0900264 PROF_END(4);
satoka3d78f62010-12-09 22:08:33 +0900265
satok61e2f852011-01-05 14:13:07 +0900266 PROF_START(5);
satok99557162012-01-26 22:49:13 +0900267 // Multiple word suggestions
268 if (SUGGEST_MULTIPLE_WORDS
269 && inputLength >= MIN_USER_TYPED_LENGTH_FOR_MULTIPLE_WORD_SUGGESTION) {
satoka85f4922012-01-30 18:18:30 +0900270 getSplitMultipleWordsSuggestions(proximityInfo, xcoordinates, ycoordinates, codes,
satok1f6b52e2012-01-30 13:53:58 +0900271 useFullEditDistance, inputLength, correction, queuePool,
272 hasAutoCorrectionCandidate);
satok662fe692010-12-08 17:05:39 +0900273 }
satok61e2f852011-01-05 14:13:07 +0900274 PROF_END(5);
satok817e5172011-03-04 06:06:45 -0800275
276 PROF_START(6);
satok99557162012-01-26 22:49:13 +0900277 // Note: This line is intentionally left blank
satok817e5172011-03-04 06:06:45 -0800278 PROF_END(6);
satok99557162012-01-26 22:49:13 +0900279
satok29dc8062012-01-17 15:59:15 +0900280 if (DEBUG_DICT) {
satok6ad15fc2012-01-16 16:21:21 +0900281 queuePool->dumpSubQueue1TopSuggestions();
satok29dc8062012-01-17 15:59:15 +0900282 for (int i = 0; i < SUB_QUEUE_MAX_COUNT; ++i) {
satok7409d152012-01-26 16:13:25 +0900283 WordsPriorityQueue* queue = queuePool->getSubQueue(FIRST_WORD_INDEX, i);
satok29dc8062012-01-17 15:59:15 +0900284 if (queue->size() > 0) {
285 WordsPriorityQueue::SuggestedWord* sw = queue->top();
286 const int score = sw->mScore;
287 const unsigned short* word = sw->mWord;
288 const int wordLength = sw->mWordLength;
satok0028ed32012-05-16 20:42:12 +0900289 float ns = Correction::RankingAlgorithm::calcNormalizedScore(
satok29dc8062012-01-17 15:59:15 +0900290 proximityInfo->getPrimaryInputWord(), i, word, wordLength, score);
291 ns += 0;
292 AKLOGI("--- TOP SUB WORDS for %d --- %d %f [%d]", i, score, ns,
satok54af64a2012-01-17 15:58:23 +0900293 (ns > TWO_WORDS_CORRECTION_WITH_OTHER_ERROR_THRESHOLD));
satok29dc8062012-01-17 15:59:15 +0900294 DUMP_WORD(proximityInfo->getPrimaryInputWord(), i);
295 DUMP_WORD(word, wordLength);
296 }
297 }
satok6ad15fc2012-01-16 16:21:21 +0900298 }
satok30088252010-12-01 21:22:15 +0900299}
300
Yusuke Nojima258bfe62011-09-28 12:59:43 +0900301void UnigramDictionary::initSuggestions(ProximityInfo *proximityInfo, const int *xCoordinates,
satok6ad15fc2012-01-16 16:21:21 +0900302 const int *yCoordinates, const int *codes, const int inputLength, Correction *correction) {
Ken Wakasade3070a2011-03-19 09:16:42 +0900303 if (DEBUG_DICT) {
satok9fb6f472012-01-13 18:01:22 +0900304 AKLOGI("initSuggest");
Satoshi Kataoka6cbe2042012-05-30 17:28:34 +0900305 DUMP_WORD_INT(codes, inputLength);
Ken Wakasade3070a2011-03-19 09:16:42 +0900306 }
satok1a6da632011-12-16 23:15:06 +0900307 proximityInfo->setInputParams(codes, inputLength, xCoordinates, yCoordinates);
satok1a6da632011-12-16 23:15:06 +0900308 const int maxDepth = min(inputLength * MAX_DEPTH_MULTIPLIER, MAX_WORD_LENGTH);
309 correction->initCorrection(proximityInfo, inputLength, maxDepth);
satok30088252010-12-01 21:22:15 +0900310}
311
satok715514d2010-12-02 20:19:59 +0900312static const char QUOTE = '\'';
satok662fe692010-12-08 17:05:39 +0900313static const char SPACE = ' ';
satok30088252010-12-01 21:22:15 +0900314
satok744dab62011-12-15 22:29:05 +0900315void UnigramDictionary::getOneWordSuggestions(ProximityInfo *proximityInfo,
316 const int *xcoordinates, const int *ycoordinates, const int *codes,
Jean Chalard8950ce62012-05-07 16:28:30 +0900317 const std::map<int, int> *bigramMap, const uint8_t *bigramFilter,
318 const bool useFullEditDistance, const int inputLength,
Jean Chalard4d9b2022012-04-23 19:25:28 +0900319 Correction *correction, WordsPriorityQueuePool *queuePool) {
satok6ad15fc2012-01-16 16:21:21 +0900320 initSuggestions(proximityInfo, xcoordinates, ycoordinates, codes, inputLength, correction);
Jean Chalard8950ce62012-05-07 16:28:30 +0900321 getSuggestionCandidates(useFullEditDistance, inputLength, bigramMap, bigramFilter, correction,
Jean Chalard4d9b2022012-04-23 19:25:28 +0900322 queuePool, true /* doAutoCompletion */, DEFAULT_MAX_ERRORS, FIRST_WORD_INDEX);
satok744dab62011-12-15 22:29:05 +0900323}
324
satok1147c7b2011-12-14 15:04:58 +0900325void UnigramDictionary::getSuggestionCandidates(const bool useFullEditDistance,
Jean Chalard8950ce62012-05-07 16:28:30 +0900326 const int inputLength, const std::map<int, int> *bigramMap, const uint8_t *bigramFilter,
Jean Chalard4d9b2022012-04-23 19:25:28 +0900327 Correction *correction, WordsPriorityQueuePool *queuePool,
satok8330b482012-01-23 16:52:37 +0900328 const bool doAutoCompletion, const int maxErrors, const int currentWordIndex) {
Satoshi Kataoka6cbe2042012-05-30 17:28:34 +0900329 uint8_t totalTraverseCount = correction->pushAndGetTotalTraverseCount();
330 if (DEBUG_DICT) {
331 AKLOGI("Traverse count %d", totalTraverseCount);
332 }
333 if (totalTraverseCount > MULTIPLE_WORDS_SUGGESTION_MAX_TOTAL_TRAVERSE_COUNT) {
334 if (DEBUG_DICT) {
335 AKLOGI("Abort traversing %d", totalTraverseCount);
336 }
337 return;
338 }
satok10266c02011-08-19 22:05:59 +0900339 // TODO: Remove setCorrectionParams
satok1147c7b2011-12-14 15:04:58 +0900340 correction->setCorrectionParams(0, 0, 0,
satokd03317c2011-12-14 21:38:11 +0900341 -1 /* spaceProximityPos */, -1 /* missingSpacePos */, useFullEditDistance,
satok1a6da632011-12-16 23:15:06 +0900342 doAutoCompletion, maxErrors);
satok662fe692010-12-08 17:05:39 +0900343 int rootPosition = ROOT_POS;
Jean Chalard980d6b62011-06-30 17:02:23 +0900344 // Get the number of children of root, then increment the position
Jean Chalard6d419812012-01-16 15:19:47 +0900345 int childCount = BinaryFormat::getGroupCountAndForwardPointer(DICT_ROOT, &rootPosition);
satok208268d2011-08-10 15:44:08 +0900346 int outputIndex = 0;
satokd2997922010-12-07 13:08:39 +0900347
satok1147c7b2011-12-14 15:04:58 +0900348 correction->initCorrectionState(rootPosition, childCount, (inputLength <= 0));
satokd2997922010-12-07 13:08:39 +0900349
satok662fe692010-12-08 17:05:39 +0900350 // Depth first search
satok208268d2011-08-10 15:44:08 +0900351 while (outputIndex >= 0) {
satok1147c7b2011-12-14 15:04:58 +0900352 if (correction->initProcessState(outputIndex)) {
353 int siblingPos = correction->getTreeSiblingPos(outputIndex);
satokd2997922010-12-07 13:08:39 +0900354 int firstChildPos;
satok0f6c8e82011-08-03 02:19:44 +0900355
satok4e4e74e2011-08-03 23:27:32 +0900356 const bool needsToTraverseChildrenNodes = processCurrentNode(siblingPos,
Jean Chalard8950ce62012-05-07 16:28:30 +0900357 bigramMap, bigramFilter, correction, &childCount, &firstChildPos, &siblingPos,
Jean Chalard4d9b2022012-04-23 19:25:28 +0900358 queuePool, currentWordIndex);
satok662fe692010-12-08 17:05:39 +0900359 // Update next sibling pos
satok1147c7b2011-12-14 15:04:58 +0900360 correction->setTreeSiblingPos(outputIndex, siblingPos);
satok208268d2011-08-10 15:44:08 +0900361
satokd2997922010-12-07 13:08:39 +0900362 if (needsToTraverseChildrenNodes) {
363 // Goes to child node
satok1147c7b2011-12-14 15:04:58 +0900364 outputIndex = correction->goDownTree(outputIndex, childCount, firstChildPos);
satokd2997922010-12-07 13:08:39 +0900365 }
366 } else {
satokcdbbea72010-12-08 16:04:16 +0900367 // Goes to parent sibling node
satok1147c7b2011-12-14 15:04:58 +0900368 outputIndex = correction->getTreeParentIndex(outputIndex);
satokd2997922010-12-07 13:08:39 +0900369 }
370 }
371}
372
Jean Chalard171d1802012-04-23 18:51:00 +0900373inline void UnigramDictionary::onTerminal(const int probability,
Jean Chalardcf9dbbd2011-12-26 15:16:59 +0900374 const TerminalAttributes& terminalAttributes, Correction *correction,
satok8330b482012-01-23 16:52:37 +0900375 WordsPriorityQueuePool *queuePool, const bool addToMasterQueue,
376 const int currentWordIndex) {
satok6ad15fc2012-01-16 16:21:21 +0900377 const int inputIndex = correction->getInputIndex();
378 const bool addToSubQueue = inputIndex < SUB_QUEUE_MAX_COUNT;
satok54af64a2012-01-17 15:58:23 +0900379
satok8876b752011-08-04 18:31:57 +0900380 int wordLength;
381 unsigned short* wordPointer;
satok54af64a2012-01-17 15:58:23 +0900382
satok1f6b52e2012-01-30 13:53:58 +0900383 if ((currentWordIndex == FIRST_WORD_INDEX) && addToMasterQueue) {
satok54af64a2012-01-17 15:58:23 +0900384 WordsPriorityQueue *masterQueue = queuePool->getMasterQueue();
Jean Chalard171d1802012-04-23 18:51:00 +0900385 const int finalProbability =
386 correction->getFinalProbability(probability, &wordPointer, &wordLength);
387 if (finalProbability != NOT_A_PROBABILITY) {
388 addWord(wordPointer, wordLength, finalProbability, masterQueue);
satok54af64a2012-01-17 15:58:23 +0900389
Jean Chalard171d1802012-04-23 18:51:00 +0900390 const int shortcutProbability = finalProbability > 0 ? finalProbability - 1 : 0;
satok54af64a2012-01-17 15:58:23 +0900391 // Please note that the shortcut candidates will be added to the master queue only.
392 TerminalAttributes::ShortcutIterator iterator =
393 terminalAttributes.getShortcutIterator();
394 while (iterator.hasNextShortcutTarget()) {
395 // TODO: addWord only supports weak ordering, meaning we have no means
396 // to control the order of the shortcuts relative to one another or to the word.
Jean Chalard171d1802012-04-23 18:51:00 +0900397 // We need to either modulate the probability of each shortcut according
398 // to its own shortcut probability or to make the queue
satok54af64a2012-01-17 15:58:23 +0900399 // so that the insert order is protected inside the queue for words
Jean Chalard9a933a72012-03-27 19:56:23 +0900400 // with the same score. For the moment we use -1 to make sure the shortcut will
401 // never be in front of the word.
satok54af64a2012-01-17 15:58:23 +0900402 uint16_t shortcutTarget[MAX_WORD_LENGTH_INTERNAL];
403 const int shortcutTargetStringLength = iterator.getNextShortcutTarget(
404 MAX_WORD_LENGTH_INTERNAL, shortcutTarget);
Jean Chalard171d1802012-04-23 18:51:00 +0900405 addWord(shortcutTarget, shortcutTargetStringLength, shortcutProbability,
406 masterQueue);
satok6ad15fc2012-01-16 16:21:21 +0900407 }
Jean Chalardcf9dbbd2011-12-26 15:16:59 +0900408 }
satok54af64a2012-01-17 15:58:23 +0900409 }
satok6ad15fc2012-01-16 16:21:21 +0900410
satok54af64a2012-01-17 15:58:23 +0900411 // We only allow two words + other error correction for words with SUB_QUEUE_MIN_WORD_LENGTH
412 // or more length.
413 if (inputIndex >= SUB_QUEUE_MIN_WORD_LENGTH && addToSubQueue) {
satok8330b482012-01-23 16:52:37 +0900414 WordsPriorityQueue *subQueue;
satok7409d152012-01-26 16:13:25 +0900415 subQueue = queuePool->getSubQueue(currentWordIndex, inputIndex);
416 if (!subQueue) {
satok8330b482012-01-23 16:52:37 +0900417 return;
418 }
Jean Chalard171d1802012-04-23 18:51:00 +0900419 const int finalProbability = correction->getFinalProbabilityForSubQueue(
420 probability, &wordPointer, &wordLength, inputIndex);
421 addWord(wordPointer, wordLength, finalProbability, subQueue);
Jean Chalardca5ef282011-06-17 15:36:26 +0900422 }
423}
424
Satoshi Kataoka6cbe2042012-05-30 17:28:34 +0900425int UnigramDictionary::getSubStringSuggestion(
satok7409d152012-01-26 16:13:25 +0900426 ProximityInfo *proximityInfo, const int *xcoordinates, const int *ycoordinates,
satok3c09bb12012-01-26 18:36:19 +0900427 const int *codes, const bool useFullEditDistance, Correction *correction,
428 WordsPriorityQueuePool* queuePool, const int inputLength,
429 const bool hasAutoCorrectionCandidate, const int currentWordIndex,
430 const int inputWordStartPos, const int inputWordLength,
satok99557162012-01-26 22:49:13 +0900431 const int outputWordStartPos, const bool isSpaceProximity, int *freqArray,
432 int*wordLengthArray, unsigned short* outputWord, int *outputWordLength) {
Satoshi Kataoka67e3cc82012-05-31 15:04:58 +0900433 if (inputWordLength > MULTIPLE_WORDS_SUGGESTION_MAX_WORD_LENGTH) {
434 return FLAG_MULTIPLE_SUGGEST_ABORT;
435 }
436
437 /////////////////////////////////////////////
438 // safety net for multiple word suggestion //
439 // TODO: Remove this safety net //
440 /////////////////////////////////////////////
441 int smallWordCount = 0;
442 int singleLetterWordCount = 0;
443 if (inputWordLength == 1) {
444 ++singleLetterWordCount;
445 }
446 if (inputWordLength <= 2) {
447 // small word == single letter or 2-letter word
448 ++smallWordCount;
449 }
450 for (int i = 0; i < currentWordIndex; ++i) {
451 const int length = wordLengthArray[i];
452 if (length == 1) {
453 ++singleLetterWordCount;
454 // Safety net to avoid suggesting sequential single letter words
455 if (i < (currentWordIndex - 1)) {
456 if (wordLengthArray[i + 1] == 1) {
457 return FLAG_MULTIPLE_SUGGEST_ABORT;
458 }
459 } else if (inputWordLength == 1) {
460 return FLAG_MULTIPLE_SUGGEST_ABORT;
461 }
462 }
463 if (length <= 2) {
464 ++smallWordCount;
465 }
466 // Safety net to avoid suggesting multiple words with many (4 or more, for now) small words
467 if (singleLetterWordCount >= 3 || smallWordCount >= 4) {
468 return FLAG_MULTIPLE_SUGGEST_ABORT;
469 }
470 }
471 //////////////////////////////////////////////
472 // TODO: Remove the safety net above //
473 //////////////////////////////////////////////
474
satok3c09bb12012-01-26 18:36:19 +0900475 unsigned short* tempOutputWord = 0;
satok1f6b52e2012-01-30 13:53:58 +0900476 int nextWordLength = 0;
satok99557162012-01-26 22:49:13 +0900477 // TODO: Optimize init suggestion
478 initSuggestions(proximityInfo, xcoordinates, ycoordinates, codes,
479 inputLength, correction);
480
satok3c09bb12012-01-26 18:36:19 +0900481 int freq = getMostFrequentWordLike(
482 inputWordStartPos, inputWordLength, proximityInfo, mWord);
483 if (freq > 0) {
satok1f6b52e2012-01-30 13:53:58 +0900484 nextWordLength = inputWordLength;
satok3c09bb12012-01-26 18:36:19 +0900485 tempOutputWord = mWord;
486 } else if (!hasAutoCorrectionCandidate) {
487 if (inputWordStartPos > 0) {
488 const int offset = inputWordStartPos;
489 initSuggestions(proximityInfo, &xcoordinates[offset], &ycoordinates[offset],
satok9df4a452012-03-23 16:05:18 +0900490 codes + offset, inputWordLength, correction);
satok3c09bb12012-01-26 18:36:19 +0900491 queuePool->clearSubQueue(currentWordIndex);
Jean Chalard4d9b2022012-04-23 19:25:28 +0900492 // TODO: pass the bigram list for substring suggestion
493 getSuggestionCandidates(useFullEditDistance, inputWordLength,
Jean Chalard8950ce62012-05-07 16:28:30 +0900494 0 /* bigramMap */, 0 /* bigramFilter */, correction, queuePool,
495 false /* doAutoCompletion */, MAX_ERRORS_FOR_TWO_WORDS, currentWordIndex);
satok3c09bb12012-01-26 18:36:19 +0900496 if (DEBUG_DICT) {
satok1f6b52e2012-01-30 13:53:58 +0900497 if (currentWordIndex < MULTIPLE_WORDS_SUGGESTION_MAX_WORDS) {
satok3c09bb12012-01-26 18:36:19 +0900498 AKLOGI("Dump word candidates(%d) %d", currentWordIndex, inputWordLength);
499 for (int i = 0; i < SUB_QUEUE_MAX_COUNT; ++i) {
500 queuePool->getSubQueue(currentWordIndex, i)->dumpTopWord();
501 }
502 }
503 }
504 }
505 WordsPriorityQueue* queue = queuePool->getSubQueue(currentWordIndex, inputWordLength);
Satoshi Kataoka6cbe2042012-05-30 17:28:34 +0900506 // TODO: Return the correct value depending on doAutoCompletion
507 if (!queue || queue->size() <= 0) {
508 return FLAG_MULTIPLE_SUGGEST_ABORT;
satok3c09bb12012-01-26 18:36:19 +0900509 }
510 int score = 0;
satok0028ed32012-05-16 20:42:12 +0900511 const float ns = queue->getHighestNormalizedScore(
satok3c09bb12012-01-26 18:36:19 +0900512 proximityInfo->getPrimaryInputWord(), inputWordLength,
satok1f6b52e2012-01-30 13:53:58 +0900513 &tempOutputWord, &score, &nextWordLength);
satok3c09bb12012-01-26 18:36:19 +0900514 if (DEBUG_DICT) {
515 AKLOGI("NS(%d) = %f, Score = %d", currentWordIndex, ns, score);
516 }
517 // Two words correction won't be done if the score of the first word doesn't exceed the
518 // threshold.
519 if (ns < TWO_WORDS_CORRECTION_WITH_OTHER_ERROR_THRESHOLD
satok1f6b52e2012-01-30 13:53:58 +0900520 || nextWordLength < SUB_QUEUE_MIN_WORD_LENGTH) {
Satoshi Kataoka6cbe2042012-05-30 17:28:34 +0900521 return FLAG_MULTIPLE_SUGGEST_SKIP;
satok3c09bb12012-01-26 18:36:19 +0900522 }
satok1f6b52e2012-01-30 13:53:58 +0900523 freq = score >> (nextWordLength + TWO_WORDS_PLUS_OTHER_ERROR_CORRECTION_DEMOTION_DIVIDER);
satok3c09bb12012-01-26 18:36:19 +0900524 }
525 if (DEBUG_DICT) {
satok1f6b52e2012-01-30 13:53:58 +0900526 AKLOGI("Freq(%d): %d, length: %d, input length: %d, input start: %d (%d)"
527 , currentWordIndex, freq, nextWordLength, inputWordLength, inputWordStartPos,
528 wordLengthArray[0]);
satok3c09bb12012-01-26 18:36:19 +0900529 }
satok1f6b52e2012-01-30 13:53:58 +0900530 if (freq <= 0 || nextWordLength <= 0
531 || MAX_WORD_LENGTH <= (outputWordStartPos + nextWordLength)) {
Satoshi Kataoka6cbe2042012-05-30 17:28:34 +0900532 return FLAG_MULTIPLE_SUGGEST_SKIP;
satok3c09bb12012-01-26 18:36:19 +0900533 }
satok1f6b52e2012-01-30 13:53:58 +0900534 for (int i = 0; i < nextWordLength; ++i) {
satok3c09bb12012-01-26 18:36:19 +0900535 outputWord[outputWordStartPos + i] = tempOutputWord[i];
536 }
satok99557162012-01-26 22:49:13 +0900537
538 // Put output values
satok1f6b52e2012-01-30 13:53:58 +0900539 freqArray[currentWordIndex] = freq;
satok99557162012-01-26 22:49:13 +0900540 // TODO: put output length instead of input length
satok1f6b52e2012-01-30 13:53:58 +0900541 wordLengthArray[currentWordIndex] = inputWordLength;
542 const int tempOutputWordLength = outputWordStartPos + nextWordLength;
543 if (outputWordLength) {
544 *outputWordLength = tempOutputWordLength;
545 }
satok99557162012-01-26 22:49:13 +0900546
satok3c09bb12012-01-26 18:36:19 +0900547 if ((inputWordStartPos + inputWordLength) < inputLength) {
satok1f6b52e2012-01-30 13:53:58 +0900548 if (outputWordStartPos + nextWordLength >= MAX_WORD_LENGTH) {
Satoshi Kataoka6cbe2042012-05-30 17:28:34 +0900549 return FLAG_MULTIPLE_SUGGEST_SKIP;
satok3c09bb12012-01-26 18:36:19 +0900550 }
satoka85f4922012-01-30 18:18:30 +0900551 outputWord[tempOutputWordLength] = SPACE;
satok1f6b52e2012-01-30 13:53:58 +0900552 if (outputWordLength) {
553 ++*outputWordLength;
554 }
555 } else if (currentWordIndex >= 1) {
satok99557162012-01-26 22:49:13 +0900556 // TODO: Handle 3 or more words
satoka85f4922012-01-30 18:18:30 +0900557 const int pairFreq = correction->getFreqForSplitMultipleWords(
558 freqArray, wordLengthArray, currentWordIndex + 1, isSpaceProximity, outputWord);
satok99557162012-01-26 22:49:13 +0900559 if (DEBUG_DICT) {
satoka85f4922012-01-30 18:18:30 +0900560 DUMP_WORD(outputWord, tempOutputWordLength);
satoka0ac31f2012-05-23 19:55:27 +0900561 for (int i = 0; i < currentWordIndex + 1; ++i) {
562 AKLOGI("Split %d,%d words: freq = %d, length = %d", i, currentWordIndex + 1,
563 freqArray[i], wordLengthArray[i]);
564 }
565 AKLOGI("Split two words: freq = %d, length = %d, %d, isSpace ? %d", pairFreq,
566 inputLength, tempOutputWordLength, isSpaceProximity);
satok99557162012-01-26 22:49:13 +0900567 }
satok1f6b52e2012-01-30 13:53:58 +0900568 addWord(outputWord, tempOutputWordLength, pairFreq, queuePool->getMasterQueue());
satok3c09bb12012-01-26 18:36:19 +0900569 }
Satoshi Kataoka6cbe2042012-05-30 17:28:34 +0900570 return FLAG_MULTIPLE_SUGGEST_CONTINUE;
satok7409d152012-01-26 16:13:25 +0900571}
572
satok1f6b52e2012-01-30 13:53:58 +0900573void UnigramDictionary::getMultiWordsSuggestionRec(ProximityInfo *proximityInfo,
574 const int *xcoordinates, const int *ycoordinates, const int *codes,
575 const bool useFullEditDistance, const int inputLength,
576 Correction *correction, WordsPriorityQueuePool* queuePool,
577 const bool hasAutoCorrectionCandidate, const int startInputPos, const int startWordIndex,
578 const int outputWordLength, int *freqArray, int* wordLengthArray,
579 unsigned short* outputWord) {
580 if (startWordIndex >= (MULTIPLE_WORDS_SUGGESTION_MAX_WORDS - 1)) {
581 // Return if the last word index
582 return;
583 }
satoka85f4922012-01-30 18:18:30 +0900584 if (startWordIndex >= 1
585 && (hasAutoCorrectionCandidate
586 || inputLength < MIN_INPUT_LENGTH_FOR_THREE_OR_MORE_WORDS_CORRECTION)) {
587 // Do not suggest 3+ words if already has auto correction candidate
588 return;
589 }
590 for (int i = startInputPos + 1; i < inputLength; ++i) {
satok1f6b52e2012-01-30 13:53:58 +0900591 if (DEBUG_CORRECTION_FREQ) {
satoka85f4922012-01-30 18:18:30 +0900592 AKLOGI("Multi words(%d), start in %d sep %d start out %d",
593 startWordIndex, startInputPos, i, outputWordLength);
594 DUMP_WORD(outputWord, outputWordLength);
satok1f6b52e2012-01-30 13:53:58 +0900595 }
satoka85f4922012-01-30 18:18:30 +0900596 int tempOutputWordLength = 0;
597 // Current word
598 int inputWordStartPos = startInputPos;
599 int inputWordLength = i - startInputPos;
Satoshi Kataoka6cbe2042012-05-30 17:28:34 +0900600 const int suggestionFlag = getSubStringSuggestion(proximityInfo, xcoordinates, ycoordinates,
601 codes, useFullEditDistance, correction, queuePool, inputLength,
602 hasAutoCorrectionCandidate, startWordIndex, inputWordStartPos, inputWordLength,
603 outputWordLength, true /* not used */, freqArray, wordLengthArray, outputWord,
604 &tempOutputWordLength);
605 if (suggestionFlag == FLAG_MULTIPLE_SUGGEST_ABORT) {
606 // TODO: break here
607 continue;
608 } else if (suggestionFlag == FLAG_MULTIPLE_SUGGEST_SKIP) {
satok1f6b52e2012-01-30 13:53:58 +0900609 continue;
610 }
611
satoka85f4922012-01-30 18:18:30 +0900612 if (DEBUG_CORRECTION_FREQ) {
613 AKLOGI("Do missing space correction");
614 }
615 // Next word
satok1f6b52e2012-01-30 13:53:58 +0900616 // Missing space
617 inputWordStartPos = i;
618 inputWordLength = inputLength - i;
Satoshi Kataoka6cbe2042012-05-30 17:28:34 +0900619 if(getSubStringSuggestion(proximityInfo, xcoordinates, ycoordinates, codes,
satok1f6b52e2012-01-30 13:53:58 +0900620 useFullEditDistance, correction, queuePool, inputLength, hasAutoCorrectionCandidate,
satoka85f4922012-01-30 18:18:30 +0900621 startWordIndex + 1, inputWordStartPos, inputWordLength, tempOutputWordLength,
Satoshi Kataoka6cbe2042012-05-30 17:28:34 +0900622 false /* missing space */, freqArray, wordLengthArray, outputWord, 0)
623 != FLAG_MULTIPLE_SUGGEST_CONTINUE) {
satoka85f4922012-01-30 18:18:30 +0900624 getMultiWordsSuggestionRec(proximityInfo, xcoordinates, ycoordinates, codes,
625 useFullEditDistance, inputLength, correction, queuePool,
626 hasAutoCorrectionCandidate, inputWordStartPos, startWordIndex + 1,
627 tempOutputWordLength, freqArray, wordLengthArray, outputWord);
628 }
satok1f6b52e2012-01-30 13:53:58 +0900629
630 // Mistyped space
631 ++inputWordStartPos;
632 --inputWordLength;
633
634 if (inputWordLength <= 0) {
635 continue;
636 }
637
638 const int x = xcoordinates[inputWordStartPos - 1];
639 const int y = ycoordinates[inputWordStartPos - 1];
640 if (!proximityInfo->hasSpaceProximity(x, y)) {
641 continue;
642 }
643
satoka85f4922012-01-30 18:18:30 +0900644 if (DEBUG_CORRECTION_FREQ) {
645 AKLOGI("Do mistyped space correction");
646 }
satok1f6b52e2012-01-30 13:53:58 +0900647 getSubStringSuggestion(proximityInfo, xcoordinates, ycoordinates, codes,
648 useFullEditDistance, correction, queuePool, inputLength, hasAutoCorrectionCandidate,
satoka85f4922012-01-30 18:18:30 +0900649 startWordIndex + 1, inputWordStartPos, inputWordLength, tempOutputWordLength,
650 true /* mistyped space */, freqArray, wordLengthArray, outputWord, 0);
satok1f6b52e2012-01-30 13:53:58 +0900651 }
652}
653
satoka85f4922012-01-30 18:18:30 +0900654void UnigramDictionary::getSplitMultipleWordsSuggestions(ProximityInfo *proximityInfo,
satok744dab62011-12-15 22:29:05 +0900655 const int *xcoordinates, const int *ycoordinates, const int *codes,
satok1f6b52e2012-01-30 13:53:58 +0900656 const bool useFullEditDistance, const int inputLength,
satok99557162012-01-26 22:49:13 +0900657 Correction *correction, WordsPriorityQueuePool* queuePool,
satok8330b482012-01-23 16:52:37 +0900658 const bool hasAutoCorrectionCandidate) {
satokbd6ccdd2012-01-23 12:30:20 +0900659 if (inputLength >= MAX_WORD_LENGTH) return;
satok612c6e42011-08-01 19:35:27 +0900660 if (DEBUG_DICT) {
satok1f6b52e2012-01-30 13:53:58 +0900661 AKLOGI("--- Suggest multiple words");
662 }
satok54af64a2012-01-17 15:58:23 +0900663
satokbd6ccdd2012-01-23 12:30:20 +0900664 // Allocating fixed length array on stack
665 unsigned short outputWord[MAX_WORD_LENGTH];
satok1f6b52e2012-01-30 13:53:58 +0900666 int freqArray[MULTIPLE_WORDS_SUGGESTION_MAX_WORDS];
667 int wordLengthArray[MULTIPLE_WORDS_SUGGESTION_MAX_WORDS];
668 const int outputWordLength = 0;
669 const int startInputPos = 0;
670 const int startWordIndex = 0;
671 getMultiWordsSuggestionRec(proximityInfo, xcoordinates, ycoordinates, codes,
672 useFullEditDistance, inputLength, correction, queuePool, hasAutoCorrectionCandidate,
673 startInputPos, startWordIndex, outputWordLength, freqArray, wordLengthArray,
674 outputWord);
Jean Chalarde6715e32011-06-30 19:47:25 +0900675}
676
Jean Chalard1059f272011-06-28 20:45:05 +0900677// Wrapper for getMostFrequentWordLikeInner, which matches it to the previous
678// interface.
679inline int UnigramDictionary::getMostFrequentWordLike(const int startInputIndex,
satok1147c7b2011-12-14 15:04:58 +0900680 const int inputLength, ProximityInfo *proximityInfo, unsigned short *word) {
Jean Chalard1059f272011-06-28 20:45:05 +0900681 uint16_t inWord[inputLength];
682
683 for (int i = 0; i < inputLength; ++i) {
satok1147c7b2011-12-14 15:04:58 +0900684 inWord[i] = (uint16_t)proximityInfo->getPrimaryCharAt(startInputIndex + i);
Jean Chalard1059f272011-06-28 20:45:05 +0900685 }
686 return getMostFrequentWordLikeInner(inWord, inputLength, word);
687}
688
689// This function will take the position of a character array within a CharGroup,
690// and check it actually like-matches the word in inWord starting at startInputIndex,
691// that is, it matches it with case and accents squashed.
692// The function returns true if there was a full match, false otherwise.
693// The function will copy on-the-fly the characters in the CharGroup to outNewWord.
694// It will also place the end position of the array in outPos; in outInputIndex,
695// it will place the index of the first char AFTER the match if there was a match,
696// and the initial position if there was not. It makes sense because if there was
697// a match we want to continue searching, but if there was not, we want to go to
698// the next CharGroup.
699// In and out parameters may point to the same location. This function takes care
700// not to use any input parameters after it wrote into its outputs.
701static inline bool testCharGroupForContinuedLikeness(const uint8_t flags,
702 const uint8_t* const root, const int startPos,
703 const uint16_t* const inWord, const int startInputIndex,
704 int32_t* outNewWord, int* outInputIndex, int* outPos) {
705 const bool hasMultipleChars = (0 != (UnigramDictionary::FLAG_HAS_MULTIPLE_CHARS & flags));
706 int pos = startPos;
707 int32_t character = BinaryFormat::getCharCodeAndForwardPointer(root, &pos);
Tadashi G. Takaoka6e3cb272011-11-11 14:26:13 +0900708 int32_t baseChar = toBaseLowerCase(character);
709 const uint16_t wChar = toBaseLowerCase(inWord[startInputIndex]);
Jean Chalard1059f272011-06-28 20:45:05 +0900710
711 if (baseChar != wChar) {
712 *outPos = hasMultipleChars ? BinaryFormat::skipOtherCharacters(root, pos) : pos;
713 *outInputIndex = startInputIndex;
714 return false;
715 }
716 int inputIndex = startInputIndex;
717 outNewWord[inputIndex] = character;
718 if (hasMultipleChars) {
719 character = BinaryFormat::getCharCodeAndForwardPointer(root, &pos);
720 while (NOT_A_CHARACTER != character) {
Tadashi G. Takaoka6e3cb272011-11-11 14:26:13 +0900721 baseChar = toBaseLowerCase(character);
722 if (toBaseLowerCase(inWord[++inputIndex]) != baseChar) {
Jean Chalard1059f272011-06-28 20:45:05 +0900723 *outPos = BinaryFormat::skipOtherCharacters(root, pos);
724 *outInputIndex = startInputIndex;
725 return false;
726 }
727 outNewWord[inputIndex] = character;
728 character = BinaryFormat::getCharCodeAndForwardPointer(root, &pos);
729 }
730 }
731 *outInputIndex = inputIndex + 1;
732 *outPos = pos;
733 return true;
734}
735
736// This function is invoked when a word like the word searched for is found.
737// It will compare the frequency to the max frequency, and if greater, will
738// copy the word into the output buffer. In output value maxFreq, it will
739// write the new maximum frequency if it changed.
740static inline void onTerminalWordLike(const int freq, int32_t* newWord, const int length,
741 short unsigned int* outWord, int* maxFreq) {
742 if (freq > *maxFreq) {
743 for (int q = 0; q < length; ++q)
744 outWord[q] = newWord[q];
745 outWord[length] = 0;
746 *maxFreq = freq;
747 }
748}
749
750// Will find the highest frequency of the words like the one passed as an argument,
751// that is, everything that only differs by case/accents.
752int UnigramDictionary::getMostFrequentWordLikeInner(const uint16_t * const inWord,
753 const int length, short unsigned int* outWord) {
754 int32_t newWord[MAX_WORD_LENGTH_INTERNAL];
755 int depth = 0;
756 int maxFreq = -1;
757 const uint8_t* const root = DICT_ROOT;
758
Jean Chalard4c0eca62012-01-16 15:15:53 +0900759 int startPos = 0;
760 mStackChildCount[0] = BinaryFormat::getGroupCountAndForwardPointer(root, &startPos);
Jean Chalard1059f272011-06-28 20:45:05 +0900761 mStackInputIndex[0] = 0;
Jean Chalard4c0eca62012-01-16 15:15:53 +0900762 mStackSiblingPos[0] = startPos;
Jean Chalard1059f272011-06-28 20:45:05 +0900763 while (depth >= 0) {
764 const int charGroupCount = mStackChildCount[depth];
765 int pos = mStackSiblingPos[depth];
766 for (int charGroupIndex = charGroupCount - 1; charGroupIndex >= 0; --charGroupIndex) {
767 int inputIndex = mStackInputIndex[depth];
768 const uint8_t flags = BinaryFormat::getFlagsAndForwardPointer(root, &pos);
769 // Test whether all chars in this group match with the word we are searching for. If so,
770 // we want to traverse its children (or if the length match, evaluate its frequency).
771 // Note that this function will output the position regardless, but will only write
772 // into inputIndex if there is a match.
773 const bool isAlike = testCharGroupForContinuedLikeness(flags, root, pos, inWord,
774 inputIndex, newWord, &inputIndex, &pos);
775 if (isAlike && (FLAG_IS_TERMINAL & flags) && (inputIndex == length)) {
776 const int frequency = BinaryFormat::readFrequencyWithoutMovingPointer(root, pos);
777 onTerminalWordLike(frequency, newWord, inputIndex, outWord, &maxFreq);
778 }
779 pos = BinaryFormat::skipFrequency(flags, pos);
780 const int siblingPos = BinaryFormat::skipChildrenPosAndAttributes(root, flags, pos);
781 const int childrenNodePos = BinaryFormat::readChildrenPosition(root, flags, pos);
782 // If we had a match and the word has children, we want to traverse them. We don't have
783 // to traverse words longer than the one we are searching for, since they will not match
784 // anyway, so don't traverse unless inputIndex < length.
785 if (isAlike && (-1 != childrenNodePos) && (inputIndex < length)) {
786 // Save position for this depth, to get back to this once children are done
787 mStackChildCount[depth] = charGroupIndex;
788 mStackSiblingPos[depth] = siblingPos;
789 // Prepare stack values for next depth
790 ++depth;
791 int childrenPos = childrenNodePos;
792 mStackChildCount[depth] =
793 BinaryFormat::getGroupCountAndForwardPointer(root, &childrenPos);
794 mStackSiblingPos[depth] = childrenPos;
795 mStackInputIndex[depth] = inputIndex;
796 pos = childrenPos;
797 // Go to the next depth level.
798 ++depth;
799 break;
800 } else {
801 // No match, or no children, or word too long to ever match: go the next sibling.
802 pos = siblingPos;
803 }
804 }
805 --depth;
806 }
807 return maxFreq;
808}
809
Satoshi Kataoka2f854e12012-05-29 15:58:13 +0900810int UnigramDictionary::getFrequency(const int32_t* const inWord, const int length) const {
811 const uint8_t* const root = DICT_ROOT;
812 int pos = BinaryFormat::getTerminalPosition(root, inWord, length);
813 if (NOT_VALID_WORD == pos) {
814 return NOT_A_PROBABILITY;
815 }
816 const uint8_t flags = BinaryFormat::getFlagsAndForwardPointer(root, &pos);
817 const bool hasMultipleChars = (0 != (FLAG_HAS_MULTIPLE_CHARS & flags));
818 if (hasMultipleChars) {
819 pos = BinaryFormat::skipOtherCharacters(root, pos);
820 } else {
821 BinaryFormat::getCharCodeAndForwardPointer(DICT_ROOT, &pos);
822 }
823 const int unigramFreq = BinaryFormat::readFrequencyWithoutMovingPointer(root, pos);
824 return unigramFreq;
Jean Chalard1059f272011-06-28 20:45:05 +0900825}
826
827// TODO: remove this function.
828int UnigramDictionary::getBigramPosition(int pos, unsigned short *word, int offset,
829 int length) const {
830 return -1;
831}
832
833// ProcessCurrentNode returns a boolean telling whether to traverse children nodes or not.
834// If the return value is false, then the caller should read in the output "nextSiblingPosition"
835// to find out the address of the next sibling node and pass it to a new call of processCurrentNode.
836// It is worthy to note that when false is returned, the output values other than
837// nextSiblingPosition are undefined.
838// If the return value is true, then the caller must proceed to traverse the children of this
839// node. processCurrentNode will output the information about the children: their count in
840// newCount, their position in newChildrenPosition, the traverseAllNodes flag in
841// newTraverseAllNodes, the match weight into newMatchRate, the input index into newInputIndex, the
842// diffs into newDiffs, the sibling position in nextSiblingPosition, and the output index into
843// newOutputIndex. Please also note the following caveat: processCurrentNode does not know when
844// there aren't any more nodes at this level, it merely returns the address of the first byte after
845// the current node in nextSiblingPosition. Thus, the caller must keep count of the nodes at any
846// given level, as output into newCount when traversing this level's parent.
satok8876b752011-08-04 18:31:57 +0900847inline bool UnigramDictionary::processCurrentNode(const int initialPos,
Jean Chalard8950ce62012-05-07 16:28:30 +0900848 const std::map<int, int> *bigramMap, const uint8_t *bigramFilter, Correction *correction,
849 int *newCount, int *newChildrenPosition, int *nextSiblingPosition,
850 WordsPriorityQueuePool *queuePool, const int currentWordIndex) {
Jean Chalard85a1d1e2011-06-21 22:23:21 +0900851 if (DEBUG_DICT) {
satokcfca3c62011-08-10 14:30:10 +0900852 correction->checkState();
Jean Chalard85a1d1e2011-06-21 22:23:21 +0900853 }
Jean Chalard0584f022011-06-30 19:23:16 +0900854 int pos = initialPos;
Jean Chalard0584f022011-06-30 19:23:16 +0900855
Jean Chalard1059f272011-06-28 20:45:05 +0900856 // Flags contain the following information:
857 // - Address type (MASK_GROUP_ADDRESS_TYPE) on two bits:
858 // - FLAG_GROUP_ADDRESS_TYPE_{ONE,TWO,THREE}_BYTES means there are children and their address
859 // is on the specified number of bytes.
860 // - FLAG_GROUP_ADDRESS_TYPE_NOADDRESS means there are no children, and therefore no address.
861 // - FLAG_HAS_MULTIPLE_CHARS: whether this node has multiple char or not.
862 // - FLAG_IS_TERMINAL: whether this node is a terminal or not (it may still have children)
863 // - FLAG_HAS_BIGRAMS: whether this node has bigrams or not
864 const uint8_t flags = BinaryFormat::getFlagsAndForwardPointer(DICT_ROOT, &pos);
865 const bool hasMultipleChars = (0 != (FLAG_HAS_MULTIPLE_CHARS & flags));
satok8876b752011-08-04 18:31:57 +0900866 const bool isTerminalNode = (0 != (FLAG_IS_TERMINAL & flags));
867
868 bool needsToInvokeOnTerminal = false;
Jean Chalard85a1d1e2011-06-21 22:23:21 +0900869
Jean Chalard1059f272011-06-28 20:45:05 +0900870 // This gets only ONE character from the stream. Next there will be:
871 // if FLAG_HAS_MULTIPLE CHARS: the other characters of the same node
872 // else if FLAG_IS_TERMINAL: the frequency
873 // else if MASK_GROUP_ADDRESS_TYPE is not NONE: the children address
874 // Note that you can't have a node that both is not a terminal and has no children.
875 int32_t c = BinaryFormat::getCharCodeAndForwardPointer(DICT_ROOT, &pos);
876 assert(NOT_A_CHARACTER != c);
Jean Chalard85a1d1e2011-06-21 22:23:21 +0900877
Jean Chalard1059f272011-06-28 20:45:05 +0900878 // We are going to loop through each character and make it look like it's a different
879 // node each time. To do that, we will process characters in this node in order until
880 // we find the character terminator. This is signalled by getCharCode* returning
881 // NOT_A_CHARACTER.
882 // As a special case, if there is only one character in this node, we must not read the
883 // next bytes so we will simulate the NOT_A_CHARACTER return by testing the flags.
884 // This way, each loop run will look like a "virtual node".
885 do {
886 // We prefetch the next char. If 'c' is the last char of this node, we will have
887 // NOT_A_CHARACTER in the next char. From this we can decide whether this virtual node
888 // should behave as a terminal or not and whether we have children.
889 const int32_t nextc = hasMultipleChars
890 ? BinaryFormat::getCharCodeAndForwardPointer(DICT_ROOT, &pos) : NOT_A_CHARACTER;
891 const bool isLastChar = (NOT_A_CHARACTER == nextc);
892 // If there are more chars in this nodes, then this virtual node is not a terminal.
893 // If we are on the last char, this virtual node is a terminal if this node is.
satok8876b752011-08-04 18:31:57 +0900894 const bool isTerminal = isLastChar && isTerminalNode;
Jean Chalard85a1d1e2011-06-21 22:23:21 +0900895
satokcfca3c62011-08-10 14:30:10 +0900896 Correction::CorrectionType stateType = correction->processCharAndCalcState(
satok8876b752011-08-04 18:31:57 +0900897 c, isTerminal);
satokcfca3c62011-08-10 14:30:10 +0900898 if (stateType == Correction::TRAVERSE_ALL_ON_TERMINAL
899 || stateType == Correction::ON_TERMINAL) {
satok8876b752011-08-04 18:31:57 +0900900 needsToInvokeOnTerminal = true;
satokd03317c2011-12-14 21:38:11 +0900901 } else if (stateType == Correction::UNRELATED || correction->needsToPrune()) {
satok8876b752011-08-04 18:31:57 +0900902 // We found that this is an unrelated character, so we should give up traversing
903 // this node and its children entirely.
904 // However we may not be on the last virtual node yet so we skip the remaining
905 // characters in this node, the frequency if it's there, read the next sibling
906 // position to output it, then return false.
907 // We don't have to output other values because we return false, as in
908 // "don't traverse children".
Jean Chalard1059f272011-06-28 20:45:05 +0900909 if (!isLastChar) {
910 pos = BinaryFormat::skipOtherCharacters(DICT_ROOT, pos);
911 }
912 pos = BinaryFormat::skipFrequency(flags, pos);
913 *nextSiblingPosition =
914 BinaryFormat::skipChildrenPosAndAttributes(DICT_ROOT, flags, pos);
915 return false;
Jean Chalard85a1d1e2011-06-21 22:23:21 +0900916 }
917
Jean Chalard1059f272011-06-28 20:45:05 +0900918 // Prepare for the next character. Promote the prefetched char to current char - the loop
919 // will take care of prefetching the next. If we finally found our last char, nextc will
920 // contain NOT_A_CHARACTER.
921 c = nextc;
Jean Chalard1059f272011-06-28 20:45:05 +0900922 } while (NOT_A_CHARACTER != c);
Jean Chalard85a1d1e2011-06-21 22:23:21 +0900923
satok8876b752011-08-04 18:31:57 +0900924 if (isTerminalNode) {
satok6ad15fc2012-01-16 16:21:21 +0900925 // The frequency should be here, because we come here only if this is actually
926 // a terminal node, and we are on its last char.
Jean Chalard171d1802012-04-23 18:51:00 +0900927 const int unigramFreq = BinaryFormat::readFrequencyWithoutMovingPointer(DICT_ROOT, pos);
satok6ad15fc2012-01-16 16:21:21 +0900928 const int childrenAddressPos = BinaryFormat::skipFrequency(flags, pos);
929 const int attributesPos = BinaryFormat::skipChildrenPosition(flags, childrenAddressPos);
930 TerminalAttributes terminalAttributes(DICT_ROOT, flags, attributesPos);
Jean Chalard8950ce62012-05-07 16:28:30 +0900931 // bigramMap contains the bigram frequencies indexed by addresses for fast lookup.
932 // bigramFilter is a bloom filter of said frequencies for even faster rejection.
Jean Chalard49ba1352012-05-07 20:14:00 +0900933 const int probability = BinaryFormat::getProbability(initialPos, bigramMap, bigramFilter,
934 unigramFreq);
Jean Chalard171d1802012-04-23 18:51:00 +0900935 onTerminal(probability, terminalAttributes, correction, queuePool, needsToInvokeOnTerminal,
satok8330b482012-01-23 16:52:37 +0900936 currentWordIndex);
Jean Chalard1059f272011-06-28 20:45:05 +0900937
satok8876b752011-08-04 18:31:57 +0900938 // If there are more chars in this node, then this virtual node has children.
939 // If we are on the last char, this virtual node has children if this node has.
940 const bool hasChildren = BinaryFormat::hasChildrenInFlags(flags);
941
942 // This character matched the typed character (enough to traverse the node at least)
943 // so we just evaluated it. Now we should evaluate this virtual node's children - that
944 // is, if it has any. If it has no children, we're done here - so we skip the end of
945 // the node, output the siblings position, and return false "don't traverse children".
946 // Note that !hasChildren implies isLastChar, so we know we don't have to skip any
947 // remaining char in this group for there can't be any.
948 if (!hasChildren) {
949 pos = BinaryFormat::skipFrequency(flags, pos);
950 *nextSiblingPosition =
951 BinaryFormat::skipChildrenPosAndAttributes(DICT_ROOT, flags, pos);
952 return false;
953 }
954
955 // Optimization: Prune out words that are too long compared to how much was typed.
satokcfca3c62011-08-10 14:30:10 +0900956 if (correction->needsToPrune()) {
satok8876b752011-08-04 18:31:57 +0900957 pos = BinaryFormat::skipFrequency(flags, pos);
958 *nextSiblingPosition =
959 BinaryFormat::skipChildrenPosAndAttributes(DICT_ROOT, flags, pos);
satok10266c02011-08-19 22:05:59 +0900960 if (DEBUG_DICT_FULL) {
satok9fb6f472012-01-13 18:01:22 +0900961 AKLOGI("Traversing was pruned.");
satok10266c02011-08-19 22:05:59 +0900962 }
satok8876b752011-08-04 18:31:57 +0900963 return false;
964 }
965 }
Jean Chalard1059f272011-06-28 20:45:05 +0900966
967 // Now we finished processing this node, and we want to traverse children. If there are no
968 // children, we can't come here.
969 assert(BinaryFormat::hasChildrenInFlags(flags));
970
971 // If this node was a terminal it still has the frequency under the pointer (it may have been
972 // read, but not skipped - see readFrequencyWithoutMovingPointer).
973 // Next come the children position, then possibly attributes (attributes are bigrams only for
974 // now, maybe something related to shortcuts in the future).
975 // Once this is read, we still need to output the number of nodes in the immediate children of
976 // this node, so we read and output it before returning true, as in "please traverse children".
977 pos = BinaryFormat::skipFrequency(flags, pos);
978 int childrenPos = BinaryFormat::readChildrenPosition(DICT_ROOT, flags, pos);
979 *nextSiblingPosition = BinaryFormat::skipChildrenPosAndAttributes(DICT_ROOT, flags, pos);
980 *newCount = BinaryFormat::getGroupCountAndForwardPointer(DICT_ROOT, &childrenPos);
981 *newChildrenPosition = childrenPos;
982 return true;
Jean Chalard85a1d1e2011-06-21 22:23:21 +0900983}
984
satok30088252010-12-01 21:22:15 +0900985} // namespace latinime