Как найти похожие шаблоны в списках / массивах строк
Я ищу способы найти подходящие шаблоны в списках или массивах строк, особенно в.NET, но алгоритмы или логика из других языков были бы полезны.
Скажем, у меня есть 3 массива (или в данном конкретном случае List(Of String))
Array1
"Do"
"Re"
"Mi"
"Fa"
"So"
"La"
"Ti"
Array2
"Mi"
"Fa"
"Jim"
"Bob"
"So"
Array3
"Jim"
"Bob"
"So"
"La"
"Ti"
Я хочу сообщить о появлении матчей
("Mi", "Fa") In Arrays (1,2)
("So") In Arrays (1,2,3)
("Jim", "Bob", "So") in Arrays (2,3)
("So", "La", "Ti") in Arrays (1, 3)
... и любые другие.
Я использую это для устранения проблемы, а не для того, чтобы сделать ее коммерческим продуктом, и не хотел бы делать это вручную (есть 110 списков из 100-200 наименований).
Существуют ли какие-либо алгоритмы, существующий код или идеи, которые помогут мне найти описанные результаты?
8 ответов
Как уже упоминали другие, функция, которую вы хотите, это Intersect. Если вы используете.NET 3.0, рассмотрите возможность использования функции пересечения LINQ.
Смотрите следующий пост для получения дополнительной информации
Рассмотрите возможность использования LinqPAD для экспериментов.
Простейший способ написания кода - создать словарь, а затем перебрать каждый элемент в каждом массиве. Для каждого элемента сделайте это:
Проверьте, если элемент находится в диктонарном, если это так, добавьте список в массив. Если предмета нет в словаре, добавьте его и в список.
Поскольку, как вы сказали, это непроизводственный код, производительность не имеет значения, поэтому этот подход должен работать нормально.
Вот решение, использующее модуль SuffixTree для поиска подпоследовательностей:
#!/usr/bin/env python
from SuffixTree import SubstringDict
from collections import defaultdict
from itertools import groupby
from operator import itemgetter
import sys
def main(stdout=sys.stdout):
"""
>>> import StringIO
>>> s = StringIO.StringIO()
>>> main(stdout=s)
>>> print s.getvalue()
[['Mi', 'Fa']] In Arrays (1, 2)
[['So', 'La', 'Ti']] In Arrays (1, 3)
[['Jim', 'Bob', 'So']] In Arrays (2, 3)
[['So']] In Arrays (1, 2, 3)
<BLANKLINE>
"""
# array of arrays of strings
arr = [
["Do", "Re", "Mi", "Fa", "So", "La", "Ti",],
["Mi", "Fa", "Jim", "Bob", "So",],
["Jim", "Bob", "So", "La", "Ti",],
]
#### # 28 seconds (27 seconds without lesser substrs inspection (see below))
#### N, M = 100, 100
#### import random
#### arr = [[random.randrange(100) for _ in range(M)] for _ in range(N)]
# convert to ASCII alphabet (for SubstringDict)
letter2item = {}
item2letter = {}
c = 1
for item in (i for a in arr for i in a):
if item not in item2letter:
c += 1
if c == 128:
raise ValueError("too many unique items; "
"use a less restrictive alphabet for SuffixTree")
letter = chr(c)
letter2item[letter] = item
item2letter[item] = letter
arr_ascii = [''.join(item2letter[item] for item in a) for a in arr]
# populate substring dict (based on SuffixTree)
substring_dict = SubstringDict()
for i, s in enumerate(arr_ascii):
substring_dict[s] = i+1
# enumerate all substrings, save those that occur more than once
substr2indices = {}
indices2substr = defaultdict(list)
for str_ in arr_ascii:
for start in range(len(str_)):
for size in reversed(range(1, len(str_) - start + 1)):
substr = str_[start:start + size]
if substr not in substr2indices:
indices = substring_dict[substr] # O(n) SuffixTree
if len(indices) > 1:
substr2indices[substr] = indices
indices2substr[tuple(indices)].append(substr)
#### # inspect all lesser substrs
#### # it could diminish size of indices2substr[ind] list
#### # but it has no effect for input 100x100x100 (see above)
#### for i in reversed(range(len(substr))):
#### s = substr[:i]
#### if s in substr2indices: continue
#### ind = substring_dict[s]
#### if len(ind) > len(indices):
#### substr2indices[s] = ind
#### indices2substr[tuple(ind)].append(s)
#### indices = ind
#### else:
#### assert set(ind) == set(indices), (ind, indices)
#### substr2indices[s] = None
#### break # all sizes inspected, move to next `start`
for indices, substrs in indices2substr.iteritems():
# remove substrs that are substrs of other substrs
substrs = sorted(substrs, key=len) # sort by size
substrs = [p for i, p in enumerate(substrs)
if not any(p in q for q in substrs[i+1:])]
# convert letters to items and print
items = [map(letter2item.get, substr) for substr in substrs]
print >>stdout, "%s In Arrays %s" % (items, indices)
if __name__=="__main__":
# test
import doctest; doctest.testmod()
# measure performance
import timeit
t = timeit.Timer(stmt='main(stdout=s)',
setup='from __main__ import main; from cStringIO import StringIO as S; s = S()')
N = 1000
milliseconds = min(t.repeat(repeat=3, number=N))
print("%.3g milliseconds" % (1e3*milliseconds/N))
Обработка 100 списков по 100 пунктов занимает около 30 секунд. SubstringDict в приведенном выше коде может быть эмулировано grep -F -f,
Старое решение:
В Python (сохраните его в файл 'group_patterns.py'):
#!/usr/bin/env python
from collections import defaultdict
from itertools import groupby
def issubseq(p, q):
"""Return whether `p` is a subsequence of `q`."""
return any(p == q[i:i + len(p)] for i in range(len(q) - len(p) + 1))
arr = (("Do", "Re", "Mi", "Fa", "So", "La", "Ti",),
("Mi", "Fa", "Jim", "Bob", "So",),
("Jim", "Bob", "So", "La", "Ti",))
# store all patterns that occure at least twice
d = defaultdict(list) # a map: pattern -> indexes of arrays it's within
for i, a in enumerate(arr[:-1]):
for j, q in enumerate(arr[i+1:]):
for k in range(len(a)):
for size in range(1, len(a)+1-k):
p = a[k:k + size] # a pattern
if issubseq(p, q): # `p` occures at least twice
d[p] += [i+1, i+2+j]
# group patterns by arrays they are within
inarrays = lambda pair: sorted(set(pair[1]))
for key, group in groupby(sorted(d.iteritems(), key=inarrays), key=inarrays):
patterns = sorted((pair[0] for pair in group), key=len) # sort by size
# remove patterns that are subsequences of other patterns
patterns = [p for i, p in enumerate(patterns)
if not any(issubseq(p, q) for q in patterns[i+1:])]
print "%s In Arrays %s" % (patterns, key)
Следующая команда:
$ python group_patterns.py
печатает:
[('Mi', 'Fa')] In Arrays [1, 2]
[('So',)] In Arrays [1, 2, 3]
[('So', 'La', 'Ti')] In Arrays [1, 3]
[('Jim', 'Bob', 'So')] In Arrays [2, 3]
Решение ужасно неэффективно.
Я взломал программу ниже примерно за 10 минут Perl. Он не идеален, он использует глобальную переменную и просто выводит счетчики каждого элемента, видимого программой в каждом списке, но это хорошее приближение к тому, что вы хотите сделать, и его очень легко кодировать.
Вы действительно хотите все комбинации всех подмножеств элементов, общих для каждого массива? Вы можете перечислить все элементы более умным способом, если хотите, но если вы просто хотите, чтобы все элементы, которые существуют хотя бы один раз в каждом массиве, вы могли использовать команду Unix "grep -v 0" в выводе ниже, и это показало бы Вы пересечение всех элементов, общих для всех массивов. В вашем вопросе не хватает деталей, поэтому я не могу идеально реализовать то, что решает вашу проблему.
Если вы анализируете больше данных, чем программируете, сценарии могут быть очень полезны для постановки вопросов из текстовых данных, подобных этой. Если вы не знаете, как кодировать на языке сценариев, подобном этому, я потратил бы месяц или два на чтение того, как кодировать на Perl, Python или Ruby. Они могут быть замечательными для одноразовых взломов, таких как этот, особенно в тех случаях, когда вы действительно не знаете, чего хотите. Время и мозговые затраты на написание такой программы действительно низки, так что (если вы быстрые) вы можете написать и переписать ее несколько раз, продолжая изучать определение вашего вопроса.
#!/usr/bin/perl -w
use strict;
my @Array1 = ( "Do", "Re", "Mi", "Fa", "So", "La", "Ti");
my @Array2 = ( "Mi", "Fa", "Jim", "Bob", "So" );
my @Array3 = ( "Jim", "Bob", "So", "La", "Ti" );
my %counts;
sub count_array {
my $array = shift;
my $name = shift;
foreach my $e (@$array) {
$counts{$e}{$name}++;
}
}
count_array( \@Array1, "Array1" );
count_array( \@Array2, "Array2" );
count_array( \@Array3, "Array3" );
my @names = qw/ Array1 Array2 Array3 /;
print join ' ', ('element',@names);
print "\n";
my @unique_names = keys %counts;
foreach my $unique_name (@unique_names) {
my @counts = map {
if ( exists $counts{$unique_name}{$_} ) {
$counts{$unique_name}{$_};
} else {
0;
}
}
@names;
print join ' ', ($unique_name,@counts);
print "\n";
}
Вывод программы:
element Array1 Array2 Array3
Ti 1 0 1
La 1 0 1
So 1 1 1
Mi 1 1 0
Fa 1 1 0
Do 1 0 0
Bob 0 1 1
Jim 0 1 1
Re 1 0 0
Я уверен, что есть намного более элегантный способ, но...
Поскольку это не рабочий код, почему бы не взломать его и не преобразовать каждый массив в строку с разделителями, а затем найти в каждой строке нужный вам шаблон? т.е.
private void button1_Click(object sender, EventArgs e)
{
string[] array1 = { "do", "re", "mi", "fa", "so" };
string[] array2 = { "mi", "fa", "jim", "bob", "so" };
string[] pattern1 = { "mi", "fa" };
MessageBox.Show(FindPatternInArray(array1, pattern1).ToString());
MessageBox.Show(FindPatternInArray(array2, pattern1).ToString());
}
private bool FindPatternInArray(string[] AArray, string[] APattern)
{
return string.Join("~", AArray).IndexOf(string.Join("~", APattern)) >= 0;
}
Похоже, вы хотите использовать функцию пересечения для наборов данных. Пересечение выбирает элементы, которые являются общими в обоих (или более) наборах.
Проблема с этой точкой зрения состоит в том, что наборы не могут содержать более одного каждого элемента, то есть не более одного Jim на набор, также он не может распознавать несколько элементов в строке, считая образец, однако вы можете изменить функцию сравнения, чтобы посмотреть дальше чтобы увидеть только это.
Могут быть такие функции, как пересечение, которое работает на сумках (что-то вроде наборов, но допускает идентичные элементы).
Эти функции должны быть стандартными на большинстве языков или написаны довольно легко.
Сначала начните с подсчета каждого предмета. Вы создаете временный список: "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 пунктов, которые появляются как минимум дважды (сохраните его).
И вы продолжаете так до тех пор, пока временный список не станет пустым.
В конце вы берете все сохраненные списки и объединяете их.
Этот алгоритм не является оптимальным (я думаю, что мы можем добиться большего успеха с подходящими структурами данных), но его легко реализовать:)
Предположим, пароль состоит из девяти символов английского алфавита (26 символов). Если бы каждый возможный пароль мог быть проверен за миллисекунду, сколько времени потребуется для проверки всех возможных паролей?