Нужен эффективный способ поиска следующего специфического требования - PullRequest
1 голос
/ 09 ноября 2009

Я должен искать данное имя файла (скажем, ключевое слово) в каталоге, содержащем файлы. Если бы было только несколько ключевых слов для поиска, я мог бы использовать обычный поиск (например, создать массив имен файлов, находящихся в указанном каталоге, а затем выполнить поиск в каждом имени файла по заданному ключевому слову). Так как мне нужно искать очень большое количество ключевых слов динамически, поиск неэффективен с помощью обычного поиска. У меня была пара идей:

1. Использование хеширования (но не ясно, как его создать)

2.Использование Bloom Filters для поиска (пожалуйста, Google, если вы не знаете об этом, его работа очень интересна!): Проблема в использовании фильтров Bloom: «Возможны ложные срабатывания, а ложные отрицания - нет». Я мог бы пропустить некоторые результаты ....

1 Ответ

1 голос
/ 09 ноября 2009

Перед поиском создайте три всех положительных совпадений.

Создание дерева займет O (n), где n - количество слов.

Чтобы найти, попробуйте сопоставить слово со словом три. Поиск выполняется в O (m), где m - это длина слова для поиска.

Общее время выполнения: O (n + nm) => O (nm), чтобы найти все слова.

...