圧縮テキストに対する文字列照合問題 竹田研究室 博士課程二年 喜田 拓也.

Slides:



Advertisements
Similar presentations
Determining Optical Flow. はじめに オプティカルフローとは画像内の明る さのパターンの動きの見かけの速さの 分布 オプティカルフローは物体の動きの よって変化するため、オプティカルフ ローより速度に関する情報を得ること ができる.
Advertisements

Collage System 圧縮テキストパターン照合のための統一的枠組み
文法変換に基づく圧縮 九州大学附属図書館 研究開発室 喜田拓也.
透過的データ圧縮 Transparent Data Compression
情報生命科学特別講義III (1) 文字列マッチング
Fill-in LevelつきIC分解による 前処理について
情報知識ネットワーク 有村・喜田研究室 ex. 7678, 7679
LZ圧縮回路の設計とハード・ソフト 最適分割の検討 電子情報デザイン学科 高性能計算研究室 4回生 中山 和也 2009/2/27.
ラベル付き区間グラフを列挙するBDDとその応用
全体ミーティング (4/25) 村田雅之.
Finger patternのブロック化による 陰的wavelet近似逆行列前処理の 高速化
基礎プログラミングおよび演習 第9回
アルゴリズムとデータ構造 2012年7月19日
分子生物情報学 動的計画法に基づく配列比較法 (ペアワイズアライメント法)
全文検索のためのデータ構造と 構成の効率について
AllReduce アルゴリズムによる QR 分解の精度について
アルゴリズムとデータ構造 第9回演習解答.
P,Q比が変更可能なScaLAPACKの コスト見積もり関数の開発
データ構造と アルゴリズム 第二回 知能情報学部 新田直也.
動的ハフマン符号化の例 入力:ABCDEからなる文字列 出力:動的に作ったハフマン木.
ランダムプロジェクションを用いた 音声特徴量変換
日本大学 文理学部 情報システム解析学科 谷研究室 益田真太郎
3次元剛体運動の理論と シミュレーション技法
IIR輪講復習 #5 Index compression
基礎情報科学のトピックス (平成15年度版) 喜田拓也 (
文字列照合アルゴリズム 情報知識ネットワーク特論 喜田拓也 参考文献:
アルゴリズムとデータ構造 2013年7月18日
A Unifying Framework for Compressed Pattern Matching
サーバ負荷分散におけるOpenFlowを用いた省電力法
篠原 歩,石野 明 東北大学情報科学研究科 竹田 正幸 九州大学システム情報科学研究院 下薗 真一,坂本 比呂志 九州工業大学情報工学部
データ構造とプログラミング技法 (第10回) ー文字列照合(KMP法、BM法)ー.
ネット時代の情報センス 基礎情報科学のトピックス.
情報検索技術のトピックス (平成16年度版) 喜田拓也 (
九州大学大学院システム情報科学研究科 情報理学専攻 竹田研究室 博士課程3年 喜田 拓也
Pattern Matching on Compressed Texts
生物情報ソフトウェア特論 (1) 文字列マッチング・データ構造
k 個のミスマッチを許した点集合マッチング・アルゴリズム
喜田 拓也,竹田 正幸,篠原 歩 九州大学大学院システム情報科学府 情報理学専攻
Fast Pattern Matching Algorithms in Compressed Texts
定兼邦彦 今井浩 東京大学理学系研究科 情報科学専攻
文字列照合を用いた XMLデータアクセス機構の提案
Proceedings of the Third South American Workshop on String Processing.
確率的学習アルゴリズムを用いた有限状態オートマトンの抽出に関する研究
データ構造とアルゴリズム 第14回 文字列の照合.
Jh NAHI 横田 理央 (東京工業大学) Hierarchical low-rank approximation methods on distributed memory and GPUs 背景  H行列、H2行列、HSS行列などの階層的低ランク近似法はO(N2)の要素を持つ密行列をO(N)の要素を持つ行列に圧縮することができる。圧縮された行列を用いることで、行列積、LU分解、固有値計算をO(NlogN)で行うことができるため、従来密行列の解法が用いられてきた分野では階層的低ランク近似法
確率的学習アルゴリズムを用いた有限状態オートマトンの抽出に関する研究
アルゴリズムとデータ構造 2011年7月12日
半構造化テキストに対する 文字列照合アルゴリズム
分子生物情報学(2) 配列のマルチプルアライメント法
テキスト検索は 文字列検索でも木検索でもない
A Dynamic Edit Distance Table
データ圧縮技術による文字列照合処理の高速化に関する研究
Nightmare at Test Time: Robust Learning by Feature Deletion
アルゴリズム論 (第12回) 佐々木研(情報システム構築学講座) 講師 山田敬三
長さの制限付きギャップと 文字クラスを含むパタンに対する 照合アルゴリズムの改善
Hoffman符号 2011/05/23.
2007年度 情報数理学.
生物情報ソフトウェア特論 (2)たたみ込みとハッシュに 基づくマッチング
Wavelet係数の局所テクスチャ特徴量を用いたGraph Cutsによる画像セグメンテーション
わかりやすいパターン認識 第7章:部分空間法  7.1 部分空間法の基本  7.2 CLAFIC法                  6月13日(金)                  大城 亜里沙.
短い部分文字列の ミスマッチトレランスを 高速計算するアルゴリズム
構造的類似性を持つ半構造化文書における頻度分析
Jh NAHI 横田 理央 (東京工業大学) Hierarchical low-rank approximation methods on distributed memory and GPUs 背景  H行列、H2行列、HSS行列などの階層的低ランク近似法はO(N2)の要素を持つ密行列をO(N)の要素を持つ行列に圧縮することができる。圧縮された行列を用いることで、行列積、LU分解、固有値計算をO(Nlog2N)で行うことができるため、従来密行列の解法が用いられてきた分野では階層的低ランク近似
LZW 圧縮テキストに対する 高速文字列照合アルゴリズム 喜田 拓也 竹田 正幸 篠原 歩 九州大学大学院システム情報科学研究科
PROGRAMMING IN HASKELL
テキストデータベース.
情報論理工学 研究室 第1回:並列とは.
情報生命科学特別講義III (3)たたみ込みとハッシュに 基づくマッチング
データ構造とアルゴリズム 第14回 文字列の照合.
8.文字列処理 8.1 C#の文字列 C#では, “ABCD”のように文字列を2重引用符で挟んで指定します。ASCIIコード体系のとき,以下のような内部形式となります。 1 1 文字 ‘A’ ナル文字 1 1 文字 ‘B’ A B C D \ 文字 ‘C’ 1 1 文字 ‘D’ ナル文字‘\0’
Presentation transcript:

圧縮テキストに対する文字列照合問題 竹田研究室 博士課程二年 喜田 拓也

発表内容 圧縮テキスト上の文字列照合問題 本研究分野の歩み 近似文字列照合アルゴリズム まとめ 発表内容

文字列照合問題 hanage 日本経済新聞 11月16日 朝刊(ジュネーブ発 西山 章宏) 日本経済新聞 11月16日 朝刊(ジュネーブ発 西山 章宏) スイスの保養地、ダヴォス・プラッツで11月10日から11月14まで、行われた、世界知覚認識学会(ミシェル・ポーター会長)で、北海道大学医学部の斉藤信(まこと)教授が提唱した、痛みを表す「hanage」と言う単位を、世界で共通の単位とする事が承認された。本来、痛みは、個人差が大きく、同じ刺激でも主観によって感じ方が異なるため、客観的に数値で表すことは、不可能であると思われていた。しかし、斉藤教授は、「鼻の粘膜は、人体の中で一番個人差が小さい。」事に注目し研究を進めた結果、1センチの鼻毛を、1N(ニュートン)の力で、引っ張る時に生じる痛みを、1hanageと定義出来ることを発見し、そして今学会で単位として承認された。 文字列照合問題

文字列照合問題 データ圧縮 ... O(テキストの長さ) 既存の手法 限界 !? 索引構造 Knuth-Morris-Pratt (1974) Boyer-Moore (1977) Karp-Rabin (1987) Bit-parallelism (1987) 既存の手法 O(テキストの長さ) 限界 !? データ圧縮 数多くのアルゴリズムが提唱されている. 細かい改良も数多くなされたが,照合スピードは頭打ちになっている. この分野での進展はもうない. 索引構造 Suffix array Inverted file 文字列照合問題

圧縮テキスト上の文字列照合問題 原テキスト テキスト パターン 展開 圧縮 非圧縮 圧縮テキスト 圧縮テキスト 普通の 文字列照合機械 圧縮テキストに対する 文字列照合機械 圧縮テキスト 圧縮 テキスト 非圧縮 パターン 圧縮テキスト上の文字列照合問題

圧縮テキスト上の文字列照合問題とは 本研究分野の歩み 圧縮テキスト上の近似文字列照合問題 まとめ 圧縮テキスト上の文字列照合問題とは 本研究分野の歩み 圧縮テキスト上の近似文字列照合問題 まとめ

Eliam-Tsoreff and Vishkin run-length 1992 Amir, Landau, and Vishkin 年 研究者 圧縮法 1988 Eliam-Tsoreff and Vishkin run-length 1992 Amir, Landau, and Vishkin two-dimensional run-length 1992 Amir and Benson two-dimensional run-length Amir, Benson, and Farach 1994 two-dimensional run-length 1994 Manber original compression scheme 1995 Farach and Thorup LZ77 1996 Gasieniec, et al. LZ77 1996 Amir, Benson and Farach LZW 1997 Karpinski, Rytter, and Shinohara straight-line programs 1997 Miyazaki, Shinohara, and Takeda straight-line programs 1997 Takeda finite state encoding 1998 Fukamachi, Shinohara, and Takeda Huffman encoding 1998 Kida, et al. LZW これまでの研究1

Dictionary based methods 年 研究者 圧縮法 1998 Kida, et al. LZW 1998 de Moura, et al. Word based encoding 1999 Kida, et al. LZW 1999 Navarro and Raffinot LZ family 1999 Shibata, et al. Antidictionaries Kida, et al. 1999 Dictionary based methods (Collage system) 1999 Shibata, et al. Byte pair encoding 2000 Shibata, et al. Collage system これまでの研究2

Amirらのアイデア 3 4 5 1 2 3 4 3 4 5 1 abababba a b a b a b b パターン 7 1 2 4 5 : goto 関数 : failure 関数 Knuth-Morris-Pratt(KMP) automaton a 1 2 4 5 b 3 -1 3 4 5 1 2 3 4 3 4 5 1 状態 テキスト abababba 圧縮テキスト X1 X2 X3 X4 Amirらのアイデア

我々の改良 Amir et al. 我々[DCC’98] KMP照合機械 Aho-Corasick照合機械 単一のパターンのみ もっと速くしたいなぁ… Amir et al. 我々[DCC’98] KMP照合機械 Aho-Corasick照合機械 単一のパターンのみ 複数パターンに対応 最初の出現のみ報告 すべての出現位置を報告 O(n + m2)時間領域 O(n log m + m )時間 O(n+m)領域 O(n + m2)時間領域 実験結果なし 実装&実験済み 我々の改良[DCC’98]

Bit-parallelism ababb a b a b b b a a abababba a b パターン 1 2 4 5 3 1 2  a 1 2 4 5 b 3 a b a b b b a a abababba テキスト 1 2 3 4 5 1 Bit-parallelism

Ri = (Ri-1<<1 | 1) & M(T[i]) Bit-parallelism ababb マスクビット列M ab 1 a b パターン abababba テキスト 1 2 3 4 5 1 & Ri = (Ri-1<<1 | 1) & M(T[i]) Shift-And法の計算式

拡張のアイデア ababb abababba ab 1 1 a b パターン テキスト 2 3 4 5 Jump! Jump! a b パターン abababba テキスト 1 2 3 4 5 Jump! Jump! 圧縮テキスト上のShift-And法

実験結果 (CPU時間) Time (sec) Pattern length uncompress+AC 0.2 0.4 0.6 0.8 0.2 0.4 0.6 0.8 1.0 1.2 1.4 5 10 15 20 25 30 Pattern length Time (sec) uncompress+agrep gunzip+AC gunzip+agrep uncomAC gunzipAC AC on LZW Bit-parallel on LZW AlphaStation XP1000 (Alpha21264: 667MH) Tru64 UNIX V4.0F Genbank(DNA sequence) 17.1Mbyte 実験結果

Medline(348,566 references) 60.3Mbyte 実験結果 (実時間) Medline(348,566 references) 60.3Mbyte method Local Remote 原テキストに agrep 2.39 9.03 uncomAC 4.10 6.93 gunzipAC 3.38 6.49 AC on LZW 3.29 5.51 Bit-parallel on LZW 3.01 5.49 データ転送速度 24.9Mbyte/sec データ転送速度 6.57Mbyte/sec Local Remote 実験結果

Dictionary based methods 年 研究者 圧縮法 1998 Kida, et al. LZW 1998 de Moura, et al. Word based encoding 1999 Kida, et al. LZW 1999 Navarro and Raffinot LZ family ショック! ショック! 1999 Shibata, et al. Antidictionaries Kida, et al. 1999 Dictionary based methods (Collage system) 1999 Shibata, et al. Byte pair encoding 2000 Shibata, et al. Collage system これまでの研究3

反撃のSPIRE’99 統一的枠組み 統一的枠組みに対する 照合アルゴリズム 従来 T. Kida, M. Takeda, A. Shinohara, Y. Shibata, and S. Arikawa. A Unifying Framework for Compressed Pattern Matching. In 6th International Symposium on String Processing and Information Retrieval, pp.89-96. IEEE Computer Society, 1999. 統一的枠組みに対する 照合アルゴリズム 圧縮方法C 圧縮方法B 圧縮方法A 統一的枠組み 従来 照合アルゴリズムC 圧縮方法C 照合アルゴリズムB 圧縮方法B 照合アルゴリズムA 圧縮方法A Collage systemによる統一

(一文字代入,連結,繰り返し,切り落とし) Collage system 直線的プログラム+αの表現力 (一文字代入,連結,繰り返し,切り落とし) 圧縮テキストを抽象的に表現 (辞書部分と符号化列を分離: 〈D, S 〉) 辞書式圧縮法を統一的に扱える 一文字代入,連結,繰り返し,切り落とし 辞書部分と符号化列を分離: 〈D, S 〉 S X3 , X6 , X4 , X7 X1 = a ; X2 = b ; X7 = X6・X4 ; X6 = [ 3 ]X5 ; X5 = ( X3 )3 ; X4 = X2・X1 ; X3 = X1・X2 ; D S ここで、 X3 からX7 まではそれぞれ、このような文字列に対応しています。 すなわちこのS は下の文字列を表現していることになります。 これが原テキストで、S が圧縮テキストです。 abbabbababba Collage system

O( (||D||+|S|) ・height(D) + m2 + r ) 時間 Collage systemから得られた知見 O( (||D||+|S|) ・height(D) + m2 + r ) 時間 O( ||D|| + |S| + m2 + r ) 時間 LZ77 LZSS LZ78 Run length 切り取り操作がある BPE Huffman LZW 切り取り操作がない O( ||D|| + m2 ) 領域 Collage systemによる知見

Dictionary based methods 年 研究者 圧縮法 ほんと、速いよ。 1998 Kida, et al. LZW 1998 de Moura, et al. Word based encoding 1999 Kida, et al. LZW 1999 Navarro and Raffinot LZ family 1999 Shibata, et al. Antidictionaries Kida, et al. 1999 Dictionary based methods (Collage system) 1999 Shibata, et al. Byte pair encoding BMタイプ! 2000 Shibata, et al. Collage system これまでの研究4(柴田登場)

BPE圧縮法 ABABCDEBDEFABDEABC AB G GGCDEBDEFGDEGC DE H GGCHBHFGHGC GC I ペア表 A B C D E F G H I Code Pair AB DE GC テキスト ABABCDEBDEFABDEABC G AB GGCDEBDEFGDEGC H DE GGCHBHFGHGC I GC GIHBHFGHI BPE圧縮法

実験結果 Time (sec) Pattern length 0.00 0.05 0.10 0.15 0.20 0.25 5 10 15 30 Pattern length Time (sec) AlphaStation XP1000 (Alpha21264: 667MH) Tru64 UNIX V4.0F Genbank(DNA sequence) 17.1Mbyte KMP Agrep Bit-parallel on BPE BM on BPE 実験結果

目標の変遷 理論的興味のみ 照合を高速化する圧縮法の開発 展開時間 + 照合時間 < 原テキストの照合時間 照合時間 < 照合時間 < 原テキストの照合時間 照合を高速化する圧縮法の開発 目標の変遷

圧縮テキスト上の文字列照合問題とは 本研究分野の歩み 圧縮テキスト上の近似文字列照合問題 まとめ 圧縮テキスト上の文字列照合問題とは 本研究分野の歩み 圧縮テキスト上の近似文字列照合問題 まとめ

近似文字列照合 CARRIAGE MARRIAGE MASSAGE 近似文字列照合問題

編集距離(レヴェンシュタイン距離) 1 3 文字列 x[1...n] を文字列 y[1...n] へ変換する ために要する最小コスト d 置換 = 削除 = 挿入 = 1 各操作のコスト CARRIAGE 1 MARRIAGE k = 2 MASSAGE 3 編集距離

非決定性オートマトンによる解法 POKEMON PIKACHU パターン 1 2 3 テキスト エラー数     N P O K E   N P O K E M   N P O K E M   N P O K E M   1 2 3 PIKACHU テキスト 非決定オートマトンによる解法

R. Baeza-Yates and G. Navarro Bit-parallelismの利用 R. Baeza-Yates and G. Navarro N P O K E M   1111 0011 0111 0000 0000 状態 S (mk+1)(k+1) サイズ Bit-parallelismの適用

基本的アイデア Jump(S, “PIK”) Output(S, “PIK”) P I     N P O K E M  N P

Jump (S, w) ∪ l d (i, j) , ( w S Jump ) = M(w;l, d). Ç ) ( l, d S Å ) , | min(| max( k d m w £ + - l 平行移動 O( k2 ) l 前処理で OK! d (i, j) Jumpのアイデア

Output (S, w)  Xi OMANZAIOMOROI •••PAPEPON POK EMON d=1 d=2 POKEMON テキスト OMANZAIOMOROI •••PAPEPON POK EMON パターン d=1 d=2 POKEMON NOMEKOP Outputのアイデア

O( k2(||D||+|S| )+km )) 時間 理論的結果 T. Matsumoto, T. Kida, M. Takeda, A. Shinohara, and S. Arikawa. Bit-parallel approach to approximate string matching in compressed texts. In 6th International Symposium on String Processing and Information Retrieval. Simple Collage system LZ78, LZW O( k2(||D||+|S| )+km )) 時間 O( k2||D|| ) 領域 O(k2n+km)) 時間 O(k2n) 領域 ||D|| : 辞書の大きさ, m : パターン長 |S| : 符号列の長さ, k : エラーの上限 n : 圧縮テキスト長 J. Karkkainen, G. Navarro, and E. Ukkonen. Approximate string matching over Ziv-Lempel compressed text. In Proc.11th Ann. Symp. on Combinatorial Pattern Matching. J. Karkkainen, et al. O(mkn) 時間領域 動的計画法が土台 理論的結果

Genbank(DNA sequence) 実験結果(CPU時間) m (k =1) 8 12 16 20 24 28 32 uncompress+DP 2.572 3.638 4.578 5.513 6.504 7.466 8.375 Bit-parallel on LZW 5.364 6.233 6.475 6.633 6.829 7.021 7.269 k (m =14) 1 2 3 4 5 uncompress+DP 4.108 4.110 4.101 4.102 4.098 Bit-parallel on LZW 6.327 12.91 21.51 31.50 43.03 AlphaStation XP1000 (Alpha21264: 667MH) Tru64 UNIX V4.0F Genbank(DNA sequence) 17.1Mbyte compression ratio 26.8% 実験結果

圧縮テキスト上の文字列照合問題とは 本研究分野の歩み 圧縮テキスト上の近似文字列照合問題 まとめ 圧縮テキスト上の文字列照合問題とは 本研究分野の歩み 圧縮テキスト上の近似文字列照合問題 まとめ

まとめ 圧縮テキスト上の文字列照合は実用的な技術である. Collage systemは本研究のための強力な道具である. 辞書式圧縮法の抽象的な枠組みによる統一的手法. BPE圧縮法は,圧縮テキスト上の文字列照合に非常に適した圧縮法である. サイズ固定の静的辞書,固定長符号,単純なアルゴリズム. 文字列照合を高速化するためのデータ圧縮. 圧縮テキスト上の近似文字列照合アルゴリズムはまだ実用的でない. O( kn ) 時間? まとめ

Bit-parallelismでのOutput (S, w)

じ も く 3 文字列照合問題 5 圧縮テキスト上の文字列照合問題 6 本研究分野の歩み 22 実験結果(CIAC&CPM2K) 7 これまでの研究1 23 目標の変遷 8 これまでの研究2 25 圧縮テキスト上の近似文字列照合問題 9 Amirらのアイデア(KMP) 26 編集距離 10 我々の改良[DCC’98] 27 非決定オートマトンによる解法 11 Bit-parallelism[CPM’99] 28 Bit-parallelismの適用 15 実験結果(DCC&CPM--ELT) 29 基本的アイデア 14 実験結果(DCC&CPM--CPU) 30 Jumpのアイデア 17 Collage systemによる統一 31 Outputのアイデア 32 理論的結果 21 BPE圧縮法 33 実験結果 もくじ