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

Pattern matching for strings independent from symbols

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

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

作为第二个示例,模式 abcd 应该 return 12 个匹配项(thistextisat 中的每个位置一个)。由于模式中没有变量重复,所以它在任何地方都可以简单匹配。即使在 texttest 的情况下,因为变量 ad 的模式映射到相同的符号。

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

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

我没有使用 Regex 来处理任何太复杂的事情,所以我不知道在 Regex 中是否可以做这样的事情,当你基本上不关心符号本身,而只考虑他们的出现。

非常感谢您的帮助!

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

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 并检查数字是否等于或小于。