海外格安航空券 海外旅行保険が無料！
簡単!!Trie構造動的なTrie構造と静的なTrie構造さて、Trie構造を実現するために、皆さんはどのようにプログラムをされるでしょうか。 構造体ポインターを利用して木構造を造るというのが、多いかも知れません。良い線です。例えば、メモリーに乗りきらないほど大きなデータの場合を考えてみてください。 どうすればよいだろうか？ ハードウェアに堆肥しておく、圧縮を行う．．などなど、 データが大きくなると、構造体ポインターの利用だけでは、 速度の問題やら、データが収まらないなどなど．．解決していかなくてはならない 問題が肥大化していきます。 今回は静的なTrie構造と動的なTrieデータ構造について解説します。 (あくまで、mirage-tech語ですので．．使いどころは慎重に．) 動的なTrie構造各ノードの追加や入れ替えが、簡単に出来る構造を動的なTrie構造ということにします。 例えば、構造体ポインターを用いる方法などは木を追加する事が簡単に出来ます。 しかし、ハードディスク上に保存したTrie構造は簡単に入れ替えることは出来ません。 メモリーの場合のようにポインターのようなものを設計してみましょう。すると、 子のノードに移るごとにseekを行わなくてはならず、結構重い処理になってしまいます。 そして、入れ替えを行うごとに、離れたところに子ノートが配置されるようになり だんだんとseekに掛かる時間が大きくなって行きます。また、データを圧縮する場合にもハードディスクにデータを落とす場合も整列化をしてあげなくては なりません。整列化されたデータを静的なTrie構造と呼ぶ事にしましょう。静的なデータは前述したとおり、 追加や入れ替えるのに、大きなコストを必要とします。 |
無料ホームページ 楽天モバイル[UNLIMITが今なら1円] 海外格安航空券 海外旅行保険が無料！