사전으로 사용하기 위해 패트리샤 트리를 구현합니다

Question

방법으로 패트리샤 트리를 구현하려고합니다. addWord(), isWord(), 그리고 isPrefix() 빠른 검색 (접두사 검색 포함)을 위해 큰 단어 사전을 저장하는 수단으로. 나는 개념을 읽었지만 구현을 명확히하는 것은 아닙니다. (Java 또는 Python 코드에서) 트리를 구현하는 방법, 특히 노드 (또는 재귀 적으로 구현해야 함)를 알고 싶습니다. 26 개의 어린이 노드 배열로 Null/None으로 설정된 한 사람을 보았습니다. 더 나은 전략 (예 : 글자를 비트로 취급)과 어떻게 구현 하시겠습니까?

Answer 1

다른 사람이 Patricia에 대해 얼마 전에 시도하는 것에 대해 질문을했는데, 나는 파이썬 구현을하는 것에 대해 생각했지만 이번에는 실제로 그것을 촬영하기로 결정했습니다 (예, 이것은 선상이지만 멋진 작은 프로젝트처럼 보였습니다). 내가 만든 것은 아마도 순수한 Patricia Trie 구현이 아니지만 내 길을 더 좋아합니다. 다른 Patricia는 (다른 언어로) 어린이를위한 목록 만 사용하고 각 어린이가 성냥이 있는지 확인하는 것을 확인하지만, 이것이 비효율적이라고 생각해서 사전을 사용합니다. 기본적으로 설정 한 방법은 다음과 같습니다.

루트 노드에서 시작하겠습니다. 뿌리는 단지 사전 일뿐입니다. 사전에는 모두 단일 문자 (단어의 첫 글자)가 분기로 이어지는 키가 있습니다. 각 키에 해당하는 값은 첫 번째 항목이 트리 의이 분기와 일치하는 나머지 문자열을 제공하는 문자열 인 목록이며, 두 번째 항목은이 노드에서 추가 분기로 이어지는 사전입니다. 이 사전에는 또한 나머지 단어의 첫 글자와 일치하는 단일 문자 키가 있으며 프로세스는 트리 아래로 계속됩니다.

내가 언급해야 할 또 다른 것은 주어진 노드에 분기가 있지만 트리 자체의 단어라면 '' 목록이있는 노드로 이어지는 사전의 키 ['',{}].

다음은 단어가 저장되는 방법을 보여주는 작은 예입니다 (루트 노드는 변수입니다. _d):

>>> x = patricia()
>>> x.addWord('abcabc')
>>> x._d
{'a': ['bcabc', {}]}
>>> x.addWord('abcdef')
>>> x._d
{'a': ['bc', {'a': ['bc', {}], 'd': ['ef', {}]}]}
>>> x.addWord('abc')
{'a': ['bc', {'a': ['bc', {}], '': ['', {}], 'd': ['ef', {}]}]}

마지막 경우, ''키가 사전에 추가되어 'ABC'가 'ABCDEF'및 'ABCABC'에 추가 된 단어임을 나타냅니다.

소스 코드

class patricia():
    def __init__(self):
        self._data = {}

    def addWord(self, word):
        data = self._data
        i = 0
        while 1:
            try:
                node = data[word[i:i+1]]
            except KeyError:
                if data:
                    data[word[i:i+1]] = [word[i+1:],{}]
                else:
                    if word[i:i+1] == '':
                        return
                    else:
                        if i != 0:
                            data[''] = ['',{}]
                        data[word[i:i+1]] = [word[i+1:],{}]
                return

            i += 1
            if word.startswith(node[0],i):
                if len(word[i:]) == len(node[0]):
                    if node[1]:
                        try:
                            node[1]['']
                        except KeyError:
                            data = node[1]
                            data[''] = ['',{}]
                    return
                else:
                    i += len(node[0])
                    data = node[1]
            else:
                ii = i
                j = 0
                while ii != len(word) and j != len(node[0]) and \
                      word[ii:ii+1] == node[0][j:j+1]:
                    ii += 1
                    j += 1
                tmpdata = {}
                tmpdata[node[0][j:j+1]] = [node[0][j+1:],node[1]]
                tmpdata[word[ii:ii+1]] = [word[ii+1:],{}]
                data[word[i-1:i]] = [node[0][:j],tmpdata]
                return

    def isWord(self,word):
        data = self._data
        i = 0
        while 1:
            try:
                node = data[word[i:i+1]]
            except KeyError:
                return False
            i += 1
            if word.startswith(node[0],i):
                if len(word[i:]) == len(node[0]):
                    if node[1]:
                        try:
                            node[1]['']
                        except KeyError:
                            return False
                    return True
                else:
                    i += len(node[0])
                    data = node[1]
            else:
                return False

    def isPrefix(self,word):
        data = self._data
        i = 0
        wordlen = len(word)
        while 1:
            try:
                node = data[word[i:i+1]]
            except KeyError:
                return False
            i += 1
            if word.startswith(node[0][:wordlen-i],i):
                if wordlen - i > len(node[0]):
                    i += len(node[0])
                    data = node[1]
                else:
                    return True
            else:
                return False

    def removeWord(self,word):
        data = self._data
        i = 0
        while 1:
            try:
                node = data[word[i:i+1]]
            except KeyError:
                print "Word is not in trie."
                return
            i += 1
            if word.startswith(node[0],i):
                if len(word[i:]) == len(node[0]):
                    if node[1]:
                        try:
                            node[1]['']
                            node[1].pop('')
                        except KeyError:
                            print "Word is not in trie."
                        return
                    data.pop(word[i-1:i])
                    return
                else:
                    i += len(node[0])
                    data = node[1]
            else:
                print "Word is not in trie."
                return


    __getitem__ = isWord

당신은 결국 내가 설정 한 것을 알았을 것입니다. __getitem__ isword 메소드에. 이것은 그것을 의미합니다

x['abc']

트리에서 'ABC'여부를 반환합니다.

나는 이것으로 모듈을 만들어 PYPI에 제출해야한다고 생각하지만 더 많은 테스트와 최소한 removeword 메소드가 필요하다고 생각합니다. 버그를 찾으면 알려 주지만 잘 작동하는 것 같습니다. 또한 효율성이 크게 향상된다면 그것에 대해 듣고 싶습니다. 나는 각 지점의 맨 아래에 빈 사전을 갖는 것에 대해 무언가를 고려했지만 지금은 그대로두고 있습니다. 이러한 빈 사전은 구현의 사용을 확장하기 위해 단어에 연결된 데이터로 대체 될 수 있습니다.

어쨌든, 내가 구현 한 방식이 마음에 들지 않으면 적어도 이것은 자신의 버전을 구현하는 방법에 대한 아이디어를 줄 것입니다.

Answer 2

다음은 더 많은 Pythonic 방법을 사용하는 재귀 구현입니다.

def matching_prefix_index(word1, word2):
    max_len = min(len(word1),len(word2))
    for i in range(max_len):
        if word2[i] != word1[i]:
            return i
    return max_len

class PatriciaTrie(object):
    def __init__(self):
        self._storage = {}
        self._complete_prefix_flag = False

    def _find_storage_key(self, word):
        for key in self._storage:
            prefix_index = matching_prefix_index(key, word)
            if prefix_index > 0:
                return (key, prefix_index)
        return (None, None)

    def add(self, word):
        if word == '':
            self._complete_prefix_flag = True
            return True

        key, prefix_index = self._find_storage_key(word)
        if key is not None:
            if prefix_index == len(key):
                return self._storage[key].add(word[len(key):])
            else:
                new_tree = PatriciaTrie()
                new_tree._storage[key[prefix_index:]] = self._storage.pop(key)
                self._storage[key[0:prefix_index]] = new_tree
                return new_tree.add(word[prefix_index:])
        else:
            self._storage[word] = PatriciaTrie()
            self._storage[word].add('')
            return True

    def remove(self, word):
        if word == '':
            self._complete_prefix_flag = False
            return True

        key, prefix_index = self._find_storage_key(word)
        if key is None or prefix_index != len(key):
            return False

        subword = word[prefix_index:]
        subtrie = self._storage[key]
        if subtrie.remove(subword):
            if (not subtrie._complete_prefix_flag) and len(subtrie._storage) == 0:
                self._storage.pop(key)
            return True
        else:
            return False

    def __contains__(self, word):
        if word == '':
            return self._complete_prefix_flag

        key, prefix_index = self._find_storage_key(word)
        if key is None or prefix_index != len(key):
            return False
        else:
            return (word[prefix_index:] in self._storage[key])

    def has_prefix(self, word):
        if word == '':
            return True

        key, prefix_index = self._find_storage_key(word)
        if key is None:
            return False
        elif len(key) > len(word):
            return (prefix_index == len(word))
        elif len(key) != prefix_index:
            return False
        else:
            return self._storage[key].has_prefix(word[prefix_index:])