我正在寻找在字符串列表或数组中查找匹配模式的方法，特别是在 .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)
...以及任何其他人。
我正在使用它来解决问题，而不是专门制作它的商业产品，并且宁愿不手工完成（有大约 100-200 个项目的 110 个列表）。
是否有任何算法、现有代码或想法可以帮助我找到所描述的结果？
最简单的编码方法是构建一个 Dictionary 然后循环遍历每个数组中的每个项目。对于每个项目，请执行以下操作：
检查项目是否在字典中，如果是，则将列表添加到数组中。如果该项目不在字典中，请添加它和列表。
正如你所说，这是非生产代码性能并不重要，所以这种方法应该可以正常工作。
这是使用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，它也不能识别一行中的多个元素作为模式，但是您可以修改比较函数以进一步查看看到这一点。
有一些像 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 等。您可以从临时列表中删除所有匹配 = 1 的列表（例如：“Do”）。临时列表包含非唯一项目的列表（将其保存在某处）。
现在，您尝试从临时列表中的一个和原始列表中的后续列表中创建两个列表。“So” + “La” = 2、“Bob” + “So” = 2 等。删除 = 1 的那些。你有至少出现两次的情侣列表（保存在某处）。
现在，尝试列出 3 个项目，从临时列表中获取一对，并从原始列表中获取以下内容。("Mi", "Fa") + "So" = 1, ("Mi", "Fa") + "Jim" = 1, ("So", "La") + "Ti" = 2 去掉那些with = 1。您有至少出现两次的 3 个项目的列表（保存它）。
然后你继续这样，直到临时列表为空。
最后，您获取所有已保存的列表并将它们合并。
这个算法不是最优的（我认为我们可以用合适的数据结构做得更好），但它很容易实现:)
假设密码由来自英文字母表的九个字符（26 个字符）组成。如果可以在一毫秒内测试每个可能的密码，那么测试所有可能的密码需要多长时间？