簡単!!Trie構造

動的なTrie構造と静的なTrie構造

　さて、Trie構造を実現するために、皆さんはどのようにプログラムをされるでしょうか。構造体ポインターを利用して木構造を造るというのが、多いかも知れません。

　良い線です。例えば、メモリーに乗りきらないほど大きなデータの場合を考えてみてください。どうすればよいだろうか？
ハードウェアに堆肥しておく、圧縮を行う．．などなど、データが大きくなると、構造体ポインターの利用だけでは、速度の問題やら、データが収まらないなどなど．．解決していかなくてはならない問題が肥大化していきます。

　今回は静的なTrie構造と動的なTrieデータ構造について解説します。 (あくまで、mirage-tech語ですので．．使いどころは慎重に．)

動的なTrie構造

　各ノードの追加や入れ替えが、簡単に出来る構造を動的なTrie構造ということにします。例えば、構造体ポインターを用いる方法などは木を追加する事が簡単に出来ます。しかし、ハードディスク上に保存したTrie構造は簡単に入れ替えることは出来ません。　メモリーの場合のようにポインターのようなものを設計してみましょう。すると、子のノードに移るごとにseekを行わなくてはならず、結構重い処理になってしまいます。　そして、入れ替えを行うごとに、離れたところに子ノートが配置されるようになりだんだんとseekに掛かる時間が大きくなって行きます。

　また、データを圧縮する場合にもハードディスクにデータを落とす場合も整列化をしてあげなくてはなりません。整列化されたデータを静的なTrie構造と呼ぶ事にしましょう。静的なデータは前述したとおり、追加や入れ替えるのに、大きなコストを必要とします。

テレワークならECナビ Yahoo 楽天 LINEがデータ消費ゼロで月額500円～！
無料ホームページ無料のクレジットカード海外格安航空券　海外旅行保険が無料！海外ホテル