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

问题描述 投票：40回答：9

给定一组字符串，例如：

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] [红，绿，蓝]

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

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

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

algorithm pattern-matching
9个回答
10
投票

我会从这里开始：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）相同。

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

5
投票

好问题！解决方案的步骤是：

  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))
2
投票

这样的事可能有用。

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

在你给出的例子中，根将有两条边：“E”和“J”。然后“J”分支将分成“Jo”和“J2”。

  1. 单股分叉，例如EntrieS-（分叉到1,2）表示选择，因此这将是EntrieS [1,2]
  2. 如果股线相对于叉子“太短”，例如B-A-（分叉到N-A-N-A和H-A-M-A-S），我们列出两个词（“香蕉，巴哈马”）而不是一个选择（“ba [nana，hamas]”）。 “太短”可能就像“如果叉子之后的部分比之前的部分长”，或者可能通过具有给定前缀的单词数加权。
  3. 如果两个子树“足够相似”，那么它们可以合并，这样您就可以使用一般图形而不是树。例如，如果您有ABRed，ABBlue，ABGreen，CDRed，CDBlue，CDGreen，您可能会发现以“AB”为根的子树与以“CD”为根的子树相同，因此您将合并它们。在你的输出中，它将如下所示：[左分支，右分支] [子树]，所以：[AB，CD] [红色，蓝色，绿色]。如何处理接近但不完全相同的子树？可能没有绝对的答案，但这里有人可能有个好主意。

我正在为这个答案社区维基做标记。请随意扩展它，以便我们可以对这个问题有一个合理的答案。

2
投票

字符串相似性有很多种方法。我建议看看这个开源库，它实现了许多指标，如Levenshtein距离。

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

1
投票

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

1
投票

尝试“frak”。它从字符串集创建正则表达式。也许对它的一些修改会对你有所帮助。 https://github.com/noprompt/frak

希望能帮助到你。

1
投票

提出了许多解决方案来解决寻找共同子串的一般情况。但是，这里的问题更加专业。您正在寻找共同的前缀，而不仅仅是子串。这使它更简单一些。可以在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
0
投票

对于这个特殊的字符串示例，考虑使用简单的字/数字分离，使其非常简单。

非数字序列显然可以以大写字母（整数）开头。在将所有字符串分成序列组之后，类似于

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

然后开始按组分组，你很快就可以看到前缀“Entire”对于某些组是常见的，并且所有子组都有S作为headgroup，因此只有那些变量为1,2。对于J27案例，您可以看到J27只是叶子，但它然后以红色和绿色分支。

所以List <Pair <list，string >> -structure（复合模式，如果我没记错）。

0
投票
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));
    }
}
最新问题
© www.soinside.com 2019 - 2024. All rights reserved.