如何检测字符串列表中的常见子字符串

http://en.wikipedia.org/wiki/Longest_common_substring_problem

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

编辑添加:

基于讨论,我仍然认为最长的常见子串可能是这个问题的核心。即使在您在注释中引用的日志示例中,该集合的定义特征也是子字符串“journal”。

我首先考虑什么定义了一个集合与其他集合是分开的。这就给了您划分数据的分区,然后问题在于度量一个集合中有多少共性。如果定义特征是一个公共子串,那么最长的公共子串将是一个逻辑起点。

为了自动化集合检测的过程,一般来说,您需要一个共性的成对度量,您可以使用它来度量所有可能的对之间的“差异”。然后您需要一个算法来计算导致总体最小总差的分区。如果差分度量不是最长的常用子字符串,那就没问题了,但是您需要确定它是什么。显然,它需要一些具体的东西,你可以测量。

还要记住,差分测量的特性将取决于可用于划分的算法。例如,假设diff(x,y)给出了x和y之间的差的度量,那么如果距离的度量是diff(a,c)<=diff(a,b)+diff(b,c),那么它可能会很有用。显然,diff(a,c)应该和diff(c,a)相同。

在考虑这一点时,我也开始怀疑我们是否可以把“差异”想象成任何两条弦之间的距离,并且,通过对距离的严格定义,我们是否可以尝试某种 cluster analysis 在输入字符串上。只是一个想法。

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

1. tokenizing 输入
2. 使用令牌构建适当的 data structure .一 DAWG 是理想,但 Trie 是一个简单而体面的起点。
3. 为简化子树或将子树聚类为单独输出而对数据结构进行的可选后处理
4. serialization 数据结构的 regular 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))

类似的事情可能会奏效。

1. 构建一个表示所有字符串的trie。

在您给出的示例中,从根开始有两条边:“e”和“j”。然后,“J”分支将分为“jo”和“j2”。

2. 分叉的单链,例如E-N-T-I-R-E-S-(分叉为1,2),表示一种选择,因此这将是实体[1,2]

3. 如果链相对于分叉“太短”,例如b-a-(分叉到n-a-n-a和h-a-m-a-s),我们列出两个单词(“香蕉,巴哈马”),而不是一个选项(“b a[纳纳,哈马斯”)。“太短”可能与“如果分叉后的部分比之前的部分长”一样简单,也可能由具有给定前缀的单词数加权。

4. 如果两个子树“足够相似”,那么可以合并它们,这样就可以有一个通用图而不是一个树。例如,如果您删除了abbred、abblue、abgreen、cdred、cdblue、cdgreen,您可能会发现在“ab”上根的子树与在“cd”上根的子树相同,因此您将合并它们。在您的输出中,这看起来像这样:【左分支,右分支】【子树】,所以:【AB,CD】【红,蓝,绿】。如何处理接近但不完全相同的子树?可能没有绝对的答案,但这里的人可能有一个好主意。

我正在标记这个答案社区wiki。请随意延长,以便我们一起对这个问题有一个合理的答案。

字符串相似性有很多种方法。我建议您看看这个开源库,它实现了许多度量,比如Levenshtein距离。

http://sourceforge.net/projects/simmetrics/

您应该能够使用通用后缀树来实现这一点:在后缀树中查找来自多个源字符串的长路径。

试试“FRAK”。它从一组字符串创建regex表达式。也许对它进行一些修改会对你有所帮助。 https://github.com/noprompt/frak

希望它有帮助。

有许多解决方案可以解决寻找公共子串的一般情况。然而,这里的问题更为专门化。您要查找的是通用前缀,而不仅仅是子字符串。这使它简单了一点。 查找最长公共前缀的一个很好的解释可以在 http://www.geeksforgeeks.org/longest-common-prefix-set-1-word-by-word-matching/

所以我建议的“pythonese”伪代码是这样的(请参阅链接以获取 find_lcp :

def count_groups(items):
  sorted_list = sorted(items)

  prefix = sorted_list[0]
  ctr = 0
  groups = {}
  saved_common_prefix = ""
  for i in range(1, sorted_list):
    common_prefix = find_lcp(prefix, sorted_list[i])
    if len(common_prefix) > 0: #we are still in the same group of items
      ctr += 1
      saved_common_prefix = common_prefix
      prefix = common_prefix
    else: # we must have switched to a new group
      groups[saved_common_prefix] = ctr
      ctr = 0
      saved_common_prefix = ""
      prefix = sorted_list[i]
  return groups

对于这个特殊的字符串示例,要保持它非常简单,请考虑使用简单的单词/数字分隔。

非数字序列显然可以以大写字母(整个)开头。把所有的字符串分成一组序列后,比如

[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]

然后开始按组分组,很快就会发现前缀“wholet”对于某些组来说很常见,并且所有子组都有s作为头组,所以这些组的唯一变量是1,2。 对于J27,您可以看到J27只是叶子,但它随后以红色和绿色分支。

所以某种类型的列表,对列表,字符串结构(如果我调用正确,则为复合模式)。

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));
    }
}