Как я могу обнаружить общие подстроки в списке строк

Question

Дан набор строк, например:

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

Я хочу быть в состоянии обнаружить, что это три набора файлов:

• заходы [1,2]
• J27 [красный, зеленый] Р [1,2]
• JournalP [1,2] [красный, зеленый, синий]

Существуют ли какие-либо известные способы решения этой проблемы - какие-либо опубликованные статьи, которые я могу прочитать по этому вопросу?

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

Обратите внимание, что это не то же самое, что 'Как определить группы общих строк в именах файлов' , потому что это предполагает, что строка всегда будет иметь последовательность цифр после нее.

Answer 1

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

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

Отредактировано, чтобы добавить:

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

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

Чтобы автоматизировать процесс обнаружения множества, в общем, вам понадобится парная мера общности, которую вы можете использовать для измерения «разницы» между всеми возможными парами. Затем вам понадобится алгоритм для вычисления раздела, который приведет к общей наименьшей общей разнице. Если мера разности не Longest Common Substring, это нормально, но тогда вам нужно определить, что это будет. Очевидно, это должно быть что-то конкретное, что вы можете измерить.

Помните также, что свойства вашего измерения различий будут зависеть от алгоритмов, которые можно использовать для создания раздела. Например, предположим, что diff (X, Y) дает меру разницы между X и Y. Тогда, вероятно, было бы полезно, если бы ваша мера расстояния была такой, что diff (A, C) <= diff (A, B) + diff (ДО НАШЕЙ ЭРЫ). И, очевидно, diff (A, C) должен быть таким же, как diff (C, A). </p>

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

Answer 2

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

1. токенизация ввод
2. с использованием токенов для построения соответствующей структуры данных . DAWG идеален, но Trie проще и является хорошей отправной точкой.
3. необязательная пост-обработка структуры данных для упрощения или кластеризации поддеревьев в отдельные выходные данные
4. сериализация структуры данных в регулярное выражение или аналогичный синтаксис

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

Answer 3

Нечто подобное может сработать.

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

В приведенном вами примере от корня будет два ребра: "E" и "J". Тогда ветвь «J» разделится на «Джо» и «J2».

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

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

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

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

Answer 4

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

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

Answer 5

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

Answer 6

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

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

Answer 7

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

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

Answer 9

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

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

[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 > (составной шаблон, если я правильно помню).