Быстрый поиск, не токенизация

Question

Я ищу способ быстро скопировать полный текст в миллион строк 1 килобайт.

Популярные способы ускорения такого рода вещей (Lucene или текстовый индекс в MongoDB), по-видимому, вызывают высокую производительность при поиске времени от разбиения строк содержимого на токены, которые они выполняют при построении индекса время. Эти жетоны основаны на словах естественного языка. Однако я хотел бы избежать этого вида токенизации, потому что я хочу искать строки, которые не имеют никакого отношения к словам естественного языка.

Я ищу что-то подобное по функциональности SQL «LIKE»% abc% '», но не только« abc ». Скажем, для строки, такой как «a.1», и соответствуют этому документу, например «.......... a.123 ........»

Я получаю впечатление, что теоретически это возможно с использованием suffix trees, но я не нашел соответствующей реализации Java. Под «подходящим» я подразумеваю тот, который не полагается на полное дерево суффикса, загружаемое в память сразу.

Это еще не придумано?

Answer 1

Под «соответствующим» подразумевается тот, который не полагается на полное дерево суффикса, загружаемое в память сразу.

Насколько я знаю и понимаю деревья суффикса, нет возможности загрузить только часть дерева суффиксов и использовать его. Вы можете избежать этого, используя алгоритм, такой как алгоритм Aho-Corasick или Boyer-Moore, как упоминалось @fge.

Одна из реализации, должны Poppular является: https://github.com/abahgat/suffixtree

Также есть хороший и простой alghorithm найти подстроку в строке: Aho–Corasick algorithm который хорошо изложены в «Составители: принципы, методы и Инструменты ", например Эта альгота используется в антивирусах для поиска сигнатуры вируса в вирусе db и в обработке ДНК, которая очень впечатляет.