の実施、パトリシア-Trieとして使用辞書
-
18-09-2019 - |
質問
私は試行を実施するパトリシア-再生の方法 addWord()
, isWord()
, は、 isPrefix()
手段として、マルチメディア関連サービ辞書の言葉を迅速に検索(前方一致検索).を読んで、概念な思を明確に実装されます。知りたい(JavaまたはPythonコードをどのように実施するかについTrieを中心に、ノード(またははいを実施する再帰的に).イベントを通した者が実施することにより、配列の26の子ノードはnullに設定/なし。がより良い戦略などの処理の文字としてのビットは、どのようなを実装するのですか?
解決
他の誰かが質問を受けて圧縮にもらいたいという思いが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方法です。性を示すものバグを知らせてくれそうですね。また、なければ大きな改善の効率化したいと思います。私は考えについては空の辞書の各支店が、これらのイ...続きをします。これらの空の辞書に置き換えることができデータ連携の拡大のための実装を備えています。
とにかくんだり、思い思いの実装では、少なくともそこまで過ごせばよいかを教えてくれるアイデアについを実装する独自のバージョン。
他のヒント
ここではより多くの神託のメソッドを使用して再帰的な実装です。
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:])