#algorithm #complexity-theory #signal-processing #convolution
#алгоритм #сложность-теория #обработка сигналов #свертка
Вопрос:
Я пытаюсь решить проблему точного сопоставления с образцом, когда алфавит состоит из 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.
Любые предложения о том, как решить это с помощью свертки?
Комментарии:
1. Насколько велик ваш алфавит? Я знаю довольно простой способ добиться этого, который добавляет коэффициент, пропорциональный размеру алфавита, к временной сложности, поэтому он довольно хорош для небольших алфавитов (например, ДНК).
2. Я только что заметил ошибку. Вы заметили что-то, что я пропустил? Если это так, мне было бы интересно услышать об этом и извлечь из этого уроки.
Ответ №1:
Я думаю, вы можете справиться с проблемой, как указано, для произвольных размеров алфавита с учетом точности с плавающей запятой. Для алфавита из n символов сопоставьте текстовые символы с (комплексными) n-мя корнями из единицы. Для символов шаблона сопоставьте # с 0 и сопоставьте обычные символы с мультипликативной инверсией соответствующего текстового символа, а также с n-мя корнями из единицы.
Затем вы используете теорему о свертке, чтобы в каждой точке вычислить скалярное произведение текста с этой точки на шаблон. Если текст и шаблон совпадают, каждый компонент продукта равен либо 0 (с подстановочной картой), либо 1, начиная с r * r ^ -1, поэтому, если у вас есть совпадение, результатом будет m, где m — количество символов, не являющихся подстановочными знаками в шаблоне. Если совпадения нет, то не все компоненты скалярного произведения будут равны 1. Думая об этих комплексных числах как о 2-мерных векторах, скалярное произведение этих векторов с вектором, представляющим 1, будет меньше m, поэтому несоответствие не может привести к результату m и выглядеть как совпадение.
Я отмечаю, что если вы разделите текст на буферы, длина которых в несколько раз превышает длину шаблона, вы можете достаточно эффективно использовать БПФ такой длины, поэтому сложность составляет не n log n, где n — длина текста для поиска, а n log m, где m- длина шаблона. Несмотря на это, мне нужно было бы увидеть время тестирования, прежде чем я поверю, что это конкурентный метод, по сравнению даже с наивным поиском.
Ответ №2:
Алгоритм BNDM может работать с подстановочными знаками, как показывает эта реализация, и в среднем соответствует вашим требованиям к скорости. Однако он имеет сложность O (nm) в наихудшем случае.
Почему именно вам здесь требуется свертка?
Ответ №3:
У меня есть одна идея, как это сделать.
Вычислите функцию взаимной корреляции между T и P. Это делается путем свертки T и P. Для длинных сигналов свертка наиболее эффективно выполняется с помощью быстрого преобразования Фурье, и для этого требуется время, пропорциональное N * log (N):
Взаимная корреляция
Свертка
Быстрое преобразование Фурье
Затем найдите максимум функции взаимной корреляции. Он укажет положение, в котором T и P выровнены.
Свертка должна будет обрабатывать «#» как особый случай, и, если не гарантируется, что P будет найдено в T, это должно быть явно проверено в конце.