algorithm - 如何像 Excel 一样发现和分析相似的模式？

Question

当您键入具有特定模式的 3 行并将该列一直向下拖动时，您知道 Excel 中的功能，Excel 会尝试为您继续该模式。

例如

类型...

• 测试-1
• 测试2
• 测试3

Excel 将继续:

• 测试4
• 测试5
• 测试-n...

同样适用于一些其他模式，例如日期等。

我正在尝试完成类似的事情，但我还想处理更多异常(exception)情况，例如:

• test-blue-somethingelse
• 测试-黄色-somethingelse
• test-red-somethingelse

现在基于这个条目我想说模式是:

• test-[DYNAMIC]-something

继续使用其他颜色的 [DYNAMIC] 是另一回事，我现在并不关心这个。我最感兴趣的是检测模式中的 [DYNAMIC] 部分。

我需要从大量池条目中检测到这一点。假设您有 10,000 个具有这种模式的字符串，您希望根据相似性对这些字符串进行分组，并检测文本的哪一部分在不断变化 ([DYNAMIC])。

文档分类在这种情况下很有用，但我不确定从哪里开始。

更新:

我忘了说也可以有多个 [DYNAMIC] 模式。

如:

• test_[DYNAMIC]12[DYNAMIC2]

我认为这不重要，但我计划在 .NET 中实现它，但任何有关要使用的算法的提示都会非常有帮助。

Answer 1

一旦您开始考虑寻找以下形式的模式的动态部分:<const1><dynamic1><const2><dynamic2>....如果没有任何其他假设，那么您将需要找到 longest common subsequence您提供的示例字符串。例如，如果我有 test-123-abc和 test-48953-defg那么濒海战斗舰就是test-和 - .动态部分将是 LCS 结果之间的差距。然后，您可以在适当的数据结构中查找您的动态部分。

寻找超过 2 个字符串的 LCS 的问题非常昂贵，这将是您问题的瓶颈。以准确性为代价，您可以使这个问题变得容易处理。例如，您可以在所有字符串对之间执行 LCS，并将具有相似 LCS 结果的字符串集组合在一起。但是，这意味着无法正确识别某些模式。

当然，如果您可以对字符串施加进一步的限制，那么所有这些都可以避免，就像 Excel 所做的那样，它似乎只允许 <const><dynamic> 形式的模式。 .