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
25namespace latinime {
26
27class 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