Fuzzy Matching Numbers

Question

Pracuję z Double Metaphone i Caverphone2 dla porównania String i działają dobrze na takich rzeczach, jak nazwiska, adresy, itp. (Caverphone2 działa najlepiej dla mnie). Jednak produkują zbyt wiele fałszywych alarmów, kiedy dojdziesz do wartości numerycznych, takich jak numery telefonów, adresy IP, numery kart kredytowych itp

Więc szukałem na algorytmach Luhn i Verhoeff i opisują zasadniczo co Chcę, ale nie całkiem. Wydaje się, że są dobre w sprawdzaniu poprawności, ale nie wydają się być budowane dla dopasowania rozmytego. Czy istnieje coś, co zachowuje się jak Luhn i Verhoeff, które mogą wykrywać jednocyfrowe błędy i transpozycję z udziałem dwóch sąsiednich cyfr, do celów kodowania i porównywania podobnych do algorytmów rozmytych ciągów znaków?

Chciałbym zakodować numer, a następnie porównać go z 100 000 innych liczb, aby znaleźć dokładnie identyczne dopasowania. Tak więc coś w rodzaju 7041234 byłoby zgodne z 7041324 jako możliwym błędem transkrypcji, ale coś takiego jak 4213704 nie byłoby.

Answer 1

Levenshteinandfriends może być dobre dla znalezienia odległości między określonymi ciągami lub liczbami. Jednakże, jeśli chcesz zbudować korektor pisowni, nie chcesz przechodzić przez całą bazę danych słów przy każdym zapytaniu.

Peter Norvig napisał a very nice article na prostym "poprawnym dopasowaniu" w pisowni korektora opartym na niektórych technologiach sugerujących pisanie google.

Jeśli Twój słownik ma pozycje N, a średnie słowo ma długość L, podejście "Brute force Levenshtein" zajmie trochę czasu O(N*L^3). Podejście Petera Norviga zamiast tego generuje wszystkie słowa w pewnej odległości edycyjnej od danych wejściowych i wyszukuje je w słowniku. Stąd osiąga on wartość O(L^k), gdzie k jest najdalszą odległością do edycji.