字符串中的模式的符号表示,并找到"相似的"子模式

Question

字符串"abab"可以被认为是索引符号"0101"的模式.字符串"bcbc"也将由"0101"表示.这非常漂亮,可以进行强有力的比较,但它很快就会脱离完美的情况.

"babcbc"将是"010202".如果我想要注意它包含一个等于"0101"(bcbc部分)的模式,我只能考虑在每个索引处进行某种规范化处理,以便从符号上"重新表示"从n到长度的子字符串进行比较.如果我试图看看"babcbc"和"dababd"(010202 vs 012120)是否有任何共同之处,那就变得复杂了.效率低下!

如何有效地完成这项工作,处理所有可能的嵌套案例？请注意,我正在寻找类似的模式,而不是实际文本中的类似子字符串.

Answer 1

您的算法因压缩字符串的原始数据集而丢失了信息，因此我不确定您是否可以恢复完整的信息集，而无需做比比较原始字符串更多的工作。此外，虽然您的数据集看起来更易于人类阅读，但它当前占用的空间与原始字符串一样多，并且字符串的差异图（其中值是前一个字符和当前字符之间的距离）可能具有更具可比性的信息放。

但是，至于如何检测所有公共子集，您应该查看最不常见子序列算法以找到最大匹配模式。它是一个定义明确的算法并且非常高效——O(n * m)，其中 n 和 m 是字符串的长度。请参阅SO和Wikipedia上的 LCS。如果您还想查看环绕字符串的模式（作为循环搅拌 - 其中和应该匹配），那么您将需要一个圆形 LCS，Andy Nguyen在一篇论文中对此进行了描述。abeabeabab

您需要稍微更改算法以考虑到目前为止的变化数量。我的建议是向 LCS 表添加两个附加维度，表示两个原始字符串的过去 k 个字符中遇到的唯一数字的数量以及每个字符串的压缩版本。然后，您可以进行 LCS 求解，其中您始终朝着与压缩字符串相匹配的方向移动，并且在过去的 k 个字符的两个字符串中匹配相同数量的唯一字符。这应该对所有可能的唯一子字符串匹配进行编码。

棘手的部分始终是选择最大化包含相同数量的唯一字符的 k 的方向。因此，在 LCS 表的每个元素处，您都将进行额外的字符串搜索，以找到 k 值的最佳步骤。由于较长的序列总是包含所有可能的较小序列，因此如果您在每个步骤中最大化您的 k 个选择，您就会知道下一次迭代的最佳 k 至多 1 步之遥，因此一旦 4D 表填写完毕，它应该是可以以与原始 LCS 表类似的方式求解。请注意，因为您有一个 4D 表，所以逻辑确实会变得更加复杂，但是如果您阅读了 LCS 的工作原理，您将能够了解如何定义一致的规则以在每个步骤中向左上角移动。因此，LCS 算法保持不变，只是扩展到更多维度。

这个解决方案一旦完成就非常复杂，因此在开始编写这样的算法之前，您可能需要重新考虑您想要实现的目标/如果此模式编码了您实际想要的信息。