JP2940948B2 - データ圧縮方式 - Google Patents
データ圧縮方式Info
- Publication number
- JP2940948B2 JP2940948B2 JP21574489A JP21574489A JP2940948B2 JP 2940948 B2 JP2940948 B2 JP 2940948B2 JP 21574489 A JP21574489 A JP 21574489A JP 21574489 A JP21574489 A JP 21574489A JP 2940948 B2 JP2940948 B2 JP 2940948B2
- Authority
- JP
- Japan
- Prior art keywords
- buffer
- data
- encoded
- character
- character string
- Prior art date
- Legal status (The legal status is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the status listed.)
- Expired - Lifetime
Links
Landscapes
- Compression, Expansion, Code Conversion, And Decoders (AREA)
Description
【発明の詳細な説明】 〔産業上の利用分野〕 本発明は、文字等のモード列で構成される情報のデー
タ圧縮方式に関し、特に、符号化された符号化データを
処理し易い形式に保ちながらデータの圧縮率を高めるこ
とのできるデータ圧縮方式に関するものである。
タ圧縮方式に関し、特に、符号化された符号化データを
処理し易い形式に保ちながらデータの圧縮率を高めるこ
とのできるデータ圧縮方式に関するものである。
蓄積・伝送すべきデータ量が大きいときには、通信回
線や記憶装置の容量を有効に利用するために、データ列
を圧縮して蓄積・伝送し、再度そのデータを使用すると
きに元のデータ列に復元することが行われている。従
来、文字列（本明細書では、情報理論等で使われている
呼称を踏襲してデータの１ワード毎を文字と呼ぶことに
する）を能率よくデータ圧縮する方式として、Ziv−Lem
pel符号が知られている。このZiv−Lempel符号では、ユ
ニバーサル型と増分分解型という２つのアルゴリズム
（詳しくは、例えば、宗像清治:Ziv−Lempelのデータ圧
縮法，情報処理,Vol.26,No.1（1985））が提案されてい
る。この２つのアルゴリズムの内のユニバーサル型のア
ルゴリズムは、符号化済みの文字列の中から符号化対象
の文字列に最大長に一致する文字部分列を検索して、そ
の文字部分列を複製として符号化を実行する方式であっ
て、増分分解型よりも高いデータ圧縮率が実現できる方
式である。このようなアルゴリズムを実装していくにあ
たっては、データの圧縮率をより高めていく構成を採用
していく必要があるとともに、符号化された符号化デー
タが利用され易い形式となる構成にしていく必要がある
のである。
線や記憶装置の容量を有効に利用するために、データ列
を圧縮して蓄積・伝送し、再度そのデータを使用すると
きに元のデータ列に復元することが行われている。従
来、文字列（本明細書では、情報理論等で使われている
呼称を踏襲してデータの１ワード毎を文字と呼ぶことに
する）を能率よくデータ圧縮する方式として、Ziv−Lem
pel符号が知られている。このZiv−Lempel符号では、ユ
ニバーサル型と増分分解型という２つのアルゴリズム
（詳しくは、例えば、宗像清治:Ziv−Lempelのデータ圧
縮法，情報処理,Vol.26,No.1（1985））が提案されてい
る。この２つのアルゴリズムの内のユニバーサル型のア
ルゴリズムは、符号化済みの文字列の中から符号化対象
の文字列に最大長に一致する文字部分列を検索して、そ
の文字部分列を複製として符号化を実行する方式であっ
て、増分分解型よりも高いデータ圧縮率が実現できる方
式である。このようなアルゴリズムを実装していくにあ
たっては、データの圧縮率をより高めていく構成を採用
していく必要があるとともに、符号化された符号化デー
タが利用され易い形式となる構成にしていく必要がある
のである。
従来のZiv−Lempel符号のユニバーサル型のアルゴリ
ズムを例にして、符号化済みの文字列の中から符号化対
象の文字列に最大長に一致する文字部分列を検索して、
その文字部分列を複製として符号化を実行するデータ圧
縮方式の従来技術について説明する。ここで、Ziv−Lem
pel符号のユニバーサル型のアルゴリズムは、より実際
的な方法であるLZSS符号（T.C.Bell,“Better OPM/L Te
xt Compression",IEEE Trans.on Commun.,Vol.34,No.1
2,Dec.1986）に従って説明する。
ズムを例にして、符号化済みの文字列の中から符号化対
象の文字列に最大長に一致する文字部分列を検索して、
その文字部分列を複製として符号化を実行するデータ圧
縮方式の従来技術について説明する。ここで、Ziv−Lem
pel符号のユニバーサル型のアルゴリズムは、より実際
的な方法であるLZSS符号（T.C.Bell,“Better OPM/L Te
xt Compression",IEEE Trans.on Commun.,Vol.34,No.1
2,Dec.1986）に従って説明する。
従来では、第５図（ａ）に示すように、例えば４ビッ
トのインデックス情報をもってこれから符号化する文字
列を格納するＱバッファ（４ビットのインデックスに対
応して16個の文字数を格納できる）と、第５図（ｂ）に
示すように、例えば12ビットのインデックス情報をもっ
て符号化済みの文字列を格納するＰバッファ（12ビット
のインデックスに対応して4096個の文字数を格納でき
る）とを備えるよう構成する。そして、第６図に示すよ
うに、Ｑバッファの文字列とＰバッファの文字列とを照
合し最大長に一致する文字部分列を求めて、この求めら
れた文字部分列を指定するために、「その文字部分列の
Ｐバッファにおける一致開始位置」と「その文字部分列
の一致長」とを符号化していくよう処理するとともに、
Ｑバッファ内の符号化した文字列をＰバッファに移し
て、Ｑバッファ内に符号化した文字列分の新たな文字列
を入力していくことで符号化を実行していくよう処理す
る。
トのインデックス情報をもってこれから符号化する文字
列を格納するＱバッファ（４ビットのインデックスに対
応して16個の文字数を格納できる）と、第５図（ｂ）に
示すように、例えば12ビットのインデックス情報をもっ
て符号化済みの文字列を格納するＰバッファ（12ビット
のインデックスに対応して4096個の文字数を格納でき
る）とを備えるよう構成する。そして、第６図に示すよ
うに、Ｑバッファの文字列とＰバッファの文字列とを照
合し最大長に一致する文字部分列を求めて、この求めら
れた文字部分列を指定するために、「その文字部分列の
Ｐバッファにおける一致開始位置」と「その文字部分列
の一致長」とを符号化していくよう処理するとともに、
Ｑバッファ内の符号化した文字列をＰバッファに移し
て、Ｑバッファ内に符号化した文字列分の新たな文字列
を入力していくことで符号化を実行していくよう処理す
る。
そして、第７図に示すように、８個の符号化データ若
しくは生データを１組のデータとしてまとめるととも
に、このまとめられた各８個のデータが符号化データな
のか生データなのかを表示する８ビットの識別データを
先頭に付加してこの１組のデータを出力していくよう処
理することで、符号化できない生データの蓄積・伝送を
実行するとともに、２バイトの符号化データよりも生デ
ータの方を蓄積・伝送した方が有利である場合において
の生データの蓄積・伝送を実行していくという構成を採
るのである。
しくは生データを１組のデータとしてまとめるととも
に、このまとめられた各８個のデータが符号化データな
のか生データなのかを表示する８ビットの識別データを
先頭に付加してこの１組のデータを出力していくよう処
理することで、符号化できない生データの蓄積・伝送を
実行するとともに、２バイトの符号化データよりも生デ
ータの方を蓄積・伝送した方が有利である場合において
の生データの蓄積・伝送を実行していくという構成を採
るのである。
このような従来技術にあって、データの圧縮率を高め
ていくためには、Ｐバッファの格納文字数を多くしてい
く必要があるとともに、Ｑバッファの格納文字数を多く
していく必要がある。しかるに、ＰバッファとＱバッフ
ァの格納文字数を増加させると、符号化データが８ビッ
トの倍数でなくなるため、データを転送する際にビット
詰め等の面倒な処理が強いられ極めて不便なものとな
る。そうかといって、Ｐバッファのビット幅を18ビッ
ト、Ｑバッファのビット幅を６ビット等といったように
符号化データが３バイトになるようにすれば、符号化デ
ータのデータ量が著しく多くなってしまうという問題点
がでてくることになる。
ていくためには、Ｐバッファの格納文字数を多くしてい
く必要があるとともに、Ｑバッファの格納文字数を多く
していく必要がある。しかるに、ＰバッファとＱバッフ
ァの格納文字数を増加させると、符号化データが８ビッ
トの倍数でなくなるため、データを転送する際にビット
詰め等の面倒な処理が強いられ極めて不便なものとな
る。そうかといって、Ｐバッファのビット幅を18ビッ
ト、Ｑバッファのビット幅を６ビット等といったように
符号化データが３バイトになるようにすれば、符号化デ
ータのデータ量が著しく多くなってしまうという問題点
がでてくることになる。
本発明はかかる事情に鑑みてなされたものであって、
符号化済みの文字列の中から符号化対象の文字列に最大
長に一致する文字部分列を検索して、その文字部分列を
複製として符号化を実行するデータ圧縮方式において、
符号化された符号化データを処理し易い形式に保ちなが
らデータの圧縮率を高めることのできる新たなデータ圧
縮方式の提供を目的とするものである。
符号化済みの文字列の中から符号化対象の文字列に最大
長に一致する文字部分列を検索して、その文字部分列を
複製として符号化を実行するデータ圧縮方式において、
符号化された符号化データを処理し易い形式に保ちなが
らデータの圧縮率を高めることのできる新たなデータ圧
縮方式の提供を目的とするものである。
第１図は本発明の原理構成図である。
図中、１は本発明を具備する符号化処理装置、２は入
力データファイルであって、符号化対象のデータを格納
するもの、３は出力データファイルであって、符号化デ
ータを格納するもの、10はファイル読出手段であって、
入力データファイル２からデータを読み出すもの、11は
第１のバッファであって、、例えば５ビットのインデッ
クス情報に従って符号化対象の文字列を順次格納してい
くもの、12は第２のバッファであって、例えば３個とい
った複数のバッファの接続により構成されて、符号化済
みの文字列を順次格納していくもの、13は第２のバッフ
ァ12を構成する複数のバッファであって、各バッファ13
のインデックス情報のビット数と第１のバッファ11のイ
ンデックス情報のビット数との合計値がバイトの倍数に
なるようなビット数のインデックス情報に従って符号化
済みの文字列を順次格納していくもの、14は文字列転送
制御手段であって、ファイル読出手段10から第１のバッ
ファ11への文字列転送と、第１のバッファ11から第２の
バッファ12への文字列転送を制御するもの、15は符号化
手段であって、第１のバッファ11の文字列と第２のバッ
ファ12の文字列とを照合することで最大長に一致する文
字部分列を求めるとともに、対応するバッファ13の先頭
位置からのインデックス情報により表されるこの文字部
分列の一致開始位置情報とこの文字部分列の一致長情報
とを符号化するもの、16は出力手段であって、符号化手
段15により符号化される符号化データ若しくは生データ
の複数個を１組のデータとして出力データファイル３に
出力していくもの、17は出力手段16が増える識別データ
付加手段であって、１組のデータとして出力される符号
化データの一致開始位置の位置するバッファ13の識別名
と、１組のデータとして出力される生データの識別子と
を表示する識別データを、出力する１組のデータの先頭
に付加していくものである。
力データファイルであって、符号化対象のデータを格納
するもの、３は出力データファイルであって、符号化デ
ータを格納するもの、10はファイル読出手段であって、
入力データファイル２からデータを読み出すもの、11は
第１のバッファであって、、例えば５ビットのインデッ
クス情報に従って符号化対象の文字列を順次格納してい
くもの、12は第２のバッファであって、例えば３個とい
った複数のバッファの接続により構成されて、符号化済
みの文字列を順次格納していくもの、13は第２のバッフ
ァ12を構成する複数のバッファであって、各バッファ13
のインデックス情報のビット数と第１のバッファ11のイ
ンデックス情報のビット数との合計値がバイトの倍数に
なるようなビット数のインデックス情報に従って符号化
済みの文字列を順次格納していくもの、14は文字列転送
制御手段であって、ファイル読出手段10から第１のバッ
ファ11への文字列転送と、第１のバッファ11から第２の
バッファ12への文字列転送を制御するもの、15は符号化
手段であって、第１のバッファ11の文字列と第２のバッ
ファ12の文字列とを照合することで最大長に一致する文
字部分列を求めるとともに、対応するバッファ13の先頭
位置からのインデックス情報により表されるこの文字部
分列の一致開始位置情報とこの文字部分列の一致長情報
とを符号化するもの、16は出力手段であって、符号化手
段15により符号化される符号化データ若しくは生データ
の複数個を１組のデータとして出力データファイル３に
出力していくもの、17は出力手段16が増える識別データ
付加手段であって、１組のデータとして出力される符号
化データの一致開始位置の位置するバッファ13の識別名
と、１組のデータとして出力される生データの識別子と
を表示する識別データを、出力する１組のデータの先頭
に付加していくものである。
本発明では、第１のバッファ11が例えば５ビットのイ
ンデックス情報に従って32個の符号化対象の文字列を格
納していくときには、例えば３個設けられる各バッファ
13は、例えば11ビットのインデックス情報を持つよう構
成されることで2048個の文字数を格納できるよう構成さ
れる。従って、このとき第２のバッファ12は、2048×３
個の文字数を格納できるよう構成される。
ンデックス情報に従って32個の符号化対象の文字列を格
納していくときには、例えば３個設けられる各バッファ
13は、例えば11ビットのインデックス情報を持つよう構
成されることで2048個の文字数を格納できるよう構成さ
れる。従って、このとき第２のバッファ12は、2048×３
個の文字数を格納できるよう構成される。
符号化手段15は、この第１のバッファ11を第６図で説
明したＱバッファとして用い、第２のバッファ12を第６
図で説明したＰバッファとして用いて、第１のバッファ
11の文字列と第２のバッファ12の文字列とを照合するこ
とで最大長に一致する文字部分列を求めて、この求めら
れた文字部分列の第２のバッファ12における位置を指定
するために、「文字部分列の一致開始位置の位置するバ
ッファ13の識別名」を特定するとともに、「その特定さ
れたバッファ13における文字部分列の一致開始位置のイ
ンデックス情報」と「文字部分列の一致長情報」とを符
号化する。このようにして符号化される符号化データ
は、11ビットのインデックス情報と一致長情報の５ビッ
トとに従って２バイトで表されることになる。
明したＱバッファとして用い、第２のバッファ12を第６
図で説明したＰバッファとして用いて、第１のバッファ
11の文字列と第２のバッファ12の文字列とを照合するこ
とで最大長に一致する文字部分列を求めて、この求めら
れた文字部分列の第２のバッファ12における位置を指定
するために、「文字部分列の一致開始位置の位置するバ
ッファ13の識別名」を特定するとともに、「その特定さ
れたバッファ13における文字部分列の一致開始位置のイ
ンデックス情報」と「文字部分列の一致長情報」とを符
号化する。このようにして符号化される符号化データ
は、11ビットのインデックス情報と一致長情報の５ビッ
トとに従って２バイトで表されることになる。
そして、出力手段16が符号化手段15により符号化され
る２バイトの符号化データ若しくは生データの例えば４
個を１組のデータとして出力データファイル３に出力し
ていくときにあって、識別データ付加手段17は、符号化
データの元となったインデックス情報がどのバッファ13
に係るものなのかを識別データの中に表示していくよう
処理することで、第２のバッファ12中における文字部分
列の一致開始位置を特定できるよう処理する。
る２バイトの符号化データ若しくは生データの例えば４
個を１組のデータとして出力データファイル３に出力し
ていくときにあって、識別データ付加手段17は、符号化
データの元となったインデックス情報がどのバッファ13
に係るものなのかを識別データの中に表示していくよう
処理することで、第２のバッファ12中における文字部分
列の一致開始位置を特定できるよう処理する。
このように、第６図に説明した従来技術であれば、16
個の文字数しか格納できないＱバッファと4096個の文字
数しか格納できないＰバッファとに従って、２バイトの
符号化データが生成されていたのに対して、本発明によ
れば、例えば、32個の文字数を格納できる第１のバッフ
ァ１と2048×３個の文字数を格納できる第２のバッファ
12とに従って、同じ２バイトの符号化データを生成でき
るようになる。これから、符号化済みの文字列の中から
符号化対象の文字列に最大長に一致する文字部分列を検
索して、その文字部分列を複製として符号化を実行する
データ圧縮方式において、符号化データを例えば２バイ
トというバイトの倍数の処理し易い形式に保ちながら、
照合対象の文字数を増加させることでデータの圧縮率を
高めることができるようになるのである。
個の文字数しか格納できないＱバッファと4096個の文字
数しか格納できないＰバッファとに従って、２バイトの
符号化データが生成されていたのに対して、本発明によ
れば、例えば、32個の文字数を格納できる第１のバッフ
ァ１と2048×３個の文字数を格納できる第２のバッファ
12とに従って、同じ２バイトの符号化データを生成でき
るようになる。これから、符号化済みの文字列の中から
符号化対象の文字列に最大長に一致する文字部分列を検
索して、その文字部分列を複製として符号化を実行する
データ圧縮方式において、符号化データを例えば２バイ
トというバイトの倍数の処理し易い形式に保ちながら、
照合対象の文字数を増加させることでデータの圧縮率を
高めることができるようになるのである。
以下、実施例に従って本発明を詳細に説明する。
第２図に、第５図で説明したところのＰバッファとＱ
バッファについての本発明の一実施例を図示する。この
第２図（ａ）に示すように、本発明のＱバッファは、従
来のＱバッファより多くの文字数である例えば32個の文
字数を格納できるように、例えば５ビットのインデック
ス情報を有するもので構成される。一方、本発明のＰバ
ッファは、この第２図（ｂ）に示すように、例えばP1バ
ッファ13−ａ、P2バッファ13−ｂ、P3バッファ13−ｃと
いう３個のバッファを接続することで構成されるもの
で、この各Piバッファ13−ｉ（ｉ＝a,b,c）は、各Piバ
ッファ13−ｉのインデックス情報のビット数とＱバッフ
ァのインデックス情報のビット数との合計値がバイトの
倍数となるビット数のインデックス情報を有するもので
構成されることになる。具体的には、各Piバッファ13−
ｉは、例えば11ビットという同一のインデックス情報を
有するもので構成される。従って、本発明のＰバッファ
は、この11ビットのインデックス情報に従って例えば20
48×３個の文字数を格納できることになる。
バッファについての本発明の一実施例を図示する。この
第２図（ａ）に示すように、本発明のＱバッファは、従
来のＱバッファより多くの文字数である例えば32個の文
字数を格納できるように、例えば５ビットのインデック
ス情報を有するもので構成される。一方、本発明のＰバ
ッファは、この第２図（ｂ）に示すように、例えばP1バ
ッファ13−ａ、P2バッファ13−ｂ、P3バッファ13−ｃと
いう３個のバッファを接続することで構成されるもの
で、この各Piバッファ13−ｉ（ｉ＝a,b,c）は、各Piバ
ッファ13−ｉのインデックス情報のビット数とＱバッフ
ァのインデックス情報のビット数との合計値がバイトの
倍数となるビット数のインデックス情報を有するもので
構成されることになる。具体的には、各Piバッファ13−
ｉは、例えば11ビットという同一のインデックス情報を
有するもので構成される。従って、本発明のＰバッファ
は、この11ビットのインデックス情報に従って例えば20
48×３個の文字数を格納できることになる。
このように、第５図に図示した従来技術であれば、Ｑ
バッファが16個の文字数、Ｐバッファが4096個の文字数
しか格納できないのに対して、本発明では、Ｑバッファ
が32個の文字数、Ｐバッファが2048×３個の文字数を格
納できるように構成されるのである。
バッファが16個の文字数、Ｐバッファが4096個の文字数
しか格納できないのに対して、本発明では、Ｑバッファ
が32個の文字数、Ｐバッファが2048×３個の文字数を格
納できるように構成されるのである。
しかしながら、このようにＰバッファのインデックス
情報を多くすると、符号化データを２バイトの構成にで
きなくなり、データを転送する際にビット詰め等の面倒
な処理が強いられて極めて不便なものになる。そこで、
本発明では、まとめて出力する１組のデータの先頭に付
加されることになる識別データ（第７図に図示してある
もの）を利用して、求められる文字部分列の一致開始位
置が属するPiバッファ13−ｉの識別名をこの識別データ
に表示するよう構成するものである。そして、符号化対
象となる実際のＰバッファのインデックス情報（文字部
分列の一致開始位置情報を指定するもの）については、
一致開始位置が属するPiバッファ13−ｉのインデックス
情報を使用することで11ビットで済ませるようにして、
符号化データを従来通りの２バイトで実現できるよう構
成するものである。
情報を多くすると、符号化データを２バイトの構成にで
きなくなり、データを転送する際にビット詰め等の面倒
な処理が強いられて極めて不便なものになる。そこで、
本発明では、まとめて出力する１組のデータの先頭に付
加されることになる識別データ（第７図に図示してある
もの）を利用して、求められる文字部分列の一致開始位
置が属するPiバッファ13−ｉの識別名をこの識別データ
に表示するよう構成するものである。そして、符号化対
象となる実際のＰバッファのインデックス情報（文字部
分列の一致開始位置情報を指定するもの）については、
一致開始位置が属するPiバッファ13−ｉのインデックス
情報を使用することで11ビットで済ませるようにして、
符号化データを従来通りの２バイトで実現できるよう構
成するものである。
すなわち、本発明では、Ｐバッファを３個のPiバッフ
ァ13−ｉで構成するときには、第３図に示すように、ま
とめて出力する１組のデータを４個とするとともに、８
ビットの識別データを２ビット単位に区切って、符号化
データの元となった文字部分列の一致開始位置がP1バッ
ファ13−１に属するときにはこの２ビットに“00"を割
り付け、P2バッファ13−２に属するときには“01"を割
り付け、P3バッファ13−３に属するときには“10"を割
り付けることで、符号化データに関してのインデックス
情報がどのPiバッファ13−ｉに係るものであるのかを表
示するよう構成するのである。なお、生データについて
は、この識別データの２ビットに“11"が割り付けられ
ることになる。
ァ13−ｉで構成するときには、第３図に示すように、ま
とめて出力する１組のデータを４個とするとともに、８
ビットの識別データを２ビット単位に区切って、符号化
データの元となった文字部分列の一致開始位置がP1バッ
ファ13−１に属するときにはこの２ビットに“00"を割
り付け、P2バッファ13−２に属するときには“01"を割
り付け、P3バッファ13−３に属するときには“10"を割
り付けることで、符号化データに関してのインデックス
情報がどのPiバッファ13−ｉに係るものであるのかを表
示するよう構成するのである。なお、生データについて
は、この識別データの２ビットに“11"が割り付けられ
ることになる。
次に、第４図のフローチャートに従って、このように
構成される本発明の符号化処理について説明する。
構成される本発明の符号化処理について説明する。
第４図のフローチャートのステップ１で示すように、
先ず最初に、符号化対象の文字列をＱバッファに読み込
む。続いて、ステップ２で、符号化対象とされるすべて
の文字列の処理が終了したのか否かを判断する。この判
断で、未だ処理が終了していないと判断するときには、
次のステップ３で、ＰバッファとＱバッファとの照合処
理（以下、Ｐバッファスキャンと称する）を４回実行し
たのか否かを判断する。すなわち、１組としてまとめて
出力する符号化データ・生データが得られたのか否かを
判断するのである。このステップ３の判断で未だ４回の
Ｐバッファスキャンを実行していないと判断するときに
は、ステップ４に進んでＰバッファスキャンを実行する
ことで、Ｐバッファの中で一致する最大長の文字部分列
を求める処理を行う。このＰバッファスキャンのとき、
３個のPiバッファ13−ｉに格納されている符号化済みの
文字列は、あたかも一続きの文字列として扱われること
になる。
先ず最初に、符号化対象の文字列をＱバッファに読み込
む。続いて、ステップ２で、符号化対象とされるすべて
の文字列の処理が終了したのか否かを判断する。この判
断で、未だ処理が終了していないと判断するときには、
次のステップ３で、ＰバッファとＱバッファとの照合処
理（以下、Ｐバッファスキャンと称する）を４回実行し
たのか否かを判断する。すなわち、１組としてまとめて
出力する符号化データ・生データが得られたのか否かを
判断するのである。このステップ３の判断で未だ４回の
Ｐバッファスキャンを実行していないと判断するときに
は、ステップ４に進んでＰバッファスキャンを実行する
ことで、Ｐバッファの中で一致する最大長の文字部分列
を求める処理を行う。このＰバッファスキャンのとき、
３個のPiバッファ13−ｉに格納されている符号化済みの
文字列は、あたかも一続きの文字列として扱われること
になる。
ステップ４でのＰバッファスキャンにより文字部分列
が無いと判断されるときには、ステップ５に進んで、生
データを出力処理のために用意される出力バッファに格
納し、次のステップ６で、生データであることを表す識
別子を生データとの対応をとりつつ出力バッファに格納
してから、続くステップ７で、Ｐバッファの更新処理を
実行（このステップ６を経由するときには実質的な更新
処理は行われない）してステップ１に戻るよう処理す
る。
が無いと判断されるときには、ステップ５に進んで、生
データを出力処理のために用意される出力バッファに格
納し、次のステップ６で、生データであることを表す識
別子を生データとの対応をとりつつ出力バッファに格納
してから、続くステップ７で、Ｐバッファの更新処理を
実行（このステップ６を経由するときには実質的な更新
処理は行われない）してステップ１に戻るよう処理す
る。
一方、ステップ４でのＰバッファスキャンにより文字
部分列が有ると判断されるときには、ステップ８に進ん
で、その文字部分列の一致開始位置が属するPiバッファ
13−ｉの識別名を検出するとともに、文字部分列の一致
開始位置が位置するインデックス情報をその検出された
Piバッファ13−ｉのインデックス情報に換算して作成
し、更に、文字部分列の一致長を検出する処理を実行す
る。すなわち、第２図（ｂ）のＰバッファ構成で具体的
に説明するならば、作成されるインデックス値Ｉは、検
出される文字部分列の一致開始位置のインデックス値
Ｉ′から、次式に従って、 ＊ 211≦Ｉ′≦211×２−１のとき Ｉ＝Ｉ′−211 ＊ 211×２≦Ｉ′≦211×３−１のとき Ｉ＝Ｉ′−211×２ で算出されることになる。
部分列が有ると判断されるときには、ステップ８に進ん
で、その文字部分列の一致開始位置が属するPiバッファ
13−ｉの識別名を検出するとともに、文字部分列の一致
開始位置が位置するインデックス情報をその検出された
Piバッファ13−ｉのインデックス情報に換算して作成
し、更に、文字部分列の一致長を検出する処理を実行す
る。すなわち、第２図（ｂ）のＰバッファ構成で具体的
に説明するならば、作成されるインデックス値Ｉは、検
出される文字部分列の一致開始位置のインデックス値
Ｉ′から、次式に従って、 ＊ 211≦Ｉ′≦211×２−１のとき Ｉ＝Ｉ′−211 ＊ 211×２≦Ｉ′≦211×３−１のとき Ｉ＝Ｉ′−211×２ で算出されることになる。
このようにして、ステップ８の処理により符号化すべ
きインデックス値と一致長とが求まると、次のステップ
９で、従来技術と同様の処理に従って符号化データを作
成して出力バッファに格納し、続くステップ10で、ステ
ップ８の処理により求められたPiバッファ13−ｉの識別
名を符号化データとの対応をとりつつ出力バッファに格
納してから、ステップ７に進んで、Ｐバッファの更新処
理を実行してステップ１に戻るよう処理する。なお、こ
のフローチャートでは省略してあるが、符号化データよ
りも生データを蓄積・伝送した方が有利であることが判
明したときには、ステップ５及びステップ６での処理が
実行されることになる。
きインデックス値と一致長とが求まると、次のステップ
９で、従来技術と同様の処理に従って符号化データを作
成して出力バッファに格納し、続くステップ10で、ステ
ップ８の処理により求められたPiバッファ13−ｉの識別
名を符号化データとの対応をとりつつ出力バッファに格
納してから、ステップ７に進んで、Ｐバッファの更新処
理を実行してステップ１に戻るよう処理する。なお、こ
のフローチャートでは省略してあるが、符号化データよ
りも生データを蓄積・伝送した方が有利であることが判
明したときには、ステップ５及びステップ６での処理が
実行されることになる。
このようにして、Ｐバッファスキャンを繰り返し実行
していくと、ステップ３の判断でＰバッファスキャンを
４回実行したことが判断されることになるので、このと
きには、ステップ11に進んで、出力バッファを参照する
ことで１組として出力することになる４個のデータに関
しての識別データを作成し、次のステップ12で、出力バ
ッファを参照することで１組として出力することになる
４個のデータをまとめるよう処理し、そして、続くステ
ップ13で、この識別データとまとめられたデータとを図
示しない出力ファイル等に出力してステップ１に戻るこ
とで、処理対象の文字列の符号化処理を実行していくよ
う処理することになる。
していくと、ステップ３の判断でＰバッファスキャンを
４回実行したことが判断されることになるので、このと
きには、ステップ11に進んで、出力バッファを参照する
ことで１組として出力することになる４個のデータに関
しての識別データを作成し、次のステップ12で、出力バ
ッファを参照することで１組として出力することになる
４個のデータをまとめるよう処理し、そして、続くステ
ップ13で、この識別データとまとめられたデータとを図
示しない出力ファイル等に出力してステップ１に戻るこ
とで、処理対象の文字列の符号化処理を実行していくよ
う処理することになる。
以上図示実施例について説明したが、本発明はこれに
限定されるものではない。例えば明細書中の数値は説明
の便宜のために用いたものであって、これに限られるも
のではないのである。
限定されるものではない。例えば明細書中の数値は説明
の便宜のために用いたものであって、これに限られるも
のではないのである。
以上説明したように、本発明によれば、符号化済みの
文字列の中から符号化対象の文字列に最大長に一致する
文字部分列を検索して、その文字部分列を複製として符
号化を実行するデータ圧縮方式において、照合処理の対
象となる文字列数を長くとれるようになることからデー
タ圧縮率を高めることができるようになるとともに、符
号化データを例えば２バイトというようにバイトの倍数
に設定できるので、ビット詰め等の処理を必要とするこ
となく符号化データを処理し易い形式に保てるのであ
る。
文字列の中から符号化対象の文字列に最大長に一致する
文字部分列を検索して、その文字部分列を複製として符
号化を実行するデータ圧縮方式において、照合処理の対
象となる文字列数を長くとれるようになることからデー
タ圧縮率を高めることができるようになるとともに、符
号化データを例えば２バイトというようにバイトの倍数
に設定できるので、ビット詰め等の処理を必要とするこ
となく符号化データを処理し易い形式に保てるのであ
る。
第１図は本発明の原理構成図、 第２図は本発明のＰバッファとＱバッファの一実施例、 第３図は本発明の符号化データ構造の一実施例、 第４図は本発明が実行するフローチャート、 第５図、第６図及び第７図は従来技術の説明図である。 図中、１は符号化処理装置、２は入力データファイル、
３は出力データファイル、10はファイル読出手段、11は
第１のバッファ、12は第２のバッファ、13はバッファ、
14は文字列転送制御手段、15は符号化手段、16は出力手
段、17は識別データ付加手段である。
３は出力データファイル、10はファイル読出手段、11は
第１のバッファ、12は第２のバッファ、13はバッファ、
14は文字列転送制御手段、15は符号化手段、16は出力手
段、17は識別データ付加手段である。
フロントページの続き (56)参考文献 ＩＥＥＥ Ｔｒａｎｓａｃｔｉｏｎｓ ｏｎ Ｃｏｍｍｕｎｉｃａｔｉｏｎ ｓ，Ｖｏｌ．ＣＯＭ−34，Ｎｏ．12，Ｄ ｅｃ．1986，Ｔｉｍｏｔｈｙ Ｃ．Ｂｅ ｌｌ，”Ｂｅｔｔｅｒ ＯＰＭ／Ｌ Ｔ ｅｘｔ Ｃｏｍｐｒｅｓｓｉｏｎ，Ｐ. 1176−1182 (58)調査した分野(Int.Cl.6，ＤＢ名) H03M 7/40
Claims (1)
- 【請求項１】符号化対象となる文字列を格納する第１の
バッファと、 符号化済みの文字列を格納するものとして用意され、同
一文字数を格納できる複数の構成単位バッファの繋がり
で構成されて、該構成単位バッファの格納できる文字数
を2mで表したときの値ｍと、上記第１のバッファの格納
できる文字数を2nで表したときの値ｎとの合計がバイト
の倍数となる第２のバッファと、 上記第１のバッファの文字列と、上記第２のバッファの
文字列とを照合することで最大長に一致する文字部分列
を求めて、該文字部分列の一致開始位置が属する上記構
成単位バッファの先頭位置から指定される該一致開始位
置の情報と、該文字部分列の一致長情報とを符号化する
符号化手段と、 上記符号化手段により符号化される符号化データ又は符
号化されない生データの複数個を１組の出力対象データ
として、該出力対象データに、符号化データについて
は、上記一致開始位置の属する上記構成単位バッファの
識別子情報を表示し、生データについては、その旨の情
報を表示するヘッダ情報を付加して出力する出力手段と
を備えることを、 特徴とするデータ圧縮方式。
Priority Applications (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| JP21574489A JP2940948B2 (ja) | 1989-08-22 | 1989-08-22 | データ圧縮方式 |
Applications Claiming Priority (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| JP21574489A JP2940948B2 (ja) | 1989-08-22 | 1989-08-22 | データ圧縮方式 |
Publications (2)
| Publication Number | Publication Date |
|---|---|
| JPH0378322A JPH0378322A (ja) | 1991-04-03 |
| JP2940948B2 true JP2940948B2 (ja) | 1999-08-25 |
Family
ID=16677491
Family Applications (1)
| Application Number | Title | Priority Date | Filing Date |
|---|---|---|---|
| JP21574489A Expired - Lifetime JP2940948B2 (ja) | 1989-08-22 | 1989-08-22 | データ圧縮方式 |
Country Status (1)
| Country | Link |
|---|---|
| JP (1) | JP2940948B2 (ja) |
Families Citing this family (6)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| CA2077271C (en) * | 1991-12-13 | 1998-07-28 | David J. Craft | Method and apparatus for compressing data |
| JP3242795B2 (ja) * | 1994-10-17 | 2001-12-25 | 富士通株式会社 | データ処理装置及びデータ処理方法 |
| US5771010A (en) * | 1995-03-22 | 1998-06-23 | Ibm Corporation | Apparatus for compressing data using a Lempel-Ziv-type algorithm |
| US5913216A (en) * | 1996-03-19 | 1999-06-15 | Lucent Technologies, Inc. | Sequential pattern memory searching and storage management technique |
| US5798718A (en) * | 1997-05-12 | 1998-08-25 | Lexmark International, Inc. | Sliding window data compression method and apparatus |
| JP6048251B2 (ja) * | 2013-03-21 | 2016-12-21 | 富士通株式会社 | データ圧縮装置、データ圧縮方法、およびデータ圧縮プログラム、並びにデータ復元装置、データ復元方法、およびデータ復元プログラム |
-
1989
- 1989-08-22 JP JP21574489A patent/JP2940948B2/ja not_active Expired - Lifetime
Non-Patent Citations (1)
| Title |
|---|
| ＩＥＥＥ Ｔｒａｎｓａｃｔｉｏｎｓ ｏｎ Ｃｏｍｍｕｎｉｃａｔｉｏｎｓ，Ｖｏｌ．ＣＯＭ−３４，Ｎｏ．１２，Ｄｅｃ．１９８６，Ｔｉｍｏｔｈｙ Ｃ．Ｂｅｌｌ，"Ｂｅｔｔｅｒ ＯＰＭ／Ｌ Ｔｅｘｔ Ｃｏｍｐｒｅｓｓｉｏｎ，Ｐ．１１７６−１１８２ |
Also Published As
| Publication number | Publication date |
|---|---|
| JPH0378322A (ja) | 1991-04-03 |
Similar Documents
| Publication | Publication Date | Title |
|---|---|---|
| US5608396A (en) | Efficient Ziv-Lempel LZI data compression system using variable code fields | |
| US5229768A (en) | Adaptive data compression system | |
| JP3240495B2 (ja) | データの可逆符号化方法および装置、並びに、伸長装置 | |
| US5353024A (en) | Method for data compression having an improved encoding algorithm which utilizes a token stacking technique | |
| US5594435A (en) | Permutation-based data compression | |
| JP3241788B2 (ja) | データ圧縮方式 | |
| JP2940948B2 (ja) | データ圧縮方式 | |
| US6240213B1 (en) | Data compression system having a string matching module | |
| JP2536422B2 (ja) | デ―タ圧縮装置及びデ―タ復元装置 | |
| JP3105598B2 (ja) | ユニバーサル符号を用いたデータ圧縮方式 | |
| JPH05134847A (ja) | データ圧縮方法 | |
| JP3199292B2 (ja) | ハフマン符号の符号化でのランレングス抽出方法、ハフマン符号変換方法およびｍｈ符号化処理方法 | |
| JP2823917B2 (ja) | データ圧縮方式 | |
| JP3051501B2 (ja) | データ圧縮方法 | |
| JP2999561B2 (ja) | データ圧縮及び復元装置 | |
| JP3384844B2 (ja) | データ圧縮方法および装置並びにデータ復元方法および装置 | |
| JP3199291B2 (ja) | ハフマン復号化テーブルの構成方法 | |
| JP3100206B2 (ja) | データ圧縮方法 | |
| JPH05341955A (ja) | データ圧縮および復元方式 | |
| JPS6276931A (ja) | デ−タ圧縮装置 | |
| JP3078601B2 (ja) | データ圧縮方法 | |
| US6285303B1 (en) | Gate table data compression and recovery process | |
| JP3442105B2 (ja) | データ圧縮および復元方式 | |
| JPH06291677A (ja) | データ圧縮装置及びデータ復元装置 | |
| JPH02218224A (ja) | データ転送方法 |