データ圧縮技術による文字列照合処理の高速化に関する研究

Presentation on theme: "データ圧縮技術による文字列照合処理の高速化に関する研究"— Presentation transcript:

1 データ圧縮技術による文字列照合処理の高速化に関する研究
九州大学附属図書館研究開発室

2 Knuth-Morris-Pratt (1974)
文字列照合問題 パタン matching テキスト Pattern matching is one of the most fundamental operations in string processing. Recently, a new trend for accelerating pattern matching has emerged: Speeding up pattern matching by text compression. From the traditional criteria for data compression, i.e., compression ratio and compression/decompression time, adaptive dictionary methods such as the Lempel-Ziv family are often preferred. However, such methods cannot speed up the pattern matching since an extra work is needed to keep track of compression mechanism. Knuth-Morris-Pratt (1974) Boyer-Moore (1977) Aho-Corasick (1975) Shift-Or (1992)

3 文字列照合を用いた検索システム RDBほか 文字列照合を基にした独自の方式 索引構造作成エンジン 索引 項目検索用 エンジン 検索プログラム
テキストデータ 項目検索用DB 索引 全文検索用 エンジン 全文検索用DB 文字列照合を基にした独自の方式 検索プログラム テキストデータ 全文検索用 項目検索用 エンジン 全文検索用DB

4 本研究の目的 復号 文字列照合 アルゴリズム 転送 文字列照合 アルゴリズム 転送 転送 圧縮文字列照合 アルゴリズム テキスト データ
二次記憶装置上 テキスト データ 文字列照合 アルゴリズム 転送 メモリ上 二次記憶装置上 圧縮テキスト メモリ上 文字列照合 アルゴリズム 復号 転送 メモリ上 二次記憶装置上 圧縮テキスト 転送 メモリ上 圧縮文字列照合 アルゴリズム

5 BPE圧縮法 困難さと解決策 BM型文字列照合 そのまま 圧縮テキストを 高速に照合
Boyer-Moore type PM algorithm Byte Pair Encoding BPE圧縮法 圧縮テキストを そのまま 高速に照合

6 実験結果 （非圧縮テキスト上のアルゴリズムとの対比）
0.0 0.3 0.4 0.5 0.8 0.1 0.2 0.6 0.7 AlphaStation XP1000 (Alpha21264: 667MHz) Tru64 UNIX V4.0F Medline（英文テキスト） 60.3Mbyte CPU時間（秒） 我々の手法 非圧縮テキストをKMPで照合 非圧縮テキストをAgrepで照合 5 10 15 20 25 30 パタンの長さ

7 近似文字列照合問題（あいまい検索） MARRIAGE MASS AGE 削除 置換 MARRIAGE MASSAGE CARRIAGE

8 圧縮テキスト上の近似文字列照合技術 そのまま フィルタリング手法 復号 圧縮テキスト上での 複数パタン文字列照合技術 圧縮テキストを
主記憶装置上 二次記憶装置上 圧縮テキスト 近似文字列照合 アルゴリズム 復号 転送 主記憶装置上 Multiple-pattern matching on compressed texts 圧縮テキスト上での 複数パタン文字列照合技術 フィルタリング手法 Filtration technique 圧縮テキストを そのまま 高速に近似文字列照合

9 LZW圧縮法における実験結果 7 6 5 4 CPU時間（秒） 3 2 1 1 2 3 4 5 許容される最大の編集距離 k
Intel Pentium III 550MHz (RAM: 64Mb; Linux) Wall Street Journal の記事（英文テキスト）10Mbyte パタンの長さ＝10 6 5 4 復号後にフィルタリング手法で照合 CPU時間（秒） 復号後に[Myers98]で照合 3 圧縮テキストにフィルタリング/AC 2 圧縮テキストにフィルタリング/BM 圧縮テキストにフィルタリング/BP 1 1 2 3 4 5 許容される最大の編集距離 k