私は、メソッド、、を使用して、および迅速な検索（プレフィックス検索を含む）のために単語の大きな辞書を格納する手段として、addWord()PatriciaTrieを実装しようとしています。私は概念を読みましたが、それらは実装を明確にしていません。Trie、特にノードを実装する方法を（JavaまたはPythonコードで）知りたい（または再帰的に実装する必要がある）。26個の子ノードの配列をnull/Noneに設定して実装した人を見ました。より良い戦略（文字をビットとして扱うなど）はありますか？それをどのように実装しますか？isWord()isPrefix()
7887 次
2 に答える
13
少し前に誰かがパトリシアの試みについて質問し、私は Python の実装を考えましたが、今回は実際に試してみることにしました (はい、これはやり過ぎですが、素敵な小さなプロジェクトのように思えました)。私が作成したものは、おそらく純粋なパトリシア トライの実装ではありませんが、私の方法の方が気に入っています。他のパトリシアは（他の言語で）子供たちのリストだけを使って、それぞれの子供たちを調べて一致するかどうかを調べていますが、これはかなり非効率的だと思ったので、辞書を使用しています。基本的に私が設定した方法は次のとおりです。
ルート ノードから始めます。ルートは単なる辞書です。ディクショナリには、分岐につながるすべての単一文字 (単語の最初の文字) であるキーがあります。各キーに対応する値はリストであり、最初の項目はトライのこの分岐に一致する残りの文字列を与える文字列であり、2 番目の項目はこのノードからさらに分岐する辞書です。この辞書には、残りの単語の最初の文字に対応する 1 文字のキーもあり、プロセスはトライを続けます。
もう 1 つ言及する必要があるのは、特定のノードに分岐があるが、トライ自体の単語でもある場合、それは''list を持つノードにつながる辞書のキーを持つことによって示されるということ['',{}]です。
単語がどのように格納されるかを示す小さな例を次に示します (ルート ノードは variable です_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 メソッドが必要です。バグを見つけた場合はお知らせください。ただし、かなりうまく機能しているようです。また、効率に大きな改善が見られた場合は、それについてもお聞きしたいと思います。各ブランチの下部に空の辞書を配置することを検討しましたが、今のところはそのままにしておきます。これらの空の辞書は、たとえば実装の用途を拡張するために、単語にリンクされたデータに置き換えることができます。
とにかく、私の実装方法が気に入らない場合は、少なくとも、独自のバージョンを実装する方法についていくつかのアイデアが得られるかもしれません.
于 2010-03-09T20:51:45.317 に答える