use*_*ser 13 python regex string
我有两套串(中A和B),我想知道的所有字符串对a in A,并b in B在那里a是一个子b.
对此进行编码的第一步如下:
for a in A:
for b in B:
if a in b:
print (a,b)
但是,我想知道 - 使用正则表达式是否有更有效的方法(例如,而不是检查if a in b:,检查正则表达式是否'.*' + a + '.*':匹配'b'.我认为可能使用这样的东西会让我缓存Knuth-莫里斯-普拉特对所有故障的功能a.此外,使用列表理解为内for b in B:循环可能会给出一个相当大的加速(和嵌套列表理解可能会更好).
我对这个算法的渐近运行时间的巨大飞跃并不感兴趣(例如使用后缀树或其他复杂而聪明的东西).我更关心常量(我只需要为几对A和B集合做这个,我不希望它一整周都运行).
您是否知道任何技巧或有任何通用建议来更快地完成此操作？非常感谢您分享的任何见解!
编辑:
使用@ninjagecko和@Sven Marnach的建议,我构建了一个10-mer的快速前缀表:
import collections
prefix_table = collections.defaultdict(set)
for k, b in enumerate(B):
for i in xrange(len(prot_seq)-10):
j = i+10+1
prefix_table[b[i:j]].add(k)
for a in A:
if len(a) >= 10:
for k in prefix_table[a[:10]]:
# check if a is in b
# (missing_edges is necessary, but not sufficient)
if a in B[k]:
print (a,b)
else:
for k in xrange(len(prots_and_seqs)):
# a is too small to use the table; check if
# a is in any b
if a in B[k]:
print (a, b)
Sve*_*ach 10
当然,您可以轻松地将其写为列表理解:
[(a, b) for a in A for b in B if a in b]
这可能会略微加快循环速度,但不要期望太多.我怀疑使用正则表达式会对此有任何帮助.
编辑:以下是一些时间:
import itertools
import timeit
import re
import collections
with open("/usr/share/dict/british-english") as f:
A = [s.strip() for s in itertools.islice(f, 28000, 30000)]
B = [s.strip() for s in itertools.islice(f, 23000, 25000)]
def f():
result = []
for a in A:
for b in B:
if a in b:
result.append((a, b))
return result
def g():
return [(a, b) for a in A for b in B if a in b]
def h():
res = [re.compile(re.escape(a)) for a in A]
return [(a, b) for a in res for b in B if a.search(b)]
def ninjagecko():
d = collections.defaultdict(set)
for k, b in enumerate(B):
for i, j in itertools.combinations(range(len(b) + 1), 2):
d[b[i:j]].add(k)
return [(a, B[k]) for a in A for k in d[a]]
print "Nested loop", timeit.repeat(f, number=1)
print "List comprehension", timeit.repeat(g, number=1)
print "Regular expressions", timeit.repeat(h, number=1)
print "ninjagecko", timeit.repeat(ninjagecko, number=1)
结果:
Nested loop [0.3641810417175293, 0.36279606819152832, 0.36295199394226074]
List comprehension [0.362030029296875, 0.36148500442504883, 0.36158299446105957]
Regular expressions [1.6498990058898926, 1.6494300365447998, 1.6480278968811035]
ninjagecko [0.06402897834777832, 0.063711881637573242, 0.06389307975769043]
编辑2:添加了ninjagecko建议的算法的变体到时间.你可以看到它比所有蛮力方法都要好得多.
编辑3:使用集而不是列表来消除重复.(我没有更新时间 - 它们基本保持不变.)
让我们假设你的单词有一个合理的大小(让我们说10个字母).执行以下操作以实现线性(!)时间复杂度,即O(A+B):
55*O(B)= 更差O(B)),以及它所属的字符串的元数据O(1)查询到您的哈希表/索引树找到所有的B-字符串它是,产生这些(在写这个答案的时候,如果OP的"单词"是有限的,那么它们没有任何反应.如果它们没有界限,这个解决方案仍然适用,但是存在依赖性O(maxwordsize^2),但实际上它在实践中更好,因为并非所有单词都是相同的大小,因此,它可能O(averagewordsize^2)与正确的分布一样好.例如,如果所有单词的大小都是20,那么问题大小将增加4倍,而不是大小为10.大小10-> 20,那么复杂性不会有太大变化.)
编辑: https ://stackoverflow.com/q/8289199/711085实际上是一个理论上更好的答案.在发布该答案之前,我正在查看链接的维基百科页面,并且正在考虑"字符串大小中的线性不是您想要的",并且后来才意识到它正是您想要的.你构建正则表达式的直觉(Aword1|Aword2|Aword3|...)是正确的,因为在幕后生成的有限自动机将快速执行匹配,如果它支持同时重叠匹配,并非所有正则表达式引擎都可能.最终你应该使用的取决于你是否计划重复使用As或Bs,或者这只是一次性的事情.上述技术更容易实现,但仅在您的单词有界时才有效(如果您不拒绝超过特定大小限制的单词,则会引入DoS漏洞),但如果您不想要,可能就是您正在寻找的的阿霍Corasick字符串匹配有限自动机或类似的,或它是作为一个库不可用.
搜索大量字符串的一种非常快速的方法是使用有限自动机(因此你对regexp的猜测并不是那么远),即Aho Corasick字符串匹配机器,它用于像grep,病毒这样的工具扫描仪等.
首先,它将您要搜索的字符串(在您的情况下是A中的单词)编译为具有失败功能的有限状态自动机(如果您对细节感兴趣,请参阅'75中的文章).然后,此自动机读取输入字符串并输出所有找到的搜索字符串(可能您想稍微修改它,以便它输出找到搜索字符串的字符串).
这种方法的优点是它可以同时搜索所有搜索字符串,因此只需要查看输入字符串的每个字符一次(线性复杂度)!
有在PyPI中的霍corasick模式匹配的实现,但我没有测试过,所以我不能说这些实现的性能,可用性或正确性什么.
编辑:我尝试了Aho-Corasick自动机的这个实现,它确实是迄今为止最快的建议方法,并且易于使用:
import pyahocorasick
def aho(A, B):
t = pyahocorasick.Trie();
for a in A:
t.add_word(a, a)
t.make_automaton()
return [(s,b) for b in B for (i,res) in t.iter(b) for s in res]
我观察到的一件事是,在使用@SvenMarnachs脚本测试此实现时,它产生的结果比其他方法略少,我不知道为什么.我给创作者写了一封邮件,也许他会搞清楚.