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

Я пытаюсь решить проблему точного сопоставления с образцом, когда алфавит состоит из 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.

Любые предложения о том, как решить это с помощью свертки?


algorithm convolution signal-processing complexity-theory
person Community    schedule 23.10.2011    source источник
comment
Насколько велик ваш алфавит? Я знаю довольно простой способ сделать это, который добавляет коэффициент, пропорциональный размеру алфавита, к временной сложности, поэтому он довольно хорош для небольших алфавитов (например, ДНК).   -  person j_random_hacker    schedule 24.10.2011
comment
Я только что заметил непринятие. Вы заметили что-то, что я пропустил? Если да, то мне было бы интересно узнать об этом и извлечь из этого уроки.   -  person mcdowella    schedule 05.11.2011

Ответы (3)


arrow_upward
7
arrow_downward

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

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

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

person mcdowella    schedule 24.10.2011

arrow_upward
0
arrow_downward

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

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

person thiton    schedule 24.10.2011

arrow_upward
0
arrow_downward

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

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

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

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

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

person Alexey Frunze    schedule 24.10.2011