Лучшая практика для определения вероятности совпадения двух строк

Question

Мне нужно написать код, чтобы определить, совпадают ли 2 строки, когда одна из строк может содержать небольшое отклонение от второй строки, например, "Южная Африка" v "Южная Африка" или "Англия" v "Энлганд".В настоящий момент я рассматриваю следующий подход

1. Определить процент символов в строке 1, которые совпадают с символами в строке 2
2. Определить истинную вероятность совпадения путем объединения результата1 со сравнением длины 2 строк, например, хотя все символы в «SA» находятся в «Южной Африке», это не очень вероятно совпадение, так как «SA» можно найти в ряде других названий стран, например:хорошо.

Буду признателен за то, что в настоящее время рекомендуется выполнять такие сопоставления строк.

Answer 1

Вы можете посмотреть на Расстояние Левенштейна . Это расстояние между двумя строками. Те же строки имеют расстояние, равное 0. Строки, такие как kitten и sitten , имеют расстояние, равное 1, и так далее. Расстояние измеряется минимальным количеством простых операций, которые преобразуют одну строку в другую.

Более подробная информация и алгоритм в псевдокоде приведены в ссылке.

Я также помню, что эта тема упоминалась в Драгоценные камни программирования игры: том 6 : статья 1.6 Алгоритм сопоставления ближайших строк

Answer 2

Чтобы идеальное совпадение нечетких строк, важно знать о контексте строк. Когда речь идет о небольших опечатках, Левенштейн может быть достаточно хорош. Когда речь идет о неслышном звуке, вы можете использовать фонетический алгоритм, такой как soundex или metaphone. В большинстве случаев вам нужна комбинация следующих алгоритмов и некоторые более конкретные написанные вручную вещи.

• Иглман-Вунш
• Soundex
• Metaphone
• Расстояние Левенштейна
• Растровое изображение
• Расстояние Хэмминга

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

Answer 3

Не изобретай велосипед. В Википедии есть алгоритм Левенштейна, в котором есть метрики того, что вы хотите сделать.

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

Есть также Soundex, но это может быть слишком упрощенно для ваших требований.

Answer 4

Я нашел реализацию Objective-C алгоритма расстояния Левенштейна здесь . Это прекрасно работает для меня.

Answer 5

Использование Soundex хорошо сработало для меня: С небольшим или двумя изменениями в реализации сопоставление Soundex может проверить кросс-языки , если две строки на разных языках звучат одинаково ..

Реализация Objective-C Soundex: http://www.cocoadev.com/index.pl?NSStringSoundex