Расстояние Левенштейна - что это и как использовать.
Расстояние Левенштейна между двумя строками - это минимальное количество операций вставки одного символа, удаления одного символа и замены одного символа на другой, необходимых для превращения одной строки в другую [Википедия]. Например, есть строки:
"text" и "text!"
Для того чтобы первую строку превратить во вторую, нужно добавить к ней символ "!", и наоборот - для того чтобы превратить вторую в первую - нужно удалить из нее восклицательный знак. Иными словами, нужно выполнить одну операцию. Это значение и называют расстоянием Левенштейна. Зачем используется такое понятие? Расстояние Левенштейна имеет множество практических применений. Например - различные утилиты, которые предназначены для мержа файлов исходного кода, утилита для сравнения текстов diff в Linux, нестрогое сравнение текстов - когда нужно "примерно" сравнить две порции текстовых данных, и прочее.
Готовые реализации.
В качестве примера и старта, для практического использования, приведу две библиотеки, с помощью которых можно рассчитать значения расстояния Левинштейна для двух текстов (строк). Первая библиотека, которая предназначена для сравнения текстовых данных, и кстати пригодна не только для вышеуказанной цели, это - google-diff-match-patch. Отличительной особенностью этой библиотеки является то, что она реализована на разных языках, имея при этом единообразный API. Среди языков, которые поддерживаются - Java, JavaScript, Python, C++, CSharp, Lua, Objective-C, Dart.
Вот пример метода, который возвращает расстояние Левенштейна, используя google-diff-match-patch (пример на Java):
public int getLevinshteinDistance(final String string1,
final String string2) {
diff_match_patch dmp = new diff_match_patch();
LinkedList<diff_match_patch.Diff> diffs =
dmp.diff_main(string1, string2);
return dmp.diff_levenshtein(diffs);
}
Вторая библиотека подойдет если вы испльзуете Java. Это Apache Commons. Здесь все еще проще:
StringUtils.getLevenshteinDistance(string1, string2);
Если ваш проект собирается с помощью Maven, для включения необходимой зависимости, добавьте в pom.xml:
<groupId>org.apache.commons</groupId> <artifactId>commons-lang3</artifactId> <version>3.3.2</version>
Теги: algorithms academic programming
comments powered by Disqus