文法圧縮入門：超高速テキスト処理のためのデータ圧縮（NLP2014チュートリアル）
言語処理学会第２０回年次大会（2014/3）のチュートリアル講義資料です。 - 要旨 - 文法圧縮とは，入力テキストをよりコンパクトな文脈自由文法（CFG）に変換する圧縮法の総称である． 文法圧縮の強みは圧縮テキストを展開すること無く，検索等のテキスト処理を効率よく行える点にある． 驚くべきことにその処理速度は，元テキスト上での同じ処理を理論的に，時には実際にも凌駕する． また近年，ウェブアーカイブやログ，ゲノム配列等の大規模実データを高効率に圧縮できることで注目を集めている． しかしながら，文法圧縮についての初学者向けの解説資料はまだまだ少ない． そこで本チュートリアルでは，文法圧縮の歴史的背景から最新動向までを幅広く紹介する． 具体的には文法変換アルゴリズム，圧縮テキスト上での文字列パターン検索，文法圧縮に基づく省メモリデータ構造等の解説を行う．Read less
「高速文字列解析の世界」を読む前に知っておくと良いこと - EchizenBlog-Zwei
「高速文字列解析の世界」という大変すばらしい本が発売された。わりと敷居が高い本ではあるので読む前に知っておくとよさそうなことを書いておく。 「高速文字列解析」とは 本書でいう高速文字列解析というのは主に2つのことを指している。ひとつはデータを圧縮して小さくしてディスクよりメモリ、メモリよりキャッシュというようにより高速な記憶装置で扱いましょう、という話。もうひとつはデータ構造を工夫することで複雑な操作もそこそこ高速に扱えますよ、という話。つまり「圧縮」の話と「効率的なデータ構造」の話があると考えておくと良い。 キーワードは3つ オビにも書いてあるけれど、本書が主に扱うのは「BWT」「簡潔データ構造」「ウェーブレット木」の3つ。具体的には「BWT」が「圧縮」に関わっていて「ウェーブレット木」が「効率的なデータ構造」に関わっている。「簡潔データ構造」は基本的な道具として本書の色々なところで出て
1
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
処理を実行中です
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
