Необходим эффективный способ поиска по следующему конкретному требованию
-
19-09-2019 - |
Вопрос
Я должен выполнить поиск по заданному имени файла (скажем, по ключевому слову) в каталоге, содержащем файлы.Если бы для поиска требовалось всего несколько ключевых слов, я мог бы использовать обычный поиск (например, создать массив имен файлов, находящихся в указанном каталоге, а затем выполнить поиск по каждому имени файла с заданным ключевым словом).Поскольку мне нужно выполнять динамический поиск по очень большому количеству ключевых слов, использование обычного поиска неэффективно.У меня была пара идей:
1.использование хеширования (но не ясно, как его спроектировать)
2. Использование фильтров Bloom для поиска (пожалуйста, погуглите, если вы не знаете об этом, его работа очень интересна!):Проблема при использовании фильтров Блума заключается в том, что "Ложноположительные результаты возможны, но ложноотрицательные - нет".Я могу пропустить некоторые результаты....
Решение
Перед поиском создайте три из всех положительных совпадений.
Для создания трие потребуется O(n), где n - количество слов.
Чтобы выполнить поиск, попробуйте сопоставить слово с трие.Поиск выполняется в O(m), где m - длина слова для поиска.
Общее время выполнения:O(n + nm) => O (nm), чтобы найти все слова.