在Python列表中查找“最接近”的字符串（按字母顺序）

我有一个Python列表的字符串，例如初始化如下：在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或语音那样的花式。

感谢

来源

2009-08-24 Roee Adler

这正是平分模块的用途。这将比迭代大型列表快得多。

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上写了这个，所以请检查输入错误。

来源

2009-08-24 15:21:21 Triptych

+1的清洁解决方案，而且名称选择:) – 2009-08-24 15:25:46

你需要采取在列表为空的情况下照顾：如果index == 0：左=无其他：左=草垛[指数1] 如果index == LEN（干草堆）：右=无其他：右=草垛[指数] 回左，右 – tonfa 2009-08-24 15:29:15

对不起，我认为这是可能把代码中的注释。 – tonfa 2009-08-24 15:29:55

您可以改写的问题是：

给出一个字符串l的排序列表和输入字符串s，发现其中s应插入，这样l保持后分类保存在l指数插入。

l在index-1和index+1（如果它们存在）的元素是你正在寻找的。为了找到索引，您可以使用binary search。

来源

2009-08-24 15:15:49

一个非常幼稚的实现，只适用于简短列表：您可以非常容易地遍历列表并比较您的选择和每个选项，然后突破第一次选择比所比较的项目“更大”。

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

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

来源

2009-08-24 15:17:18

这就是我现在正在做的，编辑我的答案... – 2009-08-24 15:19:39

这些相对较短的名单，并且内容是否改变，还是相当静态？

如果你有大量的字符串，并且它们相对固定，那么你可能需要考虑将数据存储在Trie结构中。一旦你建立它，那么它很容易搜索，并按照你喜欢的方式找到你最近的邻居。

来源

2009-08-24 16:23:07 khedron

在Python列表中查找“最接近”的字符串（按字母顺序）

回答

相关问题