regex - 用于矩阵模式搜索的类正则表达式库

Question

是否有一个库（任何语言）可以在矩阵中搜索模式，如正则表达式适用于字符串？类似于矩阵的正则表达式或任何矩阵模式搜索方法？

score 1 · Accepted Answer

-:如果您不反对使用 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

match 运算符的一个很好的特性是您可以使用它来比较任意维度的数组。如果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 的重叠副本，并且仅标记一个像素可以让您看到每个匹配图块的位置。

score 0 · Accepted Answer

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

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

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

祝你好运！

score 0 · Accepted Answer

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

score 0 · Accepted Answer

我认为对于大于 1 的维度不存在任何类似于正则表达式的东西，但是如果你想匹配一个精确的模式而不是一类模式，那么我可能建议你阅读卷积（或者更确切地说是交叉相关）

原因是，有许多高度优化的库函数（例如 IPP）可以比您自己希望实现的速度更快。这种方法也可以扩展到更高的维度。

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

4 回答 4