Coverage for cpyquickhelper/algorithms/edit_distance.py: 100%
24 statements
« prev ^ index » next coverage.py v7.2.7, created at 2023-06-30 05:30 +0200
« prev ^ index » next coverage.py v7.2.7, created at 2023-06-30 05:30 +0200
1"""
2@file
3@brief Edit distance.
4"""
5import numpy
6from .edit_distance_c import edit_distance # pylint: disable=E0611
9def edit_distance_string(s1, s2, cmp_cost=1.):
10 """
11 Computes the edit distance between strings *s1* and *s2*.
13 :param s1: first string
14 :param s2: second string
15 :return: dist, list of tuples of aligned characters
16 """
17 n1 = len(s1) + 1
18 n2 = len(s2) + 1
19 dist = numpy.empty((n1, n2), dtype=numpy.float64)
20 pred = numpy.empty(dist.shape, dtype=numpy.int32)
21 seq1 = numpy.array(list(map(ord, s1)), dtype=numpy.int32)
22 seq2 = numpy.array(list(map(ord, s2)), dtype=numpy.int32)
23 d = edit_distance(seq1, seq2, cmp_cost, dist, pred)
25 equals = []
26 i, j = len(s1), len(s2)
27 p = pred[i, j]
28 while p != -1:
29 if p == 3:
30 equals.append((i - 1, j - 1))
31 i -= 1
32 j -= 1
33 elif p == 2:
34 j -= 1
35 elif p == 1:
36 i -= 1
37 else:
38 raise RuntimeError( # pragma: no cover
39 "Unexpected value for p=%d at position=%r." % (p, (i, j)))
40 p = pred[i, j]
41 return d, list(reversed(equals))