Home | History | Annotate | Download | only in utils 
      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 <algorithm>
     21 
     22 #include "defines.h"
     23 #include "suggest/policyimpl/utils/edit_distance_policy.h"
     24 
     25 namespace latinime {
     26 
     27 class EditDistance {
     28  public:
     29     // CAVEAT: There may be performance penalty if you need the edit distance as an integer value.
     30     AK_FORCE_INLINE static float getEditDistance(const EditDistancePolicy *const policy) {
     31         const int beforeLength = policy->getString0Length();
     32         const int afterLength = policy->getString1Length();
     33         float dp[(beforeLength + 1) * (afterLength + 1)];
     34         for (int i = 0; i <= beforeLength; ++i) {
     35             dp[(afterLength + 1) * i] = i * policy->getInsertionCost(i - 1, -1);
     36         }
     37         for (int i = 0; i <= afterLength; ++i) {
     38             dp[i] = i * policy->getDeletionCost(-1, i - 1);
     39         }
     40 
     41         for (int i = 0; i < beforeLength; ++i) {
     42             for (int j = 0; j < afterLength; ++j) {
     43                 dp[(afterLength + 1) * (i + 1) + (j + 1)] = std::min(
     44                         dp[(afterLength + 1) * i + (j + 1)] + policy->getInsertionCost(i, j),
     45                         std::min(
     46                                 dp[(afterLength + 1) * (i + 1) + j] + policy->getDeletionCost(i, j),
     47                                 dp[(afterLength + 1) * i + j] + policy->getSubstitutionCost(i, j)));
     48                 if (policy->allowTransposition(i, j)) {
     49                     dp[(afterLength + 1) * (i + 1) + (j + 1)] = std::min(
     50                             dp[(afterLength + 1) * (i + 1) + (j + 1)],
     51                             dp[(afterLength + 1) * (i - 1) + (j - 1)]
     52                                     + policy->getTranspositionCost(i, j));
     53                 }
     54             }
     55         }
     56         if (DEBUG_EDIT_DISTANCE) {
     57             AKLOGI("IN = %d, OUT = %d", beforeLength, afterLength);
     58             for (int i = 0; i < beforeLength + 1; ++i) {
     59                 for (int j = 0; j < afterLength + 1; ++j) {
     60                     AKLOGI("EDIT[%d][%d], %f", i, j, dp[(afterLength + 1) * i + j]);
     61                 }
     62             }
     63         }
     64         return dp[(beforeLength + 1) * (afterLength + 1) - 1];
     65     }
     66 
     67     AK_FORCE_INLINE static void dumpEditDistance10ForDebug(const float *const editDistanceTable,
     68             const int editDistanceTableWidth, const int outputLength) {
     69         if (DEBUG_DICT) {
     70             AKLOGI("EditDistanceTable");
     71             for (int i = 0; i <= 10; ++i) {
     72                 float c[11];
     73                 for (int j = 0; j <= 10; ++j) {
     74                     if (j < editDistanceTableWidth + 1 && i < outputLength + 1) {
     75                         c[j] = (editDistanceTable + i * (editDistanceTableWidth + 1))[j];
     76                     } else {
     77                         c[j] = -1.0f;
     78                     }
     79                 }
     80                 AKLOGI("[ %f, %f, %f, %f, %f, %f, %f, %f, %f, %f, %f ]",
     81                         c[0], c[1], c[2], c[3], c[4], c[5], c[6], c[7], c[8], c[9], c[10]);
     82                 (void)c; // To suppress compiler warning
     83             }
     84         }
     85     }
     86 
     87  private:
     88     DISALLOW_IMPLICIT_CONSTRUCTORS(EditDistance);
     89 };
     90 } // namespace latinime
     91 
     92 #endif  // LATINIME_EDIT_DISTANCE_H
     93