Pythonリスト（アルファベット順）に「最も近い」文字列を見つける

Question

私はPythonの文字列リストを持っています。以下のように初期化：

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

をI、すなわち（アルファベット順と大文字と小文字を区別せずに、何の音声学をこのリストに対して、入力文字列をテストしたいとしない、そして「それ以下の最も近い文字列」と「それ以上の最も近い文字列」を見つけるだろう、ちょうどa<bなど）。入力がリストに存在する場合、「下」と「上」の両方が入力を返すはずです。

いくつかの例：

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

Pythonでこれを達成するためのneatest方法は何ですか？ （現在、私はソートされたリストを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でこれを書いたので、タイプミスがないかチェックしてください。

Answer 2

あなたはこれに問題を修正してくださいすることができます：文字列lと入力文字列sのソートされたリストを考えると

、lは後にソートされたままであるように、sが挿入されなければならないlにインデックスを見つけます挿入。

lのindex-1とindex+1（存在する場合）の要素は、探しているものです。インデックスを検索するには、binary searchを使用します。

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構造体に格納することを検討してください。一度それを構築すると、素早く検索して、あなたの好きな方法であなたの最寄りのものを見つけることが簡単です。&