Как определить общие подстроки в списке строк

Ответ 1

Я бы начал здесь: http://en.wikipedia.org/wiki/Longest_common_substring_problem

Есть ссылки на дополнительную информацию во внешних ссылках, включая реализацию Perl двух алгоритмов, описанных в статье.

Отредактировано для добавления:

Основываясь на обсуждении, я по-прежнему думаю, что самая большая общая подстрока может быть в центре этой проблемы. Даже в примере Журнала вы ссылаетесь в своем комментарии, определяющей характеристикой этого набора является подстрока "Журнал".

Сначала я рассмотрю, что определяет набор как отдельный от других множеств. Это дает вам раздел для разделения данных, а затем проблема заключается в измерении того, насколько общность существует в наборе. Если определяющий признак является общей подстрокой, то самая длинная общая подстрока будет логической отправной точкой.

Для автоматизации процесса обнаружения множества, в общем, вам понадобится парная мера общности, которую вы можете использовать для измерения "разницы" между всеми возможными парами. Затем вам нужен алгоритм для вычисления раздела, который приводит к общей минимальной суммарной разности. Если разностная мера не является самой длинной общей подстрокой, это прекрасно, но тогда вам нужно определить, что это будет. Очевидно, что это должно быть нечто конкретное, что вы можете измерить.

Имейте в виду также, что свойства вашего разностного измерения будут иметь отношение к алгоритмам, которые можно использовать для создания раздела. Например, предположим, что diff (X, Y) дает меру разницы между X и Y. Тогда это, вероятно, было бы полезно, если бы ваша мера расстояния была такой, что diff (A, C) <= diff (A, B) + Diff (В, С). И, очевидно, diff (A, C) должен быть таким же, как diff (C, A).

Обдумывая это, я также начинаю задаваться вопросом, можем ли мы представить себе "разницу" как расстояние между любыми двумя строками и, при строгом определении расстояния, можем ли мы затем попытаться сделать что-то вроде кластерный анализ на входных строках. Просто мысль.

Ответ 2

Существует много разных подходов к сходству строк. Я бы предложил взглянуть на эту библиотеку с открытым исходным кодом, которая реализует множество показателей, таких как расстояние Левенштейна.

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

Ответ 3

Что-то вроде этого может работать.

• Создайте три, которые представляют все ваши строки.

В примере, который вы указали, из корня будут два ребра: "E" и "J". Затем ветвь "J" разделилась на "Jo" и "J2".

2. Одна нить, которая вилки, например. E-n-t-i-r-e-S- (forks to 1, 2) указывает на выбор, так что это будет EntireS [1,2]

3. Если нить "слишком короткая" относительно вилки, например. B-A- (вилки N-A-N-A и H-A-M-A-S), мы перечислим два слова ( "банан, бахамы" ), а не выбор ( "ba [nana, hamas]" ). "Слишком короткий" может быть таким же простым, как "если часть после того, как вилка длиннее, чем часть раньше" или, может быть, взвешена по количеству слов, которые имеют данный префикс.

4. Если два поддерева "достаточно схожи", то они могут быть объединены, так что вместо дерева у вас теперь есть общий граф. Например, если у вас есть ABRed, ABBlue, ABGreen, CDRed, CDBlue, CDGreen, вы можете обнаружить, что поддерево, основанное на "AB", такое же, как и поддерево, установленное на "CD", поэтому вы объедините их. В вашем представлении это будет выглядеть так: [левая ветвь, правая ветвь] [поддерево], поэтому: [AB, CD] [красный, синий, зеленый]. Как иметь дело с поддеревьями, которые близки, но не совсем то же самое? Вероятно, нет абсолютного ответа, но у кого-то здесь может быть хорошая идея.

Я отмечаю эту вики сообщества ответов. Пожалуйста, не стесняйтесь распространять его так, чтобы вместе мы могли получить разумный ответ на этот вопрос.

Ответ 4

Отличный вопрос! Шаги к решению:

• tokenizing ввод
• с использованием токенов для создания соответствующей структуры . a DAWG идеально, но Trie проще и достойная отправная точка.
• дополнительная пост-обработка структуры данных для упрощения или кластеризации поддеревьев на отдельные выходы
• serialization структуры данных в регулярное выражение или аналогичный синтаксис

Я реализовал этот подход в 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))

Ответ 5

Вы должны иметь возможность добиться этого с помощью обобщенных деревьев суффикса: найдите длинные пути в дереве суффиксов, которые поступают из нескольких строк источника.

Ответ 6

попробуйте "frak". Он создает выражение регулярного выражения из набора строк. Возможно, какая-то модификация этого поможет вам. https://github.com/noprompt/frak

Надеюсь, что это поможет.

Ответ 7

Для этого конкретного примера строк, чтобы держать его чрезвычайно простым, рассмотрим использование простого слова/цифры-разделителя.

Незнакомая последовательность, по-видимому, может начинаться с заглавной буквы (Весь). Разбив все строки на группы последовательностей, что-то вроде

[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 - это только лист, но затем он разветвляется на красный и зеленый.

Итак, некоторые из List < Pair < list, string → > -структура (составной шаблон, если я правильно помню).

Ответ 8

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

Ответ 9

Существует множество решений, которые разрешают общий случай нахождения общих подстрок. Однако проблема здесь более специализирована. Вы ищете общие префиксы, а не подстроки. Это делает его немного проще. Хорошее объяснение поиска самого длинного общего префикса можно найти в 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