在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循环遍历排序列表)

进一步澄清:我对简单的字典字母比较感兴趣,而不是像Levenshtein或语音学那样的任何想法.

谢谢

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上写了这个,所以请检查拼写错误.