blob: eafc2e5aac5734914372751ceaf9d0825c27b8a8 [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;
Jean Chalardaa8df592012-04-06 18:54:20 +0900180 if (BinaryFormat::REQUIRES_GERMAN_UMLAUT_PROCESSING & FLAGS)
Jean Chalardc2bbc6a2011-02-25 17:56:53 +0900181 { // Incrementally tune the word and try all possibilities
satok9df4a452012-03-23 16:05:18 +0900182 int codesBuffer[getCodesBufferSize(codes, codesSize)];
satok219a5142012-03-08 11:53:18 +0900183 int xCoordinatesBuffer[codesSize];
184 int yCoordinatesBuffer[codesSize];
Jean Chalardc2bbc6a2011-02-25 17:56:53 +0900185 getWordWithDigraphSuggestionsRec(proximityInfo, xcoordinates, ycoordinates, codesBuffer,
Jean Chalard8950ce62012-05-07 16:28:30 +0900186 xCoordinatesBuffer, yCoordinatesBuffer, codesSize, bigramMap, bigramFilter,
Jean Chalard4d9b2022012-04-23 19:25:28 +0900187 useFullEditDistance, codes, codesSize, 0, codesBuffer, masterCorrection,
Jean Chalard338d3ec2012-04-06 19:28:34 +0900188 queuePool, GERMAN_UMLAUT_DIGRAPHS,
Jean Chalard6c300612012-03-06 19:54:03 +0900189 sizeof(GERMAN_UMLAUT_DIGRAPHS) / sizeof(GERMAN_UMLAUT_DIGRAPHS[0]));
Jean Chalardaa8df592012-04-06 18:54:20 +0900190 } else if (BinaryFormat::REQUIRES_FRENCH_LIGATURES_PROCESSING & FLAGS) {
satokacb6c542012-03-23 20:58:18 +0900191 int codesBuffer[getCodesBufferSize(codes, codesSize)];
Jean Chalardcc78d032012-03-23 16:48:49 +0900192 int xCoordinatesBuffer[codesSize];
193 int yCoordinatesBuffer[codesSize];
194 getWordWithDigraphSuggestionsRec(proximityInfo, xcoordinates, ycoordinates, codesBuffer,
Jean Chalard8950ce62012-05-07 16:28:30 +0900195 xCoordinatesBuffer, yCoordinatesBuffer, codesSize, bigramMap, bigramFilter,
Jean Chalard4d9b2022012-04-23 19:25:28 +0900196 useFullEditDistance, codes, codesSize, 0, codesBuffer, masterCorrection,
Jean Chalard338d3ec2012-04-06 19:28:34 +0900197 queuePool, FRENCH_LIGATURES_DIGRAPHS,
Jean Chalardcc78d032012-03-23 16:48:49 +0900198 sizeof(FRENCH_LIGATURES_DIGRAPHS) / sizeof(FRENCH_LIGATURES_DIGRAPHS[0]));
Jean Chalardc2bbc6a2011-02-25 17:56:53 +0900199 } else { // Normal processing
Jean Chalard338d3ec2012-04-06 19:28:34 +0900200 getWordSuggestions(proximityInfo, xcoordinates, ycoordinates, codes, codesSize,
Jean Chalard8950ce62012-05-07 16:28:30 +0900201 bigramMap, bigramFilter, useFullEditDistance, masterCorrection, queuePool);
Jean Chalardc2bbc6a2011-02-25 17:56:53 +0900202 }
203
satok817e5172011-03-04 06:06:45 -0800204 PROF_START(20);
satok8330b482012-01-23 16:52:37 +0900205 if (DEBUG_DICT) {
satok0028ed32012-05-16 20:42:12 +0900206 float ns = queuePool->getMasterQueue()->getHighestNormalizedScore(
satok8330b482012-01-23 16:52:37 +0900207 proximityInfo->getPrimaryInputWord(), codesSize, 0, 0, 0);
208 ns += 0;
209 AKLOGI("Max normalized score = %f", ns);
210 }
satoka7e5a5a2011-12-15 16:49:12 +0900211 const int suggestedWordsCount =
satokdb1939d2012-05-15 17:43:31 +0900212 queuePool->getMasterQueue()->outputSuggestions(
213 proximityInfo->getPrimaryInputWord(), codesSize, frequencies, outWords);
Jean Chalardc2bbc6a2011-02-25 17:56:53 +0900214
215 if (DEBUG_DICT) {
satok0028ed32012-05-16 20:42:12 +0900216 float ns = queuePool->getMasterQueue()->getHighestNormalizedScore(
satok8330b482012-01-23 16:52:37 +0900217 proximityInfo->getPrimaryInputWord(), codesSize, 0, 0, 0);
218 ns += 0;
satok9fb6f472012-01-13 18:01:22 +0900219 AKLOGI("Returning %d words", suggestedWordsCount);
Jean Chalard980d6b62011-06-30 17:02:23 +0900220 /// Print the returned words
221 for (int j = 0; j < suggestedWordsCount; ++j) {
satok16379df2011-12-12 20:53:22 +0900222 short unsigned int* w = outWords + j * MAX_WORD_LENGTH;
Jean Chalard980d6b62011-06-30 17:02:23 +0900223 char s[MAX_WORD_LENGTH];
224 for (int i = 0; i <= MAX_WORD_LENGTH; i++) s[i] = w[i];
Jean-Baptiste Querucd7c4132012-05-16 16:56:11 -0700225 (void)s;
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");
Ken Wakasade3070a2011-03-19 09:16:42 +0900305 }
satok1a6da632011-12-16 23:15:06 +0900306 proximityInfo->setInputParams(codes, inputLength, xCoordinates, yCoordinates);
satok1a6da632011-12-16 23:15:06 +0900307 const int maxDepth = min(inputLength * MAX_DEPTH_MULTIPLIER, MAX_WORD_LENGTH);
308 correction->initCorrection(proximityInfo, inputLength, maxDepth);
satok30088252010-12-01 21:22:15 +0900309}
310
satok715514d2010-12-02 20:19:59 +0900311static const char QUOTE = '\'';
satok662fe692010-12-08 17:05:39 +0900312static const char SPACE = ' ';
satok30088252010-12-01 21:22:15 +0900313
satok744dab62011-12-15 22:29:05 +0900314void UnigramDictionary::getOneWordSuggestions(ProximityInfo *proximityInfo,
315 const int *xcoordinates, const int *ycoordinates, const int *codes,
Jean Chalard8950ce62012-05-07 16:28:30 +0900316 const std::map<int, int> *bigramMap, const uint8_t *bigramFilter,
317 const bool useFullEditDistance, const int inputLength,
Jean Chalard4d9b2022012-04-23 19:25:28 +0900318 Correction *correction, WordsPriorityQueuePool *queuePool) {
satok6ad15fc2012-01-16 16:21:21 +0900319 initSuggestions(proximityInfo, xcoordinates, ycoordinates, codes, inputLength, correction);
Jean Chalard8950ce62012-05-07 16:28:30 +0900320 getSuggestionCandidates(useFullEditDistance, inputLength, bigramMap, bigramFilter, correction,
Jean Chalard4d9b2022012-04-23 19:25:28 +0900321 queuePool, true /* doAutoCompletion */, DEFAULT_MAX_ERRORS, FIRST_WORD_INDEX);
satok744dab62011-12-15 22:29:05 +0900322}
323
satok1147c7b2011-12-14 15:04:58 +0900324void UnigramDictionary::getSuggestionCandidates(const bool useFullEditDistance,
Jean Chalard8950ce62012-05-07 16:28:30 +0900325 const int inputLength, const std::map<int, int> *bigramMap, const uint8_t *bigramFilter,
Jean Chalard4d9b2022012-04-23 19:25:28 +0900326 Correction *correction, WordsPriorityQueuePool *queuePool,
satok8330b482012-01-23 16:52:37 +0900327 const bool doAutoCompletion, const int maxErrors, const int currentWordIndex) {
satok10266c02011-08-19 22:05:59 +0900328 // TODO: Remove setCorrectionParams
satok1147c7b2011-12-14 15:04:58 +0900329 correction->setCorrectionParams(0, 0, 0,
satokd03317c2011-12-14 21:38:11 +0900330 -1 /* spaceProximityPos */, -1 /* missingSpacePos */, useFullEditDistance,
satok1a6da632011-12-16 23:15:06 +0900331 doAutoCompletion, maxErrors);
satok662fe692010-12-08 17:05:39 +0900332 int rootPosition = ROOT_POS;
Jean Chalard980d6b62011-06-30 17:02:23 +0900333 // Get the number of children of root, then increment the position
Jean Chalard6d419812012-01-16 15:19:47 +0900334 int childCount = BinaryFormat::getGroupCountAndForwardPointer(DICT_ROOT, &rootPosition);
satok208268d2011-08-10 15:44:08 +0900335 int outputIndex = 0;
satokd2997922010-12-07 13:08:39 +0900336
satok1147c7b2011-12-14 15:04:58 +0900337 correction->initCorrectionState(rootPosition, childCount, (inputLength <= 0));
satokd2997922010-12-07 13:08:39 +0900338
satok662fe692010-12-08 17:05:39 +0900339 // Depth first search
satok208268d2011-08-10 15:44:08 +0900340 while (outputIndex >= 0) {
satok1147c7b2011-12-14 15:04:58 +0900341 if (correction->initProcessState(outputIndex)) {
342 int siblingPos = correction->getTreeSiblingPos(outputIndex);
satokd2997922010-12-07 13:08:39 +0900343 int firstChildPos;
satok0f6c8e82011-08-03 02:19:44 +0900344
satok4e4e74e2011-08-03 23:27:32 +0900345 const bool needsToTraverseChildrenNodes = processCurrentNode(siblingPos,
Jean Chalard8950ce62012-05-07 16:28:30 +0900346 bigramMap, bigramFilter, correction, &childCount, &firstChildPos, &siblingPos,
Jean Chalard4d9b2022012-04-23 19:25:28 +0900347 queuePool, currentWordIndex);
satok662fe692010-12-08 17:05:39 +0900348 // Update next sibling pos
satok1147c7b2011-12-14 15:04:58 +0900349 correction->setTreeSiblingPos(outputIndex, siblingPos);
satok208268d2011-08-10 15:44:08 +0900350
satokd2997922010-12-07 13:08:39 +0900351 if (needsToTraverseChildrenNodes) {
352 // Goes to child node
satok1147c7b2011-12-14 15:04:58 +0900353 outputIndex = correction->goDownTree(outputIndex, childCount, firstChildPos);
satokd2997922010-12-07 13:08:39 +0900354 }
355 } else {
satokcdbbea72010-12-08 16:04:16 +0900356 // Goes to parent sibling node
satok1147c7b2011-12-14 15:04:58 +0900357 outputIndex = correction->getTreeParentIndex(outputIndex);
satokd2997922010-12-07 13:08:39 +0900358 }
359 }
360}
361
Jean Chalard171d1802012-04-23 18:51:00 +0900362inline void UnigramDictionary::onTerminal(const int probability,
Jean Chalardcf9dbbd2011-12-26 15:16:59 +0900363 const TerminalAttributes& terminalAttributes, Correction *correction,
satok8330b482012-01-23 16:52:37 +0900364 WordsPriorityQueuePool *queuePool, const bool addToMasterQueue,
365 const int currentWordIndex) {
satok6ad15fc2012-01-16 16:21:21 +0900366 const int inputIndex = correction->getInputIndex();
367 const bool addToSubQueue = inputIndex < SUB_QUEUE_MAX_COUNT;
satok54af64a2012-01-17 15:58:23 +0900368
satok8876b752011-08-04 18:31:57 +0900369 int wordLength;
370 unsigned short* wordPointer;
satok54af64a2012-01-17 15:58:23 +0900371
satok1f6b52e2012-01-30 13:53:58 +0900372 if ((currentWordIndex == FIRST_WORD_INDEX) && addToMasterQueue) {
satok54af64a2012-01-17 15:58:23 +0900373 WordsPriorityQueue *masterQueue = queuePool->getMasterQueue();
Jean Chalard171d1802012-04-23 18:51:00 +0900374 const int finalProbability =
375 correction->getFinalProbability(probability, &wordPointer, &wordLength);
376 if (finalProbability != NOT_A_PROBABILITY) {
377 addWord(wordPointer, wordLength, finalProbability, masterQueue);
satok54af64a2012-01-17 15:58:23 +0900378
Jean Chalard171d1802012-04-23 18:51:00 +0900379 const int shortcutProbability = finalProbability > 0 ? finalProbability - 1 : 0;
satok54af64a2012-01-17 15:58:23 +0900380 // Please note that the shortcut candidates will be added to the master queue only.
381 TerminalAttributes::ShortcutIterator iterator =
382 terminalAttributes.getShortcutIterator();
383 while (iterator.hasNextShortcutTarget()) {
384 // TODO: addWord only supports weak ordering, meaning we have no means
385 // to control the order of the shortcuts relative to one another or to the word.
Jean Chalard171d1802012-04-23 18:51:00 +0900386 // We need to either modulate the probability of each shortcut according
387 // to its own shortcut probability or to make the queue
satok54af64a2012-01-17 15:58:23 +0900388 // so that the insert order is protected inside the queue for words
Jean Chalard9a933a72012-03-27 19:56:23 +0900389 // with the same score. For the moment we use -1 to make sure the shortcut will
390 // never be in front of the word.
satok54af64a2012-01-17 15:58:23 +0900391 uint16_t shortcutTarget[MAX_WORD_LENGTH_INTERNAL];
392 const int shortcutTargetStringLength = iterator.getNextShortcutTarget(
393 MAX_WORD_LENGTH_INTERNAL, shortcutTarget);
Jean Chalard171d1802012-04-23 18:51:00 +0900394 addWord(shortcutTarget, shortcutTargetStringLength, shortcutProbability,
395 masterQueue);
satok6ad15fc2012-01-16 16:21:21 +0900396 }
Jean Chalardcf9dbbd2011-12-26 15:16:59 +0900397 }
satok54af64a2012-01-17 15:58:23 +0900398 }
satok6ad15fc2012-01-16 16:21:21 +0900399
satok54af64a2012-01-17 15:58:23 +0900400 // We only allow two words + other error correction for words with SUB_QUEUE_MIN_WORD_LENGTH
401 // or more length.
402 if (inputIndex >= SUB_QUEUE_MIN_WORD_LENGTH && addToSubQueue) {
satok8330b482012-01-23 16:52:37 +0900403 WordsPriorityQueue *subQueue;
satok7409d152012-01-26 16:13:25 +0900404 subQueue = queuePool->getSubQueue(currentWordIndex, inputIndex);
405 if (!subQueue) {
satok8330b482012-01-23 16:52:37 +0900406 return;
407 }
Jean Chalard171d1802012-04-23 18:51:00 +0900408 const int finalProbability = correction->getFinalProbabilityForSubQueue(
409 probability, &wordPointer, &wordLength, inputIndex);
410 addWord(wordPointer, wordLength, finalProbability, subQueue);
Jean Chalardca5ef282011-06-17 15:36:26 +0900411 }
412}
413
satok99557162012-01-26 22:49:13 +0900414bool UnigramDictionary::getSubStringSuggestion(
satok7409d152012-01-26 16:13:25 +0900415 ProximityInfo *proximityInfo, const int *xcoordinates, const int *ycoordinates,
satok3c09bb12012-01-26 18:36:19 +0900416 const int *codes, const bool useFullEditDistance, Correction *correction,
417 WordsPriorityQueuePool* queuePool, const int inputLength,
418 const bool hasAutoCorrectionCandidate, const int currentWordIndex,
419 const int inputWordStartPos, const int inputWordLength,
satok99557162012-01-26 22:49:13 +0900420 const int outputWordStartPos, const bool isSpaceProximity, int *freqArray,
421 int*wordLengthArray, unsigned short* outputWord, int *outputWordLength) {
satok3c09bb12012-01-26 18:36:19 +0900422 unsigned short* tempOutputWord = 0;
satok1f6b52e2012-01-30 13:53:58 +0900423 int nextWordLength = 0;
satok99557162012-01-26 22:49:13 +0900424 // TODO: Optimize init suggestion
425 initSuggestions(proximityInfo, xcoordinates, ycoordinates, codes,
426 inputLength, correction);
427
satok3c09bb12012-01-26 18:36:19 +0900428 int freq = getMostFrequentWordLike(
429 inputWordStartPos, inputWordLength, proximityInfo, mWord);
430 if (freq > 0) {
satok1f6b52e2012-01-30 13:53:58 +0900431 nextWordLength = inputWordLength;
satok3c09bb12012-01-26 18:36:19 +0900432 tempOutputWord = mWord;
433 } else if (!hasAutoCorrectionCandidate) {
434 if (inputWordStartPos > 0) {
435 const int offset = inputWordStartPos;
436 initSuggestions(proximityInfo, &xcoordinates[offset], &ycoordinates[offset],
satok9df4a452012-03-23 16:05:18 +0900437 codes + offset, inputWordLength, correction);
satok3c09bb12012-01-26 18:36:19 +0900438 queuePool->clearSubQueue(currentWordIndex);
Jean Chalard4d9b2022012-04-23 19:25:28 +0900439 // TODO: pass the bigram list for substring suggestion
440 getSuggestionCandidates(useFullEditDistance, inputWordLength,
Jean Chalard8950ce62012-05-07 16:28:30 +0900441 0 /* bigramMap */, 0 /* bigramFilter */, correction, queuePool,
442 false /* doAutoCompletion */, MAX_ERRORS_FOR_TWO_WORDS, currentWordIndex);
satok3c09bb12012-01-26 18:36:19 +0900443 if (DEBUG_DICT) {
satok1f6b52e2012-01-30 13:53:58 +0900444 if (currentWordIndex < MULTIPLE_WORDS_SUGGESTION_MAX_WORDS) {
satok3c09bb12012-01-26 18:36:19 +0900445 AKLOGI("Dump word candidates(%d) %d", currentWordIndex, inputWordLength);
446 for (int i = 0; i < SUB_QUEUE_MAX_COUNT; ++i) {
447 queuePool->getSubQueue(currentWordIndex, i)->dumpTopWord();
448 }
449 }
450 }
451 }
452 WordsPriorityQueue* queue = queuePool->getSubQueue(currentWordIndex, inputWordLength);
453 if (!queue || queue->size() < 1) {
satok99557162012-01-26 22:49:13 +0900454 return false;
satok3c09bb12012-01-26 18:36:19 +0900455 }
456 int score = 0;
satok0028ed32012-05-16 20:42:12 +0900457 const float ns = queue->getHighestNormalizedScore(
satok3c09bb12012-01-26 18:36:19 +0900458 proximityInfo->getPrimaryInputWord(), inputWordLength,
satok1f6b52e2012-01-30 13:53:58 +0900459 &tempOutputWord, &score, &nextWordLength);
satok3c09bb12012-01-26 18:36:19 +0900460 if (DEBUG_DICT) {
461 AKLOGI("NS(%d) = %f, Score = %d", currentWordIndex, ns, score);
462 }
463 // Two words correction won't be done if the score of the first word doesn't exceed the
464 // threshold.
465 if (ns < TWO_WORDS_CORRECTION_WITH_OTHER_ERROR_THRESHOLD
satok1f6b52e2012-01-30 13:53:58 +0900466 || nextWordLength < SUB_QUEUE_MIN_WORD_LENGTH) {
satok99557162012-01-26 22:49:13 +0900467 return false;
satok3c09bb12012-01-26 18:36:19 +0900468 }
satok1f6b52e2012-01-30 13:53:58 +0900469 freq = score >> (nextWordLength + TWO_WORDS_PLUS_OTHER_ERROR_CORRECTION_DEMOTION_DIVIDER);
satok3c09bb12012-01-26 18:36:19 +0900470 }
471 if (DEBUG_DICT) {
satok1f6b52e2012-01-30 13:53:58 +0900472 AKLOGI("Freq(%d): %d, length: %d, input length: %d, input start: %d (%d)"
473 , currentWordIndex, freq, nextWordLength, inputWordLength, inputWordStartPos,
474 wordLengthArray[0]);
satok3c09bb12012-01-26 18:36:19 +0900475 }
satok1f6b52e2012-01-30 13:53:58 +0900476 if (freq <= 0 || nextWordLength <= 0
477 || MAX_WORD_LENGTH <= (outputWordStartPos + nextWordLength)) {
satok99557162012-01-26 22:49:13 +0900478 return false;
satok3c09bb12012-01-26 18:36:19 +0900479 }
satok1f6b52e2012-01-30 13:53:58 +0900480 for (int i = 0; i < nextWordLength; ++i) {
satok3c09bb12012-01-26 18:36:19 +0900481 outputWord[outputWordStartPos + i] = tempOutputWord[i];
482 }
satok99557162012-01-26 22:49:13 +0900483
484 // Put output values
satok1f6b52e2012-01-30 13:53:58 +0900485 freqArray[currentWordIndex] = freq;
satok99557162012-01-26 22:49:13 +0900486 // TODO: put output length instead of input length
satok1f6b52e2012-01-30 13:53:58 +0900487 wordLengthArray[currentWordIndex] = inputWordLength;
488 const int tempOutputWordLength = outputWordStartPos + nextWordLength;
489 if (outputWordLength) {
490 *outputWordLength = tempOutputWordLength;
491 }
satok99557162012-01-26 22:49:13 +0900492
satok3c09bb12012-01-26 18:36:19 +0900493 if ((inputWordStartPos + inputWordLength) < inputLength) {
satok1f6b52e2012-01-30 13:53:58 +0900494 if (outputWordStartPos + nextWordLength >= MAX_WORD_LENGTH) {
satok99557162012-01-26 22:49:13 +0900495 return false;
satok3c09bb12012-01-26 18:36:19 +0900496 }
satoka85f4922012-01-30 18:18:30 +0900497 outputWord[tempOutputWordLength] = SPACE;
satok1f6b52e2012-01-30 13:53:58 +0900498 if (outputWordLength) {
499 ++*outputWordLength;
500 }
501 } else if (currentWordIndex >= 1) {
satok99557162012-01-26 22:49:13 +0900502 // TODO: Handle 3 or more words
satoka85f4922012-01-30 18:18:30 +0900503 const int pairFreq = correction->getFreqForSplitMultipleWords(
504 freqArray, wordLengthArray, currentWordIndex + 1, isSpaceProximity, outputWord);
satok99557162012-01-26 22:49:13 +0900505 if (DEBUG_DICT) {
satoka85f4922012-01-30 18:18:30 +0900506 DUMP_WORD(outputWord, tempOutputWordLength);
507 AKLOGI("Split two words: %d, %d, %d, %d, (%d) %d", freqArray[0], freqArray[1], pairFreq,
508 inputLength, wordLengthArray[0], tempOutputWordLength);
satok99557162012-01-26 22:49:13 +0900509 }
satok1f6b52e2012-01-30 13:53:58 +0900510 addWord(outputWord, tempOutputWordLength, pairFreq, queuePool->getMasterQueue());
satok3c09bb12012-01-26 18:36:19 +0900511 }
satok99557162012-01-26 22:49:13 +0900512 return true;
satok7409d152012-01-26 16:13:25 +0900513}
514
satok1f6b52e2012-01-30 13:53:58 +0900515void UnigramDictionary::getMultiWordsSuggestionRec(ProximityInfo *proximityInfo,
516 const int *xcoordinates, const int *ycoordinates, const int *codes,
517 const bool useFullEditDistance, const int inputLength,
518 Correction *correction, WordsPriorityQueuePool* queuePool,
519 const bool hasAutoCorrectionCandidate, const int startInputPos, const int startWordIndex,
520 const int outputWordLength, int *freqArray, int* wordLengthArray,
521 unsigned short* outputWord) {
522 if (startWordIndex >= (MULTIPLE_WORDS_SUGGESTION_MAX_WORDS - 1)) {
523 // Return if the last word index
524 return;
525 }
satoka85f4922012-01-30 18:18:30 +0900526 if (startWordIndex >= 1
527 && (hasAutoCorrectionCandidate
528 || inputLength < MIN_INPUT_LENGTH_FOR_THREE_OR_MORE_WORDS_CORRECTION)) {
529 // Do not suggest 3+ words if already has auto correction candidate
530 return;
531 }
532 for (int i = startInputPos + 1; i < inputLength; ++i) {
satok1f6b52e2012-01-30 13:53:58 +0900533 if (DEBUG_CORRECTION_FREQ) {
satoka85f4922012-01-30 18:18:30 +0900534 AKLOGI("Multi words(%d), start in %d sep %d start out %d",
535 startWordIndex, startInputPos, i, outputWordLength);
536 DUMP_WORD(outputWord, outputWordLength);
satok1f6b52e2012-01-30 13:53:58 +0900537 }
satoka85f4922012-01-30 18:18:30 +0900538 int tempOutputWordLength = 0;
539 // Current word
540 int inputWordStartPos = startInputPos;
541 int inputWordLength = i - startInputPos;
satok1f6b52e2012-01-30 13:53:58 +0900542 if (!getSubStringSuggestion(proximityInfo, xcoordinates, ycoordinates, codes,
543 useFullEditDistance, correction, queuePool, inputLength, hasAutoCorrectionCandidate,
satoka85f4922012-01-30 18:18:30 +0900544 startWordIndex, inputWordStartPos, inputWordLength, outputWordLength,
545 true /* not used */, freqArray, wordLengthArray, outputWord,
546 &tempOutputWordLength)) {
satok1f6b52e2012-01-30 13:53:58 +0900547 continue;
548 }
549
satoka85f4922012-01-30 18:18:30 +0900550 if (DEBUG_CORRECTION_FREQ) {
551 AKLOGI("Do missing space correction");
552 }
553 // Next word
satok1f6b52e2012-01-30 13:53:58 +0900554 // Missing space
555 inputWordStartPos = i;
556 inputWordLength = inputLength - i;
satoka85f4922012-01-30 18:18:30 +0900557 if(!getSubStringSuggestion(proximityInfo, xcoordinates, ycoordinates, codes,
satok1f6b52e2012-01-30 13:53:58 +0900558 useFullEditDistance, correction, queuePool, inputLength, hasAutoCorrectionCandidate,
satoka85f4922012-01-30 18:18:30 +0900559 startWordIndex + 1, inputWordStartPos, inputWordLength, tempOutputWordLength,
560 false /* missing space */, freqArray, wordLengthArray, outputWord, 0)) {
561 getMultiWordsSuggestionRec(proximityInfo, xcoordinates, ycoordinates, codes,
562 useFullEditDistance, inputLength, correction, queuePool,
563 hasAutoCorrectionCandidate, inputWordStartPos, startWordIndex + 1,
564 tempOutputWordLength, freqArray, wordLengthArray, outputWord);
565 }
satok1f6b52e2012-01-30 13:53:58 +0900566
567 // Mistyped space
568 ++inputWordStartPos;
569 --inputWordLength;
570
571 if (inputWordLength <= 0) {
572 continue;
573 }
574
575 const int x = xcoordinates[inputWordStartPos - 1];
576 const int y = ycoordinates[inputWordStartPos - 1];
577 if (!proximityInfo->hasSpaceProximity(x, y)) {
578 continue;
579 }
580
satoka85f4922012-01-30 18:18:30 +0900581 if (DEBUG_CORRECTION_FREQ) {
582 AKLOGI("Do mistyped space correction");
583 }
satok1f6b52e2012-01-30 13:53:58 +0900584 getSubStringSuggestion(proximityInfo, xcoordinates, ycoordinates, codes,
585 useFullEditDistance, correction, queuePool, inputLength, hasAutoCorrectionCandidate,
satoka85f4922012-01-30 18:18:30 +0900586 startWordIndex + 1, inputWordStartPos, inputWordLength, tempOutputWordLength,
587 true /* mistyped space */, freqArray, wordLengthArray, outputWord, 0);
satok1f6b52e2012-01-30 13:53:58 +0900588 }
589}
590
satoka85f4922012-01-30 18:18:30 +0900591void UnigramDictionary::getSplitMultipleWordsSuggestions(ProximityInfo *proximityInfo,
satok744dab62011-12-15 22:29:05 +0900592 const int *xcoordinates, const int *ycoordinates, const int *codes,
satok1f6b52e2012-01-30 13:53:58 +0900593 const bool useFullEditDistance, const int inputLength,
satok99557162012-01-26 22:49:13 +0900594 Correction *correction, WordsPriorityQueuePool* queuePool,
satok8330b482012-01-23 16:52:37 +0900595 const bool hasAutoCorrectionCandidate) {
satokbd6ccdd2012-01-23 12:30:20 +0900596 if (inputLength >= MAX_WORD_LENGTH) return;
satok612c6e42011-08-01 19:35:27 +0900597 if (DEBUG_DICT) {
satok1f6b52e2012-01-30 13:53:58 +0900598 AKLOGI("--- Suggest multiple words");
599 }
satok54af64a2012-01-17 15:58:23 +0900600
satokbd6ccdd2012-01-23 12:30:20 +0900601 // Allocating fixed length array on stack
602 unsigned short outputWord[MAX_WORD_LENGTH];
satok1f6b52e2012-01-30 13:53:58 +0900603 int freqArray[MULTIPLE_WORDS_SUGGESTION_MAX_WORDS];
604 int wordLengthArray[MULTIPLE_WORDS_SUGGESTION_MAX_WORDS];
605 const int outputWordLength = 0;
606 const int startInputPos = 0;
607 const int startWordIndex = 0;
608 getMultiWordsSuggestionRec(proximityInfo, xcoordinates, ycoordinates, codes,
609 useFullEditDistance, inputLength, correction, queuePool, hasAutoCorrectionCandidate,
610 startInputPos, startWordIndex, outputWordLength, freqArray, wordLengthArray,
611 outputWord);
Jean Chalarde6715e32011-06-30 19:47:25 +0900612}
613
Jean Chalard1059f272011-06-28 20:45:05 +0900614// Wrapper for getMostFrequentWordLikeInner, which matches it to the previous
615// interface.
616inline int UnigramDictionary::getMostFrequentWordLike(const int startInputIndex,
satok1147c7b2011-12-14 15:04:58 +0900617 const int inputLength, ProximityInfo *proximityInfo, unsigned short *word) {
Jean Chalard1059f272011-06-28 20:45:05 +0900618 uint16_t inWord[inputLength];
619
620 for (int i = 0; i < inputLength; ++i) {
satok1147c7b2011-12-14 15:04:58 +0900621 inWord[i] = (uint16_t)proximityInfo->getPrimaryCharAt(startInputIndex + i);
Jean Chalard1059f272011-06-28 20:45:05 +0900622 }
623 return getMostFrequentWordLikeInner(inWord, inputLength, word);
624}
625
626// This function will take the position of a character array within a CharGroup,
627// and check it actually like-matches the word in inWord starting at startInputIndex,
628// that is, it matches it with case and accents squashed.
629// The function returns true if there was a full match, false otherwise.
630// The function will copy on-the-fly the characters in the CharGroup to outNewWord.
631// It will also place the end position of the array in outPos; in outInputIndex,
632// it will place the index of the first char AFTER the match if there was a match,
633// and the initial position if there was not. It makes sense because if there was
634// a match we want to continue searching, but if there was not, we want to go to
635// the next CharGroup.
636// In and out parameters may point to the same location. This function takes care
637// not to use any input parameters after it wrote into its outputs.
638static inline bool testCharGroupForContinuedLikeness(const uint8_t flags,
639 const uint8_t* const root, const int startPos,
640 const uint16_t* const inWord, const int startInputIndex,
641 int32_t* outNewWord, int* outInputIndex, int* outPos) {
642 const bool hasMultipleChars = (0 != (UnigramDictionary::FLAG_HAS_MULTIPLE_CHARS & flags));
643 int pos = startPos;
644 int32_t character = BinaryFormat::getCharCodeAndForwardPointer(root, &pos);
Tadashi G. Takaoka6e3cb272011-11-11 14:26:13 +0900645 int32_t baseChar = toBaseLowerCase(character);
646 const uint16_t wChar = toBaseLowerCase(inWord[startInputIndex]);
Jean Chalard1059f272011-06-28 20:45:05 +0900647
648 if (baseChar != wChar) {
649 *outPos = hasMultipleChars ? BinaryFormat::skipOtherCharacters(root, pos) : pos;
650 *outInputIndex = startInputIndex;
651 return false;
652 }
653 int inputIndex = startInputIndex;
654 outNewWord[inputIndex] = character;
655 if (hasMultipleChars) {
656 character = BinaryFormat::getCharCodeAndForwardPointer(root, &pos);
657 while (NOT_A_CHARACTER != character) {
Tadashi G. Takaoka6e3cb272011-11-11 14:26:13 +0900658 baseChar = toBaseLowerCase(character);
659 if (toBaseLowerCase(inWord[++inputIndex]) != baseChar) {
Jean Chalard1059f272011-06-28 20:45:05 +0900660 *outPos = BinaryFormat::skipOtherCharacters(root, pos);
661 *outInputIndex = startInputIndex;
662 return false;
663 }
664 outNewWord[inputIndex] = character;
665 character = BinaryFormat::getCharCodeAndForwardPointer(root, &pos);
666 }
667 }
668 *outInputIndex = inputIndex + 1;
669 *outPos = pos;
670 return true;
671}
672
673// This function is invoked when a word like the word searched for is found.
674// It will compare the frequency to the max frequency, and if greater, will
675// copy the word into the output buffer. In output value maxFreq, it will
676// write the new maximum frequency if it changed.
677static inline void onTerminalWordLike(const int freq, int32_t* newWord, const int length,
678 short unsigned int* outWord, int* maxFreq) {
679 if (freq > *maxFreq) {
680 for (int q = 0; q < length; ++q)
681 outWord[q] = newWord[q];
682 outWord[length] = 0;
683 *maxFreq = freq;
684 }
685}
686
687// Will find the highest frequency of the words like the one passed as an argument,
688// that is, everything that only differs by case/accents.
689int UnigramDictionary::getMostFrequentWordLikeInner(const uint16_t * const inWord,
690 const int length, short unsigned int* outWord) {
691 int32_t newWord[MAX_WORD_LENGTH_INTERNAL];
692 int depth = 0;
693 int maxFreq = -1;
694 const uint8_t* const root = DICT_ROOT;
695
Jean Chalard4c0eca62012-01-16 15:15:53 +0900696 int startPos = 0;
697 mStackChildCount[0] = BinaryFormat::getGroupCountAndForwardPointer(root, &startPos);
Jean Chalard1059f272011-06-28 20:45:05 +0900698 mStackInputIndex[0] = 0;
Jean Chalard4c0eca62012-01-16 15:15:53 +0900699 mStackSiblingPos[0] = startPos;
Jean Chalard1059f272011-06-28 20:45:05 +0900700 while (depth >= 0) {
701 const int charGroupCount = mStackChildCount[depth];
702 int pos = mStackSiblingPos[depth];
703 for (int charGroupIndex = charGroupCount - 1; charGroupIndex >= 0; --charGroupIndex) {
704 int inputIndex = mStackInputIndex[depth];
705 const uint8_t flags = BinaryFormat::getFlagsAndForwardPointer(root, &pos);
706 // Test whether all chars in this group match with the word we are searching for. If so,
707 // we want to traverse its children (or if the length match, evaluate its frequency).
708 // Note that this function will output the position regardless, but will only write
709 // into inputIndex if there is a match.
710 const bool isAlike = testCharGroupForContinuedLikeness(flags, root, pos, inWord,
711 inputIndex, newWord, &inputIndex, &pos);
712 if (isAlike && (FLAG_IS_TERMINAL & flags) && (inputIndex == length)) {
713 const int frequency = BinaryFormat::readFrequencyWithoutMovingPointer(root, pos);
714 onTerminalWordLike(frequency, newWord, inputIndex, outWord, &maxFreq);
715 }
716 pos = BinaryFormat::skipFrequency(flags, pos);
717 const int siblingPos = BinaryFormat::skipChildrenPosAndAttributes(root, flags, pos);
718 const int childrenNodePos = BinaryFormat::readChildrenPosition(root, flags, pos);
719 // If we had a match and the word has children, we want to traverse them. We don't have
720 // to traverse words longer than the one we are searching for, since they will not match
721 // anyway, so don't traverse unless inputIndex < length.
722 if (isAlike && (-1 != childrenNodePos) && (inputIndex < length)) {
723 // Save position for this depth, to get back to this once children are done
724 mStackChildCount[depth] = charGroupIndex;
725 mStackSiblingPos[depth] = siblingPos;
726 // Prepare stack values for next depth
727 ++depth;
728 int childrenPos = childrenNodePos;
729 mStackChildCount[depth] =
730 BinaryFormat::getGroupCountAndForwardPointer(root, &childrenPos);
731 mStackSiblingPos[depth] = childrenPos;
732 mStackInputIndex[depth] = inputIndex;
733 pos = childrenPos;
734 // Go to the next depth level.
735 ++depth;
736 break;
737 } else {
738 // No match, or no children, or word too long to ever match: go the next sibling.
739 pos = siblingPos;
740 }
741 }
742 --depth;
743 }
744 return maxFreq;
745}
746
Jean Chalard522a04e2012-04-23 15:37:07 +0900747bool UnigramDictionary::isValidWord(const int32_t* const inWord, const int length) const {
Jean Chalard6a0e9642011-07-25 18:17:11 +0900748 return NOT_VALID_WORD != BinaryFormat::getTerminalPosition(DICT_ROOT, inWord, length);
Jean Chalard1059f272011-06-28 20:45:05 +0900749}
750
751// TODO: remove this function.
752int UnigramDictionary::getBigramPosition(int pos, unsigned short *word, int offset,
753 int length) const {
754 return -1;
755}
756
757// ProcessCurrentNode returns a boolean telling whether to traverse children nodes or not.
758// If the return value is false, then the caller should read in the output "nextSiblingPosition"
759// to find out the address of the next sibling node and pass it to a new call of processCurrentNode.
760// It is worthy to note that when false is returned, the output values other than
761// nextSiblingPosition are undefined.
762// If the return value is true, then the caller must proceed to traverse the children of this
763// node. processCurrentNode will output the information about the children: their count in
764// newCount, their position in newChildrenPosition, the traverseAllNodes flag in
765// newTraverseAllNodes, the match weight into newMatchRate, the input index into newInputIndex, the
766// diffs into newDiffs, the sibling position in nextSiblingPosition, and the output index into
767// newOutputIndex. Please also note the following caveat: processCurrentNode does not know when
768// there aren't any more nodes at this level, it merely returns the address of the first byte after
769// the current node in nextSiblingPosition. Thus, the caller must keep count of the nodes at any
770// given level, as output into newCount when traversing this level's parent.
satok8876b752011-08-04 18:31:57 +0900771inline bool UnigramDictionary::processCurrentNode(const int initialPos,
Jean Chalard8950ce62012-05-07 16:28:30 +0900772 const std::map<int, int> *bigramMap, const uint8_t *bigramFilter, Correction *correction,
773 int *newCount, int *newChildrenPosition, int *nextSiblingPosition,
774 WordsPriorityQueuePool *queuePool, const int currentWordIndex) {
Jean Chalard85a1d1e2011-06-21 22:23:21 +0900775 if (DEBUG_DICT) {
satokcfca3c62011-08-10 14:30:10 +0900776 correction->checkState();
Jean Chalard85a1d1e2011-06-21 22:23:21 +0900777 }
Jean Chalard0584f022011-06-30 19:23:16 +0900778 int pos = initialPos;
Jean Chalard0584f022011-06-30 19:23:16 +0900779
Jean Chalard1059f272011-06-28 20:45:05 +0900780 // Flags contain the following information:
781 // - Address type (MASK_GROUP_ADDRESS_TYPE) on two bits:
782 // - FLAG_GROUP_ADDRESS_TYPE_{ONE,TWO,THREE}_BYTES means there are children and their address
783 // is on the specified number of bytes.
784 // - FLAG_GROUP_ADDRESS_TYPE_NOADDRESS means there are no children, and therefore no address.
785 // - FLAG_HAS_MULTIPLE_CHARS: whether this node has multiple char or not.
786 // - FLAG_IS_TERMINAL: whether this node is a terminal or not (it may still have children)
787 // - FLAG_HAS_BIGRAMS: whether this node has bigrams or not
788 const uint8_t flags = BinaryFormat::getFlagsAndForwardPointer(DICT_ROOT, &pos);
789 const bool hasMultipleChars = (0 != (FLAG_HAS_MULTIPLE_CHARS & flags));
satok8876b752011-08-04 18:31:57 +0900790 const bool isTerminalNode = (0 != (FLAG_IS_TERMINAL & flags));
791
792 bool needsToInvokeOnTerminal = false;
Jean Chalard85a1d1e2011-06-21 22:23:21 +0900793
Jean Chalard1059f272011-06-28 20:45:05 +0900794 // This gets only ONE character from the stream. Next there will be:
795 // if FLAG_HAS_MULTIPLE CHARS: the other characters of the same node
796 // else if FLAG_IS_TERMINAL: the frequency
797 // else if MASK_GROUP_ADDRESS_TYPE is not NONE: the children address
798 // Note that you can't have a node that both is not a terminal and has no children.
799 int32_t c = BinaryFormat::getCharCodeAndForwardPointer(DICT_ROOT, &pos);
800 assert(NOT_A_CHARACTER != c);
Jean Chalard85a1d1e2011-06-21 22:23:21 +0900801
Jean Chalard1059f272011-06-28 20:45:05 +0900802 // We are going to loop through each character and make it look like it's a different
803 // node each time. To do that, we will process characters in this node in order until
804 // we find the character terminator. This is signalled by getCharCode* returning
805 // NOT_A_CHARACTER.
806 // As a special case, if there is only one character in this node, we must not read the
807 // next bytes so we will simulate the NOT_A_CHARACTER return by testing the flags.
808 // This way, each loop run will look like a "virtual node".
809 do {
810 // We prefetch the next char. If 'c' is the last char of this node, we will have
811 // NOT_A_CHARACTER in the next char. From this we can decide whether this virtual node
812 // should behave as a terminal or not and whether we have children.
813 const int32_t nextc = hasMultipleChars
814 ? BinaryFormat::getCharCodeAndForwardPointer(DICT_ROOT, &pos) : NOT_A_CHARACTER;
815 const bool isLastChar = (NOT_A_CHARACTER == nextc);
816 // If there are more chars in this nodes, then this virtual node is not a terminal.
817 // If we are on the last char, this virtual node is a terminal if this node is.
satok8876b752011-08-04 18:31:57 +0900818 const bool isTerminal = isLastChar && isTerminalNode;
Jean Chalard85a1d1e2011-06-21 22:23:21 +0900819
satokcfca3c62011-08-10 14:30:10 +0900820 Correction::CorrectionType stateType = correction->processCharAndCalcState(
satok8876b752011-08-04 18:31:57 +0900821 c, isTerminal);
satokcfca3c62011-08-10 14:30:10 +0900822 if (stateType == Correction::TRAVERSE_ALL_ON_TERMINAL
823 || stateType == Correction::ON_TERMINAL) {
satok8876b752011-08-04 18:31:57 +0900824 needsToInvokeOnTerminal = true;
satokd03317c2011-12-14 21:38:11 +0900825 } else if (stateType == Correction::UNRELATED || correction->needsToPrune()) {
satok8876b752011-08-04 18:31:57 +0900826 // We found that this is an unrelated character, so we should give up traversing
827 // this node and its children entirely.
828 // However we may not be on the last virtual node yet so we skip the remaining
829 // characters in this node, the frequency if it's there, read the next sibling
830 // position to output it, then return false.
831 // We don't have to output other values because we return false, as in
832 // "don't traverse children".
Jean Chalard1059f272011-06-28 20:45:05 +0900833 if (!isLastChar) {
834 pos = BinaryFormat::skipOtherCharacters(DICT_ROOT, pos);
835 }
836 pos = BinaryFormat::skipFrequency(flags, pos);
837 *nextSiblingPosition =
838 BinaryFormat::skipChildrenPosAndAttributes(DICT_ROOT, flags, pos);
839 return false;
Jean Chalard85a1d1e2011-06-21 22:23:21 +0900840 }
841
Jean Chalard1059f272011-06-28 20:45:05 +0900842 // Prepare for the next character. Promote the prefetched char to current char - the loop
843 // will take care of prefetching the next. If we finally found our last char, nextc will
844 // contain NOT_A_CHARACTER.
845 c = nextc;
Jean Chalard1059f272011-06-28 20:45:05 +0900846 } while (NOT_A_CHARACTER != c);
Jean Chalard85a1d1e2011-06-21 22:23:21 +0900847
satok8876b752011-08-04 18:31:57 +0900848 if (isTerminalNode) {
satok6ad15fc2012-01-16 16:21:21 +0900849 // The frequency should be here, because we come here only if this is actually
850 // a terminal node, and we are on its last char.
Jean Chalard171d1802012-04-23 18:51:00 +0900851 const int unigramFreq = BinaryFormat::readFrequencyWithoutMovingPointer(DICT_ROOT, pos);
satok6ad15fc2012-01-16 16:21:21 +0900852 const int childrenAddressPos = BinaryFormat::skipFrequency(flags, pos);
853 const int attributesPos = BinaryFormat::skipChildrenPosition(flags, childrenAddressPos);
854 TerminalAttributes terminalAttributes(DICT_ROOT, flags, attributesPos);
Jean Chalard8950ce62012-05-07 16:28:30 +0900855 // bigramMap contains the bigram frequencies indexed by addresses for fast lookup.
856 // bigramFilter is a bloom filter of said frequencies for even faster rejection.
Jean Chalard49ba1352012-05-07 20:14:00 +0900857 const int probability = BinaryFormat::getProbability(initialPos, bigramMap, bigramFilter,
858 unigramFreq);
Jean Chalard171d1802012-04-23 18:51:00 +0900859 onTerminal(probability, terminalAttributes, correction, queuePool, needsToInvokeOnTerminal,
satok8330b482012-01-23 16:52:37 +0900860 currentWordIndex);
Jean Chalard1059f272011-06-28 20:45:05 +0900861
satok8876b752011-08-04 18:31:57 +0900862 // If there are more chars in this node, then this virtual node has children.
863 // If we are on the last char, this virtual node has children if this node has.
864 const bool hasChildren = BinaryFormat::hasChildrenInFlags(flags);
865
866 // This character matched the typed character (enough to traverse the node at least)
867 // so we just evaluated it. Now we should evaluate this virtual node's children - that
868 // is, if it has any. If it has no children, we're done here - so we skip the end of
869 // the node, output the siblings position, and return false "don't traverse children".
870 // Note that !hasChildren implies isLastChar, so we know we don't have to skip any
871 // remaining char in this group for there can't be any.
872 if (!hasChildren) {
873 pos = BinaryFormat::skipFrequency(flags, pos);
874 *nextSiblingPosition =
875 BinaryFormat::skipChildrenPosAndAttributes(DICT_ROOT, flags, pos);
876 return false;
877 }
878
879 // Optimization: Prune out words that are too long compared to how much was typed.
satokcfca3c62011-08-10 14:30:10 +0900880 if (correction->needsToPrune()) {
satok8876b752011-08-04 18:31:57 +0900881 pos = BinaryFormat::skipFrequency(flags, pos);
882 *nextSiblingPosition =
883 BinaryFormat::skipChildrenPosAndAttributes(DICT_ROOT, flags, pos);
satok10266c02011-08-19 22:05:59 +0900884 if (DEBUG_DICT_FULL) {
satok9fb6f472012-01-13 18:01:22 +0900885 AKLOGI("Traversing was pruned.");
satok10266c02011-08-19 22:05:59 +0900886 }
satok8876b752011-08-04 18:31:57 +0900887 return false;
888 }
889 }
Jean Chalard1059f272011-06-28 20:45:05 +0900890
891 // Now we finished processing this node, and we want to traverse children. If there are no
892 // children, we can't come here.
893 assert(BinaryFormat::hasChildrenInFlags(flags));
894
895 // If this node was a terminal it still has the frequency under the pointer (it may have been
896 // read, but not skipped - see readFrequencyWithoutMovingPointer).
897 // Next come the children position, then possibly attributes (attributes are bigrams only for
898 // now, maybe something related to shortcuts in the future).
899 // Once this is read, we still need to output the number of nodes in the immediate children of
900 // this node, so we read and output it before returning true, as in "please traverse children".
901 pos = BinaryFormat::skipFrequency(flags, pos);
902 int childrenPos = BinaryFormat::readChildrenPosition(DICT_ROOT, flags, pos);
903 *nextSiblingPosition = BinaryFormat::skipChildrenPosAndAttributes(DICT_ROOT, flags, pos);
904 *newCount = BinaryFormat::getGroupCountAndForwardPointer(DICT_ROOT, &childrenPos);
905 *newChildrenPosition = childrenPos;
906 return true;
Jean Chalard85a1d1e2011-06-21 22:23:21 +0900907}
908
satok30088252010-12-01 21:22:15 +0900909} // namespace latinime