빠른 중위 검색

Question

저는 10 억 단어/구를 신속하게 쿼리해야하는 자동 완성 기능을 구축 중이며 몇 가지 문제가 있습니다. 내 첫 번째 아이디어는 일종의 트리/삼항 트리 구조를 통과하는 것이었지만, 엄격하게 접두사 일치로되어있어 내 응용 프로그램에 적합하지 않습니다 (완전한 중위 일치를 원합니다). 그런 다음 더 큰 솔루션 인 SqlServer FullText Indexing, Lucene, Solr, Sphinx로 옮겼지만 Lucene 및 SqlServer FullText Indexing은 실제로 fulltext가 아니라 멋진 기능 (soundex, proximity 등)이 붙습니다. 나는 Levenshtein 편집 거리가 도움이 될 수있는 방법을 생각하려고 노력했으나, 높은 편집 거리 (즉, google과 ogl 편집 거리, 3의 편집 거리, 3은 일반적인 임계 값보다 높은 임계 값).

제 질문은 Google/bing 등의 강력한 업체는 어떻게합니까? 그들은 조금이라도 무차별 적으로 굴니까? 나는 상상할 것이다. 그러나 나는 그것의 어떤지지를 발견 할 수 없다.

도움이 될 것입니다.

Answer 1

, 당신은 같은 선행 및 후행 와일드 카드를 사용할 수 있습니다.

이전의 "용어와 색인을 반대로 할 수있는 쿼리 문자열을 사전 처리 할 수있는 경우이 방법은 충분히 빠르지는 않지만 일부 경우 (접두사 전용 와일드 카드 검색이 정확해야 함) that also "트릭 :

acillateM 

Answer 2

Lucene/Solr이이를 매우 쉽게 수행 할 수 있습니다. Lucene/Solr의 검색 단위는 Term이며 일반적으로 단어이지만 text analysis의 구성 방법에 따라 실제로는 거의 아무것도 될 수 있습니다.

Solr을 사용하면 여러 가지 방법 (ngrams/대상 포진, 패싯 접두어, TermsComponent ...)을 구현할 수 있습니다. Solr의 최신 버전은 autocomplete based on spell checking에 대한 특정 구성 요소와 함께 제공됩니다. "메탈"포함 "talli"를 포함하는 모든 한 단어 조건을 선택할 것

*talli* 

: 당신이 루씬에 queryParser.setAllowLeadingWildcard(true);을 사용하는 경우

Answer 3

2013 년에 삽입 검색이 필요할 때, 나는 약간의 조사를했습니다. 내가 찾은 유일한 길은 Sphinx engine입니다. 하나는이는 눈 깜짝 할 사이에 문제를 다루는 한 후 중위 검색을

index tra 
{ 
    [...] 
    enable_star=1 
    min_infix_len=2 
} 

를 지원하도록 구성해야합니다. 나는 그것이 200K 레코드에 관한 것이라고 생각한다. 필자는 메모리 내 검색 라이브러리를 모방하기 위해 로컬 엔진을 사용했습니다.