Расстояние Левенштейна с границей / пределом

Question

Я нашел несколько Python реализаций расстояния Левенштейна .

Мне интересно, как эти алгоритмы могут быть эффективно изменены так, чтобы они ломались, если расстояние Левенштейна больше, чем n (например, 3) вместо запуска до конца?

Так что, по сути, я не хочу, чтобы алгоритм работал слишком долго, чтобы вычислить конечное расстояние, если я просто хочу знать, больше ли расстояние чем порог или нет.

Я нашел несколько соответствующих сообщений здесь:

1. Изменение алгоритма расстояния Левенштейна, чтобы не рассчитать все расстояния
2. Предел расстояния Левенштейна
3. Наиболее эффективный способ вычисления расстояния Левенштейна
4. Алгоритм расстояния Левенштейна лучше, чем O (n * m)?

но, тем не менее, я не вижу ни одного Python кода, который бы делал то, что я описываю выше (что более или менее то, что описывают и эти посты).

PS: Решение n, предоставленный @amirouche ниже, основан на самой быстрой реализации, которую я протестировал с некоторым тестированием (отсюда: https://en.wikibooks.org/wiki/Algorithm_Implementation/Strings/Levenshtein_distance#Python, { ссылка }), и его ограниченная версия является самой быстрой в своем роде из моих тестов (не исключая, что могут быть и более быстрые).

Answer 1

Как описано в Предел расстояния Левенштейна , вы можете добавить тест к строке, которая вычисляется для раннего возврата:

def levenshtein(s1, s2, maximum):
    if len(s1) > len(s2):
        s1, s2 = s2, s1

    distances = range(len(s1) + 1)
    for i2, c2 in enumerate(s2):
        distances_ = [i2+1]
        for i1, c1 in enumerate(s1):
            if c1 == c2:
                distances_.append(distances[i1])
            else:
                distances_.append(1 + min((distances[i1], distances[i1 + 1], distances_[-1])))
        if all((x >= maximum for x in distances_)):
            return False
        distances = distances_
    return distances[-1]