Context-Sensitive Grammar Transform: Compression and Pattern Matching
スポンサーリンク
概要
- 論文の詳細を見る
A framework of context-sensitive grammar transform for speeding-up compressed pattern matching (CPM) is proposed. A greedy compression algorithm with the transform model is presented as well as a Knuth-Morris-Pratt (KMP)-type compressed pattern matching algorithm. The compression ratio is a match for gzip and Re-Pair, and the search speed of our CPM algorithm is almost twice faster than the KMP-type CPM algorithm on Byte-Pair-Encoding by Shibata et al.[18], and in the case of short patterns, faster than the Boyer-Moore-Horspool algorithm with the stopper encoding by Rautio et al.[14], which is regarded as one of the best combinations that allows a practically fast search.
著者
-
MARUYAMA Shirou
Graduate School of Information Science and Electrical Engineering, Kyushu University
-
TANAKA Youhei
Graduate School of Computer Science and Systems Engineering, Kyushu Institute of Technology
-
SAKAMOTO Hiroshi
Graduate School of Computer Science and Systems Engineering, Kyushu Institute of Technology
-
TAKEDA Masayuki
Graduate School of Information Science and Electrical Engineering, Kyushu University
関連論文
- Context-Sensitive Grammar Transform: Compression and Pattern Matching
- 1P-115 ヘムオキシゲナーゼ-1・シトクロムP450還元酵素複合体結合様式の解明(ヘム蛋白質,第46回日本生物物理学会年会)
- Context-Sensitive Grammar Transform : Compression and Pattern Matching
- Interaction between Heme and Synthetic Peptides Containing Heme Regulatory Motifs of Rat Heme Oxygenase-2
- Purification and Characterization of Human Uroporphyrinogen III Synthase Expressed in Escherichia coli
- Functional Analysis of Heme Reguratory Motifs of Rat Heme Oxygenase-2
- 3P021 擬似原子モデル構築のためのGUIを持った支援ツールの開発(蛋白質-構造,第48回日本生物物理学会年会)
- Sensitive heme sensor using fluorescent-labeled heme oxygenase-1
- 1I1512 電子顕微鏡画像に基づいた拘束付き分子動力学法 : シトクロムP450還元酵素・ヘムオキシゲナーゼ-1複合体の原子モデル構築(ヘム蛋白質 1,第49回日本生物物理学会年会)
- Role of Proline in Heme Regulatory Motifs of Heme Oxygenase-2