diff options
Diffstat (limited to 'native/src')
| -rw-r--r-- | native/src/bigram_dictionary.cpp | 265 | ||||
| -rw-r--r-- | native/src/bigram_dictionary.h | 56 | ||||
| -rw-r--r-- | native/src/char_utils.h | 2 | ||||
| -rw-r--r-- | native/src/debug.h | 72 | ||||
| -rw-r--r-- | native/src/defines.h | 170 | ||||
| -rw-r--r-- | native/src/dictionary.cpp | 586 | ||||
| -rw-r--r-- | native/src/dictionary.h | 199 | ||||
| -rw-r--r-- | native/src/proximity_info.cpp | 66 | ||||
| -rw-r--r-- | native/src/proximity_info.h | 47 | ||||
| -rw-r--r-- | native/src/unigram_dictionary.cpp | 1127 | ||||
| -rw-r--r-- | native/src/unigram_dictionary.h | 152 |
11 files changed, 2112 insertions, 630 deletions
diff --git a/native/src/bigram_dictionary.cpp b/native/src/bigram_dictionary.cpp new file mode 100644 index 000000000..11e6dc250 --- /dev/null +++ b/native/src/bigram_dictionary.cpp @@ -0,0 +1,265 @@ +/* +** +** Copyright 2010, The Android Open Source Project +** +** Licensed under the Apache License, Version 2.0 (the "License"); +** you may not use this file except in compliance with the License. +** You may obtain a copy of the License at +** +** http://www.apache.org/licenses/LICENSE-2.0 +** +** Unless required by applicable law or agreed to in writing, software +** distributed under the License is distributed on an "AS IS" BASIS, +** WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. +** See the License for the specific language governing permissions and +** limitations under the License. +*/ + +#include <string.h> + +#define LOG_TAG "LatinIME: bigram_dictionary.cpp" + +#include "bigram_dictionary.h" +#include "dictionary.h" + +namespace latinime { + +BigramDictionary::BigramDictionary(const unsigned char *dict, int maxWordLength, + int maxAlternatives, const bool isLatestDictVersion, const bool hasBigram, + Dictionary *parentDictionary) + : DICT(dict), MAX_WORD_LENGTH(maxWordLength), + MAX_ALTERNATIVES(maxAlternatives), IS_LATEST_DICT_VERSION(isLatestDictVersion), + HAS_BIGRAM(hasBigram), mParentDictionary(parentDictionary) { + if (DEBUG_DICT) { + LOGI("BigramDictionary - constructor"); + LOGI("Has Bigram : %d", hasBigram); + } +} + +BigramDictionary::~BigramDictionary() { +} + +bool BigramDictionary::addWordBigram(unsigned short *word, int length, int frequency) { + word[length] = 0; + if (DEBUG_DICT) { + char s[length + 1]; + for (int i = 0; i <= length; i++) s[i] = word[i]; + LOGI("Bigram: Found word = %s, freq = %d :", s, frequency); + } + + // Find the right insertion point + int insertAt = 0; + while (insertAt < mMaxBigrams) { + if (frequency > mBigramFreq[insertAt] || (mBigramFreq[insertAt] == frequency + && length < Dictionary::wideStrLen(mBigramChars + insertAt * MAX_WORD_LENGTH))) { + break; + } + insertAt++; + } + if (DEBUG_DICT) { + LOGI("Bigram: InsertAt -> %d maxBigrams: %d", insertAt, mMaxBigrams); + } + if (insertAt < mMaxBigrams) { + memmove((char*) mBigramFreq + (insertAt + 1) * sizeof(mBigramFreq[0]), + (char*) mBigramFreq + insertAt * sizeof(mBigramFreq[0]), + (mMaxBigrams - insertAt - 1) * sizeof(mBigramFreq[0])); + mBigramFreq[insertAt] = frequency; + memmove((char*) mBigramChars + (insertAt + 1) * MAX_WORD_LENGTH * sizeof(short), + (char*) mBigramChars + (insertAt ) * MAX_WORD_LENGTH * sizeof(short), + (mMaxBigrams - insertAt - 1) * sizeof(short) * MAX_WORD_LENGTH); + unsigned short *dest = mBigramChars + (insertAt ) * MAX_WORD_LENGTH; + while (length--) { + *dest++ = *word++; + } + *dest = 0; // NULL terminate + if (DEBUG_DICT) { + LOGI("Bigram: Added word at %d", insertAt); + } + return true; + } + return false; +} + +int BigramDictionary::getBigramAddress(int *pos, bool advance) { + int address = 0; + + address += (DICT[*pos] & 0x3F) << 16; + address += (DICT[*pos + 1] & 0xFF) << 8; + address += (DICT[*pos + 2] & 0xFF); + + if (advance) { + *pos += 3; + } + + return address; +} + +int BigramDictionary::getBigramFreq(int *pos) { + int freq = DICT[(*pos)++] & FLAG_BIGRAM_FREQ; + + return freq; +} + + +int BigramDictionary::getBigrams(unsigned short *prevWord, int prevWordLength, int *codes, + int codesSize, unsigned short *bigramChars, int *bigramFreq, int maxWordLength, + int maxBigrams, int maxAlternatives) { + mBigramFreq = bigramFreq; + mBigramChars = bigramChars; + mInputCodes = codes; + mInputLength = codesSize; + mMaxBigrams = maxBigrams; + + if (HAS_BIGRAM && IS_LATEST_DICT_VERSION) { + int pos = mParentDictionary->getBigramPosition(prevWord, prevWordLength); + if (DEBUG_DICT) { + LOGI("Pos -> %d", pos); + } + if (pos < 0) { + return 0; + } + + int bigramCount = 0; + int bigramExist = (DICT[pos] & FLAG_BIGRAM_READ); + if (bigramExist > 0) { + int nextBigramExist = 1; + while (nextBigramExist > 0 && bigramCount < maxBigrams) { + int bigramAddress = getBigramAddress(&pos, true); + int frequency = (FLAG_BIGRAM_FREQ & DICT[pos]); + // search for all bigrams and store them + searchForTerminalNode(bigramAddress, frequency); + nextBigramExist = (DICT[pos++] & FLAG_BIGRAM_CONTINUED); + bigramCount++; + } + } + + return bigramCount; + } + return 0; +} + +void BigramDictionary::searchForTerminalNode(int addressLookingFor, int frequency) { + // track word with such address and store it in an array + unsigned short word[MAX_WORD_LENGTH]; + + int pos; + int followDownBranchAddress = DICTIONARY_HEADER_SIZE; + bool found = false; + char followingChar = ' '; + int depth = -1; + + while(!found) { + bool followDownAddressSearchStop = false; + bool firstAddress = true; + bool haveToSearchAll = true; + + if (depth < MAX_WORD_LENGTH && depth >= 0) { + word[depth] = (unsigned short) followingChar; + } + pos = followDownBranchAddress; // pos start at count + int count = DICT[pos] & 0xFF; + if (DEBUG_DICT) { + LOGI("count - %d",count); + } + pos++; + for (int i = 0; i < count; i++) { + // pos at data + pos++; + // pos now at flag + if (!getFirstBitOfByte(&pos)) { // non-terminal + if (!followDownAddressSearchStop) { + int addr = getBigramAddress(&pos, false); + if (addr > addressLookingFor) { + followDownAddressSearchStop = true; + if (firstAddress) { + firstAddress = false; + haveToSearchAll = true; + } else if (!haveToSearchAll) { + break; + } + } else { + followDownBranchAddress = addr; + followingChar = (char)(0xFF & DICT[pos-1]); + if (firstAddress) { + firstAddress = false; + haveToSearchAll = false; + } + } + } + pos += 3; + } else if (getFirstBitOfByte(&pos)) { // terminal + if (addressLookingFor == (pos-1)) { // found !! + depth++; + word[depth] = (0xFF & DICT[pos-1]); + found = true; + break; + } + if (getSecondBitOfByte(&pos)) { // address + freq (4 byte) + if (!followDownAddressSearchStop) { + int addr = getBigramAddress(&pos, false); + if (addr > addressLookingFor) { + followDownAddressSearchStop = true; + if (firstAddress) { + firstAddress = false; + haveToSearchAll = true; + } else if (!haveToSearchAll) { + break; + } + } else { + followDownBranchAddress = addr; + followingChar = (char)(0xFF & DICT[pos-1]); + if (firstAddress) { + firstAddress = false; + haveToSearchAll = true; + } + } + } + pos += 4; + } else { // freq only (2 byte) + pos += 2; + } + + // skipping bigram + int bigramExist = (DICT[pos] & FLAG_BIGRAM_READ); + if (bigramExist > 0) { + int nextBigramExist = 1; + while (nextBigramExist > 0) { + pos += 3; + nextBigramExist = (DICT[pos++] & FLAG_BIGRAM_CONTINUED); + } + } else { + pos++; + } + } + } + depth++; + if (followDownBranchAddress == 0) { + if (DEBUG_DICT) { + LOGI("ERROR!!! Cannot find bigram!!"); + } + break; + } + } + if (checkFirstCharacter(word)) { + addWordBigram(word, depth, frequency); + } +} + +bool BigramDictionary::checkFirstCharacter(unsigned short *word) { + // Checks whether this word starts with same character or neighboring characters of + // what user typed. + + int *inputCodes = mInputCodes; + int maxAlt = MAX_ALTERNATIVES; + while (maxAlt > 0) { + if ((unsigned int) *inputCodes == (unsigned int) *word) { + return true; + } + inputCodes++; + maxAlt--; + } + return false; +} + +// TODO: Move functions related to bigram to here +} // namespace latinime diff --git a/native/src/bigram_dictionary.h b/native/src/bigram_dictionary.h new file mode 100644 index 000000000..c07458a38 --- /dev/null +++ b/native/src/bigram_dictionary.h @@ -0,0 +1,56 @@ +/* + * Copyright (C) 2010 The Android Open Source Project + * + * Licensed under the Apache License, Version 2.0 (the "License"); + * you may not use this file except in compliance with the License. + * You may obtain a copy of the License at + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + * See the License for the specific language governing permissions and + * limitations under the License. + */ + +#ifndef LATINIME_BIGRAM_DICTIONARY_H +#define LATINIME_BIGRAM_DICTIONARY_H + +namespace latinime { + +class Dictionary; +class BigramDictionary { +public: + BigramDictionary(const unsigned char *dict, int maxWordLength, int maxAlternatives, + const bool isLatestDictVersion, const bool hasBigram, Dictionary *parentDictionary); + int getBigrams(unsigned short *word, int length, int *codes, int codesSize, + unsigned short *outWords, int *frequencies, int maxWordLength, int maxBigrams, + int maxAlternatives); + ~BigramDictionary(); +private: + bool addWordBigram(unsigned short *word, int length, int frequency); + int getBigramAddress(int *pos, bool advance); + int getBigramFreq(int *pos); + void searchForTerminalNode(int addressLookingFor, int frequency); + bool getFirstBitOfByte(int *pos) { return (DICT[*pos] & 0x80) > 0; } + bool getSecondBitOfByte(int *pos) { return (DICT[*pos] & 0x40) > 0; } + bool checkFirstCharacter(unsigned short *word); + + const unsigned char *DICT; + const int MAX_WORD_LENGTH; + const int MAX_ALTERNATIVES; + const bool IS_LATEST_DICT_VERSION; + const bool HAS_BIGRAM; + + Dictionary *mParentDictionary; + int *mBigramFreq; + int mMaxBigrams; + unsigned short *mBigramChars; + int *mInputCodes; + int mInputLength; +}; + +} // namespace latinime + +#endif // LATINIME_BIGRAM_DICTIONARY_H diff --git a/native/src/char_utils.h b/native/src/char_utils.h index 921ecb4a5..a69a35e7a 100644 --- a/native/src/char_utils.h +++ b/native/src/char_utils.h @@ -21,6 +21,6 @@ namespace latinime { unsigned short latin_tolower(unsigned short c); -}; // namespace latinime +} // namespace latinime #endif // LATINIME_CHAR_UTILS_H diff --git a/native/src/debug.h b/native/src/debug.h new file mode 100644 index 000000000..38b2f107a --- /dev/null +++ b/native/src/debug.h @@ -0,0 +1,72 @@ +/* +** +** Copyright 2011, The Android Open Source Project +** +** Licensed under the Apache License, Version 2.0 (the "License"); +** you may not use this file except in compliance with the License. +** You may obtain a copy of the License at +** +** http://www.apache.org/licenses/LICENSE-2.0 +** +** Unless required by applicable law or agreed to in writing, software +** distributed under the License is distributed on an "AS IS" BASIS, +** WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. +** See the License for the specific language governing permissions and +** limitations under the License. +*/ + +#ifndef LATINIME_DEBUG_H +#define LATINIME_DEBUG_H + +#include "defines.h" + +static inline unsigned char* convertToUnibyteString(unsigned short* input, unsigned char* output, + const unsigned int length) { + int i = 0; + for (; i <= length && input[i] != 0; ++i) + output[i] = input[i] & 0xFF; + output[i] = 0; + return output; +} + +static inline unsigned char* convertToUnibyteStringAndReplaceLastChar(unsigned short* input, + unsigned char* output, const unsigned int length, unsigned char c) { + int i = 0; + for (; i <= length && input[i] != 0; ++i) + output[i] = input[i] & 0xFF; + output[i-1] = c; + output[i] = 0; + return output; +} + +static inline void LOGI_S16(unsigned short* string, const unsigned int length) { + unsigned char tmp_buffer[length]; + convertToUnibyteString(string, tmp_buffer, length); + LOGI(">> %s", tmp_buffer); + // The log facility is throwing out log that comes too fast. The following + // is a dirty way of slowing down processing so that we can see all log. + // TODO : refactor this in a blocking log or something. + // usleep(10); +} + +static inline void LOGI_S16_PLUS(unsigned short* string, const unsigned int length, + unsigned char c) { + unsigned char tmp_buffer[length+1]; + convertToUnibyteStringAndReplaceLastChar(string, tmp_buffer, length, c); + LOGI(">> %s", tmp_buffer); + // Likewise + // usleep(10); +} + +static inline void printDebug(const char* tag, int* codes, int codesSize, int MAX_PROXIMITY_CHARS) { + unsigned char *buf = (unsigned char*)malloc((1 + codesSize) * sizeof(*buf)); + + buf[codesSize] = 0; + while (--codesSize >= 0) + buf[codesSize] = (unsigned char)codes[codesSize * MAX_PROXIMITY_CHARS]; + LOGI("%s, WORD = %s", tag, buf); + + free(buf); +} + +#endif // LATINIME_DEBUG_H diff --git a/native/src/defines.h b/native/src/defines.h new file mode 100644 index 000000000..0a3240507 --- /dev/null +++ b/native/src/defines.h @@ -0,0 +1,170 @@ +/* +** +** Copyright 2010, The Android Open Source Project +** +** Licensed under the Apache License, Version 2.0 (the "License"); +** you may not use this file except in compliance with the License. +** You may obtain a copy of the License at +** +** http://www.apache.org/licenses/LICENSE-2.0 +** +** Unless required by applicable law or agreed to in writing, software +** distributed under the License is distributed on an "AS IS" BASIS, +** WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. +** See the License for the specific language governing permissions and +** limitations under the License. +*/ + +#ifndef LATINIME_DEFINES_H +#define LATINIME_DEFINES_H + +#ifdef FLAG_DBG +#include <cutils/log.h> +#ifndef LOG_TAG +#define LOG_TAG "LatinIME: " +#endif +#define DEBUG_DICT true +#define DEBUG_DICT_FULL false +#define DEBUG_SHOW_FOUND_WORD DEBUG_DICT_FULL +#define DEBUG_NODE DEBUG_DICT_FULL +#define DEBUG_TRACE DEBUG_DICT_FULL +#define DEBUG_PROXIMITY_INFO true + +// Profiler +#include <time.h> +#define PROF_BUF_SIZE 100 +static double profile_buf[PROF_BUF_SIZE]; +static double profile_old[PROF_BUF_SIZE]; +static unsigned int profile_counter[PROF_BUF_SIZE]; + +#define PROF_RESET prof_reset() +#define PROF_COUNT(prof_buf_id) ++profile_counter[prof_buf_id] +#define PROF_OPEN do { PROF_RESET; PROF_START(PROF_BUF_SIZE - 1); } while(0) +#define PROF_START(prof_buf_id) do { \ + PROF_COUNT(prof_buf_id); profile_old[prof_buf_id] = (clock()); } while(0) +#define PROF_CLOSE do { PROF_END(PROF_BUF_SIZE - 1); PROF_OUTALL; } while(0) +#define PROF_END(prof_buf_id) profile_buf[prof_buf_id] += ((clock()) - profile_old[prof_buf_id]) +#define PROF_CLOCKOUT(prof_buf_id) \ + LOGI("%s : clock is %f", __FUNCTION__, (clock() - profile_old[prof_buf_id])) +#define PROF_OUTALL do { LOGI("--- %s ---", __FUNCTION__); prof_out(); } while(0) + +static void prof_reset(void) { + for (int i = 0; i < PROF_BUF_SIZE; ++i) { + profile_buf[i] = 0; + profile_old[i] = 0; + profile_counter[i] = 0; + } +} + +static void prof_out(void) { + if (profile_counter[PROF_BUF_SIZE - 1] != 1) { + LOGI("Error: You must call PROF_OPEN before PROF_CLOSE."); + } + LOGI("Total time is %6.3f ms.", + profile_buf[PROF_BUF_SIZE - 1] * 1000 / (double)CLOCKS_PER_SEC); + double all = 0; + for (int i = 0; i < PROF_BUF_SIZE - 1; ++i) { + all += profile_buf[i]; + } + if (all == 0) all = 1; + for (int i = 0; i < PROF_BUF_SIZE - 1; ++i) { + if (profile_buf[i] != 0) { + LOGI("(%d): Used %4.2f%%, %8.4f ms. Called %d times.", + i, (profile_buf[i] * 100 / all), + profile_buf[i] * 1000 / (double)CLOCKS_PER_SEC, profile_counter[i]); + } + } +} + +#else // FLAG_DBG +#define LOGE(fmt, ...) +#define LOGI(fmt, ...) +#define DEBUG_DICT false +#define DEBUG_DICT_FULL false +#define DEBUG_SHOW_FOUND_WORD false +#define DEBUG_NODE false +#define DEBUG_TRACE false +#define DEBUG_PROXIMITY_INFO false + +#define PROF_BUF_SIZE 0 +#define PROF_RESET +#define PROF_COUNT(prof_buf_id) +#define PROF_OPEN +#define PROF_START(prof_buf_id) +#define PROF_CLOSE +#define PROF_END(prof_buf_id) +#define PROF_CLOCK_OUT(prof_buf_id) +#define PROF_CLOCKOUT(prof_buf_id) +#define PROF_OUTALL + +#endif // FLAG_DBG + +#ifndef U_SHORT_MAX +#define U_SHORT_MAX 1 << 16 +#endif +#ifndef S_INT_MAX +#define S_INT_MAX 2147483647 // ((1 << 31) - 1) +#endif + +// Define this to use mmap() for dictionary loading. Undefine to use malloc() instead of mmap(). +// We measured and compared performance of both, and found mmap() is fairly good in terms of +// loading time, and acceptable even for several initial lookups which involve page faults. +#define USE_MMAP_FOR_DICTIONARY + +// 22-bit address = ~4MB dictionary size limit, which on average would be about 200k-300k words +#define ADDRESS_MASK 0x3FFFFF + +// The bit that decides if an address follows in the next 22 bits +#define FLAG_ADDRESS_MASK 0x40 +// The bit that decides if this is a terminal node for a word. The node could still have children, +// if the word has other endings. +#define FLAG_TERMINAL_MASK 0x80 + +#define FLAG_BIGRAM_READ 0x80 +#define FLAG_BIGRAM_CHILDEXIST 0x40 +#define FLAG_BIGRAM_CONTINUED 0x80 +#define FLAG_BIGRAM_FREQ 0x7F + +#define DICTIONARY_VERSION_MIN 200 +#define DICTIONARY_HEADER_SIZE 2 +#define NOT_VALID_WORD -99 + +#define KEYCODE_SPACE ' ' + +#define SUGGEST_WORDS_WITH_MISSING_CHARACTER true +#define SUGGEST_WORDS_WITH_MISSING_SPACE_CHARACTER true +#define SUGGEST_WORDS_WITH_EXCESSIVE_CHARACTER true +#define SUGGEST_WORDS_WITH_TRANSPOSED_CHARACTERS true +#define SUGGEST_WORDS_WITH_SPACE_PROXIMITY true + +// The following "rate"s are used as a multiplier before dividing by 100, so they are in percent. +#define WORDS_WITH_MISSING_CHARACTER_DEMOTION_RATE 80 +#define WORDS_WITH_MISSING_CHARACTER_DEMOTION_START_POS_10X 12 +#define WORDS_WITH_MISSING_SPACE_CHARACTER_DEMOTION_RATE 67 +#define WORDS_WITH_EXCESSIVE_CHARACTER_DEMOTION_RATE 75 +#define WORDS_WITH_EXCESSIVE_CHARACTER_OUT_OF_PROXIMITY_DEMOTION_RATE 75 +#define WORDS_WITH_TRANSPOSED_CHARACTERS_DEMOTION_RATE 60 +#define FULL_MATCHED_WORDS_PROMOTION_RATE 120 +#define WORDS_WITH_PROXIMITY_CHARACTER_DEMOTION_RATE 90 + +// This should be greater than or equal to MAX_WORD_LENGTH defined in BinaryDictionary.java +// This is only used for the size of array. Not to be used in c functions. +#define MAX_WORD_LENGTH_INTERNAL 48 + +#define MAX_DEPTH_MULTIPLIER 3 + +// TODO: Reduce this constant if possible; check the maximum number of umlauts in the same German +// word in the dictionary +#define DEFAULT_MAX_UMLAUT_SEARCH_DEPTH 5 + +// Minimum suggest depth for one word for all cases except for missing space suggestions. +#define MIN_SUGGEST_DEPTH 1 +#define MIN_USER_TYPED_LENGTH_FOR_MISSING_SPACE_SUGGESTION 3 +#define MIN_USER_TYPED_LENGTH_FOR_EXCESSIVE_CHARACTER_SUGGESTION 3 + +// The size of next letters frequency array. Zero will disable the feature. +#define NEXT_LETTERS_SIZE 0 + +#define min(a,b) ((a)<(b)?(a):(b)) + +#endif // LATINIME_DEFINES_H diff --git a/native/src/dictionary.cpp b/native/src/dictionary.cpp index 1a39f585b4..9e32ee80f 100644 --- a/native/src/dictionary.cpp +++ b/native/src/dictionary.cpp @@ -16,581 +16,53 @@ */ #include <stdio.h> -#include <fcntl.h> -#include <sys/mman.h> -#include <string.h> -//#define LOG_TAG "dictionary.cpp" -//#include <cutils/log.h> -#define LOGI -#include "dictionary.h" -#include "basechars.h" -#include "char_utils.h" +#define LOG_TAG "LatinIME: dictionary.cpp" -#define DEBUG_DICT 0 -#define DICTIONARY_VERSION_MIN 200 -#define DICTIONARY_HEADER_SIZE 2 -#define NOT_VALID_WORD -99 +#include "dictionary.h" namespace latinime { -Dictionary::Dictionary(void *dict, int typedLetterMultiplier, int fullWordMultiplier) -{ - mDict = (unsigned char*) dict; - mTypedLetterMultiplier = typedLetterMultiplier; - mFullWordMultiplier = fullWordMultiplier; - getVersionNumber(); -} - -Dictionary::~Dictionary() -{ -} - -int Dictionary::getSuggestions(int *codes, int codesSize, unsigned short *outWords, int *frequencies, - int maxWordLength, int maxWords, int maxAlternatives, int skipPos, - int *nextLetters, int nextLettersSize) -{ - int suggWords; - mFrequencies = frequencies; - mOutputChars = outWords; - mInputCodes = codes; - mInputLength = codesSize; - mMaxAlternatives = maxAlternatives; - mMaxWordLength = maxWordLength; - mMaxWords = maxWords; - mSkipPos = skipPos; - mMaxEditDistance = mInputLength < 5 ? 2 : mInputLength / 2; - mNextLettersFrequencies = nextLetters; - mNextLettersSize = nextLettersSize; - - if (checkIfDictVersionIsLatest()) { - getWordsRec(DICTIONARY_HEADER_SIZE, 0, mInputLength * 3, false, 1, 0, 0); - } else { - getWordsRec(0, 0, mInputLength * 3, false, 1, 0, 0); - } - - // Get the word count - suggWords = 0; - while (suggWords < mMaxWords && mFrequencies[suggWords] > 0) suggWords++; - if (DEBUG_DICT) LOGI("Returning %d words", suggWords); - +// TODO: Change the type of all keyCodes to uint32_t +Dictionary::Dictionary(void *dict, int dictSize, int mmapFd, int dictBufAdjust, + int typedLetterMultiplier, int fullWordMultiplier, + int maxWordLength, int maxWords, int maxAlternatives) + : mDict((unsigned char*) dict), mDictSize(dictSize), + mMmapFd(mmapFd), mDictBufAdjust(dictBufAdjust), + // Checks whether it has the latest dictionary or the old dictionary + IS_LATEST_DICT_VERSION((((unsigned char*) dict)[0] & 0xFF) >= DICTIONARY_VERSION_MIN) { if (DEBUG_DICT) { - LOGI("Next letters: "); - for (int k = 0; k < nextLettersSize; k++) { - if (mNextLettersFrequencies[k] > 0) { - LOGI("%c = %d,", k, mNextLettersFrequencies[k]); - } - } - LOGI("\n"); - } - return suggWords; -} - -void -Dictionary::registerNextLetter(unsigned short c) -{ - if (c < mNextLettersSize) { - mNextLettersFrequencies[c]++; - } -} - -void -Dictionary::getVersionNumber() -{ - mVersion = (mDict[0] & 0xFF); - mBigram = (mDict[1] & 0xFF); - LOGI("IN NATIVE SUGGEST Version: %d Bigram : %d \n", mVersion, mBigram); -} - -// Checks whether it has the latest dictionary or the old dictionary -bool -Dictionary::checkIfDictVersionIsLatest() -{ - return (mVersion >= DICTIONARY_VERSION_MIN) && (mBigram == 1 || mBigram == 0); -} - -unsigned short -Dictionary::getChar(int *pos) -{ - unsigned short ch = (unsigned short) (mDict[(*pos)++] & 0xFF); - // If the code is 255, then actual 16 bit code follows (in big endian) - if (ch == 0xFF) { - ch = ((mDict[*pos] & 0xFF) << 8) | (mDict[*pos + 1] & 0xFF); - (*pos) += 2; - } - return ch; -} - -int -Dictionary::getAddress(int *pos) -{ - int address = 0; - if ((mDict[*pos] & FLAG_ADDRESS_MASK) == 0) { - *pos += 1; - } else { - address += (mDict[*pos] & (ADDRESS_MASK >> 16)) << 16; - address += (mDict[*pos + 1] & 0xFF) << 8; - address += (mDict[*pos + 2] & 0xFF); - *pos += 3; - } - return address; -} - -int -Dictionary::getFreq(int *pos) -{ - int freq = mDict[(*pos)++] & 0xFF; - - if (checkIfDictVersionIsLatest()) { - // skipping bigram - int bigramExist = (mDict[*pos] & FLAG_BIGRAM_READ); - if (bigramExist > 0) { - int nextBigramExist = 1; - while (nextBigramExist > 0) { - (*pos) += 3; - nextBigramExist = (mDict[(*pos)++] & FLAG_BIGRAM_CONTINUED); - } - } else { - (*pos)++; - } - } - - return freq; -} - -int -Dictionary::wideStrLen(unsigned short *str) -{ - if (!str) return 0; - unsigned short *end = str; - while (*end) - end++; - return end - str; -} - -bool -Dictionary::addWord(unsigned short *word, int length, int frequency) -{ - word[length] = 0; - if (DEBUG_DICT) { - char s[length + 1]; - for (int i = 0; i <= length; i++) s[i] = word[i]; - LOGI("Found word = %s, freq = %d : \n", s, frequency); - } - - // Find the right insertion point - int insertAt = 0; - while (insertAt < mMaxWords) { - if (frequency > mFrequencies[insertAt] - || (mFrequencies[insertAt] == frequency - && length < wideStrLen(mOutputChars + insertAt * mMaxWordLength))) { - break; - } - insertAt++; - } - if (insertAt < mMaxWords) { - memmove((char*) mFrequencies + (insertAt + 1) * sizeof(mFrequencies[0]), - (char*) mFrequencies + insertAt * sizeof(mFrequencies[0]), - (mMaxWords - insertAt - 1) * sizeof(mFrequencies[0])); - mFrequencies[insertAt] = frequency; - memmove((char*) mOutputChars + (insertAt + 1) * mMaxWordLength * sizeof(short), - (char*) mOutputChars + (insertAt ) * mMaxWordLength * sizeof(short), - (mMaxWords - insertAt - 1) * sizeof(short) * mMaxWordLength); - unsigned short *dest = mOutputChars + (insertAt ) * mMaxWordLength; - while (length--) { - *dest++ = *word++; - } - *dest = 0; // NULL terminate - if (DEBUG_DICT) LOGI("Added word at %d\n", insertAt); - return true; - } - return false; -} - -bool -Dictionary::addWordBigram(unsigned short *word, int length, int frequency) -{ - word[length] = 0; - if (DEBUG_DICT) { - char s[length + 1]; - for (int i = 0; i <= length; i++) s[i] = word[i]; - LOGI("Bigram: Found word = %s, freq = %d : \n", s, frequency); - } - - // Find the right insertion point - int insertAt = 0; - while (insertAt < mMaxBigrams) { - if (frequency > mBigramFreq[insertAt] - || (mBigramFreq[insertAt] == frequency - && length < wideStrLen(mBigramChars + insertAt * mMaxWordLength))) { - break; - } - insertAt++; - } - LOGI("Bigram: InsertAt -> %d maxBigrams: %d\n", insertAt, mMaxBigrams); - if (insertAt < mMaxBigrams) { - memmove((char*) mBigramFreq + (insertAt + 1) * sizeof(mBigramFreq[0]), - (char*) mBigramFreq + insertAt * sizeof(mBigramFreq[0]), - (mMaxBigrams - insertAt - 1) * sizeof(mBigramFreq[0])); - mBigramFreq[insertAt] = frequency; - memmove((char*) mBigramChars + (insertAt + 1) * mMaxWordLength * sizeof(short), - (char*) mBigramChars + (insertAt ) * mMaxWordLength * sizeof(short), - (mMaxBigrams - insertAt - 1) * sizeof(short) * mMaxWordLength); - unsigned short *dest = mBigramChars + (insertAt ) * mMaxWordLength; - while (length--) { - *dest++ = *word++; - } - *dest = 0; // NULL terminate - if (DEBUG_DICT) LOGI("Bigram: Added word at %d\n", insertAt); - return true; - } - return false; -} - -unsigned short -Dictionary::toLowerCase(unsigned short c) { - if (c < sizeof(BASE_CHARS) / sizeof(BASE_CHARS[0])) { - c = BASE_CHARS[c]; - } - if (c >='A' && c <= 'Z') { - c |= 32; - } else if (c > 127) { - c = latin_tolower(c); - } - return c; -} - -bool -Dictionary::sameAsTyped(unsigned short *word, int length) -{ - if (length != mInputLength) { - return false; - } - int *inputCodes = mInputCodes; - while (length--) { - if ((unsigned int) *inputCodes != (unsigned int) *word) { - return false; + if (MAX_WORD_LENGTH_INTERNAL < maxWordLength) { + LOGI("Max word length (%d) is greater than %d", + maxWordLength, MAX_WORD_LENGTH_INTERNAL); + LOGI("IN NATIVE SUGGEST Version: %d", (mDict[0] & 0xFF)); } - inputCodes += mMaxAlternatives; - word++; } - return true; + mUnigramDictionary = new UnigramDictionary(mDict, typedLetterMultiplier, fullWordMultiplier, + maxWordLength, maxWords, maxAlternatives, IS_LATEST_DICT_VERSION); + mBigramDictionary = new BigramDictionary(mDict, maxWordLength, maxAlternatives, + IS_LATEST_DICT_VERSION, hasBigram(), this); } -static char QUOTE = '\''; - -void -Dictionary::getWordsRec(int pos, int depth, int maxDepth, bool completion, int snr, int inputIndex, - int diffs) -{ - // Optimization: Prune out words that are too long compared to how much was typed. - if (depth > maxDepth) { - return; - } - if (diffs > mMaxEditDistance) { - return; - } - int count = getCount(&pos); - int *currentChars = NULL; - if (mInputLength <= inputIndex) { - completion = true; - } else { - currentChars = mInputCodes + (inputIndex * mMaxAlternatives); - } - - for (int i = 0; i < count; i++) { - // -- at char - unsigned short c = getChar(&pos); - // -- at flag/add - unsigned short lowerC = toLowerCase(c); - bool terminal = getTerminal(&pos); - int childrenAddress = getAddress(&pos); - // -- after address or flag - int freq = 1; - if (terminal) freq = getFreq(&pos); - // -- after add or freq - - // If we are only doing completions, no need to look at the typed characters. - if (completion) { - mWord[depth] = c; - if (terminal) { - addWord(mWord, depth + 1, freq * snr); - if (depth >= mInputLength && mSkipPos < 0) { - registerNextLetter(mWord[mInputLength]); - } - } - if (childrenAddress != 0) { - getWordsRec(childrenAddress, depth + 1, maxDepth, - completion, snr, inputIndex, diffs); - } - } else if ((c == QUOTE && currentChars[0] != QUOTE) || mSkipPos == depth) { - // Skip the ' or other letter and continue deeper - mWord[depth] = c; - if (childrenAddress != 0) { - getWordsRec(childrenAddress, depth + 1, maxDepth, false, snr, inputIndex, diffs); - } - } else { - int j = 0; - while (currentChars[j] > 0) { - if (currentChars[j] == lowerC || currentChars[j] == c) { - int addedWeight = j == 0 ? mTypedLetterMultiplier : 1; - mWord[depth] = c; - if (mInputLength == inputIndex + 1) { - if (terminal) { - if (//INCLUDE_TYPED_WORD_IF_VALID || - !sameAsTyped(mWord, depth + 1)) { - int finalFreq = freq * snr * addedWeight; - if (mSkipPos < 0) finalFreq *= mFullWordMultiplier; - addWord(mWord, depth + 1, finalFreq); - } - } - if (childrenAddress != 0) { - getWordsRec(childrenAddress, depth + 1, - maxDepth, true, snr * addedWeight, inputIndex + 1, - diffs + (j > 0)); - } - } else if (childrenAddress != 0) { - getWordsRec(childrenAddress, depth + 1, maxDepth, - false, snr * addedWeight, inputIndex + 1, diffs + (j > 0)); - } - } - j++; - if (mSkipPos >= 0) break; - } - } - } +Dictionary::~Dictionary() { + delete mUnigramDictionary; + delete mBigramDictionary; } -int -Dictionary::getBigramAddress(int *pos, bool advance) -{ - int address = 0; - - address += (mDict[*pos] & 0x3F) << 16; - address += (mDict[*pos + 1] & 0xFF) << 8; - address += (mDict[*pos + 2] & 0xFF); - - if (advance) { - *pos += 3; - } - - return address; +bool Dictionary::hasBigram() { + return ((mDict[1] & 0xFF) == 1); } -int -Dictionary::getBigramFreq(int *pos) -{ - int freq = mDict[(*pos)++] & FLAG_BIGRAM_FREQ; - - return freq; +bool Dictionary::isValidWord(unsigned short *word, int length) { + return mUnigramDictionary->isValidWord(word, length); } - -int -Dictionary::getBigrams(unsigned short *prevWord, int prevWordLength, int *codes, int codesSize, - unsigned short *bigramChars, int *bigramFreq, int maxWordLength, int maxBigrams, - int maxAlternatives) -{ - mBigramFreq = bigramFreq; - mBigramChars = bigramChars; - mInputCodes = codes; - mInputLength = codesSize; - mMaxWordLength = maxWordLength; - mMaxBigrams = maxBigrams; - mMaxAlternatives = maxAlternatives; - - if (mBigram == 1 && checkIfDictVersionIsLatest()) { - int pos = isValidWordRec(DICTIONARY_HEADER_SIZE, prevWord, 0, prevWordLength); - LOGI("Pos -> %d\n", pos); - if (pos < 0) { - return 0; - } - - int bigramCount = 0; - int bigramExist = (mDict[pos] & FLAG_BIGRAM_READ); - if (bigramExist > 0) { - int nextBigramExist = 1; - while (nextBigramExist > 0 && bigramCount < maxBigrams) { - int bigramAddress = getBigramAddress(&pos, true); - int frequency = (FLAG_BIGRAM_FREQ & mDict[pos]); - // search for all bigrams and store them - searchForTerminalNode(bigramAddress, frequency); - nextBigramExist = (mDict[pos++] & FLAG_BIGRAM_CONTINUED); - bigramCount++; - } - } - - return bigramCount; - } - return 0; -} - -void -Dictionary::searchForTerminalNode(int addressLookingFor, int frequency) -{ - // track word with such address and store it in an array - unsigned short word[mMaxWordLength]; - - int pos; - int followDownBranchAddress = DICTIONARY_HEADER_SIZE; - bool found = false; - char followingChar = ' '; - int depth = -1; - - while(!found) { - bool followDownAddressSearchStop = false; - bool firstAddress = true; - bool haveToSearchAll = true; - - if (depth >= 0) { - word[depth] = (unsigned short) followingChar; - } - pos = followDownBranchAddress; // pos start at count - int count = mDict[pos] & 0xFF; - LOGI("count - %d\n",count); - pos++; - for (int i = 0; i < count; i++) { - // pos at data - pos++; - // pos now at flag - if (!getFirstBitOfByte(&pos)) { // non-terminal - if (!followDownAddressSearchStop) { - int addr = getBigramAddress(&pos, false); - if (addr > addressLookingFor) { - followDownAddressSearchStop = true; - if (firstAddress) { - firstAddress = false; - haveToSearchAll = true; - } else if (!haveToSearchAll) { - break; - } - } else { - followDownBranchAddress = addr; - followingChar = (char)(0xFF & mDict[pos-1]); - if (firstAddress) { - firstAddress = false; - haveToSearchAll = false; - } - } - } - pos += 3; - } else if (getFirstBitOfByte(&pos)) { // terminal - if (addressLookingFor == (pos-1)) { // found !! - depth++; - word[depth] = (0xFF & mDict[pos-1]); - found = true; - break; - } - if (getSecondBitOfByte(&pos)) { // address + freq (4 byte) - if (!followDownAddressSearchStop) { - int addr = getBigramAddress(&pos, false); - if (addr > addressLookingFor) { - followDownAddressSearchStop = true; - if (firstAddress) { - firstAddress = false; - haveToSearchAll = true; - } else if (!haveToSearchAll) { - break; - } - } else { - followDownBranchAddress = addr; - followingChar = (char)(0xFF & mDict[pos-1]); - if (firstAddress) { - firstAddress = false; - haveToSearchAll = true; - } - } - } - pos += 4; - } else { // freq only (2 byte) - pos += 2; - } - - // skipping bigram - int bigramExist = (mDict[pos] & FLAG_BIGRAM_READ); - if (bigramExist > 0) { - int nextBigramExist = 1; - while (nextBigramExist > 0) { - pos += 3; - nextBigramExist = (mDict[pos++] & FLAG_BIGRAM_CONTINUED); - } - } else { - pos++; - } - } - } - depth++; - if (followDownBranchAddress == 0) { - LOGI("ERROR!!! Cannot find bigram!!"); - break; - } - } - if (checkFirstCharacter(word)) { - addWordBigram(word, depth, frequency); - } -} - -bool -Dictionary::checkFirstCharacter(unsigned short *word) -{ - // Checks whether this word starts with same character or neighboring characters of - // what user typed. - - int *inputCodes = mInputCodes; - int maxAlt = mMaxAlternatives; - while (maxAlt > 0) { - if ((unsigned int) *inputCodes == (unsigned int) *word) { - return true; - } - inputCodes++; - maxAlt--; - } - return false; -} - -bool -Dictionary::isValidWord(unsigned short *word, int length) -{ - if (checkIfDictVersionIsLatest()) { - return (isValidWordRec(DICTIONARY_HEADER_SIZE, word, 0, length) != NOT_VALID_WORD); +int Dictionary::getBigramPosition(unsigned short *word, int length) { + if (IS_LATEST_DICT_VERSION) { + return mUnigramDictionary->getBigramPosition(DICTIONARY_HEADER_SIZE, word, 0, length); } else { - return (isValidWordRec(0, word, 0, length) != NOT_VALID_WORD); + return mUnigramDictionary->getBigramPosition(0, word, 0, length); } } -int -Dictionary::isValidWordRec(int pos, unsigned short *word, int offset, int length) { - // returns address of bigram data of that word - // return -99 if not found - - int count = getCount(&pos); - unsigned short currentChar = (unsigned short) word[offset]; - for (int j = 0; j < count; j++) { - unsigned short c = getChar(&pos); - int terminal = getTerminal(&pos); - int childPos = getAddress(&pos); - if (c == currentChar) { - if (offset == length - 1) { - if (terminal) { - return (pos+1); - } - } else { - if (childPos != 0) { - int t = isValidWordRec(childPos, word, offset + 1, length); - if (t > 0) { - return t; - } - } - } - } - if (terminal) { - getFreq(&pos); - } - // There could be two instances of each alphabet - upper and lower case. So continue - // looking ... - } - return NOT_VALID_WORD; -} - - } // namespace latinime diff --git a/native/src/dictionary.h b/native/src/dictionary.h index d13496e01..3dc577a56 100644 --- a/native/src/dictionary.h +++ b/native/src/dictionary.h @@ -17,90 +17,145 @@ #ifndef LATINIME_DICTIONARY_H #define LATINIME_DICTIONARY_H -namespace latinime { - -// 22-bit address = ~4MB dictionary size limit, which on average would be about 200k-300k words -#define ADDRESS_MASK 0x3FFFFF - -// The bit that decides if an address follows in the next 22 bits -#define FLAG_ADDRESS_MASK 0x40 -// The bit that decides if this is a terminal node for a word. The node could still have children, -// if the word has other endings. -#define FLAG_TERMINAL_MASK 0x80 +#include "bigram_dictionary.h" +#include "defines.h" +#include "proximity_info.h" +#include "unigram_dictionary.h" -#define FLAG_BIGRAM_READ 0x80 -#define FLAG_BIGRAM_CHILDEXIST 0x40 -#define FLAG_BIGRAM_CONTINUED 0x80 -#define FLAG_BIGRAM_FREQ 0x7F +namespace latinime { class Dictionary { public: - Dictionary(void *dict, int typedLetterMultipler, int fullWordMultiplier); - int getSuggestions(int *codes, int codesSize, unsigned short *outWords, int *frequencies, - int maxWordLength, int maxWords, int maxAlternatives, int skipPos, - int *nextLetters, int nextLettersSize); + Dictionary(void *dict, int dictSize, int mmapFd, int dictBufAdjust, int typedLetterMultipler, + int fullWordMultiplier, int maxWordLength, int maxWords, int maxAlternatives); + int getSuggestions(ProximityInfo *proximityInfo, int *xcoordinates, int *ycoordinates, + int *codes, int codesSize, int flags, unsigned short *outWords, int *frequencies) { + return mUnigramDictionary->getSuggestions(proximityInfo, xcoordinates, ycoordinates, codes, + codesSize, flags, outWords, frequencies); + } + + // TODO: Call mBigramDictionary instead of mUnigramDictionary int getBigrams(unsigned short *word, int length, int *codes, int codesSize, unsigned short *outWords, int *frequencies, int maxWordLength, int maxBigrams, - int maxAlternatives); + int maxAlternatives) { + return mBigramDictionary->getBigrams(word, length, codes, codesSize, outWords, frequencies, + maxWordLength, maxBigrams, maxAlternatives); + } + bool isValidWord(unsigned short *word, int length); - void setAsset(void *asset) { mAsset = asset; } - void *getAsset() { return mAsset; } + void *getDict() { return (void *)mDict; } + int getDictSize() { return mDictSize; } + int getMmapFd() { return mMmapFd; } + int getDictBufAdjust() { return mDictBufAdjust; } ~Dictionary(); + // public static utility methods + // static inline methods should be defined in the header file + static unsigned short getChar(const unsigned char *dict, int *pos); + static int getCount(const unsigned char *dict, int *pos); + static bool getTerminal(const unsigned char *dict, int *pos); + static int getAddress(const unsigned char *dict, int *pos); + static int getFreq(const unsigned char *dict, const bool isLatestDictVersion, int *pos); + static int wideStrLen(unsigned short *str); + // returns next sibling's position + static int setDictionaryValues(const unsigned char *dict, const bool isLatestDictVersion, + const int pos, unsigned short *c, int *childrenPosition, + bool *terminal, int *freq); + + // TODO: delete this + int getBigramPosition(unsigned short *word, int length); + private: + bool hasBigram(); - void getVersionNumber(); - bool checkIfDictVersionIsLatest(); - int getAddress(int *pos); - int getBigramAddress(int *pos, bool advance); - int getFreq(int *pos); - int getBigramFreq(int *pos); - void searchForTerminalNode(int address, int frequency); - - bool getFirstBitOfByte(int *pos) { return (mDict[*pos] & 0x80) > 0; } - bool getSecondBitOfByte(int *pos) { return (mDict[*pos] & 0x40) > 0; } - bool getTerminal(int *pos) { return (mDict[*pos] & FLAG_TERMINAL_MASK) > 0; } - int getCount(int *pos) { return mDict[(*pos)++] & 0xFF; } - unsigned short getChar(int *pos); - int wideStrLen(unsigned short *str); - - bool sameAsTyped(unsigned short *word, int length); - bool checkFirstCharacter(unsigned short *word); - bool addWord(unsigned short *word, int length, int frequency); - bool addWordBigram(unsigned short *word, int length, int frequency); - unsigned short toLowerCase(unsigned short c); - void getWordsRec(int pos, int depth, int maxDepth, bool completion, int frequency, - int inputIndex, int diffs); - int isValidWordRec(int pos, unsigned short *word, int offset, int length); - void registerNextLetter(unsigned short c); - - unsigned char *mDict; - void *mAsset; - - int *mFrequencies; - int *mBigramFreq; - int mMaxWords; - int mMaxBigrams; - int mMaxWordLength; - unsigned short *mOutputChars; - unsigned short *mBigramChars; - int *mInputCodes; - int mInputLength; - int mMaxAlternatives; - unsigned short mWord[128]; - int mSkipPos; - int mMaxEditDistance; - - int mFullWordMultiplier; - int mTypedLetterMultiplier; - int *mNextLettersFrequencies; - int mNextLettersSize; - int mVersion; - int mBigram; -}; + const unsigned char *mDict; -// ---------------------------------------------------------------------------- + // Used only for the mmap version of dictionary loading, but we use these as dummy variables + // also for the malloc version. + const int mDictSize; + const int mMmapFd; + const int mDictBufAdjust; + + const bool IS_LATEST_DICT_VERSION; + UnigramDictionary *mUnigramDictionary; + BigramDictionary *mBigramDictionary; +}; -}; // namespace latinime +// public static utility methods +// static inline methods should be defined in the header file +inline unsigned short Dictionary::getChar(const unsigned char *dict, int *pos) { + unsigned short ch = (unsigned short) (dict[(*pos)++] & 0xFF); + // If the code is 255, then actual 16 bit code follows (in big endian) + if (ch == 0xFF) { + ch = ((dict[*pos] & 0xFF) << 8) | (dict[*pos + 1] & 0xFF); + (*pos) += 2; + } + return ch; +} + +inline int Dictionary::getCount(const unsigned char *dict, int *pos) { + return dict[(*pos)++] & 0xFF; +} + +inline bool Dictionary::getTerminal(const unsigned char *dict, int *pos) { + return (dict[*pos] & FLAG_TERMINAL_MASK) > 0; +} + +inline int Dictionary::getAddress(const unsigned char *dict, int *pos) { + int address = 0; + if ((dict[*pos] & FLAG_ADDRESS_MASK) == 0) { + *pos += 1; + } else { + address += (dict[*pos] & (ADDRESS_MASK >> 16)) << 16; + address += (dict[*pos + 1] & 0xFF) << 8; + address += (dict[*pos + 2] & 0xFF); + *pos += 3; + } + return address; +} + +inline int Dictionary::getFreq(const unsigned char *dict, + const bool isLatestDictVersion, int *pos) { + int freq = dict[(*pos)++] & 0xFF; + if (isLatestDictVersion) { + // skipping bigram + int bigramExist = (dict[*pos] & FLAG_BIGRAM_READ); + if (bigramExist > 0) { + int nextBigramExist = 1; + while (nextBigramExist > 0) { + (*pos) += 3; + nextBigramExist = (dict[(*pos)++] & FLAG_BIGRAM_CONTINUED); + } + } else { + (*pos)++; + } + } + return freq; +} + +inline int Dictionary::wideStrLen(unsigned short *str) { + if (!str) return 0; + unsigned short *end = str; + while (*end) + end++; + return end - str; +} + +inline int Dictionary::setDictionaryValues(const unsigned char *dict, + const bool isLatestDictVersion, const int pos, unsigned short *c,int *childrenPosition, + bool *terminal, int *freq) { + int position = pos; + // -- at char + *c = Dictionary::getChar(dict, &position); + // -- at flag/add + *terminal = Dictionary::getTerminal(dict, &position); + *childrenPosition = Dictionary::getAddress(dict, &position); + // -- after address or flag + *freq = (*terminal) ? Dictionary::getFreq(dict, isLatestDictVersion, &position) : 1; + // returns next sibling's position + return position; +} + +} // namespace latinime #endif // LATINIME_DICTIONARY_H diff --git a/native/src/proximity_info.cpp b/native/src/proximity_info.cpp new file mode 100644 index 000000000..209c31e6e --- /dev/null +++ b/native/src/proximity_info.cpp @@ -0,0 +1,66 @@ +/* + * Copyright (C) 2011 The Android Open Source Project + * + * Licensed under the Apache License, Version 2.0 (the "License"); + * you may not use this file except in compliance with the License. + * You may obtain a copy of the License at + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + * See the License for the specific language governing permissions and + * limitations under the License. + */ + +#include <stdio.h> +#include <string.h> + +#define LOG_TAG "LatinIME: proximity_info.cpp" + +#include "proximity_info.h" + +namespace latinime { + +ProximityInfo::ProximityInfo(const int maxProximityCharsSize, const int keyboardWidth, + const int keyboardHeight, const int gridWidth, const int gridHeight, + const uint32_t *proximityCharsArray) + : MAX_PROXIMITY_CHARS_SIZE(maxProximityCharsSize), KEYBOARD_WIDTH(keyboardWidth), + KEYBOARD_HEIGHT(keyboardHeight), GRID_WIDTH(gridWidth), GRID_HEIGHT(gridHeight), + CELL_WIDTH((keyboardWidth + gridWidth - 1) / gridWidth), + CELL_HEIGHT((keyboardHeight + gridHeight - 1) / gridHeight) { + const int len = GRID_WIDTH * GRID_HEIGHT * MAX_PROXIMITY_CHARS_SIZE; + mProximityCharsArray = new uint32_t[len]; + if (DEBUG_PROXIMITY_INFO) { + LOGI("Create proximity info array %d", len); + } + memcpy(mProximityCharsArray, proximityCharsArray, len * sizeof(mProximityCharsArray[0])); +} + +ProximityInfo::~ProximityInfo() { + delete[] mProximityCharsArray; +} + +inline int ProximityInfo::getStartIndexFromCoordinates(const int x, const int y) const { + return ((y / CELL_HEIGHT) * GRID_WIDTH + (x / CELL_WIDTH)) + * MAX_PROXIMITY_CHARS_SIZE; +} + +bool ProximityInfo::hasSpaceProximity(const int x, const int y) const { + const int startIndex = getStartIndexFromCoordinates(x, y); + if (DEBUG_PROXIMITY_INFO) { + LOGI("hasSpaceProximity: index %d", startIndex); + } + for (int i = 0; i < MAX_PROXIMITY_CHARS_SIZE; ++i) { + if (DEBUG_PROXIMITY_INFO) { + LOGI("Index: %d", mProximityCharsArray[startIndex + i]); + } + if (mProximityCharsArray[startIndex + i] == KEYCODE_SPACE) { + return true; + } + } + return false; +} + +} // namespace latinime diff --git a/native/src/proximity_info.h b/native/src/proximity_info.h new file mode 100644 index 000000000..327cd0940 --- /dev/null +++ b/native/src/proximity_info.h @@ -0,0 +1,47 @@ +/* + * Copyright (C) 2011 The Android Open Source Project + * + * Licensed under the Apache License, Version 2.0 (the "License"); + * you may not use this file except in compliance with the License. + * You may obtain a copy of the License at + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + * See the License for the specific language governing permissions and + * limitations under the License. + */ + +#ifndef LATINIME_PROXIMITY_INFO_H +#define LATINIME_PROXIMITY_INFO_H + +#include <stdint.h> + +#include "defines.h" + +namespace latinime { + +class ProximityInfo { +public: + ProximityInfo(const int maxProximityCharsSize, const int keyboardWidth, + const int keybaordHeight, const int gridWidth, const int gridHeight, + const uint32_t *proximityCharsArray); + ~ProximityInfo(); + bool hasSpaceProximity(const int x, const int y) const; +private: + int getStartIndexFromCoordinates(const int x, const int y) const; + const int MAX_PROXIMITY_CHARS_SIZE; + const int KEYBOARD_WIDTH; + const int KEYBOARD_HEIGHT; + const int GRID_WIDTH; + const int GRID_HEIGHT; + const int CELL_WIDTH; + const int CELL_HEIGHT; + uint32_t *mProximityCharsArray; +}; + +} // namespace latinime + +#endif // LATINIME_PROXIMITY_INFO_H diff --git a/native/src/unigram_dictionary.cpp b/native/src/unigram_dictionary.cpp new file mode 100644 index 000000000..e3296f12a --- /dev/null +++ b/native/src/unigram_dictionary.cpp @@ -0,0 +1,1127 @@ +/* +** +** Copyright 2010, The Android Open Source Project +** +** Licensed under the Apache License, Version 2.0 (the "License"); +** you may not use this file except in compliance with the License. +** You may obtain a copy of the License at +** +** http://www.apache.org/licenses/LICENSE-2.0 +** +** Unless required by applicable law or agreed to in writing, software +** distributed under the License is distributed on an "AS IS" BASIS, +** WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. +** See the License for the specific language governing permissions and +** limitations under the License. +*/ + +#include <assert.h> +#include <string.h> + +#define LOG_TAG "LatinIME: unigram_dictionary.cpp" + +#include "basechars.h" +#include "char_utils.h" +#include "dictionary.h" +#include "unigram_dictionary.h" + +namespace latinime { + +const UnigramDictionary::digraph_t UnigramDictionary::GERMAN_UMLAUT_DIGRAPHS[] = + { { 'a', 'e' }, + { 'o', 'e' }, + { 'u', 'e' } }; + +// TODO: check the header +UnigramDictionary::UnigramDictionary(const uint8_t* const streamStart, int typedLetterMultiplier, + int fullWordMultiplier, int maxWordLength, int maxWords, int maxProximityChars, + const bool isLatestDictVersion) + : DICT_ROOT(streamStart), + MAX_WORD_LENGTH(maxWordLength), MAX_WORDS(maxWords), + MAX_PROXIMITY_CHARS(maxProximityChars), IS_LATEST_DICT_VERSION(isLatestDictVersion), + TYPED_LETTER_MULTIPLIER(typedLetterMultiplier), FULL_WORD_MULTIPLIER(fullWordMultiplier), + ROOT_POS(isLatestDictVersion ? DICTIONARY_HEADER_SIZE : 0), + BYTES_IN_ONE_CHAR(MAX_PROXIMITY_CHARS * sizeof(*mInputCodes)), + MAX_UMLAUT_SEARCH_DEPTH(DEFAULT_MAX_UMLAUT_SEARCH_DEPTH) { + if (DEBUG_DICT) { + LOGI("UnigramDictionary - constructor"); + } +} + +UnigramDictionary::~UnigramDictionary() {} + +static inline unsigned int getCodesBufferSize(const int* codes, const int codesSize, + const int MAX_PROXIMITY_CHARS) { + return sizeof(*codes) * MAX_PROXIMITY_CHARS * codesSize; +} + +bool UnigramDictionary::isDigraph(const int* codes, const int i, const int codesSize) const { + + // There can't be a digraph if we don't have at least 2 characters to examine + if (i + 2 > codesSize) return false; + + // Search for the first char of some digraph + int lastDigraphIndex = -1; + const int thisChar = codes[i * MAX_PROXIMITY_CHARS]; + for (lastDigraphIndex = sizeof(GERMAN_UMLAUT_DIGRAPHS) / sizeof(GERMAN_UMLAUT_DIGRAPHS[0]) - 1; + lastDigraphIndex >= 0; --lastDigraphIndex) { + if (thisChar == GERMAN_UMLAUT_DIGRAPHS[lastDigraphIndex].first) break; + } + // No match: return early + if (lastDigraphIndex < 0) return false; + + // It's an interesting digraph if the second char matches too. + return GERMAN_UMLAUT_DIGRAPHS[lastDigraphIndex].second == codes[(i + 1) * MAX_PROXIMITY_CHARS]; +} + +// Mostly the same arguments as the non-recursive version, except: +// codes is the original value. It points to the start of the work buffer, and gets passed as is. +// codesSize is the size of the user input (thus, it is the size of codesSrc). +// codesDest is the current point in the work buffer. +// codesSrc is the current point in the user-input, original, content-unmodified buffer. +// codesRemain is the remaining size in codesSrc. +void UnigramDictionary::getWordWithDigraphSuggestionsRec(const ProximityInfo *proximityInfo, + const int *xcoordinates, const int* ycoordinates, const int *codesBuffer, + const int codesBufferSize, const int flags, const int* codesSrc, const int codesRemain, + const int currentDepth, int* codesDest, unsigned short* outWords, int* frequencies) { + + if (currentDepth < MAX_UMLAUT_SEARCH_DEPTH) { + for (int i = 0; i < codesRemain; ++i) { + if (isDigraph(codesSrc, i, codesRemain)) { + // Found a digraph. We will try both spellings. eg. the word is "pruefen" + + // Copy the word up to the first char of the digraph, then continue processing + // on the remaining part of the word, skipping the second char of the digraph. + // In our example, copy "pru" and continue running on "fen" + // Make i the index of the second char of the digraph for simplicity. Forgetting + // to do that results in an infinite recursion so take care! + ++i; + memcpy(codesDest, codesSrc, i * BYTES_IN_ONE_CHAR); + getWordWithDigraphSuggestionsRec(proximityInfo, xcoordinates, ycoordinates, + codesBuffer, codesBufferSize, flags, + codesSrc + (i + 1) * MAX_PROXIMITY_CHARS, codesRemain - i - 1, + currentDepth + 1, codesDest + i * MAX_PROXIMITY_CHARS, outWords, + frequencies); + + // Copy the second char of the digraph in place, then continue processing on + // the remaining part of the word. + // In our example, after "pru" in the buffer copy the "e", and continue on "fen" + memcpy(codesDest + i * MAX_PROXIMITY_CHARS, codesSrc + i * MAX_PROXIMITY_CHARS, + BYTES_IN_ONE_CHAR); + getWordWithDigraphSuggestionsRec(proximityInfo, xcoordinates, ycoordinates, + codesBuffer, codesBufferSize, flags, codesSrc + i * MAX_PROXIMITY_CHARS, + codesRemain - i, currentDepth + 1, codesDest + i * MAX_PROXIMITY_CHARS, + outWords, frequencies); + return; + } + } + } + + // If we come here, we hit the end of the word: let's check it against the dictionary. + // In our example, we'll come here once for "prufen" and then once for "pruefen". + // If the word contains several digraphs, we'll come it for the product of them. + // eg. if the word is "ueberpruefen" we'll test, in order, against + // "uberprufen", "uberpruefen", "ueberprufen", "ueberpruefen". + const unsigned int remainingBytes = BYTES_IN_ONE_CHAR * codesRemain; + if (0 != remainingBytes) + memcpy(codesDest, codesSrc, remainingBytes); + + getWordSuggestions(proximityInfo, xcoordinates, ycoordinates, codesBuffer, + (codesDest - codesBuffer) / MAX_PROXIMITY_CHARS + codesRemain, outWords, frequencies); +} + +int UnigramDictionary::getSuggestions(const ProximityInfo *proximityInfo, const int *xcoordinates, + const int *ycoordinates, const int *codes, const int codesSize, const int flags, + unsigned short *outWords, int *frequencies) { + + if (REQUIRES_GERMAN_UMLAUT_PROCESSING & flags) + { // Incrementally tune the word and try all possibilities + int codesBuffer[getCodesBufferSize(codes, codesSize, MAX_PROXIMITY_CHARS)]; + getWordWithDigraphSuggestionsRec(proximityInfo, xcoordinates, ycoordinates, codesBuffer, + codesSize, flags, codes, codesSize, 0, codesBuffer, outWords, frequencies); + } else { // Normal processing + getWordSuggestions(proximityInfo, xcoordinates, ycoordinates, codes, codesSize, + outWords, frequencies); + } + + PROF_START(20); + // Get the word count + int suggestedWordsCount = 0; + while (suggestedWordsCount < MAX_WORDS && mFrequencies[suggestedWordsCount] > 0) { + suggestedWordsCount++; + } + + if (DEBUG_DICT) { + LOGI("Returning %d words", suggestedWordsCount); + LOGI("Next letters: "); + for (int k = 0; k < NEXT_LETTERS_SIZE; k++) { + if (mNextLettersFrequency[k] > 0) { + LOGI("%c = %d,", k, mNextLettersFrequency[k]); + } + } + } + PROF_END(20); + PROF_CLOSE; + return suggestedWordsCount; +} + +void UnigramDictionary::getWordSuggestions(const ProximityInfo *proximityInfo, + const int *xcoordinates, const int *ycoordinates, const int *codes, const int codesSize, + unsigned short *outWords, int *frequencies) { + + PROF_OPEN; + PROF_START(0); + initSuggestions(codes, codesSize, outWords, frequencies); + if (DEBUG_DICT) assert(codesSize == mInputLength); + + const int MAX_DEPTH = min(mInputLength * MAX_DEPTH_MULTIPLIER, MAX_WORD_LENGTH); + PROF_END(0); + + PROF_START(1); + getSuggestionCandidates(-1, -1, -1, mNextLettersFrequency, NEXT_LETTERS_SIZE, MAX_DEPTH); + PROF_END(1); + + PROF_START(2); + // Suggestion with missing character + if (SUGGEST_WORDS_WITH_MISSING_CHARACTER) { + for (int i = 0; i < codesSize; ++i) { + if (DEBUG_DICT) { + LOGI("--- Suggest missing characters %d", i); + } + getSuggestionCandidates(i, -1, -1, NULL, 0, MAX_DEPTH); + } + } + PROF_END(2); + + PROF_START(3); + // Suggestion with excessive character + if (SUGGEST_WORDS_WITH_EXCESSIVE_CHARACTER + && mInputLength >= MIN_USER_TYPED_LENGTH_FOR_EXCESSIVE_CHARACTER_SUGGESTION) { + for (int i = 0; i < codesSize; ++i) { + if (DEBUG_DICT) { + LOGI("--- Suggest excessive characters %d", i); + } + getSuggestionCandidates(-1, i, -1, NULL, 0, MAX_DEPTH); + } + } + PROF_END(3); + + PROF_START(4); + // Suggestion with transposed characters + // Only suggest words that length is mInputLength + if (SUGGEST_WORDS_WITH_TRANSPOSED_CHARACTERS) { + for (int i = 0; i < codesSize; ++i) { + if (DEBUG_DICT) { + LOGI("--- Suggest transposed characters %d", i); + } + getSuggestionCandidates(-1, -1, i, NULL, 0, mInputLength - 1); + } + } + PROF_END(4); + + PROF_START(5); + // Suggestions with missing space + if (SUGGEST_WORDS_WITH_MISSING_SPACE_CHARACTER + && mInputLength >= MIN_USER_TYPED_LENGTH_FOR_MISSING_SPACE_SUGGESTION) { + for (int i = 1; i < codesSize; ++i) { + if (DEBUG_DICT) { + LOGI("--- Suggest missing space characters %d", i); + } + getMissingSpaceWords(mInputLength, i); + } + } + PROF_END(5); + + PROF_START(6); + if (SUGGEST_WORDS_WITH_SPACE_PROXIMITY && proximityInfo) { + // The first and last "mistyped spaces" are taken care of by excessive character handling + for (int i = 1; i < codesSize - 1; ++i) { + if (DEBUG_DICT) { + LOGI("--- Suggest words with proximity space %d", i); + } + const int x = xcoordinates[i]; + const int y = ycoordinates[i]; + if (DEBUG_PROXIMITY_INFO) { + LOGI("Input[%d] x = %d, y = %d, has space proximity = %d", + i, x, y, proximityInfo->hasSpaceProximity(x, y)); + } + if (proximityInfo->hasSpaceProximity(x, y)) { + getMistypedSpaceWords(mInputLength, i); + } + } + } + PROF_END(6); +} + +void UnigramDictionary::initSuggestions(const int *codes, const int codesSize, + unsigned short *outWords, int *frequencies) { + if (DEBUG_DICT) { + LOGI("initSuggest"); + } + mFrequencies = frequencies; + mOutputChars = outWords; + mInputCodes = codes; + mInputLength = codesSize; + mMaxEditDistance = mInputLength < 5 ? 2 : mInputLength / 2; +} + +static inline void registerNextLetter(unsigned short c, int *nextLetters, int nextLettersSize) { + if (c < nextLettersSize) { + nextLetters[c]++; + } +} + +// TODO: We need to optimize addWord by using STL or something +// TODO: This needs to take an const unsigned short* and not tinker with its contents +bool UnigramDictionary::addWord(unsigned short *word, int length, int frequency) { + word[length] = 0; + if (DEBUG_DICT && DEBUG_SHOW_FOUND_WORD) { + char s[length + 1]; + for (int i = 0; i <= length; i++) s[i] = word[i]; + LOGI("Found word = %s, freq = %d", s, frequency); + } + if (length > MAX_WORD_LENGTH) { + if (DEBUG_DICT) { + LOGI("Exceeded max word length."); + } + return false; + } + + // Find the right insertion point + int insertAt = 0; + while (insertAt < MAX_WORDS) { + // TODO: How should we sort words with the same frequency? + if (frequency > mFrequencies[insertAt]) { + break; + } + insertAt++; + } + if (insertAt < MAX_WORDS) { + if (DEBUG_DICT) { + char s[length + 1]; + for (int i = 0; i <= length; i++) s[i] = word[i]; + LOGI("Added word = %s, freq = %d, %d", s, frequency, S_INT_MAX); + } + memmove((char*) mFrequencies + (insertAt + 1) * sizeof(mFrequencies[0]), + (char*) mFrequencies + insertAt * sizeof(mFrequencies[0]), + (MAX_WORDS - insertAt - 1) * sizeof(mFrequencies[0])); + mFrequencies[insertAt] = frequency; + memmove((char*) mOutputChars + (insertAt + 1) * MAX_WORD_LENGTH * sizeof(short), + (char*) mOutputChars + insertAt * MAX_WORD_LENGTH * sizeof(short), + (MAX_WORDS - insertAt - 1) * sizeof(short) * MAX_WORD_LENGTH); + unsigned short *dest = mOutputChars + insertAt * MAX_WORD_LENGTH; + while (length--) { + *dest++ = *word++; + } + *dest = 0; // NULL terminate + if (DEBUG_DICT) { + LOGI("Added word at %d", insertAt); + } + return true; + } + return false; +} + +inline void UnigramDictionary::addWordAlternatesSpellings(const uint8_t* const root, int pos, + int depth, int finalFreq) { + // TODO: actually add alternates when the format supports it. +} + +static inline bool hasAlternateSpellings(uint8_t flags) { + // TODO: when the format supports it, return the actual value. + return false; +} + +static inline unsigned short toBaseLowerCase(unsigned short c) { + if (c < sizeof(BASE_CHARS) / sizeof(BASE_CHARS[0])) { + c = BASE_CHARS[c]; + } + if (c >='A' && c <= 'Z') { + c |= 32; + } else if (c > 127) { + c = latin_tolower(c); + } + return c; +} + +bool UnigramDictionary::sameAsTyped(const unsigned short *word, int length) const { + if (length != mInputLength) { + return false; + } + const int *inputCodes = mInputCodes; + while (length--) { + if ((unsigned int) *inputCodes != (unsigned int) *word) { + return false; + } + inputCodes += MAX_PROXIMITY_CHARS; + word++; + } + return true; +} + +static const char QUOTE = '\''; +static const char SPACE = ' '; + +void UnigramDictionary::getSuggestionCandidates(const int skipPos, + const int excessivePos, const int transposedPos, int *nextLetters, + const int nextLettersSize, const int maxDepth) { + if (DEBUG_DICT) { + LOGI("getSuggestionCandidates %d", maxDepth); + assert(transposedPos + 1 < mInputLength); + assert(excessivePos < mInputLength); + assert(missingPos < mInputLength); + } + int rootPosition = ROOT_POS; + // Get the number of child of root, then increment the position + int childCount = Dictionary::getCount(DICT_ROOT, &rootPosition); + int depth = 0; + + mStackChildCount[0] = childCount; + mStackTraverseAll[0] = (mInputLength <= 0); + mStackNodeFreq[0] = 1; + mStackInputIndex[0] = 0; + mStackDiffs[0] = 0; + mStackSiblingPos[0] = rootPosition; + mStackOutputIndex[0] = 0; + + // Depth first search + while (depth >= 0) { + if (mStackChildCount[depth] > 0) { + --mStackChildCount[depth]; + bool traverseAllNodes = mStackTraverseAll[depth]; + int matchWeight = mStackNodeFreq[depth]; + int inputIndex = mStackInputIndex[depth]; + int diffs = mStackDiffs[depth]; + int siblingPos = mStackSiblingPos[depth]; + int outputIndex = mStackOutputIndex[depth]; + int firstChildPos; + // depth will never be greater than maxDepth because in that case, + // needsToTraverseChildrenNodes should be false + const bool needsToTraverseChildrenNodes = processCurrentNode(siblingPos, outputIndex, + maxDepth, traverseAllNodes, matchWeight, inputIndex, diffs, skipPos, + excessivePos, transposedPos, nextLetters, nextLettersSize, &childCount, + &firstChildPos, &traverseAllNodes, &matchWeight, &inputIndex, &diffs, + &siblingPos, &outputIndex); + // Update next sibling pos + mStackSiblingPos[depth] = siblingPos; + if (needsToTraverseChildrenNodes) { + // Goes to child node + ++depth; + mStackChildCount[depth] = childCount; + mStackTraverseAll[depth] = traverseAllNodes; + mStackNodeFreq[depth] = matchWeight; + mStackInputIndex[depth] = inputIndex; + mStackDiffs[depth] = diffs; + mStackSiblingPos[depth] = firstChildPos; + mStackOutputIndex[depth] = outputIndex; + } + } else { + // Goes to parent sibling node + --depth; + } + } +} + +static const int TWO_31ST_DIV_255 = S_INT_MAX / 255; +static inline int capped255MultForFullMatchAccentsOrCapitalizationDifference(const int num) { + return (num < TWO_31ST_DIV_255 ? 255 * num : S_INT_MAX); +} + +static const int TWO_31ST_DIV_2 = S_INT_MAX / 2; +inline static void multiplyIntCapped(const int multiplier, int *base) { + const int temp = *base; + if (temp != S_INT_MAX) { + // Branch if multiplier == 2 for the optimization + if (multiplier == 2) { + *base = TWO_31ST_DIV_2 >= temp ? temp << 1 : S_INT_MAX; + } else { + const int tempRetval = temp * multiplier; + *base = tempRetval >= temp ? tempRetval : S_INT_MAX; + } + } +} + +inline static int powerIntCapped(const int base, const int n) { + if (base == 2) { + return n < 31 ? 1 << n : S_INT_MAX; + } else { + int ret = base; + for (int i = 1; i < n; ++i) multiplyIntCapped(base, &ret); + return ret; + } +} + +inline static void multiplyRate(const int rate, int *freq) { + if (*freq != S_INT_MAX) { + if (*freq > 1000000) { + *freq /= 100; + multiplyIntCapped(rate, freq); + } else { + multiplyIntCapped(rate, freq); + *freq /= 100; + } + } +} + +inline static int calcFreqForSplitTwoWords( + const int typedLetterMultiplier, const int firstWordLength, const int secondWordLength, + const int firstFreq, const int secondFreq, const bool isSpaceProximity) { + if (firstWordLength == 0 || secondWordLength == 0) { + return 0; + } + const int firstDemotionRate = 100 - 100 / (firstWordLength + 1); + int tempFirstFreq = firstFreq; + multiplyRate(firstDemotionRate, &tempFirstFreq); + + const int secondDemotionRate = 100 - 100 / (secondWordLength + 1); + int tempSecondFreq = secondFreq; + multiplyRate(secondDemotionRate, &tempSecondFreq); + + const int totalLength = firstWordLength + secondWordLength; + + // Promote pairFreq with multiplying by 2, because the word length is the same as the typed + // length. + int totalFreq = tempFirstFreq + tempSecondFreq; + + // This is a workaround to try offsetting the not-enough-demotion which will be done in + // calcNormalizedScore in Utils.java. + // In calcNormalizedScore the score will be demoted by (1 - 1 / length) + // but we demoted only (1 - 1 / (length + 1)) so we will additionally adjust freq by + // (1 - 1 / length) / (1 - 1 / (length + 1)) = (1 - 1 / (length * length)) + const int normalizedScoreNotEnoughDemotionAdjustment = 100 - 100 / (totalLength * totalLength); + multiplyRate(normalizedScoreNotEnoughDemotionAdjustment, &totalFreq); + + // At this moment, totalFreq is calculated by the following formula: + // (firstFreq * (1 - 1 / (firstWordLength + 1)) + secondFreq * (1 - 1 / (secondWordLength + 1))) + // * (1 - 1 / totalLength) / (1 - 1 / (totalLength + 1)) + + multiplyIntCapped(powerIntCapped(typedLetterMultiplier, totalLength), &totalFreq); + + // This is another workaround to offset the demotion which will be done in + // calcNormalizedScore in Utils.java. + // In calcNormalizedScore the score will be demoted by (1 - 1 / length) so we have to promote + // the same amount because we already have adjusted the synthetic freq of this "missing or + // mistyped space" suggestion candidate above in this method. + const int normalizedScoreDemotionRateOffset = (100 + 100 / totalLength); + multiplyRate(normalizedScoreDemotionRateOffset, &totalFreq); + + if (isSpaceProximity) { + // A word pair with one space proximity correction + if (DEBUG_DICT) { + LOGI("Found a word pair with space proximity correction."); + } + multiplyIntCapped(typedLetterMultiplier, &totalFreq); + multiplyRate(WORDS_WITH_PROXIMITY_CHARACTER_DEMOTION_RATE, &totalFreq); + } + + multiplyRate(WORDS_WITH_MISSING_SPACE_CHARACTER_DEMOTION_RATE, &totalFreq); + return totalFreq; +} + +bool UnigramDictionary::getMissingSpaceWords(const int inputLength, const int missingSpacePos) { + return getSplitTwoWordsSuggestion( + inputLength, 0, missingSpacePos, missingSpacePos, inputLength - missingSpacePos, false); +} + +bool UnigramDictionary::getMistypedSpaceWords(const int inputLength, const int spaceProximityPos) { + return getSplitTwoWordsSuggestion( + inputLength, 0, spaceProximityPos, spaceProximityPos + 1, + inputLength - spaceProximityPos - 1, true); +} + +inline int UnigramDictionary::calculateFinalFreq(const int inputIndex, const int depth, + const int matchWeight, const int skipPos, const int excessivePos, const int transposedPos, + const int freq, const bool sameLength) const { + // TODO: Demote by edit distance + int finalFreq = freq * matchWeight; + if (skipPos >= 0) { + if (mInputLength >= 2) { + const int demotionRate = WORDS_WITH_MISSING_CHARACTER_DEMOTION_RATE + * (10 * mInputLength - WORDS_WITH_MISSING_CHARACTER_DEMOTION_START_POS_10X) + / (10 * mInputLength + - WORDS_WITH_MISSING_CHARACTER_DEMOTION_START_POS_10X + 10); + if (DEBUG_DICT_FULL) { + LOGI("Demotion rate for missing character is %d.", demotionRate); + } + multiplyRate(demotionRate, &finalFreq); + } else { + finalFreq = 0; + } + } + if (transposedPos >= 0) multiplyRate( + WORDS_WITH_TRANSPOSED_CHARACTERS_DEMOTION_RATE, &finalFreq); + if (excessivePos >= 0) { + multiplyRate(WORDS_WITH_EXCESSIVE_CHARACTER_DEMOTION_RATE, &finalFreq); + if (!existsAdjacentProximityChars(inputIndex, mInputLength)) { + multiplyRate(WORDS_WITH_EXCESSIVE_CHARACTER_OUT_OF_PROXIMITY_DEMOTION_RATE, &finalFreq); + } + } + int lengthFreq = TYPED_LETTER_MULTIPLIER; + multiplyIntCapped(powerIntCapped(TYPED_LETTER_MULTIPLIER, depth), &lengthFreq); + if (lengthFreq == matchWeight) { + // Full exact match + if (depth > 1) { + if (DEBUG_DICT) { + LOGI("Found full matched word."); + } + multiplyRate(FULL_MATCHED_WORDS_PROMOTION_RATE, &finalFreq); + } + if (sameLength && transposedPos < 0 && skipPos < 0 && excessivePos < 0) { + finalFreq = capped255MultForFullMatchAccentsOrCapitalizationDifference(finalFreq); + } + } else if (sameLength && transposedPos < 0 && skipPos < 0 && excessivePos < 0 && depth > 0) { + // A word with proximity corrections + if (DEBUG_DICT) { + LOGI("Found one proximity correction."); + } + multiplyIntCapped(TYPED_LETTER_MULTIPLIER, &finalFreq); + multiplyRate(WORDS_WITH_PROXIMITY_CHARACTER_DEMOTION_RATE, &finalFreq); + } + if (DEBUG_DICT) { + LOGI("calc: %d, %d", depth, sameLength); + } + if (sameLength) multiplyIntCapped(FULL_WORD_MULTIPLIER, &finalFreq); + return finalFreq; +} + +inline bool UnigramDictionary::needsToSkipCurrentNode(const unsigned short c, + const int inputIndex, const int skipPos, const int depth) { + const unsigned short userTypedChar = getInputCharsAt(inputIndex)[0]; + // Skip the ' or other letter and continue deeper + return (c == QUOTE && userTypedChar != QUOTE) || skipPos == depth; +} + +inline bool UnigramDictionary::existsAdjacentProximityChars(const int inputIndex, + const int inputLength) const { + if (inputIndex < 0 || inputIndex >= inputLength) return false; + const int currentChar = *getInputCharsAt(inputIndex); + const int leftIndex = inputIndex - 1; + if (leftIndex >= 0) { + const int *leftChars = getInputCharsAt(leftIndex); + int i = 0; + while (leftChars[i] > 0 && i < MAX_PROXIMITY_CHARS) { + if (leftChars[i++] == currentChar) return true; + } + } + const int rightIndex = inputIndex + 1; + if (rightIndex < inputLength) { + const int *rightChars = getInputCharsAt(rightIndex); + int i = 0; + while (rightChars[i] > 0 && i < MAX_PROXIMITY_CHARS) { + if (rightChars[i++] == currentChar) return true; + } + } + return false; +} + +// In the following function, c is the current character of the dictionary word +// currently examined. +// currentChars is an array containing the keys close to the character the +// user actually typed at the same position. We want to see if c is in it: if so, +// then the word contains at that position a character close to what the user +// typed. +// What the user typed is actually the first character of the array. +// Notice : accented characters do not have a proximity list, so they are alone +// in their list. The non-accented version of the character should be considered +// "close", but not the other keys close to the non-accented version. +inline UnigramDictionary::ProximityType UnigramDictionary::getMatchedProximityId( + const int *currentChars, const unsigned short c, const int skipPos, + const int excessivePos, const int transposedPos) { + const unsigned short baseLowerC = toBaseLowerCase(c); + + // The first char in the array is what user typed. If it matches right away, + // that means the user typed that same char for this pos. + if (currentChars[0] == baseLowerC || currentChars[0] == c) + return SAME_OR_ACCENTED_OR_CAPITALIZED_CHAR; + + // If one of those is true, we should not check for close characters at all. + if (skipPos >= 0 || excessivePos >= 0 || transposedPos >= 0) + return UNRELATED_CHAR; + + // If the non-accented, lowercased version of that first character matches c, + // then we have a non-accented version of the accented character the user + // typed. Treat it as a close char. + if (toBaseLowerCase(currentChars[0]) == baseLowerC) + return NEAR_PROXIMITY_CHAR; + + // Not an exact nor an accent-alike match: search the list of close keys + int j = 1; + while (currentChars[j] > 0 && j < MAX_PROXIMITY_CHARS) { + const bool matched = (currentChars[j] == baseLowerC || currentChars[j] == c); + if (matched) return NEAR_PROXIMITY_CHAR; + ++j; + } + + // Was not included, signal this as an unrelated character. + return UNRELATED_CHAR; +} + +inline void UnigramDictionary::onTerminal(unsigned short int* word, const int depth, + const uint8_t* const root, const uint8_t flags, int pos, + const int inputIndex, const int matchWeight, const int skipPos, + const int excessivePos, const int transposedPos, const int freq, const bool sameLength, + int* nextLetters, const int nextLettersSize) { + + const bool isSameAsTyped = sameLength ? sameAsTyped(word, depth + 1) : false; + const bool hasAlternates = hasAlternateSpellings(flags); + if (isSameAsTyped && !hasAlternates) return; + + if (depth >= MIN_SUGGEST_DEPTH) { + const int finalFreq = calculateFinalFreq(inputIndex, depth, matchWeight, skipPos, + excessivePos, transposedPos, freq, sameLength); + if (!isSameAsTyped) + addWord(word, depth + 1, finalFreq); + if (hasAlternates) + addWordAlternatesSpellings(DICT_ROOT, pos, flags, finalFreq); + } + + if (sameLength && depth >= mInputLength && skipPos < 0) { + registerNextLetter(word[mInputLength], nextLetters, nextLettersSize); + } +} + +#ifndef NEW_DICTIONARY_FORMAT +// TODO: Don't forget to bring inline functions back to over where they are used. + +// The following functions will be entirely replaced with new implementations. +void UnigramDictionary::getWordsOld(const int initialPos, const int inputLength, const int skipPos, + const int excessivePos, const int transposedPos,int *nextLetters, + const int nextLettersSize) { + int initialPosition = initialPos; + const int count = Dictionary::getCount(DICT_ROOT, &initialPosition); + getWordsRec(count, initialPosition, 0, + min(inputLength * MAX_DEPTH_MULTIPLIER, MAX_WORD_LENGTH), + mInputLength <= 0, 1, 0, 0, skipPos, excessivePos, transposedPos, nextLetters, + nextLettersSize); +} + +void UnigramDictionary::getWordsRec(const int childrenCount, const int pos, const int depth, + const int maxDepth, const bool traverseAllNodes, const int matchWeight, + const int inputIndex, const int diffs, const int skipPos, const int excessivePos, + const int transposedPos, int *nextLetters, const int nextLettersSize) { + int siblingPos = pos; + for (int i = 0; i < childrenCount; ++i) { + int newCount; + int newChildPosition; + bool newTraverseAllNodes; + int newMatchRate; + int newInputIndex; + int newDiffs; + int newSiblingPos; + int newOutputIndex; + const bool needsToTraverseChildrenNodes = processCurrentNode(siblingPos, depth, maxDepth, + traverseAllNodes, matchWeight, inputIndex, diffs, + skipPos, excessivePos, transposedPos, + nextLetters, nextLettersSize, + &newCount, &newChildPosition, &newTraverseAllNodes, &newMatchRate, + &newInputIndex, &newDiffs, &newSiblingPos, &newOutputIndex); + siblingPos = newSiblingPos; + + if (needsToTraverseChildrenNodes) { + getWordsRec(newCount, newChildPosition, newOutputIndex, maxDepth, newTraverseAllNodes, + newMatchRate, newInputIndex, newDiffs, skipPos, excessivePos, transposedPos, + nextLetters, nextLettersSize); + } + } +} + +inline int UnigramDictionary::getBestWordFreq(const int startInputIndex, const int inputLength, + unsigned short *word) { + int pos = ROOT_POS; + int count = Dictionary::getCount(DICT_ROOT, &pos); + int maxFreq = 0; + int depth = 0; + unsigned short newWord[MAX_WORD_LENGTH_INTERNAL]; + bool terminal = false; + + mStackChildCount[0] = count; + mStackSiblingPos[0] = pos; + + while (depth >= 0) { + if (mStackChildCount[depth] > 0) { + --mStackChildCount[depth]; + int firstChildPos; + int newFreq; + int siblingPos = mStackSiblingPos[depth]; + const bool needsToTraverseChildrenNodes = processCurrentNodeForExactMatch(siblingPos, + startInputIndex, depth, newWord, &firstChildPos, &count, &terminal, &newFreq, + &siblingPos); + mStackSiblingPos[depth] = siblingPos; + if (depth == (inputLength - 1)) { + // Traverse sibling node + if (terminal) { + if (newFreq > maxFreq) { + for (int i = 0; i < inputLength; ++i) word[i] = newWord[i]; + if (DEBUG_DICT && DEBUG_NODE) { + char s[inputLength + 1]; + for (int i = 0; i < inputLength; ++i) s[i] = word[i]; + s[inputLength] = 0; + LOGI("New missing space word found: %d > %d (%s), %d, %d", + newFreq, maxFreq, s, inputLength, depth); + } + maxFreq = newFreq; + } + } + } else if (needsToTraverseChildrenNodes) { + // Traverse children nodes + ++depth; + mStackChildCount[depth] = count; + mStackSiblingPos[depth] = firstChildPos; + } + } else { + // Traverse parent node + --depth; + } + } + + word[inputLength] = 0; + return maxFreq; +} + +inline bool UnigramDictionary::processCurrentNodeForExactMatch(const int firstChildPos, + const int startInputIndex, const int depth, unsigned short *word, int *newChildPosition, + int *newCount, bool *newTerminal, int *newFreq, int *siblingPos) { + const int inputIndex = startInputIndex + depth; + const int *currentChars = getInputCharsAt(inputIndex); + unsigned short c; + *siblingPos = Dictionary::setDictionaryValues(DICT_ROOT, IS_LATEST_DICT_VERSION, firstChildPos, + &c, newChildPosition, newTerminal, newFreq); + const unsigned int inputC = currentChars[0]; + if (DEBUG_DICT) { + assert(inputC <= U_SHORT_MAX); + } + const unsigned short baseLowerC = toBaseLowerCase(c); + const bool matched = (inputC == baseLowerC || inputC == c); + const bool hasChild = *newChildPosition != 0; + if (matched) { + word[depth] = c; + if (DEBUG_DICT && DEBUG_NODE) { + LOGI("Node(%c, %c)<%d>, %d, %d", inputC, c, matched, hasChild, *newFreq); + if (*newTerminal) { + LOGI("Terminal %d", *newFreq); + } + } + if (hasChild) { + *newCount = Dictionary::getCount(DICT_ROOT, newChildPosition); + return true; + } else { + return false; + } + } else { + // If this node is not user typed character, this method treats this word as unmatched. + // Thus newTerminal shouldn't be true. + *newTerminal = false; + return false; + } +} + +// TODO: use uint32_t instead of unsigned short +bool UnigramDictionary::isValidWord(unsigned short *word, int length) { + if (IS_LATEST_DICT_VERSION) { + return (getBigramPosition(DICTIONARY_HEADER_SIZE, word, 0, length) != NOT_VALID_WORD); + } else { + return (getBigramPosition(0, word, 0, length) != NOT_VALID_WORD); + } +} + + +// Require strict exact match. +int UnigramDictionary::getBigramPosition(int pos, unsigned short *word, int offset, + int length) const { + // returns address of bigram data of that word + // return -99 if not found + + int count = Dictionary::getCount(DICT_ROOT, &pos); + unsigned short currentChar = (unsigned short) word[offset]; + for (int j = 0; j < count; j++) { + unsigned short c = Dictionary::getChar(DICT_ROOT, &pos); + int terminal = Dictionary::getTerminal(DICT_ROOT, &pos); + int childPos = Dictionary::getAddress(DICT_ROOT, &pos); + if (c == currentChar) { + if (offset == length - 1) { + if (terminal) { + return (pos+1); + } + } else { + if (childPos != 0) { + int t = getBigramPosition(childPos, word, offset + 1, length); + if (t > 0) { + return t; + } + } + } + } + if (terminal) { + Dictionary::getFreq(DICT_ROOT, IS_LATEST_DICT_VERSION, &pos); + } + // There could be two instances of each alphabet - upper and lower case. So continue + // looking ... + } + return NOT_VALID_WORD; +} + + +// The following functions will be modified. +bool UnigramDictionary::getSplitTwoWordsSuggestion(const int inputLength, + const int firstWordStartPos, const int firstWordLength, const int secondWordStartPos, + const int secondWordLength, const bool isSpaceProximity) { + if (inputLength >= MAX_WORD_LENGTH) return false; + if (0 >= firstWordLength || 0 >= secondWordLength || firstWordStartPos >= secondWordStartPos + || firstWordStartPos < 0 || secondWordStartPos + secondWordLength > inputLength) + return false; + const int newWordLength = firstWordLength + secondWordLength + 1; + // Allocating variable length array on stack + unsigned short word[newWordLength]; + const int firstFreq = getBestWordFreq(firstWordStartPos, firstWordLength, mWord); + if (DEBUG_DICT) { + LOGI("First freq: %d", firstFreq); + } + if (firstFreq <= 0) return false; + + for (int i = 0; i < firstWordLength; ++i) { + word[i] = mWord[i]; + } + + const int secondFreq = getBestWordFreq(secondWordStartPos, secondWordLength, mWord); + if (DEBUG_DICT) { + LOGI("Second freq: %d", secondFreq); + } + if (secondFreq <= 0) return false; + + word[firstWordLength] = SPACE; + for (int i = (firstWordLength + 1); i < newWordLength; ++i) { + word[i] = mWord[i - firstWordLength - 1]; + } + + int pairFreq = calcFreqForSplitTwoWords(TYPED_LETTER_MULTIPLIER, firstWordLength, + secondWordLength, firstFreq, secondFreq, isSpaceProximity); + if (DEBUG_DICT) { + LOGI("Split two words: %d, %d, %d, %d, %d", firstFreq, secondFreq, pairFreq, inputLength, + TYPED_LETTER_MULTIPLIER); + } + addWord(word, newWordLength, pairFreq); + return true; +} + +inline bool UnigramDictionary::processCurrentNode(const int pos, const int depth, + const int maxDepth, const bool traverseAllNodes, int matchWeight, int inputIndex, + const int diffs, const int skipPos, const int excessivePos, const int transposedPos, + int *nextLetters, const int nextLettersSize, int *newCount, int *newChildPosition, + bool *newTraverseAllNodes, int *newMatchRate, int *newInputIndex, int *newDiffs, + int *nextSiblingPosition, int *nextOutputIndex) { + if (DEBUG_DICT) { + int inputCount = 0; + if (skipPos >= 0) ++inputCount; + if (excessivePos >= 0) ++inputCount; + if (transposedPos >= 0) ++inputCount; + assert(inputCount <= 1); + } + unsigned short c; + int childPosition; + bool terminal; + int freq; + bool isSameAsUserTypedLength = false; + + const uint8_t flags = 0; // No flags for now + + if (excessivePos == depth && inputIndex < mInputLength - 1) ++inputIndex; + + *nextSiblingPosition = Dictionary::setDictionaryValues(DICT_ROOT, IS_LATEST_DICT_VERSION, pos, + &c, &childPosition, &terminal, &freq); + *nextOutputIndex = depth + 1; + + const bool needsToTraverseChildrenNodes = childPosition != 0; + + // If we are only doing traverseAllNodes, no need to look at the typed characters. + if (traverseAllNodes || needsToSkipCurrentNode(c, inputIndex, skipPos, depth)) { + mWord[depth] = c; + if (traverseAllNodes && terminal) { + onTerminal(mWord, depth, DICT_ROOT, flags, pos, inputIndex, matchWeight, skipPos, + excessivePos, transposedPos, freq, false, nextLetters, nextLettersSize); + } + if (!needsToTraverseChildrenNodes) return false; + *newTraverseAllNodes = traverseAllNodes; + *newMatchRate = matchWeight; + *newDiffs = diffs; + *newInputIndex = inputIndex; + } else { + const int *currentChars = getInputCharsAt(inputIndex); + + if (transposedPos >= 0) { + if (inputIndex == transposedPos) currentChars += MAX_PROXIMITY_CHARS; + if (inputIndex == (transposedPos + 1)) currentChars -= MAX_PROXIMITY_CHARS; + } + + int matchedProximityCharId = getMatchedProximityId(currentChars, c, skipPos, excessivePos, + transposedPos); + if (UNRELATED_CHAR == matchedProximityCharId) return false; + mWord[depth] = c; + // If inputIndex is greater than mInputLength, that means there is no + // proximity chars. So, we don't need to check proximity. + if (SAME_OR_ACCENTED_OR_CAPITALIZED_CHAR == matchedProximityCharId) { + multiplyIntCapped(TYPED_LETTER_MULTIPLIER, &matchWeight); + } + bool isSameAsUserTypedLength = mInputLength == inputIndex + 1 + || (excessivePos == mInputLength - 1 && inputIndex == mInputLength - 2); + if (isSameAsUserTypedLength && terminal) { + onTerminal(mWord, depth, DICT_ROOT, flags, pos, inputIndex, matchWeight, skipPos, + excessivePos, transposedPos, freq, true, nextLetters, nextLettersSize); + } + if (!needsToTraverseChildrenNodes) return false; + // Start traversing all nodes after the index exceeds the user typed length + *newTraverseAllNodes = isSameAsUserTypedLength; + *newMatchRate = matchWeight; + *newDiffs = diffs + ((NEAR_PROXIMITY_CHAR == matchedProximityCharId) ? 1 : 0); + *newInputIndex = inputIndex + 1; + } + // Optimization: Prune out words that are too long compared to how much was typed. + if (depth >= maxDepth || *newDiffs > mMaxEditDistance) { + return false; + } + + // If inputIndex is greater than mInputLength, that means there are no proximity chars. + // TODO: Check if this can be isSameAsUserTypedLength only. + if (isSameAsUserTypedLength || mInputLength <= *newInputIndex) { + *newTraverseAllNodes = true; + } + // get the count of nodes and increment childAddress. + *newCount = Dictionary::getCount(DICT_ROOT, &childPosition); + *newChildPosition = childPosition; + if (DEBUG_DICT) assert(needsToTraverseChildrenNodes); + return needsToTraverseChildrenNodes; +} + +#else // NEW_DICTIONARY_FORMAT + +bool UnigramDictionary::getSplitTwoWordsSuggestion(const int inputLength, + const int firstWordStartPos, const int firstWordLength, const int secondWordStartPos, + const int secondWordLength, const bool isSpaceProximity) { + if (inputLength >= MAX_WORD_LENGTH) return false; + if (0 >= firstWordLength || 0 >= secondWordLength || firstWordStartPos >= secondWordStartPos + || firstWordStartPos < 0 || secondWordStartPos + secondWordLength > inputLength) + return false; + const int newWordLength = firstWordLength + secondWordLength + 1; + // Allocating variable length array on stack + unsigned short word[newWordLength]; + const int firstFreq = getBestWordFreq(firstWordStartPos, firstWordLength, mWord); + if (DEBUG_DICT) { + LOGI("First freq: %d", firstFreq); + } + if (firstFreq <= 0) return false; + + for (int i = 0; i < firstWordLength; ++i) { + word[i] = mWord[i]; + } + + const int secondFreq = getBestWordFreq(secondWordStartPos, secondWordLength, mWord); + if (DEBUG_DICT) { + LOGI("Second freq: %d", secondFreq); + } + if (secondFreq <= 0) return false; + + word[firstWordLength] = SPACE; + for (int i = (firstWordLength + 1); i < newWordLength; ++i) { + word[i] = mWord[i - firstWordLength - 1]; + } + + int pairFreq = calcFreqForSplitTwoWords(TYPED_LETTER_MULTIPLIER, firstWordLength, + secondWordLength, firstFreq, secondFreq, isSpaceProximity); + if (DEBUG_DICT) { + LOGI("Split two words: %d, %d, %d, %d, %d", firstFreq, secondFreq, pairFreq, inputLength, + TYPED_LETTER_MULTIPLIER); + } + addWord(word, newWordLength, pairFreq); + return true; +} + +inline bool UnigramDictionary::processCurrentNode(const int pos, const int depth, + const int maxDepth, const bool traverseAllNodes, int matchWeight, int inputIndex, + const int diffs, const int skipPos, const int excessivePos, const int transposedPos, + int *nextLetters, const int nextLettersSize, int *newCount, int *newChildPosition, + bool *newTraverseAllNodes, int *newMatchRate, int *newInputIndex, int *newDiffs, + int *nextSiblingPosition, int *nextOutputIndex) { + if (DEBUG_DICT) { + int inputCount = 0; + if (skipPos >= 0) ++inputCount; + if (excessivePos >= 0) ++inputCount; + if (transposedPos >= 0) ++inputCount; + assert(inputCount <= 1); + } + unsigned short c; + int childPosition; + bool terminal; + int freq; + bool isSameAsUserTypedLength = false; + + const uint8_t flags = 0; // No flags for now + + if (excessivePos == depth && inputIndex < mInputLength - 1) ++inputIndex; + + *nextSiblingPosition = Dictionary::setDictionaryValues(DICT_ROOT, IS_LATEST_DICT_VERSION, pos, + &c, &childPosition, &terminal, &freq); + *nextOutputIndex = depth + 1; + + const bool needsToTraverseChildrenNodes = childPosition != 0; + + // If we are only doing traverseAllNodes, no need to look at the typed characters. + if (traverseAllNodes || needsToSkipCurrentNode(c, inputIndex, skipPos, depth)) { + mWord[depth] = c; + if (traverseAllNodes && terminal) { + onTerminal(mWord, depth, DICT_ROOT, flags, pos, inputIndex, matchWeight, skipPos, + excessivePos, transposedPos, freq, false, nextLetters, nextLettersSize); + } + if (!needsToTraverseChildrenNodes) return false; + *newTraverseAllNodes = traverseAllNodes; + *newMatchRate = matchWeight; + *newDiffs = diffs; + *newInputIndex = inputIndex; + } else { + const int *currentChars = getInputCharsAt(inputIndex); + + if (transposedPos >= 0) { + if (inputIndex == transposedPos) currentChars += MAX_PROXIMITY_CHARS; + if (inputIndex == (transposedPos + 1)) currentChars -= MAX_PROXIMITY_CHARS; + } + + int matchedProximityCharId = getMatchedProximityId(currentChars, c, skipPos, excessivePos, + transposedPos); + if (UNRELATED_CHAR == matchedProximityCharId) return false; + mWord[depth] = c; + // If inputIndex is greater than mInputLength, that means there is no + // proximity chars. So, we don't need to check proximity. + if (SAME_OR_ACCENTED_OR_CAPITALIZED_CHAR == matchedProximityCharId) { + multiplyIntCapped(TYPED_LETTER_MULTIPLIER, &matchWeight); + } + bool isSameAsUserTypedLength = mInputLength == inputIndex + 1 + || (excessivePos == mInputLength - 1 && inputIndex == mInputLength - 2); + if (isSameAsUserTypedLength && terminal) { + onTerminal(mWord, depth, DICT_ROOT, flags, pos, inputIndex, matchWeight, skipPos, + excessivePos, transposedPos, freq, true, nextLetters, nextLettersSize); + } + if (!needsToTraverseChildrenNodes) return false; + // Start traversing all nodes after the index exceeds the user typed length + *newTraverseAllNodes = isSameAsUserTypedLength; + *newMatchRate = matchWeight; + *newDiffs = diffs + ((NEAR_PROXIMITY_CHAR == matchedProximityCharId) ? 1 : 0); + *newInputIndex = inputIndex + 1; + } + // Optimization: Prune out words that are too long compared to how much was typed. + if (depth >= maxDepth || *newDiffs > mMaxEditDistance) { + return false; + } + + // If inputIndex is greater than mInputLength, that means there are no proximity chars. + // TODO: Check if this can be isSameAsUserTypedLength only. + if (isSameAsUserTypedLength || mInputLength <= *newInputIndex) { + *newTraverseAllNodes = true; + } + // get the count of nodes and increment childAddress. + *newCount = Dictionary::getCount(DICT_ROOT, &childPosition); + *newChildPosition = childPosition; + if (DEBUG_DICT) assert(needsToTraverseChildrenNodes); + return needsToTraverseChildrenNodes; +} + +#endif // NEW_DICTIONARY_FORMAT + +} // namespace latinime diff --git a/native/src/unigram_dictionary.h b/native/src/unigram_dictionary.h new file mode 100644 index 000000000..154ac9b36 --- /dev/null +++ b/native/src/unigram_dictionary.h @@ -0,0 +1,152 @@ +/* + * Copyright (C) 2010 The Android Open Source Project + * + * Licensed under the Apache License, Version 2.0 (the "License"); + * you may not use this file except in compliance with the License. + * You may obtain a copy of the License at + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + * See the License for the specific language governing permissions and + * limitations under the License. + */ + +#ifndef LATINIME_UNIGRAM_DICTIONARY_H +#define LATINIME_UNIGRAM_DICTIONARY_H + +#include <stdint.h> +#include "defines.h" +#include "proximity_info.h" + +#ifndef NULL +#define NULL 0 +#endif + +namespace latinime { + +class UnigramDictionary { + + typedef enum { // Used as a return value for character comparison + SAME_OR_ACCENTED_OR_CAPITALIZED_CHAR, // Same char, possibly with different case or accent + NEAR_PROXIMITY_CHAR, // It is a char located nearby on the keyboard + UNRELATED_CHAR // It is an unrelated char + } ProximityType; + +public: + UnigramDictionary(const uint8_t* const streamStart, int typedLetterMultipler, + int fullWordMultiplier, int maxWordLength, int maxWords, int maxProximityChars, + const bool isLatestDictVersion); + bool isValidWord(unsigned short *word, int length); + int getBigramPosition(int pos, unsigned short *word, int offset, int length) const; + int getSuggestions(const ProximityInfo *proximityInfo, const int *xcoordinates, + const int *ycoordinates, const int *codes, const int codesSize, const int flags, + unsigned short *outWords, int *frequencies); + ~UnigramDictionary(); + +private: + void getWordSuggestions(const ProximityInfo *proximityInfo, const int *xcoordinates, + const int *ycoordinates, const int *codes, const int codesSize, + unsigned short *outWords, int *frequencies); + bool isDigraph(const int* codes, const int i, const int codesSize) const; + void getWordWithDigraphSuggestionsRec(const ProximityInfo *proximityInfo, + const int *xcoordinates, const int* ycoordinates, const int *codesBuffer, + const int codesBufferSize, const int flags, const int* codesSrc, const int codesRemain, + const int currentDepth, int* codesDest, unsigned short* outWords, int* frequencies); + void initSuggestions(const int *codes, const int codesSize, unsigned short *outWords, + int *frequencies); + void getSuggestionCandidates(const int skipPos, const int excessivePos, + const int transposedPos, int *nextLetters, const int nextLettersSize, + const int maxDepth); + void getVersionNumber(); + bool checkIfDictVersionIsLatest(); + int getAddress(int *pos); + int getFreq(int *pos); + bool sameAsTyped(const unsigned short *word, int length) const; + bool addWord(unsigned short *word, int length, int frequency); + void addWordAlternatesSpellings(const uint8_t* const root, int pos, int depth, int finalFreq); + void getWordsRec(const int childrenCount, const int pos, const int depth, const int maxDepth, + const bool traverseAllNodes, const int snr, const int inputIndex, const int diffs, + const int skipPos, const int excessivePos, const int transposedPos, int *nextLetters, + const int nextLettersSize); + bool getSplitTwoWordsSuggestion(const int inputLength, + const int firstWordStartPos, const int firstWordLength, + const int secondWordStartPos, const int secondWordLength, const bool isSpaceProximity); + bool getMissingSpaceWords(const int inputLength, const int missingSpacePos); + bool getMistypedSpaceWords(const int inputLength, const int spaceProximityPos); + // Keep getWordsOld for comparing performance between getWords and getWordsOld + void getWordsOld(const int initialPos, const int inputLength, const int skipPos, + const int excessivePos, const int transposedPos, int *nextLetters, + const int nextLettersSize); + int calculateFinalFreq(const int inputIndex, const int depth, const int snr, const int skipPos, + const int excessivePos, const int transposedPos, const int freq, + const bool sameLength) const; + void onTerminal(unsigned short int* word, const int depth, + const uint8_t* const root, const uint8_t flags, int pos, + const int inputIndex, const int matchWeight, const int skipPos, + const int excessivePos, const int transposedPos, const int freq, const bool sameLength, + int *nextLetters, const int nextLettersSize); + bool needsToSkipCurrentNode(const unsigned short c, + const int inputIndex, const int skipPos, const int depth); + ProximityType getMatchedProximityId(const int *currentChars, const unsigned short c, + const int skipPos, const int excessivePos, const int transposedPos); + // Process a node by considering proximity, missing and excessive character + bool processCurrentNode(const int pos, const int depth, + const int maxDepth, const bool traverseAllNodes, const int snr, int inputIndex, + const int diffs, const int skipPos, const int excessivePos, const int transposedPos, + int *nextLetters, const int nextLettersSize, int *newCount, int *newChildPosition, + bool *newTraverseAllNodes, int *newSnr, int*newInputIndex, int *newDiffs, + int *nextSiblingPosition, int *nextOutputIndex); + int getBestWordFreq(const int startInputIndex, const int inputLength, unsigned short *word); + // Process a node by considering missing space + bool processCurrentNodeForExactMatch(const int firstChildPos, + const int startInputIndex, const int depth, unsigned short *word, + int *newChildPosition, int *newCount, bool *newTerminal, int *newFreq, int *siblingPos); + bool existsAdjacentProximityChars(const int inputIndex, const int inputLength) const; + inline const int* getInputCharsAt(const int index) const { + return mInputCodes + (index * MAX_PROXIMITY_CHARS); + } + + const uint8_t* const DICT_ROOT; + const int MAX_WORD_LENGTH; + const int MAX_WORDS; + const int MAX_PROXIMITY_CHARS; + const bool IS_LATEST_DICT_VERSION; + const int TYPED_LETTER_MULTIPLIER; + const int FULL_WORD_MULTIPLIER; + const int ROOT_POS; + const unsigned int BYTES_IN_ONE_CHAR; + const int MAX_UMLAUT_SEARCH_DEPTH; + + // Flags for special processing + // Those *must* match the flags in BinaryDictionary.Flags.ALL_FLAGS in BinaryDictionary.java + // or something very bad (like, the apocalypse) will happen. + // Please update both at the same time. + enum { + REQUIRES_GERMAN_UMLAUT_PROCESSING = 0x1 + }; + static const struct digraph_t { int first; int second; } GERMAN_UMLAUT_DIGRAPHS[]; + + int *mFrequencies; + unsigned short *mOutputChars; + const int *mInputCodes; + int mInputLength; + // MAX_WORD_LENGTH_INTERNAL must be bigger than MAX_WORD_LENGTH + unsigned short mWord[MAX_WORD_LENGTH_INTERNAL]; + int mMaxEditDistance; + + int mStackChildCount[MAX_WORD_LENGTH_INTERNAL]; + bool mStackTraverseAll[MAX_WORD_LENGTH_INTERNAL]; + int mStackNodeFreq[MAX_WORD_LENGTH_INTERNAL]; + int mStackInputIndex[MAX_WORD_LENGTH_INTERNAL]; + int mStackDiffs[MAX_WORD_LENGTH_INTERNAL]; + int mStackSiblingPos[MAX_WORD_LENGTH_INTERNAL]; + int mStackOutputIndex[MAX_WORD_LENGTH_INTERNAL]; + int mNextLettersFrequency[NEXT_LETTERS_SIZE]; +}; + +} // namespace latinime + +#endif // LATINIME_UNIGRAM_DICTIONARY_H |