strstr、もしくは文字列内の文字列を探す関数

OCaml

OCaml の標準ライブラリにはなぜ文字列内の文字列を探す関数がないのか？ C にだって、char * strstr(const char *haystack, const char *needle) という関数があって、haystack(藁の山)から needle(針)を探し出してくれるのに、、、おかしいよ、変だよ。

おかしいか？変か？

まあ、おかしいかもしれないね。

でも理由がないわけじゃない。文字列サーチは使われる状況によって、効率のよい書き方が異なるからだ。

  • そもそも検索回数、needle, haystack の長さすべてが小さければ、無理やり頭から探す C の strstr と同じ方式が手っ取り早い。
  • 同じ needle を膨大な種類の haystack から見つけ出す場合、正規表現がよい。
  • 一回毎に needle が違う場合は、一つ一つの needle に対応する正規表現を作る時間が無駄なので strstr の方がいいかもしれない。
  • サーチ回数が少なくても、あまりに haystack や needle 文字列の長さが長い場合、正規表現とか、Knuth-Morris-Prattアルゴリズムを使うとよい
  • Haystack が長くても、サーチが haystack の頭の方で必ず成功するなどの性質があるなら、 strstr で当然十分。

要は TPO によるわけ。正規表現を使うにしても、Str を使うか、それとも外部ライブラリの pcre-ocaml を使うか、選択肢は残る。まあ、今時分、pcre の方がメジャーなので、そっちを使う方がいいでしょうけど。

OCaml 標準ライブラリは、非常に大雑把に言うと、これしかアルゴリズムないよ！という単純な物だけサポートするというポリシーっぽい。例えば上の strstr 方式の関数を入れちゃったりすると、これで超非効率なサーチを知らず知らずのうちにされるよりは、プログラマにちゃんと考えてもらって、状況に合った関数を使ってほしい、という思想があると思う、というか、思いたい。

でも、やっぱり strstr がないのは変だよね。だから書いておく。まあ、誰が書いてもこんな感じでしょう。というか、自分で書いてみると勉強になるよ:

(* very naive brute force algorith *)
let strstr ~haystack ~needle =
  assert (needle <> "");
  let hlen = String.length haystack in
  let nlen = String.length needle in
  (* [has_prefix hpos npos] checks 
     haystack.[hpos-npos+i] = needle.[i] for 0 <= i <= npos 
  *)
  let rec has_prefix hpos npos =
    if haystack.[hpos] <> needle.[npos] then false
    else if npos = 0 then true
    else has_prefix (hpos - 1) (npos - 1)
  in
  let npos_init = nlen - 1 in
  let hlen_nlen = hlen - nlen in
  (* check from 0 to hlen - nlen *)
  let rec loop hstart =
    if hstart > hlen_nlen then None
    else 
      if has_prefix (hstart + npos_init) npos_init then Some hstart
      else loop (hstart + 1)
  in
  loop 0

ああ、そうだ、文字列から文字を取り出すのは、わかりやすさのために、s.[i] としたけど、この関数では不正な文字列アクセスは行わないので、代わりに String.unsafe_get s i を使ったり、-unsafe オプションでコンパイルすると安全かつ早くなるよ、というかするべきです。(もすこし最適化出来そうな所もあるが、ベンチ取ってみないと判らないくらい細かいだろうから略。)

ちなみに ocaml-list でも 8年前に同じ議論はされている。