1 /* 2 * Copyright (C) 2013 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 <cmath> 18 #include <cstring> // for memset() 19 #include <sstream> // for debug prints 20 #include <vector> 21 22 #include "defines.h" 23 #include "geometry_utils.h" 24 #include "proximity_info.h" 25 #include "proximity_info_params.h" 26 #include "proximity_info_state_utils.h" 27 28 namespace latinime { 29 30 /* static */ int ProximityInfoStateUtils::trimLastTwoTouchPoints(std::vector<int> *sampledInputXs, 31 std::vector<int> *sampledInputYs, std::vector<int> *sampledInputTimes, 32 std::vector<int> *sampledLengthCache, std::vector<int> *sampledInputIndice) { 33 const int nextStartIndex = (*sampledInputIndice)[sampledInputIndice->size() - 2]; 34 popInputData(sampledInputXs, sampledInputYs, sampledInputTimes, sampledLengthCache, 35 sampledInputIndice); 36 popInputData(sampledInputXs, sampledInputYs, sampledInputTimes, sampledLengthCache, 37 sampledInputIndice); 38 return nextStartIndex; 39 } 40 41 /* static */ int ProximityInfoStateUtils::updateTouchPoints( 42 const ProximityInfo *const proximityInfo, const int maxPointToKeyLength, 43 const int *const inputProximities, const int *const inputXCoordinates, 44 const int *const inputYCoordinates, const int *const times, const int *const pointerIds, 45 const float verticalSweetSpotScale, const int inputSize, const bool isGeometric, 46 const int pointerId, const int pushTouchPointStartIndex, std::vector<int> *sampledInputXs, 47 std::vector<int> *sampledInputYs, std::vector<int> *sampledInputTimes, 48 std::vector<int> *sampledLengthCache, std::vector<int> *sampledInputIndice) { 49 if (DEBUG_SAMPLING_POINTS) { 50 if (times) { 51 for (int i = 0; i < inputSize; ++i) { 52 AKLOGI("(%d) x %d, y %d, time %d", 53 i, inputXCoordinates[i], inputYCoordinates[i], times[i]); 54 } 55 } 56 } 57 #ifdef DO_ASSERT_TEST 58 if (times) { 59 for (int i = 0; i < inputSize; ++i) { 60 if (i > 0) { 61 if (times[i] < times[i - 1]) { 62 AKLOGI("Invalid time sequence. %d, %d", times[i - 1], times[i]); 63 ASSERT(false); 64 } 65 } 66 } 67 } 68 #endif 69 const bool proximityOnly = !isGeometric 70 && (inputXCoordinates[0] < 0 || inputYCoordinates[0] < 0); 71 int lastInputIndex = pushTouchPointStartIndex; 72 for (int i = lastInputIndex; i < inputSize; ++i) { 73 const int pid = pointerIds ? pointerIds[i] : 0; 74 if (pointerId == pid) { 75 lastInputIndex = i; 76 } 77 } 78 if (DEBUG_GEO_FULL) { 79 AKLOGI("Init ProximityInfoState: last input index = %d", lastInputIndex); 80 } 81 // Working space to save near keys distances for current, prev and prevprev input point. 82 NearKeysDistanceMap nearKeysDistances[3]; 83 // These pointers are swapped for each inputs points. 84 NearKeysDistanceMap *currentNearKeysDistances = &nearKeysDistances[0]; 85 NearKeysDistanceMap *prevNearKeysDistances = &nearKeysDistances[1]; 86 NearKeysDistanceMap *prevPrevNearKeysDistances = &nearKeysDistances[2]; 87 // "sumAngle" is accumulated by each angle of input points. And when "sumAngle" exceeds 88 // the threshold we save that point, reset sumAngle. This aims to keep the figure of 89 // the curve. 90 float sumAngle = 0.0f; 91 92 for (int i = pushTouchPointStartIndex; i <= lastInputIndex; ++i) { 93 // Assuming pointerId == 0 if pointerIds is null. 94 const int pid = pointerIds ? pointerIds[i] : 0; 95 if (DEBUG_GEO_FULL) { 96 AKLOGI("Init ProximityInfoState: (%d)PID = %d", i, pid); 97 } 98 if (pointerId == pid) { 99 const int c = isGeometric ? 100 NOT_A_COORDINATE : getPrimaryCodePointAt(inputProximities, i); 101 const int x = proximityOnly ? NOT_A_COORDINATE : inputXCoordinates[i]; 102 const int y = proximityOnly ? NOT_A_COORDINATE : inputYCoordinates[i]; 103 const int time = times ? times[i] : -1; 104 105 if (i > 1) { 106 const float prevAngle = getAngle( 107 inputXCoordinates[i - 2], inputYCoordinates[i - 2], 108 inputXCoordinates[i - 1], inputYCoordinates[i - 1]); 109 const float currentAngle = getAngle( 110 inputXCoordinates[i - 1], inputYCoordinates[i - 1], x, y); 111 sumAngle += getAngleDiff(prevAngle, currentAngle); 112 } 113 114 if (pushTouchPoint(proximityInfo, maxPointToKeyLength, i, c, x, y, time, 115 verticalSweetSpotScale, isGeometric /* doSampling */, i == lastInputIndex, 116 sumAngle, currentNearKeysDistances, prevNearKeysDistances, 117 prevPrevNearKeysDistances, sampledInputXs, sampledInputYs, sampledInputTimes, 118 sampledLengthCache, sampledInputIndice)) { 119 // Previous point information was popped. 120 NearKeysDistanceMap *tmp = prevNearKeysDistances; 121 prevNearKeysDistances = currentNearKeysDistances; 122 currentNearKeysDistances = tmp; 123 } else { 124 NearKeysDistanceMap *tmp = prevPrevNearKeysDistances; 125 prevPrevNearKeysDistances = prevNearKeysDistances; 126 prevNearKeysDistances = currentNearKeysDistances; 127 currentNearKeysDistances = tmp; 128 sumAngle = 0.0f; 129 } 130 } 131 } 132 return sampledInputXs->size(); 133 } 134 135 /* static */ const int *ProximityInfoStateUtils::getProximityCodePointsAt( 136 const int *const inputProximities, const int index) { 137 return inputProximities + (index * MAX_PROXIMITY_CHARS_SIZE); 138 } 139 140 /* static */ int ProximityInfoStateUtils::getPrimaryCodePointAt(const int *const inputProximities, 141 const int index) { 142 return getProximityCodePointsAt(inputProximities, index)[0]; 143 } 144 145 /* static */ void ProximityInfoStateUtils::initPrimaryInputWord(const int inputSize, 146 const int *const inputProximities, int *primaryInputWord) { 147 memset(primaryInputWord, 0, sizeof(primaryInputWord[0]) * MAX_WORD_LENGTH); 148 for (int i = 0; i < inputSize; ++i) { 149 primaryInputWord[i] = getPrimaryCodePointAt(inputProximities, i); 150 } 151 } 152 153 /* static */ float ProximityInfoStateUtils::calculateSquaredDistanceFromSweetSpotCenter( 154 const ProximityInfo *const proximityInfo, const std::vector<int> *const sampledInputXs, 155 const std::vector<int> *const sampledInputYs, const int keyIndex, const int inputIndex) { 156 const float sweetSpotCenterX = proximityInfo->getSweetSpotCenterXAt(keyIndex); 157 const float sweetSpotCenterY = proximityInfo->getSweetSpotCenterYAt(keyIndex); 158 const float inputX = static_cast<float>((*sampledInputXs)[inputIndex]); 159 const float inputY = static_cast<float>((*sampledInputYs)[inputIndex]); 160 return SQUARE_FLOAT(inputX - sweetSpotCenterX) + SQUARE_FLOAT(inputY - sweetSpotCenterY); 161 } 162 163 /* static */ float ProximityInfoStateUtils::calculateNormalizedSquaredDistance( 164 const ProximityInfo *const proximityInfo, const std::vector<int> *const sampledInputXs, 165 const std::vector<int> *const sampledInputYs, const int keyIndex, const int inputIndex) { 166 if (keyIndex == NOT_AN_INDEX) { 167 return ProximityInfoParams::NOT_A_DISTANCE_FLOAT; 168 } 169 if (!proximityInfo->hasSweetSpotData(keyIndex)) { 170 return ProximityInfoParams::NOT_A_DISTANCE_FLOAT; 171 } 172 if (NOT_A_COORDINATE == (*sampledInputXs)[inputIndex]) { 173 return ProximityInfoParams::NOT_A_DISTANCE_FLOAT; 174 } 175 const float squaredDistance = calculateSquaredDistanceFromSweetSpotCenter(proximityInfo, 176 sampledInputXs, sampledInputYs, keyIndex, inputIndex); 177 const float squaredRadius = SQUARE_FLOAT(proximityInfo->getSweetSpotRadiiAt(keyIndex)); 178 return squaredDistance / squaredRadius; 179 } 180 181 /* static */ void ProximityInfoStateUtils::initNormalizedSquaredDistances( 182 const ProximityInfo *const proximityInfo, const int inputSize, const int *inputXCoordinates, 183 const int *inputYCoordinates, const int *const inputProximities, 184 const std::vector<int> *const sampledInputXs, const std::vector<int> *const sampledInputYs, 185 int *normalizedSquaredDistances) { 186 memset(normalizedSquaredDistances, NOT_A_DISTANCE, 187 sizeof(normalizedSquaredDistances[0]) * MAX_PROXIMITY_CHARS_SIZE * MAX_WORD_LENGTH); 188 const bool hasInputCoordinates = sampledInputXs->size() > 0 && sampledInputYs->size() > 0; 189 for (int i = 0; i < inputSize; ++i) { 190 const int *proximityCodePoints = getProximityCodePointsAt(inputProximities, i); 191 const int primaryKey = proximityCodePoints[0]; 192 const int x = inputXCoordinates[i]; 193 const int y = inputYCoordinates[i]; 194 if (DEBUG_PROXIMITY_CHARS) { 195 int a = x + y + primaryKey; 196 a += 0; 197 AKLOGI("--- Primary = %c, x = %d, y = %d", primaryKey, x, y); 198 } 199 for (int j = 0; j < MAX_PROXIMITY_CHARS_SIZE && proximityCodePoints[j] > 0; ++j) { 200 const int currentCodePoint = proximityCodePoints[j]; 201 const float squaredDistance = 202 hasInputCoordinates ? calculateNormalizedSquaredDistance( 203 proximityInfo, sampledInputXs, sampledInputYs, 204 proximityInfo->getKeyIndexOf(currentCodePoint), i) : 205 ProximityInfoParams::NOT_A_DISTANCE_FLOAT; 206 if (squaredDistance >= 0.0f) { 207 normalizedSquaredDistances[i * MAX_PROXIMITY_CHARS_SIZE + j] = 208 static_cast<int>(squaredDistance 209 * ProximityInfoParams::NORMALIZED_SQUARED_DISTANCE_SCALING_FACTOR); 210 } else { 211 normalizedSquaredDistances[i * MAX_PROXIMITY_CHARS_SIZE + j] = 212 (j == 0) ? MATCH_CHAR_WITHOUT_DISTANCE_INFO : 213 PROXIMITY_CHAR_WITHOUT_DISTANCE_INFO; 214 } 215 if (DEBUG_PROXIMITY_CHARS) { 216 AKLOGI("--- Proximity (%d) = %c", j, currentCodePoint); 217 } 218 } 219 } 220 221 } 222 223 /* static */ void ProximityInfoStateUtils::initGeometricDistanceInfos( 224 const ProximityInfo *const proximityInfo, const int sampledInputSize, 225 const int lastSavedInputSize, const float verticalSweetSpotScale, 226 const std::vector<int> *const sampledInputXs, 227 const std::vector<int> *const sampledInputYs, 228 std::vector<NearKeycodesSet> *sampledNearKeySets, 229 std::vector<float> *sampledNormalizedSquaredLengthCache) { 230 sampledNearKeySets->resize(sampledInputSize); 231 const int keyCount = proximityInfo->getKeyCount(); 232 sampledNormalizedSquaredLengthCache->resize(sampledInputSize * keyCount); 233 for (int i = lastSavedInputSize; i < sampledInputSize; ++i) { 234 (*sampledNearKeySets)[i].reset(); 235 for (int k = 0; k < keyCount; ++k) { 236 const int index = i * keyCount + k; 237 const int x = (*sampledInputXs)[i]; 238 const int y = (*sampledInputYs)[i]; 239 const float normalizedSquaredDistance = 240 proximityInfo->getNormalizedSquaredDistanceFromCenterFloatG( 241 k, x, y, verticalSweetSpotScale); 242 (*sampledNormalizedSquaredLengthCache)[index] = normalizedSquaredDistance; 243 if (normalizedSquaredDistance 244 < ProximityInfoParams::NEAR_KEY_NORMALIZED_SQUARED_THRESHOLD) { 245 (*sampledNearKeySets)[i][k] = true; 246 } 247 } 248 } 249 } 250 251 /* static */ void ProximityInfoStateUtils::popInputData(std::vector<int> *sampledInputXs, 252 std::vector<int> *sampledInputYs, std::vector<int> *sampledInputTimes, 253 std::vector<int> *sampledLengthCache, std::vector<int> *sampledInputIndice) { 254 sampledInputXs->pop_back(); 255 sampledInputYs->pop_back(); 256 sampledInputTimes->pop_back(); 257 sampledLengthCache->pop_back(); 258 sampledInputIndice->pop_back(); 259 } 260 261 /* static */ float ProximityInfoStateUtils::refreshSpeedRates(const int inputSize, 262 const int *const xCoordinates, const int *const yCoordinates, const int *const times, 263 const int lastSavedInputSize, const int sampledInputSize, 264 const std::vector<int> *const sampledInputXs, const std::vector<int> *const sampledInputYs, 265 const std::vector<int> *const sampledInputTimes, 266 const std::vector<int> *const sampledLengthCache, 267 const std::vector<int> *const sampledInputIndice, std::vector<float> *sampledSpeedRates, 268 std::vector<float> *sampledDirections) { 269 // Relative speed calculation. 270 const int sumDuration = sampledInputTimes->back() - sampledInputTimes->front(); 271 const int sumLength = sampledLengthCache->back() - sampledLengthCache->front(); 272 const float averageSpeed = static_cast<float>(sumLength) / static_cast<float>(sumDuration); 273 sampledSpeedRates->resize(sampledInputSize); 274 for (int i = lastSavedInputSize; i < sampledInputSize; ++i) { 275 const int index = (*sampledInputIndice)[i]; 276 int length = 0; 277 int duration = 0; 278 279 // Calculate velocity by using distances and durations of 280 // ProximityInfoParams::NUM_POINTS_FOR_SPEED_CALCULATION points for both forward and 281 // backward. 282 const int forwardNumPoints = min(inputSize - 1, 283 index + ProximityInfoParams::NUM_POINTS_FOR_SPEED_CALCULATION); 284 for (int j = index; j < forwardNumPoints; ++j) { 285 if (i < sampledInputSize - 1 && j >= (*sampledInputIndice)[i + 1]) { 286 break; 287 } 288 length += getDistanceInt(xCoordinates[j], yCoordinates[j], 289 xCoordinates[j + 1], yCoordinates[j + 1]); 290 duration += times[j + 1] - times[j]; 291 } 292 const int backwardNumPoints = max(0, 293 index - ProximityInfoParams::NUM_POINTS_FOR_SPEED_CALCULATION); 294 for (int j = index - 1; j >= backwardNumPoints; --j) { 295 if (i > 0 && j < (*sampledInputIndice)[i - 1]) { 296 break; 297 } 298 // TODO: use mSampledLengthCache instead? 299 length += getDistanceInt(xCoordinates[j], yCoordinates[j], 300 xCoordinates[j + 1], yCoordinates[j + 1]); 301 duration += times[j + 1] - times[j]; 302 } 303 if (duration == 0 || sumDuration == 0) { 304 // Cannot calculate speed; thus, it gives an average value (1.0); 305 (*sampledSpeedRates)[i] = 1.0f; 306 } else { 307 const float speed = static_cast<float>(length) / static_cast<float>(duration); 308 (*sampledSpeedRates)[i] = speed / averageSpeed; 309 } 310 } 311 312 // Direction calculation. 313 sampledDirections->resize(sampledInputSize - 1); 314 for (int i = max(0, lastSavedInputSize - 1); i < sampledInputSize - 1; ++i) { 315 (*sampledDirections)[i] = getDirection(sampledInputXs, sampledInputYs, i, i + 1); 316 } 317 return averageSpeed; 318 } 319 320 /* static */ void ProximityInfoStateUtils::refreshBeelineSpeedRates(const int mostCommonKeyWidth, 321 const float averageSpeed, const int inputSize, const int *const xCoordinates, 322 const int *const yCoordinates, const int *times, const int sampledInputSize, 323 const std::vector<int> *const sampledInputXs, 324 const std::vector<int> *const sampledInputYs, const std::vector<int> *const inputIndice, 325 std::vector<int> *beelineSpeedPercentiles) { 326 if (DEBUG_SAMPLING_POINTS) { 327 AKLOGI("--- refresh beeline speed rates"); 328 } 329 beelineSpeedPercentiles->resize(sampledInputSize); 330 for (int i = 0; i < sampledInputSize; ++i) { 331 (*beelineSpeedPercentiles)[i] = static_cast<int>(calculateBeelineSpeedRate( 332 mostCommonKeyWidth, averageSpeed, i, inputSize, xCoordinates, yCoordinates, times, 333 sampledInputSize, sampledInputXs, sampledInputYs, inputIndice) * MAX_PERCENTILE); 334 } 335 } 336 337 /* static */float ProximityInfoStateUtils::getDirection( 338 const std::vector<int> *const sampledInputXs, 339 const std::vector<int> *const sampledInputYs, const int index0, const int index1) { 340 ASSERT(sampledInputXs && sampledInputYs); 341 const int sampledInputSize =sampledInputXs->size(); 342 if (index0 < 0 || index0 > sampledInputSize - 1) { 343 return 0.0f; 344 } 345 if (index1 < 0 || index1 > sampledInputSize - 1) { 346 return 0.0f; 347 } 348 const int x1 = (*sampledInputXs)[index0]; 349 const int y1 = (*sampledInputYs)[index0]; 350 const int x2 = (*sampledInputXs)[index1]; 351 const int y2 = (*sampledInputYs)[index1]; 352 return getAngle(x1, y1, x2, y2); 353 } 354 355 // Calculating point to key distance for all near keys and returning the distance between 356 // the given point and the nearest key position. 357 /* static */ float ProximityInfoStateUtils::updateNearKeysDistances( 358 const ProximityInfo *const proximityInfo, const float maxPointToKeyLength, const int x, 359 const int y, const float verticalSweetspotScale, 360 NearKeysDistanceMap *const currentNearKeysDistances) { 361 currentNearKeysDistances->clear(); 362 const int keyCount = proximityInfo->getKeyCount(); 363 float nearestKeyDistance = maxPointToKeyLength; 364 for (int k = 0; k < keyCount; ++k) { 365 const float dist = proximityInfo->getNormalizedSquaredDistanceFromCenterFloatG(k, x, y, 366 verticalSweetspotScale); 367 if (dist < ProximityInfoParams::NEAR_KEY_THRESHOLD_FOR_DISTANCE) { 368 currentNearKeysDistances->insert(std::pair<int, float>(k, dist)); 369 } 370 if (nearestKeyDistance > dist) { 371 nearestKeyDistance = dist; 372 } 373 } 374 return nearestKeyDistance; 375 } 376 377 // Check if previous point is at local minimum position to near keys. 378 /* static */ bool ProximityInfoStateUtils::isPrevLocalMin( 379 const NearKeysDistanceMap *const currentNearKeysDistances, 380 const NearKeysDistanceMap *const prevNearKeysDistances, 381 const NearKeysDistanceMap *const prevPrevNearKeysDistances) { 382 for (NearKeysDistanceMap::const_iterator it = prevNearKeysDistances->begin(); 383 it != prevNearKeysDistances->end(); ++it) { 384 NearKeysDistanceMap::const_iterator itPP = prevPrevNearKeysDistances->find(it->first); 385 NearKeysDistanceMap::const_iterator itC = currentNearKeysDistances->find(it->first); 386 const bool isPrevPrevNear = (itPP == prevPrevNearKeysDistances->end() 387 || itPP->second > it->second + ProximityInfoParams::MARGIN_FOR_PREV_LOCAL_MIN); 388 const bool isCurrentNear = (itC == currentNearKeysDistances->end() 389 || itC->second > it->second + ProximityInfoParams::MARGIN_FOR_PREV_LOCAL_MIN); 390 if (isPrevPrevNear && isCurrentNear) { 391 return true; 392 } 393 } 394 return false; 395 } 396 397 // Calculating a point score that indicates usefulness of the point. 398 /* static */ float ProximityInfoStateUtils::getPointScore(const int mostCommonKeyWidth, 399 const int x, const int y, const int time, const bool lastPoint, const float nearest, 400 const float sumAngle, const NearKeysDistanceMap *const currentNearKeysDistances, 401 const NearKeysDistanceMap *const prevNearKeysDistances, 402 const NearKeysDistanceMap *const prevPrevNearKeysDistances, 403 std::vector<int> *sampledInputXs, std::vector<int> *sampledInputYs) { 404 const size_t size = sampledInputXs->size(); 405 // If there is only one point, add this point. Besides, if the previous point's distance map 406 // is empty, we re-compute nearby keys distances from the current point. 407 // Note that the current point is the first point in the incremental input that needs to 408 // be re-computed. 409 if (size <= 1 || prevNearKeysDistances->empty()) { 410 return 0.0f; 411 } 412 413 const int baseSampleRate = mostCommonKeyWidth; 414 const int distPrev = getDistanceInt(sampledInputXs->back(), sampledInputYs->back(), 415 (*sampledInputXs)[size - 2], (*sampledInputYs)[size - 2]) 416 * ProximityInfoParams::DISTANCE_BASE_SCALE; 417 float score = 0.0f; 418 419 // Location 420 if (!isPrevLocalMin(currentNearKeysDistances, prevNearKeysDistances, 421 prevPrevNearKeysDistances)) { 422 score += ProximityInfoParams::NOT_LOCALMIN_DISTANCE_SCORE; 423 } else if (nearest < ProximityInfoParams::NEAR_KEY_THRESHOLD_FOR_POINT_SCORE) { 424 // Promote points nearby keys 425 score += ProximityInfoParams::LOCALMIN_DISTANCE_AND_NEAR_TO_KEY_SCORE; 426 } 427 // Angle 428 const float angle1 = getAngle(x, y, sampledInputXs->back(), sampledInputYs->back()); 429 const float angle2 = getAngle(sampledInputXs->back(), sampledInputYs->back(), 430 (*sampledInputXs)[size - 2], (*sampledInputYs)[size - 2]); 431 const float angleDiff = getAngleDiff(angle1, angle2); 432 433 // Save corner 434 if (distPrev > baseSampleRate * ProximityInfoParams::CORNER_CHECK_DISTANCE_THRESHOLD_SCALE 435 && (sumAngle > ProximityInfoParams::CORNER_SUM_ANGLE_THRESHOLD 436 || angleDiff > ProximityInfoParams::CORNER_ANGLE_THRESHOLD_FOR_POINT_SCORE)) { 437 score += ProximityInfoParams::CORNER_SCORE; 438 } 439 return score; 440 } 441 442 // Sampling touch point and pushing information to vectors. 443 // Returning if previous point is popped or not. 444 /* static */ bool ProximityInfoStateUtils::pushTouchPoint(const ProximityInfo *const proximityInfo, 445 const int maxPointToKeyLength, const int inputIndex, const int nodeCodePoint, int x, int y, 446 const int time, const float verticalSweetSpotScale, const bool doSampling, 447 const bool isLastPoint, const float sumAngle, 448 NearKeysDistanceMap *const currentNearKeysDistances, 449 const NearKeysDistanceMap *const prevNearKeysDistances, 450 const NearKeysDistanceMap *const prevPrevNearKeysDistances, 451 std::vector<int> *sampledInputXs, std::vector<int> *sampledInputYs, 452 std::vector<int> *sampledInputTimes, std::vector<int> *sampledLengthCache, 453 std::vector<int> *sampledInputIndice) { 454 const int mostCommonKeyWidth = proximityInfo->getMostCommonKeyWidth(); 455 456 size_t size = sampledInputXs->size(); 457 bool popped = false; 458 if (nodeCodePoint < 0 && doSampling) { 459 const float nearest = updateNearKeysDistances(proximityInfo, maxPointToKeyLength, x, y, 460 verticalSweetSpotScale, currentNearKeysDistances); 461 const float score = getPointScore(mostCommonKeyWidth, x, y, time, isLastPoint, nearest, 462 sumAngle, currentNearKeysDistances, prevNearKeysDistances, 463 prevPrevNearKeysDistances, sampledInputXs, sampledInputYs); 464 if (score < 0) { 465 // Pop previous point because it would be useless. 466 popInputData(sampledInputXs, sampledInputYs, sampledInputTimes, sampledLengthCache, 467 sampledInputIndice); 468 size = sampledInputXs->size(); 469 popped = true; 470 } else { 471 popped = false; 472 } 473 // Check if the last point should be skipped. 474 if (isLastPoint && size > 0) { 475 if (getDistanceInt(x, y, sampledInputXs->back(), sampledInputYs->back()) 476 * ProximityInfoParams::LAST_POINT_SKIP_DISTANCE_SCALE < mostCommonKeyWidth) { 477 // This point is not used because it's too close to the previous point. 478 if (DEBUG_GEO_FULL) { 479 AKLOGI("p0: size = %zd, x = %d, y = %d, lx = %d, ly = %d, dist = %d, " 480 "width = %d", size, x, y, sampledInputXs->back(), 481 sampledInputYs->back(), getDistanceInt( 482 x, y, sampledInputXs->back(), sampledInputYs->back()), 483 mostCommonKeyWidth 484 / ProximityInfoParams::LAST_POINT_SKIP_DISTANCE_SCALE); 485 } 486 return popped; 487 } 488 } 489 } 490 491 if (nodeCodePoint >= 0 && (x < 0 || y < 0)) { 492 const int keyId = proximityInfo->getKeyIndexOf(nodeCodePoint); 493 if (keyId >= 0) { 494 x = proximityInfo->getKeyCenterXOfKeyIdG(keyId); 495 y = proximityInfo->getKeyCenterYOfKeyIdG(keyId); 496 } 497 } 498 499 // Pushing point information. 500 if (size > 0) { 501 sampledLengthCache->push_back( 502 sampledLengthCache->back() + getDistanceInt( 503 x, y, sampledInputXs->back(), sampledInputYs->back())); 504 } else { 505 sampledLengthCache->push_back(0); 506 } 507 sampledInputXs->push_back(x); 508 sampledInputYs->push_back(y); 509 sampledInputTimes->push_back(time); 510 sampledInputIndice->push_back(inputIndex); 511 if (DEBUG_GEO_FULL) { 512 AKLOGI("pushTouchPoint: x = %03d, y = %03d, time = %d, index = %d, popped ? %01d", 513 x, y, time, inputIndex, popped); 514 } 515 return popped; 516 } 517 518 /* static */ float ProximityInfoStateUtils::calculateBeelineSpeedRate(const int mostCommonKeyWidth, 519 const float averageSpeed, const int id, const int inputSize, const int *const xCoordinates, 520 const int *const yCoordinates, const int *times, const int sampledInputSize, 521 const std::vector<int> *const sampledInputXs, 522 const std::vector<int> *const sampledInputYs, 523 const std::vector<int> *const sampledInputIndices) { 524 if (sampledInputSize <= 0 || averageSpeed < 0.001f) { 525 if (DEBUG_SAMPLING_POINTS) { 526 AKLOGI("--- invalid state: cancel. size = %d, ave = %f", 527 sampledInputSize, averageSpeed); 528 } 529 return 1.0f; 530 } 531 const int lookupRadius = mostCommonKeyWidth 532 * ProximityInfoParams::LOOKUP_RADIUS_PERCENTILE / MAX_PERCENTILE; 533 const int x0 = (*sampledInputXs)[id]; 534 const int y0 = (*sampledInputYs)[id]; 535 const int actualInputIndex = (*sampledInputIndices)[id]; 536 int tempTime = 0; 537 int tempBeelineDistance = 0; 538 int start = actualInputIndex; 539 // lookup forward 540 while (start > 0 && tempBeelineDistance < lookupRadius) { 541 tempTime += times[start] - times[start - 1]; 542 --start; 543 tempBeelineDistance = getDistanceInt(x0, y0, xCoordinates[start], yCoordinates[start]); 544 } 545 // Exclusive unless this is an edge point 546 if (start > 0 && start < actualInputIndex) { 547 ++start; 548 } 549 tempTime= 0; 550 tempBeelineDistance = 0; 551 int end = actualInputIndex; 552 // lookup backward 553 while (end < (inputSize - 1) && tempBeelineDistance < lookupRadius) { 554 tempTime += times[end + 1] - times[end]; 555 ++end; 556 tempBeelineDistance = getDistanceInt(x0, y0, xCoordinates[end], yCoordinates[end]); 557 } 558 // Exclusive unless this is an edge point 559 if (end > actualInputIndex && end < (inputSize - 1)) { 560 --end; 561 } 562 563 if (start >= end) { 564 if (DEBUG_DOUBLE_LETTER) { 565 AKLOGI("--- double letter: start == end %d", start); 566 } 567 return 1.0f; 568 } 569 570 const int x2 = xCoordinates[start]; 571 const int y2 = yCoordinates[start]; 572 const int x3 = xCoordinates[end]; 573 const int y3 = yCoordinates[end]; 574 const int beelineDistance = getDistanceInt(x2, y2, x3, y3); 575 int adjustedStartTime = times[start]; 576 if (start == 0 && actualInputIndex == 0 && inputSize > 1) { 577 adjustedStartTime += ProximityInfoParams::FIRST_POINT_TIME_OFFSET_MILLIS; 578 } 579 int adjustedEndTime = times[end]; 580 if (end == (inputSize - 1) && inputSize > 1) { 581 adjustedEndTime -= ProximityInfoParams::FIRST_POINT_TIME_OFFSET_MILLIS; 582 } 583 const int time = adjustedEndTime - adjustedStartTime; 584 if (time <= 0) { 585 return 1.0f; 586 } 587 588 if (time >= ProximityInfoParams::STRONG_DOUBLE_LETTER_TIME_MILLIS){ 589 return 0.0f; 590 } 591 if (DEBUG_DOUBLE_LETTER) { 592 AKLOGI("--- (%d, %d) double letter: start = %d, end = %d, dist = %d, time = %d," 593 " speed = %f, ave = %f, val = %f, start time = %d, end time = %d", 594 id, (*sampledInputIndices)[id], start, end, beelineDistance, time, 595 (static_cast<float>(beelineDistance) / static_cast<float>(time)), averageSpeed, 596 ((static_cast<float>(beelineDistance) / static_cast<float>(time)) 597 / averageSpeed), adjustedStartTime, adjustedEndTime); 598 } 599 // Offset 1% 600 // TODO: Detect double letter more smartly 601 return 0.01f + static_cast<float>(beelineDistance) / static_cast<float>(time) / averageSpeed; 602 } 603 604 /* static */ float ProximityInfoStateUtils::getPointAngle( 605 const std::vector<int> *const sampledInputXs, 606 const std::vector<int> *const sampledInputYs, const int index) { 607 if (!sampledInputXs || !sampledInputYs) { 608 return 0.0f; 609 } 610 const int sampledInputSize = sampledInputXs->size(); 611 if (index <= 0 || index >= sampledInputSize - 1) { 612 return 0.0f; 613 } 614 const float previousDirection = getDirection(sampledInputXs, sampledInputYs, index - 1, index); 615 const float nextDirection = getDirection(sampledInputXs, sampledInputYs, index, index + 1); 616 const float directionDiff = getAngleDiff(previousDirection, nextDirection); 617 return directionDiff; 618 } 619 620 /* static */ float ProximityInfoStateUtils::getPointsAngle( 621 const std::vector<int> *const sampledInputXs, 622 const std::vector<int> *const sampledInputYs, 623 const int index0, const int index1, const int index2) { 624 if (!sampledInputXs || !sampledInputYs) { 625 return 0.0f; 626 } 627 const int sampledInputSize = sampledInputXs->size(); 628 if (index0 < 0 || index0 > sampledInputSize - 1) { 629 return 0.0f; 630 } 631 if (index1 < 0 || index1 > sampledInputSize - 1) { 632 return 0.0f; 633 } 634 if (index2 < 0 || index2 > sampledInputSize - 1) { 635 return 0.0f; 636 } 637 const float previousDirection = getDirection(sampledInputXs, sampledInputYs, index0, index1); 638 const float nextDirection = getDirection(sampledInputXs, sampledInputYs, index1, index2); 639 return getAngleDiff(previousDirection, nextDirection); 640 } 641 642 // This function basically converts from a length to an edit distance. Accordingly, it's obviously 643 // wrong to compare with mMaxPointToKeyLength. 644 /* static */ float ProximityInfoStateUtils::getPointToKeyByIdLength(const float maxPointToKeyLength, 645 const std::vector<float> *const sampledNormalizedSquaredLengthCache, const int keyCount, 646 const int inputIndex, const int keyId) { 647 if (keyId != NOT_AN_INDEX) { 648 const int index = inputIndex * keyCount + keyId; 649 return min((*sampledNormalizedSquaredLengthCache)[index], maxPointToKeyLength); 650 } 651 // If the char is not a key on the keyboard then return the max length. 652 return static_cast<float>(MAX_VALUE_FOR_WEIGHTING); 653 } 654 655 // Updates probabilities of aligning to some keys and skipping. 656 // Word suggestion should be based on this probabilities. 657 /* static */ void ProximityInfoStateUtils::updateAlignPointProbabilities( 658 const float maxPointToKeyLength, const int mostCommonKeyWidth, const int keyCount, 659 const int start, const int sampledInputSize, const std::vector<int> *const sampledInputXs, 660 const std::vector<int> *const sampledInputYs, 661 const std::vector<float> *const sampledSpeedRates, 662 const std::vector<int> *const sampledLengthCache, 663 const std::vector<float> *const sampledNormalizedSquaredLengthCache, 664 std::vector<NearKeycodesSet> *sampledNearKeySets, 665 std::vector<hash_map_compat<int, float> > *charProbabilities) { 666 charProbabilities->resize(sampledInputSize); 667 // Calculates probabilities of using a point as a correlated point with the character 668 // for each point. 669 for (int i = start; i < sampledInputSize; ++i) { 670 (*charProbabilities)[i].clear(); 671 // First, calculates skip probability. Starts from MAX_SKIP_PROBABILITY. 672 // Note that all values that are multiplied to this probability should be in [0.0, 1.0]; 673 float skipProbability = ProximityInfoParams::MAX_SKIP_PROBABILITY; 674 675 const float currentAngle = getPointAngle(sampledInputXs, sampledInputYs, i); 676 const float speedRate = (*sampledSpeedRates)[i]; 677 678 float nearestKeyDistance = static_cast<float>(MAX_VALUE_FOR_WEIGHTING); 679 for (int j = 0; j < keyCount; ++j) { 680 if ((*sampledNearKeySets)[i].test(j)) { 681 const float distance = getPointToKeyByIdLength( 682 maxPointToKeyLength, sampledNormalizedSquaredLengthCache, keyCount, i, j); 683 if (distance < nearestKeyDistance) { 684 nearestKeyDistance = distance; 685 } 686 } 687 } 688 689 if (i == 0) { 690 skipProbability *= min(1.0f, 691 nearestKeyDistance * ProximityInfoParams::NEAREST_DISTANCE_WEIGHT 692 + ProximityInfoParams::NEAREST_DISTANCE_BIAS); 693 // Promote the first point 694 skipProbability *= ProximityInfoParams::SKIP_FIRST_POINT_PROBABILITY; 695 } else if (i == sampledInputSize - 1) { 696 skipProbability *= min(1.0f, 697 nearestKeyDistance * ProximityInfoParams::NEAREST_DISTANCE_WEIGHT_FOR_LAST 698 + ProximityInfoParams::NEAREST_DISTANCE_BIAS_FOR_LAST); 699 // Promote the last point 700 skipProbability *= ProximityInfoParams::SKIP_LAST_POINT_PROBABILITY; 701 } else { 702 // If the current speed is relatively slower than adjacent keys, we promote this point. 703 if ((*sampledSpeedRates)[i - 1] - ProximityInfoParams::SPEED_MARGIN > speedRate 704 && speedRate 705 < (*sampledSpeedRates)[i + 1] - ProximityInfoParams::SPEED_MARGIN) { 706 if (currentAngle < ProximityInfoParams::CORNER_ANGLE_THRESHOLD) { 707 skipProbability *= min(1.0f, speedRate 708 * ProximityInfoParams::SLOW_STRAIGHT_WEIGHT_FOR_SKIP_PROBABILITY); 709 } else { 710 // If the angle is small enough, we promote this point more. (e.g. pit vs put) 711 skipProbability *= min(1.0f, 712 speedRate * ProximityInfoParams::SPEED_WEIGHT_FOR_SKIP_PROBABILITY 713 + ProximityInfoParams::MIN_SPEED_RATE_FOR_SKIP_PROBABILITY); 714 } 715 } 716 717 skipProbability *= min(1.0f, 718 speedRate * nearestKeyDistance * ProximityInfoParams::NEAREST_DISTANCE_WEIGHT 719 + ProximityInfoParams::NEAREST_DISTANCE_BIAS); 720 721 // Adjusts skip probability by a rate depending on angle. 722 // ANGLE_RATE of skipProbability is adjusted by current angle. 723 skipProbability *= (M_PI_F - currentAngle) / M_PI_F * ProximityInfoParams::ANGLE_WEIGHT 724 + (1.0f - ProximityInfoParams::ANGLE_WEIGHT); 725 if (currentAngle > ProximityInfoParams::DEEP_CORNER_ANGLE_THRESHOLD) { 726 skipProbability *= ProximityInfoParams::SKIP_DEEP_CORNER_PROBABILITY; 727 } 728 // We assume the angle of this point is the angle for point[i], point[i - 2] 729 // and point[i - 3]. The reason why we don't use the angle for point[i], point[i - 1] 730 // and point[i - 2] is this angle can be more affected by the noise. 731 const float prevAngle = getPointsAngle(sampledInputXs, sampledInputYs, i, i - 2, i - 3); 732 if (i >= 3 && prevAngle < ProximityInfoParams::STRAIGHT_ANGLE_THRESHOLD 733 && currentAngle > ProximityInfoParams::CORNER_ANGLE_THRESHOLD) { 734 skipProbability *= ProximityInfoParams::SKIP_CORNER_PROBABILITY; 735 } 736 } 737 738 // probabilities must be in [0.0, ProximityInfoParams::MAX_SKIP_PROBABILITY]; 739 ASSERT(skipProbability >= 0.0f); 740 ASSERT(skipProbability <= ProximityInfoParams::MAX_SKIP_PROBABILITY); 741 (*charProbabilities)[i][NOT_AN_INDEX] = skipProbability; 742 743 // Second, calculates key probabilities by dividing the rest probability 744 // (1.0f - skipProbability). 745 const float inputCharProbability = 1.0f - skipProbability; 746 747 const float speedxAngleRate = min(speedRate * currentAngle / M_PI_F 748 * ProximityInfoParams::SPEEDxANGLE_WEIGHT_FOR_STANDARD_DIVIATION, 749 ProximityInfoParams::MAX_SPEEDxANGLE_RATE_FOR_STANDERD_DIVIATION); 750 const float speedxNearestKeyDistanceRate = min(speedRate * nearestKeyDistance 751 * ProximityInfoParams::SPEEDxNEAREST_WEIGHT_FOR_STANDARD_DIVIATION, 752 ProximityInfoParams::MAX_SPEEDxNEAREST_RATE_FOR_STANDERD_DIVIATION); 753 const float sigma = speedxAngleRate + speedxNearestKeyDistanceRate 754 + ProximityInfoParams::MIN_STANDERD_DIVIATION; 755 756 ProximityInfoUtils::NormalDistribution 757 distribution(ProximityInfoParams::CENTER_VALUE_OF_NORMALIZED_DISTRIBUTION, sigma); 758 // Summing up probability densities of all near keys. 759 float sumOfProbabilityDensities = 0.0f; 760 for (int j = 0; j < keyCount; ++j) { 761 if ((*sampledNearKeySets)[i].test(j)) { 762 float distance = sqrtf(getPointToKeyByIdLength( 763 maxPointToKeyLength, sampledNormalizedSquaredLengthCache, keyCount, i, j)); 764 if (i == 0 && i != sampledInputSize - 1) { 765 // For the first point, weighted average of distances from first point and the 766 // next point to the key is used as a point to key distance. 767 const float nextDistance = sqrtf(getPointToKeyByIdLength( 768 maxPointToKeyLength, sampledNormalizedSquaredLengthCache, keyCount, 769 i + 1, j)); 770 if (nextDistance < distance) { 771 // The distance of the first point tends to bigger than continuing 772 // points because the first touch by the user can be sloppy. 773 // So we promote the first point if the distance of that point is larger 774 // than the distance of the next point. 775 distance = (distance 776 + nextDistance * ProximityInfoParams::NEXT_DISTANCE_WEIGHT) 777 / (1.0f + ProximityInfoParams::NEXT_DISTANCE_WEIGHT); 778 } 779 } else if (i != 0 && i == sampledInputSize - 1) { 780 // For the first point, weighted average of distances from last point and 781 // the previous point to the key is used as a point to key distance. 782 const float previousDistance = sqrtf(getPointToKeyByIdLength( 783 maxPointToKeyLength, sampledNormalizedSquaredLengthCache, keyCount, 784 i - 1, j)); 785 if (previousDistance < distance) { 786 // The distance of the last point tends to bigger than continuing points 787 // because the last touch by the user can be sloppy. So we promote the 788 // last point if the distance of that point is larger than the distance of 789 // the previous point. 790 distance = (distance 791 + previousDistance * ProximityInfoParams::PREV_DISTANCE_WEIGHT) 792 / (1.0f + ProximityInfoParams::PREV_DISTANCE_WEIGHT); 793 } 794 } 795 // TODO: Promote the first point when the extended line from the next input is near 796 // from a key. Also, promote the last point as well. 797 sumOfProbabilityDensities += distribution.getProbabilityDensity(distance); 798 } 799 } 800 801 // Split the probability of an input point to keys that are close to the input point. 802 for (int j = 0; j < keyCount; ++j) { 803 if ((*sampledNearKeySets)[i].test(j)) { 804 float distance = sqrtf(getPointToKeyByIdLength( 805 maxPointToKeyLength, sampledNormalizedSquaredLengthCache, keyCount, i, j)); 806 if (i == 0 && i != sampledInputSize - 1) { 807 // For the first point, weighted average of distances from the first point and 808 // the next point to the key is used as a point to key distance. 809 const float prevDistance = sqrtf(getPointToKeyByIdLength( 810 maxPointToKeyLength, sampledNormalizedSquaredLengthCache, keyCount, 811 i + 1, j)); 812 if (prevDistance < distance) { 813 distance = (distance 814 + prevDistance * ProximityInfoParams::NEXT_DISTANCE_WEIGHT) 815 / (1.0f + ProximityInfoParams::NEXT_DISTANCE_WEIGHT); 816 } 817 } else if (i != 0 && i == sampledInputSize - 1) { 818 // For the first point, weighted average of distances from last point and 819 // the previous point to the key is used as a point to key distance. 820 const float prevDistance = sqrtf(getPointToKeyByIdLength( 821 maxPointToKeyLength, sampledNormalizedSquaredLengthCache, keyCount, 822 i - 1, j)); 823 if (prevDistance < distance) { 824 distance = (distance 825 + prevDistance * ProximityInfoParams::PREV_DISTANCE_WEIGHT) 826 / (1.0f + ProximityInfoParams::PREV_DISTANCE_WEIGHT); 827 } 828 } 829 const float probabilityDensity = distribution.getProbabilityDensity(distance); 830 const float probability = inputCharProbability * probabilityDensity 831 / sumOfProbabilityDensities; 832 (*charProbabilities)[i][j] = probability; 833 } 834 } 835 } 836 837 if (DEBUG_POINTS_PROBABILITY) { 838 for (int i = 0; i < sampledInputSize; ++i) { 839 std::stringstream sstream; 840 sstream << i << ", "; 841 sstream << "(" << (*sampledInputXs)[i] << ", " << (*sampledInputYs)[i] << "), "; 842 sstream << "Speed: "<< (*sampledSpeedRates)[i] << ", "; 843 sstream << "Angle: "<< getPointAngle(sampledInputXs, sampledInputYs, i) << ", \n"; 844 845 for (hash_map_compat<int, float>::iterator it = (*charProbabilities)[i].begin(); 846 it != (*charProbabilities)[i].end(); ++it) { 847 if (it->first == NOT_AN_INDEX) { 848 sstream << it->first 849 << "(skip):" 850 << it->second 851 << "\n"; 852 } else { 853 sstream << it->first 854 << "(" 855 //<< static_cast<char>(mProximityInfo->getCodePointOf(it->first)) 856 << "):" 857 << it->second 858 << "\n"; 859 } 860 } 861 AKLOGI("%s", sstream.str().c_str()); 862 } 863 } 864 865 // Decrease key probabilities of points which don't have the highest probability of that key 866 // among nearby points. Probabilities of the first point and the last point are not suppressed. 867 for (int i = max(start, 1); i < sampledInputSize; ++i) { 868 for (int j = i + 1; j < sampledInputSize; ++j) { 869 if (!suppressCharProbabilities( 870 mostCommonKeyWidth, sampledInputSize, sampledLengthCache, i, j, 871 charProbabilities)) { 872 break; 873 } 874 } 875 for (int j = i - 1; j >= max(start, 0); --j) { 876 if (!suppressCharProbabilities( 877 mostCommonKeyWidth, sampledInputSize, sampledLengthCache, i, j, 878 charProbabilities)) { 879 break; 880 } 881 } 882 } 883 884 // Converting from raw probabilities to log probabilities to calculate spatial distance. 885 for (int i = start; i < sampledInputSize; ++i) { 886 for (int j = 0; j < keyCount; ++j) { 887 hash_map_compat<int, float>::iterator it = (*charProbabilities)[i].find(j); 888 if (it == (*charProbabilities)[i].end()){ 889 (*sampledNearKeySets)[i].reset(j); 890 } else if(it->second < ProximityInfoParams::MIN_PROBABILITY) { 891 // Erases from near keys vector because it has very low probability. 892 (*sampledNearKeySets)[i].reset(j); 893 (*charProbabilities)[i].erase(j); 894 } else { 895 it->second = -logf(it->second); 896 } 897 } 898 (*charProbabilities)[i][NOT_AN_INDEX] = -logf((*charProbabilities)[i][NOT_AN_INDEX]); 899 } 900 } 901 902 /* static */ void ProximityInfoStateUtils::updateSampledSearchKeySets( 903 const ProximityInfo *const proximityInfo, const int sampledInputSize, 904 const int lastSavedInputSize, 905 const std::vector<int> *const sampledLengthCache, 906 const std::vector<NearKeycodesSet> *const sampledNearKeySets, 907 std::vector<NearKeycodesSet> *sampledSearchKeySets, 908 std::vector<std::vector<int> > *sampledSearchKeyVectors) { 909 sampledSearchKeySets->resize(sampledInputSize); 910 sampledSearchKeyVectors->resize(sampledInputSize); 911 const int readForwordLength = static_cast<int>( 912 hypotf(proximityInfo->getKeyboardWidth(), proximityInfo->getKeyboardHeight()) 913 * ProximityInfoParams::SEARCH_KEY_RADIUS_RATIO); 914 for (int i = 0; i < sampledInputSize; ++i) { 915 if (i >= lastSavedInputSize) { 916 (*sampledSearchKeySets)[i].reset(); 917 } 918 for (int j = max(i, lastSavedInputSize); j < sampledInputSize; ++j) { 919 // TODO: Investigate if this is required. This may not fail. 920 if ((*sampledLengthCache)[j] - (*sampledLengthCache)[i] >= readForwordLength) { 921 break; 922 } 923 (*sampledSearchKeySets)[i] |= (*sampledNearKeySets)[j]; 924 } 925 } 926 const int keyCount = proximityInfo->getKeyCount(); 927 for (int i = 0; i < sampledInputSize; ++i) { 928 std::vector<int> *searchKeyVector = &(*sampledSearchKeyVectors)[i]; 929 searchKeyVector->clear(); 930 for (int j = 0; j < keyCount; ++j) { 931 if ((*sampledSearchKeySets)[i].test(j)) { 932 const int keyCodePoint = proximityInfo->getCodePointOf(j); 933 if (std::find(searchKeyVector->begin(), searchKeyVector->end(), keyCodePoint) 934 == searchKeyVector->end()) { 935 searchKeyVector->push_back(keyCodePoint); 936 } 937 } 938 } 939 } 940 } 941 942 // Decreases char probabilities of index0 by checking probabilities of a near point (index1) and 943 // increases char probabilities of index1 by checking probabilities of index0. 944 /* static */ bool ProximityInfoStateUtils::suppressCharProbabilities(const int mostCommonKeyWidth, 945 const int sampledInputSize, const std::vector<int> *const lengthCache, 946 const int index0, const int index1, 947 std::vector<hash_map_compat<int, float> > *charProbabilities) { 948 ASSERT(0 <= index0 && index0 < sampledInputSize); 949 ASSERT(0 <= index1 && index1 < sampledInputSize); 950 const float keyWidthFloat = static_cast<float>(mostCommonKeyWidth); 951 const float diff = fabsf(static_cast<float>((*lengthCache)[index0] - (*lengthCache)[index1])); 952 if (diff > keyWidthFloat * ProximityInfoParams::SUPPRESSION_LENGTH_WEIGHT) { 953 return false; 954 } 955 const float suppressionRate = ProximityInfoParams::MIN_SUPPRESSION_RATE 956 + diff / keyWidthFloat / ProximityInfoParams::SUPPRESSION_LENGTH_WEIGHT 957 * ProximityInfoParams::SUPPRESSION_WEIGHT; 958 for (hash_map_compat<int, float>::iterator it = (*charProbabilities)[index0].begin(); 959 it != (*charProbabilities)[index0].end(); ++it) { 960 hash_map_compat<int, float>::iterator it2 = (*charProbabilities)[index1].find(it->first); 961 if (it2 != (*charProbabilities)[index1].end() && it->second < it2->second) { 962 const float newProbability = it->second * suppressionRate; 963 const float suppression = it->second - newProbability; 964 it->second = newProbability; 965 // mCharProbabilities[index0][NOT_AN_INDEX] is the probability of skipping this point. 966 (*charProbabilities)[index0][NOT_AN_INDEX] += suppression; 967 968 // Add the probability of the same key nearby index1 969 const float probabilityGain = min(suppression 970 * ProximityInfoParams::SUPPRESSION_WEIGHT_FOR_PROBABILITY_GAIN, 971 (*charProbabilities)[index1][NOT_AN_INDEX] 972 * ProximityInfoParams::SKIP_PROBABALITY_WEIGHT_FOR_PROBABILITY_GAIN); 973 it2->second += probabilityGain; 974 (*charProbabilities)[index1][NOT_AN_INDEX] -= probabilityGain; 975 } 976 } 977 return true; 978 } 979 980 /* static */ bool ProximityInfoStateUtils::checkAndReturnIsContinuousSuggestionPossible( 981 const int inputSize, const int *const xCoordinates, const int *const yCoordinates, 982 const int *const times, const int sampledInputSize, 983 const std::vector<int> *const sampledInputXs, const std::vector<int> *const sampledInputYs, 984 const std::vector<int> *const sampledTimes, 985 const std::vector<int> *const sampledInputIndices) { 986 if (inputSize < sampledInputSize) { 987 return false; 988 } 989 for (int i = 0; i < sampledInputSize; ++i) { 990 const int index = (*sampledInputIndices)[i]; 991 if (index >= inputSize) { 992 return false; 993 } 994 if (xCoordinates[index] != (*sampledInputXs)[i] 995 || yCoordinates[index] != (*sampledInputYs)[i]) { 996 return false; 997 } 998 if (!times) { 999 continue; 1000 } 1001 if (times[index] != (*sampledTimes)[i]) { 1002 return false; 1003 } 1004 } 1005 return true; 1006 } 1007 1008 // Get a word that is detected by tracing the most probable string into codePointBuf and 1009 // returns probability of generating the word. 1010 /* static */ float ProximityInfoStateUtils::getMostProbableString( 1011 const ProximityInfo *const proximityInfo, const int sampledInputSize, 1012 const std::vector<hash_map_compat<int, float> > *const charProbabilities, 1013 int *const codePointBuf) { 1014 ASSERT(sampledInputSize >= 0); 1015 memset(codePointBuf, 0, sizeof(codePointBuf[0]) * MAX_WORD_LENGTH); 1016 int index = 0; 1017 float sumLogProbability = 0.0f; 1018 // TODO: Current implementation is greedy algorithm. DP would be efficient for many cases. 1019 for (int i = 0; i < sampledInputSize && index < MAX_WORD_LENGTH - 1; ++i) { 1020 float minLogProbability = static_cast<float>(MAX_VALUE_FOR_WEIGHTING); 1021 int character = NOT_AN_INDEX; 1022 for (hash_map_compat<int, float>::const_iterator it = (*charProbabilities)[i].begin(); 1023 it != (*charProbabilities)[i].end(); ++it) { 1024 const float logProbability = (it->first != NOT_AN_INDEX) 1025 ? it->second + ProximityInfoParams::DEMOTION_LOG_PROBABILITY : it->second; 1026 if (logProbability < minLogProbability) { 1027 minLogProbability = logProbability; 1028 character = it->first; 1029 } 1030 } 1031 if (character != NOT_AN_INDEX) { 1032 codePointBuf[index] = proximityInfo->getCodePointOf(character); 1033 index++; 1034 } 1035 sumLogProbability += minLogProbability; 1036 } 1037 codePointBuf[index] = '\0'; 1038 return sumLogProbability; 1039 } 1040 1041 /* static */ void ProximityInfoStateUtils::dump(const bool isGeometric, const int inputSize, 1042 const int *const inputXCoordinates, const int *const inputYCoordinates, 1043 const int sampledInputSize, const std::vector<int> *const sampledInputXs, 1044 const std::vector<int> *const sampledInputYs, 1045 const std::vector<int> *const sampledTimes, 1046 const std::vector<float> *const sampledSpeedRates, 1047 const std::vector<int> *const sampledBeelineSpeedPercentiles) { 1048 if (DEBUG_GEO_FULL) { 1049 for (int i = 0; i < sampledInputSize; ++i) { 1050 AKLOGI("Sampled(%d): x = %d, y = %d, time = %d", i, (*sampledInputXs)[i], 1051 (*sampledInputYs)[i], sampledTimes ? (*sampledTimes)[i] : -1); 1052 } 1053 } 1054 1055 std::stringstream originalX, originalY, sampledX, sampledY; 1056 for (int i = 0; i < inputSize; ++i) { 1057 originalX << inputXCoordinates[i]; 1058 originalY << inputYCoordinates[i]; 1059 if (i != inputSize - 1) { 1060 originalX << ";"; 1061 originalY << ";"; 1062 } 1063 } 1064 AKLOGI("===== sampled points ====="); 1065 for (int i = 0; i < sampledInputSize; ++i) { 1066 if (isGeometric) { 1067 AKLOGI("%d: x = %d, y = %d, time = %d, relative speed = %.4f, beeline speed = %d", 1068 i, (*sampledInputXs)[i], (*sampledInputYs)[i], (*sampledTimes)[i], 1069 (*sampledSpeedRates)[i], (*sampledBeelineSpeedPercentiles)[i]); 1070 } 1071 sampledX << (*sampledInputXs)[i]; 1072 sampledY << (*sampledInputYs)[i]; 1073 if (i != sampledInputSize - 1) { 1074 sampledX << ";"; 1075 sampledY << ";"; 1076 } 1077 } 1078 AKLOGI("original points:\n%s, %s,\nsampled points:\n%s, %s,\n", 1079 originalX.str().c_str(), originalY.str().c_str(), sampledX.str().c_str(), 1080 sampledY.str().c_str()); 1081 } 1082 } // namespace latinime 1083