在Python数据中搜索单词模式

Question

我希望我能把这个问题解释清楚。我是一个python实验者（以防下面的查询显得幼稚）

假设我有一个以下形式的数据集：

a = ( ('309','308','308'), ('309','308','307'), ('308', '309','306', '304'))

让我将每个('309','308','308')称为路径。在

我想找出：

a.Count('309','308', <any word>)

b.Count('309',<any word>,'308')

以及所有可能的排列。在

我在想它是某种正则表达式，可以帮助我实现这个搜索。我走的路有五万条。在

有人能建议我如何在python中执行这种操作吗？我探索了特里亚，但我认为这对我没有帮助。在

谢谢， 萨加尔

Answer 1

如果您想以CS样式高效的方式执行此操作，应该查看tries。您需要稍作修改才能将每个子树的大小存储在它的根上，但这应该不会太难。在

Answer 2

您可以使用^{}来执行此操作：

>>> from collections import Counter
>>> a = ( ('309','308','308'), ('309','308','307'), ('308', '309','306', '304'))
>>> Counter((x, y) for (x, y, *z) in a)
Counter({('309', '308'): 2, ('308', '309'): 1})
>>> Counter((x, z) for (x, y, z, *w) in a)
Counter({('308', '306'): 1, ('309', '308'): 1, ('309', '307'): 1})

我还在这里使用扩展元组解包，这在Python3.x之前并不存在，只有当元组的长度不确定时才需要。在python 2.x中，可以改为：

^{pr2}$

不过，我不能说这会有多有效。我不认为这应该是坏的。在

Counter具有类似于dict的语法：

>>> count = Counter((x, y) for (x, y, *z) in a)
>>> count['309', '308']
2

编辑：您提到它们的长度可能大于1，在这种情况下，您可能会遇到问题，因为如果它们比要求的长度短，它们将无法解包。解决方案是将生成器表达式更改为忽略任何非必需格式的表达式：

Counter((item[0], item[1]) for item in a if len(item) >= 2)

例如：

>>> a = ( ('309',), ('309','308','308'), ('309','308','307'), ('308', '309','306', '304'))
>>> Counter((x, y) for (x, y, *z) in a)
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
  File "/usr/lib/python3.2/collections.py", line 460, in __init__
    self.update(iterable, **kwds)
  File "/usr/lib/python3.2/collections.py", line 540, in update
    _count_elements(self, iterable)
  File "<stdin>", line 1, in <genexpr>
ValueError: need more than 1 value to unpack
>>> Counter((item[0], item[1]) for item in a)
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
  File "/usr/lib/python3.2/collections.py", line 460, in __init__
    self.update(iterable, **kwds)
  File "/usr/lib/python3.2/collections.py", line 540, in update
    _count_elements(self, iterable)
  File "<stdin>", line 1, in <genexpr>
IndexError: tuple index out of range
>>> Counter((item[0], item[1]) for item in a if len(item) >= 2)
Counter({('309', '308'): 2, ('308', '309'): 1})

如果需要可变长度计数，最简单的方法是使用列表切片：

start = 0
end = 2
Counter(item[start:end] for item in a if len(item) >= start+end)

当然，这只适用于连续运行，如果要单独拾取列，则必须多做一些工作：

def pick(seq, indices):
    return tuple([seq[i] for i in indices])

columns = [1, 3]
maximum = max(columns)
Counter(pick(item, columns) for item in a if len(item) > maximum)

Answer 3

如果您是Python 2.7之前的版本，则可以使用列表理解：

#Number of: ('309','308', <any word>)
>>> len([i[0] for i in a if i[0]=='309' and i[1]=='308'])
2
#Number of:('309',<any word>,'308')
>>> len([i[0] for i in a if i[0]=='309' and i[-1]=='308'])
1

使用列表合并似乎也比使用Counter要快一些，尽管元组解包很好，但它也会减慢速度。defaultdict可以更快地完成类似的任务：

^{pr2}$