矩阵模式搜索的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: （间隔成员）运营商这样：

 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，您才能看到每个匹配的瓷砖的位置。

Answer 2

我发现了两件事： gawk 和 perl 脚本。

这是一个不同的问题，因为字符串正则表达式起作用（例如， sed, grep）一维字符串的逐线工作。

除非您的矩阵是一维的（基本上是向量），否则这些程序和使用的算法将无法使用。

祝你好运！

Answer 3

只需使用Aho-Corasick（time O（矩阵大小））在输入矩阵的每一行中搜索图案的行。结果应该足够小，可以快速将其加入最终结果。

Answer 4

我认为没有什么像高于1的正则表达式的东西，但是如果您想匹配确切的模式而不是一类模式，那么我可能建议您阅读卷积（或更确切地说 互相关 )

原因是，有许多高度优化的图书馆功能（例如IPP）来执行此操作的速度比您希望自己实现的速度更快。同样，此方法也缩放到更高的维度。

另外，这不一定会给您一个“匹配”，而是相关图中的“峰”，如果该峰等于您要搜索的模式的平方系数之和，它将与匹配相对应。