|
Задача "Точного совпадения" - приемы для больших объемов Т
Добрый день, господа.
Надеюсь вы не будете сильно против, что я обращаюсь к вашему коллегиальному разуму. На то вроде бы форум...
Собственно модель задачи такая:
1. Есть Т, а точнее даже не Т, а массив строк S[].
2. Есть шаблон P. Для простоты это тоже строка (если идеи будут развиваться, то немного усложним).
3. Надо найти все строки S из Т, в которых встречается P.
А теперь уточняем:
4. Т (S[]) - const.
5. Размерность массива строк n достаточно большая. Если не сказать очень большая. Т.е. до 100М строк.
6. Можно потратить некоторое (сравнимое с O(n)) время и память для построения каких-либо дополнительных статистик/моделей и пр., которые бы способствовали более эффективному поиску шаблона
Внимание вопросы:
- Насколько это "классическая" задача;
- Что читать, кроме опять же книги Гасфилда;
- Любые идеи, и ссылки на статьи и литературу...
PS. В мой недалекий мозг пришла очень общая идея -- для начала попытаться сократить просмотр избавиться от полного прохода по массиву исходных строк для каждого шаблона. (если тема получит развитие, я с удовольствием поделюсь соображениями с уважаемой публикой, дабы выслушать разумную и конструктивную критику)
|
Линейный вид
