文字列探索スターターキット

最近重点的に勉強しているので，これまで集めた教科書情報，資料等へのリンクをまとめてみる．紹介している教科書はほとんど読んでいないので妄言注意．
この他にお薦め教科書，勉強法があればぜひ教えてください．

文字列探索は検索対象テキストの中から転置インデクスのような外部データ構造を利用せずに目的の文字列を探索する課題です．文字列探索，文字列照合，パターンマッチなどとも呼ばれています（一番オーソドックスな呼び方はなんでしょう？）

教科書

和書で文字列探索だけを取り扱っている本を見かけたことがない．アルゴリズム本の探索の章にKMP法，BM法が紹介されているだけのケースが多い．注意してみるとAC法を扱っている本が意外と少ないことに気がつく．．．

（文字列探索でよい和書の情報募集中）

• 追記 (2009-04-02) Thanks to cubicdaiyaさん!
  • 情報検索アルゴリズムにKMP法, BM法, AC法の解説有
  • Cで学ぶデータ構造とアルゴリズムにKMP法, BM法, AC法の解説有

Flexible Pattern Matching in Strings (2002)

Flexible Pattern Matching Strings: Practical On-Line Search Algorithms for Texts and Biological Sequences

• 黄色本．文字列探索では定番の教科書らしい．IR四天王ことNavarro著．あっさりとした解説なので，初めて読むのに丁度よい．
• 文字列探索では，文字種（アルファベットの種類数）Σと探索したいパターン長によって有効手法が異なってくる．本書の各章末に有効手法の適用範囲の図があるのが有難い．

Algorithms on Strings (2007)

Algorithms on Strings

• この分野では一番新しい（と思われる）教科書的文献．さらっと眺めた感じでは，やや堅い印象．網羅的．

Algorithms on Strings, Trees and Sequences (1997)

Algorithms on Strings, Trees and Sequences: Computer Science and Computational Biology

• ガスフィールド本．超有名（らしい）．やや古いのが難点．

Jewels of Stringology (2002)

Jewels of Stringology

• こちらも有名（らしい）．どこかで聞いた話によると現在絶版のText Algorithmsの焼き直しで，構成がかえってわかりづらくなっているとのこと．
• 追記 (2009-04-02) Thanks to usa9さん!
  • Text Algorithmは現在原稿がウェブ公開されています！ http://web.njit.edu/~rytter/TEACHING/TEXTS/book.html

資料等

• Pattern Matching Pointers
  • 文字列探索に関する神リンク集．学会や教科書，資料などの超網羅的なリンク

• EXACT STRING MATCHING ALGORITHMS
  • 各種アルゴリズムの解説．Cサンプルコードと，Javaによるアルゴリズムの動作確認ができる．Javaのせいか，ブラウザが落ちる可能性があるので注意．

• 配列解析アルゴリズム特論I
  • 東大渋谷先生の講義資料．神．最初の講義資料にまとめ情報あり．

• 情報知識ネットワーク特論（平成１９年度）
  • 喜田先生による「パターン照合アルゴリズム」の資料が神ががっている．Navarroの黄色本の素晴らしい要約になっている．

• Algorithms with Python 文字列の探索 (string searching)
  • M.Hiroiさんのページ．Horspool algorithmとSunday algorithmが解説されている．

• 検索アルゴリズム(3)文字列の検索-1-
• 検索アルゴリズム(4)文字列の検索-2-
  • Fussyさんのページ．Naive法，KMP法，BM法を解説．最後に多バイト文字列に対する解説あり

Wikipediaにもかなり丁寧な解説がある．代表的なものば

• KMP法
• BM法
• AC法
• Rabin-Karp法

今は各種アルゴリズムをこつこつと把握中．最新の話題についていけるくらいにはなりたいです．

どうでもいい話ですが，AC法のAho-Corasickはエイホ・コラシックと訳されることが多いけれど，どちらかといえばエイホ・コレイシックが正しい発音なのではないでしょうか．
もしコラシックと書くのであれば，エイホもアホと訳すべきなのではないでしょうか:p
（正しい発音をご存知の方がいれば教えてください．）