11.54 util.trie - Trie

Module: util.trie

このモジュールはTrieを提供します。Trieはディレクトリに似 たデータ構造で、キーを値に写像します。また、キーは任意のシーケンスです。 内部的にはデータはツリーとして保持されます。このとき各ノードがキーシー ケンスの各要素に対応します。キーの検索は O(n) で、n はキーの長さです。 したがって、全体のエントリ数には余り影響を受けません。また、キーが共通 の接頭辞をもつような値の集合を簡単にみつけられます。

以下のサンプルを見れば考え方が理解できると思います。

(define t (make-trie)) ;; create a trie (trie-put! t "pho" 3) ;; populate the trie (trie-put! t "phone" 5) (trie-put! t "phrase" 6) (trie-get t "phone") ⇒ 5 ;; lookup (trie-common-prefix t "pho") ;; common prefix search ⇒ (("phone" . 5) ("pho" . 3)) (trie-common-prefix-keys t "ph") ⇒ ("phone" "pho" "phrase")

Trieでは文字列キーを使うことが多いですが、それに限定される必要はありま せん。あらゆるシーケンス(See section gauche.sequence - シーケンスフレームワーク)をキーにすることが できます。キーの型が違えば、別のキーとして扱われます。

(trie-put! t '(#\p #\h #\o) 8) ;; different key from "pho"

Trieは<collection>を継承しており、コレクションフレームワークを ビルダも含めて実装しています。それゆえ、ジェネリックなコレクション操作 をTrieに適用することが可能です(gauche.collection - コレクションフレームワーク参照)。 反復するとTrieの各要素がキーと値の対として現れます。

Class: <trie>

Trieクラス。パブリックなスロットはありません。trieを操作するには以下の 手続きを使ってください。

Function: make-trie &optional tab-make tab-get tab-put! tab-fold

空のtrieを生成し返します。4つのオプション引数があり、これらは、 内部木のノードをどのようにマージするかをカスタマイズする手続きです。

それぞれのノードは子のノードを格納するテーブルを持つことができます。 キーシーケンスの要素でインデックスできます。(たとえば、trieがキーとし え文字列を使っているとすると、ノードのテーブルは文字でインデックスされ ています。)

tab-make

引数なしの手続き。呼ばれるとノード用の空テーブルを生成し返します。

tab-get tab elt

eltでインデックスされた子ノードを返すか、あるいはeltに対応 する子がテーブルにない場合には #fを返します。

tab-put! tab elt child-node

child-nodeが#fでなければ、child-nodeにeltとい うインデックスをつけて保存します。child-nodeが#fなら eltのインデックスをもつエントリを削除します。どちらの場合にも この手続きは更新されたテーブルを返します。

tab-fold tab proc seed

tab内の各インデックスと要素ごとにprocを呼びます。シード値 が順に渡されていきます。シード値の初期値はseedです。すなわち、 procの型は(index, node, seed) -> seed のような型というこ とになります。返り値は最後のprocの適用結果です。

デフォルトではeqv?-ハッシュ可能であることが仮定されます。すなわ ち、以下の手続きが使われます。

tab-make: (lambda () (make-hash-table 'eqv?)) tab-get: (lambda (tab k) (hash-table-get tab k #f)) tab-put!: (lambda (tab k v) (if v (hash-table-put! tab k v) (hash-table-delete! tab k)) tab) tab-fold: hash-table-fold

以下の例では子を管理するのに連想リストを用いるtrieを作成しています。 文字列キーの比較は大文字小文字を無視する方法で行っています。

(make-trie list (cut assoc-ref <> <> #f char-ci=?) (lambda (t k v) (if v (assoc-set! t k v char-ci=?) (alist-delete! k t char-ci=?))) (lambda (t f s) (fold f s t)))

tab-put!が更新されたテーブルを返すというのは重要で、これのおか げで、テーブル構造をおてがるに置き換えることができます。たとえば、 子の数が少い場合にはテーブルに連想リストを使い、いったん子の数がある閾 値を越えたら、(文字コードでインデックスされた)ベクタを使うように設計す ることができます。

Function: trie params kv …

初期の内容がkv … であるようなtrieを構成します。ここで、 kvはキーと値の対です。paramsはtrieを生成するときに make-trieに渡される引数のリストです。以下の例は2つのエントリ とデフォルトのテーブル手続をもつtrieを生成します。

(trie '() '("foo" . a) '("bar" . b))

Function: trie-with-keys params key …

キーにだけ関心がある場合には便利なtrie。各値はキーと同じ。以下 の例では2つのエントリとデフォルトのテーブル手続をもつtrieを生成します。

(trie-with-keys '() "foo" "bar")

Function: trie? obj

objがtrieなら#tを返し、さもなければ#fを返します。

Function: trie-num-entries trie

trie中のエントリの数を返します。

Function: trie-exists? trie key

trieがkeyというキーのエントリを含む場合には#tを返し、 さもなければ、#fを返します。

Function: trie-get trie key &optional fallback

trie中のkeyをもつエントリがあれば、それにむすびついている 値を返します。そのようなエントリがない場合、fallbackが与えられて いればそれを返し、さもなければ、エラーシグナルがあがります。

Function: trie-put! trie key value

keyに結びついたvalueをtrieに挿入します。

Function: trie-update! trie key proc &optional fallback

trie中のエントリの検索が一度きりしか起らないことをのぞけば以下の コードのように動きます。

(let ((val (trie-get trie key fallback))) (trie-put! trie key (proc val)))

Function: trie-delete! trie key

trieからkeyに関連するエントリを削除します。 そのようなエントリがない場合にはこの手続きはなにもしません。

Function: trie->list trie

trieの各エントリを(key . value)という対にして すべてのエントリの対のリストを返します。エントリの順序は未定義です。

Function: trie-keys trie

Function: trie-values trie

それぞれ、trieのすべてのキーのリスト、すべての値のリストを返しま す。順序は未定義です。

Function: trie->hash-table trie ht-type

ht-typeタイプのハッシュテーブル(ハッシュテーブルのタイプについて はハッシュテーブルを参照)を作成し、trieのすべてのキーと値の対を セットします。

Function: trie-common-prefix trie prefix

Function: trie-common-prefix-keys trie prefix

Function: trie-common-prefix-values trie prefix

prefixではじまるキーをもつエントリをすべて集め、 trie-common-prefixはその各エントリを(key . value)の対にし たリストを返します。trie-common-prefix-keysは、キーのリストを trie-common-prefix-valuesは値のリストを返します。返されるリスト のエントリの順序は未定義です。 trieに指定したprefixをもつキーのエントリがなければ、 空リストが返されます。

接頭辞照合ではシーケンスの型を考慮しないことに注意してください。 trieのなかに"foo"と(#\f #\o #\o)に対応するエントリ があれば、(trie-common-prefix trie "foo")はその両方を返します。

Function: trie-common-prefix-fold trie prefix proc seed

prefixではじまるキーをもつ各エントリに対して、procを3つの 引数、エントリのキー、値、現在のシード値で呼びます。seedは最初の シード値として使われ、procが返す値は次のprocの呼び出しのシー ド値として使われます。procが返した最後の値が trie-common-prefix-foldから返ります。 procが適用される順序は未定義です。trieがprefixを持つ キーのエントリを含まない場合にはprocが呼ばれることはなく、 seedが返ります。

Function: trie-common-prefix-map trie prefix proc

Function: trie-common-prefix-for-each trie prefix proc

mapやfor-eachをfoldを合せたのと同じように、 trie-common-prefix-foldに合せたものです。 trie-common-prefix-mapはprocをマッチするエントリのキーと 値に適用し結果をリストにあつめます。 trie-common-prefix-for-eachも同じくprocを適用しますが 結果は捨てます。

Function: trie-fold trie proc seed

Function: trie-map trie proc

Function: trie-for-each trie proc

これらの手続きはcommon-prefix版とおなじような働きをしますが、 trie全体をトラバースします。

This document was generated by Shiro Kawai on November, 22 2009 using texi2html 1.78.