regex - 独立于符号的字符串模式匹配

Question

我需要一种算法，它可以独立于数据和模式的实际符号/字符，在数据(以字符串形式存在)中找到预定义的模式。我只关心符号之间的关系，而不关心符号本身。对于数据中的相同符号具有不同的模式符号也是合法的。模式匹配算法必须强制执行的唯一一件事是保留模式中同一符号的多次出现。举个例子:

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

作为第二个示例，模式 abcd 应该返回 12 个匹配项(一个对应 thistextisat 中的每个位置)。由于模式中没有变量重复，所以它在任何地方都可以简单匹配。即使在 text 和 test 的情况下，因为模式的变量 a 和 d 是合法的映射到相同的符号。

该算法的目标应该是检测书面语言的相似性。想象一下，有一本英语词典，并使用 unseen 或等效的 1 2 3 4 4 2 模式对其进行解析。然后您会看到，例如，单词 belittle 包含相同的字母模式。

所以，既然我希望弄清楚我需要什么，我有一些问题:

• 这个算法叫什么？是已经解决的众所周知的问题吗？

• 是否有关于此事的出版物？当您不知道将此问题与常规模式匹配区分开来的正确搜索词时，真的很难找到任何有用的东西。

• 是否有现成的实现方案？

我没有将 Regex 用于任何太复杂的事情，所以我不知道在 Regex 中是否可以实现这样的事情，当你基本上不关心符号本身，而只考虑它们出现的模式时.

非常感谢您的帮助!

Answer 1

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

unseen
123442

这有六个字符，所以将文本中的每个单词索引为 6-mers

贬低

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 聚体，您就找到了匹配项。小于您的搜索词的任何 6 位数字也将是一个匹配项，以允许 abcd (1234) 大小写与 abca (1231) 单词匹配。

因此，给定一个包含 n 个字符的搜索词，只需将每个单词拆分为其组成的 n-mers，并检查数字是否等于或小于。