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