矩阵模式搜索的REGEXP库库
-
29-09-2019 - |
题
是否有(以任何语言)可以在矩阵中搜索模式(如正则表达式)对字符串工作?诸如矩阵的常规表现或任何矩阵模式搜索方法?
解决方案
如果您不反对使用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,其像素作为其上方的左角。这样做的原因是,Y中嵌入X的重叠副本可能是Y中的几个重叠副本,并且仅标记一个Pixel,您才能看到每个匹配的瓷砖的位置。
其他提示
只需使用Aho-Corasick(time O(矩阵大小))在输入矩阵的每一行中搜索图案的行。结果应该足够小,可以快速将其加入最终结果。
我认为没有什么像高于1的正则表达式的东西,但是如果您想匹配确切的模式而不是一类模式,那么我可能建议您阅读卷积(或更确切地说 互相关 )
原因是,有许多高度优化的图书馆功能(例如IPP)来执行此操作的速度比您希望自己实现的速度更快。同样,此方法也缩放到更高的维度。
另外,这不一定会给您一个“匹配”,而是相关图中的“峰”,如果该峰等于您要搜索的模式的平方系数之和,它将与匹配相对应。
不隶属于 StackOverflow