Как найти похожие шаблоны в списках / массивах строк

Question

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

Скажем, у меня есть 3 массива (или в этом конкретном случае List (Of String))

родовое слово

Я хочу сообщить о совпадениях

родовое слово

... и любые другие.

Я использую это для устранения проблемы, а не для того, чтобы делать из нее коммерческий продукт, и предпочел бы не делать это вручную (существует 110 списков, содержащих примерно 100-200 элементов).

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

Answer 1

Как уже упоминалось, вам нужна функция Intersect.Если вы используете .NET 3.0, подумайте об использовании функции LINQ Intersect.

Дополнительную информацию см. в следующем сообщении

Попробуйте использовать LinqPAD для экспериментов.

www.linqpad.net

Answer 2

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

Проверить, есть ли элемент в словаре, если да, добавить список в массив. Если элемент отсутствует в словаре, добавьте его и список.

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

Answer 3

Вот решение, использующее модуль SuffixTree для поиска подпоследовательностей: родовое слово

Обработка 100 списков по 100 элементов в каждом занимает около 30 секунд.SubstringDict в приведенном выше коде может быть эмулирован с помощью grep -F -f.

Старое решение:

---

В Python (сохраните его в файл group_patterns.py):

родовое слово

Следующая команда:

родовое слово

распечатывает:

родовое слово

Решение ужасно неэффективное.

Answer 4

Я взломал указанную ниже программу примерно за 10 минут на Perl. Он не идеален, он использует глобальную переменную и просто выводит количество элементов, видимых программой, в каждом списке, но это хорошее приближение к тому, что вы хотите сделать, что очень легко кодировать.

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

Если вы уделяете больше внимания анализу данных, чем программированию, сценарии могут быть очень полезны для того, чтобы задавать вопросы по таким текстовым данным. Если вы не знаете, как кодировать на таком языке сценариев, как этот, я бы потратил месяц или два на чтение о том, как кодировать на Perl, Python или Ruby. Они могут быть замечательными для одноразовых хаков, таких как этот, особенно в тех случаях, когда вы действительно не знаете, чего хотите. Время и мозговые затраты на написание такой программы действительно невелики, поэтому (если вы быстро) вы можете написать и переписать ее несколько раз, продолжая изучать определение вашего вопроса.

родовое слово

Результат программы:

родовое слово

Answer 5

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

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

Могут быть такие функции, как пересечение, которые работают с сумками (что-то вроде наборов, но допускает идентичные элементы).

Эти функции должны быть стандартными для большинства языков или их можно легко написать самостоятельно.

Answer 6

Я уверен, что есть НАМНОГО элегантнее, но ...

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

родовое слово

Answer 7

Сначала начните с подсчета каждого предмета. Вы составляете временный список: «Do»= 1, «Mi»= 2, «So»= 3 и т. Д. вы можете удалить из временного списка все, которые соответствуют= 1 (например, «Do»). Временный список содержит список неуникальных элементов (сохраните его где-нибудь).

Теперь вы пытаетесь составить списки из двух из одного во временном списке и следующего в исходных списках. «So» + «La»= 2, «Bob» + «So»= 2 и т. Д. Удалите те, которые имеют= 1. У вас есть список пар, который появляется как минимум дважды (сохраните его где-нибудь).

Теперь попробуйте составить список из 3 пунктов, взяв пару из временного списка, и возьмите следующее из исходных списков. («Mi», «Fa») + «So»= 1, («Mi», «Fa») + «Jim»= 1, («So», «La») + «Ti»= 2 Удалите те, которые имеют= 1. У вас есть список из 3 пунктов, который появляется как минимум дважды (сохраните его).

И вы продолжаете так, пока временный список не станет пустым.

В конце вы берете все сохраненные списки и объединяете их.

Этот алгоритм не оптимален (я думаю, мы можем добиться большего с подходящими структурами данных), но его легко реализовать :)

Answer 8

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