PHP/MySQL 소규모 퍼지 검색

Question

작은 PHP/MySQL 응용 프로그램에 퍼지 검색을 구현하려고합니다. 특히, 약 2400 개의 레코드가있는 데이터베이스가 있습니다 (레코드는 연간 약 600의 비율로 추가되므로 작은 데이터베이스 임). 세 가지 관심 분야는 거리 주소, 성 및 날짜입니다. 나는이 필드들 중 하나에 의해 검색 할 수 있기를 원하며 철자/문자 오류에 대한 내성을 가지고 있습니다. 즉, "123 Main St"의 주소는 "123 Main St", "123 Main St.", "123 Mian St", "123 Man St", "132 Main St"등과 같은 이름이어야합니다. 날짜.

내가 다른 유사한 질문에 대한 답변이 주요 문제 :

• 그것은 가능한 모든 잘못된 맞춤법에 대한 동의어를 정의하는 것은 불가능하다, 날짜와 이름을 그렇게 잊어 버려.
• Lucene 등은 제한된 검색 데이터 세트 (최대 5,000 개의 레코드, 레코드 당 3 개의 필드)에 대해 매우 무거운 것으로 보입니다.
• 와일드 카드를 사용하여 무언가를하는 것은 모든 가능한 맞춤법 오류와 함께 논리적으로 보이지 않습니다.

의견이 있으십니까? MySQL을 기본적으로 사용할 수는 없지만 데이터 세트가 너무 제한되어 있으므로 비교적 간단하게 유지하려고합니다. 아마도 PHP 클래스 인 을 모두의 레코드에서 가져옵니다. DB, 어떤 종류의 비교 알고리즘을 사용하고 유사한 레코드의 ID를 반환합니까?

감사합니다, 제이슨

Answer 1

Razzie의 답변 (또는 Damerau–Levenshtein 사용)은 검색 키와의 친밀도에 따라 후보자의 목록을 순위를 매 깁니다. (주의 : 열쇠가 "12 Main St"인 경우 "13 Main St"는 "12 Moin St"와 동일한 타이핑 거리를 갖지만 11 및 22 Main St처럼 낮은 순위 또는 배제를 원할 수 있습니다. 등)

하지만 관리 가능한 크기의 후보 목록을 어떻게 순위를 매겨서 선택합니까?

한 가지 방법은 검색하려는 문자열의 각 단어에 대해 메타 폰 값 (또는 이중 메타 폰을 사용하여 값)을 계산하는 것입니다. 원래의 문자열을 포함하는 행의 id를 가진 다른 테이블에 이들 메타 폰을 저장하십시오. 그런 다음 LIKE 'key %'를 사용하여이 메타 폰 값을 빠르게 검색 할 수 있습니다. 여기서 key는 검색 텍스트의 단어 메타 폰입니다.

this thread에 제안 된 답변을 확인하십시오. 꽤 깔끔하고 거대하지 않은 DB에 대해서는 잘 작동해야합니다.

Answer 2

가 매우 작은 데이터베이스 인 경우, 수 부하 한 번하고 검색 Jaro-Winkler 같은 알고리즘을 사용하는 모든 데이터. 그들은 here을 PHP로 구현했습니다.

Imho 정말 잘 작동합니다. 예제 구현 here을 살펴보십시오. 그 검색은 같은 알고리즘을 사용한다는 것을 알고 있으며, 'Nintedno'를 매우 잘 찾을 수 있습니다. 또한 쿼리 결과와 가장 유사한 결과에 따라 결과를 정렬합니다.