在Python中執行二進制搜索字符串前綴

Question

我想爲所有以給定子字符串開頭的元素搜索一個排序的字符串列表。

下面是查找所有確切匹配的例子：

import bisect 
names = ['adam', 'bob', 'bob', 'bob', 'bobby', 'bobert', 'chris'] 
names.sort() 
leftIndex = bisect.bisect_left(names, 'bob') 
rightIndex = bisect.bisect_right(names, 'bob') 
print(names[leftIndex:rightIndex]) 

它打印['bob', 'bob', 'bob']。

相反，我想搜索以'bob'開始的所有名稱。我想要的輸出是['bob', 'bob', 'bob', 'bobby', 'bobert']。如果我可以修改對分搜索的比較方法，那麼我可以使用name.startswith('bob')來執行此操作。

作爲一個例子，在Java中它會很容易。我會使用：

Arrays.binarySearch(names, "bob", myCustomComparator); 

其中「myCustomComparator」是一個比較器，是以startswith方法（和一些額外的邏輯）的優點。

如何在Python中執行此操作？

Answer 1

bisect可以被愚弄，使用自定義比較使用使用您的艇員選拔的習俗比較實例：

>>> class PrefixCompares(object): 
...  def __init__(self, value): 
...   self.value = value 
...  def __lt__(self, other): 
...   return self.value < other[0:len(self.value)] 
... 
>>> import bisect 
>>> names = ['adam', 'bob', 'bob', 'bob', 'bobby', 'bobert', 'chris'] 
>>> names.sort() 
>>> key = PrefixCompares('bob') 
>>> leftIndex = bisect.bisect_left(names, key) 
>>> rightIndex = bisect.bisect_right(names, key) 
>>> print(names[leftIndex:rightIndex]) 
['adam', 'bob', 'bob', 'bob', 'bobby', 'bobert'] 
>>> 

DOH。正確的平分線有效，但左邊的分線顯然沒有。 「adam」沒有前綴「bob」!.要修復它，你也必須調整順序。

>>> class HasPrefix(object): 
...  def __init__(self, value): 
...   self.value = value 
...  def __lt__(self, other): 
...   return self.value[0:len(other.value)] < other.value 
... 
>>> class Prefix(object): 
...  def __init__(self, value): 
...   self.value = value 
...  def __lt__(self, other): 
...   return self.value < other.value[0:len(self.value)] 
... 
>>> class AdaptPrefix(object): 
...  def __init__(self, seq): 
...   self.seq = seq 
...  def __getitem__(self, key): 
...   return HasPrefix(self.seq[key]) 
...  def __len__(self): 
...   return len(self.seq) 
... 
>>> import bisect 
>>> names = ['adam', 'bob', 'bob', 'bob', 'bobby', 'bobert', 'chris'] 
>>> names.sort() 
>>> needle = Prefix('bob') 
>>> haystack = AdaptPrefix(names) 
>>> leftIndex = bisect.bisect_left(haystack, needle) 
>>> rightIndex = bisect.bisect_right(haystack, needle) 
>>> print(names[leftIndex:rightIndex]) 
['bob', 'bob', 'bob', 'bobby', 'bobert'] 
>>> 

Answer 2

不幸的是bisect不允許您指定key函數。你可以做的是在使用它來查找最高索引之前將'\xff\xff\xff\xff'添加到字符串中，然後獲取這些元素。

Answer 3

這是一個尚未提供的解決方案：重新實現二分查找算法。

這通常應該避免，因爲你重複的代碼（二進制搜索很容易搞砸），但似乎沒有很好的解決方案。

bisect_left（）已經給出了期望的結果，所以我們只需要改變bisect_right（）。原始實施僅供參考：

def bisect_right(a, x, lo=0, hi=None): 
    if lo < 0: 
     raise ValueError('lo must be non-negative') 
    if hi is None: 
     hi = len(a) 
    while lo < hi: 
     mid = (lo+hi)//2 
     if x < a[mid]: hi = mid 
     else: lo = mid+1 
    return lo 

這是新版本。唯一的變化是我添加and not a[mid].startswith(x)，我把它叫做 「bisect_right_prefix」：

def bisect_right_prefix(a, x, lo=0, hi=None): 
    if lo < 0: 
     raise ValueError('lo must be non-negative') 
    if hi is None: 
     hi = len(a) 
    while lo < hi: 
     mid = (lo+hi)//2 
     if x < a[mid] and not a[mid].startswith(x): hi = mid 
     else: lo = mid+1 
    return lo 

現在的代碼如下所示：

names = ['adam', 'bob', 'bob', 'bob', 'bobby', 'bobert', 'chris'] 
names.sort() 
leftIndex = bisect.bisect_left(names, 'bob') 
rightIndex = bisect_right_prefix(names, 'bob') 
print(names[leftIndex:rightIndex]) 

將會產生預期的結果：

['bob', 'bob', 'bob', 'bobby', 'bobert'] 

你覺得呢，這是要走的路嗎？

Answer 4

作爲IfLoop的答案替代 - 爲什麼不使用內置的__gt__？

>>> class PrefixCompares(object): 
...  def __init__(self, value): 
...   self.value = value 
...  def __lt__(self, other): 
...   return self.value < other[0:len(self.value)] 
...  def __gt__(self, other): 
...   return self.value[0:len(self.value)] > other 
>>> import bisect 
>>> names = ['adam', 'bob', 'bob', 'bob', 'bobby', 'bobert', 'chris'] 
>>> names.sort() 
>>> key = PrefixCompares('bob') 
>>> leftIndex = bisect.bisect_left(names, key) 
>>> rightIndex = bisect.bisect_right(names, key) 
>>> print(names[leftIndex:rightIndex]) 
['bob', 'bob', 'bob', 'bobby', 'bobert'] 

Answer 5

從函數式編程背景的人，我大吃一驚的是有沒有共同的二進制搜索抽象，它可以提供自定義的比較函數。

爲了防止自己一遍又一遍地重複那件事再次或使用總值（GDP）和不可讀OOP黑客，我只是寫你所提到的Arrays.binarySearch(names, "bob", myCustomComparator);功能的等價物：這是通用的一部分

class BisectRetVal(): 
    LOWER, HIGHER, STOP = range(3) 

def generic_bisect(arr, comparator, lo=0, hi=None): 
    if lo < 0: 
     raise ValueError('lo must be non-negative') 
    if hi is None: 
     hi = len(arr) 
    while lo < hi: 
     mid = (lo+hi)//2 
     if comparator(arr, mid) == BisectRetVal.STOP: return mid 
     elif comparator(arr, mid) == BisectRetVal.HIGHER: lo = mid+1 
     else: hi = mid 
    return lo 

。這裏是你的情況下，具體的比較：

def string_prefix_comparator_right(prefix): 
    def parametrized_string_prefix_comparator_right(array, mid): 
     if array[mid][0:len(prefix)] <= prefix: 
      return BisectRetVal.HIGHER 
     else: 
      return BisectRetVal.LOWER 
    return parametrized_string_prefix_comparator_right 


def string_prefix_comparator_left(prefix): 
    def parametrized_string_prefix_comparator_left(array, mid): 
     if array[mid][0:len(prefix)] < prefix: # < is the only diff. from right 
      return BisectRetVal.HIGHER 
     else: 
      return BisectRetVal.LOWER 
    return parametrized_string_prefix_comparator_left 

這裏的片斷，你只要適應了這個函數的代碼：

>>> names = ['adam', 'bob', 'bob', 'bob', 'bobby', 'bobert', 'chris'] 
>>> names.sort() 
>>> leftIndex = generic_bisect(names, string_prefix_comparator_left("bob")) 
>>> rightIndex = generic_bisect(names, string_prefix_comparator_right("bob")) 
>>> names[leftIndex:rightIndex] 
['bob', 'bob', 'bob', 'bobby', 'bobert'] 

它的工作原理沒有改變在這兩個的Python 2和Python 3

欲瞭解更多有關如何工作的信息和更多的比較這個東西檢查了這個要點：https://gist.github.com/Shnatsel/e23fcd2fe4fbbd869581