algorithm - 如何检测字符串列表中的公共(public)子字符串

Question

给定一组字符串，例如:

EFgreen
EFgrey
EntireS1
EntireS2
J27RedP1
J27GreenP1
J27RedP2
J27GreenP2
JournalP1Black
JournalP1Blue
JournalP1Green
JournalP1Red
JournalP2Black
JournalP2Blue
JournalP2Green

我希望能够检测到这是三组文件:

• 整个[1,2]
• J27[红,绿]P[1,2]
• JournalP[1,2][红、绿、蓝]

是否有解决此问题的任何已知方法 - 我可以阅读有关此问题的任何已发表论文？

我正在考虑的方法是为每个字符串查看所有其他字符串并找到共同字符和不同字符所在的位置，试图找到最共同的字符串集，但我担心这不是很有效并且可能会产生误报。

请注意，这与 'How do I detect groups of common strings in filenames' 不同因为这假设一个字符串后面总是跟有一系列数字。

Answer 1

我将从这里开始:http://en.wikipedia.org/wiki/Longest_common_substring_problem

外部链接中有指向补充信息的链接，包括文章中解释的两种算法的 Perl 实现。

编辑添加:

根据讨论，我仍然认为最长公共(public)子串可能是这个问题的核心。即使在您在评论中引用的 Journal 示例中，该集合的定义特征也是子字符串“Journal”。

我会首先考虑什么将集合定义为与其他集合分开。这给了你你的分区来划分数据，然后问题是衡量一个集合中存在多少共性。如果定义特征是公共(public)子串，那么最长公共(public)子串将是一个逻辑起点。

要使集合检测过程自动化，一般来说，您需要一种成对的共性度量，您可以使用它来衡量所有可能对之间的“差异”。然后，您需要一种算法来计算导致总体总差最低的分区。如果差异度量不是最长公共(public)子串，那很好，但是您需要确定它将是什么。显然，它需要是您可以衡量的具体事物。

另请记住，差异测量的属性将影响可用于进行分区的算法。例如，假设 diff(X,Y) 给出了 X 和 Y 之间差异的度量。那么如果您的距离度量是 diff(A,C) <= diff(A,B) + diff，它可能会很有用(公元前)。显然 diff(A,C) 应该与 diff(C,A) 相同。

考虑到这一点，我也开始怀疑我们是否可以将“差异”设想为任意两个字符串之间的距离，并且根据距离的严格定义，我们是否可以尝试某种 cluster analysis在输入字符串上。只是一个想法。