私はトライと DAWG (直接非巡回ワード グラフ) に興味があり、それらについて多くのことを読んできましたが、出力トライまたは DAWG ファイルがどのように見えるべきかわかりません。
-またはスペースで区切られた複数の単語で構成される単語ブロックを実装する方法は?出力構造を作成して使用する方法を理解するために、最適な出力構造を理解したいと考えています。
また、 DAWGとtrieの出力がどうあるべきかを評価します。
バブルが相互にリンクされたグラフィカルな表現を見たくありません。一連の単語が試行または DAWG に変換された後の出力オブジェクトを知りたいのです。
トライを実装するにはさまざまな方法があるという点で、アンワインドは本質的に正しいです。また、大規模でスケーラブルなトライの場合、ネストされた辞書は扱いにくくなるか、少なくともスペース効率が低下する可能性があります。しかし、あなたは始めたばかりなので、それが最も簡単なアプローチだと思います。trieほんの数行で簡単にコーディングできます。まず、トライを構築する関数:
>>> _end = '_end_'
>>>
>>> def make_trie(*words):
... root = dict()
... for word in words:
... current_dict = root
... for letter in word:
... current_dict = current_dict.setdefault(letter, {})
... current_dict[_end] = _end
... return root
...
>>> make_trie('foo', 'bar', 'baz', 'barz')
{'b': {'a': {'r': {'_end_': '_end_', 'z': {'_end_': '_end_'}},
'z': {'_end_': '_end_'}}},
'f': {'o': {'o': {'_end_': '_end_'}}}}
に慣れていない場合はsetdefault、辞書でキーを検索するだけです (ここでは、letterまたは_end)。キーが存在する場合は、関連付けられた値を返します。そうでない場合は、そのキーにデフォルト値を割り当て、値 ({}または_end) を返します。get(辞書も更新するバージョンのようなものです。)
次に、単語がトライに含まれているかどうかをテストする関数:
>>> def in_trie(trie, word):
... current_dict = trie
... for letter in word:
... if letter not in current_dict:
... return False
... current_dict = current_dict[letter]
... return _end in current_dict
...
>>> in_trie(make_trie('foo', 'bar', 'baz', 'barz'), 'baz')
True
>>> in_trie(make_trie('foo', 'bar', 'baz', 'barz'), 'barz')
True
>>> in_trie(make_trie('foo', 'bar', 'baz', 'barz'), 'barzz')
False
>>> in_trie(make_trie('foo', 'bar', 'baz', 'barz'), 'bart')
False
>>> in_trie(make_trie('foo', 'bar', 'baz', 'barz'), 'ba')
False
挿入と削除は練習問題としてお任せします。
もちろん、Unwind の提案はそれほど難しいものではありません。正しいサブノードを見つけるには線形検索が必要になるため、速度が若干低下する可能性があります。ただし、検索は可能な文字数に制限されます。これを含めると 27 文字になります_end。また、ノードの膨大なリストを作成し、彼が提案するようにインデックスでそれらにアクセスしても、何も得られません。リストをネストすることもできます。
最後に、有向非巡回単語グラフ (DAWG) の作成はもう少し複雑になることを付け加えておきます。これは、現在の単語が構造内の別の単語と接尾辞を共有している状況を検出する必要があるためです。実際、これは、DAWG をどのように構造化するかによって、かなり複雑になる可能性があります。正しく理解するには、レーベンシュタイン 距離について学ぶ必要があるかもしれません。
これを見てください：
https://github.com/kmike/marisa-trie
Python (2.x および 3.x) 用の静的メモリ効率のよいトライ構造。
MARISA-trie の文字列データは、標準の Python dict よりも最大 50 倍から 100 倍少ないメモリを使用する場合があります。生のルックアップ速度は同等です。trie は、プレフィックス検索などの高速で高度な方法も提供します。
marisa-trie C++ ライブラリに基づいています。
これは、marisa trie をうまく使用している企業のブログ投稿です:
https://www.repustate.com/blog/sharing-large-data-structure-across-processes-python/
Repustate では、テキスト分析で使用するデータ モデルの多くを、単純なキーと値のペア、または Python 用語の辞書として表すことができます。私たちの特定のケースでは、辞書は巨大で、それぞれ数百 MB あり、常にアクセスする必要があります。実際、特定の HTTP リクエストに対して、4 つまたは 5 つのモデルがアクセスされる可能性があり、それぞれが 20 ～ 30 回のルックアップを実行します。したがって、私たちが直面している問題は、クライアントに対して物事を高速に保ち、サーバーに対して可能な限り軽量に保つ方法です。
...
このパッケージ、marisa attempts を見つけました。これは、marisa trie の C++ 実装の Python ラッパーです。「Marisa」は、Matching Algorithm with Recursively Implemented StorAge の頭字語です。marisa の試行の優れている点は、ストレージ メカニズムによって、必要なメモリ量が実際に縮小されることです。Python プラグインの作成者は、サイズが 50 ～ 100 分の 1 に縮小したと主張しています。私たちの経験も同様です。
marisa trie パッケージの優れている点は、基になる trie 構造をディスクに書き込んでから、メモリ マップされたオブジェクトを介して読み込むことができることです。メモリ マップされたマリサ トライにより、すべての要件が満たされました。サーバーのメモリ使用量は約 40% と劇的に減少し、パフォーマンスは Python の辞書実装を使用したときと変わりませんでした。
純粋な python 実装もいくつかありますが、制限されたプラットフォームを使用していない限り、最高のパフォーマンスを得るために上記の C++ を使用した実装を使用することをお勧めします。
Trie を実装する python パッケージのリストは次のとおりです。
senderleのメソッド (上記)から変更されました。Pythondefaultdictは、トライまたはプレフィックス ツリーを作成するのに理想的であることがわかりました。
from collections import defaultdict
class Trie:
"""
Implement a trie with insert, search, and startsWith methods.
"""
def __init__(self):
self.root = defaultdict()
# @param {string} word
# @return {void}
# Inserts a word into the trie.
def insert(self, word):
current = self.root
for letter in word:
current = current.setdefault(letter, {})
current.setdefault("_end")
# @param {string} word
# @return {boolean}
# Returns if the word is in the trie.
def search(self, word):
current = self.root
for letter in word:
if letter not in current:
return False
current = current[letter]
if "_end" in current:
return True
return False
# @param {string} prefix
# @return {boolean}
# Returns if there is any word in the trie
# that starts with the given prefix.
def startsWith(self, prefix):
current = self.root
for letter in prefix:
if letter not in current:
return False
current = current[letter]
return True
# Now test the class
test = Trie()
test.insert('helloworld')
test.insert('ilikeapple')
test.insert('helloz')
print test.search('hello')
print test.startsWith('hello')
print test.search('ilikeapple')
「すべき」はありません。それはあなた次第です。さまざまな実装にはさまざまなパフォーマンス特性があり、実装、理解、および適切な処理にさまざまな時間がかかります。私の意見では、これはソフトウェア開発全体の典型です。
おそらく最初に、これまでに作成されたすべてのトライ ノードのグローバル リストを作成し、各ノードの子ポインタをグローバル リストへのインデックスのリストとして表すことを試みます。子リンクを表すためだけに辞書を用意するのは、私には重すぎると感じます。
Python クラスとして実装された TRIE が必要な場合は、それらについて読んだ後に私が書いたものを次に示します。
class Trie:
def __init__(self):
self.__final = False
self.__nodes = {}
def __repr__(self):
return 'Trie<len={}, final={}>'.format(len(self), self.__final)
def __getstate__(self):
return self.__final, self.__nodes
def __setstate__(self, state):
self.__final, self.__nodes = state
def __len__(self):
return len(self.__nodes)
def __bool__(self):
return self.__final
def __contains__(self, array):
try:
return self[array]
except KeyError:
return False
def __iter__(self):
yield self
for node in self.__nodes.values():
yield from node
def __getitem__(self, array):
return self.__get(array, False)
def create(self, array):
self.__get(array, True).__final = True
def read(self):
yield from self.__read([])
def update(self, array):
self[array].__final = True
def delete(self, array):
self[array].__final = False
def prune(self):
for key, value in tuple(self.__nodes.items()):
if not value.prune():
del self.__nodes[key]
if not len(self):
self.delete([])
return self
def __get(self, array, create):
if array:
head, *tail = array
if create and head not in self.__nodes:
self.__nodes[head] = Trie()
return self.__nodes[head].__get(tail, create)
return self
def __read(self, name):
if self.__final:
yield name
for key, value in self.__nodes.items():
yield from value.__read(name + [key])
このバージョンは再帰を使用しています
import pprint
from collections import deque
pp = pprint.PrettyPrinter(indent=4)
inp = raw_input("Enter a sentence to show as trie\n")
words = inp.split(" ")
trie = {}
def trie_recursion(trie_ds, word):
try:
letter = word.popleft()
out = trie_recursion(trie_ds.get(letter, {}), word)
except IndexError:
# End of the word
return {}
# Dont update if letter already present
if not trie_ds.has_key(letter):
trie_ds[letter] = out
return trie_ds
for word in words:
# Go through each word
trie = trie_recursion(trie, deque(word))
pprint.pprint(trie)
出力：
Coool <algos> python trie.py
Enter a sentence to show as trie
foo bar baz fun
{
'b': {
'a': {
'r': {},
'z': {}
}
},
'f': {
'o': {
'o': {}
},
'u': {
'n': {}
}
}
}
これは以前の回答によく似ていますが、読みやすいです。
def make_trie(words):
trie = {}
for word in words:
head = trie
for char in word:
if char not in head:
head[char] = {}
head = head[char]
head["_end_"] = "_end_"
return trie
class TrieNode:
def __init__(self):
self.keys = {}
self.end = False
class Trie:
def __init__(self):
self.root = TrieNode()
def insert(self, word: str, node=None) -> None:
if node == None:
node = self.root
# insertion is a recursive operation
# this is base case to exit the recursion
if len(word) == 0:
node.end = True
return
# if this key does not exist create a new node
elif word[0] not in node.keys:
node.keys[word[0]] = TrieNode()
self.insert(word[1:], node.keys[word[0]])
# that means key exists
else:
self.insert(word[1:], node.keys[word[0]])
def search(self, word: str, node=None) -> bool:
if node == None:
node = self.root
# this is positive base case to exit the recursion
if len(word) == 0 and node.end == True:
return True
elif len(word) == 0:
return False
elif word[0] not in node.keys:
return False
else:
return self.search(word[1:], node.keys[word[0]])
def startsWith(self, prefix: str, node=None) -> bool:
if node == None:
node = self.root
if len(prefix) == 0:
return True
elif prefix[0] not in node.keys:
return False
else:
return self.startsWith(prefix[1:], node.keys[prefix[0]])