JPH11110187A - データ圧縮装置 - Google Patents
データ圧縮装置Info
- Publication number
- JPH11110187A JPH11110187A JP9264457A JP26445797A JPH11110187A JP H11110187 A JPH11110187 A JP H11110187A JP 9264457 A JP9264457 A JP 9264457A JP 26445797 A JP26445797 A JP 26445797A JP H11110187 A JPH11110187 A JP H11110187A
- Authority
- JP
- Japan
- Prior art keywords
- dictionary
- data
- node
- link information
- information
- 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.)
- Granted
Links
Landscapes
- Document Processing Apparatus (AREA)
- Compression, Expansion, Code Conversion, And Decoders (AREA)
Abstract
(57)【要約】
【課題】 データ圧縮のための辞書の検索を記憶容量の
増大を抑えてかつ高速化させる。 【解決手段】 辞書のツリー構造４０では、自分４１に
対し従来からの親４２を示す親へのリンク４３に、弟へ
のリンク４５および長男へのリンク４７を付加する。
（ｂ）に示すように、付加情報によってデータ量は増え
るけれども、２倍までは増大せず、リンク情報の付加に
よるデータ圧縮処理の高速化を図ることができる。
増大を抑えてかつ高速化させる。 【解決手段】 辞書のツリー構造４０では、自分４１に
対し従来からの親４２を示す親へのリンク４３に、弟へ
のリンク４５および長男へのリンク４７を付加する。
（ｂ）に示すように、付加情報によってデータ量は増え
るけれども、２倍までは増大せず、リンク情報の付加に
よるデータ圧縮処理の高速化を図ることができる。
Description
【０００１】
【発明の属する技術分野】本発明は、連続するデータを
圧縮するデータ圧縮装置、特にデータ通信などのため
に、リアルタイムで文字列データなどを圧縮伸長するシ
ステムのためのデータ圧縮装置に関する。
圧縮するデータ圧縮装置、特にデータ通信などのため
に、リアルタイムで文字列データなどを圧縮伸長するシ
ステムのためのデータ圧縮装置に関する。
【０００２】
【従来の技術】従来から、データ通信の分野では、ＣＣ
ＩＴＴと略称される国際電信電話諮問委員会からのＶシ
リーズ勧告に基づくデータ回線終端装置（ＤＣＥ）がモ
デムとして用いられている。図５は、ＣＣＩＴＴ勧告
Ｖ．４２ｂｉｓに基づくデータ圧縮機能とエラー訂正制
御機能とを有するデータ回線終端装置１の概略的な構成
を示す。データ回線終端端装置１は、ワークステーショ
ンやパーソナルコンピュータなどのデータ終端装置２
と、公衆電話網３との間に設けられる。ＤＴＥと略称さ
れるデータ終端装置２との接続は、相互接続回路４を介
して行われる。公衆電話網３との間の信号の変換は、信
号変換部５によって行われる。エラー訂正およびデータ
圧縮は、制御部６によって制御されるエラー訂正部７お
よびデータ圧縮部８によってそれぞれ行われる。
ＩＴＴと略称される国際電信電話諮問委員会からのＶシ
リーズ勧告に基づくデータ回線終端装置（ＤＣＥ）がモ
デムとして用いられている。図５は、ＣＣＩＴＴ勧告
Ｖ．４２ｂｉｓに基づくデータ圧縮機能とエラー訂正制
御機能とを有するデータ回線終端装置１の概略的な構成
を示す。データ回線終端端装置１は、ワークステーショ
ンやパーソナルコンピュータなどのデータ終端装置２
と、公衆電話網３との間に設けられる。ＤＴＥと略称さ
れるデータ終端装置２との接続は、相互接続回路４を介
して行われる。公衆電話網３との間の信号の変換は、信
号変換部５によって行われる。エラー訂正およびデータ
圧縮は、制御部６によって制御されるエラー訂正部７お
よびデータ圧縮部８によってそれぞれ行われる。
【０００３】データ圧縮部８は、辞書９を有し、文字列
の符号化による圧縮と、符号化されたデータの復号によ
る伸長とを行う。
の符号化による圧縮と、符号化されたデータの復号によ
る伸長とを行う。
【０００４】図６は、辞書９のデータ構造を示す。辞書
９はツリー構造１０によって表現される。このツリー構
造１０は、複数の節点を有し、アルファベットＡ，Ｂ，
Ｃ，Ｄ，…に対応するルート節点１１ａ，１１ｂ，１１
ｃ，１１ｄ，…が最上位となって、複数の節点が連なっ
て文字列を表現する。図６は、「Ａ」、「Ｂ」、「Ｂ
Ａ」、「ＢＡＧ」、「ＢＡＲ」、「ＢＡＴ」、「Ｂ
Ｉ」、「ＢＩＮ」、「Ｃ」、「Ｄ」、「ＤＥ」、「Ｄ
Ｏ」および「ＤＯＧ」の各文字列を表現している状態を
示す。節点１２ｂａ，１２ｂｉ，１２ｄｏは、ツリー構
造１０の途中にあり、文字列の最後の文字を示すリーフ
節点１２ｄｅ，１３ｂａｇ，１３ｂａｒ，１３ｂａｔ，
１３ｂｉｎ，１３ｄｏｇは中間の節点１２ｂａ，１２ｂ
ｉ，１２ｄｏよりも下位レベルの階層にある。各節点に
は、節点を識別するための符号語が割当てられる。この
ツリー構造１０の辞書９の内容は、公衆電話網３を介し
てデータ通信を行う相手側の辞書９における符号語の割
当てと一致させる。
９はツリー構造１０によって表現される。このツリー構
造１０は、複数の節点を有し、アルファベットＡ，Ｂ，
Ｃ，Ｄ，…に対応するルート節点１１ａ，１１ｂ，１１
ｃ，１１ｄ，…が最上位となって、複数の節点が連なっ
て文字列を表現する。図６は、「Ａ」、「Ｂ」、「Ｂ
Ａ」、「ＢＡＧ」、「ＢＡＲ」、「ＢＡＴ」、「Ｂ
Ｉ」、「ＢＩＮ」、「Ｃ」、「Ｄ」、「ＤＥ」、「Ｄ
Ｏ」および「ＤＯＧ」の各文字列を表現している状態を
示す。節点１２ｂａ，１２ｂｉ，１２ｄｏは、ツリー構
造１０の途中にあり、文字列の最後の文字を示すリーフ
節点１２ｄｅ，１３ｂａｇ，１３ｂａｒ，１３ｂａｔ，
１３ｂｉｎ，１３ｄｏｇは中間の節点１２ｂａ，１２ｂ
ｉ，１２ｄｏよりも下位レベルの階層にある。各節点に
は、節点を識別するための符号語が割当てられる。この
ツリー構造１０の辞書９の内容は、公衆電話網３を介し
てデータ通信を行う相手側の辞書９における符号語の割
当てと一致させる。
【０００５】図６（ｂ）に示すように、一般に、ツリー
構造１０の途中にある節点１４に対しては、１つの親１
５と１または複数の子１６が存在する。図６（ａ）に示
すルート節点１１ａ〜１１ｄに対しては親は存在しな
い。またルート節点１１ａ，１１ｃは子も存在せず、独
立した節点となっている。したがって、図６（ｂ）に示
すツリー構造１０上の各節点１４では、自己に対応する
符号語と、自己に対応する文字と、親１５の符号語と、
子供１６の有無を示す情報とを備えている必要がある。
構造１０の途中にある節点１４に対しては、１つの親１
５と１または複数の子１６が存在する。図６（ａ）に示
すルート節点１１ａ〜１１ｄに対しては親は存在しな
い。またルート節点１１ａ，１１ｃは子も存在せず、独
立した節点となっている。したがって、図６（ｂ）に示
すツリー構造１０上の各節点１４では、自己に対応する
符号語と、自己に対応する文字と、親１５の符号語と、
子供１６の有無を示す情報とを備えている必要がある。
【０００６】図７は、ＣＣＩＴＴ勧告Ｖ．４２ｂｉｓに
従って文字列検索を行って圧縮する手順を示す。ステッ
プａ０から手順を開始し、ステップａ１では文字列の最
初の文字に対応するルート節点の情報を獲得する。ステ
ップａ２では対象とする節点に対し、子供となる節点が
存在しているか否かを判断する。子供が存在していると
判定されれば、ツリー構造１０でこの節点から次の符号
語の情報を獲得する。ステップａ４では、獲得された次
の符号語の情報のうち、文字が一致するか否かを判断す
る。文字が一致するときには、ステップａ２に戻り、さ
らに子供の有無を判断する。ステップａ４で文字が一致
しないときには、ステップａ５で子供となる節点につい
ての辞書の範囲を一周しているか否かを判断する。一周
していないと判断されるときには、ステップａ３に戻
り、次の子供の符号語の情報を獲得する。ステップａ５
で辞書を一周して、文字が一致する子供の符号語がない
と判断されるときには、ステップａ６で、一致しない文
字を辞書に追加する処理を行う。ステップａ２で子供が
いないと判断されるときには、ステップａ８で文字の辞
書への追加を行う。ステップａ６またはステップａ７の
辞書への追加が終了すると、ステップａ８で文字列が一
致した範囲の符号語の出力を行い、ステップａ９で手順
を終了する。
従って文字列検索を行って圧縮する手順を示す。ステッ
プａ０から手順を開始し、ステップａ１では文字列の最
初の文字に対応するルート節点の情報を獲得する。ステ
ップａ２では対象とする節点に対し、子供となる節点が
存在しているか否かを判断する。子供が存在していると
判定されれば、ツリー構造１０でこの節点から次の符号
語の情報を獲得する。ステップａ４では、獲得された次
の符号語の情報のうち、文字が一致するか否かを判断す
る。文字が一致するときには、ステップａ２に戻り、さ
らに子供の有無を判断する。ステップａ４で文字が一致
しないときには、ステップａ５で子供となる節点につい
ての辞書の範囲を一周しているか否かを判断する。一周
していないと判断されるときには、ステップａ３に戻
り、次の子供の符号語の情報を獲得する。ステップａ５
で辞書を一周して、文字が一致する子供の符号語がない
と判断されるときには、ステップａ６で、一致しない文
字を辞書に追加する処理を行う。ステップａ２で子供が
いないと判断されるときには、ステップａ８で文字の辞
書への追加を行う。ステップａ６またはステップａ７の
辞書への追加が終了すると、ステップａ８で文字列が一
致した範囲の符号語の出力を行い、ステップａ９で手順
を終了する。
【０００７】図７の手順に従って、データ通信用の信号
ストリームを圧縮する典型的な先行技術は、たとえば特
公平５−６８８９３に開示されている。また辞書を用い
てデータ圧縮を行う考え方は、特開昭６０−２４１１５
７、特開昭６１−２３２７２４、特開平１−１０２６１
３、特開平２−１４４６６１、特開平３−０３８７７
２、特開平４−１１６６９０、特開平４−１２３６１
９、特開平４−２１７０２１、特開平４−２２３５５
６、特開平４−３４０１５６および特開平７−２３２３
８などにも開示されている。
ストリームを圧縮する典型的な先行技術は、たとえば特
公平５−６８８９３に開示されている。また辞書を用い
てデータ圧縮を行う考え方は、特開昭６０−２４１１５
７、特開昭６１−２３２７２４、特開平１−１０２６１
３、特開平２−１４４６６１、特開平３−０３８７７
２、特開平４−１１６６９０、特開平４−１２３６１
９、特開平４−２１７０２１、特開平４−２２３５５
６、特開平４−３４０１５６および特開平７−２３２３
８などにも開示されている。
【０００８】
【発明が解決しようとする課題】従来からの図６に示す
ようなツリー構造１０の辞書は、各節点の親となる節点
へのリンクでツリー構造１０を表現しているので、文字
列検索時には辞書内に記憶されている符号語を端から端
まで確認する必要があり、時間がかかっている。そのた
めリアルタイム処理を行う場合には、高速な演算装置等
が必要となる。
ようなツリー構造１０の辞書は、各節点の親となる節点
へのリンクでツリー構造１０を表現しているので、文字
列検索時には辞書内に記憶されている符号語を端から端
まで確認する必要があり、時間がかかっている。そのた
めリアルタイム処理を行う場合には、高速な演算装置等
が必要となる。
【０００９】本発明の目的は、ＣＣＩＴＴの勧告Ｖ．４
２ｂｉｓ等の圧縮伸長処理に高速な演算装置等を必要と
せず、辞書構造の変更による記憶容量の増加を可能な限
り抑えることができる辞書構造を有するデータ圧縮装置
を提供することである。
２ｂｉｓ等の圧縮伸長処理に高速な演算装置等を必要と
せず、辞書構造の変更による記憶容量の増加を可能な限
り抑えることができる辞書構造を有するデータ圧縮装置
を提供することである。
【００１０】
【課題を解決するための手段】本発明は、入力されるデ
ータ列の圧縮伸長用に、予め設定される規格に従うツリ
ー構造を有し、最上位レベルの節点から各節点までの経
路に応じて見出しデータが表現され、各節点毎に上位レ
ベルの節点に対するリンク情報と下位レベルの節点の有
無情報とを有する辞書を検索し、見出しデータに一致す
る入力データの部分列の符号化と、見出しデータに一致
しない入力データの辞書への追加とを繰返すデータ圧縮
装置において、辞書の各節点には、複数のレベルの節点
へのリンク情報が付加されており、付加されたリンク情
報も使用して辞書の検索を行う辞書検索手段と、入力デ
ータの辞書への追加の際に、予め定められる範囲の複数
レベルで、節点に対するリンク情報を付加するリンク付
加手段とを含むことを特徴とするデータ圧縮装置であ
る。
ータ列の圧縮伸長用に、予め設定される規格に従うツリ
ー構造を有し、最上位レベルの節点から各節点までの経
路に応じて見出しデータが表現され、各節点毎に上位レ
ベルの節点に対するリンク情報と下位レベルの節点の有
無情報とを有する辞書を検索し、見出しデータに一致す
る入力データの部分列の符号化と、見出しデータに一致
しない入力データの辞書への追加とを繰返すデータ圧縮
装置において、辞書の各節点には、複数のレベルの節点
へのリンク情報が付加されており、付加されたリンク情
報も使用して辞書の検索を行う辞書検索手段と、入力デ
ータの辞書への追加の際に、予め定められる範囲の複数
レベルで、節点に対するリンク情報を付加するリンク付
加手段とを含むことを特徴とするデータ圧縮装置であ
る。
【００１１】本発明に従えば、ツリー構造の辞書の最上
位レベルの節点から各節点までの経路に応じて見出しデ
ータが表現され、入力されるデータ列が見出しデータに
一致する範囲で符号化されてデータ圧縮が行われる。辞
書の各節点には、複数のレベルの節点へのリンク情報が
付加され、辞書検索手段は付加されたリンク情報も使用
して辞書の検索を行うので、データ列が辞書に記憶され
ている見出しデータに一致するか否かの判断を行う際の
検索時間を短縮することができる。リンク付加手段は、
入力データの辞書への追加の際に、予め定められる範囲
の複数レベルで節点に対するリンク情報を付加するの
で、追加されたデータを含む見出しデータの検索でも、
付加されたリンク情報を用いて迅速な検索を行うことが
できる。辞書の検索が高速化されるので、高速な演算装
置等を必要とせずに圧縮伸長処理を高速化することがで
きる。ツリー構造の辞書に対して付加するリンク情報を
少なくすることができるので、辞書の記憶容量の増大を
抑えることができる。
位レベルの節点から各節点までの経路に応じて見出しデ
ータが表現され、入力されるデータ列が見出しデータに
一致する範囲で符号化されてデータ圧縮が行われる。辞
書の各節点には、複数のレベルの節点へのリンク情報が
付加され、辞書検索手段は付加されたリンク情報も使用
して辞書の検索を行うので、データ列が辞書に記憶され
ている見出しデータに一致するか否かの判断を行う際の
検索時間を短縮することができる。リンク付加手段は、
入力データの辞書への追加の際に、予め定められる範囲
の複数レベルで節点に対するリンク情報を付加するの
で、追加されたデータを含む見出しデータの検索でも、
付加されたリンク情報を用いて迅速な検索を行うことが
できる。辞書の検索が高速化されるので、高速な演算装
置等を必要とせずに圧縮伸長処理を高速化することがで
きる。ツリー構造の辞書に対して付加するリンク情報を
少なくすることができるので、辞書の記憶容量の増大を
抑えることができる。
【００１２】また本発明で前記データ列は、データ通信
用の文字列であり、前記予め設定される規格に従って、
前記辞書を用いて文字列を符号化して通信路に送信し、
通信路から受信される信号を辞書を用いて復号化する処
理手段を備えることを特徴とする。
用の文字列であり、前記予め設定される規格に従って、
前記辞書を用いて文字列を符号化して通信路に送信し、
通信路から受信される信号を辞書を用いて復号化する処
理手段を備えることを特徴とする。
【００１３】本発明に従えば、データ通信の際に、文字
列を圧縮伸長するための辞書の検索が高速となり、高速
度の通信速度に対しても辞書を用いる圧縮伸長処理を充
分に対応させることができる。
列を圧縮伸長するための辞書の検索が高速となり、高速
度の通信速度に対しても辞書を用いる圧縮伸長処理を充
分に対応させることができる。
【００１４】また本発明で前記付加されるリンク情報
は、ツリー構造で親となる上位レベルの節点から最初に
追加された下位レベルの子である長男の節点へのリンク
情報と、同一の節点を親として共有する同一レベルの節
点間で、追加された順序が連続し、先行する兄の節点か
ら後続の弟の節点へのリンク情報とであることを特徴と
する。
は、ツリー構造で親となる上位レベルの節点から最初に
追加された下位レベルの子である長男の節点へのリンク
情報と、同一の節点を親として共有する同一レベルの節
点間で、追加された順序が連続し、先行する兄の節点か
ら後続の弟の節点へのリンク情報とであることを特徴と
する。
【００１５】本発明に従えば、親から長男へのリンク情
報と、兄弟間で兄から弟へのリンク情報とが付加される
ので、文字列の検索の際に次の節点を探す時間が短縮さ
れ、迅速な検索を行うことができ、圧縮または伸長に要
する時間の短縮を図ることができる。
報と、兄弟間で兄から弟へのリンク情報とが付加される
ので、文字列の検索の際に次の節点を探す時間が短縮さ
れ、迅速な検索を行うことができ、圧縮または伸長に要
する時間の短縮を図ることができる。
【００１６】また本発明で前記予め設定される規格は、
国際電信電話諮問委員会の勧告Ｖ．４２ｂｉｓであるこ
とを特徴とする。
国際電信電話諮問委員会の勧告Ｖ．４２ｂｉｓであるこ
とを特徴とする。
【００１７】本発明に従えば、国際電信電話諮問委員会
の勧告Ｖ．４２ｂｉｓに基づくデータ圧縮を、辞書の検
索時間を短縮して高速化することができる。
の勧告Ｖ．４２ｂｉｓに基づくデータ圧縮を、辞書の検
索時間を短縮して高速化することができる。
【００１８】
【発明の実施の形態】図１は、本発明の実施の一形態と
してのデータ回線終端装置２１の概略的な電気的構成を
示す。データ回線終端装置２１は、ＤＣＥとして、ＤＴ
Ｅであるデータ終端装置２２と公衆電話網２３との間に
設けられる。データ終端装置２２は、パーソナルコンピ
ュータやＰＥＤと称される各種形態情報端末装置などで
ある。公衆電話網２３は、公衆電話回線やＩＳＤＮ、あ
るいはＰＨＳなどの無線公衆電話網である。
してのデータ回線終端装置２１の概略的な電気的構成を
示す。データ回線終端装置２１は、ＤＣＥとして、ＤＴ
Ｅであるデータ終端装置２２と公衆電話網２３との間に
設けられる。データ終端装置２２は、パーソナルコンピ
ュータやＰＥＤと称される各種形態情報端末装置などで
ある。公衆電話網２３は、公衆電話回線やＩＳＤＮ、あ
るいはＰＨＳなどの無線公衆電話網である。
【００１９】データ回線終端装置２１には、データ終端
装置２２との間に相互接続回路２４、公衆電話網２３と
の間に信号変換部２５、内部の制御用に制御部２６、エ
ラー訂正用にエラー訂正部２７、およびデータの圧縮伸
長用にデータ圧縮部２８を含む。データ圧縮部２８は、
ツリー構造の辞書２９、辞書検索手段３０およびリンク
付加手段３１を含む。
装置２２との間に相互接続回路２４、公衆電話網２３と
の間に信号変換部２５、内部の制御用に制御部２６、エ
ラー訂正用にエラー訂正部２７、およびデータの圧縮伸
長用にデータ圧縮部２８を含む。データ圧縮部２８は、
ツリー構造の辞書２９、辞書検索手段３０およびリンク
付加手段３１を含む。
【００２０】図２は、図１の辞書２９の基本的なツリー
構造４０を示す。図２（ａ）は、ツリー構造４０の表現
例を示し、図２（ｂ）は各節点に対応して記憶されてい
る符号語情報の内容を示す。ツリー構造４０の途中の節
点が自分４１である場合を想定すると、ツリー構造４０
の上位側のレベルに親４２となる節点が存在する。自分
４１から親４２へは、親へのリンク４３でさかのぼるこ
とができる。同一の親４２からは、自分４１および弟４
４を含む複数の子が分岐し得る。親４２に対する複数の
子は、辞書に追加された順に従って兄弟の関係を有し、
自分４１に対して弟４１が存在するときには、弟へのリ
ンク４５で参照可能である。自分４１が、リーフ節点で
ないときには、１または複数個の子となる節点が存在す
る。そのうち最初に追加される節点は、長男４６であ
り、次男以降の子供４８が存在することもある。次男以
降の子供４８が存在するときには、長男４６には弟への
リンクが設けられるので、自分４１からは長男４６への
リンクである長男へのリンク４７を記憶しておくだけ
で、複数の長男４６および子供４８を順に示すことがで
きる。
構造４０を示す。図２（ａ）は、ツリー構造４０の表現
例を示し、図２（ｂ）は各節点に対応して記憶されてい
る符号語情報の内容を示す。ツリー構造４０の途中の節
点が自分４１である場合を想定すると、ツリー構造４０
の上位側のレベルに親４２となる節点が存在する。自分
４１から親４２へは、親へのリンク４３でさかのぼるこ
とができる。同一の親４２からは、自分４１および弟４
４を含む複数の子が分岐し得る。親４２に対する複数の
子は、辞書に追加された順に従って兄弟の関係を有し、
自分４１に対して弟４１が存在するときには、弟へのリ
ンク４５で参照可能である。自分４１が、リーフ節点で
ないときには、１または複数個の子となる節点が存在す
る。そのうち最初に追加される節点は、長男４６であ
り、次男以降の子供４８が存在することもある。次男以
降の子供４８が存在するときには、長男４６には弟への
リンクが設けられるので、自分４１からは長男４６への
リンクである長男へのリンク４７を記憶しておくだけ
で、複数の長男４６および子供４８を順に示すことがで
きる。
【００２１】図２（ｂ）は、各節点に記憶されている符
号語情報の内容の例を示す。図２（ａ）に示す自分４１
についての符号語情報の場合、先頭１２ビットは自分４
１に対応する符号語４１ａであり、次の８ビットは自分
４１に対応する文字４１ｂであり、次の１２ビットは親
４２の符号語４２ａであり、次の１ビットで長男４６あ
るいは子供４８など、子供がいるか否かを示すフラグ４
１ｃとなる。符号語４１ａ、文字４１ｂ、親の符号語４
２ａおよび子供がいるか否かのフラグ４１ｃは、従来か
らＶ．４２ｂｉｓ用の辞書には記憶されている。本実施
形態のツリー構造４０に対応する辞書では、網かけを施
して示す次の１２ビットの長男の符号語４６ａ、１ビッ
トの弟がいるか否かを示すフラグ４１ｄ、および１２ビ
ットの弟の符号語４４ａを付加する。この結果、従来は
３３ビットであった符号語情報が、２５ビット付加さ
れ、５８ビットに増大する。しかしながら、辞書２９に
記憶する容量の増加は２倍には達していない。
号語情報の内容の例を示す。図２（ａ）に示す自分４１
についての符号語情報の場合、先頭１２ビットは自分４
１に対応する符号語４１ａであり、次の８ビットは自分
４１に対応する文字４１ｂであり、次の１２ビットは親
４２の符号語４２ａであり、次の１ビットで長男４６あ
るいは子供４８など、子供がいるか否かを示すフラグ４
１ｃとなる。符号語４１ａ、文字４１ｂ、親の符号語４
２ａおよび子供がいるか否かのフラグ４１ｃは、従来か
らＶ．４２ｂｉｓ用の辞書には記憶されている。本実施
形態のツリー構造４０に対応する辞書では、網かけを施
して示す次の１２ビットの長男の符号語４６ａ、１ビッ
トの弟がいるか否かを示すフラグ４１ｄ、および１２ビ
ットの弟の符号語４４ａを付加する。この結果、従来は
３３ビットであった符号語情報が、２５ビット付加さ
れ、５８ビットに増大する。しかしながら、辞書２９に
記憶する容量の増加は２倍には達していない。
【００２２】図３は、図５と同様な文字列に対応する辞
書２９のツリー構造５０を示す。図３（ａ）は、ツリー
構造５０による表現例を示し、図３（ｂ）は各節点に記
憶されている符号語情報の内容例を示す。図３（ｂ）
で、本発明による付加情報の部分は、網かけを施して示
す。
書２９のツリー構造５０を示す。図３（ａ）は、ツリー
構造５０による表現例を示し、図３（ｂ）は各節点に記
憶されている符号語情報の内容例を示す。図３（ｂ）
で、本発明による付加情報の部分は、網かけを施して示
す。
【００２３】図３（ａ）に示すツリー構造５０では、ル
ート節点５１ａ，５１ｂ，５１ｃ，５１ｄでアルファベ
ットのＡ，Ｂ，Ｃ，Ｄに対応させ、途中の節点５２ｂ
ａ，５２ｂｉ，５２ｄｏからリーフ節点５２ｄｅ，５３
ｂａｇ，５３ｂａｒ，５３ｂａｔ，５３ｂｉｎ，５３ｄ
ｏｇに対し、従来からの親へのリンク４３に加えて、弟
へのリンク４５および長男へのリンク４７を付加してい
る。
ート節点５１ａ，５１ｂ，５１ｃ，５１ｄでアルファベ
ットのＡ，Ｂ，Ｃ，Ｄに対応させ、途中の節点５２ｂ
ａ，５２ｂｉ，５２ｄｏからリーフ節点５２ｄｅ，５３
ｂａｇ，５３ｂａｒ，５３ｂａｔ，５３ｂｉｎ，５３ｄ
ｏｇに対し、従来からの親へのリンク４３に加えて、弟
へのリンク４５および長男へのリンク４７を付加してい
る。
【００２４】図４は、図３に示すようなツリー構造５０
の辞書で文字列検索を行ってデータ圧縮を行う手順を示
す。ステップｂ０から手順を開始し、ステップｂ１で文
字列の最初の文字に対応するルート節点５１ａ〜５１ｄ
の情報を獲得する。ステップｂ２では、図２（ｂ）の子
供がいるか否かのフラグ４１ｃに従って、子供の有無を
判断する。子供がいると判断されるときには、長男の符
号語４６ａを長男へのリンク４７として用いて、長男の
情報を獲得する。ステップｂ４では、長男の節点につい
ての文字４１ｂが、入力された文字列で検索の対象とな
っている文字と一致しているか否かを判断する。一致し
ていないと判断されるときには、ステップｂ５で長男の
節点に対して弟となる節点がいるか否かのフラグ４１ｄ
を参照し、弟がいればステップｂ６で次の弟の情報を獲
得する。ステップｂ５で弟がいないと判断されるときに
は、ステップｂ７で一致しない文字を辞書に追加する処
理を行う。ステップｂ５で子供がいないと判断されると
きには、ステップｂ８で最後の文字についての辞書への
追加を行う。この追加の際に、リンク付加手段３１は、
新たな節点に文字を割当て、その節点の直前の兄となる
節点に対応する節点の符号語情報に対し、弟がいるか否
かのフラグ４１ｄと弟の符号語４８ａとを変更する。
の辞書で文字列検索を行ってデータ圧縮を行う手順を示
す。ステップｂ０から手順を開始し、ステップｂ１で文
字列の最初の文字に対応するルート節点５１ａ〜５１ｄ
の情報を獲得する。ステップｂ２では、図２（ｂ）の子
供がいるか否かのフラグ４１ｃに従って、子供の有無を
判断する。子供がいると判断されるときには、長男の符
号語４６ａを長男へのリンク４７として用いて、長男の
情報を獲得する。ステップｂ４では、長男の節点につい
ての文字４１ｂが、入力された文字列で検索の対象とな
っている文字と一致しているか否かを判断する。一致し
ていないと判断されるときには、ステップｂ５で長男の
節点に対して弟となる節点がいるか否かのフラグ４１ｄ
を参照し、弟がいればステップｂ６で次の弟の情報を獲
得する。ステップｂ５で弟がいないと判断されるときに
は、ステップｂ７で一致しない文字を辞書に追加する処
理を行う。ステップｂ５で子供がいないと判断されると
きには、ステップｂ８で最後の文字についての辞書への
追加を行う。この追加の際に、リンク付加手段３１は、
新たな節点に文字を割当て、その節点の直前の兄となる
節点に対応する節点の符号語情報に対し、弟がいるか否
かのフラグ４１ｄと弟の符号語４８ａとを変更する。
【００２５】ステップｂ８の辞書追加では、新たに長男
となる節点を追加し、長男の符号語４６ａを設定すると
ともに、子供がいるか否かのフラグ４１ｃを変更する。
ステップｂ７またはステップｂ８が終了すると、ステッ
プｂ９で辞書と一致する範囲の文字列に対応して符号語
を出力し、ステップｂ１０で手順を終了する。
となる節点を追加し、長男の符号語４６ａを設定すると
ともに、子供がいるか否かのフラグ４１ｃを変更する。
ステップｂ７またはステップｂ８が終了すると、ステッ
プｂ９で辞書と一致する範囲の文字列に対応して符号語
を出力し、ステップｂ１０で手順を終了する。
【００２６】以下具体的に、図４の手順で「ＢＩＮ」と
いう文字列を検索する状態を示す。ステップｂ１では図
３（ａ）のルート節点５１ｂから、「Ｂ」の情報を獲得
する。ＣＣＩＴＴの勧告Ｖ．４２ｂｉｓから、ルート節
点「Ｂ」は符号語「０４５」であることが分かるので、
図３（ｂ）から符号語「０４５」の情報を獲得する。図
４のステップｂ２では、ルート節点「０４５」に子供が
いるか否かを確認する。図３（ｂ）では符号語「０４
５」に対する子供がいるか否かのフラグが○印になって
いるので、子供がいることが確認される。ステップｂ３
では、長男に対応する符号語として「符号語２」が検索
文字の２番目の文字である「Ｉ」と一致しているか否か
確認される。この場合長男の文字は、「Ａ」であるの
で、検索文字の２文字目「Ｉ」とは一致していないこと
が確認される。ステップｂ５では、弟がいるか否かのフ
ラグを確認する。図３（ｂ）では○印となっているの
で、弟がいることが確認される。ステップｂ６では、
「符号語２」の弟の情報から「符号語８」の情報を獲得
する。次にステップｂ４に戻り、「符号語８」が検索文
字の２文字目「Ｉ」と一致していることを確認する。さ
らにステップｂ２に戻り、「符号語８」に子供がいるか
を確認する。図３（ｂ）では○印であるので子供がいる
ことを確認する。ステップｂ３で、「符号語８」の長男
の情報を、「符号語６」として獲得する。ステップｂ４
では、「符号語６」が検索文字の３文字目「Ｎ」と一致
していることを確認し、文字列「ＢＩＮ」の検索を終了
する。したがって文字列「ＢＩＮ」の符号語は「符号語
６」となる。
いう文字列を検索する状態を示す。ステップｂ１では図
３（ａ）のルート節点５１ｂから、「Ｂ」の情報を獲得
する。ＣＣＩＴＴの勧告Ｖ．４２ｂｉｓから、ルート節
点「Ｂ」は符号語「０４５」であることが分かるので、
図３（ｂ）から符号語「０４５」の情報を獲得する。図
４のステップｂ２では、ルート節点「０４５」に子供が
いるか否かを確認する。図３（ｂ）では符号語「０４
５」に対する子供がいるか否かのフラグが○印になって
いるので、子供がいることが確認される。ステップｂ３
では、長男に対応する符号語として「符号語２」が検索
文字の２番目の文字である「Ｉ」と一致しているか否か
確認される。この場合長男の文字は、「Ａ」であるの
で、検索文字の２文字目「Ｉ」とは一致していないこと
が確認される。ステップｂ５では、弟がいるか否かのフ
ラグを確認する。図３（ｂ）では○印となっているの
で、弟がいることが確認される。ステップｂ６では、
「符号語２」の弟の情報から「符号語８」の情報を獲得
する。次にステップｂ４に戻り、「符号語８」が検索文
字の２文字目「Ｉ」と一致していることを確認する。さ
らにステップｂ２に戻り、「符号語８」に子供がいるか
を確認する。図３（ｂ）では○印であるので子供がいる
ことを確認する。ステップｂ３で、「符号語８」の長男
の情報を、「符号語６」として獲得する。ステップｂ４
では、「符号語６」が検索文字の３文字目「Ｎ」と一致
していることを確認し、文字列「ＢＩＮ」の検索を終了
する。したがって文字列「ＢＩＮ」の符号語は「符号語
６」となる。
【００２７】
【発明の効果】以上のように本発明によれば、データ列
の圧縮伸長用の辞書にリンク情報を付加して検索を高速
化することができ、演算装置等の高速化を図る必要がな
いので消費電力の増加を抑えることができる。このた
め、携帯情報端末装置等の電源の負担を軽減し、小形軽
量化を図ることができる。
の圧縮伸長用の辞書にリンク情報を付加して検索を高速
化することができ、演算装置等の高速化を図る必要がな
いので消費電力の増加を抑えることができる。このた
め、携帯情報端末装置等の電源の負担を軽減し、小形軽
量化を図ることができる。
【００２８】また本発明によれば、辞書を用いて文字列
の圧縮伸長を伴って、高い伝送速度でデータ通信を容易
に行うことができる。
の圧縮伸長を伴って、高い伝送速度でデータ通信を容易
に行うことができる。
【００２９】また本発明によれば、親から長男へのリン
ク情報と、兄から弟へのリンク情報とを付加することで
辞書の検索の際の高速化を図るので、辞書の記憶容量の
増加を抑え、携帯情報端末装置等に組込む際の小形化に
対する障害となることを防ぐことができる。
ク情報と、兄から弟へのリンク情報とを付加することで
辞書の検索の際の高速化を図るので、辞書の記憶容量の
増加を抑え、携帯情報端末装置等に組込む際の小形化に
対する障害となることを防ぐことができる。
【００３０】また本発明によれば、国際電信電話諮問委
員会の勧告Ｖ．４２ｂｉｓに従うデータ通信の際の辞書
の検索を迅速に行うことができる。
員会の勧告Ｖ．４２ｂｉｓに従うデータ通信の際の辞書
の検索を迅速に行うことができる。
【図１】本発明の実施の一形態の概略的な電気的構成を
示すブロック図である。
示すブロック図である。
【図２】図１の辞書２９の基本的なツリー構造１０を示
す図および図表である。
す図および図表である。
【図３】図２のツリー構造４０に対し、特定の文字列を
対応させている状態を示すツリー構造５０の図および図
表である。
対応させている状態を示すツリー構造５０の図および図
表である。
【図４】図１の辞書２９を検索してデータ圧縮処理を行
う手順を示すフローチャートである。
う手順を示すフローチャートである。
【図５】従来からのデータ圧縮装置の概略的な電気的構
成を示すブロック図である。
成を示すブロック図である。
【図６】図５に示す辞書９のツリー構造を示す図であ
る。
る。
【図７】図５の辞書９を検索してデータ圧縮を行う手順
を示すフローチャートである。
を示すフローチャートである。
２１ データ回線終端装置 ２２ データ終端装置 ２３ 公衆電話網 ２６ 制御部 ２８ データ圧縮部 ２９ 辞書 ３０ 辞書検索手段 ３１ リンク付加手段 ４０，５０ ツリー構造 ４１ 自分 ４２ 親 ４３ 親へのリンク ４４ 弟 ４５ 弟へのリンク ４６ 長男 ４７ 長男へのリンク ４８ 子供 ５１ａ，５１ｂ，５１ｃ，５１ｄ ルート節点 ５２ｂａ，５２ｂｉ，５２ｄｏ 節点 ５２ｄｅ，５３ｂａｇ，５３ｂａｒ，５３ｂａｔ，５３
ｂｉｎ，５３ｄｏｇリーフ節点
ｂｉｎ，５３ｄｏｇリーフ節点
Claims (4)
- 【請求項１】 入力されるデータ列の圧縮伸長用に、予
め設定される規格に従うツリー構造を有し、最上位レベ
ルの節点から各節点までの経路に応じて見出しデータが
表現され、各節点毎に上位レベルの節点に対するリンク
情報と下位レベルの節点の有無情報とを有する辞書を検
索し、見出しデータに一致する入力データの部分列の符
号化と、見出しデータに一致しない入力データの辞書へ
の追加とを繰返すデータ圧縮装置において、 辞書の各節点には、複数のレベルの節点へのリンク情報
が付加されており、 付加されたリンク情報も使用して辞書の検索を行う辞書
検索手段と、 入力データの辞書への追加の際に、予め定められる範囲
の複数レベルで、節点に対するリンク情報を付加するリ
ンク付加手段とを含むことを特徴とするデータ圧縮装
置。 - 【請求項２】 前記データ列は、データ通信用の文字列
であり、 前記予め設定される規格に従って、前記辞書を用いて文
字列を符号化して通信路に送信し、通信路から受信され
る信号を辞書を用いて復号化する処理手段を備えること
を特徴とする請求項１記載のデータ圧縮装置。 - 【請求項３】 前記付加されるリンク情報は、 ツリー構造で親となる上位レベルの節点から最初に追加
された下位レベルの子である長男の節点へのリンク情報
と、 同一の節点を親として共有する同一レベルの節点間で、
追加された順序が連続し、先行する兄の節点から後続の
弟の節点へのリンク情報とであることを特徴とする請求
項１または２記載のデータ圧縮装置。 - 【請求項４】 前記予め設定される規格は、国際電信電
話諮問委員会の勧告Ｖ．４２ｂｉｓであることを特徴と
する請求項１〜３のいずれかに記載のデータ圧縮装置。
Priority Applications (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| JP26445797A JP3593244B2 (ja) | 1997-09-29 | 1997-09-29 | データ圧縮装置 |
Applications Claiming Priority (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| JP26445797A JP3593244B2 (ja) | 1997-09-29 | 1997-09-29 | データ圧縮装置 |
Publications (2)
| Publication Number | Publication Date |
|---|---|
| JPH11110187A true JPH11110187A (ja) | 1999-04-23 |
| JP3593244B2 JP3593244B2 (ja) | 2004-11-24 |
Family
ID=17403482
Family Applications (1)
| Application Number | Title | Priority Date | Filing Date |
|---|---|---|---|
| JP26445797A Expired - Fee Related JP3593244B2 (ja) | 1997-09-29 | 1997-09-29 | データ圧縮装置 |
Country Status (1)
| Country | Link |
|---|---|
| JP (1) | JP3593244B2 (ja) |
Cited By (2)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| WO2013065199A1 (ja) | 2011-11-04 | 2013-05-10 | 富士通株式会社 | 照合制御プログラム、照合制御装置および照合制御方法 |
| JP2016034158A (ja) * | 2015-12-07 | 2016-03-10 | 富士通株式会社 | 符号処理のためのプログラム及びデータ構造 |
-
1997
- 1997-09-29 JP JP26445797A patent/JP3593244B2/ja not_active Expired - Fee Related
Cited By (3)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| WO2013065199A1 (ja) | 2011-11-04 | 2013-05-10 | 富士通株式会社 | 照合制御プログラム、照合制御装置および照合制御方法 |
| US9355192B2 (en) | 2011-11-04 | 2016-05-31 | Fujitsu Limited | Collation control device, and collation control method |
| JP2016034158A (ja) * | 2015-12-07 | 2016-03-10 | 富士通株式会社 | 符号処理のためのプログラム及びデータ構造 |
Also Published As
| Publication number | Publication date |
|---|---|
| JP3593244B2 (ja) | 2004-11-24 |
Similar Documents
| Publication | Publication Date | Title |
|---|---|---|
| US4814746A (en) | Data compression method | |
| US6563438B2 (en) | Encoding and decoding apparatus with matching length means for symbol strings | |
| US20110283183A1 (en) | Method for compressing/decompressing structured documents | |
| US7043686B1 (en) | Data compression apparatus, database system, data communication system, data compression method, storage medium and program transmission apparatus | |
| JP3278297B2 (ja) | データ圧縮方法及びデータ復元方法並びにデータ圧縮装置及びデータ復元装置 | |
| EP0127815B1 (en) | Data compression method | |
| US6982661B2 (en) | Method of performing huffman decoding | |
| JPH07295867A (ja) | データ送信方法、データ等化方法及び装置 | |
| US5585793A (en) | Order preserving data translation | |
| JPH09232968A (ja) | 可変長符号生成装置 | |
| EP0138080A2 (en) | Communication system using variable length character code and coding method | |
| US8819287B2 (en) | System and method for compressing URL request parameters | |
| JP3593244B2 (ja) | データ圧縮装置 | |
| US6112208A (en) | Data compressing method and apparatus to generate bit maps in accordance with extracted data symbols | |
| EP0721699B1 (en) | Method and apparatus for a unique and efficient use of a data structure for compressing data | |
| JP3132774B2 (ja) | データ圧縮・復元装置 | |
| Ota et al. | A necessary and sufficient condition for reconstruction of circular binary string based on the lengths of substrings with weights | |
| Keller et al. | Hiding Information in Short Network Packets | |
| Mukherjee et al. | Improving bandwidth of communication controllers | |
| JPS62209948A (ja) | デ−タ圧縮伝送方法 | |
| Ong | Text compression for transmission and storage | |
| CN115103030A (zh) | 报文的处理方法、装置及计算机可读存储介质 | |
| Park et al. | Construction of efficient error-limiting variable length codes | |
| Salomon | Statistical Methods | |
| JP3015483B2 (ja) | データ圧縮及び復元方式 |
Legal Events
| Date | Code | Title | Description |
|---|---|---|---|
| A131 | Notification of reasons for refusal |
Free format text: JAPANESE INTERMEDIATE CODE: A131 Effective date: 20040210 |
|
| A521 | Written amendment |
Free format text: JAPANESE INTERMEDIATE CODE: A523 Effective date: 20040412 |
|
| TRDD | Decision of grant or rejection written | ||
| A01 | Written decision to grant a patent or to grant a registration (utility model) |
Free format text: JAPANESE INTERMEDIATE CODE: A01 Effective date: 20040824 |
|
| A61 | First payment of annual fees (during grant procedure) |
Free format text: JAPANESE INTERMEDIATE CODE: A61 Effective date: 20040827 |
|
| R150 | Certificate of patent or registration of utility model |
Free format text: JAPANESE INTERMEDIATE CODE: R150 |
|
| LAPS | Cancellation because of no payment of annual fees |