アルゴリズムとデータ構造」トピックの28回目は、文字列処理の古典的なデータ構造であるTrieについてお話しします。
この4つの記事では、ゲーム理論のアルゴリズムをいくつか紹介していますが、その中でも最も広く使われ、重要なものが最後のSG関数です。これらを理解した上で、一般的なゲーム理論のアルゴリズムを扱えば十分です。ゲーム理論そのものは、このように非常に深い理論的基礎を持っている学問であり、表面的なものですが、私たちは自分の研究に興味を持っており、それは非常にやりがいのあるものになると信じています。
以前、素晴らしい記事を読んだことがあります。
何年も前、携帯電話がまだノキアのフィーチャーフォンだった頃、アドレス帳から連絡先を検索するシンビアンシステム用のソフトウェアを開発したんです。そのソフトの機能はとてもシンプルで、連絡先を保存し、ピンインやピンインの頭文字で対応する連絡先を見つけるというものです。ここで、漢字とピンインの対応付けをする必要がありますが、それほど複雑なことではありません。
このソフトは、非常に早く作られ、作られたとき、それは使用され、非常にうまく動作することがわかりました。しかし、すぐに予期しない問題が発生した、つまり、より多くの連絡先が、ソフトウェアが非常にゆっくりと実行されると、カードです。カードの理由も非常に単純です、彼は検索を見つけるために方法の横断を使用して連絡先を検索するステップので。最初、彼はいくつかの最適化の解決策と野生のアイデアを作ったが、それは改善することができますが、それは全く問題を解決することはできません。その後、彼は関連する情報を検索することを余儀なくされ、彼は今日のTrieの主人公を見つけ、このアルゴリズムを使用した後、問題は即座に解決され、たとえ何千もの連絡先のストレージが再び遅れることはありません。それ以来、彼はアルゴリズムが単なる小手先のテクニックではなく、本当に便利なものであることに気づきました。
この投稿の問題を基に、Trieがどのように機能し、なぜそれを解決するのかを見てみましょう。
Trie
辞書の木と接頭辞の木のタイトルから、その一般的な原理、つまり、データを格納する辞書と接頭辞の形でブレインストーミングすることができます。少し抽象的に聞こえますが、実際には、完全に理解するためにイメージを見てください。
図からわかるように、Trie木は多項木です。ツリーの各ノードには文字が格納され、ルートノードからノードへのパス上の文字が連結されて単語が作られます。つまり、すべての単語はこのように縦に並んだ形でツリーに格納されているのです。
この方法で保存する利点は何ですか？最大の利点は、同じ接頭辞を持つ単語が接頭辞を共有できることです。たとえば、ana、ann、この2つの単語の最初の2文字は同じanなので、共通の接頭辞リンクを持つことになります。このような構造では、単語がツリーの中にあるかどうかを調べる必要があるとき、ツリーのルートから走査を開始するだけで、ノードの末尾に対応するノードを見つけることができれば、その単語が存在することを意味し、そうでなければ、その単語は存在しないことを意味します。
例えば、doeという単語を見つけたい場合、まずルートノードでdという文字を探し、dが存在することがわかったのでdに移動します。次にoという文字を探し、dノードの下にoという文字があることがわかったのでoに移動します。しかし、ここで問題があります。 doeaという単語が存在するとして、doeを調べてもそれは見つかりますが、doeという単語は実際には存在しないのです。
実際、これは問題になる可能性があるため、特定の単語の末尾であるかどうかをノード間で記録する必要があります。この場合、対応する単語を見つけるだけでなく、他の単語の接頭辞が単語とみなされるのを防ぐ必要があります。
単語を挿入するプロセスはクエリに非常に近く、クエリ・ノードが存在しない場合は手動で作成することを除けば、これもツリーの走査プロセスです。単語全体が挿入された後、最後の文字に対応するノードにマークが付けられ、単語の終わりであることが示されます。
単純なトライツリーは、追加とクエリを完了する必要がありますすることができ、削除を含む場合は、単にノードを通過した単語の数の間でノードに維持する必要がありますすることができます。削除では、ノードの数が0に遭遇した場合、直接削除することができますマーク-1を通過する道に沿ってノードの数。
コード実装
話しているだけで練習に来るのは当たり前。
この説明でお分かりいただけると思いますが、Trieの原理ははっきり言って非常にシンプルで、実装は難しくありません。インターネット上の多くのバージョンがありますが、それらの多くは、プロセス指向の実装であり、私はバージョンのPythonのオブジェクト指向の実装を使用して、それを少しカプセル化。原理を理解した後、あなたはバージョンの独自のスタイルを開発するために、独自のニーズに応じてすることができ、コードは実際にはあまりにも重要ではありませんが、メインはまだ原理を理解しています。
Trieツリーを2つの部分に分け、最初の部分はツリー上のノードです。Trieツリー上のノードには、2つの関数を提供する必要があります。1つ目の関数は、現在のノードが文字列の終端であるかどうかを返す関数で、2つ目の関数は、文字に基づいて後継ノードを見つける関数です。つ目の関数は、文字に基づいて後継ノードを見つける関数です。 必要なことは、後継要素を格納するフラグと dict 属性をクラスに設定することだけです。
class Node:
def __init__(self, is_leaf=False):
self.child = {}
self._is_leaf = is_leaf
@property
def is_leaf(self):
return self._is_leaf
@is_leaf.setter
def is_leaf(self, is_leaf):
self._is_leaf = is_leaf
# 子ノードを結合する
def put(self, key, value):
self.child[key] = value
@staticmethod
# 文字を数字に変換する
# 実際には、dictの使用は必要ないので、子を格納するために配列を使用する場合は、添え字を計算するために使用する必要がある
def get_idx_of_str(_str):
if len(_str):
return -1
if ord('a') <= ord(_str) <= ord('z'):
return ord(_str) - ord('a')
else:
return ord(_str) - ord('A') + 26
# 文字に基づいて次のノードを取得する
def get_next_node(self, _str):
if len(_str) != 1:
return None
idx = Node.get_idx_of_str(_str)
return self.child.get(idx, None)
def get_node(self, key):
return self.child.get(key, None)
ここでは、プロパティのカプセル化で2つのメソッドをis_leafされるので、簡単に使用することができ、これはまた、一般的なプラクティスです。ノードの後、Trieクラスを開発することは非常に便利です、Trieクラスは、2つのメソッドを実装する必要があるだけで、1つは、文字列、文字列クエリを挿入することです。ノードクラスでは、これらの2つのメソッドを実装することも非常に簡単です。
class Trie:
def __init__(self):
self.root = Node()
def insert(self, _str):
cur = self.root
# 文字の繰り返し
for c in _str:
# 次のノードを探す
if cur.get_next_node(c) is None:
# ノードが存在しない場合は、新しいノードを作って自分で挿入する。
key = Node.get_idx_of_str(c)
cur.put(key, Node())
cur = cur.get_node(key)
# そうでなければ、次の
else:
cur = cur.get_next_node(c)
cur.is_leaf = True
def query(self, _str):
cur = self.root
# 文字の反復
for c in _str:
# クエリがFalseを返さない場合
if cur.get_next_node(c) is None:
return False
cur = cur.get_next_node(c)
# 文字列の末尾が
return cur.is_leaf
どちらのコードも読めないはずはないので、最後に、試しに使ってみてください：
if __name__ == "__main__":
trie = Trie()
trie.insert('abcda')
trie.insert('abcde')
trie.insert('eecdab')
trie.insert('mout')
trie.insert('ymm')
print(trie.query('abcda'))
print(trie.query('mout'))
print(trie.query('ym'))
出力は予想と一致しており、確率が正しいことを示しています。
同じ接頭辞の文字列のトライツリーを同じリンクに格納することで、容量を大幅に節約できます。また、単語を検索する場合、Trieツリーを走査すると、その単語の長さだけ結果が得られます。また、Nodeクラスに他の情報を格納することで、Trieをdictのキーとして文字列に変換することができます。
トライツリーは機械学習、特に自然言語処理の分野でも広く使われています。高速な単語分割、単語頻度統計、ファジィマッチングなどの機能を実現することができます。また、トライツリーは、データ空間の二重配列トライツリーやACオートマトンなどの圧縮など、多くの拡張性を持っています。
