の実施、パトリシア-Trieとして使用辞書

Question

私は試行を実施するパトリシア-再生の方法 addWord(), isWord(), は、 isPrefix() 手段として、マルチメディア関連サービ辞書の言葉を迅速に検索（前方一致検索).を読んで、概念な思を明確に実装されます。知りたい(JavaまたはPythonコードをどのように実施するかについTrieを中心に、ノード(またははいを実施する再帰的に).イベントを通した者が実施することにより、配列の26の子ノードはnullに設定/なし。がより良い戦略などの処理の文字としてのビットは、どのようなを実装するのですか？

Answer 1

他の誰かが質問を受けて圧縮にもらいたいという思いがPythonを実施し、今回私は実際に何を選（このは無理がされるようになったとちょっとしたプロジェクト）。私たしかできない純粋なパトリシア-再生の実装には、私ります。その他の圧縮(その他の言語の使用の一覧が表示され、子どもをそれぞれチェックして"エク子供のある試合だと思ったのは非効率で利用する事ができます。ここでは基本的にどのようんで設定されている

私のルートノードです。のルートは辞書で調べました。辞書には鍵が全てシングル文字（ローマ字の頭文字の言葉）を支店とする。の値に対応する各々のキーはリストの最初の項目は文字列の残りの文字列に一致するこの店の再生、第二項は辞書で更なる支店からこのノードです。この辞書または単一文字のキーに対応する、の頭文字、他の言葉にももっと世界に目を向けてのtrie.

もう一つある場合には指定されたノードは店舗でも単語の再生そのものとが示する '' キー辞書につながるノードのリスト ['',{}].

こちらは小さな例かを表わす言葉を記録する(ルートノードが変数 _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'、trieいます。

と思いるのかを是正しなければならないモジュールの本提出してくださPyPIが必要である試験および少なくともremoveWord方法です。性を示すものバグを知らせてくれそうですね。また、なければ大きな改善の効率化したいと思います。私は考えについては空の辞書の各支店が、これらのイ...続きをします。これらの空の辞書に置き換えることができデータ連携の拡大のための実装を備えています。

とにかくんだり、思い思いの実装では、少なくともそこまで過ごせばよいかを教えてくれるアイデアについを実装する独自のバージョン。

Answer 2

ここではより多くの神託のメソッドを使用して再帰的な実装です。

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:])