1

在比较函数中，我基本上是在一个长二进制对象（例如，aaaAAAbbbBBB）中寻找一个模式（例如“AAA”）

我正在通过文件向后工作（我知道匹配将比开始更接近结尾），向正在检查匹配的变量添加 1 个字节：

1. aaaAAAbbbBB[B]
2. aaaAAAbbbB[BB]
3. aaaAAAbbb[BBB]
4. aaaAAAbb[bBBB]
5. ... 
n. aaa[AAAbbbBBB]

找到匹配，偏移量 = -n

鉴于我知道我的模式是 3 个元素长，我想知道我是否可以简单地对搜索变量进行窗口化而不是增加它 - 当匹配是列表中的 +1,000,000 个元素时它会变得非常慢 - 相同数据的窗口化视图将是：

1. aaaAAAbbb[BBB]
2. aaaAAAbb[bBB]B
3. aaaAAAb[bbB]BB
4. aaaAAA[bbb]BBB
5. ...
n. aaa[AAA]bbbBBB

找到匹配，偏移量 = -n

我目前的搜索看起来像：

if marker in f_data[-counter:]:
    offset = (len(f_data)-counter)+len(marker)
    return offset

在 MATLAB 中，我会使用数组寻址在数组中移动（例如调用 window = a[5:8]、window = a[4:7] 等），但我认为这在 Python（2.7）中是不可能的

我可以看到一些使用滑动窗口的建议，（Python 中的滚动或滑动窗口迭代器- 这看起来很接近）但我看不到如何实现它，或者它们引用了我不知道如何的库利用。

是否有内置功能可以执行此操作？

4

3 回答 3

5

为什么不直接使用rfind()or rindex()？

haystack = "aaaAAAbbbBBB"
needle   = "AAA"

pos = haystack.rfind(needle)

if pos >= 0:
    print "found at", pos - len(haystack)
else:
    print "not found"
于 2012-09-26T01:29:25.473 回答
0

我认为这利用了你提到的 window() 迭代器函数。

>>> l = "ABCABACAAASSD"
>>> from itertools import islice
>>>
>>> def window(seq, n=2):
...     "Returns a sliding window (of width n) over data from the iterable"
...     "   s -> (s0,s1,...s[n-1]), (s1,s2,...,sn), ...                   "
...     it = iter(seq)
...     result = tuple(islice(it, n))
...     if len(result) == n:
...         yield result
...     for elem in it:
...         result = result[1:] + (elem,)
...         yield result
...
>>>
>>> data = [c for c in l] # get each byte/charactor as separate item in list
>>> data
['A', 'B', 'C', 'A', 'B', 'A', 'C', 'A', 'A', 'A', 'S', 'S', 'D']
>>> for idx, elements in enumerate(window(reversed(data), n=3)):
...     section = "".join(elements)
...     if section == "AAA":
...         print "found at {}!".format(idx)
...
found at 3!
>>>

解释：

  • reversed()接受一个列表并返回一个迭代器，其中的元素以相反的顺序排列
  • window()接受一个可迭代对象（列表、元组、迭代器）并返回n元素的数量，一次移动索引 1 个元素。
  • enumerate()接受一个可迭代的并简单地附加一个计数器，因此它将返回计数器/位置和给定的元素项。
于 2012-09-26T01:40:09.473 回答
0

两件事情：

(1) 标准字符串类型保存字节，您可以使用正则表达式。我可以建议您将对象 slurp 成一个字符串，然后执行正则表达式搜索。

(2) 如果您确实想以艰难的方式做到这一点，请访问http://docs.python.org/library/itertools.html#itertools.groupby

于 2012-09-26T01:28:57.033 回答