맞춤법 검사기에서 제안하는 알고리즘은 무엇입니까?
단어 제안과 함께 맞춤법 검사기를 구현할 때 일반적으로 어떤 알고리즘이 사용됩니까?
처음에는 (사전에서 찾을 수없는 경우) 사전에있는 다른 모든 단어와 Levenshtein의 거리 를 비교하여 최상위 단어를 반환하는 것이 좋습니다. 그러나 이것은 전체 사전을 반복적으로 평가 해야하는 비효율적 인 것처럼 보입니다.
이것은 일반적으로 어떻게 이루어 집니까?
이 피터 노르 빅에 의해 좋은 에세이 맞춤법 교정기를 구현하는 방법은. 기본적으로 주어진 편집 거리에서 후보 문자열을 시도하는 무차별 대입 방식입니다. ( 여기에 당신이 사용하는 맞춤법 교정기의 성능을 개선 할 수있는 방법을 몇 가지 도움말 블룸 필터 및 빠른 후보 해싱은 .)
맞춤법 검사기의 요구 사항이 더 약합니다. 단어가 사전에 없다는 것을 알아야합니다. 블룸 필터 를 사용하면 메모리를 덜 소비하는 맞춤법 검사기를 만들 수 있습니다 . Jon Bentley의 Programming Pearls 에는 고대 버전이 영어 사전에 64kb를 사용하여 설명되어 있습니다.
BK-나무는 다른 접근 방식이다. 좋은 기사가 여기 있습니다 .
Levenshstein 거리는 맞춤법 검사기의 정확한 편집 거리가 아닙니다. 삽입, 삭제 및 대체 만 알고 있습니다. 조옮김이 누락되어 1 문자의 조옮김에 대해 2가 생성됩니다 (1 개의 삭제 및 1 개의 삽입). Damerau–Levenshtein 거리는 올바른 편집 거리입니다.
내가 성공적으로 사용했지만 어디에도 설명되지 않은 제안을 생성하는 방법은 "나쁜"해시 함수를 사용하여 사전을 작성할 때 사전을 계산하는 것입니다.
사람들이 만드는 맞춤법 오류 유형을보고 올바른 맞춤법과 동일한 버킷에 잘못된 맞춤법을 지정하는 해시 함수를 디자인하는 것이 좋습니다.
예를 들어, 일반적인 실수는 definite 대신 definate 와 같은 잘못된 모음을 사용하는 것 입니다. 따라서 모든 모음을 같은 문자로 취급하는 해시 함수를 디자인합니다. 가장 쉬운 방법은 먼저 입력 단어를 "정규화"한 다음 정규화 된 결과를 일반 해시 함수를 통해 넣는 것입니다. 이 예에서 정규화 함수는 모든 모음을 삭제하므로이 definite됩니다 dfnt. "정규화 된"단어는 전형적인 해시 함수로 해시됩니다.
이 특수 해시 함수를 사용하여 모든 사전 단어를 보조 색인 (해시 테이블)에 삽입하십시오. 해시 함수가 "나쁜"것이기 때문에이 테이블의 버킷에는 긴 충돌 목록이 있지만 이러한 충돌 목록은 기본적으로 사전 계산 된 제안입니다.
이제 맞춤법이 틀린 단어를 찾으면 맞춤법이 틀린 보조 버킷에서 버킷에 대한 충돌 목록을 찾습니다. Ta da : 제안 목록이 있습니다! 당신이 할 일은 그것에 단어의 순위를 지정합니다.
실제로, 다른 해시 함수가 포함 된 몇 가지 보조 색인이 필요합니다. 전치 된 철자, 단일 / 이중 문자, 심지어 발음이 잘못된 철자를 잡기위한 단순한 Soundex와 같은 다른 유형의 오류를 처리해야합니다. 실제로, 나는 단순한 발음 발음이 먼 길을 가고 사소한 오타를 찾기 위해 고안된 것 중 본질적으로 쓸모없는 것을 발견했습니다.
이제 각 보조 색인에서 맞춤법이 틀린 부분을 찾아 순위를 정하기 전에 충돌 목록을 연결합니다.
충돌 목록에는 사전에있는 단어 만 포함되어 있습니다. Peter Norvig 기사에서와 같이 대체 철자를 생성하는 방법을 사용하면 사전에 대해 필터링해야하는 수천 개의 후보를 얻을 수 있습니다. 미리 계산 된 접근 방식을 사용하면 수백 명의 후보가 생길 수 있으며, 모두 정확하게 철자가 맞는다는 것을 알고 있으므로 바로 순위로 건너 뛸 수 있습니다.
업데이트 : FAROO Distributed Search 와 비슷한 알고리즘 설명을 찾았습니다 . 이것은 여전히 편집 거리 제한 검색이지만 사전 계산 단계가 "나쁜 해시 함수"아이디어처럼 작동하기 때문에 매우 빠릅니다. FAROO는 제한된 해시 함수 개념을 사용합니다.
연산
- 철자가 틀린 단어를 입력으로 사용하십시오.
- 영어 단어 목록과 빈도를 텍스트 파일로 저장하십시오.
- 사용 가능한 모든 영어 단어 (텍스트 파일에 저장 됨)와 빈도 (단어가 얼마나 자주 영어로 사용되는지 측정)를 3 차 검색 트리에 삽입하십시오.
- 이제 3 차 검색 트리를 따라 이동합니다-
- 3 차 검색 트리에서 발견 된 각 단어에 대해 철자가 틀린 단어에서 Levensthein 거리를 계산하십시오.
- Levensthein Distance <= 3 인 경우, 우선 순위 대기열에 단어를 저장하십시오.
- 두 단어의 편집 거리가 동일한 경우 더 높은 빈도의 단어가 더 강합니다. Priority Queue에서 상위 10 개 항목을 인쇄하십시오.
최적화
- 현재 단어에서 입력 단어의 하위 문자열 편집 거리가 3보다 큰 경우 현재 노드의 하위 트리에서 단어를 제거
할 수 있습니다 . github project 에서보다 자세한 설명과 소스 코드를 찾을 수 있습니다 .
사전의 각 단어에 대한 정확한 편집 거리를 알 필요는 없습니다. 한계 값에 도달 한 후 알고리즘을 중지하고 단어를 제외 할 수 있습니다. 이렇게하면 많은 컴퓨팅 시간이 절약됩니다.
맞춤법 검사기는 Unix 맞춤법 프로그램에서와 같이 구현하기가 매우 쉽습니다. 소스 코드는 공개적으로 제공됩니다. 수정이 포함될 수 있습니다. 한 가지 기술은 편집을 수행하고이 새 단어가 사전에 있는지 다시 확인하는 것입니다. 이러한 새로운 편집 내용을 그룹화하여 사용자에게 표시 할 수 있습니다.
유닉스 시스템은 Mc IllRoy가 작성한 프로그램을 사용합니다. 다른 방법은 대용량 파일의 경우 유용 할 수있는 Trie를 사용하는 것입니다.
유닉스 접근법은 분산 사전 해시 알고리즘을 사용하기 때문에 거대한 사전을위한 공간이 매우 적습니다.
참고 URL : https://stackoverflow.com/questions/2294915/what-algorithm-gives-suggestions-in-a-spell-checker
'development' 카테고리의 다른 글
| 에 이미지 삽입 (0) | 2020.07.29 |
|---|---|
| Xcode에서 클래스 이름 바꾸기 : Refactor…가 회색으로 표시됩니다 (비활성화 됨). (0) | 2020.07.29 |
| 팝 오버가 여전히 보이는 동안 UIPopovercontroller dealloc에 도달 (0) | 2020.07.29 |
| SQLite DateTime 비교 (0) | 2020.07.29 |
| 페이지에 JavaScript 변수가 정의되어 있는지 어떻게 알 수 있습니까? (0) | 2020.07.29 |