Python - 무작위 쿼리를 사용하여 숫자와 제안에 대한 자동 완성 기능

Question

목록에 이름의 기록 데이터 (1000에 가까운)를 저장하여 사용자가 설정 한 입력 쿼리에 대해 자동 완성을 수행하는 매우 최소한의 코드가 있습니다. 지금은 사전 식으로 가장 작은 순서로 제안합니다. 목록에 저장

이름은 (가상)입니다 : 사용자가 주어진

names = ["show me 7 wonders of the world","most beautiful places","top 10 places to visit","Population > 1000","Cost greater than 100"] 

쿼리가 될 수 있습니다

queries = ["10", "greater", ">", "7 w"] 

현재 구현 :

class Index(object): 

    def __init__(self, words): 
     index = {} 
     for w in sorted(words, key=str.lower, reverse=True): 
      lw = w.lower() 
      for i in range(1, len(lw) + 1): 
       index[lw[:i]] = w 

     self.index = index 

    def by_prefix(self, prefix): 
     """Return lexicographically smallest word that starts with a given 
     prefix. 
     """ 
     return self.index.get(prefix.lower(), 'no matches found') 

def typeahead(usernames, queries): 
    users = Index(usernames) 
    print "\n".join(users.by_prefix(q) for q in queries) 

이 작품 쿼리가 미리 저장된 이름으로 시작하면 문제 없습니다. 그러나 무작위 항목 (문자열의 중간에서 쿼리)을 만들면 제안을 제공하지 못합니다. 또한 숫자를 인식하지 못하고 숫자도 인식하지 못합니다.

기존 구현을 개선하기 위해 위의 기능을 포함 할 수있는 방법이 있는지 궁금합니다.

도움을 주시면 대단히 감사하겠습니다.

Answer 1

O (n)이지만 작동합니다. 문자열이 쿼리를 포함하는 경우가 접두사로 시작하면 귀하의 기능을 확인하지만, 당신이 원하는 당신이 설명하는 동작을 확인하고 있습니다

def __init__(self, words): 
    self.index = sorted(words, key=str.lower, reverse=True) 

def by_prefix(self, prefix): 
    for item in self.index: 
     if prefix in item: 
      return item 

이 제공 :

는

top 10 places to visit 
Cost greater than 100 
Population > 1000 
show me 7 wonders of the world 

그냥 기록을 위해이 0.175 소요 내 컴퓨터에서 1,000,000 레코드의 5 개 쿼리에 대해 초 단위로 일치하며 마지막 5 개 레코드는 일치하는 레코드입니다. (최악의 시나리오)

Answer 2

성능에 신경 쓰지 않는다면 에 item 개마다 if prefix in item:을 사용할 수 있습니다. 접두사가 명확하게 가장 빠른하지 난이 이것을 달성하는 가장 간단한 방법이라고 생각 :

prefix item  match 
'foo' 'foobar' True 
'bar' 'foobar' True 
'ob'  'foobar' True 
... 

, 예컨대을 문자열 항목의 일부이지만 경우에이 문은 일치합니다.

Answer 3

또 다른 옵션은 색인에 항목을 더 추가하는 것입니다. 항목 "most beautiful places"에 대한 :

"most beautiful places" 
"beautiful places" 
"places" 

이렇게하면 당신은 문장의 첫 단어 아니다 단어를 입력하기 시작하면, 당신은 또한 일치를 얻을.

class Index(object): 

    def __init__(self, words): 
     index = {} 
     for w in sorted(words, key=str.lower, reverse=True): 
      lw = w.lower() 
      tokens = lw.split(' ') 
      for j in range(len(tokens)): 
       w_part = ' '.join(tokens[j:]) 
       for i in range(1, len(w_part) + 1): 
        index[w_part[:i]] = w 

     self.index = index 

이 방법의 단점은 인덱스가 매우 큰 얻을 수 있다는 것입니다 : 당신은이 같은 코드가 있다고 할 수정할 수 있습니다. 또한이 방법을 색인 사전에있는 모든 단어에 대해 두 자리 접두사를 저장하고 색인 사전의 항목으로이 접두사가 포함 된 쿼리 목록을 저장하여 Keatinge이 지적한 방법과 결합 할 수 있습니다.