proximity_info_state.cpp revision e2912d17e4dab75b81f4c9e41a539e491ac059ca
1/* 2 * Copyright (C) 2012 The Android Open Source Project 3 * 4 * Licensed under the Apache License, Version 2.0 (the "License"); 5 * you may not use this file except in compliance with the License. 6 * You may obtain a copy of the License at 7 * 8 * http://www.apache.org/licenses/LICENSE-2.0 9 * 10 * Unless required by applicable law or agreed to in writing, software 11 * distributed under the License is distributed on an "AS IS" BASIS, 12 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 13 * See the License for the specific language governing permissions and 14 * limitations under the License. 15 */ 16 17#include <cstring> // for memset() 18#include <sstream> // for debug prints 19 20#define LOG_TAG "LatinIME: proximity_info_state.cpp" 21 22#include "defines.h" 23#include "geometry_utils.h" 24#include "proximity_info.h" 25#include "proximity_info_state.h" 26#include "proximity_info_state_utils.h" 27 28namespace latinime { 29 30const int ProximityInfoState::NOT_A_CODE = -1; 31 32void ProximityInfoState::initInputParams(const int pointerId, const float maxPointToKeyLength, 33 const ProximityInfo *proximityInfo, const int *const inputCodes, const int inputSize, 34 const int *const xCoordinates, const int *const yCoordinates, const int *const times, 35 const int *const pointerIds, const bool isGeometric) { 36 mIsContinuationPossible = checkAndReturnIsContinuationPossible( 37 inputSize, xCoordinates, yCoordinates, times, isGeometric); 38 39 mProximityInfo = proximityInfo; 40 mHasTouchPositionCorrectionData = proximityInfo->hasTouchPositionCorrectionData(); 41 mMostCommonKeyWidthSquare = proximityInfo->getMostCommonKeyWidthSquare(); 42 mKeyCount = proximityInfo->getKeyCount(); 43 mCellHeight = proximityInfo->getCellHeight(); 44 mCellWidth = proximityInfo->getCellWidth(); 45 mGridHeight = proximityInfo->getGridWidth(); 46 mGridWidth = proximityInfo->getGridHeight(); 47 48 memset(mInputProximities, 0, sizeof(mInputProximities)); 49 50 if (!isGeometric && pointerId == 0) { 51 mProximityInfo->initializeProximities(inputCodes, xCoordinates, yCoordinates, 52 inputSize, mInputProximities); 53 } 54 55 /////////////////////// 56 // Setup touch points 57 int pushTouchPointStartIndex = 0; 58 int lastSavedInputSize = 0; 59 mMaxPointToKeyLength = maxPointToKeyLength; 60 if (mIsContinuationPossible && mSampledInputIndice.size() > 1) { 61 // Just update difference. 62 // Two points prior is never skipped. Thus, we pop 2 input point data here. 63 pushTouchPointStartIndex = mSampledInputIndice[mSampledInputIndice.size() - 2]; 64 popInputData(); 65 popInputData(); 66 lastSavedInputSize = mSampledInputXs.size(); 67 } else { 68 // Clear all data. 69 mSampledInputXs.clear(); 70 mSampledInputYs.clear(); 71 mSampledTimes.clear(); 72 mSampledInputIndice.clear(); 73 mSampledLengthCache.clear(); 74 mDistanceCache_G.clear(); 75 mNearKeysVector.clear(); 76 mSearchKeysVector.clear(); 77 mSpeedRates.clear(); 78 mBeelineSpeedPercentiles.clear(); 79 mCharProbabilities.clear(); 80 mDirections.clear(); 81 } 82 if (DEBUG_GEO_FULL) { 83 AKLOGI("Init ProximityInfoState: reused points = %d, last input size = %d", 84 pushTouchPointStartIndex, lastSavedInputSize); 85 } 86 mSampledInputSize = 0; 87 88 if (xCoordinates && yCoordinates) { 89 mSampledInputSize = ProximityInfoStateUtils::updateTouchPoints( 90 mProximityInfo->getMostCommonKeyWidth(), mProximityInfo, mMaxPointToKeyLength, 91 mInputProximities, xCoordinates, yCoordinates, times, pointerIds, inputSize, 92 isGeometric, pointerId, pushTouchPointStartIndex, &mSampledInputXs, 93 &mSampledInputYs, &mSampledTimes, &mSampledLengthCache, &mSampledInputIndice); 94 } 95 96 if (mSampledInputSize > 0 && isGeometric) { 97 mAverageSpeed = ProximityInfoStateUtils::refreshSpeedRates( 98 inputSize, xCoordinates, yCoordinates, times, lastSavedInputSize, 99 mSampledInputSize, &mSampledInputXs, &mSampledInputYs, &mSampledTimes, 100 &mSampledLengthCache, &mSampledInputIndice, &mSpeedRates, &mDirections); 101 ProximityInfoStateUtils::refreshBeelineSpeedRates( 102 mProximityInfo->getMostCommonKeyWidth(), mAverageSpeed, inputSize, 103 xCoordinates, yCoordinates, times, mSampledInputSize, &mSampledInputXs, 104 &mSampledInputYs, &mSampledInputIndice, &mBeelineSpeedPercentiles); 105 } 106 107 if (mSampledInputSize > 0) { 108 ProximityInfoStateUtils::initGeometricDistanceInfos( 109 mProximityInfo, mProximityInfo->getKeyCount(), 110 mSampledInputSize, lastSavedInputSize, &mSampledInputXs, &mSampledInputYs, 111 &mNearKeysVector, &mSearchKeysVector, &mDistanceCache_G); 112 if (isGeometric) { 113 // updates probabilities of skipping or mapping each key for all points. 114 ProximityInfoStateUtils::updateAlignPointProbabilities( 115 mMaxPointToKeyLength, mProximityInfo->getMostCommonKeyWidth(), 116 mProximityInfo->getKeyCount(), lastSavedInputSize, mSampledInputSize, 117 &mSampledInputXs, &mSampledInputYs, &mSpeedRates, &mSampledLengthCache, 118 &mDistanceCache_G, &mNearKeysVector, &mCharProbabilities); 119 ProximityInfoStateUtils::updateSearchKeysVector(mProximityInfo, mSampledInputSize, 120 lastSavedInputSize, &mSampledLengthCache, &mNearKeysVector, &mSearchKeysVector); 121 } 122 } 123 124 if (DEBUG_SAMPLING_POINTS) { 125 ProximityInfoStateUtils::dump(isGeometric, inputSize, xCoordinates, yCoordinates, 126 mSampledInputSize, &mSampledInputXs, &mSampledInputYs, &mSampledTimes, &mSpeedRates, 127 &mBeelineSpeedPercentiles); 128 } 129 // end 130 /////////////////////// 131 132 memset(mNormalizedSquaredDistances, NOT_A_DISTANCE, sizeof(mNormalizedSquaredDistances)); 133 memset(mPrimaryInputWord, 0, sizeof(mPrimaryInputWord)); 134 mTouchPositionCorrectionEnabled = mSampledInputSize > 0 && mHasTouchPositionCorrectionData 135 && xCoordinates && yCoordinates; 136 if (!isGeometric && pointerId == 0) { 137 ProximityInfoStateUtils::initPrimaryInputWord( 138 inputSize, mInputProximities, mPrimaryInputWord); 139 if (mTouchPositionCorrectionEnabled) { 140 ProximityInfoStateUtils::initNormalizedSquaredDistances( 141 mProximityInfo, inputSize, xCoordinates, yCoordinates, mInputProximities, 142 hasInputCoordinates(), &mSampledInputXs, &mSampledInputYs, 143 mNormalizedSquaredDistances); 144 } 145 } 146 if (DEBUG_GEO_FULL) { 147 AKLOGI("ProximityState init finished: %d points out of %d", mSampledInputSize, inputSize); 148 } 149} 150 151bool ProximityInfoState::checkAndReturnIsContinuationPossible(const int inputSize, 152 const int *const xCoordinates, const int *const yCoordinates, const int *const times, 153 const bool isGeometric) const { 154 if (isGeometric) { 155 for (int i = 0; i < mSampledInputSize; ++i) { 156 const int index = mSampledInputIndice[i]; 157 if (index > inputSize || xCoordinates[index] != mSampledInputXs[i] || 158 yCoordinates[index] != mSampledInputYs[i] || times[index] != mSampledTimes[i]) { 159 return false; 160 } 161 } 162 } else { 163 if (inputSize < mSampledInputSize) { 164 // Assuming the cache is invalid if the previous input size is larger than the new one. 165 return false; 166 } 167 for (int i = 0; i < mSampledInputSize && i < MAX_WORD_LENGTH; ++i) { 168 if (xCoordinates[i] != mSampledInputXs[i] 169 || yCoordinates[i] != mSampledInputYs[i]) { 170 return false; 171 } 172 } 173 } 174 return true; 175} 176 177int ProximityInfoState::getDuration(const int index) const { 178 if (index >= 0 && index < mSampledInputSize - 1) { 179 return mSampledTimes[index + 1] - mSampledTimes[index]; 180 } 181 return 0; 182} 183 184// TODO: Remove the "scale" parameter 185// This function basically converts from a length to an edit distance. Accordingly, it's obviously 186// wrong to compare with mMaxPointToKeyLength. 187float ProximityInfoState::getPointToKeyLength( 188 const int inputIndex, const int codePoint, const float scale) const { 189 const int keyId = mProximityInfo->getKeyIndexOf(codePoint); 190 if (keyId != NOT_AN_INDEX) { 191 const int index = inputIndex * mProximityInfo->getKeyCount() + keyId; 192 return min(mDistanceCache_G[index] * scale, mMaxPointToKeyLength); 193 } 194 if (isSkippableCodePoint(codePoint)) { 195 return 0.0f; 196 } 197 // If the char is not a key on the keyboard then return the max length. 198 return MAX_POINT_TO_KEY_LENGTH; 199} 200 201float ProximityInfoState::getPointToKeyLength_G(const int inputIndex, const int codePoint) const { 202 return getPointToKeyLength(inputIndex, codePoint, 1.0f); 203} 204 205// TODO: Remove the "scale" parameter 206float ProximityInfoState::getPointToKeyByIdLength( 207 const int inputIndex, const int keyId, const float scale) const { 208 return ProximityInfoStateUtils::getPointToKeyByIdLength(mMaxPointToKeyLength, 209 &mDistanceCache_G, mProximityInfo->getKeyCount(), inputIndex, keyId, scale); 210} 211 212float ProximityInfoState::getPointToKeyByIdLength(const int inputIndex, const int keyId) const { 213 return getPointToKeyByIdLength(inputIndex, keyId, 1.0f); 214} 215 216// In the following function, c is the current character of the dictionary word currently examined. 217// currentChars is an array containing the keys close to the character the user actually typed at 218// the same position. We want to see if c is in it: if so, then the word contains at that position 219// a character close to what the user typed. 220// What the user typed is actually the first character of the array. 221// proximityIndex is a pointer to the variable where getMatchedProximityId returns the index of c 222// in the proximity chars of the input index. 223// Notice : accented characters do not have a proximity list, so they are alone in their list. The 224// non-accented version of the character should be considered "close", but not the other keys close 225// to the non-accented version. 226ProximityType ProximityInfoState::getMatchedProximityId(const int index, const int c, 227 const bool checkProximityChars, int *proximityIndex) const { 228 const int *currentCodePoints = getProximityCodePointsAt(index); 229 const int firstCodePoint = currentCodePoints[0]; 230 const int baseLowerC = toBaseLowerCase(c); 231 232 // The first char in the array is what user typed. If it matches right away, that means the 233 // user typed that same char for this pos. 234 if (firstCodePoint == baseLowerC || firstCodePoint == c) { 235 return EQUIVALENT_CHAR; 236 } 237 238 if (!checkProximityChars) return UNRELATED_CHAR; 239 240 // If the non-accented, lowercased version of that first character matches c, then we have a 241 // non-accented version of the accented character the user typed. Treat it as a close char. 242 if (toBaseLowerCase(firstCodePoint) == baseLowerC) { 243 return NEAR_PROXIMITY_CHAR; 244 } 245 246 // Not an exact nor an accent-alike match: search the list of close keys 247 int j = 1; 248 while (j < MAX_PROXIMITY_CHARS_SIZE 249 && currentCodePoints[j] > ADDITIONAL_PROXIMITY_CHAR_DELIMITER_CODE) { 250 const bool matched = (currentCodePoints[j] == baseLowerC || currentCodePoints[j] == c); 251 if (matched) { 252 if (proximityIndex) { 253 *proximityIndex = j; 254 } 255 return NEAR_PROXIMITY_CHAR; 256 } 257 ++j; 258 } 259 if (j < MAX_PROXIMITY_CHARS_SIZE 260 && currentCodePoints[j] == ADDITIONAL_PROXIMITY_CHAR_DELIMITER_CODE) { 261 ++j; 262 while (j < MAX_PROXIMITY_CHARS_SIZE 263 && currentCodePoints[j] > ADDITIONAL_PROXIMITY_CHAR_DELIMITER_CODE) { 264 const bool matched = (currentCodePoints[j] == baseLowerC || currentCodePoints[j] == c); 265 if (matched) { 266 if (proximityIndex) { 267 *proximityIndex = j; 268 } 269 return ADDITIONAL_PROXIMITY_CHAR; 270 } 271 ++j; 272 } 273 } 274 // Was not included, signal this as an unrelated character. 275 return UNRELATED_CHAR; 276} 277 278int ProximityInfoState::getSpaceY() const { 279 const int keyId = mProximityInfo->getKeyIndexOf(KEYCODE_SPACE); 280 return mProximityInfo->getKeyCenterYOfKeyIdG(keyId); 281} 282 283// Puts possible characters into filter and returns new filter size. 284int ProximityInfoState::getAllPossibleChars( 285 const size_t index, int *const filter, const int filterSize) const { 286 if (index >= mSampledInputXs.size()) { 287 return filterSize; 288 } 289 int newFilterSize = filterSize; 290 const int keyCount = mProximityInfo->getKeyCount(); 291 for (int j = 0; j < keyCount; ++j) { 292 if (mSearchKeysVector[index].test(j)) { 293 const int keyCodePoint = mProximityInfo->getCodePointOf(j); 294 bool insert = true; 295 // TODO: Avoid linear search 296 for (int k = 0; k < filterSize; ++k) { 297 if (filter[k] == keyCodePoint) { 298 insert = false; 299 break; 300 } 301 } 302 if (insert) { 303 filter[newFilterSize++] = keyCodePoint; 304 } 305 } 306 } 307 return newFilterSize; 308} 309 310bool ProximityInfoState::isKeyInSerchKeysAfterIndex(const int index, const int keyId) const { 311 ASSERT(keyId >= 0); 312 ASSERT(index >= 0 && index < mSampledInputSize); 313 return mSearchKeysVector[index].test(keyId); 314} 315 316void ProximityInfoState::popInputData() { 317 ProximityInfoStateUtils::popInputData(&mSampledInputXs, &mSampledInputYs, &mSampledTimes, 318 &mSampledLengthCache, &mSampledInputIndice); 319} 320 321float ProximityInfoState::getDirection(const int index0, const int index1) const { 322 return ProximityInfoStateUtils::getDirection( 323 &mSampledInputXs, &mSampledInputYs, index0, index1); 324} 325 326float ProximityInfoState::getLineToKeyDistance( 327 const int from, const int to, const int keyId, const bool extend) const { 328 if (from < 0 || from > mSampledInputSize - 1) { 329 return 0.0f; 330 } 331 if (to < 0 || to > mSampledInputSize - 1) { 332 return 0.0f; 333 } 334 const int x0 = mSampledInputXs[from]; 335 const int y0 = mSampledInputYs[from]; 336 const int x1 = mSampledInputXs[to]; 337 const int y1 = mSampledInputYs[to]; 338 339 const int keyX = mProximityInfo->getKeyCenterXOfKeyIdG(keyId); 340 const int keyY = mProximityInfo->getKeyCenterYOfKeyIdG(keyId); 341 342 return ProximityInfoUtils::pointToLineSegSquaredDistanceFloat( 343 keyX, keyY, x0, y0, x1, y1, extend); 344} 345 346// Get a word that is detected by tracing the most probable string into codePointBuf and 347// returns probability of generating the word. 348float ProximityInfoState::getMostProbableString(int *const codePointBuf) const { 349 static const float DEMOTION_LOG_PROBABILITY = 0.3f; 350 int index = 0; 351 float sumLogProbability = 0.0f; 352 // TODO: Current implementation is greedy algorithm. DP would be efficient for many cases. 353 for (int i = 0; i < mSampledInputSize && index < MAX_WORD_LENGTH - 1; ++i) { 354 float minLogProbability = static_cast<float>(MAX_POINT_TO_KEY_LENGTH); 355 int character = NOT_AN_INDEX; 356 for (hash_map_compat<int, float>::const_iterator it = mCharProbabilities[i].begin(); 357 it != mCharProbabilities[i].end(); ++it) { 358 const float logProbability = (it->first != NOT_AN_INDEX) 359 ? it->second + DEMOTION_LOG_PROBABILITY : it->second; 360 if (logProbability < minLogProbability) { 361 minLogProbability = logProbability; 362 character = it->first; 363 } 364 } 365 if (character != NOT_AN_INDEX) { 366 codePointBuf[index] = mProximityInfo->getCodePointOf(character); 367 index++; 368 } 369 sumLogProbability += minLogProbability; 370 } 371 codePointBuf[index] = '\0'; 372 return sumLogProbability; 373} 374 375bool ProximityInfoState::hasSpaceProximity(const int index) const { 376 ASSERT(0 <= index && index < mSampledInputSize); 377 return mProximityInfo->hasSpaceProximity(getInputX(index), getInputY(index)); 378} 379 380// Returns a probability of mapping index to keyIndex. 381float ProximityInfoState::getProbability(const int index, const int keyIndex) const { 382 ASSERT(0 <= index && index < mSampledInputSize); 383 hash_map_compat<int, float>::const_iterator it = mCharProbabilities[index].find(keyIndex); 384 if (it != mCharProbabilities[index].end()) { 385 return it->second; 386 } 387 return static_cast<float>(MAX_POINT_TO_KEY_LENGTH); 388} 389} // namespace latinime 390