Suffix Arrayの練習

前から少し気になっていたhttp://ja.wikipedia.org/wiki/Suffix_Arrayを試してみた。
gitの練習がてらgithubに => http://github.com/komamitsu/ocaml-suffixarray。

これと、Str.search_forwardでちょっと性能を比べてみたのだけど、Str.search_forwardの方が圧倒的に早かったのであった…

まずは適当なテキストを作る。

komamitsu@potato:~/git/ocaml-suffixarray$ w3m -dump http://caml.inria.fr/pub/docs/oreilly-book/html/book-ora015.html > hogetext

そして、Module Suffixarrayを使うサンプルを適当に作成。1000回試行してみる。

open Printf

let debug = false
let loop_count = 1000
let keyword = "multiplication"
let filename = "hogetext"

let create_text filename =
  let file = open_in filename in
  let rec read_lines str =
    try
      let line = input_line file in
      read_lines (str ^ line ^ "\n")
    with End_of_file -> str
  in
  let text = read_lines "" in
  close_in file;
  text

let test_suffix_array suffixarray =
  if debug then printf "==== test_suffix_array ====\n";
  let findlist = Suffixarray.find suffixarray keyword in
  if debug then List.iter (fun x -> printf "[%d]\n" x) findlist

let test_regexp text =
  if debug then printf "==== test_regexp ====\n";
  let re = Str.regexp keyword in
  let rec loop start =
    try
      let pos = Str.search_forward re text start in
      if debug then printf "[%d]\n" pos;
      loop (pos + 1)
    with Not_found -> ()
  in
  loop 0

let rec loop n f v =
  if n <= 0 then ()
  else (f v; loop (n - 1) f v)

let _ =
  let text = create_text filename in
  let suffixarray = Suffixarray.create text in
  printf "text length is %d.\n" (String.length text);
  let suffixarray_start = Unix.time () in 
  loop loop_count test_suffix_array suffixarray;
  let suffixarray_end = Unix.time () in   
  let regexp_start = Unix.time () in
  loop loop_count test_regexp text;
  let regexp_end = Unix.time () in
  printf "regexp:       %f sec\n" (regexp_end -. regexp_start);
  printf "suffix array: %f sec\n" (suffixarray_end -. suffixarray_start)

これをコンパイルして実行させると… すごい負け!

komamitsu@potato:~/git/ocaml-suffixarray$ ocamlfind c -package str,unix -linkpkg -o sample suffixarray.cmo sample.ml
komamitsu@potato:~/git/ocaml-suffixarray$ ./sample
text length is 50659.
regexp:       1.000000 sec
suffix array: 109.000000 sec

ちなみに、何の工夫もなくテキスト末尾までの文字列を格納していたら、やはりメモリ消費量が激しくSwap起こしまくりだったので、先頭の一センテンスのみ格納するようにして逃げています。

何かバグっているのか… まぁ雰囲気が掴めたということで良しとするかなぁ。

あと途中で、激しくCのポインタを使いたくなった。空間効率のコントロールしやすさは、Cが一番かなぁ。