Нечеткие совпадающие числа

Question

Я работал с Double Metaphone и Caverphone2 для сравнения строк, и они хорошо работают с такими вещами, как имена, адреса и т. Д. (Caverphone2 работает лучше всего для меня).Тем не менее, они дают слишком много ложных срабатываний, когда вы получаете числовые значения, такие как номера телефонов, IP-адреса, номера кредитных карт и т. Д.и Verhoeff алгоритмы, и они описывают в основном то, что я хочу, но не совсем.Они кажутся хорошими в проверке, но, похоже, не созданы для нечеткого сопоставления.Есть ли что-нибудь, что ведет себя как Лун и Верхофф, который может обнаруживать однозначные ошибки и ошибки транспонирования, включающие две соседние цифры, для целей кодирования и сравнения, аналогично алгоритмам нечеткой строки?число, затем сравните его с 100 000 других чисел, чтобы найти близко совпадающие совпадения.Таким образом, что-то вроде 7041234 будет соответствовать 7041324 в качестве возможной ошибки транскрипции, а что-то вроде 4213704 - нет.

Answer 1

Левенштейн и friends могут быть полезны для определения расстояния между определенными строками или числами. Однако, если вы хотите создать корректор орфографии, вы не хотите проходить всю базу данных слов при каждом запросе.

Питер Норвиг написал очень хорошую статью о простом корректоре орфографии "нечеткого соответствия", основанном на некоторых технологиях, лежащих в основе предложений по написанию в Google.

Если в вашем словаре есть N статей, а среднее слово имеет длину L, то подход "грубой силы Левенштейна" займет время O(N*L^3). Вместо этого подход Питера Норвига генерирует все слова на определенном расстоянии редактирования от ввода и ищет их в словаре. Следовательно, он достигает O(L^k), где k - самое дальнее из рассмотренных расстояний редактирования.