<사용자 입력>으로 시작하는 사전의 모든 단어 나열

StackOverflow https://stackoverflow.com/questions/112532

  •  02-07-2019
  •  | 
  •  

문제

사용자가 문자열을 입력하면 프로그램이 해당 문자열로 시작하는 단어 목록을 생성하는 프로그램을 만드는 방법은 무엇입니까?

전:
사용자:"아브드"
프로그램:퇴위, 복부, 납치...

감사해요!

편집하다:저는 Python을 사용하고 있지만 이는 언어 독립적인 문제라고 가정합니다.

도움이 되었습니까?

해결책

데비안[유사] 머신을 사용한다면, 

#!/bin/bash
echo -n "Enter a word: "
read input
grep "^$input" /usr/share/dict/words

내 P200에서는 0.040초가 모두 소요됩니다.

다른 팁

사용 트라이.

트라이에 단어 목록을 추가하세요.루트에서 리프까지의 각 경로는 유효한 단어입니다.루트에서 중간 노드까지의 경로는 접두사를 나타내며 중간 노드의 하위 노드는 접두사에 대한 유효한 완성입니다.

이를 수행하는 가장 좋은 방법 중 하나는 방향성 그래프를 사용하여 사전을 저장하는 것입니다.약간의 설정이 필요하지만 일단 완료되면 귀하가 말하는 검색 유형을 수행하는 것은 매우 쉽습니다.

그래프의 노드는 단어의 문자에 해당하므로 각 노드에는 하나의 들어오는 링크와 최대 26개의(영어) 나가는 링크가 있습니다.

사전이 포함된 정렬된 목록을 유지하고 방향성 그래프를 사전에 대한 색인으로 사용하는 하이브리드 접근 방식을 사용할 수도 있습니다.그런 다음 유향 그래프에서 접두사를 찾은 다음 사전의 해당 지점으로 이동하여 검색 기준과 일치하는 모든 단어를 뱉어냅니다.

egrep `read input && echo ^$input` /usr/share/dict/words

아 Python 편집 내용은 못 봤습니다. Python에도 같은 내용이 있습니다.

my_input = raw_input("Enter beginning of word: ")
my_words = open("/usr/share/dict/words").readlines()
my_found_words = [x for x in my_words if x[0:len(my_input)] == my_input]

정말로 속도를 원한다면 트라이/오토마톤을 사용하세요.그러나 단어 목록이 정렬되어 있다는 점을 고려하면 단순히 전체 목록을 스캔하는 것보다 더 빠른 방법이 있습니다.

from itertools import takewhile, islice
import bisect

def prefixes(words, pfx):
    return list(
             takewhile(lambda x: x.startswith(pfx), 
                       islice(words, 
                              bisect.bisect_right(words, pfx), 
                              len(words)))

자동 장치는 사전 크기를 기준으로 O(1)인 반면, 이 알고리즘은 실제로 접두어로 시작하는 문자열 수를 기준으로 O(log(m)) 다음으로 O(n)입니다. 전체 스캔은 O(m)이고 n << m입니다.

def main(script, name):
    for word in open("/usr/share/dict/words"):
        if word.startswith(name):
            print word,

if __name__ == "__main__":
    import sys
    main(*sys.argv)

정말로 효율적이기를 원한다면 접미사 트리나 접미사 배열을 사용하세요. 위키피디아 기사.

문제는 접미사 트리가 처리하도록 설계된 것입니다.Python에 대한 구현도 있습니다. 여기

var words = from word in dictionary
            where word.key.StartsWith("bla-bla-bla");
            select word;

정규식을 사용하여 단어 목록을 검색해 보세요./^word/ 및 모든 일치 항목을 보고합니다.

당신이 필요하다면 정말 빨리, 트리를 사용하세요:

배열을 만들고 첫 번째 문자를 기준으로 단어를 26개 세트로 분할한 다음 두 번째 문자를 기준으로 각 항목을 26개 세트로 분할한 다음 다시 반복합니다.

따라서 사용자가 "abd"를 입력하면 Array[0][1][3]을 찾고 그렇게 시작하는 모든 단어 목록을 얻게 됩니다.이 시점에서 목록은 클라이언트에 전달되고 자바스크립트를 사용하여 필터링할 수 있을 만큼 작아야 합니다.

가장 파이썬적인 솔루션

# set your list of words, whatever the source
words_list = ('cat', 'dog', 'banana')
# get the word from the user inpuit
user_word = raw_input("Enter a word:\n")
# create an generator, so your output is flexible and store almost nothing in memory
word_generator = (word for word in words_list if word.startswith(user_word))

# now you in, you can make anything you want with it 
# here we just list it :

for word in word_generator :
    print word

생성기는 한 번만 사용할 수 있으므로 목록으로 바꾸거나(list(word_generator) 사용) 두 번 이상 사용할 것으로 예상되는 경우 itertools.tee 함수를 사용하세요.

가장 좋은 방법은 다음과 같습니다.

데이터베이스에 저장하고 SQL을 사용하여 필요한 단어를 찾으십시오.사전에 단어가 많으면 훨씬 빠르고 효율적입니다.

Python에는 작업 수행에 도움이 되는 수천 개의 DB API가 있습니다 ;-)

당신이 사용할 수있는 str.startswith().공식 문서에 녹음:

str.startswith(접두사[, 시작[, 끝]])

문자열이 접두사로 시작하면 True를 반환하고, 그렇지 않으면 False를 반환합니다.prefix는 찾을 접두사의 튜플일 수도 있습니다.선택적 시작을 사용하면 해당 위치에서 시작되는 테스트 문자열입니다.선택적 end를 사용하면 해당 위치에서 문자열 비교를 중지합니다.

아래와 같이:

user_input = input('Enter something: ')
for word in dictionary:
    if str.startswith(user_input):
        return word

사전이 정말 크다면 Python 텍스트 인덱스를 사용하여 인덱싱하는 것이 좋습니다. (PyLucene - Lucene에 Python 확장을 사용한 적이 없습니다.) 검색이 효율적이며 검색 '점수'를 반환할 수도 있습니다.

또한 사전이 상대적으로 정적인 경우 색인을 자주 다시 생성하는 오버헤드도 발생하지 않습니다.

파리를 죽이기 위해 바주카포를 사용하지 마십시오.SQLite와 같이 간단한 것을 사용하십시오.모든 현대 언어에 필요한 모든 도구가 있으며 다음과 같이 할 수 있습니다.

"SELECT word FROM dict WHERE word LIKE "user_entry%"

번개처럼 빠르며 아기도 할 수 있습니다.게다가 휴대성이 뛰어나고 지속성이 뛰어나 유지 관리가 매우 쉽습니다.

파이썬 튜토리얼:

http://www.initd.org/pub/software/pysqlite/doc/usage-guide.html

선형 스캔은 느리지만 접두사 트리는 아마도 과잉일 것입니다.단어를 정렬된 상태로 유지하고 이진 검색을 사용하는 것은 빠르고 간단한 절충안입니다.

import bisect
words = sorted(map(str.strip, open('/usr/share/dict/words')))
def lookup(prefix):
    return words[bisect.bisect_left(words, prefix):bisect.bisect_right(words, prefix+'~')]

>>> lookup('abdicat')
['abdicate', 'abdication', 'abdicative', 'abdicator']

단어를 .csv 파일에 저장하는 경우 pandas를 사용하여 이 문제를 깔끔하게 해결할 수 있으며, 일단 읽은 후 사용자가 세션당 두 번 이상의 검색을 수행할 수 있어야 하는 경우 이미 로드된 데이터 프레임을 재사용할 수 있습니다. .

df = pd.read_csv('dictionary.csv')
matching_words = df[0].loc[df[0].str.startswith(user_entry)]
라이센스 : CC-BY-SA ~와 함께 속성
제휴하지 않습니다 StackOverflow
scroll top