자동 완성 알고리즘, 논문, 전략, 등

Question

사람이 좋은 읽을 수있는 자원이나 "autcomplete"를 실험하는 코드가 있는지 궁금 해요

내가 어디서 무엇을 시작하는 자동 완성, 뒤에 이론을 알고 싶습니다

일반적인 실수 등.

Enso, Launchy, Google 크롬, 심지어 tcsh와 같은 제품이 자동 완성을 수행하는 방식을 매혹적으로 찾았습니다. 호기심을 자극하기 위해 자기 자신을 시작했으며 결론에 도달했습니다. 이전에 널리 탐구 된 분야.

누군가 구현 방법에 대한 훌륭한 기술 리소스를 공유하는 경우 감사하게 생각합니다.

미리 감사드립니다.

Answer 1

• http://humanized.com/weblog/2007/03/30/what_makes_a_good_autocomplete/-
• http://social.msdn.microsoft.com/Forums/en-US/vblanguage/thread/2ccb37b9-c7e1-4113-86ac-ad3d33b4b4b1/ - 닷넷 세계에서
• 높은위한 http://www.patentstorm.us/patents/5845300/description.html
• http://ask.metafilter.com/91068/Fuzzy-text-completion-algorithm합니다 (이론 독서를 여전히 가능 가치) 자동 완성 방법에 불쾌한 특허 취할 전략에 대한 수준 높은 토론.

Answer 2

체크 아웃 GWT를 사용하여 자동 완성을 구현하는 방법에 대한이 블로그 :

http://jroller.com/glongman/entry/gwt_autocompleter

하지만 먼저 구현이 수행하는 방법을 파악하기 위해 자신의 매우 간단한 무언가 시작 추천 할 것입니다. Trie로 시작할 것입니다. 클라이언트에 완전히 저장 한 다음 필요한 경우 서버 쿼리로 최적화하는 방법으로 진행할 수도 있습니다.

Answer 3

자동 완성은 일반적으로 다음 중 하나를 사용하여 구현됩니다

• 나무를. 트리 구조 (접두사 트리, 접미어 트리, dawg 등)에서 검색 가능한 텍스트를 인덱싱함으로써 메모리 저장 비용을 희생하여 매우 빠른 검색을 실행할 수 있습니다. 트리 순회는 근사 일치를 위해 조정될 수 있습니다.
• 패턴 파티셔닝. 텍스트를 토큰 (ngrams)으로 분할함으로써 간단한 해싱 스키마를 사용하여 패턴 어커런스를 검색 할 수 있습니다.
• 필터링. 잠재적 인 일치 항목 집합을 찾은 다음 순차 알고리즘을 적용하여 각 후보를 확인합니다.

주제에 대한 논문의 몇 :

• Bořivoj Melichar. 유한 오토마타에 의한 대략적인 문자열 매칭;
• 곤살로 나 바로. 대략적인 문자열 매칭을위한 가이드 투어;
• Leonid Boytsov. 근사 사전 검색을위한 색인 방법 : 비교 분석;
• Marios Hadjieleftheriou 및 Divesh Srivastava.대략적인 문자열 처리;
• Surajit Chaudhuri 및 Raghav Kaushik. 자동 완성을 확장하여 오류를 방지합니다.

Java 자동 완성 라이브러리 인 completely을 살펴보십시오.