파일에서 문자열 목록을 읽고 데이터 구조에 저장해야하는 응용 프로그램을 작성하고 있습니다 접두어로 그 문자열을 찾으십시오. 문자열 목록은 지정된 언어의 단어 목록입니다. 예를 들어 검색 함수가 매개 변수로 "stup"을 얻으면 [ "stupid", "stupidity", "stupor"...]를 반환해야합니다. 그것은 O (log (n) * m) 시간에 수행되어야하는데, 여기서 n은 데이터 구조의 크기이고 m은 결과의 수이며 가능한 한 빨리되어야합니다. 메모리 소비는 지금 큰 문제가 아닙니다. 나는 이것을 파이썬으로 작성하고 있으므로 파이썬 랩퍼를 사용하여 C로 구현 된 적합한 데이터 구조를 가리킬 수 있다면 좋을 것이다.빠른 접두사 검색을 사용하는 읽기 전용 문자열 목록 (약 100,000)에 대해 가장 효율적인 데이터 구조
트라이가 필요합니다.
http://en.wikipedia.org/wiki/Trie
내가 스크래블과 머뭇 거리는 프로그램을 사용했습니다. 설명 된 유스 케이스에 완벽합니다 (빠른 접두사 조회).
다음은 Python으로 trie를 작성하기위한 몇 가지 샘플 코드입니다. 이것은 몇 달 전에 함께 휘젓는 Boggle 프로그램에서 나온 것입니다. 나머지는 독자에게 운동으로 남아 있습니다. 그러나 접두어 검사를 위해서는 기본적으로 루트 노드 (변수 words)에서 시작하여 연속되는 자식 노드의 접두사의 문자를 따르고 그런 경로가 발견되면 True를 반환하고 그렇지 않으면 False를 반환하는 메서드가 필요합니다.
class Node(object):
def __init__(self, letter='', final=False):
self.letter = letter
self.final = final
self.children = {}
def __contains__(self, letter):
return letter in self.children
def get(self, letter):
return self.children[letter]
def add(self, letters, n=-1, index=0):
if n < 0: n = len(letters)
if index >= n: return
letter = letters[index]
if letter in self.children:
child = self.children[letter]
else:
child = Node(letter, index==n-1)
self.children[letter] = child
child.add(letters, n, index+1)
def load_dictionary(path):
result = Node()
for line in open(path, 'r'):
word = line.strip().lower()
result.add(word)
return result
words = load_dictionary('dictionary.txt')
trie (or prefix tree)는 골목에서 소리가납니다. O (m) 길이의 접두사 문자열에 대한 검색을 수행 할 수 있습니다.
문자열 배열. 그것을 통해
이진 검색은 첫 경기가 다음도 여기에 이후의 모든 일치하는 그것을 통해 하나
(내가 원래 연결 한 목록을 한 단계 검색하는 ...하지만 물론이 무작위가 없습니다 액세스 그래서 이것은 (나는을 downvoted 이유 아마 설명) 'BS'이었다 내 이진 검색 알고리즘은 아직 갈 수있는 가장 빠른 방법입니다하지만 tries의
맙소사, 그 남자에게 휴식을주십시오. – moo
많은 downvotes, 그리고 아무도 이유를 설명하고 신경? 사람들이 쌓이는 것처럼 느껴집니다. 이 대답은 원래 사용자가 요청한 모든 제약 조건을 충족하며 이해와 유지가 더 간단합니다. –
@reinier - 링크드리스트가 무작위 액세스에 좋지 않기 때문에 downvoted를 얻었습니다. 검색 시간은 요소 수에 선형입니다. 배열은 이미 정렬 되었으면 O (log n) 일 것이지만 trie는 O (m)입니다. 여기서 m은 접두어의 길이입니다. –
나는 반복적 인 방법으로 Node.add()를 작성하는 유혹 것 : 데프 추가 (자체, 문자) : 다음 = 자기 N = LEN ((글자, 인덱스 == n-1) next = next.children [글자 안의 글자] 글자 안의 글자 수 : 글자 안의 글자 : next.children [글자] 편지] – hughdbrown
하지만 올바른 들여 쓰기와 선으로 상상해보십시오. 휴식. – hughdbrown
적은 메모리를 사용하는 트리 인 "DAWG"도 참조하십시오. 그러나 (최소한 trie와 비교하여) 구축하는 것은 복잡합니다. – Fantius