当您键入具有特定模式的 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 中实现它，但任何有关要使用的算法的提示都会非常有帮助。
最佳答案
一旦您开始考虑寻找以下形式的模式的动态部分:<const1><dynamic1><const2><dynamic2>....如果没有任何其他假设，那么您将需要找到 longest common subsequence您提供的示例字符串。例如，如果我有 test-123-abc和 test-48953-defg那么濒海战斗舰就是test-和 - .动态部分将是 LCS 结果之间的差距。然后，您可以在适当的数据结构中查找您的动态部分。
寻找超过 2 个字符串的 LCS 的问题非常昂贵，这将是您问题的瓶颈。以准确性为代价，您可以使这个问题变得容易处理。例如，您可以在所有字符串对之间执行 LCS，并将具有相似 LCS 结果的字符串集组合在一起。但是，这意味着无法正确识别某些模式。
当然，如果您可以对字符串施加进一步的限制，那么所有这些都可以避免，就像 Excel 所做的那样，它似乎只允许 <const><dynamic> 形式的模式。 .
关于algorithm - 如何像 Excel 一样发现和分析相似的模式？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/1389135/