검색 알고리즘을 최적화하는 방법은 무엇입니까?

Question

그래서 기본적으로 내가 무엇을 의미하는지는 이 될 수있는 검색 도구 (배열이나 arraylist 등 일련의 문자열을 검색하는 것과 같은)를 만드는 방법은 무엇입니까? 반드시 빠를 필요는 없지만 유용합니다.

예를 들어 검색어에 과 비슷한이라는 결과가 나오지만 정확하지 않은 경우 '자동 수정'을 포함시키는 것이 얼마나 쉬운가요? 또는 전체 단어가 아닌 처음 3 자와 일치하는 결과 또는 결과가 일 경우이 포함되지만 전체 단어로 구성되지는 않습니까? 이 또는 클래스에 대한 API가 있습니까? 아니면 여기에서 나를 도울 알고리즘이 있습니까?

Answer 1

간단히 말해서, SIMILAR 문자열의 경우 유사성 (실제로 하나의 문자열을 다른 문자열로 바꾸기위한 이동 횟수를 찾지 만 유사한 종류의 유사도)을 찾는 "거리 편집"알고리즘을 사용할 수 있습니다. AUTOCOMPLETE 도구를 사용하면 문자 트리로 작동하는 "Trie"데이터 구조를 사용할 수 있으며 현재 단어의 문자를 읽는 동안 기존 단어에 도달 할 수있는 위치를 나타내는 노드에서 멈 춥니 다 . 단어 (문자열)을 포함하는 항목을 검색하려면 KMP 알고리즘 (또는 Aho-Corasick, 전체 텍스트에서 한 단어 이상을 검색하려는 경우)을 사용할 수 있다고 가정합니다. 루씬/SOLR/ElasticSearch에 https://en.wikipedia.org/wiki/Knuth%E2%80%93Morris%E2%80%93Pratt_algorithm

https://en.wikipedia.org/wiki/Aho%E2%80%93Corasick_algorithm