如何检测string列表中的常见子string
给定一组string，例如：
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] [红，绿，蓝]
是否有任何已知的方法来解决这个问题 – 我可以阅读的任何已发表的论文？
我正在考虑的方法是为每个string查看所有其他string，并查找常用字符以及不同字符的位置，试图查找具有最多共同string的string，但是我担心这不是非常有效，可能会给误报。
请注意，这与“如何检测文件名中的常用string组”是不一样的，因为它假定一个string总是有一系列的数字。
我会从这里开始： http : //en.wikipedia.org/wiki/Longest_common_substring_problem
在外部链接中有补充信息的链接，包括文章中解释的两种algorithm的Perl实现。
编辑添加：
基于这个讨论，我仍然认为最长公共子串可能是这个问题的核心。 即使在你的评论中你引用了Journal的例子，那个集合的定义特征就是子串“Journal”。
我首先会考虑什么定义一套与其他集合分开。 这就给了你分割数据的分区，然后问题就在于衡量一个集合中存在多less共同性。 如果定义的特征是一个共同的子string，那么最长公共子string将是一个合乎逻辑的起点。
为了自动化设置检测的过程，一般来说，您将需要一个成对的共同性度量标准，您可以使用它来度量所有可能的对之间的“差异”。 然后，您需要一个algorithm来计算分区，从而导致总体差异最小。 如果差异度量不是最长公共子string，那很好，但是你需要确定它是什么。 显然它需要具体的东西，你可以衡量。
请记住，差异度量的属性将影响可用于制作分区的algorithm。 例如，假设diff（X，Y）给出了X和Y之间差异的度量。那么，如果你的距离度量是diff（A，C）<= diff（A，B）+ diff （公元前）。 显然diff（A，C）应该和diff（C，A）一样。
考虑到这一点，我也开始怀疑，我们是否可以将“差异”看作任何两个string之间的距离，并且，通过严格的距离定义，我们可以尝试对inputstring进行某种聚类分析 。 只是一个想法。
像这样的东西可能工作。
- build立一个代表所有string的trie。
在你给出的例子中，根将有两个边：“E”和“J”。 然后“J”分支将分成“Jo”和“J2”。
-
一个分支，例如EntireS-（分叉到1,2）表示一个select，这将是EntireS [1,2]
-
如果股票相对于叉子“太短”，例如BA-（叉到NANA和HAMAS），我们列出两个词（“香蕉，巴哈马”）而不是select（“ba [nana，hamas]”） 。 “太短”可能就像“如果叉子之后的部分比之前的部分长”，或者可能由具有给定前缀的单词的数量加权那么简单。
-
如果两棵子树“足够相似”，那么它们可以合并，所以现在有一个通用图，而不是一棵树。 例如，如果您有ABRed，ABBlue，ABGreen，CDRed，CDBlue，CDGreen，您可能会发现以“AB”为根的子树与以“CD”为根的子树相同，因此您将合并它们。 在你的输出中，这看起来像这样：[左分支，右分支] [子树]，所以：[AB，CD] [红，蓝，绿]。 如何处理接近但不完全相同的子树？ 可能没有绝对的答案，但这里有人可能有一个好主意。
我正在标记这个答案社区维基。 请随意扩充，以便我们可以一起合理地回答这个问题。
string相似性有很多种方法。 我会build议看看这个开源库，它实现了像Levenshtein距离这样的很多指标。
好问题！ 解决scheme的步骤是：
- 标记input
- 使用令牌来构build适当的数据结构 。 DAWG是理想的，但Trie更简单，体面的起点。
- 可选的后处理数据结构，以便将子树简化或聚类成单独的输出
- 将数据结构串行化为 正则expression式或类似的语法
我已经在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))
你应该能够用通用的后缀树来实现这一点：在来自多个源string的后缀树中查找长path。
尝试“frak”。 它从一组string创build正则expression式。 也许有些修改会帮助你。 https://github.com/noprompt/frak
希望它有帮助。
对于这个特殊的string示例，可以考虑使用简单的字/数字分隔。
一个非数字序列显然可以以大写字母（Entire）开头。 把所有的string分解成一系列的序列之后，就像
[Entire][S][1] [Entire][S][2] [J][27][Red][P][1] [J][27][Green][P][1] [J][27][Red][P][2] .... [Journal][P][1][Blue] [Journal][P][1][Green]
然后开始按组进行分组，可以很快看到“整个”前缀对于某个组是常见的，并且所有的子组都有S作为头组，所以只有variables为1,2。 对于J27的情况，你可以看到J27只是叶子，但它然后在红色和绿色分支。
所以有一些List <Pair <list，string >> – 结构（复合模式，如果我记得正确）。
import java.util.*; class StringProblem { public List<String> subString(String name) { List<String> list=new ArrayList<String>(); for(int i=0;i<=name.length();i++) { for(int j=i+1;j<=name.length();j++) { String s=name.substring(i,j); list.add(s); } } return list; } public String commonString(List<String> list1,List<String> list2,List<String> list3) { list2.retainAll(list1); list3.retainAll(list2); Iterator it=list3.iterator(); String s=""; int length=0; System.out.println(list3); // 1 1 2 3 1 2 1 while(it.hasNext()) { if((s=it.next().toString()).length()>length) { length=s.length(); } } return s; } public static void main(String args[]) { Scanner sc=new Scanner(System.in); System.out.println("Enter the String1:"); String name1=sc.nextLine(); System.out.println("Enter the String2:"); String name2=sc.nextLine(); System.out.println("Enter the String3:"); String name3=sc.nextLine(); // String name1="salman"; // String name2="manmohan"; // String name3="rahman"; StringProblem sp=new StringProblem(); List<String> list1=new ArrayList<String>(); list1=sp.subString(name1); List<String> list2=new ArrayList<String>(); list2=sp.subString(name2); List<String> list3=new ArrayList<String>(); list3=sp.subString(name3); sp.commonString(list1,list2,list3); System.out.println(" "+sp.commonString(list1,list2,list3)); } }
