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

Question

给定一组字符串，例如：

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

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

整个S[1,2]
J27[红,绿]P[1,2]
日志P[1,2][红、绿、蓝]

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

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

请注意，这与“如何检测文件名中的常见字符串组”不同，因为它假定字符串后面总是有一系列数字。

score 12 · Accepted Answer

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

考虑到这一点，我也开始怀疑我们是否可以将“差异”设想为任何两个字符串之间的距离，并且通过对距离的严格定义，我们是否可以尝试对输入字符串进行某种聚类分析. 只是一个想法。

score 10 · Accepted Answer

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

标记化输入
使用令牌构建适当的数据结构。DAWG是理想的，但Trie更简单，也是一个不错的起点。
数据结构的可选后处理，用于简化或将子树聚类为单独的输出
将数据结构序列化为正则表达式或类似语法

我已经在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))

score 3 · Accepted Answer

类似的东西可能会奏效。

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

在您给出的示例中，从根开始会有两条边：“E”和“J”。然后“J”分支将分成“Jo”和“J2”。

一个分叉的单链，例如 EntireS-(forks to 1, 2) 表示一个选择，所以这将是 EntireS[1,2]
如果链相对于分叉“太短”，例如 BA-（分叉到 NANA 和 HAMAS），我们列出两个词（“banana, bahamas”）而不是选择（“ba[nana,hamas]”） . “太短”可能就像“如果分叉之后的部分比之前的部分长”一样简单，或者可能由具有给定前缀的单词数加权。
如果两个子树“足够相似”，那么它们可以被合并，这样你现在就有了一个通用图，而不是一棵树。例如，如果您有 ABRed，ABBlue，ABGreen，CDRed，CDBlue，CDGreen，您可能会发现以“AB”为根的子树与以“CD”为根的子树相同，因此您将它们合并。在您的输出中，这将如下所示：[左分支，右分支][子树]，因此：[AB,CD][Red,Blue,Green]。如何处理接近但不完全相同的子树？可能没有绝对的答案，但这里有人可能有一个好主意。

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

score 2 · Accepted Answer

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

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

score 2 · Accepted Answer

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

希望能帮助到你。

score 1 · Accepted Answer

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

score 1 · Accepted Answer

提出了许多解决方案来解决寻找公共子串的一般情况。但是，这里的问题更专业。您正在寻找常见的前缀，而不仅仅是子字符串。这使它更简单一些。查找最长公共前缀的一个很好的解释可以在 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

score 0 · Accepted Answer

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

一个非数字序列显然可以以大写字母 (Entire) 开头。在将所有字符串分解为序列组之后，例如

[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 作为头组，因此这些组的唯一变量是 1,2。对于 J27 案例，您可以看到 J27 只是叶子，但它随后在红色和绿色处分支。

所以某种 List<Pair<list, string>> -结构（如果我没记错的话是复合模式）。

score 0 · Accepted Answer

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

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

9 回答 9

Related

Reference