Необходим эффективный способ поиска по следующему конкретному требованию

Question

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

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

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

Answer 1

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

Для создания трие потребуется O(n), где n - количество слов.

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

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