如何发现和分析像Excel这样的类似模式呢？

Question

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

例如

类型...

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

Excel将继续使用:

• 测试-4-
• 测试-5-
• 测试-N ...

对于某些其他模式(例如日期等)也是如此.

我正在尝试完成类似的事情,但我也想处理更多例外情况,例如:

• 测试蓝somethingelse
• 测试 - 黄 - somethingelse
• 测试 - 红 - somethingelse

现在根据这些条目我想说的模式是:

• 测试 - [动态] -something

继续[动态]与其他颜色完全是另一笔交易,我现在并不在乎.我最感兴趣的是检测模式中的[DYNAMIC]部分.

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

文档分类在这种情况下很有用,但我不知道从哪里开始.

更新:

我忘了提到它也可能有多个[DYNAMIC]模式.

如:

• test_ [DYNAMIC] 12 [DYNAMIC2]

我认为这不重要,但我打算在.NET中实现这一点,但任何关于使用算法的提示都会非常有用.

Answer 1

一旦您开始考虑查找以下形式的模式的动态部分： <const1><dynamic1><const2><dynamic2>....在没有任何其他假设的情况下，您就需要找到您提供的示例字符串的最长公共子序列。例如，如果我有test-123-abc，test-48953-defg那么 LCS 将test-是-。动态部分将是 LCS 结果之间的差距。然后，您可以在适当的数据结构中查找动态部分。

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

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