test_edit_distance_op.py 3.5 KB
Newer Older
D
dzhwinter 已提交
1
#   Copyright (c) 2018 PaddlePaddle Authors. All Rights Reserve.
F
fengjiayi 已提交
2
#
D
dzhwinter 已提交
3 4 5
# 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
F
fengjiayi 已提交
6
#
D
dzhwinter 已提交
7
#     http://www.apache.org/licenses/LICENSE-2.0
F
fengjiayi 已提交
8
#
D
dzhwinter 已提交
9 10 11 12 13 14
# 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.

Y
Yibing Liu 已提交
15 16 17 18 19 20 21 22
import unittest
import numpy as np
from op_test import OpTest


def Levenshtein(hyp, ref):
    """ Compute the Levenshtein distance between two strings.

23
    :param hyp: hypothesis string in index
Y
Yibing Liu 已提交
24
    :type hyp: list
25
    :param ref: reference string in index
Y
Yibing Liu 已提交
26 27 28 29 30 31 32 33 34
    :type ref: list
    """
    m = len(hyp)
    n = len(ref)
    if m == 0:
        return n
    if n == 0:
        return m

35
    dist = np.zeros((m + 1, n + 1)).astype("float32")
Y
Yibing Liu 已提交
36 37 38 39 40 41 42 43 44 45 46 47 48 49 50
    for i in range(0, m + 1):
        dist[i][0] = i
    for j in range(0, n + 1):
        dist[0][j] = j

    for i in range(1, m + 1):
        for j in range(1, n + 1):
            cost = 0 if hyp[i - 1] == ref[j - 1] else 1
            deletion = dist[i - 1][j] + 1
            insertion = dist[i][j - 1] + 1
            substitution = dist[i - 1][j - 1] + cost
            dist[i][j] = min(deletion, insertion, substitution)
    return dist[m][n]


51
class TestEditDistanceOp(OpTest):
52 53 54
    def setUp(self):
        self.op_type = "edit_distance"
        normalized = False
55 56
        x1 = np.array([[0, 12, 3, 5, 8, 2]]).astype("int64")
        x2 = np.array([[0, 12, 4, 7, 8]]).astype("int64")
57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78
        x1 = np.transpose(x1)
        x2 = np.transpose(x2)
        x1_lod = [0, 1, 5]
        x2_lod = [0, 3, 4]

        num_strs = len(x1_lod) - 1
        distance = np.zeros((num_strs, 1)).astype("float32")
        for i in range(0, num_strs):
            distance[i] = Levenshtein(
                hyp=x1[x1_lod[i]:x1_lod[i + 1]],
                ref=x2[x2_lod[i]:x2_lod[i + 1]])
            if normalized is True:
                len_ref = x2_lod[i + 1] - x2_lod[i]
                distance[i] = distance[i] / len_ref
        self.attrs = {'normalized': normalized}
        self.inputs = {'Hyps': (x1, [x1_lod]), 'Refs': (x2, [x2_lod])}
        self.outputs = {'Out': distance}

    def test_check_output(self):
        self.check_output()


79
class TestEditDistanceOpNormalized(OpTest):
Y
Yibing Liu 已提交
80
    def setUp(self):
81
        self.op_type = "edit_distance"
Y
Yibing Liu 已提交
82
        normalized = True
83 84
        x1 = np.array([[0, 10, 3, 6, 5, 8, 2]]).astype("int64")
        x2 = np.array([[0, 10, 4, 6, 7, 8]]).astype("int64")
85 86 87 88
        x1 = np.transpose(x1)
        x2 = np.transpose(x2)
        x1_lod = [0, 1, 3, 6]
        x2_lod = [0, 2, 3, 5]
Y
Yibing Liu 已提交
89

90 91 92 93 94 95 96 97 98
        num_strs = len(x1_lod) - 1
        distance = np.zeros((num_strs, 1)).astype("float32")
        for i in range(0, num_strs):
            distance[i] = Levenshtein(
                hyp=x1[x1_lod[i]:x1_lod[i + 1]],
                ref=x2[x2_lod[i]:x2_lod[i + 1]])
            if normalized is True:
                len_ref = x2_lod[i + 1] - x2_lod[i]
                distance[i] = distance[i] / len_ref
Y
Yibing Liu 已提交
99
        self.attrs = {'normalized': normalized}
100
        self.inputs = {'Hyps': (x1, [x1_lod]), 'Refs': (x2, [x2_lod])}
Y
Yibing Liu 已提交
101 102 103 104 105 106 107 108
        self.outputs = {'Out': distance}

    def test_check_output(self):
        self.check_output()


if __name__ == '__main__':
    unittest.main()