33 lines
1.1 KiB
Python
33 lines
1.1 KiB
Python
"""Small, bounded edit-distance primitive shared by lexical checks."""
|
|
|
|
from __future__ import annotations
|
|
|
|
|
|
def bounded_levenshtein(left: str, right: str, max_distance: int) -> int | None:
|
|
"""Return the edit distance when it is within ``max_distance``."""
|
|
|
|
if max_distance < 0:
|
|
return None
|
|
if left == right:
|
|
return 0
|
|
if abs(len(left) - len(right)) > max_distance:
|
|
return None
|
|
if len(left) > len(right):
|
|
left, right = right, left
|
|
|
|
previous = list(range(len(left) + 1))
|
|
for row_index, right_char in enumerate(right, start=1):
|
|
current = [row_index]
|
|
row_minimum = current[0]
|
|
for column_index, left_char in enumerate(left, start=1):
|
|
value = min(
|
|
current[column_index - 1] + 1,
|
|
previous[column_index] + 1,
|
|
previous[column_index - 1] + (left_char != right_char),
|
|
)
|
|
current.append(value)
|
|
row_minimum = min(row_minimum, value)
|
|
if row_minimum > max_distance:
|
|
return None
|
|
previous = current
|
|
return previous[-1] if previous[-1] <= max_distance else None
|