최적의 자동 완성/제안 알고리즘, 데이터베이스 [C++/C]

최적의 자동 완성/제안 알고리즘, 데이터베이스 [C++/C]

Google, Firefox 일부 AJAX 페이지에는 사용자가 문자를 입력하는 동안 가능한 항목 목록이 표시됩니다.

자동 완성 구현을 위한 좋은 알고리즘, 데이터 구조를 제공할 수 있는 사람이 있습니까?

trie는 프리픽스와 일치하는 단어를 빠르게 찾기 위해 사용할 수 있는 데이터 구조입니다.

편집: 다음 예시는 자동완성 http://rmandvikar.blogspot.com/2008/10/trie-examples.html을 구현하는 방법을 보여 줍니다.

다음은 3가지 자동 완성 구현의 비교입니다(단, C++가 아닌 Java).

* In-Memory Trie
* In-Memory Relational Database
* Java Set

키를 조회할 때, 트라이는 Set 구현보다 약간 빠릅니다.trie와 세트 모두 관계형 데이터베이스 솔루션보다 훨씬 빠릅니다.

세트의 셋업 비용은 Trie 또는 DB 솔루션보다 저렴합니다.새로운 「워드 세트」를 자주 작성할 것인지, 검색 속도를 우선시할 것인지를 결정해야 합니다.

이러한 결과는 Java에서 확인할 수 있으며, C++ 솔루션에 따라 마일리지가 달라질 수 있습니다.

대규모 데이터셋의 경우, 백엔드에 적합한 후보가 Ternary 검색 트리입니다.바이너리 검색 트리의 낮은 공간 오버헤드와 디지털 검색의 문자 기반 시간 효율이라는 두 가지 장점을 결합합니다.

Dobbs Journal (Dr. Dobbs 저널)을 참조하십시오.http://www.ddj.com/windows/184410528

목표는 사용자가 입력한 유한 결과 세트를 빠르게 검색하는 것입니다.「컴퓨터 과학」을 검색하려면 , 「컴퓨터」또는 「과학」으로부터 타이핑을 개시할 수 있지만, 「컴퓨터」는 입력할 수 없는 것을 먼저 생각해 봅시다.그래서 문구가 주어지면 단어로 시작하는 하위 구절을 생성합니다.각 문구에 대해 TST(Ternary Search Tree)에 입력합니다.TST의 각 노드는 지금까지 입력된 구문의 프레픽스를 나타냅니다.그 프리픽스에 대한 베스트10의 결과를 그 노드에 저장합니다.노드에 대한 결과의 유한량(여기에 10개)보다 많은 후보가 있는 경우, 두 결과 간의 경쟁을 해결하기 위한 순위 기능이 있어야 한다.

트리는 데이터의 역동성에 따라 몇 시간에 한 번씩 구축할 수 있습니다.데이터가 실시간이면 다른 알고리즘이 더 잘 균형을 잡을 수 있을 것 같습니다.이 경우 절대적인 요건은 모든 키 입력에 대해 결과를 번개처럼 빠르게 검색하는 것입니다.

맞춤법 수정 제안이 포함되면 더 많은 문제가 발생할 것이다.이 경우 편집 거리 알고리즘도 고려해야 합니다.

국가 목록과 같은 소규모 데이터셋의 경우 Trie의 간단한 구현으로 충분합니다.웹 응용 프로그램에서 이러한 자동 완성 드롭다운을 구현하는 경우 목록으로 데이터를 제공한 후 YUI3의 자동 완성 위젯이 모든 작업을 수행합니다.대용량 데이터로 백업되는 자동 완성의 프런트엔드로 YUI3을 사용하는 경우 TST 기반 웹 서비스를 C++로 만든 다음 자동 완결 위젯의 스크립트 노드 데이터 소스를 사용하여 단순 목록이 아닌 웹 서비스에서 데이터를 가져옵니다.

세그먼트 트리를 사용하여 자동 완료를 효율적으로 구현할 수 있습니다.

가장 인기 있는 완성을 제안하려면 "제안 트리"를 선택하는 것이 좋습니다.제안 트리

간단한 해결책의 경우: 최소 편집(Levenshtein) 거리(1 또는 2)로 '후보'를 생성한 후 해시 컨테이너를 사용하여 후보 존재 여부를 테스트합니다(단순 용액을 위해 세트로 충분하며, 다음으로 tr1 또는 부스트에서 unordered를 사용합니다).

예:당신은 car를 썼고 당신은 car를 원합니다.arr은 1번 삭제로 생성됩니다.arr은 unordered_set에 있습니까? 아니요.crr은 1회 삭제로 생성됩니다.crr이 unordered_set에 있습니까? 아니요. 차량은 한 번의 삭제로 생성됩니다.차가 주문되지 않은 세트에 있나요? 네, 당신이 이겼습니다.

물론 삽입, 삭제, 전치 등이 있습니다.

후보를 생성하는 알고리즘은 특히 unordered_set이 매우 적은 경우 시간을 낭비하는 것입니다.

언급URL : https://stackoverflow.com/questions/1783652/what-is-the-best-autocomplete-suggest-algorithm-datastructure-c-c