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 #ifndef LATINIME_EDIT_DISTANCE_H 18 #define LATINIME_EDIT_DISTANCE_H 19 20 #include "defines.h" 21 #include "suggest/policyimpl/utils/edit_distance_policy.h" 22 23 namespace latinime { 24 25 class EditDistance { 26 public: 27 // CAVEAT: There may be performance penalty if you need the edit distance as an integer value. getEditDistance(const EditDistancePolicy * const policy)28 AK_FORCE_INLINE static float getEditDistance(const EditDistancePolicy *const policy) { 29 const int beforeLength = policy->getString0Length(); 30 const int afterLength = policy->getString1Length(); 31 float dp[(beforeLength + 1) * (afterLength + 1)]; 32 for (int i = 0; i <= beforeLength; ++i) { 33 dp[(afterLength + 1) * i] = i * policy->getInsertionCost(i - 1, -1); 34 } 35 for (int i = 0; i <= afterLength; ++i) { 36 dp[i] = i * policy->getDeletionCost(-1, i - 1); 37 } 38 39 for (int i = 0; i < beforeLength; ++i) { 40 for (int j = 0; j < afterLength; ++j) { 41 dp[(afterLength + 1) * (i + 1) + (j + 1)] = min( 42 dp[(afterLength + 1) * i + (j + 1)] + policy->getInsertionCost(i, j), 43 min(dp[(afterLength + 1) * (i + 1) + j] + policy->getDeletionCost(i, j), 44 dp[(afterLength + 1) * i + j] 45 + policy->getSubstitutionCost(i, j))); 46 if (policy->allowTransposition(i, j)) { 47 dp[(afterLength + 1) * (i + 1) + (j + 1)] = min( 48 dp[(afterLength + 1) * (i + 1) + (j + 1)], 49 dp[(afterLength + 1) * (i - 1) + (j - 1)] 50 + policy->getTranspositionCost(i, j)); 51 } 52 } 53 } 54 if (DEBUG_EDIT_DISTANCE) { 55 AKLOGI("IN = %d, OUT = %d", beforeLength, afterLength); 56 for (int i = 0; i < beforeLength + 1; ++i) { 57 for (int j = 0; j < afterLength + 1; ++j) { 58 AKLOGI("EDIT[%d][%d], %f", i, j, dp[(afterLength + 1) * i + j]); 59 } 60 } 61 } 62 return dp[(beforeLength + 1) * (afterLength + 1) - 1]; 63 } 64 65 private: 66 DISALLOW_IMPLICIT_CONSTRUCTORS(EditDistance); 67 }; 68 } // namespace latinime 69 70 #endif // LATINIME_EDIT_DISTANCE_H 71