data.trie - 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 gauche.sequence - シーケンスフレームワーク)をキーにすることが
できます。キーの型が違えば、別のキーとして扱われます。
(trie-put! t '(#\p #\h #\o) 8) ;; different key from "pho"
Trieは<collection>を継承しており、コレクションフレームワークを
ビルダも含めて実装しています。それゆえ、ジェネリックなコレクション操作
をTrieに適用することが可能です(gauche.collection - コレクションフレームワーク参照)。
反復するとTrieの各要素がキーと値の対として現れます。
{data.trie}
Trieクラス。パブリックなスロットはありません。trieを操作するには以下の
手続きを使ってください。
このクラスはまた、ディクショナリインタフェースを実装しています (ディクショナリのためのジェネリック関数参照)。
{data.trie}
空のtrieを生成し返します。オプション引数は、
内部木のノードをどのようにマージするかをカスタマイズする手続きです。
それぞれのノードは子のノードを格納するテーブルを持つことができます。 キーシーケンスの要素でインデックスできます。(たとえば、trieがキーとし え文字列を使っているとすると、ノードのテーブルは文字でインデックスされ ています。)
tab-make引数なしの手続き。呼ばれるとノード用の空テーブルを生成し返します。
tab-get tab elteltでインデックスされた子ノードを返すか、あるいはeltに対応
する子がテーブルにない場合には #fを返します。
tab-put! tab elt child-nodechild-nodeが#fでなければ、child-nodeにeltとい
うインデックスをつけて保存します。child-nodeが#fなら
eltのインデックスをもつエントリを削除します。どちらの場合にも
この手続きは更新されたテーブルを返します。
tab-fold tab proc seedtab内の各インデックスと要素ごとにprocを呼びます。シード値
が順に渡されていきます。シード値の初期値はseedです。すなわち、
procの型は(index, node, seed) -> seed のような型というこ
とになります。返り値は最後のprocの適用結果です。
tab-empty? tabtabが空なら#tを、そうでなければ#fを返す手続きです。
この手続きは省略するか#fを渡すことができます。その場合は空かどうかを
チェックするのにtab-fold手続きが使われますが、少々重くなるかもしれません。
デフォルトでは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
tab-empty?: (lambda (tab) (zero? (hash-table-num-entries tab)))
以下の例では子を管理するのに連想リストを用いる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))
null?)
tab-put!が更新されたテーブルを返すというのは重要で、これのおか
げで、テーブル構造を実行中に置き換えることができます。たとえば、
子の数が少い場合にはテーブルに連想リストを使い、いったん子の数がある閾
値を越えたら、(文字コードでインデックスされた)ベクタを使うように設計す
ることができます。
{data.trie}
初期の内容がkv … であるようなtrieを構成します。ここで、
kvはキーと値の対です。paramsはtrieを生成するときに
make-trieに渡される引数のリストです。以下の例は2つのエントリ
とデフォルトのテーブル手続をもつtrieを生成します。
(trie '() '("foo" . a) '("bar" . b))
{data.trie}
キーにだけ関心がある場合には便利なtrie。各値はキーと同じ。以下
の例では2つのエントリとデフォルトのテーブル手続をもつtrieを生成します。
(trie-with-keys '() "foo" "bar")
{data.trie}
objがtrieなら#tを返し、さもなければ#fを返します。
{data.trie}
trie中のエントリの数を返します。
{data.trie}
trieがkeyというキーのエントリを含む場合には#tを返し、
さもなければ、#fを返します。
(let1 t (trie '() '("foo" . ok))
(list (trie-exists? t "foo")
(trie-exists? t "fo")
(trie-exists? t "bar")))
⇒ '(#t #f #f)
{data.trie}
trieの中に少なくともひとつ、seqと同じではないがseqを
プリフィクスとするようなキーがあれば#tを返します。
seqと一致するキーが他にあるかないかは結果には影響を及ぼしません。
下の例を見てください。
(define t (trie '() '("foo" . ok) '("fo" . ok)))
(trie-partial-key? t "f") ⇒ #t
(trie-partial-key? t "fo") ⇒ #t
(trie-partial-key? t "foo") ⇒ #f
(trie-partial-key? t "bar") ⇒ #f
{data.trie}
trie中のkeyをもつエントリがあれば、それにむすびついている
値を返します。そのようなエントリがない場合、fallbackが与えられて
いればそれを返し、さもなければ、エラーシグナルがあがります。
{data.trie}
keyに結びついたvalueをtrieに挿入します。
{data.trie}
trie中のエントリの検索が一度きりしか起らないことをのぞけば以下の
コードのように動きます。
(let ((val (trie-get trie key fallback))) (trie-put! trie key (proc val)))
{data.trie}
trieからkeyに関連するエントリを削除します。
そのようなエントリがない場合にはこの手続きはなにもしません。
{data.trie}
trieの各エントリを(key . value)という対にして
すべてのエントリの対のリストを返します。エントリの順序は未定義です。
{data.trie}
それぞれ、trieのすべてのキーのリスト、すべての値のリストを返しま
す。順序は未定義です。
{data.trie}
ht-typeタイプのハッシュテーブル(ハッシュテーブルのタイプについて
はハッシュテーブルを参照)を作成し、trieのすべてのキーと値の対を
セットします。
{data.trie}
seqのプレフィクスになっているキーのうちもっとも長いものを見つけて、
そのキーと値のペアを返します。そういったキーが見つからなかった場合は、
fallbackが与えられればそれを返し、なければエラーが通知されます。
この手続きと以下のtrie-common-prefix-*手続きを混同しないようにしてください。
この手続きでは、キーが引数のプレフィクスです。
trie-common-prefix-*手続きでは、引数がキーのプレフィクスです。
(let1 t (make-trie)
(trie-put! t "a" 'a)
(trie-put! t "ab" 'ab)
(trie-longest-match t "abc") ⇒ ("ab" . ab)
(trie-longest-match t "acd") ⇒ ("a" . a)
(trie-longest-match t "ab") ⇒ ("ab" . ab)
(trie-longest-match t "zy") ⇒ error
)
{data.trie}
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")はその両方を返します。
{data.trie}
prefixではじまるキーをもつ各エントリに対して、procを3つの
引数、エントリのキー、値、現在のシード値で呼びます。seedは最初の
シード値として使われ、procが返す値は次のprocの呼び出しのシー
ド値として使われます。procが返した最後の値が
trie-common-prefix-foldから返ります。
procが適用される順序は未定義です。trieがprefixを持つ
キーのエントリを含まない場合にはprocが呼ばれることはなく、
seedが返ります。