[algorithm] 맞춤법 검사기에서 제안을 제공하는 알고리즘은 무엇입니까?

내가 성공적으로 사용한 제안을 생성하는 방법은 “나쁜”해시 함수를 사용하여 제안을 미리 계산하는 것입니다 (사전을 빌드 할 때).

아이디어는 사람들이 만드는 철자 오류의 유형을 살펴보고 올바른 철자와 동일한 버킷에 잘못된 철자를 할당하는 해시 함수를 설계하는 것입니다.

예를 들어, 일반적인 실수는 definite 대신 definate 와 같이 잘못된 모음을 사용하는 것 입니다. 따라서 모든 모음을 동일한 문자로 취급하는 해시 함수를 설계합니다. 이를 수행하는 쉬운 방법은 먼저 입력 단어를 “정규화”한 다음 정규화 된 결과를 정규 해시 함수를 통해 입력하는 것입니다. 이 예에서, 정규화 기능은 모든 모음을 드롭 할 수 있으므로 definite이된다 dfnt. 그런 다음 “정규화 된”단어는 일반적인 해시 함수로 해시됩니다.

이 특수 해시 함수를 사용하여 모든 사전 단어를 보조 색인 (해시 테이블)에 삽입합니다. 이 테이블의 버킷은 해시 함수가 “나쁨”이기 때문에 긴 충돌 목록을 가지지 만 이러한 충돌 목록은 본질적으로 미리 계산 된 제안입니다.

이제 맞춤법이 잘못된 단어를 찾으면 맞춤법 오류가 보조 색인에서 매핑되는 버킷의 충돌 목록을 조회합니다. Ta da : 제안 목록이 있습니다! 당신이해야 할 일은 단어의 순위를 매기는 것입니다.

실제로는 전치 문자, 단일 / 이중 문자, 심지어 소리 나는 오타를 포착하기위한 단순한 Soundex와 같은 오류와 같은 다른 유형의 오류를 처리하기 위해 다른 해시 함수가있는 몇 가지 보조 색인이 필요합니다. 실제로 저는 단순한 발음이 먼 길을 가고 있으며 사소한 오타를 찾기 위해 고안된 일부 발음을 본질적으로 쓸모 없게 만드는 것을 발견했습니다.

이제 각 보조 색인에서 맞춤법 오류를 찾아 순위를 매기기 전에 충돌 목록을 연결합니다.

충돌 목록에는 사전에있는 단어 만 포함되어 있습니다. (Peter Norvig 기사에서와 같이) 대체 철자를 생성하려는 접근 방식을 사용하면 먼저 사전에 대해 필터링해야하는 수천 개의 후보를 얻을 수 있습니다. 미리 계산 된 접근 방식을 사용하면 수백 명의 후보를 얻을 수 있으며 모두 올바른 철자임을 알고 있으므로 순위로 바로 건너 뛸 수 있습니다.

업데이트 : 이후 FAROO Distributed Search 라는 유사한 알고리즘 설명을 찾았습니다 . 이것은 여전히 ​​편집 거리가 제한된 검색이지만 사전 계산 단계가 내 “나쁜 해시 함수”아이디어처럼 작동하기 때문에 매우 빠릅니다. FAROO는 잘못된 해시 함수라는 제한된 개념을 사용합니다.

답변