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

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

Проверьте, находится ли объект в словаре, раз так добавляют список к массиву. Если объект не находится в словаре, добавляет он и список.

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

Вот является использование решения модулем 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))

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

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

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

Во-первых, запустите путем подсчета каждого объекта. Вы составляете временный список: Сделайте = 1, "Ми" = 2, "Таким образом", = 3, и т.д. можно удалить из временного списка все те, которые соответствуют = 1 (исключая: Сделайте). Временный список содержит список групповых объектов (сохраните его где-нибудь).

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

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

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

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

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

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