다음과 같은 사양 요구 사항을 검색하는 효율적인 방법이 필요했습니다.

Question

파일이 포함 된 디렉토리에서 주어진 파일 이름 (키워드라고하자)을 검색해야합니다. 검색 할 키워드가 거의 없으면 정기적으로 검색 할 수 있습니다 (지정된 디렉토리에있는 파일 이름 배열을 작성한 다음 주어진 키워드로 각 파일 이름을 검색하는 등). 매우 많은 수의 키워드를 동적으로 검색해야하므로 규칙을 사용하여 검색하는 것이 효율적이지 않습니다. 몇 가지 아이디어가있었습니다.

1. 해싱 사용 (그러나 디자인 방법은 명확하지 않음)

2. 검색을위한 블룸 필터 사용 (Google에게, 그것에 대해 알지 못하면, 작동하는 것은 매우 흥미 롭습니다!) : Bloom 필터를 사용하는 문제는 "잘못된 긍정은 가능하지만 잘못된 부정적인 것은 아닙니다"입니다. 결과를 놓칠 수 있습니다 ....

Answer 1

검색하기 전에 a 트리 모든 긍정적 인 일치 중.

트리를 만드는 것은 o (n)을 가져갑니다. 여기서 n은 단어 수입니다.

검색하려면 단어를 트리와 일치 시키십시오. 룩업은 O (m)에서 이루어집니다. 여기서 m은 길이 조회하는 단어의.

총 런타임 : O (n + nm) => o (nm) 모든 단어를 찾으려면.