Top > Search of Japanese Patents > DATA COMPRESSION/DECOMPRESSION SYSTEM, DATA COMPRESSION METHOD AND DATA DECOMPRESSION METHOD, AND DATA COMPRESSOR AND DATA DECOMPRESSOR

DATA COMPRESSION/DECOMPRESSION SYSTEM, DATA COMPRESSION METHOD AND DATA DECOMPRESSION METHOD, AND DATA COMPRESSOR AND DATA DECOMPRESSOR

Patent code P160013529
File No. S2015-0146-N0
Posted date Nov 29, 2016
Application number P2015-063449
Publication number P2016-184830A
Patent number P6256883
Date of filing Mar 25, 2015
Date of publication of application Oct 20, 2016
Date of registration Dec 15, 2017
Inventor
  • (In Japanese)山際 伸一
  • (In Japanese)坂本 比呂志
Applicant
  • (In Japanese)国立大学法人筑波大学
  • (In Japanese)国立大学法人九州工業大学
Title DATA COMPRESSION/DECOMPRESSION SYSTEM, DATA COMPRESSION METHOD AND DATA DECOMPRESSION METHOD, AND DATA COMPRESSOR AND DATA DECOMPRESSOR
Abstract PROBLEM TO BE SOLVED: To generate and apply conversion rules in line with the tendency of data, when compressing transfer data in real time.
SOLUTION: A data compression method compresses a data column in units of symbol, i.e., a data of a fixed length. A conversion table for registering an entry indicating the matching of more than one symbols before conversion and one symbol after conversion is searched. When a determination is made that more than one continuous symbols in the data column are not registered as more than one symbols before conversion, an entry for determining the more than one continuous symbols as the more than one symbols before conversion is registered in the conversion table, and the more than one continuous symbols are outputted without being converted. When the more than one continuous symbols in the data column are registered as more than one symbols before conversion in the entry of the conversion table, the more than one continuous symbols are converted into one symbol after conversion associated with that entry.
Outline of related art and contending technology (In Japanese)

近年における、データストリームがネットワーク上を流れる環境下では、データストリームを形成するストリームデータに対するリアルタイム処理を行うため、ストリームデータを送受信する様々なエンティティ間におけるデータ伝送時間の短縮化が求められている。エンティティは、例えば、ネットワークに接続された様々な通信機器(端末装置,中継装置)である。また、データストリームは、通信機器内に搭載されたプロセッサ,LSI(Large Scale Integrated Circuit),FPGA(Field Programmable Gate Array)の
ような様々なストリームデータに対する処理を行う電子回路チップ間を流れる。電子回路チップもエンティティの1つであり、エンティティ間の通信は、通信機器間の通信だけでなく、通信機器内部の電子回路チップ間の通信(いわゆる内部通信)を含む。

近年では、ストリームデータ量が増大する傾向にある。或る量のストリームデータを送信側から受信側へ効率的に伝送する手法として、エンティティ間を結ぶ伝送路の周波数を上げる(伝送帯域を広げる)ことや、エンティティ間を複数の伝送路で結び、ストリームデータを並列に送信することが考えられる。しかしながら、これらの手法は、物理的、周波数的な限界がいずれ来ると考えられている。

そこで、送信側装置でストリームデータの圧縮を行う技術が提案されている。すなわち、送信データ量の減少に伴うデータ伝送時間の短縮化を以て、データ伝送の効率化を図る。例えば、連続する2以上のシンボルが登録されている場合、2以上のシンボルを1つのシンボルに変換する変換部と、変換部で2以上のシンボルが1つのシンボルに変換された場合は、当該1つのシンボルを出力し、そうでない場合は、2以上のシンボルを出力する出力部とを含むデータ圧縮器が提案されている(例えば、特許文献1)。このようにすれば、一定時間内の処理遅延で圧縮及び解凍処理を行うことができる。

また、入力データをブロック単位で集計処理して符号化対象データ毎の発生度数を計数し、発生度数が0の符号化対象データが存在する場合に1以上の整数を一様に加算し、あるブロックにおける発生度数に基づいて作成した適応ハフマン符号表に基づき、次のブロックに対して可変長符号化を実行するという技術も提案されている(例えば、特許文献2)。

Field of industrial application (In Japanese)

本発明は、データ圧縮・解凍システム、データ圧縮方法及びデータ解凍方法、並びにデータ圧縮器及びデータ解凍器に関する。

Scope of claims (In Japanese)
【請求項1】
 
固定長のデータであるシンボル単位でデータ列を圧縮し、圧縮されたデータ列を受信側の装置へ送信する送信側の装置と、前記圧縮されたデータ列を受信し解凍する前記受信側の装置とを備えるデータ圧縮・解凍システムであって、
前記送信側の装置が、
変換前に係る2以上のシンボルと変換後に係る1つのシンボルとの対応付けを示すエントリが登録される変換テーブルを検索し、前記データ列において連続する2以上のシンボルが、変換前に係る2以上のシンボルとして登録されていないと判断された場合、前記連続する2以上のシンボルを変換前に係る2以上のシンボルとするエントリを前記変換テーブルに登録すると共に、前記連続する2以上のシンボルを変換せずに出力し、
前記データ列において連続する2以上のシンボルが、変換前に係る2以上のシンボルとして前記変換テーブルのエントリに登録されている場合、当該エントリにおいて対応付けられている変換後に係る1つのシンボルに、前記連続する2以上のシンボルを変換して出力し、
前記受信側の装置が、
解凍前に係るシンボルと解凍後に係る2以上のシンボルとの対応付けを示すエントリが登録される変換テーブルを検索し、前記データ列に含まれるシンボルが、解凍前に係るシンボルとして登録されていないと判断された場合、前記データ列に含まれるシンボル及び後続の所定数のシンボルを解凍後に係る2つ以上のシンボルとするエントリを前記変換テーブルに登録すると共に、前記データ列に含まれるシンボル及び後続する所定数のシンボルを変換せずに出力し、
前記データ列に含まれるシンボルが、解凍前に係るシンボルとして前記変換テーブルのエントリに登録されている場合、当該エントリにおいて対応付けられている解凍後に係る2以上のシンボルに、当該前記データ列に含まれるシンボルを変換して出力し、
前記送信側の装置及び前記受信側の装置は、
前記変換テーブルの空き領域にエントリを登録する際、エントリの格納を開始する位置と、以降のエントリを格納する位置を決定するための規則とに基づいて決定された位置にエントリを登録し、
前記変換テーブルからエントリを削除する際、登録されているエントリを削除するか否か初めに判断する対象となるエントリの登録位置と、以降にエントリを削除するか否か判断する対象となるエントリの登録位置を決定するための規則とに基づいて候補の位置を決定する
データ圧縮・解凍システム。

【請求項2】
 
コンピュータが、固定長のデータであるシンボル単位でデータ列を処理し、当該データ列を圧縮するデータ圧縮方法であって、
変換前に係る2以上のシンボルと変換後に係る1つのシンボルとの対応付けを示すエントリが登録される変換テーブルを検索し、前記データ列において連続する2以上のシンボルが、変換前に係る2以上のシンボルとして登録されていないと判断された場合、前記連続する2以上のシンボルを変換前に係る2以上のシンボルとするエントリを前記変換テーブルに登録すると共に、前記連続する2以上のシンボルを変換せずに出力し、
前記データ列において連続する2以上のシンボルが、変換前に係る2以上のシンボルとして前記変換テーブルのエントリに登録されている場合、当該エントリにおいて対応付けられている変換後に係る1つのシンボルに、前記連続する2以上のシンボルを変換して出力し、
前記変換テーブルの空き領域にエントリを登録する際、エントリの格納を開始する位置と、以降のエントリを格納する位置を決定するための規則とに基づいて決定された位置にエントリを登録し、
前記変換テーブルからエントリを削除する際、登録されているエントリを削除するか否か初めに判断する対象となるエントリの登録位置と、以降にエントリを削除するか否か判断する対象となるエントリの登録位置を決定するための規則とに基づいて候補の位置を決定する
データ圧縮方法。

【請求項3】
 
前記変換テーブルのエントリごとに、当該エントリが示す変換前に係る2以上のシンボルの、前記データ列における出現回数に応じた値を計数し、
計数された前記出現回数に応じた値が小さいエントリを優先して、前記変換テーブルに登録されたエントリを削除する、
請求項2に記載のデータ圧縮方法。

【請求項4】
 
前記候補の位置に登録されているエントリに対応付けられている、前記出現回数に応じた値が所定の閾値以下である場合に、当該エントリを削除する
請求項3に記載のデータ圧縮方法。

【請求項5】
 
請求項2から4のいずれか一項に記載のデータ圧縮方法を繰り返し実施し、
前段のデータ圧縮方法によって出力されたデータを入力として、後段のデータ圧縮方法を実施する
データ圧縮方法。

【請求項6】
 
変換せずに出力された少なくとも一部の前記シンボル、又は変換して出力された前記シンボルを暗号化する
請求項2から5のいずれか一項に記載のデータ圧縮方法。

【請求項7】
 
コンピュータが、通信相手の装置から受信するデータ列を、固定長のデータであるシンボル単位で処理し、当該データ列を解凍するデータ解凍方法であって、
解凍前に係るシンボルと解凍後に係る2以上のシンボルとの対応付けを示すエントリが登録される変換テーブルを検索し、前記データ列に含まれるシンボルが、解凍前に係るシンボルとして登録されていないと判断された場合、前記データ列に含まれるシンボル及び
後続の所定数のシンボルを解凍後に係る2つ以上のシンボルとするエントリを前記変換テーブルに登録すると共に、前記データ列に含まれるシンボル及び後続する所定数のシンボルを変換せずに出力し、
前記データ列に含まれるシンボルが、解凍前に係るシンボルとして前記変換テーブルのエントリに登録されている場合、当該エントリにおいて対応付けられている解凍後に係る2以上のシンボルに、当該前記データ列に含まれるシンボルを変換して出力し、
前記変換テーブルの空き領域にエントリを登録する際、エントリの格納を開始する位置と、以降のエントリを格納する位置を決定するための規則とに基づいて決定された位置にエントリを登録し、
前記変換テーブルからエントリを削除する際、登録されているエントリを削除するか否か初めに判断する対象となるエントリの登録位置と、以降にエントリを削除するか否か判断する対象となるエントリの登録位置を決定するための規則とに基づいて候補の位置を決定する
データ解凍方法。

【請求項8】
 
前記通信相手の装置から設定の初期化の指示を受信した場合、前記変換テーブルに予め登録しておくエントリ、前記変換テーブルの空き領域のうちエントリを格納する開始位置、又は前記変換テーブルの領域のうち当該領域のエントリを削除するか否か判断する開始位置を初期化する
請求項7に記載のデータ解凍方法。

【請求項9】
 
固定長のデータであるシンボル単位でデータ列を処理し、当該データ列を圧縮するデータ圧縮器であって、
変換前に係る2以上のシンボルと変換後に係る1つのシンボルとの対応付けを示すエントリが登録される変換テーブルと、
前記変換テーブルに基づいてデータ列に含まれるシンボルの変換を制御する制御回路と、
を含み、
前記制御回路は、
前記データ列において連続する2以上のシンボルが、変換前に係る2以上のシンボルとして登録されていないと判断された場合、前記連続する2以上のシンボルを変換前に係る2以上のシンボルとするエントリを前記変換テーブルに登録すると共に、前記連続する2以上のシンボルを変換せずに出力し、
前記データ列において連続する2以上のシンボルが、変換前に係る2以上のシンボルとして前記変換テーブルのエントリに登録されている場合、当該エントリにおいて対応付けられている変換後に係る1つのシンボルに、前記連続する2以上のシンボルを変換して出力し、
前記変換テーブルの空き領域にエントリを登録する際、エントリの格納を開始する位置と、以降のエントリを格納する位置を決定するための規則とに基づいて決定された位置にエントリを登録し、
前記変換テーブルからエントリを削除する際、登録されているエントリを削除するか否か初めに判断する対象となるエントリの登録位置と、以降にエントリを削除するか否か判断する対象となるエントリの登録位置を決定するための規則とに基づいて候補の位置を決定する
データ圧縮器。

【請求項10】
 
固定長のデータであるシンボル単位でデータ列を処理し、当該データ列を解凍するデータ解凍器であって、
解凍前に係るシンボルと解凍後に係る2以上のシンボルとの対応付けを示すエントリが登録される変換テーブルと、
前記変換テーブルに基づいてデータ列に含まれるシンボルの変換を制御する制御回路と、
を含み、
前記制御回路は、
前記データ列に含まれるシンボルが、解凍前に係るシンボルとして登録されていないと判断された場合、前記データ列に含まれるシンボル及び後続の所定数のシンボルを解凍後に係る2つ以上のシンボルとするエントリを前記変換テーブルに登録すると共に、前記データ列に含まれるシンボル及び後続する所定数のシンボルを変換せずに出力し、
前記データ列に含まれるシンボルが、解凍前に係るシンボルとして前記変換テーブルのエントリに登録されている場合、当該エントリにおいて対応付けられている解凍後に係る2以上のシンボルに、当該前記データ列に含まれるシンボルを変換して出力し、
前記変換テーブルの空き領域にエントリを登録する際、エントリの格納を開始する位置と、以降のエントリを格納する位置を決定するための規則とに基づいて決定された位置にエントリを登録し、
前記変換テーブルからエントリを削除する際、登録されているエントリを削除するか否か初めに判断する対象となるエントリの登録位置と、以降にエントリを削除するか否か判断する対象となるエントリの登録位置を決定するための規則とに基づいて候補の位置を決定する
データ解凍器。
IPC(International Patent Classification)
F-term
Drawing

※Click image to enlarge.

JP2015063449thum.jpg
State of application right Registered
Please contact us by E-mail or facsimile if you have any interests on this patent.


PAGE TOP

close
close
close
close
close
close
close