Выполните бинарный поиск для префикса строки в 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' - это компаратор, который использует метод начального запуска (и некоторую дополнительную логику).

Как мне это сделать в 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.правый биссект сработал, но левый явно не сработал.«Адам» не имеет префикса «Боб» !.чтобы исправить это, вы должны также изменить последовательность.

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

В качестве альтернативы ответу 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 4

Исходя из опыта функционального программирования, я поражен тем, что нет обычной абстракции бинарного поиска, в которую можно добавлять пользовательские функции сравнения.

Чтобы не допустить повторения этой вещи снова или снова или использовать грубые и нечитаемые хаки ООП, я просто написал эквивалент функции 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

Answer 5

Вот решение, которое еще не было предложено: заново реализовать алгоритм двоичного поиска.

Этого, как правило, следует избегать, потому что вы повторяете код (а двоичный поиск легко испортить), но, похоже, нет хорошего решения.

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

Как вы думаете, это путь?