O(L)のデータ構造／パターンパッチング - Tries
WEB+DB PRESS vol.42の特集「アルゴリズム＆データ構造」でもとりあげられていたTrie(とらい; p34-37)について調べてみたので、忘れないようにメモです。
Trie(s)というのは単語を辞書のなかから見つけ出すときに人がふつうに行っている探し方のアルゴリズムです。例えば、poolならまず、pのところに行って、次にoのところに行って、、、つまり、p -> o -> o -> lと探していきます。続いてprizeを見つけるとしたら、p -> r -> i -> z -> eですが、先頭の文字が同じpなので、pの付近からはずれたところから始めたりはしません。この二つの単語の場合pをprefixと見なすのがTrieです。poolとpoleだったらprefixはpoにのびていきます。prefixがのびていけばいくほど候補は減っていきます。ちょうどIDEのメソッド補完機能のように文字を打てば打つほど候補が減っていくのと同じです。例えば、pool, prize, preview prepare, produce, progressなら、木をこのように
p o o l
1 --- 2 --- 3 --- 4 --- 5 pool
| r i s e
+--- 6 --- 7 --- 8 --- 9 prize
| e v i e w
+--- 10 --- 11 --- 12 --- 13 --- 14 preview
| | p a r e
| +--- 15 --- 16 --- 17 --- 18 prepare
| o d u c e
+--- 19 --- 20 --- 21 --- 22 --- 23 produce
| g r e s s
+--- 24 --- 25 --- 26 --- 27 --- 28 progress
作ると、pを打った時点での候補は6つありますが、次にrを打つと、候補が5つに減ります。さらにeを打つと候補は2にしぼられ、続いてvを打つとついに一つの単語だけになるというものです。つまり、検索時の計算量は単語の文字数をLとすると、O(L) (big o of L)で済むアルゴリズムです。単なるHashのデータ構造では常に全ての文字のマッチングをとりますが、Trieなら、途中までのマッチングで済むこともあり、より計算量は少なくて済むという利点があります。概要については「Topcoder」が参考になります。
Trieという名前は"information retrieval system"の"retrieval"のinfix(prefix, infix, suffixのinfix)であるtrieから付けられていて、pieやlieのように"ie"を"あい"と発音することにして、"とらい"と呼ぶことになったそうです。
Trieは単語を木構造にマッピングしますがマッピング方法にはいくつかあります。加えて、木の節と枝の呼び方も文献によっていくつかありました。例えば節はvertexやnodeで、枝はedgeやarcです。話がややこしくなるので、とりあえずvertexとedgeに統一して考えることにしました。木のvertexに直接文字を割り当てる方式やvertexには数字の番号を降って、edgeをとある文字が入力されたときに移動した軌跡と見なしてedgeに文字を対応させる方式もあります。WEB+DBでも解説されている有名なDouble Arrayによる木の表現とパターンマッチング方法は後者で、しかもvertexの番号の振り方も複雑です。
Double Arrayというのは木構造の節のところで次にどこに行くのかを探す時間を減らすために考えだされたアルゴリズムで、base, check, tailの3つのlistと変数POSを使って木構造を表現しています。文献[Aoe, J., K. Morimoto, and T. Sato. An Efficient Implementation of Trie Structures. Software-Practice and Experience. Vol. 22, 9 (Sep 1992). pp. 695-721.]に記載されていた例によると、
b a c str[5]="helor#" bachelor 1 --- 7 --- 3 --- 5--- 15 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 ------------------------------------------- base 4 0 1 -15 -1 -12 1 0 0 0 0 0 0 0 -9 check 0 0 7 3 3 3 1 0 0 0 0 0 0 0 1 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 ---------------------------------------- tail h e l o r # ? ? a r # g e # y # POS=17
d str[6]="ge#" badge +--- 6 b str[4]="y#" baby +--- 4 j str[15]="ar#" jar
のように表現されます。この方式では文字は#=1, a=2, b=3, c=4, d=5, e=6, g=7, h=8, j=9, l=10, o=11, r=12, y=13のように適当な数値にマッピングされています。単語を探すときには、
b
1 --- 7 (「bが入力されたことで状態1が7に遷移した」と考える)
base[1] + c('b') = 4 + 3 = 7 (c('b')はbに対応する数値の意味)
check[7] = 1 (check[7]が1かどうか調べる。(vertex 7 の親が 1 かどうかを調べる))
のようにbaseとlistの中を探してゆきパターンパッチングを行う方法です。単語をbaseやcheckに追加・削除する方法などは上記の文献[An Efficient Implementation of Trie Structures. Software-Practice and Experience.]に詳細が解説されています。若干baseの作り方が違うのですが、「An Implementation of Double-Array Trie」もDouble Array方式です。WEB+DB PRESSで紹介されているようにDarts: Double ARray Trie SystemもDouble Array方式です。
Double Arrayではなく木構造を忠実に作っているものですが、Java言語による実装がCrazyMarty | Odds and Sodsにあったので試してみました。この実装はdump, quit, add, search, delete, avg, numのコマンドを実行できるようになっています。ただ、このままでは日本語を扱えなかったので、TrieRunner.javaをこのように書き換えました。
import java.util.Scanner; /** * Created by IntelliJ IDEA. * User: mpzarde * Date: Jul 17, 2006 * Time: 8:57:35 PM * Modified by: Yoko Harada (Jul 11, 2008) */ public class TrieRunner { /** * This is a simple little test routine * included so this class can be run as * an application to test its cababilities */ public static void main(String args[]) { Trie main = new Trie(); System.out.print("dump, quit, add, search, delete, avg, num: "); Scanner scanner = new Scanner(System.in); while (scanner.hasNext()) { String str = scanner.next(); if ("dump".equals(str)) { System.out.println("\nDUMPING:\n--------"); main.dump(); } else if ("quit".equals(str)) { return; } else if ("add".equals(str)) { String word = scanner.next(); System.out.println("Inserting " + word + "..."); try { main.insert(word, word); } catch (NonUniqueKeyException e) { System.out.println(e.toString()); } } else if ("search".equals(str)) { String word = scanner.next(); System.out.println("Searching for " + word + "..."); Object result = null; result = main.search(word); if (result == null) { System.out.println("Not found"); } else if (result instanceof Trie) { System.out.println("Multiple matches:"); Trie trie = (Trie) result; trie.quickDump(); } else { System.out.println("Found. Value is " + result.toString()); } } else if ("delete".equals(str)) { String word = scanner.next(); System.out.println("Deleting " + word + "..."); try { main.remove(word); } catch (java.util.NoSuchElementException e) { System.out.println(e.toString()); } catch (NonUniqueKeyException e) { System.out.println(e.toString()); } } else if ("avg".equals(str)) { System.out.println("\nAverage clash: " + Float.toString(main.averageClash()) + "\n"); } else if ("num".equals(str)) { System.out.println("\nAverage clash: " + Float.toString(main.averageClash()) + "\n"); } else { System.out.println("Unknown command '" + str + "'"); } System.out.println("\nTrie contains " + main.length() + " elements"); System.out.print( "dump,quit,add,search,delete,avg,num: "); } } }
百人一首の「な」で始まる8つの句の冒頭部分[ながからむ,ながらへば,なげきつつ,なげけとて,なつのよは,なにしおはば,なにはえの,なにはがた]を入力してみました。dumpを指定してどのような木構造になったかを見てみると、
DUMPING:[な] [に] [は] なにはえの なにはがた なにしおはば [げ] なげきつつ なげけとて [が] ながからむ ながらへば なつのよは
- -
のようになっています。何字決まりの句かがわかります。たとえば、「な」の一文字でsearchを行うと、
Searching for な... Multiple matches: なにはえの なにはがた なにしおはば なげきつつ なげけとて ながからむ ながらへば なつのよは
と8つすべての候補が表示されましたが、「なげ」の二文字でsearchを行うと、
Searching for なげ... Multiple matches: なげきつつ なげけとて
と二つにしぼられました。
実装は簡単ではないのですが、とても面白いアルゴリズムです。
