Вопрос по performance, algorithm, java, matrix – Быстрый подсчет двумерных субматриц с большой плотной двумерной матрицей?

4

Какой хороший алгоритм для подсчета подматриц в большой плотной матрице? Если бы у меня была одна строка данных, я мог бы использовать дерево суффиксов, но я не уверен, является ли обобщение дерева суффиксов в более высокие измерения совершенно простым или лучшим подходом здесь.

Мысли?

Мое наивное решение по индексированию первого элемента плотной матрицы и исключению поиска с полной матрицей обеспечило лишь небольшое улучшение по сравнению с сканированием с полной матрицей.

Какой лучший способ решить эту проблему?

Example:

Input:

Full matrix:
123
212
421

Search matrix:
12  
21  

Output:
2

Эта подматрица встречаетсядважды в полной матрице, поэтому вывод равен 2. Полная матрица может быть 1000x1000, однако, с матрицей поиска размером до 100x100 (переменный размер), и мне нужно обработать несколько матриц поиска в строке. Ergo, грубая сила этой проблемы слишком неэффективна, чтобы соответствовать моему подсекундному времени поиска нескольких матриц.

Во-вторых, постановка проблемы не ясна. Mebbe вы можете привести небольшой пример с ожидаемым результатом. akuhn
Вы имеете в виду считатьуникальный подматрицы? Rafał Dowgird
Я думаю, что он не подсчитывает уникальные подматрицы, а подсчитывает количество экземпляров, в которых данная матрица отображается как подматрица в большей - именно так работает пример Antti Huima
Добавил пример. Stefan Kendall
Вы хотитевсе субматрицы или только матрицы определенного размера, например квадрат в твоем примере? Вот верхняя граница первого:math.ucdavis.edu/~sonya/submatrix.pdf trashgod

Ваш Ответ

4   ответа
1

соответствие шаблона. Если у вас есть мотивация, вы, вероятно, можете преобразовать свой исходный массив с помощью БПФ и удалить журнал из поиска методом перебора. (Nlog (M)) вместо (NM)

3

^ 2 * log (размер алфавита). Учитывая подматрицу для поиска, в первую очередь дедуплицируйте ее строки. Теперь обратите внимание, что при поиске большой матрицы строка за строкой не более одной строки может появиться в любой позиции. Используйте Aho-Corasick для поиска во времени N ^ 2 * log (Размер алфавита) и запишите в каждой ячейке в большой матрице либо ноль, либо идентификатор для совпадающей строки подматрицы. Теперь снова используйте Aho-Corasick, чтобы искать вниз по столбцам этой матрицы совпадений строк и сигнализировать о совпадении, где все строки присутствуют друг под другом.

1

- Вы хотите очень быстрый поиск, сколько (времени) вы можете потратить на построение индексных структур? Когда перебор не достаточно быстр, вам нужны индексы.

- Что вы знаете о своих данных, которые вы не сообщили нам? Все ли значения во всех ваших матрицах однозначные целые числа?

- Если они представляют собой однозначные целые числа (или что-либо еще, что вы можете представить в виде одного символа или значения индекса), подумайте о линеаризации ваших 2D структур. Один из способов сделать это - прочитать матрицу вдоль диагонали, идущей сверху-справа-вниз-слева, и сканируя сверху-слева-внизу справа. Сложно объяснить словами, но почитать матрицу:

1234
5678
90ab
cdef

как 125369470c8adbef

(возьми?)

Теперь вы можете индексировать свою супер-матрицу на любую глубину, необходимую вашим требованиям к скорости и пространству; в моем примере ключ 1253 ... указывает на элемент (1,1), ключ abef указывает на элемент (3,3). Не уверен, что это работает для вас, и вам придется поиграться с параметрами вашего решения. Выберите свой любимый метод хранения пар ключ-значение: хеш, список или даже создайте некоторые индексы в индексе, если что-то не так.

С уважением

отметка

3

Рабина-Карпа Алгоритм поиска строк пришлось немного расширить, чтобы найти подходящую двумерную подматрицу так, как вы описываете.

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

При поиске матрицы N × N для матрицы M × M этот подход должен дать вам алгоритм O (N²⋅M). С трюками, я считаю, это может быть уточнено до O (N²).

Использование механизма хеширования для тестирования подстрок завершено4x быстрее в предварительном тестировании. Надеюсь, это достаточно эффективно, чтобы избежать более сложных алгоритмов поиска. Stefan Kendall
Я пробовал Knuth Morris Pratt на Rabin-Karp, но у меня были схожие результаты с моим набором данных. Это действительно был самый быстрый и легкий путь. Stefan Kendall

Похожие вопросы