Я выполняю много задач по написанию сценариев в своей сфере деятельности.

Я начал с Python, затем перешел на C # (не идеальный язык для одноразового кода), а несколько месяцев назад окончательно остановился на Go. Go - отличный язык для реализации многих сложных алгоритмов (из-за простоты реализации и времени компиляции, на мой взгляд.), и я часто использую Алгоритм расстояния Левенштейна ( LDA ).

Расстояние Левенштейна мера несходства двух струн. С человеческой точки зрения это означает, что это вычисление того, сколько изменений необходимо сделать между двумя частями текста, чтобы сделать их одинаковыми.

В качестве примера возьмем слова «котенок» и «сидящий». Если я хочу определить, насколько разные эти два слова, я мог бы взять слово и определить, сколько изменений необходимо внести, чтобы сделать эти слова идентичными, как показано ниже:

K I T T E N
S I T T I N G

Чтобы сделать их идентичными, мне пришлось бы изменить первый символ (KS), затем следующие три символа остались такими же (ITT), затем изменился пятый символ ( EI), шестой остается прежним (N), а седьмой нужно изменить или, скорее, добавить (null-G).

Этот алгоритм присутствует почти во всех проверках орфографии, которые я когда-либо наблюдал. Я также часто использую его для больших объемов текста, и он по-прежнему остается самым быстрым алгоритмом сравнения строк, с которым я сталкивался, а не прямым сравнением между ними. Ниже представлена ​​реализация в Go, которую я использую;

Итак, если мы возьмем для примера слова «котенок» и «сидящий»;

fmt.Println(computeLevenshteinValue("kitten", "sitting"))
output = 3
fmt.Println(computeLevenshteinPercentage("kitten", "sitting"))
output = 57.14

Таким образом, мы можем сделать вывод, что необходимо 3 изменения, чтобы слова стали одинаковыми, и слова идентичны на 57%.

Этот алгоритм, когда он реализован в Go, будет иметь временную сложность O (nm), где m и n - длины a и b, а сложность пространства составляет n + 1 целых чисел плюс некоторое постоянное пространство (т. е. O (n)).

Пакет можно найти на моем Github.