native/jni/src/suggest/policyimpl/utils/edit_distance.h

/*
 * 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