| /* |
| * 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/forgetting_curve_utils.h" |
| |
| #include <algorithm> |
| #include <cmath> |
| #include <stdlib.h> |
| |
| #include "suggest/policyimpl/dictionary/header/header_policy.h" |
| #include "suggest/policyimpl/dictionary/utils/probability_utils.h" |
| #include "utils/time_keeper.h" |
| |
| namespace latinime { |
| |
| const int ForgettingCurveUtils::MULTIPLIER_TWO_IN_PROBABILITY_SCALE = 8; |
| const int ForgettingCurveUtils::DECAY_INTERVAL_SECONDS = 2 * 60 * 60; |
| |
| const int ForgettingCurveUtils::MAX_LEVEL = 15; |
| const int ForgettingCurveUtils::MIN_VISIBLE_LEVEL = 2; |
| const int ForgettingCurveUtils::MAX_ELAPSED_TIME_STEP_COUNT = 31; |
| const int ForgettingCurveUtils::DISCARD_LEVEL_ZERO_ENTRY_TIME_STEP_COUNT_THRESHOLD = 30; |
| const int ForgettingCurveUtils::OCCURRENCES_TO_RAISE_THE_LEVEL = 1; |
| // TODO: Evaluate whether this should be 7.5 days. |
| // 15 days |
| const int ForgettingCurveUtils::DURATION_TO_LOWER_THE_LEVEL_IN_SECONDS = 15 * 24 * 60 * 60; |
| |
| const float ForgettingCurveUtils::UNIGRAM_COUNT_HARD_LIMIT_WEIGHT = 1.2; |
| const float ForgettingCurveUtils::BIGRAM_COUNT_HARD_LIMIT_WEIGHT = 1.2; |
| |
| const ForgettingCurveUtils::ProbabilityTable ForgettingCurveUtils::sProbabilityTable; |
| |
| // TODO: Revise the logic to decide the initial probability depending on the given probability. |
| /* static */ const HistoricalInfo ForgettingCurveUtils::createUpdatedHistoricalInfo( |
| const HistoricalInfo *const originalHistoricalInfo, const int newProbability, |
| const HistoricalInfo *const newHistoricalInfo, const HeaderPolicy *const headerPolicy) { |
| const int timestamp = newHistoricalInfo->getTimestamp(); |
| if (newProbability != NOT_A_PROBABILITY && originalHistoricalInfo->getLevel() == 0) { |
| // Add entry as a valid word. |
| const int level = clampToVisibleEntryLevelRange(newHistoricalInfo->getLevel()); |
| const int count = clampToValidCountRange(newHistoricalInfo->getCount(), headerPolicy); |
| return HistoricalInfo(timestamp, level, count); |
| } else if (!originalHistoricalInfo->isValid() |
| || originalHistoricalInfo->getLevel() < newHistoricalInfo->getLevel() |
| || (originalHistoricalInfo->getLevel() == newHistoricalInfo->getLevel() |
| && originalHistoricalInfo->getCount() < newHistoricalInfo->getCount())) { |
| // Initial information. |
| int count = newHistoricalInfo->getCount(); |
| if (count >= OCCURRENCES_TO_RAISE_THE_LEVEL) { |
| const int level = clampToValidLevelRange(newHistoricalInfo->getLevel() + 1); |
| return HistoricalInfo(timestamp, level, 0 /* count */); |
| } |
| const int level = clampToValidLevelRange(newHistoricalInfo->getLevel()); |
| return HistoricalInfo(timestamp, level, clampToValidCountRange(count, headerPolicy)); |
| } else { |
| const int updatedCount = originalHistoricalInfo->getCount() + 1; |
| if (updatedCount >= OCCURRENCES_TO_RAISE_THE_LEVEL) { |
| // The count exceeds the max value the level can be incremented. |
| if (originalHistoricalInfo->getLevel() >= MAX_LEVEL) { |
| // The level is already max. |
| return HistoricalInfo(timestamp, |
| originalHistoricalInfo->getLevel(), originalHistoricalInfo->getCount()); |
| } else { |
| // Raise the level. |
| return HistoricalInfo(timestamp, |
| originalHistoricalInfo->getLevel() + 1, 0 /* count */); |
| } |
| } else { |
| return HistoricalInfo(timestamp, originalHistoricalInfo->getLevel(), updatedCount); |
| } |
| } |
| } |
| |
| /* static */ int ForgettingCurveUtils::decodeProbability( |
| const HistoricalInfo *const historicalInfo, const HeaderPolicy *const headerPolicy) { |
| const int elapsedTimeStepCount = getElapsedTimeStepCount(historicalInfo->getTimestamp(), |
| DURATION_TO_LOWER_THE_LEVEL_IN_SECONDS); |
| return sProbabilityTable.getProbability( |
| headerPolicy->getForgettingCurveProbabilityValuesTableId(), |
| clampToValidLevelRange(historicalInfo->getLevel()), |
| clampToValidTimeStepCountRange(elapsedTimeStepCount)); |
| } |
| |
| /* static */ bool ForgettingCurveUtils::needsToKeep(const HistoricalInfo *const historicalInfo, |
| const HeaderPolicy *const headerPolicy) { |
| return historicalInfo->getLevel() > 0 |
| || getElapsedTimeStepCount(historicalInfo->getTimestamp(), |
| DURATION_TO_LOWER_THE_LEVEL_IN_SECONDS) |
| < DISCARD_LEVEL_ZERO_ENTRY_TIME_STEP_COUNT_THRESHOLD; |
| } |
| |
| /* static */ const HistoricalInfo ForgettingCurveUtils::createHistoricalInfoToSave( |
| const HistoricalInfo *const originalHistoricalInfo, |
| const HeaderPolicy *const headerPolicy) { |
| if (originalHistoricalInfo->getTimestamp() == NOT_A_TIMESTAMP) { |
| return HistoricalInfo(); |
| } |
| const int durationToLevelDownInSeconds = DURATION_TO_LOWER_THE_LEVEL_IN_SECONDS; |
| const int elapsedTimeStep = getElapsedTimeStepCount( |
| originalHistoricalInfo->getTimestamp(), durationToLevelDownInSeconds); |
| if (elapsedTimeStep <= MAX_ELAPSED_TIME_STEP_COUNT) { |
| // No need to update historical info. |
| return *originalHistoricalInfo; |
| } |
| // Lower the level. |
| const int maxLevelDownAmonut = elapsedTimeStep / (MAX_ELAPSED_TIME_STEP_COUNT + 1); |
| const int levelDownAmount = (maxLevelDownAmonut >= originalHistoricalInfo->getLevel()) ? |
| originalHistoricalInfo->getLevel() : maxLevelDownAmonut; |
| const int adjustedTimestampInSeconds = originalHistoricalInfo->getTimestamp() + |
| levelDownAmount * durationToLevelDownInSeconds; |
| return HistoricalInfo(adjustedTimestampInSeconds, |
| originalHistoricalInfo->getLevel() - levelDownAmount, 0 /* count */); |
| } |
| |
| /* static */ bool ForgettingCurveUtils::needsToDecay(const bool mindsBlockByDecay, |
| const int unigramCount, const int bigramCount, const HeaderPolicy *const headerPolicy) { |
| if (unigramCount >= getUnigramCountHardLimit(headerPolicy->getMaxUnigramCount())) { |
| // Unigram count exceeds the limit. |
| return true; |
| } else if (bigramCount >= getBigramCountHardLimit(headerPolicy->getMaxBigramCount())) { |
| // Bigram count exceeds the limit. |
| return true; |
| } |
| if (mindsBlockByDecay) { |
| return false; |
| } |
| if (headerPolicy->getLastDecayedTime() + DECAY_INTERVAL_SECONDS |
| < TimeKeeper::peekCurrentTime()) { |
| // Time to decay. |
| return true; |
| } |
| return false; |
| } |
| |
| // See comments in ProbabilityUtils::backoff(). |
| /* static */ int ForgettingCurveUtils::backoff(const int unigramProbability) { |
| // See TODO comments in ForgettingCurveUtils::getProbability(). |
| return unigramProbability; |
| } |
| |
| /* static */ int ForgettingCurveUtils::getElapsedTimeStepCount(const int timestamp, |
| const int durationToLevelDownInSeconds) { |
| const int elapsedTimeInSeconds = TimeKeeper::peekCurrentTime() - timestamp; |
| const int timeStepDurationInSeconds = |
| durationToLevelDownInSeconds / (MAX_ELAPSED_TIME_STEP_COUNT + 1); |
| return elapsedTimeInSeconds / timeStepDurationInSeconds; |
| } |
| |
| /* static */ int ForgettingCurveUtils::clampToVisibleEntryLevelRange(const int level) { |
| return std::min(std::max(level, MIN_VISIBLE_LEVEL), MAX_LEVEL); |
| } |
| |
| /* static */ int ForgettingCurveUtils::clampToValidCountRange(const int count, |
| const HeaderPolicy *const headerPolicy) { |
| return std::min(std::max(count, 0), OCCURRENCES_TO_RAISE_THE_LEVEL - 1); |
| } |
| |
| /* static */ int ForgettingCurveUtils::clampToValidLevelRange(const int level) { |
| return std::min(std::max(level, 0), MAX_LEVEL); |
| } |
| |
| /* static */ int ForgettingCurveUtils::clampToValidTimeStepCountRange(const int timeStepCount) { |
| return std::min(std::max(timeStepCount, 0), MAX_ELAPSED_TIME_STEP_COUNT); |
| } |
| |
| const int ForgettingCurveUtils::ProbabilityTable::PROBABILITY_TABLE_COUNT = 4; |
| const int ForgettingCurveUtils::ProbabilityTable::WEAK_PROBABILITY_TABLE_ID = 0; |
| const int ForgettingCurveUtils::ProbabilityTable::MODEST_PROBABILITY_TABLE_ID = 1; |
| const int ForgettingCurveUtils::ProbabilityTable::STRONG_PROBABILITY_TABLE_ID = 2; |
| const int ForgettingCurveUtils::ProbabilityTable::AGGRESSIVE_PROBABILITY_TABLE_ID = 3; |
| const int ForgettingCurveUtils::ProbabilityTable::WEAK_MAX_PROBABILITY = 127; |
| const int ForgettingCurveUtils::ProbabilityTable::MODEST_BASE_PROBABILITY = 8; |
| const int ForgettingCurveUtils::ProbabilityTable::STRONG_BASE_PROBABILITY = 9; |
| const int ForgettingCurveUtils::ProbabilityTable::AGGRESSIVE_BASE_PROBABILITY = 10; |
| |
| |
| ForgettingCurveUtils::ProbabilityTable::ProbabilityTable() : mTables() { |
| mTables.resize(PROBABILITY_TABLE_COUNT); |
| for (int tableId = 0; tableId < PROBABILITY_TABLE_COUNT; ++tableId) { |
| mTables[tableId].resize(MAX_LEVEL + 1); |
| for (int level = 0; level <= MAX_LEVEL; ++level) { |
| mTables[tableId][level].resize(MAX_ELAPSED_TIME_STEP_COUNT + 1); |
| const float initialProbability = getBaseProbabilityForLevel(tableId, level); |
| const float endProbability = getBaseProbabilityForLevel(tableId, level - 1); |
| for (int timeStepCount = 0; timeStepCount <= MAX_ELAPSED_TIME_STEP_COUNT; |
| ++timeStepCount) { |
| if (level < MIN_VISIBLE_LEVEL) { |
| mTables[tableId][level][timeStepCount] = NOT_A_PROBABILITY; |
| continue; |
| } |
| const float probability = initialProbability |
| * powf(initialProbability / endProbability, |
| -1.0f * static_cast<float>(timeStepCount) |
| / static_cast<float>(MAX_ELAPSED_TIME_STEP_COUNT + 1)); |
| mTables[tableId][level][timeStepCount] = |
| std::min(std::max(static_cast<int>(probability), 1), MAX_PROBABILITY); |
| } |
| } |
| } |
| } |
| |
| /* static */ int ForgettingCurveUtils::ProbabilityTable::getBaseProbabilityForLevel( |
| const int tableId, const int level) { |
| if (tableId == WEAK_PROBABILITY_TABLE_ID) { |
| // Max probability is 127. |
| return static_cast<float>(WEAK_MAX_PROBABILITY / (1 << (MAX_LEVEL - level))); |
| } else if (tableId == MODEST_PROBABILITY_TABLE_ID) { |
| // Max probability is 128. |
| return static_cast<float>(MODEST_BASE_PROBABILITY * (level + 1)); |
| } else if (tableId == STRONG_PROBABILITY_TABLE_ID) { |
| // Max probability is 140. |
| return static_cast<float>(STRONG_BASE_PROBABILITY * (level + 1)); |
| } else if (tableId == AGGRESSIVE_PROBABILITY_TABLE_ID) { |
| // Max probability is 160. |
| return static_cast<float>(AGGRESSIVE_BASE_PROBABILITY * (level + 1)); |
| } else { |
| return NOT_A_PROBABILITY; |
| } |
| } |
| |
| } // namespace latinime |