トライ木：接頭辞をたどって学ぶ

carを検索を押してみましょう。トライ木は各段階で一文字ずつたどり、carの終端の印を見つけます。読むのは3文字です。同じ16語を辞書順に並べて二分探索すると、catch、careful、card、carと照合します。どれもcaで始まるため、毎回3文字を読んでから次に進む方向を決めます。合計12文字です。ハッシュ表では、格納先の計算に3文字、そこにある単語の確認にさらに3文字を読み、計6文字になります。格納した16語をすべて検索すると、トライ木が読むのは70文字、ハッシュ表は140文字、二分探索は169文字です。トライ木ではノードの節約につながる共通の語頭が、二分探索では比較を長くしています。aaaからzzzまで、3文字の文字列を全17,576通り格納した場合、二分探索で一つを見つけるには平均26.4文字を調べます。トライ木で読むのは、やはり3文字です。

carで始まる単語を押してみましょう。トライ木はc、a、rをたどり、carより下の8ノードを訪ねます。合計11ノードのうち、6ノードが単語の終端です。dogやplanなどは調べません。辞書順リストでも、carで始まる単語はひとまとまりに並びます。二分探索で先頭の単語を見つけるまでに5回照合し、そこから順に6語を集め、最初に条件から外れるcatで止まります。読んだ単語は計12語です。ハッシュ表では、car、card、cargoの格納先が互いに無関係になるように作られているため、16語すべてを読んで一つずつ条件を確かめます。単語の追加では、トライ木の利点がはっきり現れます。carpetを挿入を押すと、トライ木は3ノードを追加し、既存のノードは動かしません。辞書順リストは空きを作るため、11語分のポインタを一つずつ後ろにずらします。

16語の文字数は合計70文字です。トライ木ではcar、card、careなどがc、a、rを共有するため、30ノードに収まります。ただし、ノードには文字以外の情報も必要です。省メモリな構成では、文字に1バイト、終端の印に1バイト、先頭の子と次の兄弟を指す8バイトのポインタにそれぞれ8バイトを使い、計18バイトになります。根を含む31ノードで558バイトです。単純なリストは各文字に1バイト、各単語に終端の1バイトと8バイトのポインタを使い、計214バイト。各ノードにアルファベットの各文字に対応するポインタを持たせ、配列の添字一つで次のノードを選べるようにすると、トライ木は6,479バイトとなり、リストの30倍に膨らみます。このページのように単語が最大14文字の場合、新しい単語の追加でトライ木のほうが少ないバイト数で済むのは、ノードをまったく増やさないときか、増やすノードが1個で単語が10文字以上あるときだけです。前者の例は、すでにplanetがある木にplanを加える場合です。省メモリな構成では、検索時間も増えます。目当ての文字を兄弟ノードから順に探すので、doorbellの検索には10回の比較が必要となり、二分探索より1回多くなります。