1fd02b2d6ee55d4aee7faab89a7a2b72764eafc47Keisuke Kuroyanagi/* 2fd02b2d6ee55d4aee7faab89a7a2b72764eafc47Keisuke Kuroyanagi * Copyright (C) 2013, The Android Open Source Project 3fd02b2d6ee55d4aee7faab89a7a2b72764eafc47Keisuke Kuroyanagi * 4fd02b2d6ee55d4aee7faab89a7a2b72764eafc47Keisuke Kuroyanagi * Licensed under the Apache License, Version 2.0 (the "License"); 5fd02b2d6ee55d4aee7faab89a7a2b72764eafc47Keisuke Kuroyanagi * you may not use this file except in compliance with the License. 6fd02b2d6ee55d4aee7faab89a7a2b72764eafc47Keisuke Kuroyanagi * You may obtain a copy of the License at 7fd02b2d6ee55d4aee7faab89a7a2b72764eafc47Keisuke Kuroyanagi * 8fd02b2d6ee55d4aee7faab89a7a2b72764eafc47Keisuke Kuroyanagi * http://www.apache.org/licenses/LICENSE-2.0 9fd02b2d6ee55d4aee7faab89a7a2b72764eafc47Keisuke Kuroyanagi * 10fd02b2d6ee55d4aee7faab89a7a2b72764eafc47Keisuke Kuroyanagi * Unless required by applicable law or agreed to in writing, software 11fd02b2d6ee55d4aee7faab89a7a2b72764eafc47Keisuke Kuroyanagi * distributed under the License is distributed on an "AS IS" BASIS, 12fd02b2d6ee55d4aee7faab89a7a2b72764eafc47Keisuke Kuroyanagi * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 13fd02b2d6ee55d4aee7faab89a7a2b72764eafc47Keisuke Kuroyanagi * See the License for the specific language governing permissions and 14fd02b2d6ee55d4aee7faab89a7a2b72764eafc47Keisuke Kuroyanagi * limitations under the License. 15fd02b2d6ee55d4aee7faab89a7a2b72764eafc47Keisuke Kuroyanagi */ 16fd02b2d6ee55d4aee7faab89a7a2b72764eafc47Keisuke Kuroyanagi 1788bc312ad34321fb3e81be2dc939a889d065f4a7Keisuke Kuroyanagi#include "dictionary/utils/forgetting_curve_utils.h" 182fa3693c264a4c150ac307d9bb7f6f8f18cc4ffcKen Wakasa 19865e6cf49764f3a411ee32861d927b15653ee398Keisuke Kuroyanagi#include <algorithm> 207c4dcf1e918c2b9251e7aa907d991a3ab8764bafKeisuke Kuroyanagi#include <cmath> 21c76bbceedc804d1f2988cbf032b530a107a7d561Keisuke Kuroyanagi#include <stdlib.h> 22c76bbceedc804d1f2988cbf032b530a107a7d561Keisuke Kuroyanagi 2388bc312ad34321fb3e81be2dc939a889d065f4a7Keisuke Kuroyanagi#include "dictionary/header/header_policy.h" 2488bc312ad34321fb3e81be2dc939a889d065f4a7Keisuke Kuroyanagi#include "dictionary/utils/probability_utils.h" 252fa3693c264a4c150ac307d9bb7f6f8f18cc4ffcKen Wakasa#include "utils/time_keeper.h" 26fd02b2d6ee55d4aee7faab89a7a2b72764eafc47Keisuke Kuroyanagi 27fd02b2d6ee55d4aee7faab89a7a2b72764eafc47Keisuke Kuroyanaginamespace latinime { 28fd02b2d6ee55d4aee7faab89a7a2b72764eafc47Keisuke Kuroyanagi 29b368089dbfabb84d1af4ad76d331b7add849c33bKeisuke Kuroyanagiconst int ForgettingCurveUtils::MULTIPLIER_TWO_IN_PROBABILITY_SCALE = 8; 3067c855ea6f882190d73df9d3fae0b56929fd6888Keisuke Kuroyanagiconst int ForgettingCurveUtils::DECAY_INTERVAL_SECONDS = 2 * 60 * 60; 31fd02b2d6ee55d4aee7faab89a7a2b72764eafc47Keisuke Kuroyanagi 32aae1a062eb98e7634fb4da996ec604bbefd4ddf5Keisuke Kuroyanagiconst int ForgettingCurveUtils::MAX_LEVEL = 15; 33aae1a062eb98e7634fb4da996ec604bbefd4ddf5Keisuke Kuroyanagiconst int ForgettingCurveUtils::MIN_VISIBLE_LEVEL = 2; 34aae1a062eb98e7634fb4da996ec604bbefd4ddf5Keisuke Kuroyanagiconst int ForgettingCurveUtils::MAX_ELAPSED_TIME_STEP_COUNT = 31; 35aae1a062eb98e7634fb4da996ec604bbefd4ddf5Keisuke Kuroyanagiconst int ForgettingCurveUtils::DISCARD_LEVEL_ZERO_ENTRY_TIME_STEP_COUNT_THRESHOLD = 30; 36aae1a062eb98e7634fb4da996ec604bbefd4ddf5Keisuke Kuroyanagiconst int ForgettingCurveUtils::OCCURRENCES_TO_RAISE_THE_LEVEL = 1; 37aae1a062eb98e7634fb4da996ec604bbefd4ddf5Keisuke Kuroyanagi// TODO: Evaluate whether this should be 7.5 days. 38aae1a062eb98e7634fb4da996ec604bbefd4ddf5Keisuke Kuroyanagi// 15 days 39aae1a062eb98e7634fb4da996ec604bbefd4ddf5Keisuke Kuroyanagiconst int ForgettingCurveUtils::DURATION_TO_LOWER_THE_LEVEL_IN_SECONDS = 15 * 24 * 60 * 60; 4067c855ea6f882190d73df9d3fae0b56929fd6888Keisuke Kuroyanagi 41e8750d970eed61b9239d8b2fa19648b8457696c1Keisuke Kuroyanagiconst float ForgettingCurveUtils::ENTRY_COUNT_HARD_LIMIT_WEIGHT = 1.2; 425128935ac4d7961e3c863270b828e47a79b97235Keisuke Kuroyanagi 432fa3693c264a4c150ac307d9bb7f6f8f18cc4ffcKen Wakasaconst ForgettingCurveUtils::ProbabilityTable ForgettingCurveUtils::sProbabilityTable; 447c4dcf1e918c2b9251e7aa907d991a3ab8764bafKeisuke Kuroyanagi 4505113c1847e5c41aab3176eb015aabc2acdc0a51Keisuke Kuroyanagi// TODO: Revise the logic to decide the initial probability depending on the given probability. 462fa3693c264a4c150ac307d9bb7f6f8f18cc4ffcKen Wakasa/* static */ const HistoricalInfo ForgettingCurveUtils::createUpdatedHistoricalInfo( 479d7e8c717f56a8b706a174fd3d5a2864d08d320cKeisuke Kuroyanagi const HistoricalInfo *const originalHistoricalInfo, const int newProbability, 489d7e8c717f56a8b706a174fd3d5a2864d08d320cKeisuke Kuroyanagi const HistoricalInfo *const newHistoricalInfo, const HeaderPolicy *const headerPolicy) { 49287e155e44b4e937f2a62d010805702bc813c43bKeisuke Kuroyanagi const int timestamp = newHistoricalInfo->getTimestamp(); 502fa3693c264a4c150ac307d9bb7f6f8f18cc4ffcKen Wakasa if (newProbability != NOT_A_PROBABILITY && originalHistoricalInfo->getLevel() == 0) { 519d7e8c717f56a8b706a174fd3d5a2864d08d320cKeisuke Kuroyanagi // Add entry as a valid word. 529d7e8c717f56a8b706a174fd3d5a2864d08d320cKeisuke Kuroyanagi const int level = clampToVisibleEntryLevelRange(newHistoricalInfo->getLevel()); 539d7e8c717f56a8b706a174fd3d5a2864d08d320cKeisuke Kuroyanagi const int count = clampToValidCountRange(newHistoricalInfo->getCount(), headerPolicy); 549d7e8c717f56a8b706a174fd3d5a2864d08d320cKeisuke Kuroyanagi return HistoricalInfo(timestamp, level, count); 559d7e8c717f56a8b706a174fd3d5a2864d08d320cKeisuke Kuroyanagi } else if (!originalHistoricalInfo->isValid() 569d7e8c717f56a8b706a174fd3d5a2864d08d320cKeisuke Kuroyanagi || originalHistoricalInfo->getLevel() < newHistoricalInfo->getLevel() 579d7e8c717f56a8b706a174fd3d5a2864d08d320cKeisuke Kuroyanagi || (originalHistoricalInfo->getLevel() == newHistoricalInfo->getLevel() 589d7e8c717f56a8b706a174fd3d5a2864d08d320cKeisuke Kuroyanagi && originalHistoricalInfo->getCount() < newHistoricalInfo->getCount())) { 592fa3693c264a4c150ac307d9bb7f6f8f18cc4ffcKen Wakasa // Initial information. 60aae1a062eb98e7634fb4da996ec604bbefd4ddf5Keisuke Kuroyanagi int count = newHistoricalInfo->getCount(); 61aae1a062eb98e7634fb4da996ec604bbefd4ddf5Keisuke Kuroyanagi if (count >= OCCURRENCES_TO_RAISE_THE_LEVEL) { 62aae1a062eb98e7634fb4da996ec604bbefd4ddf5Keisuke Kuroyanagi const int level = clampToValidLevelRange(newHistoricalInfo->getLevel() + 1); 63aae1a062eb98e7634fb4da996ec604bbefd4ddf5Keisuke Kuroyanagi return HistoricalInfo(timestamp, level, 0 /* count */); 64aae1a062eb98e7634fb4da996ec604bbefd4ddf5Keisuke Kuroyanagi } 659d7e8c717f56a8b706a174fd3d5a2864d08d320cKeisuke Kuroyanagi const int level = clampToValidLevelRange(newHistoricalInfo->getLevel()); 66aae1a062eb98e7634fb4da996ec604bbefd4ddf5Keisuke Kuroyanagi return HistoricalInfo(timestamp, level, clampToValidCountRange(count, headerPolicy)); 67fd02b2d6ee55d4aee7faab89a7a2b72764eafc47Keisuke Kuroyanagi } else { 682fa3693c264a4c150ac307d9bb7f6f8f18cc4ffcKen Wakasa const int updatedCount = originalHistoricalInfo->getCount() + 1; 69aae1a062eb98e7634fb4da996ec604bbefd4ddf5Keisuke Kuroyanagi if (updatedCount >= OCCURRENCES_TO_RAISE_THE_LEVEL) { 702fa3693c264a4c150ac307d9bb7f6f8f18cc4ffcKen Wakasa // The count exceeds the max value the level can be incremented. 712fa3693c264a4c150ac307d9bb7f6f8f18cc4ffcKen Wakasa if (originalHistoricalInfo->getLevel() >= MAX_LEVEL) { 722fa3693c264a4c150ac307d9bb7f6f8f18cc4ffcKen Wakasa // The level is already max. 739d7e8c717f56a8b706a174fd3d5a2864d08d320cKeisuke Kuroyanagi return HistoricalInfo(timestamp, 749d7e8c717f56a8b706a174fd3d5a2864d08d320cKeisuke Kuroyanagi originalHistoricalInfo->getLevel(), originalHistoricalInfo->getCount()); 752fa3693c264a4c150ac307d9bb7f6f8f18cc4ffcKen Wakasa } else { 76aae1a062eb98e7634fb4da996ec604bbefd4ddf5Keisuke Kuroyanagi // Raise the level. 779d7e8c717f56a8b706a174fd3d5a2864d08d320cKeisuke Kuroyanagi return HistoricalInfo(timestamp, 789d7e8c717f56a8b706a174fd3d5a2864d08d320cKeisuke Kuroyanagi originalHistoricalInfo->getLevel() + 1, 0 /* count */); 792fa3693c264a4c150ac307d9bb7f6f8f18cc4ffcKen Wakasa } 802fa3693c264a4c150ac307d9bb7f6f8f18cc4ffcKen Wakasa } else { 812fa3693c264a4c150ac307d9bb7f6f8f18cc4ffcKen Wakasa return HistoricalInfo(timestamp, originalHistoricalInfo->getLevel(), updatedCount); 822fa3693c264a4c150ac307d9bb7f6f8f18cc4ffcKen Wakasa } 83fd02b2d6ee55d4aee7faab89a7a2b72764eafc47Keisuke Kuroyanagi } 84fd02b2d6ee55d4aee7faab89a7a2b72764eafc47Keisuke Kuroyanagi} 85fd02b2d6ee55d4aee7faab89a7a2b72764eafc47Keisuke Kuroyanagi 862fa3693c264a4c150ac307d9bb7f6f8f18cc4ffcKen Wakasa/* static */ int ForgettingCurveUtils::decodeProbability( 8757816c7a8bac1a47913da7a503ece2b5dd7cc0fcKeisuke Kuroyanagi const HistoricalInfo *const historicalInfo, const HeaderPolicy *const headerPolicy) { 88287e155e44b4e937f2a62d010805702bc813c43bKeisuke Kuroyanagi const int elapsedTimeStepCount = getElapsedTimeStepCount(historicalInfo->getTimestamp(), 89aae1a062eb98e7634fb4da996ec604bbefd4ddf5Keisuke Kuroyanagi DURATION_TO_LOWER_THE_LEVEL_IN_SECONDS); 9057816c7a8bac1a47913da7a503ece2b5dd7cc0fcKeisuke Kuroyanagi return sProbabilityTable.getProbability( 91cf88cf65936962373797d14694011b15d0f4c5f0Keisuke Kuroyanagi headerPolicy->getForgettingCurveProbabilityValuesTableId(), 929d7e8c717f56a8b706a174fd3d5a2864d08d320cKeisuke Kuroyanagi clampToValidLevelRange(historicalInfo->getLevel()), 939d7e8c717f56a8b706a174fd3d5a2864d08d320cKeisuke Kuroyanagi clampToValidTimeStepCountRange(elapsedTimeStepCount)); 942fa3693c264a4c150ac307d9bb7f6f8f18cc4ffcKen Wakasa} 952fa3693c264a4c150ac307d9bb7f6f8f18cc4ffcKen Wakasa 965128935ac4d7961e3c863270b828e47a79b97235Keisuke Kuroyanagi/* static */ bool ForgettingCurveUtils::needsToKeep(const HistoricalInfo *const historicalInfo, 975128935ac4d7961e3c863270b828e47a79b97235Keisuke Kuroyanagi const HeaderPolicy *const headerPolicy) { 982fa3693c264a4c150ac307d9bb7f6f8f18cc4ffcKen Wakasa return historicalInfo->getLevel() > 0 99287e155e44b4e937f2a62d010805702bc813c43bKeisuke Kuroyanagi || getElapsedTimeStepCount(historicalInfo->getTimestamp(), 100aae1a062eb98e7634fb4da996ec604bbefd4ddf5Keisuke Kuroyanagi DURATION_TO_LOWER_THE_LEVEL_IN_SECONDS) 1015128935ac4d7961e3c863270b828e47a79b97235Keisuke Kuroyanagi < DISCARD_LEVEL_ZERO_ENTRY_TIME_STEP_COUNT_THRESHOLD; 102fd02b2d6ee55d4aee7faab89a7a2b72764eafc47Keisuke Kuroyanagi} 103fd02b2d6ee55d4aee7faab89a7a2b72764eafc47Keisuke Kuroyanagi 1042fa3693c264a4c150ac307d9bb7f6f8f18cc4ffcKen Wakasa/* static */ const HistoricalInfo ForgettingCurveUtils::createHistoricalInfoToSave( 10557816c7a8bac1a47913da7a503ece2b5dd7cc0fcKeisuke Kuroyanagi const HistoricalInfo *const originalHistoricalInfo, 10657816c7a8bac1a47913da7a503ece2b5dd7cc0fcKeisuke Kuroyanagi const HeaderPolicy *const headerPolicy) { 107287e155e44b4e937f2a62d010805702bc813c43bKeisuke Kuroyanagi if (originalHistoricalInfo->getTimestamp() == NOT_A_TIMESTAMP) { 1082fa3693c264a4c150ac307d9bb7f6f8f18cc4ffcKen Wakasa return HistoricalInfo(); 10967c855ea6f882190d73df9d3fae0b56929fd6888Keisuke Kuroyanagi } 110aae1a062eb98e7634fb4da996ec604bbefd4ddf5Keisuke Kuroyanagi const int durationToLevelDownInSeconds = DURATION_TO_LOWER_THE_LEVEL_IN_SECONDS; 1115128935ac4d7961e3c863270b828e47a79b97235Keisuke Kuroyanagi const int elapsedTimeStep = getElapsedTimeStepCount( 112287e155e44b4e937f2a62d010805702bc813c43bKeisuke Kuroyanagi originalHistoricalInfo->getTimestamp(), durationToLevelDownInSeconds); 1132fa3693c264a4c150ac307d9bb7f6f8f18cc4ffcKen Wakasa if (elapsedTimeStep <= MAX_ELAPSED_TIME_STEP_COUNT) { 1142fa3693c264a4c150ac307d9bb7f6f8f18cc4ffcKen Wakasa // No need to update historical info. 1152fa3693c264a4c150ac307d9bb7f6f8f18cc4ffcKen Wakasa return *originalHistoricalInfo; 1162fa3693c264a4c150ac307d9bb7f6f8f18cc4ffcKen Wakasa } 117aae1a062eb98e7634fb4da996ec604bbefd4ddf5Keisuke Kuroyanagi // Lower the level. 1182fa3693c264a4c150ac307d9bb7f6f8f18cc4ffcKen Wakasa const int maxLevelDownAmonut = elapsedTimeStep / (MAX_ELAPSED_TIME_STEP_COUNT + 1); 1192fa3693c264a4c150ac307d9bb7f6f8f18cc4ffcKen Wakasa const int levelDownAmount = (maxLevelDownAmonut >= originalHistoricalInfo->getLevel()) ? 1202fa3693c264a4c150ac307d9bb7f6f8f18cc4ffcKen Wakasa originalHistoricalInfo->getLevel() : maxLevelDownAmonut; 121287e155e44b4e937f2a62d010805702bc813c43bKeisuke Kuroyanagi const int adjustedTimestampInSeconds = originalHistoricalInfo->getTimestamp() + 1225128935ac4d7961e3c863270b828e47a79b97235Keisuke Kuroyanagi levelDownAmount * durationToLevelDownInSeconds; 1235128935ac4d7961e3c863270b828e47a79b97235Keisuke Kuroyanagi return HistoricalInfo(adjustedTimestampInSeconds, 1242fa3693c264a4c150ac307d9bb7f6f8f18cc4ffcKen Wakasa originalHistoricalInfo->getLevel() - levelDownAmount, 0 /* count */); 12567c855ea6f882190d73df9d3fae0b56929fd6888Keisuke Kuroyanagi} 12667c855ea6f882190d73df9d3fae0b56929fd6888Keisuke Kuroyanagi 12767c855ea6f882190d73df9d3fae0b56929fd6888Keisuke Kuroyanagi/* static */ bool ForgettingCurveUtils::needsToDecay(const bool mindsBlockByDecay, 128e8750d970eed61b9239d8b2fa19648b8457696c1Keisuke Kuroyanagi const EntryCounts &entryCounts, const HeaderPolicy *const headerPolicy) { 12978212a6d3de2c1fdaa394c58a16cbdee3ad5d046Keisuke Kuroyanagi const EntryCounts &maxNgramCounts = headerPolicy->getMaxNgramCounts(); 13078212a6d3de2c1fdaa394c58a16cbdee3ad5d046Keisuke Kuroyanagi for (const auto ngramType : AllNgramTypes::ASCENDING) { 13178212a6d3de2c1fdaa394c58a16cbdee3ad5d046Keisuke Kuroyanagi if (entryCounts.getNgramCount(ngramType) 13278212a6d3de2c1fdaa394c58a16cbdee3ad5d046Keisuke Kuroyanagi >= getEntryCountHardLimit(maxNgramCounts.getNgramCount(ngramType))) { 13378212a6d3de2c1fdaa394c58a16cbdee3ad5d046Keisuke Kuroyanagi // Unigram count exceeds the limit. 13478212a6d3de2c1fdaa394c58a16cbdee3ad5d046Keisuke Kuroyanagi return true; 13578212a6d3de2c1fdaa394c58a16cbdee3ad5d046Keisuke Kuroyanagi } 136e8750d970eed61b9239d8b2fa19648b8457696c1Keisuke Kuroyanagi } 13767c855ea6f882190d73df9d3fae0b56929fd6888Keisuke Kuroyanagi if (mindsBlockByDecay) { 13867c855ea6f882190d73df9d3fae0b56929fd6888Keisuke Kuroyanagi return false; 13967c855ea6f882190d73df9d3fae0b56929fd6888Keisuke Kuroyanagi } 1402fa3693c264a4c150ac307d9bb7f6f8f18cc4ffcKen Wakasa if (headerPolicy->getLastDecayedTime() + DECAY_INTERVAL_SECONDS 1412fa3693c264a4c150ac307d9bb7f6f8f18cc4ffcKen Wakasa < TimeKeeper::peekCurrentTime()) { 14267c855ea6f882190d73df9d3fae0b56929fd6888Keisuke Kuroyanagi // Time to decay. 14367c855ea6f882190d73df9d3fae0b56929fd6888Keisuke Kuroyanagi return true; 144c76bbceedc804d1f2988cbf032b530a107a7d561Keisuke Kuroyanagi } 14567c855ea6f882190d73df9d3fae0b56929fd6888Keisuke Kuroyanagi return false; 146fd02b2d6ee55d4aee7faab89a7a2b72764eafc47Keisuke Kuroyanagi} 147fd02b2d6ee55d4aee7faab89a7a2b72764eafc47Keisuke Kuroyanagi 148c76bbceedc804d1f2988cbf032b530a107a7d561Keisuke Kuroyanagi// See comments in ProbabilityUtils::backoff(). 149c76bbceedc804d1f2988cbf032b530a107a7d561Keisuke Kuroyanagi/* static */ int ForgettingCurveUtils::backoff(const int unigramProbability) { 150b368089dbfabb84d1af4ad76d331b7add849c33bKeisuke Kuroyanagi // See TODO comments in ForgettingCurveUtils::getProbability(). 151b368089dbfabb84d1af4ad76d331b7add849c33bKeisuke Kuroyanagi return unigramProbability; 152fd02b2d6ee55d4aee7faab89a7a2b72764eafc47Keisuke Kuroyanagi} 153fd02b2d6ee55d4aee7faab89a7a2b72764eafc47Keisuke Kuroyanagi 1545128935ac4d7961e3c863270b828e47a79b97235Keisuke Kuroyanagi/* static */ int ForgettingCurveUtils::getElapsedTimeStepCount(const int timestamp, 1555128935ac4d7961e3c863270b828e47a79b97235Keisuke Kuroyanagi const int durationToLevelDownInSeconds) { 1565128935ac4d7961e3c863270b828e47a79b97235Keisuke Kuroyanagi const int elapsedTimeInSeconds = TimeKeeper::peekCurrentTime() - timestamp; 1575128935ac4d7961e3c863270b828e47a79b97235Keisuke Kuroyanagi const int timeStepDurationInSeconds = 1585128935ac4d7961e3c863270b828e47a79b97235Keisuke Kuroyanagi durationToLevelDownInSeconds / (MAX_ELAPSED_TIME_STEP_COUNT + 1); 1595128935ac4d7961e3c863270b828e47a79b97235Keisuke Kuroyanagi return elapsedTimeInSeconds / timeStepDurationInSeconds; 1602fa3693c264a4c150ac307d9bb7f6f8f18cc4ffcKen Wakasa} 1612fa3693c264a4c150ac307d9bb7f6f8f18cc4ffcKen Wakasa 1629d7e8c717f56a8b706a174fd3d5a2864d08d320cKeisuke Kuroyanagi/* static */ int ForgettingCurveUtils::clampToVisibleEntryLevelRange(const int level) { 1639d7e8c717f56a8b706a174fd3d5a2864d08d320cKeisuke Kuroyanagi return std::min(std::max(level, MIN_VISIBLE_LEVEL), MAX_LEVEL); 1649d7e8c717f56a8b706a174fd3d5a2864d08d320cKeisuke Kuroyanagi} 1659d7e8c717f56a8b706a174fd3d5a2864d08d320cKeisuke Kuroyanagi 1669d7e8c717f56a8b706a174fd3d5a2864d08d320cKeisuke Kuroyanagi/* static */ int ForgettingCurveUtils::clampToValidCountRange(const int count, 1679d7e8c717f56a8b706a174fd3d5a2864d08d320cKeisuke Kuroyanagi const HeaderPolicy *const headerPolicy) { 168aae1a062eb98e7634fb4da996ec604bbefd4ddf5Keisuke Kuroyanagi return std::min(std::max(count, 0), OCCURRENCES_TO_RAISE_THE_LEVEL - 1); 1699d7e8c717f56a8b706a174fd3d5a2864d08d320cKeisuke Kuroyanagi} 1709d7e8c717f56a8b706a174fd3d5a2864d08d320cKeisuke Kuroyanagi 1719d7e8c717f56a8b706a174fd3d5a2864d08d320cKeisuke Kuroyanagi/* static */ int ForgettingCurveUtils::clampToValidLevelRange(const int level) { 1729d7e8c717f56a8b706a174fd3d5a2864d08d320cKeisuke Kuroyanagi return std::min(std::max(level, 0), MAX_LEVEL); 1739d7e8c717f56a8b706a174fd3d5a2864d08d320cKeisuke Kuroyanagi} 1749d7e8c717f56a8b706a174fd3d5a2864d08d320cKeisuke Kuroyanagi 1759d7e8c717f56a8b706a174fd3d5a2864d08d320cKeisuke Kuroyanagi/* static */ int ForgettingCurveUtils::clampToValidTimeStepCountRange(const int timeStepCount) { 1769d7e8c717f56a8b706a174fd3d5a2864d08d320cKeisuke Kuroyanagi return std::min(std::max(timeStepCount, 0), MAX_ELAPSED_TIME_STEP_COUNT); 1779d7e8c717f56a8b706a174fd3d5a2864d08d320cKeisuke Kuroyanagi} 1789d7e8c717f56a8b706a174fd3d5a2864d08d320cKeisuke Kuroyanagi 17970566266be1781100c673addca5af1960a0eedf8Keisuke Kuroyanagiconst int ForgettingCurveUtils::ProbabilityTable::PROBABILITY_TABLE_COUNT = 4; 18070566266be1781100c673addca5af1960a0eedf8Keisuke Kuroyanagiconst int ForgettingCurveUtils::ProbabilityTable::WEAK_PROBABILITY_TABLE_ID = 0; 18170566266be1781100c673addca5af1960a0eedf8Keisuke Kuroyanagiconst int ForgettingCurveUtils::ProbabilityTable::MODEST_PROBABILITY_TABLE_ID = 1; 18270566266be1781100c673addca5af1960a0eedf8Keisuke Kuroyanagiconst int ForgettingCurveUtils::ProbabilityTable::STRONG_PROBABILITY_TABLE_ID = 2; 18370566266be1781100c673addca5af1960a0eedf8Keisuke Kuroyanagiconst int ForgettingCurveUtils::ProbabilityTable::AGGRESSIVE_PROBABILITY_TABLE_ID = 3; 1843d70932857ce97631635c132ce2dbc38ecb0e731Keisuke Kuroyanagiconst int ForgettingCurveUtils::ProbabilityTable::WEAK_MAX_PROBABILITY = 127; 185aae1a062eb98e7634fb4da996ec604bbefd4ddf5Keisuke Kuroyanagiconst int ForgettingCurveUtils::ProbabilityTable::MODEST_BASE_PROBABILITY = 8; 186aae1a062eb98e7634fb4da996ec604bbefd4ddf5Keisuke Kuroyanagiconst int ForgettingCurveUtils::ProbabilityTable::STRONG_BASE_PROBABILITY = 9; 187aae1a062eb98e7634fb4da996ec604bbefd4ddf5Keisuke Kuroyanagiconst int ForgettingCurveUtils::ProbabilityTable::AGGRESSIVE_BASE_PROBABILITY = 10; 18870566266be1781100c673addca5af1960a0eedf8Keisuke Kuroyanagi 18957816c7a8bac1a47913da7a503ece2b5dd7cc0fcKeisuke Kuroyanagi 19057816c7a8bac1a47913da7a503ece2b5dd7cc0fcKeisuke KuroyanagiForgettingCurveUtils::ProbabilityTable::ProbabilityTable() : mTables() { 19157816c7a8bac1a47913da7a503ece2b5dd7cc0fcKeisuke Kuroyanagi mTables.resize(PROBABILITY_TABLE_COUNT); 19257816c7a8bac1a47913da7a503ece2b5dd7cc0fcKeisuke Kuroyanagi for (int tableId = 0; tableId < PROBABILITY_TABLE_COUNT; ++tableId) { 19357816c7a8bac1a47913da7a503ece2b5dd7cc0fcKeisuke Kuroyanagi mTables[tableId].resize(MAX_LEVEL + 1); 19457816c7a8bac1a47913da7a503ece2b5dd7cc0fcKeisuke Kuroyanagi for (int level = 0; level <= MAX_LEVEL; ++level) { 19557816c7a8bac1a47913da7a503ece2b5dd7cc0fcKeisuke Kuroyanagi mTables[tableId][level].resize(MAX_ELAPSED_TIME_STEP_COUNT + 1); 19670566266be1781100c673addca5af1960a0eedf8Keisuke Kuroyanagi const float initialProbability = getBaseProbabilityForLevel(tableId, level); 19770566266be1781100c673addca5af1960a0eedf8Keisuke Kuroyanagi const float endProbability = getBaseProbabilityForLevel(tableId, level - 1); 19857816c7a8bac1a47913da7a503ece2b5dd7cc0fcKeisuke Kuroyanagi for (int timeStepCount = 0; timeStepCount <= MAX_ELAPSED_TIME_STEP_COUNT; 19957816c7a8bac1a47913da7a503ece2b5dd7cc0fcKeisuke Kuroyanagi ++timeStepCount) { 200aae1a062eb98e7634fb4da996ec604bbefd4ddf5Keisuke Kuroyanagi if (level < MIN_VISIBLE_LEVEL) { 20157816c7a8bac1a47913da7a503ece2b5dd7cc0fcKeisuke Kuroyanagi mTables[tableId][level][timeStepCount] = NOT_A_PROBABILITY; 20257816c7a8bac1a47913da7a503ece2b5dd7cc0fcKeisuke Kuroyanagi continue; 20357816c7a8bac1a47913da7a503ece2b5dd7cc0fcKeisuke Kuroyanagi } 20457816c7a8bac1a47913da7a503ece2b5dd7cc0fcKeisuke Kuroyanagi const float probability = initialProbability 20570566266be1781100c673addca5af1960a0eedf8Keisuke Kuroyanagi * powf(initialProbability / endProbability, 2065128935ac4d7961e3c863270b828e47a79b97235Keisuke Kuroyanagi -1.0f * static_cast<float>(timeStepCount) 2075128935ac4d7961e3c863270b828e47a79b97235Keisuke Kuroyanagi / static_cast<float>(MAX_ELAPSED_TIME_STEP_COUNT + 1)); 20857816c7a8bac1a47913da7a503ece2b5dd7cc0fcKeisuke Kuroyanagi mTables[tableId][level][timeStepCount] = 209865e6cf49764f3a411ee32861d927b15653ee398Keisuke Kuroyanagi std::min(std::max(static_cast<int>(probability), 1), MAX_PROBABILITY); 2102fa3693c264a4c150ac307d9bb7f6f8f18cc4ffcKen Wakasa } 2112fa3693c264a4c150ac307d9bb7f6f8f18cc4ffcKen Wakasa } 2127c4dcf1e918c2b9251e7aa907d991a3ab8764bafKeisuke Kuroyanagi } 2137c4dcf1e918c2b9251e7aa907d991a3ab8764bafKeisuke Kuroyanagi} 2147c4dcf1e918c2b9251e7aa907d991a3ab8764bafKeisuke Kuroyanagi 21570566266be1781100c673addca5af1960a0eedf8Keisuke Kuroyanagi/* static */ int ForgettingCurveUtils::ProbabilityTable::getBaseProbabilityForLevel( 21670566266be1781100c673addca5af1960a0eedf8Keisuke Kuroyanagi const int tableId, const int level) { 21770566266be1781100c673addca5af1960a0eedf8Keisuke Kuroyanagi if (tableId == WEAK_PROBABILITY_TABLE_ID) { 21870566266be1781100c673addca5af1960a0eedf8Keisuke Kuroyanagi // Max probability is 127. 2193d70932857ce97631635c132ce2dbc38ecb0e731Keisuke Kuroyanagi return static_cast<float>(WEAK_MAX_PROBABILITY / (1 << (MAX_LEVEL - level))); 22070566266be1781100c673addca5af1960a0eedf8Keisuke Kuroyanagi } else if (tableId == MODEST_PROBABILITY_TABLE_ID) { 22170566266be1781100c673addca5af1960a0eedf8Keisuke Kuroyanagi // Max probability is 128. 22270566266be1781100c673addca5af1960a0eedf8Keisuke Kuroyanagi return static_cast<float>(MODEST_BASE_PROBABILITY * (level + 1)); 22370566266be1781100c673addca5af1960a0eedf8Keisuke Kuroyanagi } else if (tableId == STRONG_PROBABILITY_TABLE_ID) { 22470566266be1781100c673addca5af1960a0eedf8Keisuke Kuroyanagi // Max probability is 140. 22570566266be1781100c673addca5af1960a0eedf8Keisuke Kuroyanagi return static_cast<float>(STRONG_BASE_PROBABILITY * (level + 1)); 22670566266be1781100c673addca5af1960a0eedf8Keisuke Kuroyanagi } else if (tableId == AGGRESSIVE_PROBABILITY_TABLE_ID) { 22770566266be1781100c673addca5af1960a0eedf8Keisuke Kuroyanagi // Max probability is 160. 22870566266be1781100c673addca5af1960a0eedf8Keisuke Kuroyanagi return static_cast<float>(AGGRESSIVE_BASE_PROBABILITY * (level + 1)); 22970566266be1781100c673addca5af1960a0eedf8Keisuke Kuroyanagi } else { 23070566266be1781100c673addca5af1960a0eedf8Keisuke Kuroyanagi return NOT_A_PROBABILITY; 23170566266be1781100c673addca5af1960a0eedf8Keisuke Kuroyanagi } 23270566266be1781100c673addca5af1960a0eedf8Keisuke Kuroyanagi} 23370566266be1781100c673addca5af1960a0eedf8Keisuke Kuroyanagi 234fd02b2d6ee55d4aee7faab89a7a2b72764eafc47Keisuke Kuroyanagi} // namespace latinime 235