圧縮パターンマッチング

コンピュータ サイエンスにおいて、圧縮パターン マッチング( CPMと略される) とは、ほとんどまたはまったく解凍せずに圧縮データ内のパターンを検索するプロセスです。圧縮された文字列内の検索は、圧縮されていない文字列内の検索よりも高速で、必要なスペースも少なくなります。

圧縮ファイルが可変幅エンコーディングを使用している場合、問題が発生する可能性があります。たとえば、aのコードワードを「100」、 bのコードワードを「110100」とします。テキスト内でaの出現を探している場合、結果としてbのコードワード内にある出現も取得する可能性があります。このイベントを偽一致 と呼びます。したがって、検出された出現がコードワード境界に実際に沿っているかどうかを確認する必要があります。ただし、テキスト全体をデコードしてから従来の文字列マッチング アルゴリズム を適用することもできますが、これには通常、より多くのスペースと時間が必要になり、圧縮ファイルがオンラインでホストされている場合など、多くの場合は不可能です。圧縮パターン マッチング アルゴリズムによって返された一致が真の一致であるか偽の一致であるかを確認するこの問題と、テキスト全体をデコードできないことは、圧縮マッチング問題と呼ばれます。^[1]

コードワードの境界を見つけてテキストの完全な解凍を回避するための戦略は多数存在します。次に例を示します。

• 各コードワードの最初のビットのインデックスのリスト。バイナリ検索を適用できます。
• 差分コーディングによる各コードワードの最初のビットのインデックスのリスト。これにより、ファイル内のスペースを節約できます。
• ビットのマスク。ビット 1 は各コードワードの開始ビットを示します。
• 部分的かつ目的に沿った減圧のためにブロックに分割します。

文字列とパターンの長さの増加に伴って対数的に増加する実行時間を提供するアルゴリズムが導入された。^[2]

• Shmuel T. Klein と Dana Shapira HUFFMAN 符号化テキストのパターン マッチング (2003)
• Marek Karpinski、Wojciech Rytter、Ayumi Shinohara。短い説明を持つ文字列の効率的なパターンマッチングアルゴリズム。Nordic Journal of Computing 4(2): pp.172-168 (1997)。

• 「 ほぼ最適な完全LZW圧縮パターンマッチング」1999:316–325。CiteSeerX 10.1.1.44.5521。 {{cite journal}}:ジャーナルを引用するには|journal=(ヘルプ)が必要です
• 辞書ベースの圧縮パターンマッチングアルゴリズム(PDF) 、 2003 年 3 月 13 日のオリジナル(PDF)からアーカイブ
• 「圧縮パターンマッチングのための統一フレームワーク」1999:89–96. CiteSeerX  10.1.1.50.1745。 {{cite journal}}:ジャーナルを引用するには|journal=(ヘルプ)が必要です
• 「テキスト圧縮による文字列パターン マッチングの高速化: 新時代の幕開け」(PDF)。2007 年 8 月 8 日にオリジナル(PDF)からアーカイブ。2009年 3 月 22 日に取得。 {{cite journal}}:ジャーナルを引用するには|journal=(ヘルプ)が必要です
• 「LZW圧縮テキストにおけるパターンマッチングへのShift-andアプローチ」1999:1–13. CiteSeerX  10.1.1.15.4609。 {{cite journal}}:ジャーナルを引用するには|journal=(ヘルプ)が必要です
• 「LZW アルゴリズム」(PDF)。 {{cite journal}}:ジャーナルを引用するには|journal=(ヘルプ)が必要です