Coverage for cpyquickhelper/algorithms/edit_distance.py: 100%

1""" 

2@file 

3@brief Edit distance. 

4""" 

5import numpy 

6from .edit_distance_c import edit_distance # pylint: disable=E0611 

7 

8 

9def edit_distance_string(s1, s2, cmp_cost=1.): 

10 """ 

11 Computes the edit distance between strings *s1* and *s2*. 

12 

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) 

24 

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))