1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
|
/*
* Copyright (C) 2013 The Android Open Source Project
*
* Licensed under the Apache License, Version 2.0 (the "License");
* you may not use this file except in compliance with the License.
* You may obtain a copy of the License at
*
* http://www.apache.org/licenses/LICENSE-2.0
*
* Unless required by applicable law or agreed to in writing, software
* distributed under the License is distributed on an "AS IS" BASIS,
* WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
* See the License for the specific language governing permissions and
* limitations under the License.
*/
#ifndef LATINIME_EDIT_DISTANCE_H
#define LATINIME_EDIT_DISTANCE_H
#include "defines.h"
#include "suggest/policyimpl/utils/edit_distance_policy.h"
namespace latinime {
class EditDistance {
public:
// CAVEAT: There may be performance penalty if you need the edit distance as an integer value.
AK_FORCE_INLINE static float getEditDistance(const EditDistancePolicy *const policy) {
const int beforeLength = policy->getString0Length();
const int afterLength = policy->getString1Length();
float dp[(beforeLength + 1) * (afterLength + 1)];
for (int i = 0; i <= beforeLength; ++i) {
dp[(afterLength + 1) * i] = i * policy->getInsertionCost(i - 1, -1);
}
for (int i = 0; i <= afterLength; ++i) {
dp[i] = i * policy->getDeletionCost(-1, i - 1);
}
for (int i = 0; i < beforeLength; ++i) {
for (int j = 0; j < afterLength; ++j) {
dp[(afterLength + 1) * (i + 1) + (j + 1)] = min(
dp[(afterLength + 1) * i + (j + 1)] + policy->getInsertionCost(i, j),
min(dp[(afterLength + 1) * (i + 1) + j] + policy->getDeletionCost(i, j),
dp[(afterLength + 1) * i + j]
+ policy->getSubstitutionCost(i, j)));
if (policy->allowTransposition(i, j)) {
dp[(afterLength + 1) * (i + 1) + (j + 1)] = min(
dp[(afterLength + 1) * (i + 1) + (j + 1)],
dp[(afterLength + 1) * (i - 1) + (j - 1)]
+ policy->getTranspositionCost(i, j));
}
}
}
if (DEBUG_EDIT_DISTANCE) {
AKLOGI("IN = %d, OUT = %d", beforeLength, afterLength);
for (int i = 0; i < beforeLength + 1; ++i) {
for (int j = 0; j < afterLength + 1; ++j) {
AKLOGI("EDIT[%d][%d], %f", i, j, dp[(afterLength + 1) * i + j]);
}
}
}
return dp[(beforeLength + 1) * (afterLength + 1) - 1];
}
private:
DISALLOW_IMPLICIT_CONSTRUCTORS(EditDistance);
};
} // namespace latinime
#endif // LATINIME_EDIT_DISTANCE_H
|
