Поиск «ближайших» строк в списке Python (в алфавитном порядке)

Question

У меня есть список строк Python, например, инициализируется следующим образом:

l = ['aardvark', 'cat', 'dog', 'fish', 'tiger', 'zebra']

Я хотел бы проверить входную строку по этому списку и найти «ближайшую строку под ней» и «ближайшую строку над ней» в алфавитном порядке и без учета регистра (т. Е. Без фонетики, просто a<b и т. Д.). Если в списке есть входные данные, оба «внизу» и «выше» должны возвращать входные данные.

Несколько примеров:

Input  | Below    |  Above   
-------------------------------
bat    | aardvark | cat      
aaa    | None     | aardvark 
ferret | dog      | fish     
dog    | dog      | dog

Какой самый лучший способ достичь этого в Python? (в настоящее время я перебираю отсортированный список, используя цикл for)

Для дальнейшего уточнения: меня интересует простое словарное сравнение по словарю, а не что-нибудь необычное, как Левенштейн или фонетика.

Спасибо

Answer 1

Это именно то, для чего предназначен модуль bisect. Это будет намного быстрее, чем просто перебирать большие списки.

import bisect

def closest(haystack, needle):
    if len(haystack) == 0: return None, None

    index = bisect.bisect_left(haystack, needle)
    if index == 0:
        return None, haystack[0]
    if index == len(haystack):
        return haystack[index], None
    if haystack[index] == needle:
        return haystack[index], haystack[index]        
    return haystack[index-1], haystack[index]

В приведенном выше коде предполагается, что вы очистили ввод и список в верхнем или нижнем регистре Кроме того, я написал это на моем iPhone, поэтому, пожалуйста, проверьте на опечатки.

Answer 2

Вы можете перефразировать проблему следующим образом:

Учитывая отсортированный список строк l и входную строку s, найдите индекс в l, где нужно вставить s, чтобы l оставалось отсортированным после вставки.

Элементы l в index-1 и index+1 (если они существуют) - это те, которые вы ищете. Чтобы найти индекс, вы можете использовать бинарный поиск .

Answer 3

Очень наивная реализация, подходящая только для коротких списков: вы можете довольно легко перебрать список и сравнить свой выбор с каждым, а затем разбить первый раз, когда ваш выбор «больше», чем сравниваемый элемент.

for i, item in enumerate(l):
    if lower(item) > lower(input):
        break

print 'below: %s, above, %s' % (l[i-1], item)

Answer 4

Это относительно короткие списки, и содержание меняется или они довольно статичны?

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