Python 목록에서 "가장 가까운"문자열 찾기 (알파벳순)

Question

저는 파이썬 문자열 목록을 가지고 있습니다. 초기화 다음 없기 :

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

내가 알파벳 순으로이 목록에 대한 입력 문자열을 테스트하고 "아래 가장 가까운 문자열"과 "위 가까운 문자열을"찾아 좋아하는 경우 소문자를 구별 것 (즉, 더 음성학을 , 단지 a<b 등). 입력이 목록에 있으면 "아래"와 "위"모두 입력을 반환해야합니다.

몇 가지 예 :

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

파이썬에서 이것을 달성하기 위해 산뜻한 방법은 무엇입니까? (현재 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] 

위의 코드는 사용자가 입력 및 목록을 모두 대문자 또는 소문자로 위조 한 것으로 가정합니다. 또한, 내 아이폰에 이것을 썼습니다. 오타가 있는지 확인하십시오.

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 구조에 저장하는 것이 좋습니다. 일단 당신이 그것을 구축하면 빠른 & 통해 검색하고 가장 가까운 이웃을 당신이 원하는 방식으로 찾을 쉽습니다.