퍼지 매칭 번호

Question

저는 Double Metaphone과 Caverphone2를 String 비교를 위해 사용해 왔으며 이름, 주소 등을 잘 처리합니다 (Caverphone2가 가장 잘 작동합니다). 그러나 전화 번호, IP 주소, 신용 카드 번호 등과 같이 숫자 값에 도달하면 오탐 (false positive)이 너무 많이 발생합니다.

따라서 Luhn 및 Verhoeff 알고리즘을 살펴본 결과 본질적으로 나는 원하지만 아주. 그들은 유효성 검사를 잘하는 것처럼 보이지만 퍼지 매칭을 위해 제작 된 것 같지 않습니다. 퍼지 문자열 알고리즘과 유사한 인코딩 및 비교 목적으로 한 자리 숫자 오류 및 두 자리 숫자와 관련된 전위 오류를 감지 할 수있는 Luhn 및 Verhoeff와 같은 동작이 있습니까?

숫자를 인코딩 한 다음 100,000 개의 다른 숫자와 비교하여 거의 일치하는 것을 찾으려합니다. 그래서 7041234와 같은 것이 전사 오류로 7041324와 일치하지만 4213704와 같은 것은 그렇지 않습니다.

Answer 1

Levenshteinandfriends은 특정 문자열이나 숫자 사이의 거리를 찾는 데 유용 할 수 있습니다. 그러나 맞춤법 교정기를 작성하려면 모든 검색어에서 전체 단어 데이터베이스를 실행하고 싶지는 않습니다.

Peter Norvig는 Google 맞춤법 추천에 뒤 따르는 기술 중 일부를 기반으로하는 간단한 "퍼지 매칭"맞춤법 보정 도구에 a very nice article을 작성했습니다.

사전에 N 개의 항목이 있고 평균 단어 길이가 L 인 경우 "Brute Force Levenshtein"방식은 O(N*L^3) 시간이 걸립니다. Peter Norvig의 접근법은 대신 입력으로부터 특정 편집 거리 내의 모든 단어를 생성하고 사전에서 찾아 봅니다. 따라서 O(L^k)을 얻습니다. 여기서 k는 고려 된 가장 먼 편집 거리입니다.