저는 최근 데이터베이스에서 중복 고객 레코드를 확인하기위한 알고리즘을 개발하는 임무를 수행했습니다. DB를 레이아웃은 매우 간단합니다 : 수만대략적인 문자열 일치 가능성에 대한 사전 선택
약간의 배경 첫째 ... 등으로 FullName, 거리, 도시, 우편 번호, 전화 번호, 같은 필드 행의 수천 :
좀 광범위한 연구에했을 알고리즘을 사용하고 있으며 모든 필드가 모든 상황에서 모두 똑같이 잘 수행되는 것은 아니기 때문에 각 필드의 알고리즘이 다른 특정 금액 인 으로 계량되어야한다고 결정했습니다. 예를 들어 LastName의 가중치는 0.50입니다. 내가 사용하는 알고리즘을 선택할 평가하고 그들이 얼마나 최종 결정에 무게를 달 때 :
팩터 0.25 : JaroWinkler
팩터 0.60 : 코사인 2 그램 유사성
팩터 0.15 : DamerauLevenshtein
이
모든 것이 잘 작동, 약간의 튜닝을하면 약간의 오류로 확실성을 감지 할 수 있습니다. 지금까지 너무 좋아. 그러나, 당신이 상상할 수있는 것처럼, O (n^2)의 실행 시간 - 또는 실제로 E 형 i = 0에서 i = n -은 수만 개의 레코드를 다룰 때 그다지 효과적이지 않습니다. 속도, 멀티 쓰레딩 등을위한 컴파일러 최적화를 적극적으로 최적화하는 것은 실제 문제가 복잡하기 때문에 뭉치 일뿐입니다.
본질적으로, 나는 잠재적 인 일치를 사전 필터링하는 방법을 찾고 있으며, 지금이 연구에 3 일을했다. R-Trees, R * -Trees, KD-Trees, Eucledian vectors, minhashing 등에 대한 유용한 정보를 발견했습니다. 그러나이 모든 것들에 관한 대부분의 정보는 오히려 매우 학술적입니다. 내가 찾은 가장 중요한 자원은, "광업 대규모 데이터 세트"내 실제 질문에 이제 제 3 장
했다 : 나는이 모든 정보를 읽은
,하지만 난 그것을 넣어하는 방법을 잘 모르겠어요 모두 함께.
트리 또는 그래프 데이터 구조에서 일종의 인덱싱을 생각해 보았습니다. 여기서 문자열을 입력하고 "일치 확률이> 0.20"이라고 말하면됩니다. 이 알고리즘은 정말 빠릅니다. 그런 다음 잠재적 인 (> 0.20) 일치 목록을 얻으면 몇 가지 항목을 '비싼'선택 알고리즘과 비교할 수 있습니다. 그건 내가 믿는 매우 합리적인 가치로 런타임을 잘라야한다.
나는 위에서 언급하고 싶은 일을하기 위해 일종의 참조 코드를 찾으려고 노력했지만, 나는 학술 논문 이외의 것을 찾지 못했다. "simstring"이 실제로 컴파일되었지만 7 개의 테스트 레코드와 잘 일치하지 않는 것 같습니다. 아무도 올바른 방향으로 나를 가리킬 수 있습니까? 분명히 누군가가 이것에 뛰어 들어서 해결책을 찾았을 것입니다 ...
대단히 감사합니다!
P. C++에서이 작업을 수행하고 있지만 C#/C/Java/PHP의 샘플은 정상적으로 작동합니다.
정말 감사합니다. 이것이 데이터 마이닝 서적 3 장에서 이야기 한 내용이기도합니다. 나는 문자열 길이가 실행 가능할 수도 있지만 Levenshtein이 아니라고 생각합니다. (때로는 레코드가 "John Smith"및 "Smith, John"과 같은 필드를 존중합니다. Levenshtein이 일치 항목으로 잘못 삭제할 수도 있습니다). 나는 문자열 길이를 줄 것이고 런타임을 비교할 것이다. 당신은 다른 옵션 (R/KD 트리 등)의 실행 가능성에 대한 의견도 언급합니까? 적어도 왜 그들은 복잡하지는 않은가? – namezero