JPH04360246A - ファイル圧縮装置 - Google Patents

Abstract

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

Description

【発明の詳細な説明】

【０００１】

【産業上の利用分野】本発明は、計算機システムにおい
てオペレーティングシステムによって行われるファイル
管理の方式に係わり、特に共通部分を有する複数のファ
イルを効率良く圧縮するためのファイル圧縮装置に関す
る。

【０００２】

【従来の技術】計算機システムにおいて、記憶領域であ
る二次記憶装置を効率的に使用してデータの蓄積経費の
削減を行い、かつ転送経費の経済化をはかるため、デー
タ圧縮技術が提案され実用化されている。データ圧縮と
は、データ変換を行うことによってデータ内の冗長度を
抑圧し、データをより短いデータ長で簡潔に表現するこ
とである。

【０００３】現在、広く使用されているデータ圧縮法と
して、Ｈｕｆｆｍａｎの最適符号化法がある。これは、
データ中のパターンの出現頻度を統計的に調べ、出現頻
度の高いパターンほど短い符号を割り当てるもので、パ
ターンの数を多くすることにより平均符号長を短くする
ことが可能となる。また、Ｚｉｖ−Ｌｅｍｐｅｌのデー
タ圧縮法では、データの統計的性質や定常性を仮定する
必要がなく、任意の記号列に直接適用できる。このデー
タ圧縮法によると、長い記号列を効率良く圧縮すること
が可能なため、計算機システムで作られる各種ファイル
の圧縮に適している。

【０００４】しかしながら、この種のデータ圧縮技術に
あっては次のような問題があった。即ち、複数のファイ
ルが等しい内容のデータを有している場合、記憶領域（
二次記憶装置）には同じデータがいくつも保存されるこ
とになる。この二次記憶装置における無駄な領域は、内
容が共通である部分のサイズが大きいほど、またそれを
有するファイル数が多いほど大きくなり、二次記憶装置
の効率的な利用の妨げとなっている。

【０００５】一方、上記のようにデータ圧縮処理は、デ
ータファイルに対して個別に実行され、個々のデータフ
ァイルがよりサイズの小さいデータファイルに変換され
る。そのため、複数のファイルに共通の内容が内在して
いることによる二次記憶装置利用上の不経済性を、従来
のデータ圧縮処理では排除することができない。

【０００６】また、この問題点を解決するには、複数の
ファイルの内容を考慮した統合的な処理が必要であるが
、これまでこのような処理方法は全く実施されておらず
、未だ実用化されていない。

【０００７】

【発明が解決しようとする課題】このように従来のデー
タ圧縮処理は、個々のデータファイルに関してはそれぞ
れ圧縮効果があるものの、複数のファイルに共通の内容
が内在していることによる二次記憶装置利用上の不経済
性を排除することはできなかった。

【０００８】本発明は、上記問題点を解決するためにな
されたもので、その目的とするところは、複数のファイ
ルに共通の内容を二次記憶装置に重複して記憶する等の
不都合を避けることができ、二次記憶装置のより効率的
な利用が可能となるファイル圧縮装置を提供することに
ある。

【０００９】

【課題を解決するための手段】本発明の骨子は、複数の
ファイルに共通の内容がある場合に、共通部分とこの共
通部分を除いた非共通部分とを独立して格納することに
ある。

【００１０】即ち本発明は、複数のファイルを効率良く
圧縮するためのファイル圧縮装置において、第１の記憶
部に格納された複数のファイルに対しその内容を比較す
る手段と、この比較結果で内容が一致している部分を抜
き出す手段と、抜き出した共通部分を共通ファイルとし
て第１の記憶部又は第２の記憶部に格納する手段と、共
通部分を抜き出した後のファイルを固有ファイルとして
第１の記憶部又は第２の記憶部に格納する手段とを設け
るようにしたものである。

【００１１】本発明においては、複数のファイルの内容
を比較した結果、一つのファイル内で判定される共通部
分が複数個あってもよい。また、比較はユーザーが指定
した全てのファイル間で行うだけに限らず、指定したフ
ァイルの内の任意の複数ファイルに対して比較処理を行
い、そのファイル間の共通部分を判定するようにしても
よい。

【００１２】

【作用】本発明によれば、以下のような状況において非
常に効率の良いファイル圧縮を行うことができる。

【００１３】例えば、系の時間発展を調べるため計算機
によるシミュレーションが行われているものとする。こ
のようなシミュレーションでは、時間の離散化を行い、
その離散化された各タイムステップ毎に系の状態を計算
して時間発展を追う。計算された各タイムステップ毎の
現象の変化を把握するには、シミュレーション結果のグ
ラフィック化が非常に有効な支援手段であるため、通常
、あるタイムステップ間隔でグラフィック用のデータを
アウトプットしてデータファイルを作成する。そして、
そのデータファイルを元に、一タイムステップ毎の静止
画をつなげて動画を作る。

【００１４】一般にグラフィック用としてアウトプット
されるデータ量は、一つのタイムステップ分でも大きく
、データファイル全体のサイズは膨大なものとなる。 ところで、シミュレーションの特徴の一つとして、実行
者が希望する初期値，条件のもとでの系の状態の追跡が
可能であるという恣意性をあげることができる。そのた
め、同じ初期値において条件を変えて何回も計算を行い
、条件の違いによる時間発展の違いを調べるというシミ
ュレーションの実行例が考えられる。

【００１５】このように、同じ初期値で条件を変えたシ
ミュレーションを繰り返し行い、その結果をグラフィッ
ク化するためにデータファイルを作成した場合、データ
ファイルにアウトプットされる初期データ（一タイムス
テップ分のデータであり、動画における初期画面となる
）は全てのデータファイルで共通のものとなる。しかし
、前述したようにグラフィック用のデータのサイズは一
つのタイムステップでも非常に大きなものであるため、
いくつものデータファイルが同じ初期データを共有して
いることは、二次記憶装置中に無駄な領域を作り出すこ
とになり、記憶装置の効率的な利用の妨げとなっている
。

【００１６】このような場合、本発明のファイル圧縮処
理を行えば、初期データはただ一つ保存されることにな
るため、二次記憶装置の効率的な使用が可能となり、か
つユーザーは圧縮処理の行われたデータファイルを、そ
れぞれが初期データを保持しているものとして扱うこと
ができる。言うまでも無く、初期データがファイル間で
共通である場合、全てのデータファイルに初期データを
アウトプットする必要はないのであるが、系の時間発展
の様子を視覚的に的確に捕らえ、そこに現れている物理
的，化学的現象をより良く理解するためには、グラフィ
ック用のデータファイルに初期データが含まれているこ
とが非常に望ましい。

【００１７】また、初期データとそれ以降のタイムステ
ップのデータとを分割して、別のファイルにアウトプッ
トすることも可能であるが、このようにデータファイル
を分けた場合、その後のグラフィック化の処理やデータ
ファイルの管理がかなり煩雑なものとなる。そのため、
ファイル圧縮処理は二次記憶装置の有効利用のためのみ
でなく、ユーザーが計算機システムを能率的に使用する
上でも効果が発揮されるといえる。

【００１８】その他、ファイル圧縮処理が有効である例
として、各時刻ｔでのｘの値を計算してｔとｘの値を出
力するプログラムの実行が考えられる。このプログラム
を、時間刻みは同じで条件を変えて何回も実行した場合
、データファイルに出力される時刻ｔに関する数列は、
作成される全てのデータファイルで等しくなる。従って
、ｔの値という共通の内容を含むこれらのデータファイ
ルに対しても、このファイル圧縮処理は効果を持つ。ま
た、僅かな変更で実現できるような新しい機能や異なる
機能を実行可能なプログラムに新たに持たせたい場合、
そのソースファイルをコピーし、修正して使用する。こ
のような場合にも共通の内容を含むファイルがいくつか
作られることになるため、ファイル圧縮処理を行うこと
で二次記憶装置の有効利用に貢献することができる。

【００１９】また、全てのファイル間で行うだけに限ら
ず、指定したファイルの内の任意の複数ファイルに対し
て比較処理を行うことにより、圧縮効率が最大となるよ
うに処理することができる。例えば、３個のファイルが
存在しているときに、第１のファイルに対し第２のファ
イルは共通部分が多く、第３のファイルは共通部分が極
めて少ないとする。この場合、全てのファイルを比較処
理すると、共通部分は第１と第３のファイルの共通部分
のみとなり、圧縮効率は極めて低くなる。これに対し、
第１と第２のファイルを指定して比較処理を行えば、共
通部分のデータ量が多くなり、圧縮効率の向上をはかる
ことが可能となる。

【００２０】

【実施例】以下、本発明の実施例を図面を参照して説明
する。

【００２１】図１は、本発明の一実施例に係わるファイ
ル圧縮装置の概略構成を示すブロック図である。図中１
０は本発明に係わるファイル圧縮処理部であり、複数の
ファイルを比較する比較処理部１１，比較したファイル
の共通部分を取り出す共通部分処理部１２，及び各ファ
イルを共通部分と非共通部分に分けるファイル処理部１
３等から構成されている。２０は磁気ディスク等の二次
記憶装置（第１の記憶部）、３０も同様に磁気ディスク
等の二次記憶装置（第２の記憶部）である。なお、これ
らの二次記憶装置２０，３０は必ずしも独立したもので
はなく、共通のものであってもよい。上記装置によるフ
ァイル圧縮の動作を、図２〜図１３に示すフローチャー
ト及びファイル構造を参照して説明する。

【００２２】まず、基本的なファイル圧縮処理の手順を
、図２に示すフローチャートに従って説明する。ユーザ
ーがファイル圧縮処理のコマンドと圧縮を希望する既存
のｎ個のファイル名を入力する（ステップＳ１）と、オ
ペレーティングシステムは指定されたｎ個のファイル間
で内容データの比較を行い（ステップＳ２）、内容が完
全に一致している部分があるか否かを判断する（ステッ
プＳ３）。内容が一致している部分がなかった場合、フ
ァイル圧縮処理を終了する。

【００２３】一方、内容が一致している部分があると判
定された場合には、その部分を共通部分とみなし、それ
に共通部分であることを示す共通部分制御語を付加して
二次記憶装置に保存する（この処理を共通部分処理と呼
ぶ）（ステップＳ４）。さらに、比較が行われた後のフ
ァイルに対して、そのファイルが特定の位置に特定の共
通部分を所有していることを指定するための処理を行い
、二次記憶装置に保存する（この処理を比較後ファイル
処理と呼ぶ）（ステップＳ５）。この比較後ファイル処
理をｎ個のファイル全てに対して行うと、ファイル圧縮
処理が終了される。ファイル圧縮処理によって新たに作
成されたファイルを共通部分も含めて圧縮済ファイルと
呼ぶ。

【００２４】ここで、ファイル間の内容データを比較し
て共通部分の判定を行う方法を簡単に説明する。例とし
て、ファイル１とファイル２の共通部分を判定する場合
を考える。まず、ファイル１を適当なデータ長（例えば
この場合１行とする）に分割したとみなし、ファイル１
の全行とファイル２の全行を先頭行から順に１行ずつ比
較する。あるペアを比較した結果、その二つの行が同一
でなければ次のペアの比較を行うが、同一であった場合
には以下の処理を行う。例えば、ファイル１のｉ１　行
目とファイル２のｉ２　行目が同一であった場合は、次
にファイル１の（ｉ１　＋１）行目とファイル２の（ｉ
２　＋１）行目の比較を行う。この二つの行も同じであ
れば、（ｉ１＋２）行目と（ｉ２　＋２）行目を比較す
る。

【００２５】このように、二つの行が同一である限りフ
ァイル１とファイル２のそれぞれ次の行の比較を行う。 そして、仮にファイル１の（ｉ１　＋ｋ）行目とファイ
ル２の（ｉ２　＋ｋ）行目が同一でないと判明した場合
、ファイル１のｉ１　行目から（ｉ１　＋ｋ−１）行目
までの範囲とファイル２のｉ２　行目から（ｉ２　＋ｋ
−１）行目までの範囲が共通部分であると判定される。 もし、３個のファイルの共通部分を判定する場合は、フ
ァイル１とファイル２の共通部分とファイル３を上記と
同様の方法で比較する。

【００２６】次に、共通部分処理と比較後ファイル処理
について、より具体的に説明する。まず、図２のステッ
プＳ４の共通部分処理では、上述したように共通部分に
共通部分制御語を付加し、図３のようなファイル（これ
を共通ファイルと呼ぶ）として二次記憶装置に保存する
。ここで、共通部分制御語にはその共通部分を共有して
いる圧縮済ファイル数（これを共有ファイル数と呼ぶ）
を記録する。この共通部分制御語は、後に説明するよう
に圧縮済ファイルの更新，削除等を行うために設ける。

【００２７】図２のステップＳ５の比較後ファイル処理
として、インデックス逐次型ファイル方式を用いること
ができる。まず、従来用いられているインデックス逐次
型ファイルについて説明する。インデックス逐次型ファ
イルとは、一つのインデックスといくつかのレコード（
ファイルを分割したもの）で構成された構造を持ち、イ
ンデックスにはレコードを指定するための値（レコード
が保存されている二次記憶装置中の先頭位置と末尾位置
）が順番に記憶されている。オペレーティングシステム
はインデックスからレコードに関する情報を読取り、順
番にレコードにアクセスすることによって、インデック
ス逐次型ファイルの処理を行うことができる。これによ
ると、レコードの更新，挿入，削除も可能である。

【００２８】本発明の比較後ファイル処理では、このイ
ンデックス逐次型ファイル方式を応用して、オペレーテ
ィングシステムは図４に示すフローチャートに従った処
理を行う。初めに、比較が行われた後のファイルを共通
部分とそれ以外の部分（これを固有部分と呼ぶ）に分割
し、それぞれをレコードとみなす（ステップＳ６）。つ
まり、レコードは共通部分或いは固有部分のどちらかで
あるが、共通部分である場合、共通部分制御語を含む共
通ファイルをレコードとみなす。次に、新たに設けたイ
ンデックスにそれぞれのレコードの先頭位置と末尾位置
を示す値と、そのレコードが共通部分であるか固有部分
であるかを区別する値を記録する（ステップＳ７）。最
後に、インデックスと固有部分であるレコードを二次記
憶装置に保存して（ステップＳ８）、比較後ファイル処
理が終了される。

【００２９】従って、このインデックス逐次型ファイル
方式でファイル圧縮処理を行った場合、圧縮済ファイル
は図５に示すような構造を持つ。このようにして作成さ
れた圧縮済ファイルに対して、通常のインデックス逐次
型ファイルに対する処理（更新，削除等）と同様の処理
を行うことが可能である。但し、レコードが共通ファイ
ルである場合、レコードの先頭に共通部分制御語が付加
されているため、共通部分制御語を読み飛ばし、共通部
分のみを処理する。

【００３０】また、比較後ファイル処理をマーキング方
式と呼ぶ処理方法を用いて実行することも可能である。 この方式では、オペレーティングシステムは図６に示す
フローチャートに従った処理を行う。まず、比較処理が
行われたファイルから共通部分を取り除き、その位置に
共通部分が存在することを示すマーキングを行う（ステ
ップＳ９）。次に、ファイルにヘッダーを付加し、それ
にファイルから取り除いた共通部分に関する情報を記録
する（ステップＳ１０）。ステップＳ９とステップＳ１
０によって処理されたファイルを固有ファイルと呼び、
その構造を図７に示す。最後に、固有ファイルを二次記
憶装置に保存して（ステップＳ１１）、比較後ファイル
処理の終了となる。

【００３１】具体的なマ−キングの方法として、共通部
分が抜き出された位置に特殊文字（これを共通部分指定
文字と呼ぶ）を記録し、その後ろに抜き出した共通部分
（共通ファイル）を指定する値を記録する。この値は、
例えば共通ファイルが保存されている二次記憶装置中の
先頭位置と末尾位置を示す値である。ここで、共通部分
指定文字とそれに続く値を共通部分指定語と呼ぶ。また
、ヘッダーにも共通ファイルが保存されている先頭位置
と末尾位置を示す値を記録する。従って、マーキング方
式によるファイル圧縮処理で作成される圧縮済ファイル
は一つの固有ファイルとそれが指定する共通ファイルか
ら構成される。例えば、オペレーティングシステムがマ
ーキング方式によって作成された圧縮済ファイルを更新
する場合、次のような処理を行うことで圧縮済ファイル
を通常のファイルと同等に扱うことができる。

【００３２】即ち、圧縮済ファイルの更新のためには、
固有ファイルが二次記憶装置から作業領域である主記憶
或いは二次仮想アドレス空間へ転送される。転送の際、
各ビット毎にそれが共通部分指定文字であるか否かの判
定を行い、共通部分指定文字であると判定された場合は
、共通部分指定語をそれが指定する共通部分と置き換え
る。つまり、共通部分指定語を取り除き、その位置に共
通部分の読み込みを行う。この処理によって、作業領域
に転送される固有ファイルは、ファイル圧縮処理を行う
前と同一のファイルに変換される。但し、固有ファイル
のヘッダーの転送は行わない。

【００３３】以上記述してきた方法によると、本発明の
ファイル圧縮処理を実現することが可能となる。次に、
上述した方法によって作成された圧縮済ファイルを削除
あるいは更新するための処理と、圧縮済ファイルに対し
さらにファイル圧縮処理を行う場合の具体的な手順につ
いて説明する。

【００３４】インデツクス逐次型ファイル方式によって
作成された圧縮済ファイルを削除する場合、オペレーテ
ィングシステムは図８に示すフローチャートに従った処
理を行う。ユーザーが削除のコマンドと削除したい圧縮
済ファイルの名前を入力すると（ステップＳ１２）、オ
ペレーティングシステムは指定された圧縮済ファイルの
インデックスにアクセスし（ステップＳ１３）、レコー
ドが共通部分であるか固有部分であるかの判定を行う（
ステップＳ１４）。レコードが固有部分である場合、オ
ペレーティングシステムはそのレコード（固有部分）の
削除を行う（ステップＳ１５）。

【００３５】一方、レコードが共通部分である場合、オ
ペレーティングシステムはその共通ファイルの共通部分
制御語にアクセスし、共有ファイル数の書き替えを行う
（ステップＳ１６）。この場合は共有ファイル数を１つ
減らす。次に、共有ファイル数が０であるかないかの判
定を行い、共有ファイル数が０であればその共通部分を
削除する（この処理を零判定削除と呼ぶ）（ステップＳ
１７）。ユーザーが指定した圧縮済ファイルが所有する
全てのレコードに対して、ステップＳ１３からステップ
Ｓ１７までの処理が終わると、最後にインデックスが削
除され（ステップＳ１８）、圧縮済ファイルの削除が完
了する。

【００３６】マーキング方式による圧縮済ファイルを削
除する場合は、図９のフローチャートに従った処理が行
われる。まず、ユーザーが削除のコマンドと削除したい
圧縮済ファイルの名前を入力すると（ステップＳ１９）
、オペレーティングシステムは指定された圧縮済ファイ
ルの固有ファイルのヘッダーにアクセスし、共通ファイ
ルに関する情報を読み取る（ステップＳ２０）。次に、
共通ファイルの共有ファイル数を１つ減らして（ステッ
プＳ２１）、零判定削除を行う（ステップＳ２２）。最
後に、固有ファイルを削除して（ステップＳ２３）、圧
縮済ファイルの削除の終了となる。

【００３７】インデックス逐次型ファイル方式による圧
縮済ファイルに対する更新の手続きを、図１０に示すフ
ローチャートに従って説明する。ユーザーは圧縮済ファ
イルの編集のコマンドと圧縮済ファイル名を入力して（
ステップＳ２４）、圧縮済ファイルの編集を行う。 （ステップＳ２５）。編集が終った圧縮済ファイルを保
存する際、オペレーティングシステムはレコード毎にそ
の内部で変更が行われたかをチェックする（ステップＳ
２６）。レコード内で変更がなされなかった場合、その
レコードに対する処理は何も行わない。しかし、レコー
ド内で変更が行われた場合、レコードが共通部分である
か、固有部分であるかを判定し（ステップＳ２７）、レ
コードが固有部分であればそれを更新する（ステップＳ
２８）。

【００３８】一方、変更されたレコードが共通部分であ
る場合、そのレコードを固有部分として更新する（ステ
ップＳ２９）。つまり、共通部分制御語を取り除いた状
態で新たに保存する。そして、インデクッスの該当する
レコードの情報を、新たに保存したレコードを指定する
値に書き替える（ステップＳ３０）。さらに、変更され
る前の共通ファイルに対しては、共通部分制御語内の共
有ファイル数を１つ減らして（ステップＳ３１）、零判
定削除を行う（ステップＳ３２）。ステップＳ２６から
ステップＳ３２までの処理を圧縮済ファイルが所有する
全てのレコードに対して行って、圧縮済ファイルの更新
が完了となる。

【００３９】マーキング方式による圧縮済ファイルの更
新を行う場合、変更したファイルは通常のファイルとし
て保存する。そして、変更前の圧縮済ファイルが所有し
ていた共通ファイルの共有ファイル数を１つ減らし、零
判定削除を行う。従って、マーキング方式による圧縮済
ファイルに一旦更新が行われると、それはもはや圧縮済
ファイルではなく、通常のファイルに戻る。

【００４０】圧縮済ファイルに対するファイル圧縮処理
は、圧縮済ファイルを通常のファイルに戻した後、改め
て行う。圧縮済ファイルを通常のファイルに戻す処理は
次のような手順で行う。インデックス逐行型ファイル方
式で処理された圧縮済ファイルの場合、インデックスに
従ってレコードを一つのファイルにつなげ直す。その際
レコードが共通ファイルであれば、共通部分制御語を除
いた共通部分のみをつなげる。マーキング方式による圧
縮済ファイルの場合、共通部分指定語をそれが指定する
共通部分と置き換える。そして、圧縮済ファイルが所有
していた共通ファイルの共有ファイル数を１つ減らし、
零判定削除を行う。最後に、インデックス逐次型ファイ
ル方式の場合はインデックスを、マーキング方式の場合
はヘッダー部分を消去する。以上の手続きにより圧縮済
ファイルは通常のファイルに戻るため、その通常のファ
イルに対して改めてファイル圧縮処理を行う。

【００４１】これまで、処理される共通部分が１個であ
るという前提の下でファイル圧縮処理の説明を行ってき
たが、共通部分が複数個ある場合でもファイル圧縮処理
を実現するにあたり、何等支障を来すものではない。そ
のため、判定される共通部分が複数個ある場合の処理方
法について説明する。

【００４２】ｎ個のファイル中に、例えばｋ個の共通部
分が含まれている場合のファイル圧縮処理は、基本的に
は図２のフローチャートと同様の手続きでよいが、一部
異なる箇所がある。図２のステップＳ２においてｎ個の
ファイルが比較された結果、共通部分がｋ個判定された
場合、ステップＳ４がｋ回繰り返され、判定されたｋ個
の共通部分それぞれについて共通部分処理が行われる。 次に、ｎ個のファイルに対して比較後ファイル処理（ス
テップＳ５）が行われるが、インデックス逐次型ファイ
ル方式の場合、レコードのうちｋ個が共通部分になって
おり、マーキング方式の場合、固有ファイルにはｋ個の
共通部分指定語が記録される。またインデックスとヘッ
ダーには、ｋ個の共通部分全ての情報が記録される。こ
の比較後ファイル処理がｎ回繰り返され、ｎ個のファイ
ル全てに対する処理が終わると、ファイル圧縮処理が終
了する。

【００４３】比較処理はユーザーが指定したｎ個ファイ
ル全てに対して行うだけに限らず、その内の任意のファ
イル間で行われるものであってもよい。そのため、ファ
イル圧縮処理を行う際、比較するファイル数ｉを変化さ
せて、段階的に比較処理と共通部分処理を実行する。つ
まり、段階ｉにおいてはｉ個（ｉ≦ｎ）のファイル間で
比較を行い、そのｉ個のファイルに対する共通部分ｉを
判定して、共通部分処理を行う。ｉの値はｎからｍ（ｎ
≧ｍ≧２）まで減少方向へ変化させる。

【００４４】図１１のフローチャートを参照して、具体
的な処理の手順を説明する。ユーザーが、ファイル圧縮
処理のコマンドとｎ個のファイル名を入力する（ステッ
プＳ３３）と、まずオペレーティングシステムはｎ個の
ファイルに対して比較処理を行い（ステップＳ３４、ｉ
＝ｎ）、全ファイルの共通部分（共通部分ｎ）を判定し
（ステップＳ３５）、共通部分ｎがあれば共通部分処理
を行う（ステップＳ３６）。次に、任意のｎ−１個のフ
ァイル間において、共通部分ｎを除いた範囲で内容の比
較を行い（ステップＳ３４、ｉ＝ｎ−１）、共通部分ｎ
−１があれば、共通部分処理を実行する（ステップＳ３
６）。但し、ステップＳ３４からステップＳ３６までの
処理は、ｎＣｉ（ｎ個からｉ個選び出す組み合わせの数
）回繰り返す。つまり、ｉがｎ−１の時、繰り返しの回
数はｎＣｎ−１　＝ｎであり、全ての組み合わせのｎ−
１個のファイル間で、比較処理と共通部分処理を行う。

【００４５】このようにして、最終的にはｍ個（ｎ≧ｍ
≧２）のファイル間での比較処理と共通部分処理まで段
階別に処理を行う。最後に、入力したｎ個のファイルに
対して、そのファイル中で判定された全ての共通部分に
関する比較後ファイル処理を行い（ステップＳ３７）、
ファイル圧縮処理が終了される。以下、ファイル圧縮処
理に関する補助的な事項について記述する。

【００４６】（１）ファイル間の比較の結果、判定され
る共通部分のサイズが非常に小さい場合は、ファイル圧
縮処理の効果が十分得られないため、共通部分サイズの
下限値の指定が必要である。従ってこの場合、例えば下
限値を共通部分制御語のサイズと定める。

【００４７】（２）　共通部分処理において、共通ファ
イルの共通部分制御語に記録する情報は共有ファイル数
であるが、加えて、その共通ファイルを共有している圧
縮済ファイルの名前とその記憶位置を記録してもよい。

【００４８】（３）　インデックス逐次型ファイル方式
による比較後ファイル処理において、レコードのサイズ
が非常に大きい場合、それをさらにいくつかのレコード
に分割してもよい。

【００４９】（４）　マーキング方式による比較後ファ
イル処理において、固有ファイルの共通部分指定語中で
共通部分指定文字に続いて記録される値は、共通ファイ
ルを指定できる値であればよいため、例えば共通ファイ
ルが保存されている先頭位置と末尾位置を示す値を記録
するか、若しくは共通ファイルの名前を記録してもよい
。但し、共通部分指定語に共通ファイルの名前を記録し
た場合、ヘッダーには共通ファイルの先頭位置と末尾位
置を示す値に加えて、共通ファイルの名前も記録しなけ
ればならない。

【００５０】（５）　オペレーティングシステムはファ
イル圧縮処理を終了する前に、ユーザーに対して処理状
況を知らせてもよい。例えば、ユーザ−がオンラインで
操作を行っている場合、端末の画面に処理状況をメッセ
ージとして表示する。即ち、共通部分が判定された場合
、判定された共通部分の名前或いは番号とその共通部分
を共有する圧縮済ファイル名のリストを、共通部分が判
定されなかった場合、共通部分がなかったという内容の
メッセージを表示してもよい。

【００５１】（６）　比較するファイル数を減少させな
がら、共通部分の判定と共通部分処理を段階的に行う場
合のファイル圧縮処理（図１１）において、最終段階で
比較されるファイルの個数ｍは暗黙に指定がなされてい
てもよいし、ユーザーが指定し直すことができてもよい
。

【００５２】（７）　ｎ個のファイル間の共通部分ｎを
判定する方法として、例えば次のような手順がある。ｎ
個のファイルに番号付けを行い、まず１番目と２番目の
ファイルを比較して、共通部分を抽出する。次に、抽出
した共通部分と３番目のファイルを比較して、同じく共
通部分を抽出する。このようにファイルを一つずつ順番
に比較していき、最後のｎ−１個のファイル間での共通
部分とｎ番目のファイルを比較して、共通部分ｎを判定
する。よって共通部分ｎが判定された場合、１番目から
ｉ番目（２≦ｉ≦ｎ−１）までのファイル間では、既に
比較が行われ共通部分が抽出されている。ここで、共通
部分ｎを判定する過程で抽出されるこれらの共通部分を
仮共通部分と呼ぶ。ところで、共通部分の判定と共通部
分処理を段階的に行う場合のファイル圧縮処理（図１１
）では比較するファイル数を減少方向に変化させるため
、共通部分ｉを判定する段階では、共通部分ｎから共通
部分ｉ＋１までは判定済みとなっている。従って、上記
の方法で共通部分ｎを判定している場合には、幾つかの
仮共通部分が既に抽出されているため、ファイル圧縮処
理のステップ数を減らす目的で、抽出済みの仮共通部分
を共通部分ｉの判定のために再利用してもよい。

【００５３】（８）　１個のファイル内に共通部分が幾
つか存在する場合、このファイルに対し単独でファイル
圧縮処理を行ってもよい。これを実現するためには、ユ
ーザーがファイル圧縮処理のコマンドとファイル名を一
つ入力し、一つのファイル内だけで内容の比較を行って
共通部分１を判定してもよいし、或いは図１１のファイ
ル圧縮処理において、最終的に比較するファイル数ｍを
１としてもよい。

【００５４】（９）　本発明におけるファイル圧縮方式
は、従来行われているデータ圧縮技術（Ｈｕｆｆｍａｎ
　の最適符号化法、Ｚｉｖ　−Ｌｅｍｐｅｌ　のデータ
圧縮法など）とは全く異質の処理方法であるため、ファ
イル圧縮処理を行った後、圧縮済ファイルに対してさら
に従来のデータ圧縮を行うことに何等問題はない。さら
に、ファイル圧縮処理における変形例をいくつか説明す
る。

【００５５】圧縮済ファイルに対する更新処理の特殊な
場合として、共通部分の更新が考えられる。これは共通
部分そのものを書き替えてしまう処理であり、この処理
を行うことにより、その共通部分を含む圧縮済ファイル
は共通部分の内容が一斉に変更されることになる。共通
部分を更新するためには、共通部分制御語の変更は行わ
ず、そのまま更新を行えばよい。このように、同じ内容
を含んでいる複数のファイルに対して、その共通部分の
一括変更を希望する場合、ファイル圧縮処理と共通部分
の更新を総合した処理（これをファイル一括変更と呼ぶ
）を行うと非常に便利である。

【００５６】ファイルの一括変更は、図１２に示すフロ
ーチャートに従って行われる。初めに、ユーザーはファ
イル一括変更のコマンドと一括変更を希望するｎ個のフ
ァイル名を入力する（ステップＳ３８）。オペレーティ
ングシステムはそれらのファイルに対しファイル圧縮処
理を行い（ステップＳ３９）、共通部分の名前或いは番
号とそれを共有している圧縮済ファイル名のリストを表
示する（ステップＳ４０）。次に、ユーザーは更新した
い共通部分の編集を行い（ステップＳ４１）、オペレー
ティングシステムはその修正された共通部分を更新する
（ステップＳ４２）。この共通部分の修正と更新は繰り
返し行うことが可能である。更新したい共通部分がなく
なれば処理を終了する。

【００５７】また、ファイル圧縮処理をコピー処理とし
て用いることも可能である。この処理の手順を図１３に
示すフローチャートを参照して説明する。まず、ユーザ
ーはコピー（ファイル圧縮処理による）のコマンドとコ
ピー元とコピー先のファイル名を入力する（ステップＳ
４３）。オペレーティングシステムはコピーするファイ
ル全体を共通部分とみなし（ステップＳ４４）、共通部
分処理（ステップＳ４５）において、共有ファイル数を
２と記録する。さらに、比較後ファイル処理（ステップ
Ｓ４６）を２回行って、コピー元とコピー先の圧縮ファ
イルを作成する。

【００５８】インデックス逐次型ファイル方式による比
較後ファイル処理の場合、図４のステップＳ６の処理は
必要はなく、インデックスに記録される情報は一つのレ
コード（共通ファイル）の情報のみである（ステップＳ
７）。そして、ステップＳ８ではインデックスのみが保
存される。また、マーキング方式による比較後ファイル
処理の場合、図６に示したフローチャートに従って処理
を行う。但し、この比較後ファイル処理で作成される固
有ファイルはヘッダーと共通部分指定語のみから構成さ
れる。以上のような処理を行うことによって、二次記憶
装置には共通部分がただ一つ保存され、それをコピー元
とコピー先の圧縮済ファイルが共有することになる。

【００５９】なお、本発明は上述した実施例に限定され
るものではない。実施例ではファイルを格納する記憶部
として磁気ディスクを用いたが、この代わりには磁気テ
ープや光ディスク等の二次記憶装置（外部記憶装置）を
用いることができる。また、図１に示すファイル圧縮処
理部の構成は、ハードウェアによって実現してもよいし
、ソフトウェアによって実現してもよい。その他、本発
明の要旨を逸脱しない範囲で、種々変形して実施するこ
とができる。

【００６０】

【発明の効果】以上詳述したように本発明によれば、内
容が共通した部分を含むファイルが複数存在する場合に
、各ファイルを共通部分とこの共通部分を除いた非共通
部分とに分け、これらを二次記憶装置等の記憶部に独立
して格納している。従って、複数のファイルに共通の内
容を二次記憶装置に重複して記憶する等の不都合を避け
ることができ、二次記憶装置のより効率的な利用が可能
となるファイル圧縮装置を実現することが可能となる。

【図面の簡単な説明】

【図１】本発明の一実施例に係わるファイル圧縮装置の
概略構成を示すブロック図、

【図２】ファイル圧縮処理の基本的な手順を示すフロー
チャート、

【図３】共通ファイルの構造を示す模式図、

【図４】イ
ンデックス逐次型ファイル方式による比較後ファイル処
理を示すフローチャート、

【図５】インデックス逐次型ファイル方式によるファイ
ル圧縮処理で作成される圧縮ファイルの構造を示す模式
図、

【図６】マーキング方式による比較後ファイル処理を示
すフローチャート、

【図７】マーキング方式によるファイル圧縮処理で作成
される圧縮ファイルが持つ固有ファイルの構造を示す模
式図、

【図８】インデックス逐次型ファイル方式で処理された
圧縮ファイルを削除する手順を示すフローチャート、

【
図９】マーキング方式で処理された圧縮ファイルを削除
する手順を示すフローチャート、

【図１０】インデックス逐次型ファイル方式で処理され
た圧縮ファイルを更新する手順を示すフローチャート、

【図１１】比較するファイル数を変化させ、段階的に比
較処理と共通部分処理を行う場合のファイル圧縮処理の
手順を示すフローチャート、

【図１２】ファイル一括変更の手順を示すフローチャー
ト、

【図１３】ファイル圧縮処理をコピー処理として行う場
合の手順を示すフローチャート。

【符号の説明】

１０…ファイル圧縮処理部、 １１…比較処理部、 １２…共通部分処理部、 １３…ファイル処理部、 ２０…二次記憶装置（第１の記憶部）、３０…二次記憶
装置（第２の記憶部）。

Claims (1)

【特許請求の範囲】
1. 【請求項１】第１の記憶部に格納された複数のファイル
   に対しその内容を比較する手段と、該手段による比較結
   果で内容が一致している部分を抜き出す手段と、該手段
   により抜き出した共通部分を共通ファイルとして第１の
   記憶部又は第２の記憶部に格納する手段と、前記共通部
   分を抜き出した後のファイルを固有ファイルとして第１
   の記憶部又は第２の記憶部に格納する手段とを具備して
   なることを特徴とするファイル圧縮装置。