12.25 data.trie - Trie

Module: data.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の各要素がキーと値の対として現れます。

Class: <trie> ¶

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

このクラスはまた、ディクショナリインタフェースを実装しています (ディクショナリのためのジェネリック関数参照)。

Function: make-trie :optional tab-make tab-get tab-put! tab-fold tab-empty? ¶

{data.trie} 空のtrieを生成し返します。オプション引数は、 内部木のノードをどのようにマージするかをカスタマイズする手続きです。

それぞれのノードは子のノードを格納するテーブルを持つことができます。 キーシーケンスの要素でインデックスできます。(たとえば、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の適用結果です。

tab-empty? tab

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

Function: trie params kv … ¶

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

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

Function: trie-with-keys params key … ¶

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

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

Function: trie? obj ¶

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

Function: trie-num-entries trie ¶

{data.trie} trie中のエントリの数を返します。

Function: trie-exists? trie key ¶

{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)

Function: trie-partial-key? trie seq ¶

{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

Function: trie-get trie key :optional fallback ¶

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

Function: trie-put! trie key value ¶

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

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

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

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

Function: trie-delete! trie key ¶

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

Function: trie->list trie ¶

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

Function: trie-keys trie ¶

Function: trie-values trie ¶

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

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

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

Function: trie-longest-match trie seq :optional fallback ¶

{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
  )

Function: trie-common-prefix trie prefix ¶

Function: trie-common-prefix-keys trie prefix ¶

Function: trie-common-prefix-values trie prefix ¶

{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")はその両方を返します。

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

{data.trie} 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 ¶

{data.trie} 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 ¶

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