자동 수정 알고리즘

Question

C++에서 다음을 구현하고 싶습니다.

1) 주어진 단어가 사전에 있는지 확인하십시오. 사전 파일은 거대한 파일입니다. 100MB 또는 3-4 백만 단어를 고려하십시오.

2) 잘못된 단어에 대한 수정을 제안하십시오.

3) 자동 완성 기능.

내 접근이

1) 나는 그렇게 효율적 의지를 검색 트리를 구축 할 계획입니다.

2) 자동 수정 기능을 구현하는 방법이 표시되지 않습니다.

3) 나는 나무

위의 모든 기능을 구현하는 최선의 데이터 구조 및 알고리즘은 무엇입니까

를 사용하여 자동 완성 기능을 구현 할 수 있습니까?

Answer 1

주어진 하위 트리의 모든 문자열을보고 자동 완성을 수행 할 수 있습니다. 선택하는 데 도움이되는 점수가 도움이 될 수 있습니다. 이것은 당신이 trie에서 그 경로를 따라 내려가는 "te"와 모든 가능한 결말을 얻기 위해 전체 서브 트리를 가로 지르는 것과 같은 방식으로 작동합니다.

수정하려면 트리 위에 http://en.wikipedia.org/wiki/Levenshtein_distance과 같은 것을 구현해야합니다. trie에서 주어진 경로를 처리했다면 경로 끝을 루트로하는 서브 트리의 모든 문자열에 결과를 재사용 할 수 있다는 사실을 사용할 수 있습니다.

Answer 2

1) 외에 나무에서, 또 다른 흥미로운 방법 http://en.wikipedia.org/wiki/Burrows%E2%80%93Wheeler_transform
BWT 접미사 배열 용이 주어진 단어 접두어를 추적하는 데 사용될 수 BWT
이다. 오류 수정에 대한

2), 현대 접근 방식은 좌입니다 : 무작위로 구글 검색에 의해 제공
http://en.wikipedia.org/wiki/Locality-sensitive_hashing#LSH_algorithm_for_nearest_neighbor_search

일부 링크 : 나는에 노력하고있다
https://cs.stackexchange.com/questions/2093/efficient-map-data-structure-supporting-approximate-lookup
https://code.google.com/p/likelike/
http://aspguy.wordpress.com/2012/02/18/the-magic-behind-the-google-search/

Answer 3

같은 문제. 지금까지 내가 만난 최고의 솔루션은 자동 완성을 위해 삼항 검색 트리를 사용하는 것입니다. Ternary Search Trees는 시도보다 공간 효율적입니다. 내 삼항 검색 트리에서 조회 한 문자열을 찾을 수 없다면 가장 가까운 일치를 찾는 데 이미 빌드 된 BK 트리를 사용합니다. BK Tree는 내부적으로 Levenshtein 거리를 사용합니다. 너

메타 폰은 탐험하고 싶은 무언가이기도하지만 메타 폰의 깊이에 빠져들지는 않는다.

원한다면 BK TREE + TERNARY SEARCH TREE 용 Java 솔루션을 가지고 있습니다.