подобная регулярному выражению библиотека для поиска по шаблону матрицы

Question

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

Answer 1

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

   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.

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

 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

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

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

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

Answer 3

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

Answer 4

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

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

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

Удачи!