Алгоритм для быстрой проверки соответствия строки шаблонам?

Question

[stas8]

В упрощенном виде задача такова: есть большое количество шаблонов из нулей и единиц. Возможен символ * в конце шаблона. ( Например: 1, 10, 1011* )
И есть большое количество строк. Для каждой строки необходимо проверить, "покрывается" ли строка каким-либо из шаблонов.

Вопрос: как это сделать наиболее эффективно? Наверняка есть какой-то известный алгоритм или структура данных для этой задачи.

------------------------------
UPD: Попробовал реализовать дерево префиксов. Вроде, работает правильно, но, к сожалению слишком медленно. Буду благодарен, если кто-нибудь сможет взглянуть на код -- может быть, я что-то написал неверно/неэффективно: pastebin.com/DKZzhvXA

Answer 1

[SeptiM]

Простое решение можно реализовать через префиксное дерево. Запихиваем все шаблоны, а потом сравниваем по строчке из множества.

Если требуется сделать разово и на большом объеме данных, я бы поступил так. Определим на строках обычный лексикографический порядок (если есть строка и её префикс, то префикс меньше). Каждому шаблону со звездочкой {s}* сопоставим две строки {s} и {s}$, где $ больше 0 и 1. Шаблону без звезды, просто ставим {s} и {s}&, где & < 0 и 1. А теперь, начиная с первого символа, запускаем цифровую сортировку на строках, полученных из шаблона, + проверяемых строках.

В полученной последовательности шаблоны образуют скобочную последовательность. Все, что находится внутри скобок матчится с соответствующим шаблоном.

Из положительного, это сделать проще, когда строки не влезают в память. Число разрядов на сравнение можно ограничить длиной самого длинного шаблона.

Comments

[stas8]

Спасибо за ответ. Я попробовал реализовать через дерево префиксов. Правда, несколько иначе, чем вы описали. Вроде бы, код работает корректно, но недостаточно быстро. Не могли бы вы посмотреть, может, я что-то написал неверно или неэффективно? pastebin.com/DKZzhvXA

[SeptiM]

А пробовали профилировать? Тормозит на построении дерева или на запросах? Если первое, то по эффективности в глаза бросается поштучная аллокация объектов. Возможно имеет смысл избавиться от класса prefixTreeNode и аллоцировать несколько больших массивов для хранения вершин.

[stas8]

SeptiM, попробовал использовать массив. К сожалению, это не помогло. Значит, проблема, скорее всего в запросах matches().

[SeptiM]

Нужно все же прогнать через профайлер. Возьмите какой-нибудь YourKit, прогоните через него. Иначе будет гадание на кофейной гуще.

[stas8]

Обнаружил, в чём была проблема. Она была не в самом дереве префиксов. Узким местом было чтение данных. Класс Scanner, который я использовал для этого, работает слишком медленно из-за большого количества проверок на соответствие типов и т.п. (хоть я и читал лишь строки функцией nextLine() и, по идее, никакие проверки не были нужны). Стоило заменить Scanner на BufferedReader и всё заработало за приемлемое время.

[SeptiM]

Да, известное узкое место. Поздравляю! =)

Answer 2

[Rsa97]

Можно из шаблонов построить дерево или конечный автомат, каждую из строк достаточно будет прогнать один раз. Конечный автомат немного сложнее, зато его можно привести в минимальную форму, что ускорит сравнение.

Answer 3

[Сергей]

Вам нужно построить конечный автомат на вход которого будет подаваться поток символов, а на выходе которого будут признаки шаблона.
Одним словом вам нужно построить компилятор для компиляции шаблонов в конечный автомат.

Answer 4

[uvelichitel]

Aho–Corasick, trie?