Recherche des chaînes "les plus proches" dans une liste Python (par ordre alphabétique)

Question

J'ai une liste de chaînes Python, par ex. initialisé comme suit:

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

Je voudrais tester une chaîne d'entrée contre cette liste, et trouver la « chaîne le plus proche en dessous » et la « chaîne le plus proche au-dessus », par ordre alphabétique et indépendamment de la casse (ie pas phonétiques , juste a<b etc). Si l'entrée existe dans la liste, les deux "ci-dessous" et "ci-dessus" devraient retourner l'entrée.

Plusieurs exemples:

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

Quelle est la plus élégante façon d'y parvenir en Python? (actuellement je suis itérer sur une liste triée en utilisant une boucle for)

Pour clarifier davantage: Je suis intéressé par la simple comparaison alphabétique du dictionnaire, pas n'importe quoi de fantaisie comme Levenshtein ou phonétique.

Merci

Answer 1

C'est exactement ce que le module bisect est destiné. Ce sera beaucoup plus rapide que simplement itérer à travers de grandes listes. Le code ci-dessus suppose que vous avez nettoyé l'entrée et que la liste est en majuscules ou en minuscules. Aussi, j'ai écrit ceci sur mon iPhone, alors s'il vous plaît vérifiez les fautes de frappe.

Answer 2

Vous pouvez reformuler le problème à ceci:

Étant donné une liste de chaînes l et une chaîne d'entrée s, trouver l'index dans l où s doit être inséré de telle sorte que l triée reste triés après insertion. Les éléments de l à index-1 et index+1 (s'ils existent) sont ceux que vous recherchez. Afin de trouver l'index, vous pouvez utiliser binary search.

Answer 3

Une implémentation très naïve, valable uniquement pour les listes restreintes: vous pouvez facilement parcourir la liste et comparer votre choix par rapport à chacune, puis casser la première fois que votre choix est 'supérieur' à l'élément comparé.

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

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

Answer 4

Ces listes sont-elles relativement courtes et le contenu change-t-il ou est-il plutôt statique?

Si vous avez un grand nombre de chaînes, et qu'elles sont relativement corrigées, vous pouvez envisager de stocker vos données dans une structure Trie. Une fois que vous le construisez, il est facile de rechercher et de trouver vos voisins les plus proches comme vous le souhaitez.