在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列表中查找「最接近」的字符串（按字母順序）

回答

相關問題