如何在字符串的列表/数组中找到类似的模式
https://stackoverflow.com/questions/483429
-
20-08-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
Russian题
我正在寻找在列表或字符串阵列中查找匹配模式的方法，特别是在.NET中，但是其他语言的算法或逻辑会很有帮助。
说我有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)
...还有其他。
我正在使用此问题来解决问题，而不是专门制作商业产品，宁愿不手工做（约有110个大约100-200个项目列表）。
是否有任何算法，现有代码或想法可以帮助我完成所描述的结果？
解决方案
正如其他人提到的那样，您想要的功能是相交。如果您使用的是.NET 3.0考虑使用LINQ的Intersect函数。
考虑使用LINQPAD进行实验。
其他提示
代码的最简单方法是构建字典，然后循环通过每个数组中的每个项目。对于每个项目，请执行此操作：
检查该项目是否在dictonary中，如果要将列表添加到数组中。如果该项目不在字典中，则添加了列表。
正如您所说的那样，这是非生产代码的性能并不重要，因此这种方法应该很好。
这是一种使用的解决方案 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
看来您想在数据集上使用相交功能。交叉路口挑选出在两种（或更多）集中常见的元素。
该观点的问题是集合不能包含每个元素中的一个以上，即每组不超过一个jim，也无法连续识别几个元素，将几个元素计数为模式，但是您可以修改比较功能以进一步查看看到的。
Mey具有像Intersect一样在袋子上工作的功能（这有点像集合，但可以容忍相同的元素）。
这些功能应该是大多数语言中的标准配置，或者很容易写出自己。
我敢肯定有一种更优雅的方式，但是...
既然这不是生产代码，为什么不只是将其破解并将每个数组转换为界定字符串，然后搜索每个字符串以查找所需的模式呢？ IE
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;
}
首先，从计数每个项目开始。您可以列出一个临时列表：“ do” = 1，“ mi” = 2，“ so” = 3，等等。您可以从temp列表中删除所有匹配= 1（ex：“ do do”）的temp列表。临时列表包含非唯一项目的列表（将其保存在某个地方）。
现在，您尝试从临时列表中的一个中列出两个列表，以及原始列表中的以下内容。 “ so” +“ la” = 2，“ bob” +“ so” = 2，等。删除= 1的la = 2。
现在，尝试通过从临时列表中获取一对三个项目的列表，并从原始列表中获取以下内容。 （“ mi”，“ fa”） +“ so” = 1，（“ mi”，“ fa”） +“ jim” = 1，（“ so”，“ la”） +“ ti” = 2删除其中的带有=1。您有3个项目的列表至少出现两次（保存）。
然后您继续这样，直到临时列表为空为止。
最后，您获取所有保存的列表，然后将其合并。
该算法不是最佳的（我认为我们可以通过合适的数据结构做得更好），但是可以易于实现:)
假设密码由英语字母（26个字符）的九个字符组成。如果每个可能的密码可以以毫秒的速度进行测试，那么测试所有可能的密码需要多长时间？
