Как я могу определить общие подстроки в списке строк
https://stackoverflow.com/questions/1410822
-
05-07-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianВопрос
Учитывая набор строк, например:
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.
Отредактировано для добавления:
Основываясь на обсуждении, я все еще думаю, что в основе этой проблемы может лежать самая длинная общая подстрока.Даже в примере журнала, на который вы ссылаетесь в своем комментарии, определяющей характеристикой этого набора является подстрока 'Journal'.
Сначала я бы рассмотрел, что определяет набор как отдельный от других наборов.Это дает вам ваш раздел для разделения данных, и тогда проблема заключается в измерении того, насколько много общего существует внутри набора.Если определяющей характеристикой является общая подстрока, то логической отправной точкой будет самая длинная общая подстрока.
Чтобы автоматизировать процесс определения множества, в общем случае вам понадобится попарная мера общности, которую вы можете использовать для измерения "разницы" между всеми возможными парами.Затем вам нужен алгоритм для вычисления раздела, который приводит к общей наименьшей суммарной разнице.Если мерой различия не является Самая длинная общая подстрока, это нормально, но тогда вам нужно определить, какой она будет.Очевидно, что это должно быть что-то конкретное, что вы можете измерить.
Имейте также в виду, что свойства вашего измерения разницы будут зависеть от алгоритмов, которые могут быть использованы для создания раздела.Например, предположим, что diff(X,Y) дает меру разницы между X и Y.Тогда, вероятно, было бы полезно, если бы ваша мера расстояния была такой, чтобы diff(A, C) <= разница (A,B) + разница(B, C).И очевидно, что diff(A, C) должен быть таким же, как diff(C,A).
Размышляя об этом, я также начинаю задаваться вопросом, могли бы мы представить себе "разницу" как расстояние между любыми двумя строками, и, имея строгое определение расстояния, могли бы мы затем попытаться кластерный анализ на входных строках.Просто мысль.
Другие советы
Отличный вопрос!Шаги к решению следующие:
- токенизация входные данные
- использование токенов для создания соответствующего структура данных.a ЧУВАК является идеальным, но Три это проще и достойная отправная точка.
- необязательная последующая обработка структуры данных для упрощения или кластеризации поддеревьев в отдельные выходные данные
- сериализация из структуры данных в регулярное выражение или аналогичный синтаксис
Я реализовал этот подход в 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))
Что-то подобное могло бы сработать.
- Создайте trie, который представляет все ваши строки.
В примере, который вы привели, было бы два ребра от корня:"E" и "J".Затем ветвь "J" разделилась бы на "Jo" и "J2".
Единственная нить, которая разветвляется, напримерE-n-t-i-r-e-S-(разветвляется на 1, 2) указывает на выбор, так что это были бы целые числа [1,2]
Если прядь "слишком короткая" по отношению к вилке, напримерB-A- (разветвляется на N-A-N-A и H-A-M-A-S), мы перечисляем два слова ("банан, багамские острова") вместо выбора ("ба [нана, хамас]")."Слишком короткий" может быть таким же простым, как "если часть после разветвления длиннее части до", или, возможно, взвешенным по количеству слов с заданным префиксом.
Если два поддерева "достаточно похожи", то их можно объединить, чтобы вместо дерева у вас теперь был общий график.Например, если у вас есть ABRed, ABBlue, ABGreen,CDRed, CDBlue, CDGreen, вы можете обнаружить, что поддерево с корнем в "AB" совпадает с поддеревом с корнем в "CD", поэтому вам следует объединить их.В вашем выводе это будет выглядеть следующим образом:[левая ветвь, правая ветвь][поддерево], так что:[AB,CD][Красный,Синий,Зеленый].Как иметь дело с поддеревьями, которые близки, но не совсем совпадают?Вероятно, абсолютного ответа нет, но у кого-то здесь может быть хорошая идея.
Я отмечаю этот ответ сообществом wiki.Пожалуйста, не стесняйтесь расширить его, чтобы вместе мы могли получить разумный ответ на этот вопрос.
Существует множество подходов к подобию строк.Я бы предложил взглянуть на эту библиотеку с открытым исходным кодом, которая реализует множество показателей, таких как расстояние Левенштейна.
Вы должны быть в состоянии достичь этого с помощью обобщенных деревьев суффиксов:ищите длинные пути в дереве суффиксов, которые исходят из нескольких исходных строк.
попробуйте "фрак" .Он создает регулярное выражение из набора строк.Возможно, вам поможет какая-то его модификация.https://github.com/noprompt/frak
Надеюсь, это поможет.
Предложено множество решений, которые решают общий случай нахождения общих подстрок.Однако проблема здесь более специализированная.Вы ищете общие префиксы, а не только подстроки.Это немного упрощает задачу.Хорошее объяснение для поиска самого длинного общего префикса можно найти по адресу http://www.geeksforgeeks.org/longest-common-prefix-set-1-word-by-word-matching/
Итак, мой предлагаемый "питоновский" псевдокод выглядит примерно так (обратитесь к ссылке для реализации 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 - это всего лишь лист, но затем он разветвляется на красный и Зеленый.
Итак, что-то вроде списка<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));
}
}
