如何检测字符串列表中的公共子字符串

Question

给定一组字符串,例如:

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

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

• EntireS [1,2]
• J27 [红色,绿色] P [1,2]
• JournalP [1,2] [红,绿,蓝]

有没有任何已知的方法来解决这个问题 - 我可以阅读任何已发表的论文吗？

我正在考虑的方法是每个字符串查看所有其他字符串并查找常见字符和不同字符的位置,尝试查找最常见的字符串集,但我担心这不是非常有效并且可能会给出误报.

请注意,这与"如何检测文件名中的常见字符串组"不同,因为它假定字符串后面始终有一系列数字.

Answer 1

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

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

编辑添加:

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

我首先考虑什么定义一个集合与其他集合分开.这为您提供了划分数据的分区,然后问题在于测量集合中存在多少共性.如果定义特征是公共子字符串,则最长公共子字符串将是逻辑起始点.

为了使集合检测过程自动化,通常需要成对的共性度量,您可以使用它来衡量所有可能对之间的"差异".然后,您需要一种算法来计算导致总体差异最小的分区.如果差异度量不是最长公共子串,那很好,但是你需要确定它将是什么.显然,它需要是一个可以衡量的具体事物.

还要记住,差异测量的属性将依赖于可用于制作分区的算法.例如,假设diff(X,Y)给出了X和Y之间差异的度量.那么如果你的距离测量值是diff(A,C)<= diff(A,B)+ diff,那么它可能会很有用. (公元前).显然,diff(A,C)应该与diff(C,A)相同.

考虑到这一点,我也开始怀疑我们是否可以将"差异"视为任意两个字符串之间的距离,并且通过严格定义距离,我们可以在输入字符串上尝试某种聚类分析.只是一个想法.

Answer 2

好问题!解决方案的步骤是:

1. 标记化输入
2. 使用令牌构建适当的数据结构.一个DAWG是理想的,但特里是简单和体面的起点.
3. 数据结构的可选后处理,以简化或将子树聚类为单独的输出
4. 将数据结构序列化为正则表达式或类似语法

我在regroup.py中实现了这种方法.这是一个例子:

$ cat | ./regroup.py --cluster-prefix-len=2
EFgreen
EFgrey
EntireS1
EntireS2
J27RedP1
J27GreenP1
J27RedP2
J27GreenP2
JournalP1Black
JournalP1Blue
JournalP1Green
JournalP1Red
JournalP2Black
JournalP2Blue
JournalP2Green
^D
EFgre(en|y)
EntireS[12]
J27(Green|Red)P[12]
JournalP[12](Bl(ack|ue)|(Green|Red))