(57)【要約】【課題】  復元時の参照局所性を改善する。【解決手段】  本発明は、サンプル文字列長M（M＜＜N）の部分文字列長Sとし、入力文字列Nの開始位置から長さSの部分文字列を取得してサンプル文字列記憶手段に格納し、入力文字列Nの開始位置ｉから始まる部分文字列と、サンプル文字列記憶手段から読み出したサンプル文字列Mの最大一致長LMと該部分文字列の出現位置PMと、入力文字列Nの開始位置ｉ番目から始まる部分文字列とし、該入力文字列Nの０番目からｉ−1番目までに出現した部分文字列との最大一致長LNと、該出現した部分文字列の出現位置を求め、LM<LNである場合は、置換ポインタを該入力文字列Nの過去の位置を示すものとし、LM≧LN以上である場合は該置換ポインタをサンプル文字列M上の位置を示すものとし、該入力文字列Nの[i…i+L+1]の部分文字列を出現済みの部分文字列として動的辞書記憶手段に格納し、置換ポインタ列と該サンプル文字列を出力する。【選択図】  図３
2014204356.tif 000002
【特許請求の範囲】
【請求項１】
置換方式による文字列圧縮装置であって、
サンプル文字列長M（M＜＜N）の部分文字列長Sとし、入力文字列Nの開始位置から長さSの部分文字列を取得してサンプル文字列記憶手段に格納するサンプル文字列生成手段と、
前記入力文字列Nの開始位置ｉから始まる部分文字列と、前記サンプル文字列記憶手段から読み出した前記サンプル文字列Mの最大一致長LMと該部分文字列の出現位置PMと、前記入力文字列Nの開始位置ｉ番目から始まる部分文字列とし、該入力文字列Nの０番目からｉ−1番目までに出現した部分文字列との最大一致長LNと、該出現した部分文字列の出現位置を求め、該最大一致長LNが該最大一致長LMより大きい場合は、置換ポインタを該入力文字列Nの過去の位置を示すものとし、該最大一致長LMが該最大一致長LN以上である場合は、該置換ポインタをサンプル文字列M上の位置を示すものとし、該入力文字列Nの[i…i+L+1]の部分文字列を出現済みの部分文字列として動的辞書記憶手段に格納し、置換ポインタ列と該サンプル文字列を出力する置換ポインタ生成手段と、
を有する符号化手段と、
前記置換ポインタ生成手段から前記置換ポインタ列と前記サンプル文字列を取得し、置換ポインタがサンプル文字列M上の位置を示している場合には、該置換ポインタが参照するサンプル文字列M上の部分文字列を出力し、該置換ポインタが前記入力文字列Nの過去の位置を示す場合には、該置換ポインタが参照する既に復元済みの部分文字列を出力する置換ポインタ分析手段を有する復号手段と、
を有することを特徴とするサンプル文字列（辞書）を用いた二段階置き換えによる圧縮装置。
【請求項２】
前記サンプル文字列記憶手段は、前記入力文字列Nに対して１％以下程度の領域とする
請求項１記載のサンプル文字列（辞書）を用いた二段階置き換えによる圧縮装置。
【請求項３】
置換方式による文字列圧縮方法であって、
サンプル文字列生成手段と、サンプル文字列記憶手段と、動的辞書記憶手段と、置換ポインタ生成手段とを有する符号化手段、及び、置換ポインタ分析手段を有する復号手段とを有する装置において、
前記符号化手段の前記サンプル文字列生成手段が、サンプル文字列長M（M＜＜N）の部分文字列長Sとし、入力文字列Nの開始位置から長さSの部分文字列を取得してサンプル文字列記憶手段に格納するサンプル文字列生成ステップと、
前記符号化手段の前記置換ポインタ生成手段が、前記入力文字列Nの開始位置ｉから始まる部分文字列と、前記サンプル文字列記憶手段から読み出した前記サンプル文字列Mの最大一致長LMと該部分文字列の出現位置PMと、前記入力文字列Nの開始位置ｉ番目から始まる部分文字列とし、該入力文字列Nの０番目からｉ−1番目までに出現した部分文字列との最大一致長LNと、該出現した部分文字列の出現位置を求め、該最大一致長LNが該最大一致長LMより大きい場合は、置換ポインタを該入力文字列Nの過去の位置を示すものとし、該最大一致長LMが該最大一致長LN以上である場合は該置換ポインタをサンプル文字列M上の位置を示すものとし、該入力文字列Nの[i…i+L+1]の部分文字列を出現済みの部分文字列として動的辞書記憶手段に格納し、置換ポインタ列と該サンプル文字列を出力する置換ポインタ生成ステップと、
前記復号手段の前記置換ポインタ分析手段が、前記符号化手段より前記置換ポインタ列と前記サンプル文字列を取得し、置換ポインタがサンプル文字列M上の位置を示している場合には、該置換ポインタが参照するサンプル文字列M上の部分文字列を出力し、該置換ポインタが前記入力文字列Nの過去の位置を示す場合には、該置換ポインタが参照する既に復元済みの部分文字列を出力する置換ポインタ分析ステップと、
を行うことを特徴とするサンプル文字列（辞書）を用いた二段階置き換えによる圧縮方法。
【請求項４】
前記サンプル文字列記憶手段を、前記入力文字列Nに対して１％以下程度の領域とする
請求項３記載のサンプル文字列（辞書）を用いた二段階置き換えによる圧縮方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、文字列圧縮方法及び装置に係り、特に、置換方式における文字列の圧縮方式において、参照局所性を向上させるためのサンプル文字列（辞書）を用いた二段階置き換えによる文字列圧縮方法及び装置に関する。
【０００２】
具体的には、圧縮対象の入力文字列Nから適当な方法で取得したサンプル文字列（部分文字列集合からなる符号化辞書）を、圧縮を行う前に生成して、圧縮時に積極的にサンプル文字列内の部分文字列を参照するポインタに置換することで、復元処理の階層型メモリ構造における参照局性を改善する技術に関する。
【背景技術】
【０００３】
入力された文字列を圧縮する方法としては、以下のような方法がある。
【０００４】
圧縮するべきデータ列を入力として、ハッシュを元にした探索データ構造を用いて適宜現在の圧縮対象文字列と、過去の出現文字列を比較し、出現しているものを過去の出現文字列へのポインタに置き換えることで圧縮を実現する方法がある（例えば、特許文献1参照）。例えば、図1の例では、1回目に出現した文字列「abcd」に対し、2回目以降に同一の文字列「abcd」が出現した場合に、置換ポインタを1回目に出現した文字列のポインタに置き換えることで文字列を圧縮していく。
【０００５】
また、圧縮するべきデータ列を入力として、現在の圧縮対象の文字列と過去の一致文字列を比較判定する処理を適用することで効率的なデータ圧縮を行う方法がある（例えば、特許文献２参照）。
【０００６】
また、辞書に基づく符号化を行う複数のLZ系圧縮を、それらの「圧縮率」を評価しながら適用するLZ圧縮法を切り替えることで圧縮率を効率化する方法がある（例えば、特許文献３参照）。
【先行技術文献】
【特許文献】
【０００７】
【特許文献１】Dean K. Gibson, Mark D. Graybill, "Apparatus and method for very high data rate-compression incorporating lossless data compression and expansion utilizing a hashing technique". US Patent 5,049,881.
【特許文献２】特開2003-179501号公報
【特許文献３】特許第3065591号公報
【発明の概要】
【発明が解決しようとする課題】
【０００８】
しかしながら、上記従来の圧縮方法は、図１に示すように、過去に出現した任意位置の文字列と、現在の文字列が一致した場合に、その過去の該出現文字列へのポインタに置き換えることで圧縮を実現する方法であり、過去の任意の位置に出現した文字列に対するポインタに置き換えていくため、復元時にそのポインタを参照して元の文字列に置き換える際に、特にルールを設けていないため、任意のポインタを参照することになり、メモリ上のどの位置を参照してよいかを特定することができず、ポインタの参照先の参照局所性が保障されない。特に、圧縮対象となる文字列のサイズが100M〜1G等の大きなサイズの場合は復元処理が遅延する可能性がある。
【０００９】
また、特許文献3の方法は、複数のLZ圧縮を組み合わせて使用する技術であるが、「圧縮率」のみを評価対象にそれらの方法を切り替えているため、単純にこれらの組み合わせだけでは復元時の参照局所性の向上、さらには復元速度の向上効果は得られない、という問題がある。
【００１０】
本発明は、上記の点に鑑みなされたもので、従来技術のポインタ置換の前に、サンプル文字列（辞書）を用いることで、復元時の参照局所性を改善し、復元速度を向上させることが可能な文字列圧縮方法及び装置を提供することを目的とする。
【課題を解決するための手段】
【００１１】
本発明は、置換方式による文字列圧縮装置であって、サンプル文字列長M（M＜＜N）の部分文字列長Sとし、入力文字列Nの開始位置から長さSの部分文字列を取得してサンプル文字列記憶手段に格納するサンプル文字列生成手段と、
前記入力文字列Nの開始位置ｉから始まる部分文字列と、前記サンプル文字列記憶手段から読み出した前記サンプル文字列Mの最大一致長LMと該部分文字列の出現位置PMと、前記入力文字列Nの開始位置ｉ番目から始まる部分文字列とし、該入力文字列Nの０番目からｉ−1番目までに出現した部分文字列との最大一致長LNと、該出現した部分文字列の出現位置を求め、該最大一致長LNが該最大一致長LMより大きい場合（LN＞LM）は、置換ポインタを該入力文字列Nの過去の位置を示すものとし、該最大一致長LMが該最大一致長LN以上である場合（LM≦LN）は、該置換ポインタをサンプル文字列M上の位置を示すものとし、該入力文字列Nの[i…i+L+1]の部分文字列を出現済みの部分文字列として動的辞書記憶手段に格納し、置換ポインタ列と該サンプル文字列を出力する置換ポインタ生成手段と、
を有する符号化手段と、
前記置換ポインタ生成手段から前記置換ポインタ列と前記サンプル文字列を取得し、置換ポインタがサンプル文字列M上の位置を示している場合には、該置換ポインタが参照するサンプル文字列M上の部分文字列を出力し、該置換ポインタが前記入力文字列Nの過去の位置を示す場合には、該置換ポインタが参照する既に復元済みの部分文字列を出力する置換ポインタ分析手段を有する復号手段と、を有する。
【発明の効果】
【００１２】
本発明は、固定長間隔サンプル方式によりまとめられたサンプル文字列Mは非常に小さい領域（M<<Nを前提とし、入力文字列Nに対して１％以下程度（例えば、1M,10M程度））としているため、サンプル文字列M上の部分文字列を参照している置換ポインタは、この局所領域を積極的に参照することから、復元時の参照局性が改善し、従来方式と比べて１０倍程度の復元速度が期待できる。特に、入力文字列N中により多くの重複文字列を含む場合（サーバやサービスが出力する一定規則に従ったログ出力など）により高い効果が期待できる。
【図面の簡単な説明】
【００１３】
【図１】置換方式による文字列の圧縮を説明するための図である。
【図２】本発明の一実施の形態における概要を示す図である。
【図３】本発明の一実施の形態における文字列圧縮装置の構成図である。
【図４】本発明の一実施の形態における文字列圧縮処理のフローチャートである。
【図５】本発明の一実施の形態におけるサンプル文字列生成部の処理のフローチャートである。
【図６】本発明の一実施の形態におけるサンプル文字列生成部の処理を示す図である。
【図７】本発明の一実施の形態における置換ポインタ生成部の処理のフローチャートである。
【図８】本発明の一実施の形態における動的辞書記憶部の例である。
【図９】本発明の一実施の形態における置換ポインタ記憶部の例である。
【図１０】本発明の一実施の形態における置換ポインタ分析部の処理のフローチャートである。
【図１１】本発明の効果を示す図である。
【発明を実施するための形態】
【００１４】
以下、図面と共に本発明の実施の形態を説明する。
【００１５】
最初に本発明の概要を説明する。
【００１６】
図２は、本発明の一実施の形態における概要を説明するための図である。
【００１７】
本発明では、サンプル文字列を用いた置換方式の圧縮の改善を目的としており、記憶部（サンプル文字列M記憶部）に格納されているサンプル文字列M（但し、M＜＜入力文字列Nとする）内の部分文字列と置換することにより、サンプル文字列Mは非常に小さい（全入力文字列Nの１％）という前提の下、参照局所性が改善される。なお、上記の１％は、実験により求められた数値である。図２において、サンプル文字列上にないパターンは従来技術による置換方式を適用するものとする。
【００１８】
図３は、本発明の一実施の形態における文字列圧縮装置の構成を示す。
【００１９】
同図に示す文字列圧縮装置は、符号化部１００と復号部２００を有する。
【００２０】
符号化部１００は、サンプル文字列生成部１１０、サンプル文字列取得部１２０、置換ポインタ生成部１３０、サンプル文字列探索部１４０、サンプル文字列M記憶部１５０、動的辞書探索・更新部１６０、動的辞書記憶部１７０、置換ポインタ記憶部１８０を有する。
【００２１】
復号部２００は、置換ポインタ分析部２１０、入力サンプル文字列記憶部２２０、出力文字列記憶部２３０を有する。
【００２２】
上記の構成における処理を以下に示す。
【００２３】
最初に、符号化部１００の処理について説明する。
【００２４】
図４は、本発明の一実施の形態における文字列圧縮処理のフローチャートである。
【００２５】
ステップ１００）  符号化部１００は、入力から圧縮対象の入力文字列Nを受け取るまで待機する。
【００２６】
ステップ２００）  サンプル文字列生成部１１０は、入力文字列Nを引数としてサンプル文字列Mを生成する。
【００２７】
ステップ４００）  置換ポインタ生成部１３０は、入力文字列Nを引数として置換ポインタを生成して置換ポインタ記憶部１８０に格納する。
【００２８】
次に、上記のステップ２００のサンプル文字列生成部１１０の処理を説明する。
【００２９】
図５は、本発明の一実施の形態におけるサンプル文字列生成部の処理のフローチャートである。
【００３０】
ステップ２１０）  サンプル文字列生成部１１０は、入力引数から入力文字列Nを受け取る。
【００３１】
ステップ２２０）  サンプル文字列長をM(M<<N)、部分文字長をSとする。
【００３２】
ステップ２３０）  入力文字列の位置カウントｉを０とする。
【００３３】
ステップ２４０）  入力文字列の開始位置ｉ*N(M/S)から長さSの部分も文字列を取得して、サンプル文字列M記憶部１５０に記録されている文字列の最後尾に連結する。
【００３４】
ステップ２５０）  ｉを１インクリメントする。
【００３５】
ステップ２６０）  M/Sがｉより大きい場合はステップ２４０に移行し、そうでない場合は、当該処理を終了する。
【００３６】
上記の符号化部１００のサンプル文字列生成部１１０は、図６に示すように、入力文字列Nが入力されると、サンプル文字列Mを生成する際に、固定サンプル長（部分文字列長）をSとして、入力文字列Nの位置０,N/(M/S),2N/(M/S),…のM/Sの箇所において、部分文字列長Sを取得して、連結してサンプル文字列Mとする。
【００３７】
サンプル文字列取得部１２０は、サンプル文字列生成部１１０で生成されたサンプル文字列Mをサンプル文字列M記憶部１５０に追加格納する。
【００３８】
次に、上記のステップ３００の置換ポインタ生成部１３０の処理を説明する。
【００３９】
図７は、本発明の一実施の形態における置換ポインタ生成部の処理のフローチャートである。
【００４０】
ステップ３０１）  置換ポインタ生成部１３０は、入力引数から入力文字列Nを受け取る。
【００４１】
ステップ３０２）  入力文字列の位置カウントｉを０とする。
【００４２】
ステップ３０３）  サンプル文字列探索部１４０に対して、入力文字列Nの開始位置ｉ番目から始まる部分文字列と、サンプル文字列M記憶部１５０のサンプル文字列M上の文字列との最大一致長LMと出現位置PMの計算を指示する。サンプル文字列探索部１４０は、入力文字列Nとサンプル文字列M記憶部１５０を参照して、サンプル文字列MのLMとその出現位置PMを計算し、置換ポインタ生成部１３０に返却する。
【００４３】
ステップ３０４）  置換ポインタ生成部１３０は、ステップ３０３と同様に、動的辞書探索・更新部１６０に対して、入力文字列Nの開始位置ｉ番目から始まる部分文字列と入力文字列の[0…ｉ−1]までに出現した部分文字列との最大一致長LNとその出現位置PNの計算を指示する。動的辞書探索・更新部１６０は、入力文字列Nの開始位置ｉ番目から始まる部分文字列と入力文字列の[0…ｉ−1]を比較して最大一致長LNを求め、さらに、最大一致した部分文字列に基づいて動的辞書記憶部１７０を参照して、出現位置PNを取得する。動的辞書記憶部１７０は、図８に示すように、出現文字列と出現位置を格納する辞書であり、出現位置は、例えば、入力文字列Nが「zxywe…」であった場合に、"zxy"の出現位置を"０"、"xyw"の出現位置を"１"、"ywe"の出現位置を"２"のように１文字ずつスライドさせて動的辞書記憶部１７０に登録する。
【００４４】
ステップ３０５）  ステップ３０３で求められた最大一致長LMとステップ３０４で求められた最大一致長LNを比較し、LM<LNであればステップ３０６に移行し、LM≧LNであればステップ３０８に移行する。
【００４５】
ステップ３０６）  置換ポインタ生成部１３０は、LM<LNであるとき（過去の文字列N系列上に出現した場合）、置換ポインタフラグFを０に設定する。つまり、置換ポインタは入力文字列Nの過去の位置となる。
【００４６】
ステップ３０７）  最大一致長LをLNとし、ポインタをLNとし、ステップ３１０に移行する。
【００４７】
ステップ３０８）  置換ポインタ生成部１３０は、LM≧LNであるとき（サンプル文字列M上に出現した場合）、置換ポインタフラグFを１に設定する。つまり、置換ポインタは、サンプリング文字列M上の位置となる。
【００４８】
ステップ３０９）  最大一致長LをLMとし、ポインタをサンプル文字列Mの出現位置PMとする。
【００４９】
ステップ３１０）  上記のステップ３０６、ステップ３０８の置換ポインタフラグFと置換ポインタ（L/P/文字列Nの（ｉ+L+1）番目の文字）を置換ポインタ記憶部１８０に格納する。
【００５０】
置換ポインタ記憶部１８０の例を図９に示す。置換ポインタ記憶部１８０は、置換ポインタ種別フラグと置換ポインタを格納する。置換ポインタ種別フラグが"０"である場合は、置換ポインタは入力文字列Nの過去の位置を表し、"１"である場合は、置換ポインタはサンプル文字列M上の位置を表す。置換ポインタは、{先頭からの位置、長さ、置換文字列の終端文字}の組で構成される。図９の例において、置換ポインタ記憶部１８０の１番目のエントリの置換ポインタ種別フラグは、"１"であるので、置換ポインタがサンプル文字列M上の位置を示す。[サンプル文字列M：abcdefg…]、[入力文字列N：zxywefghｉc…abcdk…ef ghｉj…]であるとき、サンプル文字列Mの"abcd"と入力文字列Nの"abcd"の最大一致長Lは"４"であり、サンプル文字列の開始位置Pは０番目であり、L/P/入力文字列Nの（ｉ+L+1）番目の文字が"k"であるので、置換ポインタは、「0,4,'k'」となる。
【００５１】
ステップ３１１）  入力文字列Nの[ｉ…ｉ+L+1]の部分文字列を動的辞書探索・更新部１６０を用いて出現済みの部分文字列として、動的辞書記憶部１７０に登録する。
【００５２】
ステップ３１２）  ｉをｉ＝ｉ＋L＋１とする。
【００５３】
ステップ３１３）  ｉ＜全入力文字列Ｎであればステップ３０３に移行し、そうでない場合は当該処理を終了する。
【００５４】
上記の処理の後、置換ポインタ生成部１３０は、置換ポインタ記憶部１８０から置換ポインタ列とサンプル文字列Mを復号部２００の置換ポインタ分析部２１０に出力する。
【００５５】
以下、図４のステップ４００の復号部２００の置換ポインタ分析部２１０について説明する。復号部２００は、置換ポインタ生成部１３０から出力された置換ポインタ列とサンプル文字列から文字列Nを復元する。
【００５６】
図１０は、本発明の一実施の形態における置換ポインタ分析部の処理のフローチャートである。
【００５７】
ステップ４０１）  置換ポインタ分析部２１０は、入力引数から置換ポインタ列とポインタ文字列Mを符号化部１００から受け取る。
【００５８】
ステップ４０２）  置換ポインタ分析部２１０は、受け取ったサンプル文字列Mを入力サンプル文字列記憶部２２０に格納する。
【００５９】
ステップ４０３）  置換ポインタ総数をZに設定する。
【００６０】
ステップ４０４）  置換ポインタのカウンタｉを０とする。
【００６１】
ステップ４０５）  ステップ４０１で取得した置換ポインタ列からｉ番目の置換ポインタに含まれる置換ポインタFを取得する。
【００６２】
ステップ４０６）  置換ポインタFが１であるかを判定し、１であればステップ４０８に移行し、そうでなければステップ４０７に移行する。
【００６３】
ステップ４０７）  置換ポインタFが参照する既に復元済みの部分文字列を出力文字列記憶部２３０に出力し、ステップ４０９に移行する。
【００６４】
ステップ４０８）  ｉを１インクリメントする。
【００６５】
ステップ４０９）  ｉ<Zであれば、ステップ４０５に移行し、そうでなければ、当該処理を終了する。
【００６６】
上記の処理により置換ポインタ列は２度以上出現した文字列を初回に出現した文字列の位置のポインタに置換することにより、ポインタが参照している先の文字列を単純に複製していくだけで、元の文字列Nを復元することができる。
【００６７】
上記のように、本発明は、圧縮対象の入力文字列Nから全体の１％以下の部分文字列を固定間隔でサンプリングを行うことで、動的辞書として保存し、圧縮時置き換える文字列のパターンが動的辞書上に存在する場合にはその文字列を、そうでない場合には過去の出現文字列を参照するよう置き換えを実施する。これにより、図１１に示すように、本発明（実線）は、従来技術（点線）に比べて、復元時において、データサイズの大きい領域（512K〜100M）で５〜１０倍程度の復元速度を得ることができる。なお、図１１の測定条件としては、マシン:Xeon5670（メモリ16Gバイト搭載）により、システムコマンドdstatのCSVログ100Mバイトのデータを使用した。
【００６８】
なお、上記の図３に示す文字列圧縮装置の構成要素の動作をプログラムとして構築し、文字列圧縮装置として利用されるコンピュータにインストールして実行させる、または、ネットワークを介して流通させることが可能である。
【００６９】
本発明は、上記の実施の形態に限定されることなく、特許請求の範囲内において、種々変更・応用が可能である。
【符号の説明】
【００７０】
１００  符号化部
１１０  サンプル文字列生成部
１２０  サンプル文字列取得部
１３０  置換ポインタ生成部
１４０  サンプル文字列探索部
１５０  サンプル文字列M記憶部
１６０  動的辞書探索・更新部
１７０  動的辞書記憶部
１８０  置換ポインタ記憶部
２００  復号部
２１０  置換ポインタ分析部
２２０  入力サンプル文字列記憶部
２３０  出力文字列記憶部
【図１】
2014204356.tif 000003
【図２】
2014204356.tif 000004
【図３】
2014204356.tif 000005
【図４】
2014204356.tif 000006
【図５】
2014204356.tif 000007
【図６】
2014204356.tif 000008
【図７】
2014204356.tif 000009
【図８】
2014204356.tif 000010
【図９】
2014204356.tif 000011
【図１０】
2014204356.tif 000012
【図１１】
2014204356.tif 000013