Calculate Levenshtein edit distance between two strings. Args: s1: First string s2: Second string Returns: Edit distance (number of edits needed to transform s1 into s2)
(s1: str, s2: str)
| 60 | |
| 61 | |
| 62 | def _edit_distance(s1: str, s2: str) -> int: |
| 63 | """Calculate Levenshtein edit distance between two strings. |
| 64 | |
| 65 | Args: |
| 66 | s1: First string |
| 67 | s2: Second string |
| 68 | |
| 69 | Returns: |
| 70 | Edit distance (number of edits needed to transform s1 into s2) |
| 71 | """ |
| 72 | if len(s1) < len(s2): |
| 73 | return _edit_distance(s2, s1) |
| 74 | |
| 75 | if len(s2) == 0: |
| 76 | return len(s1) |
| 77 | |
| 78 | # Use two rows for space efficiency |
| 79 | previous_row = list(range(len(s2) + 1)) |
| 80 | current_row = [0] * (len(s2) + 1) |
| 81 | |
| 82 | for i, c1 in enumerate(s1): |
| 83 | current_row[0] = i + 1 |
| 84 | for j, c2 in enumerate(s2): |
| 85 | # Cost of insertion, deletion, substitution |
| 86 | insertions = previous_row[j + 1] + 1 |
| 87 | deletions = current_row[j] + 1 |
| 88 | substitutions = previous_row[j] + (0 if c1 == c2 else 1) |
| 89 | current_row[j + 1] = min(insertions, deletions, substitutions) |
| 90 | previous_row, current_row = current_row, previous_row |
| 91 | |
| 92 | return previous_row[-1] |
| 93 | |
| 94 | |
| 95 | def _fuzzy_score(query: str, target: str) -> tuple[float, int]: |