diff options
Diffstat (limited to 'native')
26 files changed, 514 insertions, 105 deletions
diff --git a/native/jni/Android.mk b/native/jni/Android.mk index 0594ddff0..36afea54b 100644 --- a/native/jni/Android.mk +++ b/native/jni/Android.mk @@ -85,6 +85,7 @@ LATIN_IME_CORE_SRC_FILES := \ $(addprefix suggest/policyimpl/dictionary/utils/, \ buffer_with_extendable_buffer.cpp \ byte_array_utils.cpp \ + decaying_utils.cpp \ dict_file_writing_utils.cpp \ format_utils.cpp) \ suggest/policyimpl/gesture/gesture_suggest_policy_factory.cpp \ diff --git a/native/jni/com_android_inputmethod_latin_BinaryDictionary.cpp b/native/jni/com_android_inputmethod_latin_BinaryDictionary.cpp index 85e100e33..c5ef264fc 100644 --- a/native/jni/com_android_inputmethod_latin_BinaryDictionary.cpp +++ b/native/jni/com_android_inputmethod_latin_BinaryDictionary.cpp @@ -113,10 +113,10 @@ static void latinime_BinaryDictionary_flush(JNIEnv *env, jclass clazz, jlong dic } static bool latinime_BinaryDictionary_needsToRunGC(JNIEnv *env, jclass clazz, - jlong dict) { + jlong dict, jboolean mindsBlockByGC) { Dictionary *dictionary = reinterpret_cast<Dictionary *>(dict); if (!dictionary) return false; - return dictionary->needsToRunGC(); + return dictionary->needsToRunGC(mindsBlockByGC == JNI_TRUE); } static void latinime_BinaryDictionary_flushWithGC(JNIEnv *env, jclass clazz, jlong dict, @@ -364,7 +364,7 @@ static const JNINativeMethod sMethods[] = { }, { const_cast<char *>("needsToRunGCNative"), - const_cast<char *>("(J)Z"), + const_cast<char *>("(JZ)Z"), reinterpret_cast<void *>(latinime_BinaryDictionary_needsToRunGC) }, { diff --git a/native/jni/src/defines.h b/native/jni/src/defines.h index 89dfa39b3..c2aa8ba0e 100644 --- a/native/jni/src/defines.h +++ b/native/jni/src/defines.h @@ -375,7 +375,7 @@ typedef enum { CT_TERMINAL, CT_TERMINAL_INSERTION, // Create new word with space omission - CT_NEW_WORD_SPACE_OMITTION, + CT_NEW_WORD_SPACE_OMISSION, // Create new word with space substitution CT_NEW_WORD_SPACE_SUBSTITUTION, } CorrectionType; diff --git a/native/jni/src/suggest/core/dicnode/dic_node.h b/native/jni/src/suggest/core/dicnode/dic_node.h index 41ef9d2b2..9099e8285 100644 --- a/native/jni/src/suggest/core/dicnode/dic_node.h +++ b/native/jni/src/suggest/core/dicnode/dic_node.h @@ -38,10 +38,10 @@ INTS_TO_CHARS(mDicNodeState.mDicNodeStatePrevWord.mPrevWord, \ mDicNodeState.mDicNodeStatePrevWord.getPrevWordLength(), prevWordCharBuf, \ NELEMS(prevWordCharBuf)); \ - AKLOGI("#%8s, %5f, %5f, %5f, %5f, %s, %s, %d,,", header, \ + AKLOGI("#%8s, %5f, %5f, %5f, %5f, %s, %s, %d, %5f,", header, \ getSpatialDistanceForScoring(), getLanguageDistanceForScoring(), \ getNormalizedCompoundDistance(), getRawLength(), prevWordCharBuf, charBuf, \ - getInputIndex(0)); \ + getInputIndex(0), getNormalizedCompoundDistanceAfterFirstWord()); \ } while (0) #else #define LOGI_SHOW_ADD_COST_PROP @@ -434,6 +434,13 @@ class DicNode { return mDicNodeState.mDicNodeStateScoring.getLanguageDistance(); } + // For space-aware gestures, we store the normalized distance at the char index + // that ends the first word of the suggestion. We call this the distance after + // first word. + float getNormalizedCompoundDistanceAfterFirstWord() const { + return mDicNodeState.mDicNodeStateScoring.getNormalizedCompoundDistanceAfterFirstWord(); + } + float getLanguageDistanceRatePerWordForScoring() const { const float langDist = getLanguageDistanceForScoring(); const float totalWordCount = @@ -565,6 +572,12 @@ class DicNode { inputSize, getTotalInputIndex(), errorType); } + // Saves the current normalized compound distance for space-aware gestures. + // See getNormalizedCompoundDistanceAfterFirstWord for details. + AK_FORCE_INLINE void saveNormalizedCompoundDistanceAfterFirstWordIfNoneYet() { + mDicNodeState.mDicNodeStateScoring.saveNormalizedCompoundDistanceAfterFirstWordIfNoneYet(); + } + // Caveat: Must not be called outside Weighting // This restriction is guaranteed by "friend" AK_FORCE_INLINE void forwardInputIndex(const int pointerId, const int count, diff --git a/native/jni/src/suggest/core/dicnode/internal/dic_node_state_scoring.h b/native/jni/src/suggest/core/dicnode/internal/dic_node_state_scoring.h index 4c884225a..3c85d0e9d 100644 --- a/native/jni/src/suggest/core/dicnode/internal/dic_node_state_scoring.h +++ b/native/jni/src/suggest/core/dicnode/internal/dic_node_state_scoring.h @@ -31,7 +31,8 @@ class DicNodeStateScoring { mDigraphIndex(DigraphUtils::NOT_A_DIGRAPH_INDEX), mEditCorrectionCount(0), mProximityCorrectionCount(0), mNormalizedCompoundDistance(0.0f), mSpatialDistance(0.0f), mLanguageDistance(0.0f), - mRawLength(0.0f), mExactMatch(true) { + mRawLength(0.0f), mExactMatch(true), + mNormalizedCompoundDistanceAfterFirstWord(MAX_VALUE_FOR_WEIGHTING) { } virtual ~DicNodeStateScoring() {} @@ -45,6 +46,7 @@ class DicNodeStateScoring { mRawLength = 0.0f; mDoubleLetterLevel = NOT_A_DOUBLE_LETTER; mDigraphIndex = DigraphUtils::NOT_A_DIGRAPH_INDEX; + mNormalizedCompoundDistanceAfterFirstWord = MAX_VALUE_FOR_WEIGHTING; mExactMatch = true; } @@ -58,6 +60,8 @@ class DicNodeStateScoring { mDoubleLetterLevel = scoring->mDoubleLetterLevel; mDigraphIndex = scoring->mDigraphIndex; mExactMatch = scoring->mExactMatch; + mNormalizedCompoundDistanceAfterFirstWord = + scoring->mNormalizedCompoundDistanceAfterFirstWord; } void addCost(const float spatialCost, const float languageCost, const bool doNormalization, @@ -86,6 +90,17 @@ class DicNodeStateScoring { } } + // Saves the current normalized distance for space-aware gestures. + // See getNormalizedCompoundDistanceAfterFirstWord for details. + void saveNormalizedCompoundDistanceAfterFirstWordIfNoneYet() { + // We get called here after each word. We only want to store the distance after + // the first word, so if we already have a distance we skip saving -- hence "IfNoneYet" + // in the method name. + if (mNormalizedCompoundDistanceAfterFirstWord >= MAX_VALUE_FOR_WEIGHTING) { + mNormalizedCompoundDistanceAfterFirstWord = getNormalizedCompoundDistance(); + } + } + void addRawLength(const float rawLength) { mRawLength += rawLength; } @@ -102,6 +117,13 @@ class DicNodeStateScoring { return mNormalizedCompoundDistance; } + // For space-aware gestures, we store the normalized distance at the char index + // that ends the first word of the suggestion. We call this the distance after + // first word. + float getNormalizedCompoundDistanceAfterFirstWord() const { + return mNormalizedCompoundDistanceAfterFirstWord; + } + float getSpatialDistance() const { return mSpatialDistance; } @@ -178,6 +200,7 @@ class DicNodeStateScoring { float mLanguageDistance; float mRawLength; bool mExactMatch; + float mNormalizedCompoundDistanceAfterFirstWord; AK_FORCE_INLINE void addDistance(float spatialDistance, float languageDistance, bool doNormalization, int inputSize, int totalInputIndex) { diff --git a/native/jni/src/suggest/core/dictionary/dictionary.cpp b/native/jni/src/suggest/core/dictionary/dictionary.cpp index 214df1bbf..b1d01ed86 100644 --- a/native/jni/src/suggest/core/dictionary/dictionary.cpp +++ b/native/jni/src/suggest/core/dictionary/dictionary.cpp @@ -33,6 +33,8 @@ namespace latinime { +const int Dictionary::HEADER_ATTRIBUTE_BUFFER_SIZE = 32; + Dictionary::Dictionary(JNIEnv *env, DictionaryStructureWithBufferPolicy *const dictionaryStructureWithBufferPolicy) : mDictionaryStructureWithBufferPolicy(dictionaryStructureWithBufferPolicy), @@ -121,8 +123,8 @@ void Dictionary::flushWithGC(const char *const filePath) { mDictionaryStructureWithBufferPolicy->flushWithGC(filePath); } -bool Dictionary::needsToRunGC() { - return mDictionaryStructureWithBufferPolicy->needsToRunGC(); +bool Dictionary::needsToRunGC(const bool mindsBlockByGC) { + return mDictionaryStructureWithBufferPolicy->needsToRunGC(mindsBlockByGC); } void Dictionary::getProperty(const char *const query, char *const outResult, @@ -131,27 +133,27 @@ void Dictionary::getProperty(const char *const query, char *const outResult, } void Dictionary::logDictionaryInfo(JNIEnv *const env) const { - const int BUFFER_SIZE = 16; - int dictionaryIdCodePointBuffer[BUFFER_SIZE]; - int versionStringCodePointBuffer[BUFFER_SIZE]; - int dateStringCodePointBuffer[BUFFER_SIZE]; + int dictionaryIdCodePointBuffer[HEADER_ATTRIBUTE_BUFFER_SIZE]; + int versionStringCodePointBuffer[HEADER_ATTRIBUTE_BUFFER_SIZE]; + int dateStringCodePointBuffer[HEADER_ATTRIBUTE_BUFFER_SIZE]; const DictionaryHeaderStructurePolicy *const headerPolicy = getDictionaryStructurePolicy()->getHeaderStructurePolicy(); headerPolicy->readHeaderValueOrQuestionMark("dictionary", dictionaryIdCodePointBuffer, - BUFFER_SIZE); + HEADER_ATTRIBUTE_BUFFER_SIZE); headerPolicy->readHeaderValueOrQuestionMark("version", versionStringCodePointBuffer, - BUFFER_SIZE); - headerPolicy->readHeaderValueOrQuestionMark("date", dateStringCodePointBuffer, BUFFER_SIZE); - - char dictionaryIdCharBuffer[BUFFER_SIZE]; - char versionStringCharBuffer[BUFFER_SIZE]; - char dateStringCharBuffer[BUFFER_SIZE]; - intArrayToCharArray(dictionaryIdCodePointBuffer, BUFFER_SIZE, - dictionaryIdCharBuffer, BUFFER_SIZE); - intArrayToCharArray(versionStringCodePointBuffer, BUFFER_SIZE, - versionStringCharBuffer, BUFFER_SIZE); - intArrayToCharArray(dateStringCodePointBuffer, BUFFER_SIZE, - dateStringCharBuffer, BUFFER_SIZE); + HEADER_ATTRIBUTE_BUFFER_SIZE); + headerPolicy->readHeaderValueOrQuestionMark("date", dateStringCodePointBuffer, + HEADER_ATTRIBUTE_BUFFER_SIZE); + + char dictionaryIdCharBuffer[HEADER_ATTRIBUTE_BUFFER_SIZE]; + char versionStringCharBuffer[HEADER_ATTRIBUTE_BUFFER_SIZE]; + char dateStringCharBuffer[HEADER_ATTRIBUTE_BUFFER_SIZE]; + intArrayToCharArray(dictionaryIdCodePointBuffer, HEADER_ATTRIBUTE_BUFFER_SIZE, + dictionaryIdCharBuffer, HEADER_ATTRIBUTE_BUFFER_SIZE); + intArrayToCharArray(versionStringCodePointBuffer, HEADER_ATTRIBUTE_BUFFER_SIZE, + versionStringCharBuffer, HEADER_ATTRIBUTE_BUFFER_SIZE); + intArrayToCharArray(dateStringCodePointBuffer, HEADER_ATTRIBUTE_BUFFER_SIZE, + dateStringCharBuffer, HEADER_ATTRIBUTE_BUFFER_SIZE); LogUtils::logToJava(env, "Dictionary info: dictionary = %s ; version = %s ; date = %s", diff --git a/native/jni/src/suggest/core/dictionary/dictionary.h b/native/jni/src/suggest/core/dictionary/dictionary.h index 800751745..d8a0f3e58 100644 --- a/native/jni/src/suggest/core/dictionary/dictionary.h +++ b/native/jni/src/suggest/core/dictionary/dictionary.h @@ -81,7 +81,7 @@ class Dictionary { void flushWithGC(const char *const filePath); - bool needsToRunGC(); + bool needsToRunGC(const bool mindsBlockByGC); void getProperty(const char *const query, char *const outResult, const int maxResultLength) const; @@ -95,6 +95,8 @@ class Dictionary { private: DISALLOW_IMPLICIT_CONSTRUCTORS(Dictionary); + static const int HEADER_ATTRIBUTE_BUFFER_SIZE; + DictionaryStructureWithBufferPolicy *const mDictionaryStructureWithBufferPolicy; const BigramDictionary *const mBigramDictionary; const SuggestInterface *const mGestureSuggest; diff --git a/native/jni/src/suggest/core/policy/dictionary_structure_with_buffer_policy.h b/native/jni/src/suggest/core/policy/dictionary_structure_with_buffer_policy.h index 2434287b1..c7ffef0d5 100644 --- a/native/jni/src/suggest/core/policy/dictionary_structure_with_buffer_policy.h +++ b/native/jni/src/suggest/core/policy/dictionary_structure_with_buffer_policy.h @@ -78,7 +78,7 @@ class DictionaryStructureWithBufferPolicy { virtual void flushWithGC(const char *const filePath) = 0; - virtual bool needsToRunGC() const = 0; + virtual bool needsToRunGC(const bool mindsBlockByGC) const = 0; virtual void getProperty(const char *const query, char *const outResult, const int maxResultLength) const = 0; diff --git a/native/jni/src/suggest/core/policy/weighting.cpp b/native/jni/src/suggest/core/policy/weighting.cpp index f9b777df2..0c4016893 100644 --- a/native/jni/src/suggest/core/policy/weighting.cpp +++ b/native/jni/src/suggest/core/policy/weighting.cpp @@ -38,7 +38,7 @@ static inline void profile(const CorrectionType correctionType, DicNode *const n case CT_SUBSTITUTION: PROF_SUBSTITUTION(node->mProfiler); return; - case CT_NEW_WORD_SPACE_OMITTION: + case CT_NEW_WORD_SPACE_OMISSION: PROF_NEW_WORD(node->mProfiler); return; case CT_MATCH: @@ -93,6 +93,11 @@ static inline void profile(const CorrectionType correctionType, DicNode *const n } dicNode->addCost(spatialCost, languageCost, weighting->needsToNormalizeCompoundDistance(), inputSize, errorType); + if (CT_NEW_WORD_SPACE_OMISSION == correctionType) { + // When we are on a terminal, we save the current distance for evaluating + // when to auto-commit partial suggestions. + dicNode->saveNormalizedCompoundDistanceAfterFirstWordIfNoneYet(); + } } /* static */ float Weighting::getSpatialCost(const Weighting *const weighting, @@ -108,7 +113,7 @@ static inline void profile(const CorrectionType correctionType, DicNode *const n case CT_SUBSTITUTION: // only used for typing return weighting->getSubstitutionCost(); - case CT_NEW_WORD_SPACE_OMITTION: + case CT_NEW_WORD_SPACE_OMISSION: return weighting->getNewWordSpatialCost(traverseSession, dicNode, inputStateG); case CT_MATCH: return weighting->getMatchedCost(traverseSession, dicNode, inputStateG); @@ -138,7 +143,7 @@ static inline void profile(const CorrectionType correctionType, DicNode *const n return 0.0f; case CT_SUBSTITUTION: return 0.0f; - case CT_NEW_WORD_SPACE_OMITTION: + case CT_NEW_WORD_SPACE_OMISSION: return weighting->getNewWordBigramLanguageCost( traverseSession, parentDicNode, multiBigramMap); case CT_MATCH: @@ -173,7 +178,7 @@ static inline void profile(const CorrectionType correctionType, DicNode *const n return 0; /* 0 because CT_MATCH will be called */ case CT_SUBSTITUTION: return 0; /* 0 because CT_MATCH will be called */ - case CT_NEW_WORD_SPACE_OMITTION: + case CT_NEW_WORD_SPACE_OMISSION: return 0; case CT_MATCH: return 1; diff --git a/native/jni/src/suggest/core/suggest.cpp b/native/jni/src/suggest/core/suggest.cpp index b1340e12f..e20bc497a 100644 --- a/native/jni/src/suggest/core/suggest.cpp +++ b/native/jni/src/suggest/core/suggest.cpp @@ -574,7 +574,7 @@ void Suggest::createNextWordDicNode(DicTraverseSession *traverseSession, DicNode DicNodeUtils::initAsRootWithPreviousWord( traverseSession->getDictionaryStructurePolicy(), dicNode, &newDicNode); const CorrectionType correctionType = spaceSubstitution ? - CT_NEW_WORD_SPACE_SUBSTITUTION : CT_NEW_WORD_SPACE_OMITTION; + CT_NEW_WORD_SPACE_SUBSTITUTION : CT_NEW_WORD_SPACE_OMISSION; Weighting::addCostAndForwardInputIndex(WEIGHTING, correctionType, traverseSession, dicNode, &newDicNode, traverseSession->getMultiBigramMap()); if (newDicNode.getCompoundDistance() < static_cast<float>(MAX_VALUE_FOR_WEIGHTING)) { diff --git a/native/jni/src/suggest/policyimpl/dictionary/bigram/dynamic_bigram_list_policy.cpp b/native/jni/src/suggest/policyimpl/dictionary/bigram/dynamic_bigram_list_policy.cpp index e02f4cbf1..67a085de3 100644 --- a/native/jni/src/suggest/policyimpl/dictionary/bigram/dynamic_bigram_list_policy.cpp +++ b/native/jni/src/suggest/policyimpl/dictionary/bigram/dynamic_bigram_list_policy.cpp @@ -17,10 +17,10 @@ #include "suggest/policyimpl/dictionary/bigram/dynamic_bigram_list_policy.h" #include "suggest/core/policy/dictionary_shortcuts_structure_policy.h" -#include "suggest/policyimpl/dictionary/bigram/bigram_list_read_write_utils.h" #include "suggest/policyimpl/dictionary/dynamic_patricia_trie_node_reader.h" #include "suggest/policyimpl/dictionary/dynamic_patricia_trie_writing_helper.h" #include "suggest/policyimpl/dictionary/utils/buffer_with_extendable_buffer.h" +#include "suggest/policyimpl/dictionary/utils/decaying_utils.h" namespace latinime { @@ -41,9 +41,14 @@ void DynamicBigramListPolicy::getNextBigram(int *const outBigramPos, int *const if (usesAdditionalBuffer && originalBigramPos != NOT_A_DICT_POS) { originalBigramPos += mBuffer->getOriginalBufferSize(); } - *outBigramPos = followBigramLinkAndGetCurrentBigramPtNodePos(originalBigramPos); *outProbability = BigramListReadWriteUtils::getProbabilityFromFlags(bigramFlags); *outHasNext = BigramListReadWriteUtils::hasNext(bigramFlags); + if (mIsDecayingDict && !DecayingUtils::isValidBigram(*outProbability)) { + // This bigram is too weak to output. + *outBigramPos = NOT_A_DICT_POS; + } else { + *outBigramPos = followBigramLinkAndGetCurrentBigramPtNodePos(originalBigramPos); + } if (usesAdditionalBuffer) { *bigramEntryPos += mBuffer->getOriginalBufferSize(); } @@ -153,15 +158,21 @@ bool DynamicBigramListPolicy::updateAllBigramEntriesAndDeleteUselessEntries( const int bigramTargetNodePos = followBigramLinkAndGetCurrentBigramPtNodePos(originalBigramPos); nodeReader.fetchNodeInfoInBufferFromPtNodePos(bigramTargetNodePos); - // TODO: Update probability for supporting probability decaying. if (nodeReader.isDeleted() || !nodeReader.isTerminal() || bigramTargetNodePos == NOT_A_DICT_POS) { // The target is no longer valid terminal. Invalidate the current bigram entry. if (!BigramListReadWriteUtils::writeBigramEntry(mBuffer, bigramFlags, - NOT_A_DICT_POS /* targetOffset */, &bigramEntryPos)) { + NOT_A_DICT_POS /* targetPtNodePos */, &bigramEntryPos)) { return false; } - } else { + continue; + } + bool isRemoved = false; + if (!updateProbabilityForDecay(bigramFlags, bigramTargetNodePos, &bigramEntryPos, + &isRemoved)) { + return false; + } + if (!isRemoved) { (*outValidBigramEntryCount) += 1; } } while(BigramListReadWriteUtils::hasNext(bigramFlags)); @@ -247,8 +258,14 @@ bool DynamicBigramListPolicy::addNewBigramEntryToBigramList(const int bigramTarg if (followBigramLinkAndGetCurrentBigramPtNodePos(originalBigramPos) == bigramTargetPos) { // Update this bigram entry. *outAddedNewBigram = false; + const int originalProbability = BigramListReadWriteUtils::getProbabilityFromFlags( + bigramFlags); + const int probabilityToWrite = mIsDecayingDict ? + DecayingUtils::getUpdatedBigramProbabilityDelta( + originalProbability, probability) : probability; const BigramListReadWriteUtils::BigramFlags updatedFlags = - BigramListReadWriteUtils::setProbabilityInFlags(bigramFlags, probability); + BigramListReadWriteUtils::setProbabilityInFlags(bigramFlags, + probabilityToWrite); return BigramListReadWriteUtils::writeBigramEntry(mBuffer, updatedFlags, originalBigramPos, &entryPos); } @@ -276,8 +293,11 @@ bool DynamicBigramListPolicy::addNewBigramEntryToBigramList(const int bigramTarg bool DynamicBigramListPolicy::writeNewBigramEntry(const int bigramTargetPos, const int probability, int *const writingPos) { // hasNext is false because we are adding a new bigram entry at the end of the bigram list. + const int probabilityToWrite = mIsDecayingDict ? + DecayingUtils::getUpdatedBigramProbabilityDelta(NOT_A_PROBABILITY, probability) : + probability; return BigramListReadWriteUtils::createAndWriteBigramEntry(mBuffer, bigramTargetPos, - probability, false /* hasNext */, writingPos); + probabilityToWrite, false /* hasNext */, writingPos); } bool DynamicBigramListPolicy::removeBigram(const int bigramListPos, const int bigramTargetPos) { @@ -339,4 +359,33 @@ int DynamicBigramListPolicy::followBigramLinkAndGetCurrentBigramPtNodePos( return currentPos; } +bool DynamicBigramListPolicy::updateProbabilityForDecay( + BigramListReadWriteUtils::BigramFlags bigramFlags, const int targetPtNodePos, + int *const bigramEntryPos, bool *const outRemoved) const { + *outRemoved = false; + if (mIsDecayingDict) { + // Update bigram probability for decaying. + const int newProbability = DecayingUtils::getBigramProbabilityDeltaToSave( + BigramListReadWriteUtils::getProbabilityFromFlags(bigramFlags)); + if (DecayingUtils::isValidBigram(newProbability)) { + // Write new probability. + const BigramListReadWriteUtils::BigramFlags updatedBigramFlags = + BigramListReadWriteUtils::setProbabilityInFlags( + bigramFlags, newProbability); + if (!BigramListReadWriteUtils::writeBigramEntry(mBuffer, updatedBigramFlags, + targetPtNodePos, bigramEntryPos)) { + return false; + } + } else { + // Remove current bigram entry. + *outRemoved = true; + if (!BigramListReadWriteUtils::writeBigramEntry(mBuffer, bigramFlags, + NOT_A_DICT_POS /* targetPtNodePos */, bigramEntryPos)) { + return false; + } + } + } + return true; +} + } // namespace latinime diff --git a/native/jni/src/suggest/policyimpl/dictionary/bigram/dynamic_bigram_list_policy.h b/native/jni/src/suggest/policyimpl/dictionary/bigram/dynamic_bigram_list_policy.h index 3ebf69946..b358b4ed5 100644 --- a/native/jni/src/suggest/policyimpl/dictionary/bigram/dynamic_bigram_list_policy.h +++ b/native/jni/src/suggest/policyimpl/dictionary/bigram/dynamic_bigram_list_policy.h @@ -21,6 +21,7 @@ #include "defines.h" #include "suggest/core/policy/dictionary_bigrams_structure_policy.h" +#include "suggest/policyimpl/dictionary/bigram/bigram_list_read_write_utils.h" #include "suggest/policyimpl/dictionary/dynamic_patricia_trie_writing_helper.h" namespace latinime { @@ -34,8 +35,9 @@ class DictionaryShortcutsStructurePolicy; class DynamicBigramListPolicy : public DictionaryBigramsStructurePolicy { public: DynamicBigramListPolicy(BufferWithExtendableBuffer *const buffer, - const DictionaryShortcutsStructurePolicy *const shortcutPolicy) - : mBuffer(buffer), mShortcutPolicy(shortcutPolicy) {} + const DictionaryShortcutsStructurePolicy *const shortcutPolicy, + const bool isDecayingDict) + : mBuffer(buffer), mShortcutPolicy(shortcutPolicy), mIsDecayingDict(isDecayingDict) {} ~DynamicBigramListPolicy() {} @@ -74,9 +76,13 @@ class DynamicBigramListPolicy : public DictionaryBigramsStructurePolicy { BufferWithExtendableBuffer *const mBuffer; const DictionaryShortcutsStructurePolicy *const mShortcutPolicy; + const bool mIsDecayingDict; // Follow bigram link and return the position of bigram target PtNode that is currently valid. int followBigramLinkAndGetCurrentBigramPtNodePos(const int originalBigramPos) const; + + bool updateProbabilityForDecay(BigramListReadWriteUtils::BigramFlags bigramFlags, + const int targetPtNodePos, int *const bigramEntryPos, bool *const outRemoved) const; }; } // namespace latinime #endif // LATINIME_DYNAMIC_BIGRAM_LIST_POLICY_H diff --git a/native/jni/src/suggest/policyimpl/dictionary/dynamic_patricia_trie_gc_event_listeners.cpp b/native/jni/src/suggest/policyimpl/dictionary/dynamic_patricia_trie_gc_event_listeners.cpp index 5eb473300..081163a4d 100644 --- a/native/jni/src/suggest/policyimpl/dictionary/dynamic_patricia_trie_gc_event_listeners.cpp +++ b/native/jni/src/suggest/policyimpl/dictionary/dynamic_patricia_trie_gc_event_listeners.cpp @@ -16,6 +16,8 @@ #include "suggest/policyimpl/dictionary/dynamic_patricia_trie_gc_event_listeners.h" +#include "suggest/policyimpl/dictionary/utils/decaying_utils.h" + namespace latinime { bool DynamicPatriciaTrieGcEventListeners @@ -25,6 +27,19 @@ bool DynamicPatriciaTrieGcEventListeners // PtNode is useless when the PtNode is not a terminal and doesn't have any not useless // children. bool isUselessPtNode = !node->isTerminal(); + if (node->isTerminal() && mIsDecayingDict) { + const int newProbability = + DecayingUtils::getUnigramProbabilityToSave(node->getProbability()); + int writingPos = node->getProbabilityFieldPos(); + // Update probability. + if (!DynamicPatriciaTrieWritingUtils::writeProbabilityAndAdvancePosition( + mBuffer, newProbability, &writingPos)) { + return false; + } + if (!DecayingUtils::isValidUnigram(newProbability)) { + isUselessPtNode = false; + } + } if (mChildrenValue > 0) { isUselessPtNode = false; } else if (node->isTerminal()) { @@ -41,7 +56,7 @@ bool DynamicPatriciaTrieGcEventListeners return false; } } else { - valueStack.back() += 1; + mValueStack.back() += 1; if (node->isTerminal()) { mValidUnigramCount += 1; } @@ -49,6 +64,23 @@ bool DynamicPatriciaTrieGcEventListeners return true; } +bool DynamicPatriciaTrieGcEventListeners::TraversePolicyToUpdateBigramProbability + ::onVisitingPtNode(const DynamicPatriciaTrieNodeReader *const node, + const int *const nodeCodePoints) { + if (!node->isDeleted()) { + int pos = node->getBigramsPos(); + if (pos != NOT_A_DICT_POS) { + int bigramEntryCount = 0; + if (!mBigramPolicy->updateAllBigramEntriesAndDeleteUselessEntries(&pos, + &bigramEntryCount)) { + return false; + } + mValidBigramEntryCount += bigramEntryCount; + } + } + return true; +} + // Writes dummy PtNode array size when the head of PtNode array is read. bool DynamicPatriciaTrieGcEventListeners::TraversePolicyToPlaceAndWriteValidPtNodesToBuffer ::onDescend(const int ptNodeArrayPos) { diff --git a/native/jni/src/suggest/policyimpl/dictionary/dynamic_patricia_trie_gc_event_listeners.h b/native/jni/src/suggest/policyimpl/dictionary/dynamic_patricia_trie_gc_event_listeners.h index aa6e60959..463715af5 100644 --- a/native/jni/src/suggest/policyimpl/dictionary/dynamic_patricia_trie_gc_event_listeners.h +++ b/native/jni/src/suggest/policyimpl/dictionary/dynamic_patricia_trie_gc_event_listeners.h @@ -39,23 +39,23 @@ class DynamicPatriciaTrieGcEventListeners { public: TraversePolicyToUpdateUnigramProbabilityAndMarkUselessPtNodesAsDeleted( DynamicPatriciaTrieWritingHelper *const writingHelper, - BufferWithExtendableBuffer *const buffer) - : mWritingHelper(writingHelper), mBuffer(buffer), valueStack(), - mChildrenValue(0), mValidUnigramCount(0) {} + BufferWithExtendableBuffer *const buffer, const bool isDecayingDict) + : mWritingHelper(writingHelper), mBuffer(buffer), mIsDecayingDict(isDecayingDict), + mValueStack(), mChildrenValue(0), mValidUnigramCount(0) {} ~TraversePolicyToUpdateUnigramProbabilityAndMarkUselessPtNodesAsDeleted() {}; bool onAscend() { - if (valueStack.empty()) { + if (mValueStack.empty()) { return false; } - mChildrenValue = valueStack.back(); - valueStack.pop_back(); + mChildrenValue = mValueStack.back(); + mValueStack.pop_back(); return true; } bool onDescend(const int ptNodeArrayPos) { - valueStack.push_back(0); + mValueStack.push_back(0); return true; } @@ -74,7 +74,8 @@ class DynamicPatriciaTrieGcEventListeners { DynamicPatriciaTrieWritingHelper *const mWritingHelper; BufferWithExtendableBuffer *const mBuffer; - std::vector<int> valueStack; + const int mIsDecayingDict; + std::vector<int> mValueStack; int mChildrenValue; int mValidUnigramCount; }; @@ -94,20 +95,7 @@ class DynamicPatriciaTrieGcEventListeners { bool onReadingPtNodeArrayTail() { return true; } bool onVisitingPtNode(const DynamicPatriciaTrieNodeReader *const node, - const int *const nodeCodePoints) { - if (!node->isDeleted()) { - int pos = node->getBigramsPos(); - if (pos != NOT_A_DICT_POS) { - int bigramEntryCount = 0; - if (!mBigramPolicy->updateAllBigramEntriesAndDeleteUselessEntries(&pos, - &bigramEntryCount)) { - return false; - } - mValidBigramEntryCount += bigramEntryCount; - } - } - return true; - } + const int *const nodeCodePoints); int getValidBigramEntryCount() const { return mValidBigramEntryCount; diff --git a/native/jni/src/suggest/policyimpl/dictionary/dynamic_patricia_trie_policy.cpp b/native/jni/src/suggest/policyimpl/dictionary/dynamic_patricia_trie_policy.cpp index 4581ec093..0d8c92768 100644 --- a/native/jni/src/suggest/policyimpl/dictionary/dynamic_patricia_trie_policy.cpp +++ b/native/jni/src/suggest/policyimpl/dictionary/dynamic_patricia_trie_policy.cpp @@ -18,6 +18,7 @@ #include <cstdio> #include <cstring> +#include <ctime> #include "defines.h" #include "suggest/core/dicnode/dic_node.h" @@ -27,12 +28,17 @@ #include "suggest/policyimpl/dictionary/dynamic_patricia_trie_reading_utils.h" #include "suggest/policyimpl/dictionary/dynamic_patricia_trie_writing_helper.h" #include "suggest/policyimpl/dictionary/patricia_trie_reading_utils.h" +#include "suggest/policyimpl/dictionary/utils/decaying_utils.h" #include "suggest/policyimpl/dictionary/utils/probability_utils.h" namespace latinime { const char *const DynamicPatriciaTriePolicy::UNIGRAM_COUNT_QUERY = "UNIGRAM_COUNT"; const char *const DynamicPatriciaTriePolicy::BIGRAM_COUNT_QUERY = "BIGRAM_COUNT"; +const int DynamicPatriciaTriePolicy::MAX_DICT_EXTENDED_REGION_SIZE = 1024 * 1024; +const int DynamicPatriciaTriePolicy::MIN_DICT_SIZE_TO_REFUSE_DYNAMIC_OPERATIONS = + DynamicPatriciaTrieWritingHelper::MAX_DICTIONARY_SIZE - 1024; +const int DynamicPatriciaTriePolicy::MIN_SECONDS_TO_REQUIRE_GC_WHEN_WRITING = 2 * 60 * 60; void DynamicPatriciaTriePolicy::createAndGetAllChildNodes(const DicNode *const dicNode, DicNodeVector *const childDicNodes) const { @@ -143,14 +149,17 @@ int DynamicPatriciaTriePolicy::getTerminalNodePositionOfWord(const int *const in int DynamicPatriciaTriePolicy::getProbability(const int unigramProbability, const int bigramProbability) const { - // TODO: check mHeaderPolicy.usesForgettingCurve(); - if (unigramProbability == NOT_A_PROBABILITY) { - return NOT_A_PROBABILITY; - } else if (bigramProbability == NOT_A_PROBABILITY) { - return ProbabilityUtils::backoff(unigramProbability); + if (mHeaderPolicy.isDecayingDict()) { + return DecayingUtils::getProbability(unigramProbability, bigramProbability); } else { - return ProbabilityUtils::computeProbabilityForBigram(unigramProbability, - bigramProbability); + if (unigramProbability == NOT_A_PROBABILITY) { + return NOT_A_PROBABILITY; + } else if (bigramProbability == NOT_A_PROBABILITY) { + return ProbabilityUtils::backoff(unigramProbability); + } else { + return ProbabilityUtils::computeProbabilityForBigram(unigramProbability, + bigramProbability); + } } } @@ -199,11 +208,16 @@ bool DynamicPatriciaTriePolicy::addUnigramWord(const int *const word, const int AKLOGI("Warning: addUnigramWord() is called for non-updatable dictionary."); return false; } + if (mBufferWithExtendableBuffer.getTailPosition() + >= MIN_DICT_SIZE_TO_REFUSE_DYNAMIC_OPERATIONS) { + AKLOGE("The dictionary is too large to dynamically update."); + return false; + } DynamicPatriciaTrieReadingHelper readingHelper(&mBufferWithExtendableBuffer, getBigramsStructurePolicy(), getShortcutsStructurePolicy()); readingHelper.initWithPtNodeArrayPos(getRootPosition()); DynamicPatriciaTrieWritingHelper writingHelper(&mBufferWithExtendableBuffer, - &mBigramListPolicy, &mShortcutListPolicy); + &mBigramListPolicy, &mShortcutListPolicy, mHeaderPolicy.isDecayingDict()); bool addedNewUnigram = false; if (writingHelper.addUnigramWord(&readingHelper, word, length, probability, &addedNewUnigram)) { @@ -222,6 +236,11 @@ bool DynamicPatriciaTriePolicy::addBigramWords(const int *const word0, const int AKLOGI("Warning: addBigramWords() is called for non-updatable dictionary."); return false; } + if (mBufferWithExtendableBuffer.getTailPosition() + >= MIN_DICT_SIZE_TO_REFUSE_DYNAMIC_OPERATIONS) { + AKLOGE("The dictionary is too large to dynamically update."); + return false; + } const int word0Pos = getTerminalNodePositionOfWord(word0, length0, false /* forceLowerCaseSearch */); if (word0Pos == NOT_A_DICT_POS) { @@ -233,7 +252,7 @@ bool DynamicPatriciaTriePolicy::addBigramWords(const int *const word0, const int return false; } DynamicPatriciaTrieWritingHelper writingHelper(&mBufferWithExtendableBuffer, - &mBigramListPolicy, &mShortcutListPolicy); + &mBigramListPolicy, &mShortcutListPolicy, mHeaderPolicy.isDecayingDict()); bool addedNewBigram = false; if (writingHelper.addBigramWords(word0Pos, word1Pos, probability, &addedNewBigram)) { if (addedNewBigram) { @@ -251,6 +270,11 @@ bool DynamicPatriciaTriePolicy::removeBigramWords(const int *const word0, const AKLOGI("Warning: removeBigramWords() is called for non-updatable dictionary."); return false; } + if (mBufferWithExtendableBuffer.getTailPosition() + >= MIN_DICT_SIZE_TO_REFUSE_DYNAMIC_OPERATIONS) { + AKLOGE("The dictionary is too large to dynamically update."); + return false; + } const int word0Pos = getTerminalNodePositionOfWord(word0, length0, false /* forceLowerCaseSearch */); if (word0Pos == NOT_A_DICT_POS) { @@ -262,7 +286,7 @@ bool DynamicPatriciaTriePolicy::removeBigramWords(const int *const word0, const return false; } DynamicPatriciaTrieWritingHelper writingHelper(&mBufferWithExtendableBuffer, - &mBigramListPolicy, &mShortcutListPolicy); + &mBigramListPolicy, &mShortcutListPolicy, mHeaderPolicy.isDecayingDict()); if (writingHelper.removeBigramWords(word0Pos, word1Pos)) { mBigramCount--; return true; @@ -277,7 +301,7 @@ void DynamicPatriciaTriePolicy::flush(const char *const filePath) { return; } DynamicPatriciaTrieWritingHelper writingHelper(&mBufferWithExtendableBuffer, - &mBigramListPolicy, &mShortcutListPolicy); + &mBigramListPolicy, &mShortcutListPolicy, mHeaderPolicy.isDecayingDict()); writingHelper.writeToDictFile(filePath, &mHeaderPolicy, mUnigramCount, mBigramCount); } @@ -287,17 +311,42 @@ void DynamicPatriciaTriePolicy::flushWithGC(const char *const filePath) { return; } DynamicPatriciaTrieWritingHelper writingHelper(&mBufferWithExtendableBuffer, - &mBigramListPolicy, &mShortcutListPolicy); + &mBigramListPolicy, &mShortcutListPolicy, mHeaderPolicy.isDecayingDict()); writingHelper.writeToDictFileWithGC(getRootPosition(), filePath, &mHeaderPolicy); } -bool DynamicPatriciaTriePolicy::needsToRunGC() const { +bool DynamicPatriciaTriePolicy::needsToRunGC(const bool mindsBlockByGC) const { if (!mBuffer->isUpdatable()) { AKLOGI("Warning: needsToRunGC() is called for non-updatable dictionary."); return false; } - // TODO: Implement more properly. - return mBufferWithExtendableBuffer.isNearSizeLimit(); + if (mBufferWithExtendableBuffer.isNearSizeLimit()) { + // Additional buffer size is near the limit. + return true; + } else if (mHeaderPolicy.getExtendedRegionSize() + + mBufferWithExtendableBuffer.getUsedAdditionalBufferSize() + > MAX_DICT_EXTENDED_REGION_SIZE) { + // Total extended region size exceeds the limit. + return true; + } else if (mBufferWithExtendableBuffer.getTailPosition() + >= MIN_DICT_SIZE_TO_REFUSE_DYNAMIC_OPERATIONS + && mBufferWithExtendableBuffer.getUsedAdditionalBufferSize() > 0) { + // Needs to reduce dictionary size. + return true; + } else if (mHeaderPolicy.isDecayingDict()) { + if (mUnigramCount >= DecayingUtils::MAX_UNIGRAM_COUNT) { + // Unigram count exceeds the limit. + return true; + } else if (mBigramCount >= DecayingUtils::MAX_BIGRAM_COUNT) { + // Bigram count exceeds the limit. + return true; + } else if (mindsBlockByGC && mHeaderPolicy.getLastUpdatedTime() + + MIN_SECONDS_TO_REQUIRE_GC_WHEN_WRITING < time(0)) { + // Time to update probabilities for decaying. + return true; + } + } + return false; } void DynamicPatriciaTriePolicy::getProperty(const char *const query, char *const outResult, diff --git a/native/jni/src/suggest/policyimpl/dictionary/dynamic_patricia_trie_policy.h b/native/jni/src/suggest/policyimpl/dictionary/dynamic_patricia_trie_policy.h index 7f9d4d924..d3150c6fc 100644 --- a/native/jni/src/suggest/policyimpl/dictionary/dynamic_patricia_trie_policy.h +++ b/native/jni/src/suggest/policyimpl/dictionary/dynamic_patricia_trie_policy.h @@ -37,7 +37,8 @@ class DynamicPatriciaTriePolicy : public DictionaryStructureWithBufferPolicy { mBufferWithExtendableBuffer(mBuffer->getBuffer() + mHeaderPolicy.getSize(), mBuffer->getBufferSize() - mHeaderPolicy.getSize()), mShortcutListPolicy(&mBufferWithExtendableBuffer), - mBigramListPolicy(&mBufferWithExtendableBuffer, &mShortcutListPolicy), + mBigramListPolicy(&mBufferWithExtendableBuffer, &mShortcutListPolicy, + mHeaderPolicy.isDecayingDict()), mUnigramCount(mHeaderPolicy.getUnigramCount()), mBigramCount(mHeaderPolicy.getBigramCount()) {} @@ -91,7 +92,7 @@ class DynamicPatriciaTriePolicy : public DictionaryStructureWithBufferPolicy { void flushWithGC(const char *const filePath); - bool needsToRunGC() const; + bool needsToRunGC(const bool mindsBlockByGC) const; void getProperty(const char *const query, char *const outResult, const int maxResultLength) const; @@ -101,6 +102,9 @@ class DynamicPatriciaTriePolicy : public DictionaryStructureWithBufferPolicy { static const char*const UNIGRAM_COUNT_QUERY; static const char*const BIGRAM_COUNT_QUERY; + static const int MAX_DICT_EXTENDED_REGION_SIZE; + static const int MIN_DICT_SIZE_TO_REFUSE_DYNAMIC_OPERATIONS; + static const int MIN_SECONDS_TO_REQUIRE_GC_WHEN_WRITING; const MmappedBuffer *const mBuffer; const HeaderPolicy mHeaderPolicy; diff --git a/native/jni/src/suggest/policyimpl/dictionary/dynamic_patricia_trie_writing_helper.cpp b/native/jni/src/suggest/policyimpl/dictionary/dynamic_patricia_trie_writing_helper.cpp index bae5e8cad..28124d251 100644 --- a/native/jni/src/suggest/policyimpl/dictionary/dynamic_patricia_trie_writing_helper.cpp +++ b/native/jni/src/suggest/policyimpl/dictionary/dynamic_patricia_trie_writing_helper.cpp @@ -25,6 +25,7 @@ #include "suggest/policyimpl/dictionary/header/header_policy.h" #include "suggest/policyimpl/dictionary/patricia_trie_reading_utils.h" #include "suggest/policyimpl/dictionary/shortcut/dynamic_shortcut_list_policy.h" +#include "suggest/policyimpl/dictionary/utils/decaying_utils.h" #include "suggest/policyimpl/dictionary/utils/dict_file_writing_utils.h" #include "utils/hash_map_compat.h" @@ -57,7 +58,9 @@ bool DynamicPatriciaTrieWritingHelper::addUnigramWord( wordCodePoints[matchedCodePointCount + j])) { *outAddedNewUnigram = true; return reallocatePtNodeAndAddNewPtNodes(nodeReader, - readingHelper->getMergedNodeCodePoints(), j, probability, + readingHelper->getMergedNodeCodePoints(), j, + getUpdatedProbability(NOT_A_PROBABILITY /* originalProbability */, + probability), wordCodePoints + matchedCodePointCount, codePointCount - matchedCodePointCount); } @@ -69,7 +72,8 @@ bool DynamicPatriciaTrieWritingHelper::addUnigramWord( } if (!nodeReader->hasChildren()) { *outAddedNewUnigram = true; - return createChildrenPtNodeArrayAndAChildPtNode(nodeReader, probability, + return createChildrenPtNodeArrayAndAChildPtNode(nodeReader, + getUpdatedProbability(NOT_A_PROBABILITY /* originalProbability */, probability), wordCodePoints + readingHelper->getTotalCodePointCount(), codePointCount - readingHelper->getTotalCodePointCount()); } @@ -86,7 +90,7 @@ bool DynamicPatriciaTrieWritingHelper::addUnigramWord( return createAndInsertNodeIntoPtNodeArray(parentPos, wordCodePoints + readingHelper->getPrevTotalCodePointCount(), codePointCount - readingHelper->getPrevTotalCodePointCount(), - probability, &pos); + getUpdatedProbability(NOT_A_PROBABILITY /* originalProbability */, probability), &pos); } bool DynamicPatriciaTrieWritingHelper::addBigramWords(const int word0Pos, const int word1Pos, @@ -147,7 +151,7 @@ void DynamicPatriciaTrieWritingHelper::writeToDictFile(const char *const fileNam const HeaderPolicy *const headerPolicy, const int unigramCount, const int bigramCount) { BufferWithExtendableBuffer headerBuffer(0 /* originalBuffer */, 0 /* originalBufferSize */); const int extendedRegionSize = headerPolicy->getExtendedRegionSize() + - mBuffer->getTailPosition() - mBuffer->getOriginalBufferSize(); + mBuffer->getUsedAdditionalBufferSize(); if (!headerPolicy->writeHeaderToBuffer(&headerBuffer, false /* updatesLastUpdatedTime */, unigramCount, bigramCount, extendedRegionSize)) { return; @@ -351,9 +355,11 @@ bool DynamicPatriciaTrieWritingHelper::setPtNodeProbability( if (originalPtNode->isTerminal()) { // Overwrites the probability. *outAddedNewUnigram = false; + const int probabilityToWrite = getUpdatedProbability(originalPtNode->getProbability(), + probability); int probabilityFieldPos = originalPtNode->getProbabilityFieldPos(); if (!DynamicPatriciaTrieWritingUtils::writeProbabilityAndAdvancePosition(mBuffer, - probability, &probabilityFieldPos)) { + probabilityToWrite, &probabilityFieldPos)) { return false; } } else { @@ -365,7 +371,8 @@ bool DynamicPatriciaTrieWritingHelper::setPtNodeProbability( } if (!writePtNodeToBufferByCopyingPtNodeInfo(mBuffer, originalPtNode, originalPtNode->getParentPos(), codePoints, originalPtNode->getCodePointCount(), - probability, &movedPos)) { + getUpdatedProbability(NOT_A_PROBABILITY /* originalProbability */, probability), + &movedPos)) { return false; } } @@ -481,11 +488,15 @@ bool DynamicPatriciaTrieWritingHelper::runGC(const int rootPtNodeArrayPos, DynamicPatriciaTrieGcEventListeners ::TraversePolicyToUpdateUnigramProbabilityAndMarkUselessPtNodesAsDeleted traversePolicyToUpdateUnigramProbabilityAndMarkUselessPtNodesAsDeleted( - this, mBuffer); + this, mBuffer, mIsDecayingDict); if (!readingHelper.traverseAllPtNodesInPostorderDepthFirstManner( &traversePolicyToUpdateUnigramProbabilityAndMarkUselessPtNodesAsDeleted)) { return false; } + if (mIsDecayingDict && traversePolicyToUpdateUnigramProbabilityAndMarkUselessPtNodesAsDeleted + .getValidUnigramCount() > DecayingUtils::MAX_UNIGRAM_COUNT_AFTER_GC) { + // TODO: Remove more unigrams. + } readingHelper.initWithPtNodeArrayPos(rootPtNodeArrayPos); DynamicPatriciaTrieGcEventListeners::TraversePolicyToUpdateBigramProbability @@ -495,6 +506,11 @@ bool DynamicPatriciaTrieWritingHelper::runGC(const int rootPtNodeArrayPos, return false; } + if (mIsDecayingDict && traversePolicyToUpdateBigramProbability.getValidBigramEntryCount() + > DecayingUtils::MAX_BIGRAM_COUNT_AFTER_GC) { + // TODO: Remove more bigrams. + } + // Mapping from positions in mBuffer to positions in bufferToWrite. DictPositionRelocationMap dictPositionRelocationMap; readingHelper.initWithPtNodeArrayPos(rootPtNodeArrayPos); @@ -508,7 +524,8 @@ bool DynamicPatriciaTrieWritingHelper::runGC(const int rootPtNodeArrayPos, // Create policy instance for the GCed dictionary. DynamicShortcutListPolicy newDictShortcutPolicy(bufferToWrite); - DynamicBigramListPolicy newDictBigramPolicy(bufferToWrite, &newDictShortcutPolicy); + DynamicBigramListPolicy newDictBigramPolicy(bufferToWrite, &newDictShortcutPolicy, + mIsDecayingDict); // Create reading helper for the GCed dictionary. DynamicPatriciaTrieReadingHelper newDictReadingHelper(bufferToWrite, &newDictBigramPolicy, &newDictShortcutPolicy); @@ -525,4 +542,13 @@ bool DynamicPatriciaTrieWritingHelper::runGC(const int rootPtNodeArrayPos, return true; } +int DynamicPatriciaTrieWritingHelper::getUpdatedProbability(const int originalProbability, + const int newProbability) { + if (mIsDecayingDict) { + return DecayingUtils::getUpdatedUnigramProbability(originalProbability, newProbability); + } else { + return newProbability; + } +} + } // namespace latinime diff --git a/native/jni/src/suggest/policyimpl/dictionary/dynamic_patricia_trie_writing_helper.h b/native/jni/src/suggest/policyimpl/dictionary/dynamic_patricia_trie_writing_helper.h index 827b6097f..ecee2cdbf 100644 --- a/native/jni/src/suggest/policyimpl/dictionary/dynamic_patricia_trie_writing_helper.h +++ b/native/jni/src/suggest/policyimpl/dictionary/dynamic_patricia_trie_writing_helper.h @@ -47,10 +47,13 @@ class DynamicPatriciaTrieWritingHelper { DISALLOW_COPY_AND_ASSIGN(DictPositionRelocationMap); }; + static const size_t MAX_DICTIONARY_SIZE; + DynamicPatriciaTrieWritingHelper(BufferWithExtendableBuffer *const buffer, DynamicBigramListPolicy *const bigramPolicy, - DynamicShortcutListPolicy *const shortcutPolicy) - : mBuffer(buffer), mBigramPolicy(bigramPolicy), mShortcutPolicy(shortcutPolicy) {} + DynamicShortcutListPolicy *const shortcutPolicy, const bool isDecayingDict) + : mBuffer(buffer), mBigramPolicy(bigramPolicy), mShortcutPolicy(shortcutPolicy), + mIsDecayingDict(isDecayingDict) {} ~DynamicPatriciaTrieWritingHelper() {} @@ -87,11 +90,11 @@ class DynamicPatriciaTrieWritingHelper { DISALLOW_IMPLICIT_CONSTRUCTORS(DynamicPatriciaTrieWritingHelper); static const int CHILDREN_POSITION_FIELD_SIZE; - static const size_t MAX_DICTIONARY_SIZE; BufferWithExtendableBuffer *const mBuffer; DynamicBigramListPolicy *const mBigramPolicy; DynamicShortcutListPolicy *const mShortcutPolicy; + const bool mIsDecayingDict; bool markNodeAsMovedAndSetPosition(const DynamicPatriciaTrieNodeReader *const nodeToUpdate, const int movedPos, const int bigramLinkedNodePos); @@ -127,6 +130,8 @@ class DynamicPatriciaTrieWritingHelper { bool runGC(const int rootPtNodeArrayPos, BufferWithExtendableBuffer *const bufferToWrite, int *const outUnigramCount, int *const outBigramCount); + + int getUpdatedProbability(const int originalProbability, const int newProbability); }; } // namespace latinime #endif /* LATINIME_DYNAMIC_PATRICIA_TRIE_WRITING_HELPER_H */ diff --git a/native/jni/src/suggest/policyimpl/dictionary/header/header_policy.cpp b/native/jni/src/suggest/policyimpl/dictionary/header/header_policy.cpp index 78c6c042f..9ce9994dd 100644 --- a/native/jni/src/suggest/policyimpl/dictionary/header/header_policy.cpp +++ b/native/jni/src/suggest/policyimpl/dictionary/header/header_policy.cpp @@ -20,7 +20,8 @@ namespace latinime { // Note that these are corresponding definitions in Java side in FormatSpec.FileHeader. const char *const HeaderPolicy::MULTIPLE_WORDS_DEMOTION_RATE_KEY = "MULTIPLE_WORDS_DEMOTION_RATE"; -const char *const HeaderPolicy::USES_FORGETTING_CURVE_KEY = "USES_FORGETTING_CURVE"; +// TODO: Change attribute string to "IS_DECAYING_DICT". +const char *const HeaderPolicy::IS_DECAYING_DICT_KEY = "USES_FORGETTING_CURVE"; const char *const HeaderPolicy::LAST_UPDATED_TIME_KEY = "date"; const char *const HeaderPolicy::UNIGRAM_COUNT_KEY = "UNIGRAM_COUNT"; const char *const HeaderPolicy::BIGRAM_COUNT_KEY = "BIGRAM_COUNT"; diff --git a/native/jni/src/suggest/policyimpl/dictionary/header/header_policy.h b/native/jni/src/suggest/policyimpl/dictionary/header/header_policy.h index 93b9c6fcb..4261667fa 100644 --- a/native/jni/src/suggest/policyimpl/dictionary/header/header_policy.h +++ b/native/jni/src/suggest/policyimpl/dictionary/header/header_policy.h @@ -36,8 +36,8 @@ class HeaderPolicy : public DictionaryHeaderStructurePolicy { mSize(HeaderReadWriteUtils::getHeaderSize(dictBuf)), mAttributeMap(createAttributeMapAndReadAllAttributes(dictBuf)), mMultiWordCostMultiplier(readMultipleWordCostMultiplier()), - mUsesForgettingCurve(HeaderReadWriteUtils::readBoolAttributeValue(&mAttributeMap, - USES_FORGETTING_CURVE_KEY, false /* defaultValue */)), + mIsDecayingDict(HeaderReadWriteUtils::readBoolAttributeValue(&mAttributeMap, + IS_DECAYING_DICT_KEY, false /* defaultValue */)), mLastUpdatedTime(HeaderReadWriteUtils::readIntAttributeValue(&mAttributeMap, LAST_UPDATED_TIME_KEY, time(0) /* defaultValue */)), mUnigramCount(HeaderReadWriteUtils::readIntAttributeValue(&mAttributeMap, @@ -54,8 +54,8 @@ class HeaderPolicy : public DictionaryHeaderStructurePolicy { mDictionaryFlags(HeaderReadWriteUtils::createAndGetDictionaryFlagsUsingAttributeMap( attributeMap)), mSize(0), mAttributeMap(*attributeMap), mMultiWordCostMultiplier(readMultipleWordCostMultiplier()), - mUsesForgettingCurve(HeaderReadWriteUtils::readBoolAttributeValue(&mAttributeMap, - USES_FORGETTING_CURVE_KEY, false /* defaultValue */)), + mIsDecayingDict(HeaderReadWriteUtils::readBoolAttributeValue(&mAttributeMap, + IS_DECAYING_DICT_KEY, false /* defaultValue */)), mLastUpdatedTime(HeaderReadWriteUtils::readIntAttributeValue(&mAttributeMap, LAST_UPDATED_TIME_KEY, time(0) /* defaultValue */)), mUnigramCount(0), mBigramCount(0), mExtendedRegionSize(0) {} @@ -82,8 +82,8 @@ class HeaderPolicy : public DictionaryHeaderStructurePolicy { return mMultiWordCostMultiplier; } - AK_FORCE_INLINE bool usesForgettingCurve() const { - return mUsesForgettingCurve; + AK_FORCE_INLINE bool isDecayingDict() const { + return mIsDecayingDict; } AK_FORCE_INLINE int getLastUpdatedTime() const { @@ -113,7 +113,7 @@ class HeaderPolicy : public DictionaryHeaderStructurePolicy { DISALLOW_IMPLICIT_CONSTRUCTORS(HeaderPolicy); static const char *const MULTIPLE_WORDS_DEMOTION_RATE_KEY; - static const char *const USES_FORGETTING_CURVE_KEY; + static const char *const IS_DECAYING_DICT_KEY; static const char *const LAST_UPDATED_TIME_KEY; static const char *const UNIGRAM_COUNT_KEY; static const char *const BIGRAM_COUNT_KEY; @@ -126,7 +126,7 @@ class HeaderPolicy : public DictionaryHeaderStructurePolicy { const int mSize; HeaderReadWriteUtils::AttributeMap mAttributeMap; const float mMultiWordCostMultiplier; - const bool mUsesForgettingCurve; + const bool mIsDecayingDict; const int mLastUpdatedTime; const int mUnigramCount; const int mBigramCount; diff --git a/native/jni/src/suggest/policyimpl/dictionary/patricia_trie_policy.h b/native/jni/src/suggest/policyimpl/dictionary/patricia_trie_policy.h index 4277ff5d7..8d88c68e8 100644 --- a/native/jni/src/suggest/policyimpl/dictionary/patricia_trie_policy.h +++ b/native/jni/src/suggest/policyimpl/dictionary/patricia_trie_policy.h @@ -107,7 +107,7 @@ class PatriciaTriePolicy : public DictionaryStructureWithBufferPolicy { AKLOGI("Warning: flushWithGC() is called for non-updatable dictionary."); } - bool needsToRunGC() const { + bool needsToRunGC(const bool mindsBlockByGC) const { // This method should not be called for non-updatable dictionary. AKLOGI("Warning: needsToRunGC() is called for non-updatable dictionary."); return false; diff --git a/native/jni/src/suggest/policyimpl/dictionary/utils/buffer_with_extendable_buffer.h b/native/jni/src/suggest/policyimpl/dictionary/utils/buffer_with_extendable_buffer.h index 17d2e39c2..9dc34823c 100644 --- a/native/jni/src/suggest/policyimpl/dictionary/utils/buffer_with_extendable_buffer.h +++ b/native/jni/src/suggest/policyimpl/dictionary/utils/buffer_with_extendable_buffer.h @@ -42,6 +42,10 @@ class BufferWithExtendableBuffer { return mOriginalBufferSize + mUsedAdditionalBufferSize; } + AK_FORCE_INLINE int getUsedAdditionalBufferSize() const { + return mUsedAdditionalBufferSize; + } + /** * For reading. */ diff --git a/native/jni/src/suggest/policyimpl/dictionary/utils/decaying_utils.cpp b/native/jni/src/suggest/policyimpl/dictionary/utils/decaying_utils.cpp new file mode 100644 index 000000000..942a74238 --- /dev/null +++ b/native/jni/src/suggest/policyimpl/dictionary/utils/decaying_utils.cpp @@ -0,0 +1,129 @@ +/* + * Copyright (C) 2013, 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 "suggest/policyimpl/dictionary/utils/decaying_utils.h" + +#include "suggest/policyimpl/dictionary/utils/probability_utils.h" + +namespace latinime { + +const int DecayingUtils::MAX_UNIGRAM_COUNT = 12000; +const int DecayingUtils::MAX_UNIGRAM_COUNT_AFTER_GC = 10000; +const int DecayingUtils::MAX_BIGRAM_COUNT = 12000; +const int DecayingUtils::MAX_BIGRAM_COUNT_AFTER_GC = 10000; + +const int DecayingUtils::MAX_COMPUTED_PROBABILITY = 127; +const int DecayingUtils::MAX_UNIGRAM_PROBABILITY = 120; +const int DecayingUtils::MIN_VALID_UNIGRAM_PROBABILITY = 24; +const int DecayingUtils::UNIGRAM_PROBABILITY_STEP = 8; +const int DecayingUtils::MAX_BIGRAM_PROBABILITY_DELTA = 15; +const int DecayingUtils::MIN_VALID_BIGRAM_PROBABILITY_DELTA = 3; +const int DecayingUtils::BIGRAM_PROBABILITY_DELTA_STEP = 1; + +/* static */ int DecayingUtils::getProbability(const int encodedUnigramProbability, + const int encodedBigramProbabilityDelta) { + if (encodedUnigramProbability == NOT_A_PROBABILITY) { + return NOT_A_PROBABILITY; + } else if (encodedBigramProbabilityDelta == NOT_A_PROBABILITY) { + const int rawProbability = ProbabilityUtils::backoff(decodeUnigramProbability( + encodedUnigramProbability)); + return min(getDecayedProbability(rawProbability), MAX_COMPUTED_PROBABILITY); + } else { + const int rawProbability = ProbabilityUtils::computeProbabilityForBigram( + decodeUnigramProbability(encodedUnigramProbability), + decodeBigramProbabilityDelta(encodedBigramProbabilityDelta)); + return min(getDecayedProbability(rawProbability), MAX_COMPUTED_PROBABILITY); + } +} + +/* static */ int DecayingUtils::getUpdatedUnigramProbability(const int originalEncodedProbability, + const int newProbability) { + if (originalEncodedProbability == NOT_A_PROBABILITY) { + // The unigram is not in this dictionary. + if (newProbability == NOT_A_PROBABILITY) { + // The unigram is not in other dictionaries. + return 0; + } else { + return MIN_VALID_UNIGRAM_PROBABILITY; + } + } else { + if (newProbability != NOT_A_PROBABILITY + && originalEncodedProbability < MIN_VALID_UNIGRAM_PROBABILITY) { + return MIN_VALID_UNIGRAM_PROBABILITY; + } + return min(originalEncodedProbability + UNIGRAM_PROBABILITY_STEP, MAX_UNIGRAM_PROBABILITY); + } +} + +/* static */ int DecayingUtils::getUnigramProbabilityToSave(const int encodedProbability) { + return max(encodedProbability - UNIGRAM_PROBABILITY_STEP, 0); +} + +/* static */ int DecayingUtils::getBigramProbabilityDeltaToSave(const int encodedProbabilityDelta) { + return max(encodedProbabilityDelta - BIGRAM_PROBABILITY_DELTA_STEP, 0); +} + +/* static */ int DecayingUtils::getUpdatedBigramProbabilityDelta( + const int originalEncodedProbabilityDelta, const int newProbability) { + if (originalEncodedProbabilityDelta == NOT_A_PROBABILITY) { + // The bigram relation is not in this dictionary. + if (newProbability == NOT_A_PROBABILITY) { + // The bigram target is not in other dictionaries. + return 0; + } else { + return MIN_VALID_BIGRAM_PROBABILITY_DELTA; + } + } else { + if (newProbability != NOT_A_PROBABILITY + && originalEncodedProbabilityDelta < MIN_VALID_BIGRAM_PROBABILITY_DELTA) { + return MIN_VALID_BIGRAM_PROBABILITY_DELTA; + } + return min(originalEncodedProbabilityDelta + BIGRAM_PROBABILITY_DELTA_STEP, + MAX_BIGRAM_PROBABILITY_DELTA); + } +} + +/* static */ int DecayingUtils::isValidUnigram(const int encodedUnigramProbability) { + return encodedUnigramProbability >= MIN_VALID_UNIGRAM_PROBABILITY; +} + +/* static */ int DecayingUtils::isValidBigram(const int encodedBigramProbabilityDelta) { + return encodedBigramProbabilityDelta >= MIN_VALID_BIGRAM_PROBABILITY_DELTA; +} + +/* static */ int DecayingUtils::decodeUnigramProbability(const int encodedProbability) { + const int probability = encodedProbability - MIN_VALID_UNIGRAM_PROBABILITY; + if (probability < 0) { + return NOT_A_PROBABILITY; + } else { + return min(probability, MAX_UNIGRAM_PROBABILITY); + } +} + +/* static */ int DecayingUtils::decodeBigramProbabilityDelta(const int encodedProbabilityDelta) { + const int probabilityDelta = encodedProbabilityDelta - MIN_VALID_BIGRAM_PROBABILITY_DELTA; + if (probabilityDelta < 0) { + return NOT_A_PROBABILITY; + } else { + return min(probabilityDelta, MAX_BIGRAM_PROBABILITY_DELTA); + } +} + +/* static */ int DecayingUtils::getDecayedProbability(const int rawProbability) { + return rawProbability; +} + +} // namespace latinime diff --git a/native/jni/src/suggest/policyimpl/dictionary/utils/decaying_utils.h b/native/jni/src/suggest/policyimpl/dictionary/utils/decaying_utils.h new file mode 100644 index 000000000..1ca03918f --- /dev/null +++ b/native/jni/src/suggest/policyimpl/dictionary/utils/decaying_utils.h @@ -0,0 +1,70 @@ +/* + * Copyright (C) 2013, 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_DECAYING_UTILS_H +#define LATINIME_DECAYING_UTILS_H + +#include "defines.h" + +namespace latinime { + +// TODO: Check the elapsed time and decrease the probability depending on the time. Time field is +// required to introduced to each terminal PtNode and bigram entry. +// TODO: Quit using bigram probability to indicate the delta. +// TODO: Quit using bigram probability delta. +class DecayingUtils { + public: + static const int MAX_UNIGRAM_COUNT; + static const int MAX_UNIGRAM_COUNT_AFTER_GC; + static const int MAX_BIGRAM_COUNT; + static const int MAX_BIGRAM_COUNT_AFTER_GC; + + static int getProbability(const int encodedUnigramProbability, + const int encodedBigramProbabilityDelta); + + static int getUpdatedUnigramProbability(const int originalEncodedProbability, + const int newProbability); + + static int getUpdatedBigramProbabilityDelta(const int originalEncodedProbabilityDelta, + const int newProbability); + + static int isValidUnigram(const int encodedUnigramProbability); + + static int isValidBigram(const int encodedProbabilityDelta); + + static int getUnigramProbabilityToSave(const int encodedProbability); + + static int getBigramProbabilityDeltaToSave(const int encodedProbabilityDelta); + + private: + DISALLOW_IMPLICIT_CONSTRUCTORS(DecayingUtils); + + static const int MAX_COMPUTED_PROBABILITY; + static const int MAX_UNIGRAM_PROBABILITY; + static const int MIN_VALID_UNIGRAM_PROBABILITY; + static const int UNIGRAM_PROBABILITY_STEP; + static const int MAX_BIGRAM_PROBABILITY_DELTA; + static const int MIN_VALID_BIGRAM_PROBABILITY_DELTA; + static const int BIGRAM_PROBABILITY_DELTA_STEP; + + static int decodeUnigramProbability(const int encodedProbability); + + static int decodeBigramProbabilityDelta(const int encodedProbability); + + static int getDecayedProbability(const int rawProbability); +}; +} // namespace latinime +#endif /* LATINIME_DECAYING_UTILS_H */ diff --git a/native/jni/src/suggest/policyimpl/dictionary/utils/dict_file_writing_utils.cpp b/native/jni/src/suggest/policyimpl/dictionary/utils/dict_file_writing_utils.cpp index 4fae91936..f22e94c6a 100644 --- a/native/jni/src/suggest/policyimpl/dictionary/utils/dict_file_writing_utils.cpp +++ b/native/jni/src/suggest/policyimpl/dictionary/utils/dict_file_writing_utils.cpp @@ -96,7 +96,7 @@ const char *const DictFileWritingUtils::TEMP_FILE_SUFFIX_FOR_WRITING_DICT_FILE = fclose(file); return false; } - const int additionalBufSize = buffer->getTailPosition() - buffer->getOriginalBufferSize(); + const int additionalBufSize = buffer->getUsedAdditionalBufferSize(); if (additionalBufSize > 0 && fwrite(buffer->getBuffer(true /* usesAdditionalBuffer */), additionalBufSize, 1, file) < 1) { fclose(file); diff --git a/native/jni/src/suggest/policyimpl/typing/typing_weighting.cpp b/native/jni/src/suggest/policyimpl/typing/typing_weighting.cpp index 408b12ae9..5b6b5e874 100644 --- a/native/jni/src/suggest/policyimpl/typing/typing_weighting.cpp +++ b/native/jni/src/suggest/policyimpl/typing/typing_weighting.cpp @@ -47,7 +47,7 @@ ErrorType TypingWeighting::getErrorType(const CorrectionType correctionType, case CT_TERMINAL_INSERTION: case CT_TRANSPOSITION: return ET_EDIT_CORRECTION; - case CT_NEW_WORD_SPACE_OMITTION: + case CT_NEW_WORD_SPACE_OMISSION: case CT_NEW_WORD_SPACE_SUBSTITUTION: return ET_NEW_WORD; case CT_TERMINAL: |