Лучший способ сравнения строк для строк одинаковой длины?

Question

Мне нужно реализовать алгоритм сопоставления строк, чтобы определить, какие строки наиболее точно соответствуют. Я вижу, что расстояние Хэмминга является хорошим алгоритмом сопоставления, когда эта фиксированная длина достижима.

Есть ли какое-то преимущество в качестве соответствия, если бы вместо этого я использовал формулу расстояния Левенштейна? Я знаю, что этот метод менее эффективен, учитывая, что он учитывает строки переменной длины, но здесь меня действительно интересует качество совпадений. Кроме того, есть ли лучшие алгоритмы, которые я могу рассмотреть? Я работаю на Java, если это что-то меняет.

http://en.wikipedia.org/wiki/Levenshtein_distance

http://en.wikipedia.org/wiki/Hamming_distance

Большое спасибо

Answer 1

Рассмотрим строки: "abcdefg" и "bcdefgh".

Расстояние Левенштейна равно 2. Расстояние Хэмминга (работает с символами, а не с битами) равно 7.

Так что действительно зависит, хотите ли вы считать эти строки похожими или нет. Расстояние Хэмминга имеет свои соответствующие применения, но "будут ли эти строки похожи на человека?" не один из них.

Answer 2

Вас может заинтересовать алгоритм Bitap.

алгоритм bitap (также известный как сдвиг или сдвиг и или Алгоритм Баеза-Йейтса-Гонне) алгоритм поиска нечеткой строки. Алгоритм сообщает, является ли данный текст содержит подстроку, которая «примерно равно» данному шаблон, где приблизительное равенство определяется с точки зрения Левенштейна расстояние - если подстрока и шаблон находятся в пределах заданного расстояния к друг от друга, то алгоритм считает их равными. Алгоритм начинается с предварительного вычисления набора битовые маски, содержащие один бит для каждого элемент узора. Тогда это в состоянии сделать большую часть работы с побитовые операции, которые очень быстро.