나는 많은 시간을 물었습니다. 근사 문자열 일치에 적합한 알고리즘에 대한 제안을 원합니다.대략 일치하는 문자열
응용 프로그램은 특히 회사 이름 일치에만 사용되며 다른 용도는 없습니다.
가장 큰 문제는 아마도 회사 이름 부분과 짧은 이름 부분 일 것입니다. 예 : 1. companyA pty ltd vs companyA pty. ltd. companyA 대 2. WES Engineering 대 W.E.S. 공학 (극히 드문 경우)
편집 거리가 적당하다고 생각하십니까? 나는 C 번호를
감사를 사용하고
,
사용할 수있는 다양한 문자열 거리 메트릭이 있습니다.
나는 Jaro-Winkler을 권하고 싶습니다. 비교 결과가 개별 편집 단위 인 편집 거리와 달리 JW는 0-1 점수를 제공합니다. 특히 적절한 이름에 적합합니다. 또한 this nice tutorial보고 this SO question.
는 전 C#와 함께 일하지만 여기 JW의 일부 구현 내가 발견하지 않은 온라인 :
Impl 1가 (파일 목록을 보면 그들은 너무 DOT NET 버전이)
당신이 좀 더 정교 일치하고 싶은 경우에, 당신은 단어 형태의 일부 사용자 지정 정상화 일반적으로 회사 이름에서 발생 할 시도 할 수 있습니다 당신이
distance (normalize("foo corp."), normalize("FOO CORPORATION"))
을 계산하는 경우 등 ltd/limited, inc/incorporated, corp/corporation 당신이 당신이 경우 얻을 것이 무엇 인 (0이 아닌 14로 결과를 얻어야한다 등 이런 식으로 소문자 구분, 약어를 설명하는 계산 된 levenshtein 편집 거리).
링크를 보내 주셔서 감사합니다. 매우 유용합니다. – Max
예, Levenshtein 거리가이 적합 최대. 적어도 당신이 나열한 모든 사람들을 위해 작동 할 것입니다.
Soundex을 사용할 수도 있지만 필요하지는 않습니다.
이 간단한 예제에서는 모든 영숫자가 아닌 문자 만 제거하면 각면의 데이터를 미리 계산할 수 있기 때문에 가장 쉽게 수행 할 수 있습니다. 십자가를 곱하고 편집 거리를 계산하는 것보다 훨씬 빠릅니다.
매우 흥미로운 제안입니다! – Max
나는 이미 다른 질문에 대한 답을 제공해주었습니다.
https://stackoverflow.com/a/30120166/2282794
난 당신이 얘기 한 유사한 이름이 일치하는 요구 사항에 정말 큰 규모의 시스템에서 일했습니다. 이름 일치는 그리 간단하지 않으며 이름과 성의 순서가 다를 수 있습니다. 단순한 퍼지 이름 일치 알고리즘은 이러한 시나리오에서 비참하게 실패합니다.
근사치 문자열 매칭 알고리즘에 대해 이야기하고 싶다면 많은 정보가 있습니다. Jaro-Winkler, 편집 거리 (Levenshtein), Jaccard 유사성, Soundex/Phonetics 기반 알고리즘 등 몇 가지가 있습니다. 간단한 인터넷 검색 결과 우리에게 모든 세부 정보가 제공됩니다. C#으로 모두 구현할 수 있습니다.
아이러니는 주어진 입력 문자열 두 개를 일치 시키려고 할 때 작동합니다. 이론적으로는 어쨌든 퍼지 또는 근사 문자열 매칭이 작동하는 방식을 보여줄 수 있습니다.
그러나, 현저하게 절제된 점은 어떻게하면 프로덕션 설정에서 동일한 것을 사용합니까? 대략적인 문자열 매칭 알고리즘을 찾고있는 사람들은 누구나 프로덕션 환경에서 동일한 문제를 해결할 수있는 방법을 알고있었습니다.
저는 Java에 특정한 Lucene에 대해서 이야기했을 지 모르지만 .Net에도 Lucene이 있습니다.
는 내가 모든 도트 문자를 제거한 다음 나중에 levenshtein 거리를 사용하는 것 같네요. 비슷하지만 빠른 levenshtein보다 다른 알고리즘을 찾았습니다. 그 사람의 이름은 알고리즘 sift3입니다. 매우 흥미로운. – Max