ブログの更新がとまっていましたが、また少しずつ更新してきたいと思います。 今回はtrie(トライ)の最近の話をしたいと思います。 trieはキー集合を扱うためのデータ構造の一種です。例えば、単語集合からなる辞書であったり、クロールしたURL情報を扱ったり、最近だと、KVS(Key Value Store)のようにキーを介してデータを保存、読み込みをしたりと様々な場面で利用されます。 同じようにキー集合を格納するデータ構造としてハッシュを利用する方法があります。キーからハッシュ値を計算し、その場所に文字列へのポインタを格納しておくデータ構造です。ハッシュを利用した場合とtrieを利用した場合の一番の大きな違いは、trieの場合だと、ある文字列から始まるキーを全て列挙する、いわゆる接頭辞探索ができることです。例えば”te”で始まる文字列を網羅的に調べることができます。木をたどって、”te”の下
![最近のtrieの話(xbwなど) - Preferred Networks Research & Development](https://cdn-ak-scissors.b.st-hatena.com/image/square/3a80aa689dba02734140530cce65593efdea308d/height=288;version=1;width=512/https%3A%2F%2Ftech.preferred.jp%2Fwp-content%2Fuploads%2F2011%2F05%2Ftrie-300x207.jpg)