1527c128309da708d0fdaf7928da833320d1754e9Keisuke Kuroynagi/* 2527c128309da708d0fdaf7928da833320d1754e9Keisuke Kuroynagi * Copyright (C) 2013 The Android Open Source Project 3527c128309da708d0fdaf7928da833320d1754e9Keisuke Kuroynagi * 4527c128309da708d0fdaf7928da833320d1754e9Keisuke Kuroynagi * Licensed under the Apache License, Version 2.0 (the "License"); 5527c128309da708d0fdaf7928da833320d1754e9Keisuke Kuroynagi * you may not use this file except in compliance with the License. 6527c128309da708d0fdaf7928da833320d1754e9Keisuke Kuroynagi * You may obtain a copy of the License at 7527c128309da708d0fdaf7928da833320d1754e9Keisuke Kuroynagi * 8527c128309da708d0fdaf7928da833320d1754e9Keisuke Kuroynagi * http://www.apache.org/licenses/LICENSE-2.0 9527c128309da708d0fdaf7928da833320d1754e9Keisuke Kuroynagi * 10527c128309da708d0fdaf7928da833320d1754e9Keisuke Kuroynagi * Unless required by applicable law or agreed to in writing, software 11527c128309da708d0fdaf7928da833320d1754e9Keisuke Kuroynagi * distributed under the License is distributed on an "AS IS" BASIS, 12527c128309da708d0fdaf7928da833320d1754e9Keisuke Kuroynagi * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 13527c128309da708d0fdaf7928da833320d1754e9Keisuke Kuroynagi * See the License for the specific language governing permissions and 14527c128309da708d0fdaf7928da833320d1754e9Keisuke Kuroynagi * limitations under the License. 15527c128309da708d0fdaf7928da833320d1754e9Keisuke Kuroynagi */ 16527c128309da708d0fdaf7928da833320d1754e9Keisuke Kuroynagi 17527c128309da708d0fdaf7928da833320d1754e9Keisuke Kuroynagi#include "utils/autocorrection_threshold_utils.h" 18527c128309da708d0fdaf7928da833320d1754e9Keisuke Kuroynagi 19527c128309da708d0fdaf7928da833320d1754e9Keisuke Kuroynagi#include <cmath> 20527c128309da708d0fdaf7928da833320d1754e9Keisuke Kuroynagi 21527c128309da708d0fdaf7928da833320d1754e9Keisuke Kuroynagi#include "defines.h" 22527c128309da708d0fdaf7928da833320d1754e9Keisuke Kuroynagi#include "suggest/policyimpl/utils/edit_distance.h" 23527c128309da708d0fdaf7928da833320d1754e9Keisuke Kuroynagi#include "suggest/policyimpl/utils/damerau_levenshtein_edit_distance_policy.h" 24527c128309da708d0fdaf7928da833320d1754e9Keisuke Kuroynagi 25527c128309da708d0fdaf7928da833320d1754e9Keisuke Kuroynaginamespace latinime { 26527c128309da708d0fdaf7928da833320d1754e9Keisuke Kuroynagi 27527c128309da708d0fdaf7928da833320d1754e9Keisuke Kuroynagiconst int AutocorrectionThresholdUtils::MAX_INITIAL_SCORE = 255; 28527c128309da708d0fdaf7928da833320d1754e9Keisuke Kuroynagiconst int AutocorrectionThresholdUtils::TYPED_LETTER_MULTIPLIER = 2; 29527c128309da708d0fdaf7928da833320d1754e9Keisuke Kuroynagiconst int AutocorrectionThresholdUtils::FULL_WORD_MULTIPLIER = 2; 30527c128309da708d0fdaf7928da833320d1754e9Keisuke Kuroynagi 31527c128309da708d0fdaf7928da833320d1754e9Keisuke Kuroynagi/* static */ int AutocorrectionThresholdUtils::editDistance(const int *before, 32527c128309da708d0fdaf7928da833320d1754e9Keisuke Kuroynagi const int beforeLength, const int *after, const int afterLength) { 33527c128309da708d0fdaf7928da833320d1754e9Keisuke Kuroynagi const DamerauLevenshteinEditDistancePolicy daemaruLevenshtein( 34527c128309da708d0fdaf7928da833320d1754e9Keisuke Kuroynagi before, beforeLength, after, afterLength); 35527c128309da708d0fdaf7928da833320d1754e9Keisuke Kuroynagi return static_cast<int>(EditDistance::getEditDistance(&daemaruLevenshtein)); 36527c128309da708d0fdaf7928da833320d1754e9Keisuke Kuroynagi} 37527c128309da708d0fdaf7928da833320d1754e9Keisuke Kuroynagi 38527c128309da708d0fdaf7928da833320d1754e9Keisuke Kuroynagi// In dictionary.cpp, getSuggestion() method, 39527c128309da708d0fdaf7928da833320d1754e9Keisuke Kuroynagi// When USE_SUGGEST_INTERFACE_FOR_TYPING is true: 40527c128309da708d0fdaf7928da833320d1754e9Keisuke Kuroynagi// 41527c128309da708d0fdaf7928da833320d1754e9Keisuke Kuroynagi// // TODO: Revise the following logic thoroughly by referring to the logic 42527c128309da708d0fdaf7928da833320d1754e9Keisuke Kuroynagi// // marked as "Otherwise" below. 43527c128309da708d0fdaf7928da833320d1754e9Keisuke Kuroynagi// SUGGEST_INTERFACE_OUTPUT_SCALE was multiplied to the original suggestion scores to convert 44527c128309da708d0fdaf7928da833320d1754e9Keisuke Kuroynagi// them to integers. 45527c128309da708d0fdaf7928da833320d1754e9Keisuke Kuroynagi// score = (int)((original score) * SUGGEST_INTERFACE_OUTPUT_SCALE) 46527c128309da708d0fdaf7928da833320d1754e9Keisuke Kuroynagi// Undo the scaling here to recover the original score. 47527c128309da708d0fdaf7928da833320d1754e9Keisuke Kuroynagi// normalizedScore = ((float)score) / SUGGEST_INTERFACE_OUTPUT_SCALE 48527c128309da708d0fdaf7928da833320d1754e9Keisuke Kuroynagi// 49527c128309da708d0fdaf7928da833320d1754e9Keisuke Kuroynagi// Otherwise: suggestion scores are computed using the below formula. 50527c128309da708d0fdaf7928da833320d1754e9Keisuke Kuroynagi// original score 51527c128309da708d0fdaf7928da833320d1754e9Keisuke Kuroynagi// := powf(mTypedLetterMultiplier (this is defined 2), 52527c128309da708d0fdaf7928da833320d1754e9Keisuke Kuroynagi// (the number of matched characters between typed word and suggested word)) 53527c128309da708d0fdaf7928da833320d1754e9Keisuke Kuroynagi// * (individual word's score which defined in the unigram dictionary, 54527c128309da708d0fdaf7928da833320d1754e9Keisuke Kuroynagi// and this score is defined in range [0, 255].) 55527c128309da708d0fdaf7928da833320d1754e9Keisuke Kuroynagi// Then, the following processing is applied. 56527c128309da708d0fdaf7928da833320d1754e9Keisuke Kuroynagi// - If the dictionary word is matched up to the point of the user entry 57527c128309da708d0fdaf7928da833320d1754e9Keisuke Kuroynagi// (full match up to min(before.length(), after.length()) 58527c128309da708d0fdaf7928da833320d1754e9Keisuke Kuroynagi// => Then multiply by FULL_MATCHED_WORDS_PROMOTION_RATE (this is defined 1.2) 59527c128309da708d0fdaf7928da833320d1754e9Keisuke Kuroynagi// - If the word is a true full match except for differences in accents or 60527c128309da708d0fdaf7928da833320d1754e9Keisuke Kuroynagi// capitalization, then treat it as if the score was 255. 61527c128309da708d0fdaf7928da833320d1754e9Keisuke Kuroynagi// - If before.length() == after.length() 62527c128309da708d0fdaf7928da833320d1754e9Keisuke Kuroynagi// => multiply by mFullWordMultiplier (this is defined 2)) 63527c128309da708d0fdaf7928da833320d1754e9Keisuke Kuroynagi// So, maximum original score is powf(2, min(before.length(), after.length())) * 255 * 2 * 1.2 64527c128309da708d0fdaf7928da833320d1754e9Keisuke Kuroynagi// For historical reasons we ignore the 1.2 modifier (because the measure for a good 65527c128309da708d0fdaf7928da833320d1754e9Keisuke Kuroynagi// autocorrection threshold was done at a time when it didn't exist). This doesn't change 66527c128309da708d0fdaf7928da833320d1754e9Keisuke Kuroynagi// the result. 67527c128309da708d0fdaf7928da833320d1754e9Keisuke Kuroynagi// So, we can normalize original score by dividing powf(2, min(b.l(),a.l())) * 255 * 2. 68527c128309da708d0fdaf7928da833320d1754e9Keisuke Kuroynagi 69527c128309da708d0fdaf7928da833320d1754e9Keisuke Kuroynagi/* static */ float AutocorrectionThresholdUtils::calcNormalizedScore(const int *before, 70527c128309da708d0fdaf7928da833320d1754e9Keisuke Kuroynagi const int beforeLength, const int *after, const int afterLength, const int score) { 71527c128309da708d0fdaf7928da833320d1754e9Keisuke Kuroynagi if (0 == beforeLength || 0 == afterLength) { 72527c128309da708d0fdaf7928da833320d1754e9Keisuke Kuroynagi return 0.0f; 73527c128309da708d0fdaf7928da833320d1754e9Keisuke Kuroynagi } 74527c128309da708d0fdaf7928da833320d1754e9Keisuke Kuroynagi const int distance = editDistance(before, beforeLength, after, afterLength); 75527c128309da708d0fdaf7928da833320d1754e9Keisuke Kuroynagi int spaceCount = 0; 76527c128309da708d0fdaf7928da833320d1754e9Keisuke Kuroynagi for (int i = 0; i < afterLength; ++i) { 77527c128309da708d0fdaf7928da833320d1754e9Keisuke Kuroynagi if (after[i] == KEYCODE_SPACE) { 78527c128309da708d0fdaf7928da833320d1754e9Keisuke Kuroynagi ++spaceCount; 79527c128309da708d0fdaf7928da833320d1754e9Keisuke Kuroynagi } 80527c128309da708d0fdaf7928da833320d1754e9Keisuke Kuroynagi } 81527c128309da708d0fdaf7928da833320d1754e9Keisuke Kuroynagi 82527c128309da708d0fdaf7928da833320d1754e9Keisuke Kuroynagi if (spaceCount == afterLength) { 83527c128309da708d0fdaf7928da833320d1754e9Keisuke Kuroynagi return 0.0f; 84527c128309da708d0fdaf7928da833320d1754e9Keisuke Kuroynagi } 85527c128309da708d0fdaf7928da833320d1754e9Keisuke Kuroynagi 8602833d11c3191282b7a05bca4e9f19a7b036980eSatoshi Kataoka if (score <= 0 || distance >= afterLength) { 8702833d11c3191282b7a05bca4e9f19a7b036980eSatoshi Kataoka // normalizedScore must be 0.0f (the minimum value) if the score is less than or equal to 0, 8802833d11c3191282b7a05bca4e9f19a7b036980eSatoshi Kataoka // or if the edit distance is larger than or equal to afterLength. 8902833d11c3191282b7a05bca4e9f19a7b036980eSatoshi Kataoka return 0.0f; 9002833d11c3191282b7a05bca4e9f19a7b036980eSatoshi Kataoka } 91527c128309da708d0fdaf7928da833320d1754e9Keisuke Kuroynagi // add a weight based on edit distance. 92527c128309da708d0fdaf7928da833320d1754e9Keisuke Kuroynagi const float weight = 1.0f - static_cast<float>(distance) / static_cast<float>(afterLength); 93527c128309da708d0fdaf7928da833320d1754e9Keisuke Kuroynagi 94527c128309da708d0fdaf7928da833320d1754e9Keisuke Kuroynagi // TODO: Revise the following logic thoroughly by referring to... 95527c128309da708d0fdaf7928da833320d1754e9Keisuke Kuroynagi if (true /* USE_SUGGEST_INTERFACE_FOR_TYPING */) { 96527c128309da708d0fdaf7928da833320d1754e9Keisuke Kuroynagi return (static_cast<float>(score) / SUGGEST_INTERFACE_OUTPUT_SCALE) * weight; 97527c128309da708d0fdaf7928da833320d1754e9Keisuke Kuroynagi } 98527c128309da708d0fdaf7928da833320d1754e9Keisuke Kuroynagi // ...this logic. 99527c128309da708d0fdaf7928da833320d1754e9Keisuke Kuroynagi const float maxScore = score >= S_INT_MAX ? static_cast<float>(S_INT_MAX) 100527c128309da708d0fdaf7928da833320d1754e9Keisuke Kuroynagi : static_cast<float>(MAX_INITIAL_SCORE) 101527c128309da708d0fdaf7928da833320d1754e9Keisuke Kuroynagi * powf(static_cast<float>(TYPED_LETTER_MULTIPLIER), 102527c128309da708d0fdaf7928da833320d1754e9Keisuke Kuroynagi static_cast<float>(min(beforeLength, afterLength - spaceCount))) 103527c128309da708d0fdaf7928da833320d1754e9Keisuke Kuroynagi * static_cast<float>(FULL_WORD_MULTIPLIER); 104527c128309da708d0fdaf7928da833320d1754e9Keisuke Kuroynagi 105527c128309da708d0fdaf7928da833320d1754e9Keisuke Kuroynagi return (static_cast<float>(score) / maxScore) * weight; 106527c128309da708d0fdaf7928da833320d1754e9Keisuke Kuroynagi} 107527c128309da708d0fdaf7928da833320d1754e9Keisuke Kuroynagi 108527c128309da708d0fdaf7928da833320d1754e9Keisuke Kuroynagi} // namespace latinime 109