我怎么可以检测公共子串在一个列表中的字符串

StackOverflow https://stackoverflow.com/questions/1410822

  •  05-07-2019
  •  | 
  •  

题

给予一个组串，例如：

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

我希望能够检测这些都是三套文件：

  • 条目[1,2]
  • J27[红色，绿色]P[1,2]
  • JournalP[1,2][红色、绿色、蓝色]

是否有任何已知的方式处理这一问题的任何发布的文件我能读在这个吗？

这办法我正在考虑是每个字符串看看所有其他串并找到共同的人物和不同的字符，试图找到集串具有最多共同点，但我恐怕，这不是非常有效的和可得到的误报。

注意，这是不一样的 '如何做我检测组的共同串在文件名' 因为，假定一串总是会有一系列的数字如下。

有帮助吗？

解决方案

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

有链接到的补充信息在外部的链接，包括Perl实现两个算法解释该条款。

编辑，以增加：

基于上述讨论，我仍然认为，最常见的字符串可以在心脏这一问题。甚至在《日刊》的例子中引注释，该定义特征，集substring'Journal'.

我首先考虑什么样的定义定为独立的其他集。给你你的分区划分的数据，那么问题是在计量有多少共同点存在一组。如果决定性特征是一个共同的子串，然后最长的公共子串将是一个合乎逻辑的起点。

自动化进程的设置检测，在一般情况下，你就需要对测量的共同点，你可以用它来衡量的'区别'之间所有可能对。然后你需要一个算法计算的分区结果的总体最低的总体差异。如果的差别措施不是最长的公共子串，这很好，但你需要确定什么它会。显然，这需要具体的东西，你可以衡量的。

铭记还的属性差测量将承担的算法可用来使分区。例如，假设的差异(X,Y)给出测量之间的差异X和Y。然后它可能会是有用的，如果你测量距离是这样的比较(A、C) <=差异(A、B)+差异(B、C)。显然差异(A、C)应该是相同的，因为差异(C)。

在思考这个，我也开始不知道是否我们可以想象的'区别'，作为一个间距离的任何两个串，并与一个严格定义的距离，然后我们可以尝试某种 群集分析 在输入串。只是一个想法。

其他提示

伟大的问题！步骤一个解决方案是：

  1. 切分 输入
  2. 使用标记，以建立一个合适的 数据结构.一个 耶 是理想的，但一个 Trie 更简单一个体面的起点。
  3. 可选后处理的数据结构的简化或群集的子树为单独的产出
  4. 化 数据结构 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. 建立一个特里代表所有你的琴弦。

在例如你给，将有两个边缘从根："E"和"J"。"J"分将分为"乔"和"J2"。

  1. 一个单一的股分叉，例如E-n-t-i-r-e-S-(fork1、2)表示的选择，因此将条目[1,2]

  2. 如果该股是"太短"关于叉，例如B-A-(fork N-一个和H-A-M)，我们列出了两个词("香蕉，巴哈马群岛")，而不是一种选择("ba[娜娜，哈马斯]")."太短了"可作为简单，因为"如果之后的部分叉的长度大于部分之前的"或可能加权数字具有一定的前缀。

  3. 如果两个子树是"足够相似的"然后可以将它们合并，这样，而不是树，你现在有一个大的曲线图。例如，如果你有ABRed,ABBlue,ABGreen,CDRed,CDBlue,CDGreen，您可能发现的子树植根在"AB"是一样的子树植根在"光盘"，这样你会合并他们。在你输出这会是这样的：[左支右分][树]，因此：[AB、CD][红色的，蓝色，绿色].如何处理子树，都是靠近但不完全相同？有可能是没有绝对的答案，但这里有人可以有一个良好的想法。

我是标志着这个回答社会wiki。请随时延长这样，一起，我们可以有一个合理的答案的问题。

有许多许多办法来串的相似性。我建议把一个看看这个公开来源库，实现了很多指标，如编辑的距离。

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

你应该能够实现这种广义的后缀树木：看起来长的路径中的后缀树哪些来自多个来源串。

试试"搞".它创造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]

然后开始组团体，可以相当快看到，前缀"整个"是一种常见的一些集团和所有子组S作为头，因此唯一的变量，对于那些为1,2.为J27种情况下你可以看到，J27只是叶，但是它随后在红色和绿色的。

所以somekind列表<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));
    }
}
许可以下： CC-BY-SA 和 归因
不隶属于 StackOverflow
scroll top