Библиотека, похожая на REGEXP для поиска рисунка матрицы

Question

Есть ли библиотека (на любом языке), которая может искать шаблоны в матрицах, таких как обычные выражения, работают на строки? Что -то вроде регулярных эксплуатаций для матриц или любых методов поиска с шаблоном матрицы?

Answer 1

Если вы не против использования J, вы можете выяснить, равны ли две матрицы, используя -: (матч) Оператор. Например:

   X =: 4 3 $ i.12
   X
0  1  2
3  4  5
6  7  8
9 10 11
   Y =: 4 3 $ (1+i.12)
   Y
 1  2  3
 4  5  6
 7  8  9
10 11 12
   X -: X
1
   X -: Y
0

Одна хорошая особенность оператора матча заключается в том, что вы можете использовать его для сравнения массивов произвольного измерения; если A это массив 3x3x4 и B это массив 2x1, тогда A-:B возврат 0.

Чтобы выяснить, является ли матрица подводной лодкой другой матрицы, вы можете использовать E: (член интервала) Оператор, как SO:

 X =: 2 2 $ 1 2 4 5  
   X
1 2
4 5
   Y =: 4 3 $ (1+i.12)
   Y
 1  2  3
 4  5  6
 7  8  9
10 11 12
   X E. Y
1 0 0
0 0 0
0 0 0
0 0 0

1 в левом верхнем углу результата означает, что часть y, равная x, имеет данный пиксель в качестве верхнего левого угла. Причиной этого является то, что может быть несколько перекрывающихся копий X, встроенных в Y, и только помещение одного пикселя позволяет вам увидеть местоположение каждой подходящей плитки.

Answer 2

Я нашел две вещи: gawk и perl сценарий

Это другая проблема, потому что работают регулярные выражения (например, работают (например, sed, grep) Рабочая линия за линией на одномерных строках.

Если ваши матрицы не являются одномерными (в основном векторов), эти программы и алгоритмы, которые они используют, не будут работать.

Удачи!

Answer 3

Просто найдите ряды шаблона в каждой строке входной матрицы, используя aho-corasick (время o (размер матрицы)). Результат должен быть достаточно маленьким, чтобы быстро присоединиться к его конечному результату.

Answer 4

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

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

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