regexp-подобная библиотека для поиска по матричным шаблонам
Существует ли библиотека (на любом языке), которая может искать шаблоны в матрицах, например регулярные выражения, для строк? Что-то вроде регулярных выражений для матриц или какого-либо метода поиска по матричным шаблонам?
4 ответа
Если вы не прочь использовать 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: (член интервала) следующим образом:
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, и только отметка одного пикселя позволяет увидеть расположение каждой совпадающей плитки.
Я обнаружил две вещи: gawk и perl ] скрипт.
Это другая проблема, потому что строковые регулярные выражения работают (например, sed , grep ) построчно работают с одномерными строками.
Если ваши матрицы не одномерные (в основном векторы), эти программы и используемые ими алгоритмы не будут работать.
Удачи!
Просто найдите строки шаблона в каждой строке входной матрицы, используя Aho-Corasick (время O (размер матрицы)). Результат должен быть достаточно маленьким, чтобы быстро объединить его в окончательный результат.
Я не думаю, что существует что-то похожее на регулярные выражения для размеров выше 1, но если вы хотите сопоставить точный шаблон, а не класс шаблонов, я мог бы предложить вам прочитать о свертке (или, скорее, Взаимная корреляция )
Причина в том, что существует множество высокооптимизированных библиотечных функций (например, IPP), позволяющих делать это быстрее, чем вы могли бы когда-либо надеяться достичь самостоятельно. Также этот метод масштабируется до более высоких измерений.
Кроме того, это не обязательно даст вам «совпадение», а скорее «пик» на карте корреляции, который будет соответствовать совпадению, если этот пик равен сумме квадратов коэффициентов шаблона, который вы ищете. за.