睡眠不足?! RSSフィード

2227440

2009-03-29

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

最近重点的に勉強しているので,これまで集めた教科書情報,資料等へのリンクをまとめてみる.紹介している教科書はほとんど読んでいないので妄言注意.

この他にお薦め教科書,勉強法があればぜひ教えてください.


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


教科書

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

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

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

Algorithms on Strings (2007)
Algorithms on Strings

Algorithms on Strings

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

Algorithms on Strings, Trees and Sequences (1997)
  • ガスフィールド本.超有名(らしい).やや古いのが難点.

Jewels of Stringology (2002)
Jewels of Stringology

Jewels of Stringology


資料等



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



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


どうでもいい話ですが,AC法のAho-Corasickはエイホ・コラシックと訳されることが多いけれど,どちらかといえばエイホ・コレイシックが正しい発音なのではないでしょうか.

もしコラシックと書くのであれば,エイホもアホと訳すべきなのではないでしょうか:p

(正しい発音をご存知の方がいれば教えてください.)

naoyanaoya 2009/03/29 09:18 弊社社内では「アホっ子らしく」と呼ばれています。「せめて、アホっ子らしく」

...失礼しました

sleepy_yoshisleepy_yoshi 2009/03/29 15:12 > naoyaさん
その発想はなかったですww
アホっ子,頂きますm(_ _)m

cubicdaiyacubicdaiya 2009/03/29 16:27 「情報検索アルゴリズム」だと、KMP法とBM法とAC法の3つを扱っています。
解説だけでなく、擬似コードも載っているので、わかりやすいと思います。

http://www.kyoritsu-pub.co.jp/texthp/joho/12036-1.html

usa9usa9 2009/03/30 13:25 Text Algorithmsは,PDFで読めるようになったらしいです.
> http://web.njit.edu/~rytter/TEACHING/TEXTS/book.html

usa9usa9 2009/03/30 13:28 上のText Algorithmsは,PSファイルでした.
個人的には,Algorithms on StringsがJewels of Stringologyと比べてどのくらいわかりやすくなってるのかが気になります.

sleepy_yoshisleepy_yoshi 2009/04/02 00:40 > cubicsaiyaさん
ご指摘ありがとうございます!
情報検索アルゴリズム,スルーしていました.
AC法扱っている貴重な?和書ですね.

その後本棚の本を眺めてたら

Cで学ぶデータ構造とアルゴリズム
http://www.amazon.co.jp/C%E3%81%A7%E5%AD%A6%E3%81%B6%E3%83%87%E3%83%BC%E3%82%BF%E6%A7%8B%E9%80%A0%E3%81%A8%E3%82%A2%E3%83%AB%E3%82%B4%E3%83%AA%E3%82%BA%E3%83%A0-%E8%A5%BF%E5%8E%9F-%E6%B8%85%E4%B8%80/dp/4274205002

にもAC法の解説を見つけました!

sleepy_yoshisleepy_yoshi 2009/04/02 00:44 > usa9さん
ありがとうございます!さっそくダウンロードしてps2pdfしました:)
まだ全然読んでないですが,Text Algorithm読みやすそうですね.
こつこつ読んでいきたいと思います.

スパム対策のためのダミーです。もし見えても何も入力しないでください
ゲスト


画像認証

トラックバック - http://d.hatena.ne.jp/sleepy_yoshi/20090329/p1