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