python - 在 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']
>>> 

卫生部。右边的一分为二有效，但左边的显然没有。 “亚当”的前缀不是“鲍勃”!要修复它，您还必须调整顺序。

>>> 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']
>>>