aboutsummaryrefslogtreecommitdiffstats
path: root/native/src
diff options
context:
space:
mode:
Diffstat (limited to 'native/src')
-rw-r--r--native/src/bigram_dictionary.cpp254
-rw-r--r--native/src/bigram_dictionary.h55
-rw-r--r--native/src/defines.h156
-rw-r--r--native/src/dictionary.cpp561
-rw-r--r--native/src/dictionary.h190
-rw-r--r--native/src/unigram_dictionary.cpp622
-rw-r--r--native/src/unigram_dictionary.h118
7 files changed, 1357 insertions, 599 deletions
diff --git a/native/src/bigram_dictionary.cpp b/native/src/bigram_dictionary.cpp
new file mode 100644
index 000000000..5ec310f07
--- /dev/null
+++ b/native/src/bigram_dictionary.cpp
@@ -0,0 +1,254 @@
+/*
+**
+** 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");
+ if (DEBUG_DICT) 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->isValidWordRec(
+ DICTIONARY_HEADER_SIZE, prevWord, 0, 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..d658b93e6
--- /dev/null
+++ b/native/src/bigram_dictionary.h
@@ -0,0 +1,55 @@
+/*
+ * 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/defines.h b/native/src/defines.h
new file mode 100644
index 000000000..c1eaf0df2
--- /dev/null
+++ b/native/src/defines.h
@@ -0,0 +1,156 @@
+/*
+**
+** 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
+
+// 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
+#define LOGI
+#define DEBUG_DICT false
+#define DEBUG_DICT_FULL false
+#define DEBUG_SHOW_FOUND_WORD false
+#define DEBUG_NODE false
+#define DEBUG_TRACE 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
+
+// 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 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
+
+// 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 75
+#define WORDS_WITH_MISSING_SPACE_CHARACTER_DEMOTION_RATE 80
+#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
+
+// This is used as a bare multiplier (not subject to /100)
+#define FULL_MATCH_ACCENTS_OR_CAPITALIZATION_DIFFER_MULTIPLIER 2
+
+// 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
+
+// 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
+
+#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..fe3375706 100644
--- a/native/src/dictionary.cpp
+++ b/native/src/dictionary.cpp
@@ -16,559 +16,62 @@
*/
#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);
-
- 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;
+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) {
- 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;
- }
- inputCodes += mMaxAlternatives;
- word++;
- }
- return true;
-}
-
-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;
- }
- }
- }
-}
-
-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;
-}
-
-int
-Dictionary::getBigramFreq(int *pos)
-{
- int freq = mDict[(*pos)++] & FLAG_BIGRAM_FREQ;
-
- return freq;
-}
-
-
-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++;
- }
+ 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));
}
-
- return bigramCount;
}
- return 0;
+ 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);
}
-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);
- }
+Dictionary::~Dictionary() {
+ delete mUnigramDictionary;
+ delete mBigramDictionary;
}
-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::hasBigram() {
+ return ((mDict[1] & 0xFF) == 1);
}
-bool
-Dictionary::isValidWord(unsigned short *word, int length)
+// TODO: use uint16_t instead of unsigned short
+bool Dictionary::isValidWord(unsigned short *word, int length)
{
- if (checkIfDictVersionIsLatest()) {
+ if (IS_LATEST_DICT_VERSION) {
return (isValidWordRec(DICTIONARY_HEADER_SIZE, word, 0, length) != NOT_VALID_WORD);
} else {
return (isValidWordRec(0, word, 0, length) != NOT_VALID_WORD);
}
}
-int
-Dictionary::isValidWordRec(int pos, unsigned short *word, int offset, int 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);
+ int count = Dictionary::getCount(mDict, &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);
+ unsigned short c = Dictionary::getChar(mDict, &pos);
+ int terminal = Dictionary::getTerminal(mDict, &pos);
+ int childPos = Dictionary::getAddress(mDict, &pos);
if (c == currentChar) {
if (offset == length - 1) {
if (terminal) {
@@ -584,13 +87,11 @@ Dictionary::isValidWordRec(int pos, unsigned short *word, int offset, int length
}
}
if (terminal) {
- getFreq(&pos);
+ Dictionary::getFreq(mDict, IS_LATEST_DICT_VERSION, &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..cef1cf9eb 100644
--- a/native/src/dictionary.h
+++ b/native/src/dictionary.h
@@ -17,90 +17,142 @@
#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 "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);
+ Dictionary(void *dict, int dictSize, int mmapFd, int dictBufAdjust, int typedLetterMultipler,
+ int fullWordMultiplier, int maxWordLength, int maxWords, int maxAlternatives);
int getSuggestions(int *codes, int codesSize, unsigned short *outWords, int *frequencies,
- int maxWordLength, int maxWords, int maxAlternatives, int skipPos,
- int *nextLetters, int nextLettersSize);
+ int *nextLetters, int nextLettersSize) {
+ return mUnigramDictionary->getSuggestions(codes, codesSize, outWords, frequencies,
+ nextLetters, nextLettersSize);
+ }
+
+ // 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; }
+ int isValidWordRec(int pos, unsigned short *word, int offset, int length);
+ 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);
+
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;
};
// ----------------------------------------------------------------------------
+// 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/unigram_dictionary.cpp b/native/src/unigram_dictionary.cpp
new file mode 100644
index 000000000..dfbe8228e
--- /dev/null
+++ b/native/src/unigram_dictionary.cpp
@@ -0,0 +1,622 @@
+/*
+**
+** 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 <fcntl.h>
+#include <stdio.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 {
+
+UnigramDictionary::UnigramDictionary(const unsigned char *dict, int typedLetterMultiplier,
+ int fullWordMultiplier, int maxWordLength, int maxWords, int maxProximityChars,
+ const bool isLatestDictVersion)
+ : DICT(dict), 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) {
+ if (DEBUG_DICT) LOGI("UnigramDictionary - constructor");
+}
+
+UnigramDictionary::~UnigramDictionary() {}
+
+int UnigramDictionary::getSuggestions(int *codes, int codesSize, unsigned short *outWords,
+ int *frequencies, int *nextLetters, int nextLettersSize) {
+ 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, nextLetters, nextLettersSize, 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);
+ // 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 < nextLettersSize; k++) {
+ if (nextLetters[k] > 0) {
+ LOGI("%c = %d,", k, nextLetters[k]);
+ }
+ }
+ }
+ PROF_END(6);
+ PROF_CLOSE;
+ return suggestedWordsCount;
+}
+
+void UnigramDictionary::initSuggestions(int *codes, 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;
+}
+
+void UnigramDictionary::registerNextLetter(
+ unsigned short c, int *nextLetters, int nextLettersSize) {
+ if (c < nextLettersSize) {
+ nextLetters[c]++;
+ }
+}
+
+// TODO: We need to optimize addWord by using STL or something
+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) {
+ if (frequency > mFrequencies[insertAt] || (mFrequencies[insertAt] == frequency
+ && length < Dictionary::wideStrLen(mOutputChars + insertAt * MAX_WORD_LENGTH))) {
+ 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", s, frequency);
+ }
+ 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;
+}
+
+unsigned short UnigramDictionary::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 UnigramDictionary::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;
+ }
+ 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, &rootPosition);
+ int depth = 0;
+
+ mStackChildCount[0] = childCount;
+ mStackTraverseAll[0] = (mInputLength <= 0);
+ mStackNodeFreq[0] = 1;
+ mStackInputIndex[0] = 0;
+ mStackDiffs[0] = 0;
+ mStackSiblingPos[0] = rootPosition;
+
+ // Depth first search
+ while (depth >= 0) {
+ if (mStackChildCount[depth] > 0) {
+ --mStackChildCount[depth];
+ bool traverseAllNodes = mStackTraverseAll[depth];
+ int snr = mStackNodeFreq[depth];
+ int inputIndex = mStackInputIndex[depth];
+ int diffs = mStackDiffs[depth];
+ int siblingPos = mStackSiblingPos[depth];
+ int firstChildPos;
+ // depth will never be greater than maxDepth because in that case,
+ // needsToTraverseChildrenNodes should be false
+ const bool needsToTraverseChildrenNodes = processCurrentNode(siblingPos, depth,
+ maxDepth, traverseAllNodes, snr, inputIndex, diffs, skipPos, excessivePos,
+ transposedPos, nextLetters, nextLettersSize, &childCount, &firstChildPos,
+ &traverseAllNodes, &snr, &inputIndex, &diffs, &siblingPos);
+ // Update next sibling pos
+ mStackSiblingPos[depth] = siblingPos;
+ if (needsToTraverseChildrenNodes) {
+ // Goes to child node
+ ++depth;
+ mStackChildCount[depth] = childCount;
+ mStackTraverseAll[depth] = traverseAllNodes;
+ mStackNodeFreq[depth] = snr;
+ mStackInputIndex[depth] = inputIndex;
+ mStackDiffs[depth] = diffs;
+ mStackSiblingPos[depth] = firstChildPos;
+ }
+ } else {
+ // Goes to parent sibling node
+ --depth;
+ }
+ }
+}
+
+inline static void multiplyRate(const int rate, int *freq) {
+ if (rate > 1000000) {
+ *freq = (*freq / 100) * rate;
+ } else {
+ *freq = *freq * rate / 100;
+ }
+}
+
+bool UnigramDictionary::getMissingSpaceWords(const int inputLength, const int missingSpacePos) {
+ if (missingSpacePos <= 0 || missingSpacePos >= inputLength
+ || inputLength >= MAX_WORD_LENGTH) return false;
+ const int newWordLength = inputLength + 1;
+ // Allocating variable length array on stack
+ unsigned short word[newWordLength];
+ const int firstFreq = getBestWordFreq(0, missingSpacePos, mWord);
+ if (DEBUG_DICT) LOGI("First freq: %d", firstFreq);
+ if (firstFreq <= 0) return false;
+
+ for (int i = 0; i < missingSpacePos; ++i) {
+ word[i] = mWord[i];
+ }
+
+ const int secondFreq = getBestWordFreq(missingSpacePos, inputLength - missingSpacePos, mWord);
+ if (DEBUG_DICT) LOGI("Second freq: %d", secondFreq);
+ if (secondFreq <= 0) return false;
+
+ word[missingSpacePos] = SPACE;
+ for (int i = (missingSpacePos + 1); i < newWordLength; ++i) {
+ word[i] = mWord[i - missingSpacePos - 1];
+ }
+
+ int pairFreq = ((firstFreq + secondFreq) / 2);
+ for (int i = 0; i < inputLength; ++i) pairFreq *= TYPED_LETTER_MULTIPLIER;
+ multiplyRate(WORDS_WITH_MISSING_SPACE_CHARACTER_DEMOTION_RATE, &pairFreq);
+ addWord(word, newWordLength, pairFreq);
+ return true;
+}
+
+// Keep this for comparing spec to new getWords
+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, &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 snr, 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;
+ const int newDepth = depth + 1;
+ bool newTraverseAllNodes;
+ int newSnr;
+ int newInputIndex;
+ int newDiffs;
+ int newSiblingPos;
+ const bool needsToTraverseChildrenNodes = processCurrentNode(siblingPos, depth, maxDepth,
+ traverseAllNodes, snr, inputIndex, diffs, skipPos, excessivePos, transposedPos,
+ nextLetters, nextLettersSize,
+ &newCount, &newChildPosition, &newTraverseAllNodes, &newSnr,
+ &newInputIndex, &newDiffs, &newSiblingPos);
+ siblingPos = newSiblingPos;
+
+ if (needsToTraverseChildrenNodes) {
+ getWordsRec(newCount, newChildPosition, newDepth, maxDepth, newTraverseAllNodes,
+ newSnr, newInputIndex, newDiffs, skipPos, excessivePos, transposedPos,
+ nextLetters, nextLettersSize);
+ }
+ }
+}
+
+inline int UnigramDictionary::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) {
+ // TODO: Demote by edit distance
+ int finalFreq = freq * snr;
+ if (skipPos >= 0) multiplyRate(WORDS_WITH_MISSING_CHARACTER_DEMOTION_RATE, &finalFreq);
+ 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;
+ for (int i = 0; i < depth; ++i) lengthFreq *= TYPED_LETTER_MULTIPLIER;
+ if (lengthFreq == snr) {
+ 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 *= FULL_MATCH_ACCENTS_OR_CAPITALIZATION_DIFFER_MULTIPLIER;
+ }
+ }
+ if (sameLength && skipPos < 0) finalFreq *= FULL_WORD_MULTIPLIER;
+ return finalFreq;
+}
+
+inline void UnigramDictionary::onTerminalWhenUserTypedLengthIsGreaterThanInputLength(
+ unsigned short *word, const int inputIndex, const int depth, const int snr,
+ int *nextLetters, const int nextLettersSize, const int skipPos, const int excessivePos,
+ const int transposedPos, const int freq) {
+ const int finalFreq = calculateFinalFreq(inputIndex, depth, snr, skipPos, excessivePos,
+ transposedPos, freq, false);
+ if (depth >= MIN_SUGGEST_DEPTH) addWord(word, depth + 1, finalFreq);
+ if (depth >= mInputLength && skipPos < 0) {
+ registerNextLetter(mWord[mInputLength], nextLetters, nextLettersSize);
+ }
+}
+
+inline void UnigramDictionary::onTerminalWhenUserTypedLengthIsSameAsInputLength(
+ unsigned short *word, const int inputIndex, const int depth, const int snr,
+ const int skipPos, const int excessivePos, const int transposedPos, const int freq) {
+ if (sameAsTyped(word, depth + 1)) return;
+ const int finalFreq = calculateFinalFreq(inputIndex, depth, snr, skipPos,
+ excessivePos, transposedPos, freq, true);
+ // Proximity collection will promote a word of the same length as what user typed.
+ if (depth >= MIN_SUGGEST_DEPTH) addWord(word, depth + 1, finalFreq);
+}
+
+inline bool UnigramDictionary::needsToSkipCurrentNode(const unsigned short c,
+ const int inputIndex, const int skipPos, const int depth) {
+ const unsigned short userTypedChar = (mInputCodes + (inputIndex * MAX_PROXIMITY_CHARS))[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) {
+ if (inputIndex < 0 || inputIndex >= inputLength) return false;
+ const int currentChar = *getInputCharsAt(inputIndex);
+ const int leftIndex = inputIndex - 1;
+ if (leftIndex >= 0) {
+ 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) {
+ int *rightChars = getInputCharsAt(rightIndex);
+ int i = 0;
+ while (rightChars[i] > 0 && i < MAX_PROXIMITY_CHARS) {
+ if (rightChars[i++] == currentChar) return true;
+ }
+ }
+ return false;
+}
+
+inline UnigramDictionary::ProximityType UnigramDictionary::getMatchedProximityId(
+ const int *currentChars, const unsigned short c, const int skipPos,
+ const int excessivePos, const int transposedPos) {
+ const unsigned short lowerC = toLowerCase(c);
+ int j = 0;
+ while (currentChars[j] > 0 && j < MAX_PROXIMITY_CHARS) {
+ const bool matched = (currentChars[j] == lowerC || currentChars[j] == c);
+ // If skipPos is defined, not to search proximity collections.
+ // First char is what user typed.
+ if (matched) {
+ if (j > 0) return NEAR_PROXIMITY_CHAR;
+ return SAME_OR_ACCENTED_OR_CAPITALIZED_CHAR;
+ } else if (skipPos >= 0 || excessivePos >= 0 || transposedPos >= 0) {
+ // Not to check proximity characters
+ return UNRELATED_CHAR;
+ }
+ ++j;
+ }
+ return UNRELATED_CHAR;
+}
+
+inline bool UnigramDictionary::processCurrentNode(const int pos, const int depth,
+ const int maxDepth, const bool traverseAllNodes, 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) {
+ 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;
+
+ if (excessivePos == depth && inputIndex < mInputLength - 1) ++inputIndex;
+
+ *nextSiblingPosition = Dictionary::setDictionaryValues(DICT, IS_LATEST_DICT_VERSION, pos, &c,
+ &childPosition, &terminal, &freq);
+
+ 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) {
+ onTerminalWhenUserTypedLengthIsGreaterThanInputLength(mWord, inputIndex, depth,
+ snr, nextLetters, nextLettersSize, skipPos, excessivePos, transposedPos, freq);
+ }
+ if (!needsToTraverseChildrenNodes) return false;
+ *newTraverseAllNodes = traverseAllNodes;
+ *newSnr = snr;
+ *newDiffs = diffs;
+ *newInputIndex = inputIndex;
+ } else {
+ int *currentChars = mInputCodes + (inputIndex * MAX_PROXIMITY_CHARS);
+
+ 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) {
+ snr = snr * TYPED_LETTER_MULTIPLIER;
+ }
+ bool isSameAsUserTypedLength = mInputLength == inputIndex + 1
+ || (excessivePos == mInputLength - 1 && inputIndex == mInputLength - 2);
+ if (isSameAsUserTypedLength && terminal) {
+ onTerminalWhenUserTypedLengthIsSameAsInputLength(mWord, inputIndex, depth, snr,
+ skipPos, excessivePos, transposedPos, freq);
+ }
+ if (!needsToTraverseChildrenNodes) return false;
+ // Start traversing all nodes after the index exceeds the user typed length
+ *newTraverseAllNodes = isSameAsUserTypedLength;
+ *newSnr = snr;
+ *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, &childPosition);
+ *newChildPosition = childPosition;
+ if (DEBUG_DICT) assert(needsToTraverseChildrenNodes);
+ return needsToTraverseChildrenNodes;
+}
+
+inline int UnigramDictionary::getBestWordFreq(const int startInputIndex, const int inputLength,
+ unsigned short *word) {
+ int pos = ROOT_POS;
+ int count = Dictionary::getCount(DICT, &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 = mInputCodes + (inputIndex * MAX_PROXIMITY_CHARS);
+ unsigned short c;
+ *siblingPos = Dictionary::setDictionaryValues(DICT, 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 lowerC = toLowerCase(c);
+ const bool matched = (inputC == lowerC || 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, 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;
+ }
+}
+} // namespace latinime
diff --git a/native/src/unigram_dictionary.h b/native/src/unigram_dictionary.h
new file mode 100644
index 000000000..90c98149b
--- /dev/null
+++ b/native/src/unigram_dictionary.h
@@ -0,0 +1,118 @@
+/*
+ * 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 "defines.h"
+
+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 unsigned char *dict, int typedLetterMultipler, int fullWordMultiplier,
+ int maxWordLength, int maxWords, int maxProximityChars, const bool isLatestDictVersion);
+ int getSuggestions(int *codes, int codesSize, unsigned short *outWords, int *frequencies,
+ int *nextLetters, int nextLettersSize);
+ ~UnigramDictionary();
+
+private:
+ void initSuggestions(int *codes, 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);
+ int wideStrLen(unsigned short *str);
+ bool sameAsTyped(unsigned short *word, int length);
+ bool addWord(unsigned short *word, int length, int frequency);
+ unsigned short toLowerCase(unsigned short c);
+ 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 getMissingSpaceWords(const int inputLength, const int missingSpacePos);
+ // 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);
+ void registerNextLetter(unsigned short c, int *nextLetters, 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);
+ void onTerminalWhenUserTypedLengthIsGreaterThanInputLength(unsigned short *word,
+ const int inputIndex, const int depth, const int snr, int *nextLetters,
+ const int nextLettersSize, const int skipPos, const int excessivePos,
+ const int transposedPos, const int freq);
+ void onTerminalWhenUserTypedLengthIsSameAsInputLength(unsigned short *word,
+ const int inputIndex, const int depth, const int snr, const int skipPos,
+ const int excessivePos, const int transposedPos, const int freq);
+ 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 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);
+ int* getInputCharsAt(const int index) {return mInputCodes + (index * MAX_PROXIMITY_CHARS);}
+ const unsigned char *DICT;
+ 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;
+
+ int *mFrequencies;
+ unsigned short *mOutputChars;
+ 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];
+};
+
+// ----------------------------------------------------------------------------
+
+}; // namespace latinime
+
+#endif // LATINIME_UNIGRAM_DICTIONARY_H
generated by cgit v1.2.3-83-g751a (git 2.47.1) at 2025-05-29 01:49:20 +0000