Префикс/суффикс дерева, как правило, стандартный, лучший и самый осторожный решение для такого рода вещей, на мой взгляд. Вы не можете ошибиться с ними.
Но вот другая идея, которая относится к Bloom filters. Вероятно, вы знаете, что это такое, но на всякий случай (и для других людей, читающих этот ответ): Bloom-фильтры - очень маленькие, очень компактные битовые векторы, которые приближенно устанавливают включение. Если у вас есть множество S и фильтр Блума для этого множества B (S), затем
x ∈ S ⇒ x ∈ B(S)
но взаимность ложно. Это то, что вероятностно относительно структуры: существует вероятность (quantifiable), что фильтр Bloom вернет ложный положительный результат. Но приближение включения с фильтром Блума дико быстрее, чем тестирование его точно на множестве.
(Простой случай использования: в большом количестве приложений, фильтр Bloom используется, ну, как фильтр Проверка кэша дорого, потому что вы должны сделать доступ жесткого диска, так что программы, как. Squid сначала проверит небольшой фильтр Bloom в памяти, и если фильтр Bloom вернет положительный результат, Squid пойдет проверять кеш. Если он был ложным, то это нормально, потому что Squid обнаружит это при фактическом посещении кеша --- но преимущество заключается в том, что фильтр Bloom пощадил Squid, чтобы проверить кеш для большого количества запросов, где это было бы бесполезно.)
Цветные фильтры использовались с некоторым успехом в строке поиск. Вот эскиз (я могу вспомнить некоторые неправильные детали) этого приложения. Текстовым файлом является последовательность из N строк. Вы ищете слово, состоящее из букв M (и ни одно слово не может быть распространено по двум строкам). Фаза предварительной обработки будет строить ONE Bloom-фильтр для каждой строки, добавив каждую подпоследовательность линии к фильтру Bloom; например, для этой линии
Touching this dreaded sight, twice seene of vs,
И соответствующий Bloom фильтр будет создан с «Т», «К», «Тоу» ... «о», «НУ», ... «против, "," s "," s ",", ". (Возможно, эта часть может быть неправильной. Или вы можете оптимизировать.)
Затем, при поиске подслова размера M, просто выполните очень быструю проверку на каждом из фильтров Bloom, и когда есть удар, например, изучить линию близко к алгоритму KMP. На практике, если вы хорошо настраиваете фильтры Bloom, компромисс замечателен. Поиск невероятно быстрый, потому что вы устраняете все бесполезные линии.
Я считаю, что из этой концепции вы могли бы извлечь полезную схему для своей ситуации. Прямо сейчас, я вижу два очевидной адаптации:
либо вырезать ваши данные установки во многих блоках размером K (каждый со своим фильтром Блума, как строки в предыдущем примере);
или используйте разновидность дихотомии, в которой вы разбиваете набор на два подмножества, каждый с фильтром Блума, затем каждое подмножество разбивается на два подмножества с собственным фильтром Блума и т. Д. (Если вы собираетесь добавьте все подстроки, как было предложено с помощью описанного метода, эта вторая идея была бы немного запретительной - за исключением того, что вам не нужно добавлять все подстроки, только подстроки размером от 1 до 10).
Обе идеи могут быть объединены изобретательскими способами для создания многослойных схем.
Это зависит от характера данных. Не могли бы вы отсортировать его, индексировать, ...? (вы можете посмотреть в таблицы радуги, так как для этого вы обычно ищете 10-байтовую строку в 10 миллиардов байт) – mvds
btw большой O, о котором вы говорите, не учитывает, что 10 миллиардов байтов могут не помещаться в память - сколько у вас есть? Disk i/o * действительно * медленный по сравнению с RAM. – mvds
И эта 10-байтовая строка поиска, это случайная или имеется ограниченный диапазон строк поиска? вам действительно нужно поделиться некоторыми подробностями. – mvds