文字列のリスト/配列に類似したパターンを発見する方法
https://stackoverflow.com/questions/483429
-
20-08-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
Russian質問
私は、特に.NETで、文字列のリストや配列に一致するパターンを発見する方法を探していますが、他の言語からのアルゴリズムやロジックが参考になります。
I 3つのアレイ（または列のこの特定のケース・リスト（）で）を有すると言います
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)
...と他のもの。
私は、特にそれの市販品をしないように、問題のトラブルシューティングを行うには、これを使用していて、かなり（約100〜200項目の110件のリストがあります）手でそれをしないでしょう。
私が記載された結果を見つけるの達成に役立つ任意のアルゴリズムを、既存のコード、またはアイデアはありますか？
解決
他の人はあなたが望む機能を述べてきたように交差があります。あなたは.NET 3.0を使用している場合はLINQの交差機能を使用することを検討します。
詳細については、以下の記事を参照してくださいする
実験するLinqPADの使用を検討します。
他のヒント
コードする最も簡単な方法は、各アレイ内の各アイテムを介して、ループを辞書を構築することであろう。各項目について次の操作を行います。
その配列にリストを追加した場合の項目はdictonaryにあるか確認してください。 項目が辞書にない場合は、それとリストを追加します。
あなたはこれで非生産コードのパフォーマンスは、このアプローチが正常に動作する必要がありますので、重要ではありません言ったように。
ので、ここの部分配列を見つけるために接尾辞木のモジュールを使用したソリューションです：
#!/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]
ソリューションはひどく非効率的である。
私は、Perlの約10分で、以下のプログラムをハッキング。それはグローバル変数を使用して、完璧ではない、それはちょうど、各リストのプログラムで見られるすべての要素の数を出力しますが、それはあなたがそれをコードする超簡単です何をしたいのかに良い近似です。
あなたが実際に各配列に共通する要素のすべてのサブセットのすべての組み合わせをしたいですか？あなたが望んでいた場合は、よりスマートな方法内のすべての要素を列挙することができますが、あなただけの各配列に少なくとも一度存在するすべての要素を望んでいた場合には、Unixコマンドを使用することができます「はgrep -v 0」以下の出力にそれが表示されるでしょうあなたのすべてのアレイに共通するすべての要素の交差点。あなたの質問は、詳細を少し不足しているので、私は完全にあなたの問題を解決し、何かを実装することはできません。
あなたがプログラミングよりも多くのデータ分析を行う場合、スクリプトはこのようなテキストデータからの質問をするために非常に役立ちます。あなたは、このようなスクリプト言語でコーディングする方法がわからない場合、私は、Perl、PythonやRubyでコーディングする方法について読ん月または2費やすだろう。あなたが本当に欲しいものを知っていないとき、彼らは特に例では、このような一回限りのハックのために素晴らしいことができます。まだあなたの質問の定義を模索しながら、あなたはそれを数回書き込み、再書き込みすることができます（あなたが速いなら）ように、このようなプログラムを書いている時点と脳コストは、本当に低いです。
#!/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
あなたがデータのセットに交差機能を使用したいように見えます。交差点は、両方の（またはそれ以上）のセットで共通する要素を選択する。
この観点での問題は、セットが各要素の複数を含むことができないということである、セットごとに1つ以下のジム、すなわち、また、それがパターンとして、行カウントでいくつかの要素を認識することはできません、あなたはしかし、比較関数を変更することができますちょうどそれを見てさらに探すためます。
MEYあり袋に取り組んでいますが交差するような関数である（一種のセットのようなものですが、同じ要素を許容し）ます。
これらの機能は、ほとんどの言語の標準や自分自身を書くことは、かなり簡単なはずです。
私はもっとエレガントな方法があります確信している、しかし...
これは、生産コードではありませんので、、なぜそれをハックし、区切られた文字列に各配列を変換し、あなたがしたいパターンのために、各文字列を検索しませんか？すなわちます。
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;
}
まず、各項目をカウントすることによって開始します。 "だから"、= 2、 "ミ" = 1 "ですか" = 3、など：あなたは一時リストを作成します あなたは、一時リストから= 1（：「DO」EX）と一致するすべてのものを削除することができます。 一時リストには、非ユニークなアイテム（どこかでそれを保存）のリストが含まれています。
さて、あなたは一時リスト中の1から2のリストを作ってみると、オリジナルのリストに次のよう。 "だから" + "ラ" = 2、 "ボブ" + "だから" = 2、など = 1を持つものを削除します。 あなたは、少なくとも二回（どこかでそれを保存）が表示されます夫婦のリストを持っています。
さて、一時リストからカップルを取ることによって、3つの項目のリストを作ってみると、オリジナルのリストから、次のことを取ります。 （ "ミ"、 "FA"）+ "だから" = 1、（ "ミ"、 "FA"）+ "ジム" = 1、（ "だから"、 "ラ"）+ "チタン" = 2 = 1を持つものを削除します。 あなたは（それを保存）少なくとも2回出現し3つの項目のリストを持っています。
とTEMPのリストが空になるまで、あなたがそのように続けます。
最後には、あなたが保存されたすべてのリストを取得し、あなたがそれらをマージします。
このアルゴリズムは最適ではありません（私たちは、適切なデータ構造をよりよく行うことができると思う）、実現するのは簡単です：）
パスワードは、英語のアルファベット（26文字）から9文字の文字列で構成されたとします。それぞれの可能なパスワードはミリ秒単位でテストすることができれば、どのくらいの時間は、すべての可能なパスワードをテストするために取るのでしょうか？
