文字列探索アルゴリズム談義
-
- いいね！1
Ryoma Sin'ya
@sinya8282
電通大の大山先生の講義で 「BVMD(BitVisorの拡張[VMM])ではI/OをClamAVのシグネチャを元にAho-Corasick 法でマッチングしてマルウェアを検出してます.」と聞いた. http://t.co/hsfm11xg
2012-01-12 01:11:54
Ryoma Sin'ya
@sinya8282
「Aho-Corasickは文字列スキップしない探索アルゴリズム. 複数文字列探索でもスキップを行うCommentz-Walter法やWu-Manber法の方が高速ですよー」と教えたら知らなかったらしく喜んでた.
2012-01-12 01:15:53
Ryoma Sin'ya
@sinya8282
複数文字列探索はなぜかAho-Corasickだけ有名ですよね. trieを作るということだけど, 正規表現の部分クラス(先頭の.*?以外Kleene閉包なし)に対応するオートマトンの構成方法だよね?
2012-01-12 01:19:00
Ryoma Sin'ya
@sinya8282
Uratani-Takeda法ってどんなアルゴリズムだったか... (複数)文字列探索アルゴリズムって,亜種がとても多くて面白い. 40種類ぐらい紹介してる資料もあるし.
2012-01-12 01:27:03
Tohirohi SASSA
@SassaHero
@sinya8282 喜田先生に聞いたところ，Uratani-Takeda法はほとんど実装されていないらしく，特に純粋なアルゴリズムのオープンな実装は見たことがないとのことでした．某企業のエンジンでアルゴリズムのアイディアを用いた実装が動いている様です．
2012-01-12 01:36:20
Ryoma Sin'ya
@sinya8282
@SassaHero 僕の読んでた資料(喜田先生の情報検索とパターン照合)ではWu-Manberがこのあたりのアルゴリズムでが高速だよーと紹介されていました. ちなみに GNU grep とかでは Commentz-Walter法使われてます.
2012-01-12 01:28:38
Ryoma Sin'ya
@sinya8282
Boyer-Moore法はスキップ以外にも「お尻から頭に向けてマッチングするんだぜ!」っていうのが衝撃的なアルゴリムなんだけど, 実はおしりから探索する必要はないでござる. ってのが Quick-Search法. これが最も高速っぽい. http://t.co/qBRHhGkv
2012-01-12 01:36:22
Ryoma Sin'ya
@sinya8282
Boyer-Moore 法は1977年発表とわりと最近. お尻から見る必要なかったんや！っていうQuick-Searchが発表されたのが1990年. このへん面白い. 「検索の歴史 一文字進化するのに掛かった年数は、なんと… 」 - http://t.co/WJXiUGQK
2012-01-12 01:38:29
Ryoma Sin'ya
@sinya8282
まぁバツグンにQuick-Searchの方がシンプルだし高速なので固定文字列探索はQuick-Search一択な感じ.
2012-01-12 01:39:31
Ryoma Sin'ya
@sinya8282
@SassaHero 実装の世界ではせいぜいが Aho-Corasick ですよね. 正直スキップを行うアルゴリズムであれば速度の差は劇的ではないだろうと思いますが, もっと知られるべき探索アルゴリズムって多いですよね.
2012-01-12 01:42:36
Ryoma Sin'ya
@sinya8282
ちなみに僕はKMP法を理解してません(爆) なんか「ひたすら複雑なくせにBMより遅いんだろ?」という先入観があり無視してきてた.
2012-01-12 01:46:51
Ryoma Sin'ya
@sinya8282
BM法もテーブルを2つ使うのと, 1つのみの方法(こっちがBMH法だっけ)あるけど後者が分かりやすくて好きです.
2012-01-12 01:47:41
K.Takata
@k_takata
@sinya8282 テーブル1つは簡易BMとか言ったような気が。BMHは不一致の場合の移動量の求め方が違います。 http://t.co/1XRF1nhc
2012-01-12 02:01:11
Ryoma Sin'ya
@sinya8282
@k_takata ふむふむ, 簡易BMみたいな言い方でしたか. BMHもテーブルは一つでしたよね? 移動量の算出が若干ちがうのか.
2012-01-12 02:04:28
K.Takata
@k_takata
@sinya8282 あちこちのサイトを見ても、BM→簡易BM→BMHという流れで説明されていて、テーブルは1つのようですが、元々の論文がそうだったのかは調べていません。
2012-01-12 02:13:46
Ryoma Sin'ya
@sinya8282
Sorting は情報系学部ではわりとがっつり叩き込まれると思うけど(それでも大抵QuickSort止まりかな), String Search はそうでもない感じ. 嘆かわしい!! (何様)
2012-01-12 01:52:25
Ryoma Sin'ya
@sinya8282
@daimatz 琉大ではそんな感じでしたが, 東工大もですか. Sort はどのへんまでやりました? (学部必修で)
2012-01-12 01:55:37
Daisuke Matsumoto
@daimatz
@sinya8282 情報工学科のカリキュラムだと、いわゆるアルゴリズムの授業はグラフ理論の一部として出てくるような感じでソートはCのプログラミングの授業で扱う程度でしたね。それでクイックソート、マージソートまでだったような。
2012-01-12 02:00:25
Ryoma Sin'ya
@sinya8282
@daimatz ふむふむ, ソートはプログラミングの方向からですか. たしかに再帰(分割統治)の良い例題ですからね.
2012-01-12 02:02:31
Daisuke Matsumoto
@daimatz
@sinya8282 http://t.co/a9ra38oD と http://t.co/qLiykjJc が学部2年前期で https://t.co/tSBefcGS が学部3年前期でした。他に学部1年後期に全学科目として http://t.co/Znni5rCN があります
2012-01-12 02:07:50
Daisuke Matsumoto
@daimatz
@sinya8282 て、そういえばCS入門のTAやってるんですがその授業ではちらっと文字列もやってました。ただこれは先生ごとの好みが大きくて僕が学部1年のときはやってなかったような。
2012-01-12 02:10:29
Ryoma Sin'ya
@sinya8282
@daimatz 1年次から首藤先生にプログラミング教えてもらえるなんて…(嫉妬しちゃう><) Pythonなのかー. というかグラフの講義は充実してますね… これは僕受けるべきだ...
2012-01-12 02:13:07