Все вхождения одной матрицы в другую

[tlf]

Даны две бинарные (состоящие только из 0 и 1) матрицы. Какими способами (кроме банального брутфорса) можно найти все вхождения одной матрицы в другую?

[Maslov]

Если поиск однократный, то единственное, что приходит на ум - это искать брутфорсом, слегка модифицированным аналогично алгоритму Бойера — Мура поиска строки в подстроке.
Если надо искать несколько матриц $M\times N$ в матрице $P\times Q$, то можно попробовать сформировать новую матрицу $(P-M+1)\times(Q-N+1)$, поместив в ячейку $(i,j)$ хэш, рассчитанный по подматрице $[i..i+M-1, j..j+N-1]$ исходной матрицы. После этого можно сравнивать не элементы матриц, а хэши, и проверять равенство элементов только если хэши совпали.
В любом случае, целезообразность использования того или иного способа надо оценивать "по месту"

[PAV]

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

[tlf]

Поиск однократный (то есть ищутся все вхождения в данную матрицу только одной данной подматрицы).

Цитата:

Если поиск однократный, то единственное, что приходит на ум - это искать брутфорсом, слегка модифицированным аналогично алгоритму Бойера — Мура поиска строки в подстроке.

Можно подробнее? Вы предлагаете представить матрицы в виде строк?

Цитата:

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

Боюсь, что это бессмысленно: в 63 случаях из 64 придётся работать с битами из двух разных цепочек. Займёт ещё больше времени.
Хотя идея интересная. При необходимости минимизировать выделяемую память имела бы смысл. Быть может, идея имеет смысл при наличии некоторых эвристик-предположений о входных данных (например, если предположить, что обе матрицы состоят в основном из огромных нулевых или единичных кусков).

Существует ещё вариант (описанный в статье "Efficient Processing for Binary Submatrix Matching" -- http://www.scipub.org/fulltext/ajas/ajas6178-88.pdf):
Например, есть матрица

0 0 0 0 1 1
1 1 1 1 1 1
1 1 0 0 1 1
0 0 1 1 0 1
0 0 0 0 1 1
1 1 1 0 0 0

Она представляется в виде

4 2
0 6
0 2 2 2
2 2 1 1
4 2
0 3 3

(то есть 4 нуля, 2 единицы, 0 нулей, 6 единиц, и так далее)

Аналогично представляется искомая подматрица. Это просто.
А далее “matrix submatching algorithm” по построенным матрицам выглядит громоздким и плохо, сумбурно описанным. Может быть, у кого-нибудь есть лучший вариант (если вдобавок реализованный на языке программирования -- ещё лучше)?

[Maslov]

tlf в сообщении #253031 писал(а):

Цитата:
Если поиск однократный, то единственное, что приходит на ум - это искать брутфорсом, слегка модифицированным аналогично алгоритму Бойера — Мура поиска строки в подстроке.

Можно подробнее? Вы предлагаете представить матрицы в виде строк?

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

0 0 0 1

а первая строка большей

0 0 1 0 . . .

то после обнаружения несовпадения в позиции 2 (считая с 0), мы можем сдвинуть "окно" не в позицию 1, а сразу в позицию 3.

-- Пн окт 19, 2009 19:40:06 --

Для этого перед началом поиска меньшую матрицу надо обсчитать аналогично тому, как это делается с образцом в алгоритме Бойера-Мура.

[PAV]

tlf в сообщении #253031 писал(а):

Боюсь, что это бессмысленно: в 63 случаях из 64 придётся работать с битами из двух разных цепочек. Займёт ещё больше времени.

Нет, Вы ошибаетесь. Смотрите. Допустим, мы работаем с 64-битными целыми. Пусть первые 64 элемента первой строки матрицы записаны в переменной a, следующие 64 бита - в b, а первые 64 бита первой строки искомой подматрицы записаны в v.

Пусть мы хотим проверить, совпадают ли 64 бита подматрицы с битами основной матрицы начиная, скажем, с 10-й позиции. Для этого нужно сравнить v со следующим значением:

(a<<10)|(b>>54)

То есть сравнение 64 бит происходит одновременно и на него тратится всего два сдвига, один побитовый OR и одно сравнение 64-битных целых. Учтите также, что побитовые операции - самые быстрые в процессоре, быстрее арифметических. Это будет работать в десятки раз быстрее, чем сравнивать по одному биту.