JPH06508456A

JPH06508456A - 多重レベルを利用するデータ圧縮

Info

Publication number: JPH06508456A
Application number: JP5500423A
Authority: JP
Inventors: ブガイスキー　ジョセフ　エム; ラソー　ジェームズ　ティー
Original assignee: トライアーダ　リミテッド
Priority date: 1991-05-29
Filing date: 1992-05-11
Publication date: 1994-09-22
Anticipated expiration: 2016-10-15
Also published as: JP3217781B2; US5245337A; EP0588921A4; US5293164A; CA2103445A1; EP0588921A1; WO1992022141A1

Abstract

(57)【要約】本公報は電子出願前の出願データであるため要約のデータは記録されません。

Description

【発明の詳細な説明】本発明は、入力データ本体を、蓄積、転送、暗号化等のために、人力データ本体に関して圧縮した整列データ構造に変換する、ディジタルデータ変換システムデータ圧縮、または、ときに「テキスト圧縮」と言われるものの方法ならびに装置は、英数字テキスト、ディジタル化画像、コンピュータコートなとといった到来するディジタルデータ本体に作用して、そのデータを格納するための記憶所要容量を削減する、あるいは、通信チャネルを介してデータ本体を転送するために要する時間、または安全保護のためにデータを暗号化するために要する時間を短縮する。

データ圧縮は入力データ本体の冗長性を除くことによって作用し、達成されるであろう圧縮の度合はデータ本体の冗長性に比例する。データ圧縮システムは、圧縮データから入力データ本体を正確に復元できる無損失システムと、完全に可逆的な復元プロセスを要しない音声および画像といったディジタル化アナログ信号にしばしば使用される損失システムと、に大きく分かれる。本発明は、可逆システムまたはノイズレスシステムと呼ばれることもある、無損失システムの類に属する。

無損失圧縮システムは、更に、出現確立に基づいて各記号にコートを割り当てる統計的コート化と、入力データ本体の連続文字集合を、ディクショナリ内の該当ノーケンス格納位置を表すコートに置き換えるディクショナリ圧縮と、に分がｎる。本発明は、ディクショナリ式の圧縮装置および方法に関するものである。

ディクノヨナリ式データ圧縮方法は、更に、入力データ本体の一般的性質に関する事前知識に基づいて、固定ディクショナリを備えた静的ディクショナリ配列に分割される。例えば、データ本体か英語のテキストである場合、そのディクショナリは、当該テキストのデータシーケンスの統計学的出現頻度に基つくものとｔ；る。これに換わる方法は、入力データ本体の最初のセクションを利用してディクソヨナリを構成する、動的または適応ディクショナリエンコーダであり、この場合、ディクショナリはデータ本体より多くのデータか処理されるように変更される。本発明は、このような動的ディクノヨナリ圧縮システムに関するものである。

無損失動的ディクショナリ圧縮の分野においては、ＺＩＶ−ＬＥＭＰＥＬ圧縮と呼ばれる構成か、きわめて効果的であるとされている。ＺＩＶ−ＬＥＭＰＥＬ法に関する変態は、イーストマン他による合衆国特許第４．４６４．６５０号、ウェルチによる合衆国特許第４．５５８．３０２号：フィアラ他による合衆国特許第４．９０６．９９１号で開示されている。

これらのＺＩＶ−ＬＥＭＰＥＬプロセッサは、入力直列ストリームとしてコード化されたデータ本体を広汎に受け入れて、データストリームの最初のセグメントを格納するディクショナリを作成する。以降に出現するセグメントは、メモリ内の事前出現ストリングの一端を指摘し、入力セグメントと同一のストリング長を識別し、入力セグメント内の次の固有文字を組み込むために、この格納セグメントに比較される。

データ圧縮の分野の概説は、１９８９年１２月発行のＡＣＭコンピユーティン本発明は、少なくともある種のデータに関し、従来技術と比べて圧縮の効率、速度、簡便性を向上した、無損失動的ディクショナリ圧縮方式を実行するための方法と装置に関する。

本発明の方法によって作成されるデータ構造は、人間の脳の記憶機能の作用に類似させた連合原理を採用している。例えば、顔のイメージ、流行歌のメロディ、または授業の内容を表す入力のような、永久記録にてきしていると脳か見なす知覚入力群を、脳か初めて受信したとき、脳は、これらの知覚信号の連合を記録する。そして、再びその顔を見たり、その歌を聞いたり、その授業を体験したりするなとして、再び同じ知覚入力群が出現すると、脳は、先に記憶に留められた連合と新しい入力とを互いに関係付け、新しい入力を、古い画像の繰り返しをなすものと認識する。脳は、これらの繰返し出現した同−知覚入力群を記憶せずに、既に脳か学習した連合を強化する。

同様に、本発明の機械は、連合データ記憶機械である。この機械は、情報を連合として記憶する。連合は、一つの事象集合か出現したことの記憶である。以降の同一事象集合の出現によって、新しい記憶が生じることはなく、すてにメモリの中に存在する連合が増強される。機械か、ある事象集合を学習すると、後から入力データストリームに生じた集合と比較するため、および、新セクションを学習する必要はなく、以前に学習されたセクションと等しいと確認することたけて十分である、と連合か認識される場合に、この事象集合を利用できる。この連合因子により、全入力データストリームを記憶するための所要メモリよりも少ないメモリの記憶データ構造となる。

機械の構造は、一階層、以下「レベルＪと呼ぶ、の処理である。各レベルは、各入力値集合ごとに単一出力値を生成する関数を実施しなくてはならない。また、この関数は可逆的でなくてはならない、即ち、この関数は、各出力値について、逆方向に作用し、別個の独自入力値集合を再生できなくてはならない。機械の全レベルで同一関数を利用する必要はないが、各関数は数学的に可逆的である。

このような関数の一つは、入力値を固定長二進数と考え、一対の数字を連結するだけで長さが倍（ビット数が倍）の固定長二進数を生成する、というものである。この関数の逆は、長い二進数を二つの短い数字に分割することである。これは、前記要件に適した最も単純な関数である。しかしながら、この関数は、数字のヒント数か各レベルごとに倍になるので、あまり役に立たない。

利用可能な別の種類の関数は、レベル内の局部記憶を用いて、実際にそのレベルで処理される入力値に関わる情報を記録するというものである。

この種の簡単な関数は、提供された各単独対の入力値のコピーを、局部記憶に保管するというものである。入力対のコピーか入る局部記憶のアドレスは、出力値として使用される。以前に処理した入力対と同じ入力対に遭遇すると、新しい局部記憶は使用されず、その入力値と合致する値が既に入っている局部メモリのアドレスが、出力値として再使用される。新入力を、既に学習された連合と比較する速度を最適化するための改善点を多少備えたこの関数は、本発明の好適実施例の基礎となる。

本発明の方法は、広汎には、直列式の入力データストリームを、データエレメント、好ましくはデータ対、という短かいシーケンスに分割し、入力データの各連続ソーケンスを表す信号から成る出力ストリームを生成することによって、直列式の入力データストリームを分析することに関わる。次に、この出力ストリームは第二プロセスまたはレベルに送出され、第二プロセスまたはレベルでは、入力データストリームに対して第一プロセスが作用したのと同じように、第一プロセスの出力信号に対して作用する。第ニレベルの出力は第三レベルに送出され、これは、最後のレベルまで繰り返される。

各レベルは、進行レベルによる複数入力データエレメントの処理を待機した後に、直前の下位レベルから単一データエレメントを受け取らなくてはならないので、レベルか上位であるほどゆっくりした速さで作用するように、各レベルのデータエレメントは入力信号よりも出力信号の方が少ない。

本発明の好適方法は、概括的には、入力データストリームのデータの未出現シーケンスを検出し、このような未出現シーケンスを格納手段に格納し、データエレメントが入力シーケンスよりも少ない出力信号を用いて、格納手段の各入力シーケンスの格納場所を表す出力信号を生成するアルゴリズムを、繰り返し利用することと考えられる。

入力データストリームは、工程を逆にして、蓄積データエレメントを上位レベルから下位レベルへ送り、学習過程で分解されたのと同方法で入力データストリームを再生することによって、メモリ構造から容易に復元できる。

本発明の方法を実施するための装置は、汎用コンピュータから構成できるか、チェーンの各プロセッサが、データ構造が構成される記憶サイクル時に順次下位のプロセッサの出力を受信し、入力データ本体の復元時にチェーンの順次上位プロセッサの出力を受信するように、両方向通信リンクによって直列チェーンに結合された個別プロセッサを採用した、専用目的システムより構成されることか好ましい。各プロセッサは、チェーン内の場所に適したサイズの専用メモリを備えることが好ましい。本発明の好適実施例には、データ格納時にチェーンの最高レベルプロセッサからの出力を受信するための直列メモリも組み込るれる。

データ格納工程時のプロセッサへの各入力対か単一信号出力となる本発明の好適実施例では、入力時も固有対が出現すると、プロセッサは、４ワードのエントリをメレリに格納する。そのうち２個のワードは、固有対を構成し、三番目のワードは入力データ中にその対か出現した回数、四番目のワードは、この入力で出現頻度か少ない、そのメモリ中の別のエントリのアドレスを表す連結ポインタである。

各プロセッサは、各入力からの各数字対を、複数の連結リストのいずれかへ割り当てるハツシュ関数も実施する。本発明の好適実施例では、ハツシュ関数は、所定数の、各入力対の２個の数字の最下位のビットの合計を生成することによって、すへての入力対をいずれかのリストに分けるように作用する。プロセッサは、連結されたリストの各々の最も頻繁に出現するエントリに対するポインタが入ったハッンユインデックステーブルも作成する。この構成は、入力対か以前に出現したかとうかを判断するタスクを効率的にするために使用される。いずれの連結リストと比較されるべきかを判断するために、入力対の最下位のビットを合計した後、最も頻繁に出現した連結リストの対の記憶位置か判定されたために／％ツシュテーブルか使用され、入力対と、その連結リスト内に格納されている少頻度入力対の各々が比較され、入力対の固有性か判定される。

本発明の代替実施例は、あるレベルの全使用可能メモリかいっばいになった後でも新しい入力記録を処理し続ける方法を提供する。この代替実施例では、あるレベルに対する入力の全固有データ対がデータ構造のエントリとなる初期学習期間の後、第二モートのオペレーションが開始される。この第二モートでは、固有対か検出されると、次の上位プロセスに空白信号か出力され、固有データ対はプロセッサからの出力信号にアペンデージとして追加され、上方向に、次々に高いレベルのプロセッサを通り、システムの最高プロセッサの出力を受信する直列メモリに渡される。全レベルからのアペンデージは、最高レベルからの出力と共に格納される。記録か復元されると、復元された記録の空白が適当な固有データ対に交換できるように、アベンデージは送り返される。この構成により、システムは無数の入力記録を処理し、記録を可逆的に復元できる。

本発明の別の代替実施例は、第一モードのオペレーションのときには出現しないか、第二モードのオペレーションのときに一旦出現し始めると比較的高頻度で出現するデータ対のレベルに、メモリ部分を確保する。これは、各プロセッサに関わるメモリを、一方は永久メモリおよび他方は一時メモリと呼ばれる２部分に分けることによって実施される。第一モードのオペレーションのあいだ、入力ストリーム中にこれまで出現したことのないプロセッサへの各入力は、永久メモリ部分に格納される。データ構造内の全エントリか永久部分に作成される初期学習期間の後、第二モードのオペレーションが開始される。この第二モードでは、固有対が検出されると、一時メモリ部分にロードされ、次の上位プロセスに空白信号が出力され、固有データ対はプロセッサからの出力信号にアペンデージとして追加され、上方向に、より上位レベルのプロセッサを通って、システムの最高プロセッサの出力を受信する直列メモリに渡される。全レベルからのアベンデージは、最高レベルからの出力と共に格納される。記録が復元されると、復元された記録の空白が適当な固有データ対に交換できるように、アペンデージが送り返される。一時メモリ部分のエントリが、入力信号中に所定回数出現すると、永久メモリに昇進させられ、普通の方法で処理される。この構成により、システムは無限長の入力記録を処理し、記録を両方向に復元できるのである。

本発明の他の目的、利益、応用は、本発明の好適実施例に関する以下の詳細説明によって明らかになるであろう。説明は、添付図面を参照して行われる。

図面の簡単な説明図１は、本発明の装置の好適実施例を表す機械の概略図である。

好適実施例の説明本発明の方法は、広範囲な形をとるディジタルプロセッサによって実施されることか好ましい。極端な例として、データ圧縮の点で本発明が最高効率を示す大データ本体かなければ、本発明は汎用ノイマン型コンピュータで実施できるか、汎用コンピュータによる実施は、データ格納タスクも復元タスクも非常に緩慢である。従って、本発明の装置の好適実施例は、図１のような形の専用コンピュータの形を取る。

機械は、ディジタルプロセッサ２０ａ、２０ｂ、２０ｃ、２０ｄ、−・２Ｏｎのチェーンから成っている。プロセッサは、両方向データ経路２２ａ、２２ｂ、２２ｃ等によって、別のプロセッサに相互接続されている。各プロセッサは、関連ディジタルメモリ２４ａ、２４ｂ、２４ｃ、２４ｄ、・・２４ｎに相互接続されている。各プロセッサとその関連メモリの相互接続は、両方向接続２６ａ、２６ｂ、２６ｃ、２６ｄ、・・２６ｎを介している。チェーンの最後のプロセッサ２Ｏｎは、両方向データ経路３０によって直列メモリ２８に接続されている。

以下において、チェーンの一端のプロセッサ２０ａとその関連メモリ２４ａをシステム内最低レベルと呼び、プロセッサ２Ｏｎとその関連メモリ２４ｎを最高レベルと呼ぶことかある。メモリ２０ａ−ｎに順序付きデータ構造を生成するために機械に処理される入力データは、入力チャネル３２を介して最低レベルプロセッサ２０ａに提供される。線路３２の初期の入力データストリームと同じ形の復元データ構造出力は、最低レベルプロセッサ２０ａから出力チャネル３４を介して提供される。

本発明の最も簡単な実施例では、プロセッサ２０ａは、特定記号シーケンスがその入力データに以前に出現したことがあるかどうかを判断するために、アスキ一様式てコード化される英数字データの形を取るであろう各入力信号対を検査する。未出現のもの、あるいは、固有のものである場合、その入力対は、メモリ２４ａに格納される。メモリ２４ａの内容は、プロセッサ２０ａによって、入力ストリーム中の記号対が固有のものであるかどうかを判断するために使用される。

プロセッサ２０ａは、回線２２ａを介してプロセッサ２０ｂに出力を提供し、プロセッサ２０ｂは回線２２ａの新語言うを入力として扱って、プロセッサ２０ａが行ったのと同しプロセスを正確に繰り返す。この処理アルゴリズムは、各プロセッサによって繰り返される。このように、各プロセッサが受信する各ディジタルワード対ごとに信号ディジタルワードを出力し、発生する唯一の格納は、そのレベルで固有の入力対の格納であるように見える。

このシステムの作用を理解するために、図１の機械が、最初は空で、“ＪＯＨＮ　Ｊ、ＪＯＮＥＳ　ＨＡＳ　ＪＯＩＮＥＤ　ＪＯＨＮＳＯＮ　ＡＮＤ　ＪＯＨＮＳＯＮ　ＡＳ　Ａ　ＪＵＮＩＯＲＪＡＮＩＴＯＲ”というテキストを受け取ることを考える。この例では、６レベルのオペレーションを示す。下記リストでは、はっきり分かるようにするために空白を−で示しである。

プロセッサ２０ａは、このテキストを１度に二文字ずつ処理する。

回線３２の　ローカルアト　メモリ２４ａ　プロセッサ２０ａＨＮ　２　ＨＮ　２ＮＥ　５　ＮＥ　５Ｓ−６Ｓ−６８Ａ　７　ＨＡ　７ＩＮ　８　１Ｎ　８ＥＤ　９　ＥＤ　９ −Ｊ　３０Ｈ１００Ｈ１ＯＮＳ　ｌ　Ｉ　ＮＳ　Ｉ　ＩＯＮ　１２　ＯＮ　ｌ　２ −Ａ　ｌ　３　−Ａ　１３ＮＤ　１４　ＮＤ　ｌ　４Ａ−１５Ａ−１５Ｊｕ　ｌ　６　ＪＵ　１６ＮＴ　Ｉ　７　Ｎｌ　１７０Ｒ１８０Ｒｌ　８ −Ｊ　３ＡＮ　ｌ　９　ＡＮ　１９ＩＴ　２０　ＩＴ　２００Ｒ１８プロセツサ２０ｂとメモリ２４ｂより成るレベル２は、レベル１からの出力を、一度に数字２個ずつ処理する。

回線２２ａ　ローカルアト　メモリ２４ｂ　プロセッサ２０ｃの入力対　レスへの格納　の内容　への出力データ＋１１２　８　１１１２　８＋３１４　９　１３１４　９１３　６　１０　＋３　６　１０＋５１６　１１　１５１６　１１プロセツサ２０ｃとメモリ２４ｃより成るレベル３は、レベル２がらの出力を、一度に数字２個ずつ処理する。

回線２２ｂ　ローカルアト　メモリ２４ｃ　プロセッサ２０ｄ８１０６’３９　６＋１１２　７　１０１１　７１３＋４　８　１２１３　８プロセツサ２０ｄとメモリ２４ｄより成るレベル４は、レベル３からの出力を、一度に数字２個ずつ処理する。

回線２２ｃ　ローカルアト　メモリ２４ｄ　プロセッサ２０ｅプロセツサ２０ｅとメモリ２４ｅより成るレベル５は、レベル４からの出力を、一度に数字２個ずつ処理する。

回線２２ｄ　ローカルアト　メモリ２４ｅ　プロセッサ２Ｏｆプロセツサ２Ｏｆとメモリ２４ｆより成るレベル６は、レベル５がらの出力を、一度に数字２個ずつ処理する。

回線２２ｅ　ローカルアト　メモリ２４ｆ　プロセッサ２８ここで、この機械に提供される初期入力データは、莫大な量の局部記憶となることに注意されたい。

各レベルの入力対は、そのレベルで初めて見られたものである。処理されるデータか増えると、既に局部記憶にあるものと合致する入力対か頻繁に出現するようになり、格納する必要のある新しいことの出現は頻度が低くなる。

この例では、更に、データの格納はテキストストリングＪＯＨＮ　Ｊ、ＪＯＮＥＳ　ＯＦ　ＪＯＨＮＳＯＮ　ＡＮＤ　ＪＯＨＮＳＯＮ　ＤＯＥＳ　Ｎ０ＴＬＩＫＥ　ＨＩＳ　ＪＯＢ　ＮＯＷ、　ＪＯＨＮ　Ｊ、ＪＯＮＥＳ　ＷＩＬＬＱＵＩＴ　ＪＯＨＮＳＯＮ　ＡＮＤ　ＪＯＨＮＳＯＮ　ＡＮＤ　５ＥＥＫ　ＡＮＥＷ　ＪＯＢ”と続く。レベルｌは、再び、このテキストを一度に２文字ずつ処理する。

下記リストでは、見えるようにするために空白を−で示しである。

ローカルアト　メモリＯＦ　２１　０Ｆ　２１ −Ｄ　２２　−Ｄ　２２０Ｅ　２３　０Ｅ　２３Ｓ−６Ｎｏ　２４　Ｎｏ　２４Ｔ−２５Ｔ−２５Ｌｌ　２６　’Ｌｌ　２６ＫＥ　２７　ＫＥ　２７ −Ｈ２８−Ｈ２８Ｉｓ　２９’　Ｉｓ　２９１９３９　２７　＋９３９　２７３０４　３１　３０４　３ルヘル３は、レベル２からの出力を、一度に数字２個ずつ処理する。

８１６　＋０　８１６　１０１７１８　１！　＋７１８　１１＋９２０　１２　１９２０　１２２＋２２　１３　２１２２　１３レベル４は、レベル３から出力を、一度に数字２個ずつ処理する。

ローカルアト　メモリ＋０　１１　７　１０　１１　７１２１３　８　＋２１３　８＋１４９　１１４９１７１８　１１　１７１８　＋１レヘル５は、レベル４から出力を、一度に数字２個ずつ処理する。

ローカルアト　メモリ入力対　レスへの格納　の内容　出力データレベル６は、レベル５から出力を、一度に数字２個ずつ処理する。

ローカルアト　メモリ第二例で、レベルｌとレベル２で、局所メモリに新しい入力対を格納する必要かあったものは、割合として第−例の約１／２であったことに注意されたい。レベル３てさえ、僅かながらも、新メモリを使用しない入力対を処理した。更に多くのデータか処理されると、この現像は継続していくであろう。新しい入力対の出現は次第に少なくなる。高い方のレベルでさえ、新メモリを要しない入力対か出始めるであろう。

データは、システムを逆方向に作用させることによって復元できる。直列メモリ２８に格納されている数字は、各レベルを通って戻すことができる。上記の例では、プロセッサ２Ｏｆは、数字２を受信すると、数字３と４の対であるエントリアドレス２の内容に取り、それらを経路２２ｅを介してプロセッサ２０ｅに送出する。プロセッサ２０ｅは、そのアドレス３と４の内容を、下位レベル等に送ることによって対応する。最低レベルにおいて、プロセッサ２０ａは、復元された文字集合を出力チャネル３４へ送る。

大量のデータか機械に格納されているとき、事象の頻度分布はある種の特性を示す。少数の高頻度数字対が、レベル毎に見られる入力データの大部分を占める。

局部記憶の大部分を占めることができる多数の低頻度数字対は、入力データのほんのわずかな部分である。格納および検索回収機能の速さを最適化し、機械の各レベルに要求される局部記憶量の実際的な限界を設定するために、この頻度分布の予想の知識を使用して連合機能ならびに局部記憶の配分を計画できる。

低頻度入力数字対は、それらか要求する入力部分と不釣合いな速さで、局部記憶を使い果してしまうので、本発明の好適モードは、出力へのアペンデージとして低頻度数字対を渡すことによって、低頻度数字対が局部記憶を使い果たす空間を限定する方法を具備している。

これは、入力の新情報量と関連した方法で、出力サイズを増大する効果かある。

本発明の機械の好適モードにおいて、各レベルは、大ダイナミックラムメモリを備えたＩＮＭＯＮ　Ｔ２Ｏ（ｌｌ−ランスピユータと、オペレーティングソフトウェアのコピーより成っている。Ｔａ２Ｏは、４ギガバイトまでのメモリを直接アドレス指定できる３２ビットアドレス空間を存している。各レベルは、直列通信リンクによって、各々、その上位のレベルに結合され、別の直列通信リンクによって、各々、その下位のレベルに結合されている。最上位および最下位レベルは、人力／出力インタフェースに結合されている。

各レベルの作用は、レベルが高くなるほど記録サイズが小さくなるということ以外は、他のレベルの作用と同じである。記録サイズとは、データ格納時に最高レベルからの１アドレス値の出力となる、データ量のことである。この同一記録サイズは、最高レベルに提供されたｌアドレス値に由来する復元プロセスのときに、各レベル毎に生成される出力に適用される。

局部記憶に格納されるデータは、連結リストにこれらの項目を結合する各対およびポインタの出現回数と、入力データストリームの一部であった数字の固有対と、から成っている。使用されるのは、論理的に別個の連結リストの固定番号である。連結リストは、物理的順序と同一ではない論理的順序をリストが存することのできるデータ構造である。各要素が次のものへのポインタを有しているので、連結リストは順次アクセスされる。

入力からの各数字対に、いずれか１個の連結リストを割り当てるためにハツシュ関数が使用される。ハツシュ関数は、数多の項目（この場合は、入力数字対）を、少数の値（この場合は、ハツシュインデックステーブルへのインデックス）にマツピングする。好適実施例で使用されるハツシュ関数は、入力対の数字２個の合計である１６個の最下位ビットを取る。

ハツシュインデックステーブルは、各連結リストの論理的第一エントリに対するポインタを含む固定長テーブルである。好適実施例では、ハツシュインデックステーブルは６５５３６個のアドレスを含むか、その各々は、対応連結リストの論理的第一エントリの３２ビツトアトルスである。

一つのエントリの長さは４ワードである。最初の２ワードは、少なくとも１回以上出現した数字対である。次のワードは、連結ポインタ、即ち同一連結リストの一部である別のエントリのアドレス、である。四番目のワードは、その対が入力データ中に何回出現したかの回数である。

連結リストは、最も頻繁に出現したエントリがリストの最初に来て、最も出現した頻度が少なかったエントリかリストの最後に来るように保持される。

各連結リストは、ハツシュインデックステーブルに含まれるポインタから始まる。このポインタは、（リストにいずれかのエントリがある場合には）メモリ内のエントリのアドレス、または、リストの最後を示すデフォルト値である。

格納のためにレベルに入力記録を提供するときは、以下の手順に従う。プロセッサは、記録を最初から始める入力数字対を取り、ハツシュ関数を使用してハツシュインデックステーブルで適当なエントリを決定し、一致する数字対が見つかるか、リストの最後に達するまで、指定された連結リストを探索する。

連結リスト内を探索するとき、プロセッサは、探索後にリストを更新するときに必要となるであろう数件の情報のトラックをとっておく。また、逆方向ポインタがないので、現在見ているエントリの一つ前のエントリ（以下、第−前エントリと言う）に対するポインタと、その前の連結ポインタ（第二前連結ポインタ）とをとっておく。

合致するものが見つからなければ、この新項目は次のようにしてリストに追加される。リスト内の最終エントリの連結ポインタは、未使用メモリ中の次の利用可能空間を指定するように設定され、入力数字対、その回数、およびリストの最後を示すデフォルトポインタを使用して、その空間に新しいエントリが作られる。

新エントリのアドレスが出力記録に入る。

合致するものが見つかった場合は、そのエントリのアドレスが出力記録に入り、そのエントリの回数が増分される。但し、この回数が、再連結に関する所定しきい値より多く第−前エントリの回数を越える場合は、このエントリはリストの論理的シーケンスに上げられる。これは、当該連結ポインタと二つの前エントリとを書き換えることによって実施される。現エントリの連結ポインタにあったアドレスは、第−前エントリの連結ポインタにコピーされる。第−前エントリのアドレスは、現エントリの連結ポインタに書き込まれる。現エントリのアドレスは、第二前リンクポインタに書き込まれる。

一つの入力対の処理か終了すると、同人力記録からの次の入力対が取られ、同じように処理される。

あるレベルの使用可能メモリがいっばいになった場合、その中にはもうデータ対を格納できない。したがって、既存のデータ対のいずれかに合致しない入力対を構造に追加することは不可能である。新しい入力記録の格納時にこのような非合致入力対が発生した場合、アドレスの代わりに空白値か出力記録に書き込まれ、当該データ対はアペンデージとして出力記録の最後に入る。入力記録と一緒に受理されるこのようなアペンデージも、出力記録の最後に追加されるので、あらゆるレベルからのアペンデージは、最高レベルからの出力に一緒に入っている。

構造が比較的いっばいになるまで出現しはじめないデータ対のために、あるレベルのメモリの一部を確保する本発明の代替実施例では、メモリを、アドレス空間の両端から組み立てられる二つのヒープとして扱う。一方は永久メモリと呼ばれる。他方は一部メモリと呼ばれる。各レベルのオペレーションの初期モードのとき、すべての新エントリ永久メモリに作られる。メモリの所定部分がいっばいになると、第二モードのオペレーションが始まり、その間、新エントリ用に一部メモリか使用される。

この一時ヒープのエントリは、永久メモリのエントリと同構造であるか、保持は同方法では行われない。一時エントリは、当該レベルへの入力で出現したものの永久メモリに入れるほどの頻度ではない数字対を保持する。一時エントリの中には空白のものもあり、即ち、その位置には現在は有効数字対が保持されていないことを示すデフォルト値を入れておくことができる。

各連結リストは、ハツシュインデックステーブルに入っているポインタで始まる。このポインタは、（リストにいずれかの永久エントリがある場合には）永久メモリ内のエントリのアドレス、または、このリストの事前に割当てられた第−一部エントリのアドレスである。永久エントリがある場合、それらの各々は、事前に割当てられた第−一部エントリを指定する最後のもの以外は、別の永久エントリを指定する。リストには、追加的な一部エントリもある。各一時エントリは、リストの最後を示すポインタにデフォルト値を有する最後のもの以外は、隣の一部エントリを指定する。

連結リスト内を探索するとき、プロセッサは、探索後にリストを更新するときに必要となるであろう数件の情報のトラックをとっておく。また、逆方向ポインタかないので、現在見ているエントリの一つ前のエントリ（以下、第−前エントリと言う）に対するポインタと、その前の連結ポインタ（第二前連結ポインタ）とをとっておく。永久メモリの連結リストの最後に達した場合、ポインタ１個を永久メモリの最後の連結ポインタとしてとっておく。リスト内に永久エントリがなかった場合、ハツンユインデックルテーブル内の位置は、永久メモリでの最終連結ポインタであると見なされる。連結リストの永久部分の探索後、当該リストの事前割当て第−一部エントリで始まる対応一時リストが探索される。リスト内に、いずれか空の一部エントリが見つかった場合、ポインタを第−空一部エントリに保管する。

合致するものか見つからなければ、低頻度入力対の出現を示す出力値が出力記録に入り、入力対は低頻度了ペンデージ用のバッファにコピーされ、新項目は次のようにしてリストに追加される。空の一部エントリが見つかった場合、その中に数字対を格納し、カウンタを１に初期設定する。空の一部エントリか見つからなかった場合、リスト内の最後のエントリの連結ポインタは、一時ヒープ上の次の利用可能空間を指定するように設定され、入力数字対、その回数、およびリストの！＆後を示すデフォルトポインタを使用して、新しいエントリが作られる。

永久領域で合致するものが見つかった場合は、そのエントリのアドレスか出力記録に入り、そのエントリの回数か増分される。但し、この回数が、再連結に関する所定のしきい値より多く第−前エントリの回数を越える場合は、このエントリはリストの論理的シーケンスに上げられる　これは、当該連結ポインタと二つの前エントリとを書き換えることによって実施される。現エントリの連結ポインタにあったアドレスは、第−前エントリの連結ポインタにコピーされる。第−前エントリのアドレスは、現エントリの連結ポインタに書き込まれる。現エントリの了ドレスは、第二前リンクポインタに書き込まれる。

一時領域で合致するものが見つかった場合は、そのエントリの回数が増分される。二の回数が、永久メモリを作るための所定のしきい値を越える場合、このエントリは永久メモリに移行される。これは、永久メモリ内の次の利用可能空間を使用してエントリを作ることによって実施される。入力数字対と回数とは、新エントリにコピーされる。一時メモリ内の現エントリは、空の一部エントリのためにデフォルト値を書き込むことによって空にできる。永久メモリ内の最終連結ポインタに保持されているアドレスは新エントリにコピーされ、新エントリのアドレスは（永久メモリ内の最終連結ポインタだった）連結ポインタに書き込まれる。

こうして新永久エントリのアドレスは、出力記録に入れられる。回数かしきい値を越えない場合、低頻度入力対の出現を示す出力値が出力記録に入れられ、入力対は低頻度アペンデージのバッファにコピーされる。

一時または永久エントリを追加するだけの空間か残っていない場合は、必ず、すべての一時エントリか廃棄される。これは、各リストの事前割当て第−一部エントリを、空として、および、そのリスト内の最終エントリとしてマーキングすることによって実施される。

一つの入力対の処理が終了すると、同人力記録からの次の入力対が取られ、同じように処理される。入力記録の固定長部分の最後には、下位レベルからの低頻度数字のアペンデージを入れることができる。このアベンデージは、出力、次に低頻度アペンデージ用の当該レベルのバッファの内容に、コピーできる。

Claims

【特許請求の範囲】

１．入力データストリームを受信して、入力データストリームを、整列された格納データ本体に変換するために効果のある装置であって、順番に整列された複数のメモリレベルと；各々１個のメモリレベルと関係のある複数の処理手段と；から成り、第一メモリレベルに関連付けられた前記処理手段は、前記入力データストリームを受信し、前記ストリームを分析して前記ストリーム中の未出現シーケンスを検出し、前記第一メモリレベルにそのシーケンスを格納し、前記入力ストリーム中の各データエレメントシーケンスの第一メモリレベルでの格納位置を表す信号を出力する働きをなし、後続の各メモリに関連付けられた処理手段は、次の下位メモリレベルに関連付けられた処理手段からの出力信号を受信し、当該出力信号中に出現したデータエレメントの未出現シーケンスを、その関連メモリレベルで検出ならびに格納し、その入力信号の各データエレメントシーケンスの関連メモリレベル内の格納位置を表す信号を次の上位メモリレベルと関連付けられた処理手段に出力する働きをなすことを特徴とする、前記装置。
２．各処理手段で使用されるデータエレメントのシーケンスは、エレメント対から成ることを特徴とする、請求の範囲第１項に記載の装置。
３．各メモリレベルに、各格納入力シーケンスの入力信号中の出現数を記録するための手段を具備することを特徴とする、請求の範囲第１項に記載の装置。
４．入力データストリームを受信して、この入力データストリームを、入力データストリームを復元できる整列された記憶アレイに変換するために有効な装置であって、整列されたメモリレベルのシーケンスと；下位のメモリレベルに関連付けられた処理手段からの入力信号を受信し、その入力信号中のいずれかエレメントのシーケンスをその関連メモリレベルに格納し、順次上位のメモリレベルに関連付けられた処理エレメントヘの出力信号を生成する働きを各々がなす複数の処理手段と；から成り、前記各処理手段は、当該入力ストリーム中の複数の連続データエレメントを、当該出力信号の単一データエレメントに変換する働きをなし、前記各処理手段は、更に、各メモリレベルが入力データエレメントの固有シーケンスを単一位置のみ格納するように、当該入力ストリームに初めて出現したエレメントシーケンスを当該関連メモリに格納する働きをなすことを特徴とする、前記装置。
５．入力データストリームを復元できる整列されたデータ本体を生成するために入力データストリームに関して運用する方法であって、データエレメントの未出現シーケンスを検出して入力データストリームを分析し、このような未出現シーケンスを格納手段に格納し、前記格納手段内のデータエレメントの各入力シーケンスの格納場所の表す出力信号、前記出力信号のデータエレメントは前記入力シーケンスよりも少ない、を生成するアルゴリズムから成り、かかる出力信号で前記アルゴリズム実施することを特徴とする、前記方法。
６．入力データストリームを受信して、入力データストリームを復元できるメモリ手段内データ整列構造に変換するために有効な装置であって、前記入力ストリーム内のデータエレメントの入力シーケンスを分析し、前記メモリ手段内のかかるデータエレメントの少なくともいずれか未出現シーケンスを格納し、データエレメントの少なくともいずれか入力シーケンスのメモリ手段での格納位置を表す出力信号、前記出力信号のデータエレメントは前記入力シーケンスよりも少ない、を生成するための、複数の順次整列された手段から成り、最初のかかる分析手段は、前記入力データストリームを入力シーケンスとして順次受信し、後続のかかる分析手段は、かかる手段の下位のものから出力信号を順次受信し、それらの出力信号をかかる手段の上位のものに順次送出することを特徴とする、前記装置。