在python列表中查找“最近”字符串(按字母顺序)

这正是对分模块的作用所在。它将比只遍历大型列表快得多。

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上写了这个,所以请检查是否有错别字。

您可以将问题重新表述为:

给出了字符串的排序列表 l 和输入字符串 s ,在中查找索引 L 哪里 S 应插入,以便 L 插入后保持排序。

元素 L 在 index-1 和 index+1 (如果它们存在的话)是你正在寻找的。为了找到索引,可以使用 binary search .

一个非常幼稚的实现,只适用于短列表:您可以非常容易地遍历列表并将您的选择与每个列表进行比较,然后在第一次选择“大于”被比较的项时中断。

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

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

这些是相对较短的列表,内容是变化的还是相当静态的?

如果您有大量的字符串,而且它们相对固定,那么您可能需要考虑将数据存储在trie结构中。一旦你建造了它,你就可以很快很容易地搜索并找到你最接近的邻居。