字符串模式匹配与符号无关

Question

我需要一种算法，能够在数据中（以字符串形式存在）找到预定义的模式，与数据和模式的实际符号/字符无关，我只关心符号之间的关系，而不是它们本身。在数据中，相同符号可以有不同的模式符号。模式匹配算法唯一需要强制执行的是保留模式中相同符号的多个出现次数。举个例子：

模式是“abca”，所以第一个和最后一个字母相同。对于我的应用程序，等效的写法是“1 2 3 1”，其中数字只是变量。我的数据是“thistextisatest”。结果算法应该给我这里两个正确的匹配，“text”和“test”。因为只有在这两种情况下，第一个和第四个字母才与模式中相同。

作为第二个例子，模式“abcd”应该返回12个匹配项（每个位置都有一个）。由于模式中没有重复的变量，它在任何地方都很容易匹配。即使在“text”和“test”的情况下，因为模式的变量“a”和“d”映射到相同的符号是合法的。

这个算法的目标应该是检测书面语言中的相似之处。想象一下拥有英语词典并使用模式“unseen”或等效的“1 2 3 4 4 2”解析它。然后，您会发现，例如，单词“belittle”包含相同的字母模式。

所以，现在我希望能够清楚地表达我的需求，我有一些问题：

• 这个算法叫什么？这是一个已经解决的众所周知的问题吗？
• 是否有相关出版物？当你不知道正确的搜索术语来将此问题与常规模式匹配分开时，很难找到任何有用的东西。
• 是否有现成的实现？

我没有在Regex中使用过任何太复杂的内容，因此我不知道是否可能在Regex中实现这样的内容，当你基本上不关心符号本身，而只考虑其出现的模式时。

我非常感谢您的帮助！

- mOfl

---

很有趣。但是，你可以使用正则表达式匹配所有内容。首先，(.).{2}\1（或者((.).{2}\2)更好地捕获文本）将返回“test”和“text”（https://regex101.com/r/cV7bD1/3），其次，`(?=(.{4}))`将返回12个您感兴趣的匹配项（https://regex101.com/r/cV7bD1/2）。因此，主要问题可能是将模式转换为数字，检查重复数字并创建相应的正则表达式。 - Wiktor Stribiżew

我理解你的建议，但这对我来说似乎更像是最后的手段，如果我必须从每个模式（其中将有数百万个）生成一个正则表达式。当然，更方便的方法是拥有某种通配符正则表达式（或完全不同的算法），可以处理所有实例。 - mOfl

Answer 1

我认为您在这里不需要正则表达式。您的搜索词：

unseen
123442

这句话有六个字符，所以将文本的每个单词分成6个字母为一组的序列。

贬低

12,12,12,12,11,12,12 2-mers
123,123,123,122,112,123 3-mers
1234,1234,1233,1223,1123 4-mers
12345,12344,12334,12234 5-mers
123455,123442,123321 6-mers

仅查看6-mer，您就可以找到匹配项。任何小于搜索项的6位数字也将匹配，以允许abcd（1234）匹配abca（1231）单词的情况。

因此，对于一个n个字符的搜索项，只需将每个单词拆分为其组成的n-mer，并检查是否为数字相等或更小。

- user1717259

---

谢谢您的建议！通过您的例子，您指出的是，无论数据有多少个字母，如果将其分割成n-mer，则始终可以找到模式（具有相同变量编号）。我现在看到这也可以轻松地进行子模式匹配，因为您也可以构建模式的n-mer。 - mOfl