Как решить точное сопоставление с шаблоном

Question

Я пытаюсь решить проблему точного сопоставления с образцом, когда алфавит состоит из 5 символов {a, b, c, d, #}, где специальный символ # соответствует любому символу (включая самого себя).

Например, если T = ab # aca # ab # a и P = da # ac, то P начинается, начиная с позиции 3 в T. Я пытаюсь найти алгоритм времени O (nlogn), чтобы определить, является ли шаблон P длиныn встречается в тексте T длиной 2n, предполагая, что символ # встречается (возможно, O (n) раз) в T и P.

Есть предложения о том, как решить его с помощью свертки?

Answer 1

Я думаю, что вы можете решить проблему, как указано, для произвольных размеров алфавита, с учетом точности с плавающей запятой. Для алфавита из n символов сопоставьте текстовые символы с (сложными) n-ю корнями единицы. Для символов шаблона сопоставьте # с 0 и сопоставьте обычные символы с мультипликативной инверсией соответствующего символа текста, а также n-ными корнями единицы.

Затем вы используете теорему свертки для определения в каждой точке точечного произведения текста с этой точки с шаблоном. Если текст и шаблон совпадают, каждый компонент продукта равен либо 0 (подстановочный знак), либо 1 из r * r ^ -1, поэтому, если у вас есть совпадение, результатом будет m, где m - число не подстановочных знаков в шаблоне. Если нет совпадения, то не все компоненты скалярного произведения будут равны 1. Думая об этих комплексных числах как двухмерных векторах, скалярное произведение этих векторов с вектором, представляющим 1, будет меньше m, поэтому несоответствие не может привести к результату m и выглядеть как совпадение.

Замечу, что если вы разделите текст на буферы, длина которых в несколько раз превышает длину шаблона, вы можете использовать БПФ такой длины достаточно эффективно, поэтому сложность не равна n log n, где n - длина текст для поиска, но n log m, где m - длина шаблона. Несмотря на это, мне нужно будет увидеть время тестирования, прежде чем я пойму, что это конкурентный метод по сравнению даже с наивным поиском.

Answer 2

У меня есть одна идея, как это сделать.

Рассчитать функцию взаимной корреляции между T и P. Это делается путем свертки T и P. Для длинных сигналов свертка наиболее эффективно выполняется с помощью быстрого преобразования Фурье, и для этого требуется время, пропорциональное N * log (N):

Кросс-корреляция
свертка
Быстрое преобразование Фурье

Затем найдите максимум функции взаимной корреляции. Он покажет положение, в котором Т и Р выровнены.

Свертка должна обрабатывать "#" как особый случай, и, если P не гарантированно найден в T, это должно быть явно проверено в конце.

Answer 3

Алгоритм BNDM может обрабатывать символы подстановки, , так как эта реализация показывает , и соответствует вашему требованию скорости в среднем случае. Тем не менее, он имеет O (нм) сложность в худшем случае.

Почему именно здесь требуется свертка?