(57)【要約】【目的】データ量の少ない圧縮データを生成する。【構成】新ファイル中に圧縮対象窓が設定され，新ファイル中の圧縮対象窓に先行する位置に第１参照窓がそれぞれ設定される。また旧ファイルの文字列に第２参照窓が設定される（ステップ11）。圧縮対象窓中の文字列と第１参照窓中の文字列が比較され，一致する最長の文字列が検索される（ステップ12）。一致する文字列が検索されると（ステップ13でYES ），第１参照窓中の一致文字列の先頭の文字位置と文字列長を表す符号化データＡが生成されて記憶される（ステップ14）。さらに圧縮対象文字列と旧ファイル中の第２参照窓中の文字列についても同様の処理が行われ，符号化データＢが生成されて記憶される（ステップ15，ステップ16でYES ，ステップ17）。一致文字数の多い方の符号化データがパッチ・データ（圧縮データ）に採用される（ステップ21，22）。【選択図】  図２
2004201144.tif 000002
【特許請求の範囲】
【請求項１】
第１ファイル中の圧縮対象文字列と，上記圧縮対象文字列に先行する第１ファイル中の第１比較文字列とを比較して一致する最長の文字列を検索し，一致する文字列が検索された場合に，上記第１比較文字列における一致文字列の先頭の文字の位置と一致文字列の文字列長を符号化した第１符号化データを生成し，
第１ファイル中の圧縮対象文字列と，第２ファイル中の第２比較文字列とを比較して一致する最長の文字列を検索し，一致する文字列が検索された場合に，上記第２比較文字列における一致文字列の先頭の文字の位置と一致文字列の文字列長を符号化した第２符号化データを生成し，
圧縮対象文字列中の一致文字列を第１符号化データまたは第２符号化データを用いて表した，第１ファイルの圧縮データを生成する，データ圧縮方法。
【請求項２】
第１符号化データまたは第２符号化データによって表された一致文字列の文字数分，圧縮対象文字列，第１比較文字列および第２比較文字列をそれぞれスライドする，請求項１に記載のデータ圧縮方法。
【請求項３】
上記第１比較文字列における一致文字列の先頭の文字の位置および上記第２比較文字列における一致文字列の先頭の文字の位置は，上記圧縮対象文字列の位置に対する相対位置である，請求項２に記載のデータ圧縮方法。
【請求項４】
上記圧縮対象文字列について第１符号化データと第２符号化データの両方が生成された場合に，第１比較文字列における一致文字列の文字列長と，第２比較文字列における一致文字列の文字列長とを比較し，
文字列長が長い方についての第１符号化データまたは第２符号化データを用いて圧縮データを生成し，
文字列長が同じである場合には，第１符号化データまたは第２符号化データのいずれかを用いて圧縮データを生成する，請求項１から３のいずれか一項に記載のデータ圧縮方法。
【請求項５】
第１ファイル中の圧縮対象文字列と，上記圧縮対象文字列に先行する第１ファイル中の第１比較文字列とを比較して一致する最長の文字列を検索する第１の検索手段，
上記第１の検索手段によって一致する文字列が検索された場合に，上記第１比較文字列における一致文字列の先頭の文字の位置と一致文字列の文字列長を符号化した第１符号化データを生成する第１符号化データ生成手段，
第１ファイル中の圧縮対象文字列と，第２ファイル中の第２比較文字列とを比較して一致する最長の文字列を検索する第２の検索手段，
上記第２の検索手段によって一致する文字列が検索された場合に，上記第２比較文字列における一致文字列の先頭の文字の位置と一致文字列の文字列長を符号化した第２符号化データを生成する第２符号化データ生成手段，ならびに
圧縮対象文字列中の一致文字列を第１符号化データまたは第２符号化データを用いて表した第１ファイルの圧縮データを生成する圧縮データ生成手段を備えた，データ圧縮装置。
【請求項６】
第１符号化データまたは第２符号化データによって表された一致文字列の文字数分，圧縮対象文字列，第１比較文字列および第２比較文字列をスライドする手段を備えた，請求項５に記載のデータ圧縮装置。
【請求項７】
上記第１比較文字列における一致文字列の先頭の文字の位置および上記第２比較文字列における一致文字列の先頭の文字の位置は，上記圧縮対象文字列の位置に対する相対位置である，請求項６に記載のデータ圧縮装置。
【請求項８】
上記圧縮対象文字列について第１符号化データと第２符号化データの両方が生成された場合に，第１比較文字列における一致文字列の文字列長と，第２比較文字列における一致文字列の文字列長とを比較する比較手段をさらに備え，
上記圧縮データ生成手段は，
上記比較手段によって一致文字列の文字列長が長いと判定された方についての第１符号化データまたは第２符号化データを用いて圧縮データを生成し，
上記比較手段によって一致文字列の長さが同じと判定された場合には，第１符号化データまたは第２符号化データのいずれかを用いて圧縮データを生成する，請求項５から７のいずれか一項に記載のデータ圧縮装置。
【請求項９】
第１ファイル中の圧縮対象文字列と，上記圧縮対象文字列に先行する第１ファイル中の第１比較文字列とを比較して一致する最長の文字列を検索させ，一致する文字列が検索された場合に，上記第１比較文字列における一致文字列の先頭の文字の位置と一致文字列の文字列長を符号化した第１符号化データを生成させ，
第１ファイル中の圧縮対象文字列と，第２ファイル中の第２比較文字列とを比較して一致する最長の文字列を検索させ，一致する文字列が検索された場合に，上記第２比較文字列における一致文字列の先頭の文字の位置と一致文字列の文字列長を符号化した第２符号化データを生成させ，
圧縮対象文字列中の一致文字列を第１符号化データまたは第２符号化データを用いて表した第１ファイルの圧縮データを生成させるようにコンピュータを制御する，データ圧縮プログラム。
【請求項１０】
第２ファイルの一部を更新した第１ファイル中の圧縮対象文字列と，上記第２ファイル中の比較文字列とを比較して一致する最長の文字列を検索し，
一致する文字列が検索された場合に，上記比較文字列における一致文字列の先頭の文字の位置と一致文字列の文字列長を符号化した符号化データを生成し，
圧縮対象文字列を符号化データを用いて表した第１ファイルの圧縮データを生成する，データ圧縮方法。
【請求項１１】
第２ファイルの一部を更新した第１ファイル中の圧縮対象文字列と，上記第２ファイル中の比較文字列とを比較して一致する最長の文字列を検索する検索手段，
上記検索手段によって一致する文字列が検索された場合に，上記比較文字列における一致文字列の先頭の文字の位置と一致文字列の文字列長を符号化した符号化データを生成する符号化データ生成手段，および
圧縮対象文字列を，上記符号化データ生成手段によって生成された符号化データを用いて表した第１ファイルの圧縮データを生成する圧縮データ生成手段を備えた，データ圧縮装置。
【請求項１２】
第２ファイルの一部を更新した第１ファイル中の圧縮対象文字列と，上記第２ファイル中の比較文字列とを比較して一致する最長の文字列を検索させ，
一致する文字列が検索された場合に，上記比較文字列における一致文字列の先頭の文字の位置と一致文字列の文字列長を符号化した符号化データを生成させ，
圧縮対象文字列を符号化データによって表した第１ファイルの圧縮データを生成させるようにコンピュータを制御する，データ圧縮プログラム。
【請求項１３】
旧ファイルと旧ファイルの一部を更新した新ファイルとに基づいてパッチ・データを生成する方法であって，
新ファイル中の圧縮対象文字列と，上記圧縮対象文字列に先行する新ファイル中の第１比較文字列とを比較して一致する最長の文字列を検索し，一致する文字列が検索された場合に，上記第１比較文字列における一致文字列の先頭の文字の位置と一致文字列の文字列長を符号化した第１符号化データを生成し，
新ファイル中の圧縮対象文字列と，旧ファイル中の第２比較文字列とを比較して一致する最長の文字列を検索し，一致する文字列が検索された場合に，上記第２比較文字列における一致文字列の先頭の文字の位置と一致文字列の文字列長を符号化した第２符号化データを生成し，
圧縮対象文字列中の一致文字列を第１符号化データまたは第２符号化データを用いて表したパッチ・データを生成する，パッチ・データ生成方法。
【請求項１４】
旧ファイルと旧ファイルの一部を更新した新ファイルとに基づいてパッチ・データを生成する装置であって，
新ファイル中の圧縮対象文字列と，上記圧縮対象文字列に先行する新ファイル中の第１比較文字列とを比較して一致する最長の文字列を検索する第１の検索手段，
上記第１の検索手段によって一致する文字列が検索された場合に，上記第１比較文字列における一致文字列の先頭の文字の位置と一致文字列の文字列長を符号化した第１符号化データを生成する第１符号化データ生成手段，
新ファイル中の圧縮対象文字列と，旧ファイル中の第２比較文字列とを比較して一致する最長の文字列を検索する第２の検索手段，
上記第２の検索手段によって一致する文字列が検索された場合に，上記第２比較文字列における一致文字列の先頭の文字の位置と一致文字列の文字列長を符号化した第２符号化データを生成する第２符号化データ生成手段，ならびに
圧縮対象文字列中の一致文字列を第１符号化データまたは第２符号化データを用いて表したパッチ・データを生成するパッチ・データ生成手段を備えた，
パッチ・データ生成装置。
【請求項１５】
請求項１４に記載のパッチ・データ生成装置によって生成されたパッチ・データを記憶する記憶手段を備えたサーバと，クライアントとがネットワークを介して相互に接続されるビデオ・ゲーム・システムにおいて用いられる上記サーバであって，
クライアントから送信されるパッチ・データ送信要求に応答して，上記パッチ・データを上記クライアントに送信する送信手段を備えている，サーバ。
【請求項１６】
請求項１４に記載のパッチ・データ生成装置によって生成されたパッチ・データを記憶する記憶手段を備えたサーバと，クライアントとがネットワークを介して相互に接続されるビデオ・ゲーム・システムにおいて用いられる上記クライアントであって，
上記旧ファイルを記憶する記憶手段，
パッチ・データ送信要求を上記サーバに送信する送信手段，
上記サーバから送信される上記パッチ・データを受信する受信手段，および
上記受信手段によって受信されたパッチ・データと記憶手段に記憶された上記旧ファイルとに基づいて，上記新ファイルを生成する手段を備えている，
クライアント。
【発明の詳細な説明】
【０００１】
【技術分野】
この発明は，データ圧縮方法および装置に関する。
【０００２】
【従来例】
図15(A)，(B)を参照して，ＬＺ（Lempel-Ziv）方式に基づくデータ圧縮の基本的な考え方を説明する。ＬＺ方式に基づくデータ圧縮では，データ列中に繰返し現れるデータ列の一部を利用し，元データを復元できるようにデータ列を圧縮する。
【０００３】
非圧縮データ列が，文字列「An outcry in Spain is an outcry in vain」 （図15(A) 参照）であるとする（スペースも文字として扱う）。この文字列を先頭から順に見ていくと，「Spain 」に含まれる「in 」 （iと，nと，スペースの３文字）という文字列は，先行する文字列「An outcry in 」に含まれる「in 」と一致する文字列である。同様に，「・・・is an outcry in vain」に含まれる「n outcry in 」 は，先行する「An outcry in 」中の「n outcry in 」と一致する文字列である。最後の「vain」に含まれる「ain」は，先行する「Spain」に含まれる「ain」と一致する文字列である。
【０００４】
先行する文字列を有する文字列，上述の例の場合は，「in 」，「n outcry in」および「ain」のそれぞれが，先行する文字列の位置によって表わされる。
【０００５】
先行する文字列の位置を，たとえば，「＜−６，３＞」のように表す。＜−６，３＞は，６文字分文字列を遡って３文字分の文字列であることを意味する。
【０００６】
図15(A)において，先行する文字列を有する文字列（「in 」，「n outcry in 」および「ain」）について上述のように「＜＞」を用いて表すと，図15(A)の文字列は，「An outcry in Spa<-6,3>is a <-22,12>v<-21,3>」（図15(B)）のように表すことができる。
【０００７】
１文字分のビット数を８ビットとすると，図15(A) の文字列には39文字（スペースも１文字としてカウントする）が含まれているので，８×39＝312 ビットのデータ量となる。図15(B) において３つの「＜○，○＞」の部分のビット数を，たとえばそれぞれ13ビットとする（図15(A) の文字列を最大に遡るときに39文字分戻るので，遡る39文字分の文字数をカウントするために６ビットが必要，39文字分文字列を遡った場合に，39文字分（最大値）をカウントするためにさらに６ビットが必要，「＜○，○＞」であることを示すために１ビットを必要とすると，６＋６＋１＝13ビットのデータ量が必要となる）。図15(B) の文字列には，21文字分の文字と，３つの「＜○，○＞」を含むので，データ量は８×21＋13×３＝168＋39＝207ビットのデータ量となる。312ビットのデータ量のデータが207ビットのデータ量のデータによって表されている。すなわち，図15(B) の文字列は，図15(A) の文字列の約60％程度のデータ量に圧縮されている。
【０００８】
図15(B)の文字列（圧縮データ列）を伸長する場合には，図15(B)の文字列を先頭から見ていき，<-6,3>の部分は，６文字分文字列を遡って３文字分の文字列（in ） に置換する。次に<-22,12>の部分は，22文字分文字列を遡って12文字分の文字列（n outcry in ） に置換する。さらに<-21,3>の部分は，21文字分文字列を遡って３文字分の文字列（ain）に置換する。図15(A)と同じ文字列に戻る。このように，図15(B)（圧縮データ列）から図15(A)（非圧縮データ列）を完全に復元することができるので，ＬＺ方式のデータ圧縮は可逆的な圧縮方式である。
【０００９】
ＬＺ方式のさらなる特徴として，圧縮の対象となる文字列と，その文字列と比較される先行する文字列とが，非圧縮データ中の一定量（一定文字数）について設定される点があげられる。
【００１０】
図16および図17を用いて，ＬＺ方式のデータ圧縮をさらに説明する。
【００１１】
圧縮の対象となる文字列部分を５文字分とし，比較される先行する文字列部分も５文字分とする。圧縮の対象となる文字列部分および比較される先行する文字列部分は，次に説明するように，圧縮処理中において文字列の後ろの向きに順次スライドしていく。以下，圧縮の対象となる文字列部分の範囲を「圧縮対象窓」，比較される先行する文字列部分の範囲を「参照窓」と呼ぶ。図16および図17において，圧縮対象窓を実線によって，参照窓を破線によってそれぞれ枠で囲って示す。圧縮対象窓が位置する文字列の前の５文字分の範囲に，参照窓が位置する。
【００１２】
圧縮対象の文字列（非圧縮データ列）を「１２４４２６２３４２１２３４２６２３４２」とする。
【００１３】
はじめに圧縮対象窓を圧縮対象文字列の先頭から５文字分に位置させる。参照窓は圧縮対象窓の前の５文字分の範囲に位置するので，初期状態では，参照窓には圧縮対象文字列中の文字は入っていない（図16(A) ）。
【００１４】
圧縮対象窓中の５文字のうちの先頭から５文字，先頭から４文字，先頭から３文字，先頭から２文字，先頭から１文字を，参照窓中の文字列によって表すことができるかどうかが判断される。具体的には「１２４４２」と同じ文字列が参照窓中にあるか，「１２４４」と同じ文字列が参照窓中にあるか，「１２４」と同じ文字列が参照窓中にあるか，「１２」と同じ文字列が参照窓中にあるか，「１」と同じ文字列が参照窓中にあるかが，順番に判断される。
【００１５】
図16(A) では参照窓中に文字列がない。この場合には，符号化データとして圧縮対象窓中の先頭の１文字がそのまま用いられる。先頭の１文字が符号化データとされたので，圧縮対象窓と参照窓とがそれぞれ１文字分，文字列の後ろ向きにスライドする（図16(B) ）。
【００１６】
図16(D) を参照して，圧縮対象窓中の先頭の文字「４」は，参照窓中に存在する。圧縮対象窓中の先頭の文字「４」の位置を起点に，１文字分文字列を遡って１文字分を表す「＜−１，１＞」が，符号化データとして採用される。
【００１７】
図17(B) を参照して，圧縮対象窓中の先頭から２文字分の「４２」は，参照窓中に存在する。圧縮対象窓中の先頭の文字「４」の位置を起点に，５文字分遡って２文字分を表す「＜−５，２＞」が，符号化データとして採用される。
【００１８】
同様に，図17(D) を参照して，圧縮対象窓中の先頭から４文字分の「２３４２」は，参照窓中に存在する。圧縮対象窓中の先頭の文字「２」の位置を起点に，５文字分遡って４文字分を表す「＜−５，４＞」が，符号化データとして採用される。
【００１９】
上述のようにして，圧縮対象の文字列は，最終的には図17(F) に示す符号化データによって表される。
【００２０】
ＬＺ方式に基づくデータ圧縮を改良した方式，一例を挙げると，ＬＺ方式のデータ圧縮を高速に処理するための装置および方法等も提案されている（たとえば，特許文献１参照）。いずれにしても，従来のＬＺ（Lempel-Ziv）方式に基づくデータ圧縮処理は，一つの文字列中においてその文字列を圧縮することを基本としている。
【００２１】
【特許文献１】
特開平１０−１８７４１０号公報
【００２２】
【発明の開示】
この発明は，異なる２つの文字列を用いて，圧縮データを生成することを目的とする。
【００２３】
この発明はさらに，更新前の文字列と，更新前の文字列の一部を更新した更新後の文字列とを用いて，圧縮データを生成することを目的とする。
【００２４】
この発明によるデータ圧縮方法は，第１ファイル中の圧縮対象文字列（入力データ）と，上記圧縮対象文字列に先行する第１ファイル中の第１比較文字列（第１辞書データ）とを比較して一致する最長の文字列を検索し，一致する文字列が検索された場合に，上記第１比較文字列における一致文字列の先頭の文字の位置と一致文字列の文字列長を符号化した第１符号化データを生成する。さらに，第１ファイル中の圧縮対象文字列と，第２ファイル中の第２比較文字列（第２辞書データ）とを比較して一致する最長の文字列を検索し，一致する文字列が検索された場合に，上記第２比較文字列における一致文字列の先頭の文字の位置と一致文字列の文字列長を符号化した第２符号化データを生成する。そして，圧縮対象文字列中の一致文字列を第１符号化データまたは第２符号化データを用いて表した，第１ファイルの圧縮データを生成する。
【００２５】
この発明によるデータ圧縮装置は，第１ファイル中の圧縮対象文字列（入力データ）と，上記圧縮対象文字列に先行する第１ファイル中の第１比較文字列（第１辞書データ）とを比較して一致する最長の文字列を検索する第１の検索手段，上記第１の検索手段によって一致する文字列が検索された場合に，上記第１比較文字列における一致文字列の先頭の文字の位置と一致文字列の文字列長を符号化した第１符号化データを生成する第１符号化データ生成手段，第１ファイル中の圧縮対象文字列と，第２ファイル中の第２比較文字列（第２辞書データ）とを比較して一致する最長の文字列を検索する第２の検索手段，上記第２の検索手段によって一致する文字列が検索された場合に，上記第２比較文字列における一致文字列の先頭の文字の位置と一致文字列の文字列長を符号化した第２符号化データを生成する第２符号化データ生成手段，ならびに圧縮対象文字列中の一致文字列を第１符号化データまたは第２符号化データを用いて表した第１ファイルの圧縮データを生成する圧縮データ生成手段を備えている。
【００２６】
この発明によると，第１ファイル中に含まれる圧縮対象文字列と同じ文字列が，圧縮対象文字列に先行する第１比較文字列に含まれている場合に，第１比較文字列における一致文字列の位置を符号化した第１符号化データが生成される。さらに，圧縮対象文字列と同じ文字列が第２ファイル中の第２比較文字列に含まれている場合には，第２比較文字列における一致文字列の位置を符号化した第２符号化データが生成される。すなわち，この発明のデータ圧縮方法および装置では，従来のＬＺ方式によるデータ圧縮，すなわち第１ファイル中に含まれる先行する同一の文字列を利用したデータ圧縮に加えて，第２ファイル中に含まれる文字列を利用したデータ圧縮が行われる。
【００２７】
この発明は，第１ファイルが第２ファイルの一部に追加，変更または削除（以下，「追加，変更または削除」を包括的に「更新」という）を施したファイルである場合に，その効果が一層高められる。第１ファイルが第２ファイルの一部を更新したものである場合，第１ファイルには第２ファイルに含まれる文字列と同じ（同一）の文字列を多く含んでいる。この発明によると，更新前の第２ファイル中の第２比較文字列が用いられて，一致文字列の先頭の文字の位置と一致文字列の文字列長を符号化した第２符号化データが生成される。第１ファイルが第２ファイルの一部を更新したものである場合，文字列長が長い一致文字列について第２符号化データが生成される頻度が高い。生成される圧縮データの圧縮率を大幅に高めることができる。
【００２８】
このようにこの発明によると，圧縮対象文字列中の一致文字列を第１符号化データまたは第２符号化データによって表した第１ファイルの圧縮データが生成される。第１符号化データは第１ファイル中の先行する文字列を用いた符号化データであるので，従来のＬＺ方式と同様に，第１ファイルのみによって第１符号化データから元の文字列を得ることができる。第２符号化データは，第２ファイル中の文字列を用いた符号化データであるので，第２符号化データから元の文字列を得る場合には第２ファイルが存在することが必要とされる。すなわち，この発明によって得られる第２符号化データを含む圧縮データは，第２ファイルが存在することを前提として伸張する（第１ファイルを得る）ことができるデータであると言える。
【００２９】
一般的には，第１ファイルに含まれる文字列の一部が圧縮対象文字列とされ，第１ファイルに含まれる文字列の一部が第１比較文字列とされる。また，第２ファイルに含まれる文字列の一部が第２比較文字列とされる。好ましくは，圧縮対象文字列中の一致文字列について第１符号化データまたは第２符号化データが生成された場合，符号化された一致文字列の文字数分，圧縮対象文字列，第１比較文字列および第２比較文字列がスライド（シフト）する（スライディング・ウインドウ；動的辞書法）。第１ファイル中の新たな圧縮対象文字列と，新たな第１比較文字列および新たな第２比較文字列とが比較される（同一の文字列が存在するかどうかが判断される）。この処理を繰返すことによって，第１ファイルに含まれるすべての文字列について圧縮処理が施されることになる。この場合には，上記第１比較文字列における一致文字列の先頭の文字の位置および上記第２比較文字列における一致文字列の先頭の文字の位置には，上記圧縮対象文字列の位置に対する相対位置が用いられる。
【００３０】
一実施態様では，上記圧縮対象文字列について第１符号化データと第２符号化データの両方が生成された場合には，第１比較文字列における一致文字列の文字列長と，第２比較文字列における一致文字列の文字列長とを比較し，文字列長が長い方についての第１符号化データまたは第２符号化データを用いて圧縮データを生成する。文字列長の長い一致文字列についての符号化データが用いられて圧縮データが生成されるので，高い圧縮率を実現することができる。文字列長が同じである場合には，第１符号化データおよび第２符号化データのいずれを用いても圧縮率は同じになるので，第１符号化データまたは第２符号化データのいずれか（いずれでもよい）を用いて圧縮データを生成する。
【００３１】
この発明を次のように表現することもできる。この発明によるパッチ・データの生成方法は，旧ファイルと旧ファイルの一部を更新した新ファイルとに基づいてパッチ・データを生成する方法であって，新ファイル中の圧縮対象文字列と，上記圧縮対象文字列に先行する新ファイル中の第１比較文字列とを比較して一致する最長の文字列を検索し，一致する文字列が検索された場合に，上記第１比較文字列における一致文字列の先頭の文字の位置と一致文字列の文字列長を符号化した第１符号化データを生成し，新ファイル中の圧縮対象文字列と，旧ファイル中の第２比較文字列とを比較して一致する最長の文字列を検索し，一致する文字列が検索された場合に，上記第２比較文字列における一致文字列の先頭の文字の位置と一致文字列の文字列長を符号化した第２符号化データを生成し，圧縮対象文字列中の一致文字列を第１符号化データまたは第２符号化データを用いて表したパッチ・データを生成する。
【００３２】
この発明によるパッチ・データ生成装置は，旧ファイルと旧ファイルの一部を更新した新ファイルとに基づいてパッチ・データを生成する装置であって，新ファイル中の圧縮対象文字列と，上記圧縮対象文字列に先行する新ファイル中の第１比較文字列とを比較して一致する最長の文字列を検索する第１の検索手段，上記第１の検索手段によって一致する文字列が検索された場合に，上記第１比較文字列における一致文字列の先頭の文字の位置と一致文字列の文字列長を符号化した第１符号化データを生成する第１符号化データ生成手段，新ファイル中の圧縮対象文字列と，旧ファイル中の第２比較文字列とを比較して一致する最長の文字列を検索する第２の検索手段，上記第２の検索手段によって一致する文字列が検索された場合に，上記第２比較文字列における一致文字列の先頭の文字の位置と一致文字列の文字列長を符号化した第２符号化データを生成する第２符号化データ生成手段，ならびに圧縮対象文字列中の一致文字列を第１符号化データまたは第２符号化データを用いて表したパッチ・データを生成するパッチ・データ生成手段を備えている。
【００３３】
この発明によると，旧ファイルと旧ファイルを更新した新ファイルとに基づいてパッチ・データが生成される。パッチ・データは，旧ファイルの存在を前提に新ファイルを生成するためのデータである。すなわち，パッチ・データに含まれる第１符号化データおよび第２符号化データについて，第１符号化データであれば先行する新ファイル中の文字列に置換え，第２符号化データであれば旧ファイル中の文字列に置換えることによって，新ファイルを生成することができる。たとえば，旧ファイルが存在するが新ファイルは存在しないコンピュータにおいて，パッチ・データが取得されることによって新ファイルを生成することができる。このように，パッチ・データは旧ファイルを新ファイルに更新するためのデータであると言える。
【００３４】
この発明は，上述のパッチ・データ生成装置によって生成されたパッチ・データを記憶する記憶手段を備えたサーバと，クライアントとがネットワークを介して相互に接続されるビデオ・ゲーム・システムにおいて用いられる上記サーバと，上記クライアント（ビデオ・ゲーム装置，パーソナル・コンピュータ等）も提供している。
【００３５】
この発明によるビデオ・ゲーム・システムにおいて用いられるサーバは，上述のパッチ・データ生成装置によって生成されたパッチ・データを記憶する記憶手段を備え，クライアントから送信されるパッチ・データ送信要求に応答して，上記パッチ・データを上記クライアントに送信する送信手段を備えたものである。
【００３６】
この発明によるビデオ・ゲーム・システムにおいて用いられるクライアントは，上記旧ファイルを記憶する記憶手段，パッチ・データ送信要求を上記サーバに送信する送信手段，上記サーバから送信される上記パッチ・データを受信する受信手段，および上記受信手段によって受信されたパッチ・データと記憶手段に記憶された上記旧ファイルとに基づいて，上記新ファイルを生成する手段を備えている。
【００３７】
サーバは，クライアントからのパッチ・データ送信要求に応答して，クライアントにパッチ・データを送信する。クライアントは旧ファイルを記憶しているので，旧ファイルとサーバから送信されたパッチ・データとに基づいて新ファイルを得ることができる。パッチ・データのデータ量は新ファイルのデータ量に比べて格段にデータ量が少ないので，サーバからクライアントに新ファイルを送信する場合に比べて，少ないデータ通信量でサーバからクライアントにパッチ・データを送信することができる。データ伝送時間を大幅に短縮することができる。
【００３８】
第１ファイル（新ファイル）中の先行する文字列（上述の第１比較文字列）を用いることなく，第２ファイル（旧ファイル）中の文字列（上述の第２比較文字列）のみを用いて符号化データを作成し，この符号化データを圧縮データに採用してもよい。この発明によるデータ圧縮方法は，第２ファイルの一部を更新した第１ファイル中の圧縮対象文字列と，上記第２ファイル中の比較文字列とを比較して一致する最長の文字列を検索し，一致する文字列が検索された場合に，上記比較文字列における一致文字列の先頭の文字の位置と一致文字列の文字列長を符号化した符号化データを生成し，圧縮対象文字列を符号化データを用いて表した第１ファイルの圧縮データを生成する。
【００３９】
この発明によるデータ圧縮装置は，第２ファイルの一部を更新した第１ファイル中の圧縮対象文字列と，上記第２ファイル中の比較文字列とを比較して一致する最長の文字列を検索する検索手段，上記検索手段によって一致する文字列が検索された場合に，上記比較文字列における一致文字列の先頭の文字の位置と一致文字列の文字列長を符号化した符号化データを生成する符号化データ生成手段，および圧縮対象文字列を，上記符号化データ生成手段によって生成された符号化データを用いて表した第１ファイルの圧縮データを生成する圧縮データ生成手段を備えたものである。
【００４０】
第１ファイルは第２ファイルの一部を更新したものであるので，生成される圧縮データに含まれる符号化データは一致文字長の長い文字列を表す頻度が高く，データ量の小さい圧縮データを得ることができる。
【００４１】
この発明は，上述の圧縮データの生成をコンピュータに実行させるためのプログラムも提供している。
【００４２】
【実施例の説明】
（１）パッチ・データ作成処理（圧縮処理）およびバージョン・アップ処理（伸張処理）
図１は，パッチ・データ作成処理（圧縮処理）とバージョン・アップ処理（伸張処理）を概念的に示すものである。
【００４３】
この実施例における圧縮処理は，旧ファイルと新ファイルの２つのファイルを利用して，新ファイルを圧縮した圧縮データを作成する処理である。伸張処理は旧ファイルと上述の圧縮処理によって作成された圧縮データとを利用して，新ファイルを得るための処理である。
【００４４】
圧縮処理によって作成される圧縮データは，旧ファイルを有し，かつ新ファイルを持たないコンピュータにおいて伸張処理によって新たに新ファイルを得るために用いられる。圧縮処理の対象とされる新ファイルは，一般には，旧ファイルの一部に追加，変更または削除（以下，追加，変更または削除を包括的に「更新」という）を施したものである。圧縮データは，旧ファイルから，旧ファイルを更新した新ファイルを得るために必要とされるデータと言える。以下の説明では，圧縮データを「パッチ・データ」と言うことにする。圧縮処理を「パッチ・データ作成処理」と言うことにする。
【００４５】
伸張処理は，旧ファイルとパッチ・データとに基づいて新ファイルを得るための処理である。伸張処理は，旧ファイルを新ファイルに更新するための処理と言える。以下の説明では，伸張処理を「バージョン・アップ処理」ということにする。
【００４６】
(i) パッチ・データ作成処理（圧縮処理）
図２はパッチ・データ作成処理の流れを示すフローチャートである。図３(A) 〜(D)および図４(A)〜(D) は，パッチ・データ作成処理の流れを，具体的に示すものである。
【００４７】
パッチ・データ作成処理は，上述のように，旧ファイルと新ファイルの２つのファイルを利用してパッチ・データを作成する処理である。パッチ・データ作成処理はコンピュータによって実行される。パッチ・データ作成処理を実行するコンピュータには，旧ファイルと，新ファイルと，パッチ・データ作成プログラムがあらかじめ用意される。
【００４８】
パッチ・データ作成処理は，新ファイルの文字列中に繰返し出現する文字列と，旧ファイル中に出現する新ファイルと同じ文字列とを利用して，新ファイルの文字列を圧縮する処理である。後述するように，パッチ・データ作成処理では，新ファイルに含まれる文字列のうちの一部についての圧縮が連続して行われる。この実施例では，新ファイル中に含まれる文字列のうち圧縮処理の対象となる文字列部分を５文字分とする。また後述するように，圧縮処理対象の文字列部分は，同じ新ファイル中の先行する文字列部分と比較される。比較される先行する文字列部分も５文字分とする。新ファイルにおいて圧縮処理対象となる文字列部分の範囲を「圧縮対象窓」，比較される先行する文字列部分の範囲を「第１参照窓」と呼ぶ。
【００４９】
旧ファイル中にも，圧縮処理対象の文字列部分と比較される文字列部分が設けられる。旧ファイルにおいて比較される文字列部分の範囲を「第２参照窓」と呼ぶ。第２参照窓の範囲は１０文字分とする。
【００５０】
後述するように，圧縮対象窓，第１参照窓，第２参照窓は，文字列の後ろ向きに順次スライドする。圧縮対象窓がスライドすることによって，新ファイル中のすべての文字列について圧縮処理が施される。
【００５１】
図３および図４を参照して具体的に説明する。旧ファイルを「１２４４５４２３４３０２３４２６２３４２」とする。新ファイルを「１２４４２６２３４２１２３４２６２３４２」とする。
【００５２】
はじめに，圧縮対象窓を新ファイルの先頭から５文字分「１２４４２」に位置させる。第１参照窓は圧縮対象窓の前の５文字分に位置させる（初期状態において，第１参照窓には新ファイル中の文字列は入っていない）。さらに，旧ファイルにおいて１０文字分の第２参照窓を位置させる。第２参照窓の位置は，第１参照窓および圧縮対象窓を合わせた位置と同じ位置とする（図３(A) ）。コンピュータ処理の観点から言えば，コンピュータのメモリのバッファ・エリアに，圧縮対象窓中の文字列，第１参照窓中の文字列，第２参照窓中の文字列が記憶される（ステップ11）。
【００５３】
はじめに，圧縮対象窓中の５文字分の文字列「１２４４２」のうち，先頭から５文字「１２４４２」，４文字「１２４４」，３文字「１２４」，２文字「１２」，１文字「１」と一致する文字列が，第１参照窓の文字列に含まれているかどうか順次検索される（ステップ12）。
【００５４】
圧縮対象窓中の文字列と一致する文字列が第１参照窓に含まれている場合には（ステップ13でYES ），一致する文字列が符号化データによって表される（詳しくは，後述する）。第１参照窓中の文字列が用いられて作成された符号化データを「符号化データＡ」と呼ぶ。符号化データＡはコンピュータのメモリに一時的に記憶される。
【００５５】
図３(A) の例では，第１参照窓中に文字列がないので圧縮対象窓中の文字列と一致する文字列は第１参照窓中の文字列には含まれていない（ステップ13でNO）。
【００５６】
次に，圧縮対象窓中の５文字分の文字列のうち，先頭から５文字，４文字，３文字，２文字，１文字と一致する文字列が，第２参照窓の文字列に含まれているかどうか順次検索される（ステップ15）。
【００５７】
図３(A) の例では，圧縮対象窓中の先頭から４文字「１２４４」が，第２参照窓中に存在する。旧ファイルの第２参照窓において「１２４４」の４文字分の位置を表す「＜旧，０，４＞」が符号化データとしてコンピュータのメモリに一時的に記憶される（ステップ16でYES ，ステップ17）。「＜旧，０，４＞」は，旧ファイルの第２参照窓中の文字列であって，０文字目の位置（圧縮対象用窓中の先頭の文字に対応する位置にある第２参照窓中の文字の位置）を起点にして，４文字分の文字列（すなわち「１２４４」；一致文字数は「４」）であることを表す。第２参照窓中の文字列が用いられて作成される符号化データを「符号化データＢ」と呼ぶ。
【００５８】
符号化データＡおよび／または符号化データＢがメモリに一時的に記憶された場合には（ステップ18でYES ），第１参照窓中の文字列を用いた符号化データＡと第２参照窓中の文字列を用いた符号化データＢとにおいて，一致文字数（一致文字列長）が比較される（ステップ19）。符号化データＡまたは符号化データＢのうち，一致文字数がより多い方が符号化データとして採用される（ステップ21またはステップ22）。
【００５９】
新ファイルのすべての文字列について圧縮処理を終えたかどうかが判断される（ステップ23）。圧縮処理すべき文字列が残っている場合には（ステップ23でNO），圧縮対象窓，第１参照窓および第２参照窓が文字列の後ろの方向にスライドする（ステップ24）。図３(A) の例の場合には，圧縮対象窓中の４文字分が符号化データとされたので，圧縮対象窓，第１参照窓および第２参照窓がそれぞれ４文字分，文字列の後ろ向きにスライドする（図３(B) ）。
【００６０】
新たに圧縮対象窓中に含まれるようになった５文字分の文字列について，上述と同様に，第１参照窓または第２参照窓中の文字列に同一の文字列が含まれているかどうかが判断される。
【００６１】
図３(B) を参照して，圧縮対象窓中の５文字分の文字列「２６２３４」のうち，先頭から５文字「２６２３４」，４文字「２６２３」，３文字「２６２」，２文字「２６」，１文字「２」と一致する文字列が，第１参照窓中の文字列にあるかどうかが順次判断され（ステップ12），さらに第２参照窓中の文字列にあるかどうかが順次判断される（ステップ15）。
【００６２】
圧縮対象窓中の先頭の文字「２」は，第１参照窓および第２参照窓のいずれにも含まれている。符号化データＡおよび符号化データＢがメモリに一時的に記憶される。符号化データＡの一致文字数と符号化データＢの一致文字数が同じである場合には，第１参照窓中の文字列を用いた符号化データＡが符号化データとして採用される（ステップ19でＡ≧Ｂ，ステップ21）（図２(B) において「＜新，−３，１＞」）。「＜新，−３，１＞」は，新ファイルの第１参照窓中の文字列であって，圧縮対象窓中の先頭の文字を起点にして３文字分文字列を遡って１文字分の文字列であることを意味する。
【００６３】
符号化データよりも，圧縮対象窓中の文字列をそのまま用いた方がデータ量が少ないような場合には，圧縮対象窓中の文字列をそのまま用いるようにしてもよい。具体的に言うと，上述の例の場合には，＜新，−３，１＞を符号化データとする（「＜新，−３，１＞」によって文字列「２」を表す）のに代えて，文字列「２」を符号化データとして用いてもよい。
【００６４】
圧縮対象窓中の１文字分が符号化データとされたので，圧縮対象窓，第１参照窓および第２参照窓がそれぞれ１文字分，文字列の後ろ向きにスライドする（ステップ24，図３(C) ）。
【００６５】
図３(C) を参照して，圧縮対象窓中の文字列「６２３４２」，「６２３４」，「６２３」，「６２」および「６」のいずれも第１参照窓および第２参照窓に含まれていない（ステップ18でNO）。この場合には圧縮対象窓中の先頭の１文字が符号化データとされる。すなわち，圧縮対象用窓中の文字列が「６２３４２」の場合には，その先頭の文字「６」が符号化データとされる（ステップ20）。
【００６６】
圧縮対象窓中の１文字分が符号化データとされたので，圧縮対象窓，第１参照窓および第２参照窓がそれぞれ１文字分，文字列の後ろ向きにスライドする（図３(D) ）。
【００６７】
図３(D) を参照して，圧縮対象窓中の文字列「２３４２１」のうち，先頭の１文字「２」は第１参照窓中に含まれている（符号化データＡは＜旧，−５，１＞または＜旧，−２，１＞）（ステップ13でYES ）。符号化データＡ「＜旧，−５，１＞」または「＜旧，−２，１＞」がメモリに一時的に記憶される（ステップ14）。また，圧縮対象窓中の先頭から３文字「２３４」は，第２参照窓に含まれている（符号化データＢは＜旧，０，３＞）（ステップ16でYES ）。符号化データＢ「＜旧，０，３＞」がメモリに一時的に記憶される（ステップ17）。符号化データＢの方が符号化データＡよりも一致文字数は多いので，符号化データＢ「＜旧，０，３＞」が符号化データとして採用される（ステップ19でＡ＜Ｂ，ステップ22）。圧縮対象窓，第１参照窓および第２参照窓がそれぞれ３文字分，文字列の後ろ向きにスライドする（図４(A) ）。
【００６８】
図４(A) を参照して，圧縮対象窓中の先頭の１文字「２」は，第１参照窓および第２参照窓のいずれにも含まれている。第１参照窓中の「２」の位置を表す符号化データが採用される（図４(A) において「＜新，−５，１＞」）（ステップ19でＡ≧Ｂ，ステップ21）。圧縮対象窓，第１参照窓および第２参照窓がそれぞれ１文字分，文字列の後ろ向きにスライドする（図４(B) ）。
【００６９】
図４(B) を参照して，圧縮対象窓中の「１２３４２」，「１２３４」，「１２３」，「１２」および「１」のいずれも第１参照窓および第２参照窓に含まれていない。符号化データとして圧縮対象窓中の先頭の１文字「１」が用いられる（ステップ18でNO，ステップ20）。圧縮対象窓，第１参照窓および第２参照窓がそれぞれ１文字分，文字列の後ろ向きにスライドする（図４(C) ）。
【００７０】
図４(C) を参照して，圧縮対象窓中の「２３４２６」は第２参照窓中に含まれている。「＜旧，０，５＞」が符号化データとされる（ステップ19でＡ＜Ｂ，ステップ22）。圧縮対象用窓，第１参照窓および第２参照窓がそれぞれ５文字分，文字列の後ろ向きにスライドする（図４(D) ）。
【００７１】
図４(D) を参照して，圧縮対象用窓中の「２３４２」は第１参照用窓にも，第２参照用窓にも含まれている。「＜新，−５，４＞」が符号化データとして採用される（ステップ19でＡ≧Ｂ，ステップ21）。
【００７２】
新ファイル中のすべての文字列について圧縮処理が終了すると，パッチ・データ作成処理が終了する（ステップ23でYES ）。図４(D) に示す符号化データが「パッチ・データ」である。
【００７３】
１文字分のビット数を８ビットとすると，図３および図４に示す新ファイルには20文字含まれているので，８×20＝160 ビットのデータ量となる。ここで，図４(D) のパッチ・データにおいて，符号化データ「＜○，○，○＞」の部分のビット数を，たとえば９ビットとする（第２参照窓において文字列の位置を表すのに４ビットが必要，最大５文字分をカウントするために３ビットが必要，「＜＞」であることを示すために１ビットが必要，新または旧（第１参照用窓中の文字列であるか，第２参照用窓中の文字列であるか）の区別に１ビットが必要とすると，４＋３＋１＋１＝９ビットのデータ量が必要となる）。図４(D) に示すパッチ・データには，２文字分の文字と，６つの「＜○，○，○＞」を含むので，データ量は８×２＋６×９＝70ビットのデータ量となる。パッチ・データは，新ファイルのデータ量の約４０％程度のデータ量となる。
【００７４】
(ii)バージョン・アップ処理（伸張処理）
バーション・アップ処理は，上述したように，旧ファイルとパッチ・データとを用いて，新ファイルを作成する処理である。図５は，図４(D) に示す旧ファイルとパッチ・データを用いて新ファイルを作成する処理を具体的に示すものである。バージョン・アップ処理は，バーション・アップ・プログラムを有するコンピュータにおいて実行される。バージョン・アップ・プログラムが実行されることによってバージョン・アップ処理が進行する。
【００７５】
パッチ・データを先頭から見ていく。＜旧，０，４＞の部分は，旧ファイルの文字列の先頭から４文字分と置換される（「１２４４」）。＜新，−３，１＞は，作成途中の新ファイルにおいて３文字分遡って１文字分の文字列と置換される（「１２４４２」）。次の「６」はそのまま「６」が用いられる（「１２４４２６」）。＜旧，０，３＞は，旧ファイルの文字列の０文字目から３文字分と置換される。６文字分まで新ファイルが完成しているので旧ファイルの文字列の０文字目は，旧ファイルの文字列のうち先頭から６文字分を除いた次の文字（７文字目）になる（「１２４４２６２３４」）。＜新，−５，１＞は，作成途中の新ファイルにおいて５文字分遡って１文字分の文字列と置換される（「１２４４２６２３４２」）。次の「１」はそのまま「１」が用いられる（「１２４４２６２３４２１」）。＜旧，０，５＞は旧ファイルの文字列の０文字目（11文字分まで新ファイルが完成しているので，０文字目は旧ファイルの12文字目になる）から５文字分と置換される（「１２４４２６２３４２１２３４２６」）。＜新，−５，４＞は，作成途中の新ファイルにおいて５文字分遡って４文字分と置換される（「１２４４２６２３４２１２３４２６２３４２」）。このようにして，旧ファイルとパッチ・データとから，新ファイルを得ることができる。
【００７６】
旧ファイルと新ファイルの両方を有し，かつパッチデータ作成処理プログラムを有するコンピュータをコンピュータＡとする。旧ファイルを有し，バージョン・アップ・プログラムを有するコンピュータをコンピュータＢとする。上述のように，コンピュータＡでは新ファイルと旧ファイルとに基づいてパッチ・データを作成することができる。コンピュータＡからコンピュータＢにパッチ・データを送信することによって，コンピュータＢにおいてはバーション・アップ・プログラムによって新ファイルを得ることができる。上述のように，パッチ・データのデータ量は，新ファイルのデータ量よりも格段に少ない。新ファイルそのものをコンピュータＡからコンピュータＢに送信する場合に比べて，少ないデータ通信量でコンピュータＢにおいて新ファイルを得ることができる。データ伝送時間を大幅に短縮することができる。
【００７７】
（２）応用例
図６は，ネットワークを利用したビデオ・ゲーム・システムのブロック図を示している。このビデオ・ゲーム・システムは，上述のパッチ・データ作成処理およびバージョン・アップ処理を利用して，ユーザの所有するビデオ・ゲーム装置のハードディスクに記憶されているビデオ・ゲームを，バージョン・アップさせることができるシステムである。
【００７８】
ネットワークを利用したビデオ・ゲーム・システムは，ネットワーク１と，サーバ・コンピュータ２（以下，サーバ２という）と，複数のビデオ・ゲーム装置３とから構成される。
【００７９】
ネットワークを利用したビデオ・ゲーム・システムでは，後述するように，サーバ２においてビデオ・ゲームのためのプログラムまたはデータについてのバージョン・アップが行われた場合に，サーバ２において上述のパッチ・データ作成処理が行われ，パッチ・データが作成される。このパッチ・データがユーザの所有するビデオ・ゲーム装置３にネットワーク１を介して送信（配信）される。ビデオ・ゲーム装置３において，上述のバージョン・アップ処理が行われることによって，ビデオ・ゲーム装置３には最新のプログラムまたはデータが保存される。
【００８０】
図７は，ビデオ・ゲーム装置３の全体的構成を示している。図８はビデオ・ゲーム装置３の電気的構成を示すブロック図である。
【００８１】
ビデオ・ゲーム装置３は，ゲーム機本体31，表示画面上に現れるポインタ等を操作するためのコントローラ32，ゲームの進行状態等を記録するためのメモリ・カード33およびゲーム機本体から出力される画像データおよび音声データの入力を受付け，受付けた画像データによって表される画像を表示画面上に表示し，音声データによって表される音声をスピーカから出力する出力装置（スピーカを持つ表示装置等）34を含む。ゲーム機本体31の前端面には，ビデオ・ゲームのためのプログラムおよびデータ等が記録されたＤＶＤ−ＲＯＭ（またはＣＤ−ＲＯＭ）（以下，単にＤＶＤという）35を装填するためのディスク・トレイ36が設けられている。ＤＶＤ35はこのディスク・トレイ36上に載置される。ディスク・トレイ36の右側には，リセット・ボタン37およびエジェクト・ボタン38が設けられている。リセット・ボタン37はゲーム機本体31のＲＡＭを初期化する（リセットする）ために用いられる。エジェクト・ボタン38はディスク・トレイ36の開閉に用いられる。さらにゲーム機本体31の前端面には，メモリ・カード33を接続するためのメモリ・カード・スロット39，コントローラ32を接続するためのコントローラ・コネクタ40，外部機器等を接続するためのＵＳＢ（Universal Serial Bus）コネクタ41がそれぞれ２つずつ設けられている。図７では，メモリ・カード・スロット39にメモリ・カード33が，コントローラ・コネクタ40にコントローラ32が，それぞれ１つずつ接続されている。
【００８２】
図８を参照して，ゲーム機本体31はＣＰＵ51を含む。ＣＰＵ51はゲーム機本体31の動作を統括的に制御する。ＣＰＵ51にはバス54を介して，ワーク・エリア，バッファ・エリア，カウンタ・エリア等を提供するＲＡＭ52，ＤＶＤ35に記録されたプログラムおよびデータを読出すＤＶＤ−ＲＯＭドライブ53，ＤＶＤ35，ＲＡＭ52，ハードディスク59等に記憶されたサウンド・データを処理して出力装置34に出力するサウンド処理回路55，ＤＶＤ35，ＲＡＭ52，ハードディスク59等に記憶されたグラフィック・データを処理して出力装置34に出力するグラフィック処理回路56，ネットワーク１を通じてデータ等を送受信するための通信装置58とバス54との間，およびコントローラ32とバス54との間のデータの送受信を制御するインターフェース回路57，オペレーティング・システム，ブラウザ，ビデオ・ゲーム・プログラムおよびデータ，バージョン・アップ・プログラム等が記憶されたハードディスク（ＨＤ）59がそれぞれ接続されている。
【００８３】
ハードディスク59に記憶されているビデオ・ゲーム・プログラムおよびデータは，ＤＶＤ−ＲＯＭドライブ53によってＤＶＤ35から読取られてインストールされたものと，後述するようにして，ネットワーク１を介してサーバ２から送信されたパッチ・データを，バージョン・アップ・プログラムによって処理することによって得られるプログラムまたはデータを含む。
【００８４】
図９は，サーバ２の電気的構成を示すブロック図である。
【００８５】
サーバ２は，サーバ２を統括的に制御するＣＰＵ61を含む。ＣＰＵ61にデータ入力等に用いられる入力装置（キーボード，マウス等）62，文字，画像等を可視的に出力する表示装置（ＬＣＤディスプレイ等）63，ワーク・エリア，バッファ・エリア等を提供するメモリ64，ネットワーク１を通じてデータ等を送受信するための通信装置65，ならびにプログラムおよびデータを記憶するハードディスク66が接続されている。
【００８６】
ハードディスク66には，ビデオ・ゲームのためのプログラムおよびデータと，パッチ・データと，パッチ・データ作成プログラムとが記憶されている。
【００８７】
ビデオ・ゲームのためのプログラムおよびデータは，複数のプログラム・ファイルおよびデータ・ファイルによって構成される。一般的には，ハードディスク66には，複数の種類のビデオ・ゲームのそれぞれについて複数のプログラム・ファイルおよびデータ・ファイルが記憶されているが，説明を簡単にするために，この実施例では，一種類のビデオ・ゲーム（以下，「コンテンツＡ」と呼ぶ）のためのプログラム・ファイルおよびデータ・ファイルが記憶されているものとする。
【００８８】
さらに，ハードディスク66には，一つのコンテンツＡについて，異なるバージョンのものが記憶されている。すなわち，サーバ２において，コンテンツＡに含まれる複数のプログラム・ファイルおよびデータ・ファイルのうち，一または複数のプログラム・ファイルおよびデータ・ファイルについて修正，追加，削除等（更新）が行われる（バージョン・アップ）と，更新前のコンテンツＡと，更新後のコンテンツＡとがハードディスク66に記憶される。コンテンツＡはバージョン番号を持つ。更新が行われる度にコンテンツＡのバージョンがインクリメントされる（バージョン１からバージョン２へのバージョン・アップ，バージョン２からバージョン３へのバージョン・アップ等）。
【００８９】
コンテンツＡについてバージョン・アップが行われると，更新されたファイル（プログラム・ファイルおよび／またはデータ・ファイル）と，更新前のファイルとが用いられて，パッチ・データが作成される。パッチ・データの作成は，ハードディスク66に記憶されたパッチ・データ作成プログラムの処理にもとづく。サーバ２において実行されるパッチ・データ作成プログラムの処理は，図２を参照して説明した処理と同じ処理である。作成されたパッチ・データもハードディスク66に記憶される。
【００９０】
図10は，ネットワークを用いたビデオ・ゲーム・システムにおけるビデオ・ゲーム装置３とサーバ２のそれぞれの処理と，これらの間のデータ通信の流れを示すフローチャートである。図10に示す処理のためのプログラムおよびデータは，ビデオ・ゲーム装置３とサーバ２のそれぞれにあらかじめ記憶されているものとする。
【００９１】
ユーザの所有するビデオ・ゲーム装置３のゲーム機本体31に内蔵されているハードディスク59には，ビデオ・ゲーム（コンテンツＡとする）のためのプログラム・ファイルおよびデータ・ファイルが記憶されているものとする。すなわち，ユーザは，コンテンツＡのプログラム・ファイルおよびデータ・ファイルが記録されたＤＶＤ35を購入し，購入したＤＶＤ35をＤＶＤ−ＲＯＭドライブ53に装着する。ＤＶＤ35に記録されているコンテンツＡのプログラム・ファイルおよびデータ・ファイルがＤＶＤ−ＲＯＭドライブ53によって読出され，ビデオ・ゲーム装置３のハードディスク59にインストールされる。
【００９２】
また，ビデオ・ゲーム装置３のユーザには，サーバ２の管理者（たとえば，コンテンツＡを提供する企業）からあらかじめＩＤとパスワードを付与されているものとする。ユーザに付与されたＩＤおよびパスワードも，ビデオ・ゲーム装置３のハードディスク59に記憶されているものとする。
【００９３】
ユーザがビデオ・ゲーム装置３のゲーム機本体31の電源をオンし，所定の操作を行うと，ハードディスク59に記憶されているＩＤとパスワードが，ネットワーク１を介してビデオ・ゲーム装置３からサーバ２に送信される（ステップ71）。サーバ２においてＩＤおよびパスワードを用いたユーザ認証が行われる（ステップ91）。
【００９４】
ビデオ・ゲーム装置３の出力装置34の表示画面上には，ハードディスク59に記憶されているビデオ・ゲームの名称が一覧に表示される。ハードディスク59の複数の種類のビデオ・ゲームのためのプログラム・ファイルおよびデータ・ファイルが記憶されている場合には，複数のビデオ・ゲームの名称が表示画面上に表示される。ユーザはプレイしようとしているゲームの名称を，コントローラ32を用いて選択する（ステップ72）。
【００９５】
ビデオ・ゲーム装置３のハードディスク59に記憶されているビデオ・ゲーム（ビデオ・ゲームのためのプログラム・ファイルおよびデータ・ファイルの少なくとも一つ）には，バージョン情報が記憶されている。ユーザがコントローラ32を用いてゲームの名称を選択すると，選択されたビデオ・ゲームの種類を表すデータと，そのバージョン情報とが，ネットワーク１を通じてビデオ・ゲーム装置３からサーバ２に送信される（ステップ73）。
【００９６】
サーバ２はビデオ・ゲーム装置３からビデオ・ゲームの種類とそのバージョン情報を受信すると，ビデオ・ゲーム装置３のハードディスク59に記憶されている選択されたビデオ・ゲーム（コンテンツＡとする）についてのバージョンが，最新のバージョンであるかどうかを判断する（ステップ92）。最新バージョンであるか，または古いバージョン（最新ではないバージョン）であるかを表すデータ（比較結果）が，サーバ２からビデオ・ゲーム装置３に送信される（ステップ93）。
【００９７】
ビデオ・ゲーム装置３において，ビデオ・ゲーム装置３のハードディスク59に記憶されているコンテンツＡのバージョンが最新バージョンである旨のデータを受信した場合には（ステップ74でYES ），ビデオ・ゲーム装置３の出力装置34の表示画面上に最新バージョンである旨を表すメッセージが表示され（ステップ75），その後コンテンツＡのビデオ・ゲームがスタートする（ステップ82）。サーバ２において，バージョン・アップのための処理は行われない（ステップ94でNO）。
【００９８】
ビデオ・ゲーム装置３のハードディスク59に記憶されているコンテンツＡのバージョンが最新ではない旨のデータを受信した場合には（ステップ74でNO），ビデオ・ゲーム装置３の表示画面には，バージョン・アップを行う旨のメッセージが表示される（ステップ76）。
【００９９】
サーバ２において，ユーザのビデオ・ゲーム装置３のハードディスク59に記憶されているコンテンツＡのバージョンが最新のものでないことが判断されると（ステップ94でYES ），サーバ２はバージョン・アップに必要なデータ量をビデオ・ゲーム装置３に送信する（ステップ95）。
【０１００】
バージョン・アップに必要なデータ量を表すデータを受信したビデオ・ゲーム装置３では，ハードディスク59の空き容量が十分であるかどうかを判断する（ステップ77）。
【０１０１】
バージョン・アップに必要とされる十分な空き容量がビデオ・ゲーム装置３のハードディスク59に残っていない場合には（ステップ77でNG），ビデオ・ゲーム装置３の表示画面上にハードディスク59の空き容量が不足している旨のメッセージが表示される（ステップ79）。その後，古いバージョンのコンテンツＡのビデオ・ゲームがスタートする（ステップ82）。ハードディスク59に記憶されている不必要なファイルの削除またはハードディスクの追加等をユーザに勧めるメッセージを，表示画面上に表示してもよい。
【０１０２】
ハードディスク59の空き容量が十分にある場合（ステップ77でOK），ビデオ・ゲーム装置３からサーバ２にパッチ・データの送信要求が送信される（ステップ78）。パッチ・データの送信要求を受信したサーバ２は，バージョン・アップに必要なパッチ・データをビデオ・ゲーム装置３に送信する（ステップ96でYES ，ステップ97）。パッチ・データの送信要求を所定の時間内に受信しなかった場合には，サーバ２はバージョン・アップのための処理を終了する（ステップ96でNO）。
【０１０３】
パッチ・データを受信したビデオ・ゲーム装置３では，バージョン・アップ・プログラムが起動し，バージョン・アップ処理が実行される（ステップ80）。バージョン・アップ処理は，図５を参照して説明した処理と同じ処理である。
【０１０４】
図11は，バージョン・アップ処理におけるサーバ・コンピュータ２およびビデオ・ゲーム装置３の処理と，これらの間のデータの流れとを，分かりやすく示すものである。
【０１０５】
サーバ２は，コンテンツＡ（バージョン１）とコンテンツＡ（バージョン２）の異なる２つのバージョンのコンテンツＡをハードディスク66に記憶しているものとする。コンテンツＡ（バージョン１）は，ファイルａ，ファイルｂ，ファイルｃ，ファイルｄおよびファイルｅの５つのファイルを含む。コンテンツＡ（バージョン２）は，ファイルａ，ファイルｂ，ファイルｃ’，ファイルｄおよびファイルｅの５つのファイルを含む。すなわち，コンテンツＡ（バージョン２）は，コンテンツＡ（バージョン１）のファイルｃが，ファイルｃ’に置き換えられたものである。
【０１０６】
他方，ビデオ・ゲーム装置３のハードディスク59にはコンテンツＡ（バージョン１）（ファイルａ，ファイルｂ，ファイルｃ，ファイルｄおよびファイルｅ）が記憶されている。ここでユーザがビデオ・ゲーム装置３の電源をオンとし，プレイするゲームとしてコンテンツＡを選択すると，パッチ・データ送信要求がビデオ・ゲーム装置３からサーバ２に送信される。サーバ２のハードディスク66には，ファイルｃとファイルｃ’とに基づいてパッチ・データ作成プログラムにしたがって作成されたパッチ・データｘ（符号100 で示す）が記憶されている。パッチ・データ送信要求の受信に応じて，パッチ・データｘがサーバ２からビデオ・ゲーム装置３に送信される。もちろん，パッチ・データ送信要求を受信するたびに，サーバ２においてパッチ・データを作成するようにしてもよい。
【０１０７】
図12はパッチ・データのデータ構造を概念的に示している。パッチ・データ100 は，パッチ・データ本体と，ファイル名（ヘッダ情報）とを含む。ファイル名は，パッチ・データの作成に用いられた旧ファイル（更新前のファイル）のファイル名である。図11に示す例の場合には，ファイル名の部分には「ファイルｃ」が記述される。
【０１０８】
ビデオ・ゲーム装置３では，サーバ２から受信したパッチ・データｘに含まれるファイル名（ファイルｃ）に基づいて，バージョン・アップすべきファイルｃをＲＡＭ52に読出す。ＲＡＭ52に読出されたファイルｃとパッチ・データｘのパッチ・データ本体とに基づいてバージョン・アップ処理が実行される。新たにファイルｃ’が作成される。作成されたファイルｃ’がコンテンツＡに組込まれる。ファイルａ，ファイルｂ，ファイルｃ’，ファイルｄおよびファイルｅから構成されるコンテンツＡ（バージョン２）が，ビデオ・ゲーム装置３のハードディスクに保存される。バージョン情報（ファイルａ，ｂ，ｃ’，ｄまたはｅのいずれかに記述されている，バージョン情報のみが記述されたファイルをコンテンツＡに含ませておいてもよい）が，バージョン１からバージョン２に書替えられる。ファイルｃ（旧ファイル）は，一般にはビデオ・ゲーム装置３のハードディスク59から削除される。
【０１０９】
図10に戻って，バージョン・アップが成功すると，正常にバージョン・アップが終了した旨を表すデータがビデオ・ゲーム装置３からサーバ２に送信される（ステップ81）。その後，ビデオ・ゲーム装置３において最新バージョンのコンテンツＡのビデオ・ゲームがスタートする（ステップ82）。
【０１１０】
このように，ネットワークを用いたビデオ・ゲーム・システムでは，ビデオ・ゲーム装置３のハードディスク59に記憶されているビデオ・ゲームのバージョン・アップ（旧ファイルのバージョン・アップ）に必要なパッチ・データが，ネットワーク１を介してサーバ２から送信される。ビデオ・ゲーム装置３では旧ファイルとパッチ・データに基づいて新ファイルが作成されてバージョン・アップが完了する。パッチ・データのデータ量は新ファイルに比べて格段にデータ量が少ないので，新ファイルそのものをサーバ２からビデオ・ゲーム装置３に送信する場合に比べてデータ通信量を少なくすることができ，短い時間でデータ通信を終えることができる。
【０１１１】
（３）変形例
図13は，図10に示すビデオ・ゲーム装置３とサーバ２のそれぞれの処理と，これらの間のデータ通信の流れを示すフローチャートの変形例を示すものである。図10のフローチャートと同じ処理には同一の符号を付し，重複する説明を避ける。図14は，変形例において，サーバ２のハードディスク66に記憶されるデータベース（バージョン管理データベース101 ）の一例を示している。サーバ２のハードディスク66にバージョン管理データベース101 が記憶されている点を除き，サーバ２の構成は上述の図９と同じである。ビデオ・ゲーム装置３についても上述の図７および図８と同じ構成を持つ。
【０１１２】
サーバ２のハードディスク59に記憶されているバージョン管理データベース101 は，ユーザＩＤ，パスワード，ユーザ氏名，ビデオ・ゲーム名およびバージョン番号に関するデータが記憶されている。ユーザが所有するビデオ・ゲームごとに，そのビデオ・ゲームのバージョンがサーバ２において管理される。
【０１１３】
ビデオ・ゲーム装置３からＩＤおよびパスワード，ならびに選択されたビデオ・ゲームの種類を表すデータがサーバ２に送信されると（ステップ71，72），サーバ２はバージョン管理データベース101 をアクセスして，ＩＤおよびパスワードによって特定されるユーザが選択したビデオ・ゲームのバージョン情報を取得する。選択されたビデオ・ゲームが最新バージョンであるかどうかが判断される（ステップ92Ａ）。
【０１１４】
バージョン・アップが正常終了した旨のデータをサーバ２が受信すると，サーバ２ではバージョン管理データベース101 に格納されているバージョン番号を新たなバージョン番号に更新する（ステップ78）。このようにして，ユーザが所有するビデオ・ゲーム装置３のハードディスク59に記憶されているビデオ・ゲームのバージョンがサーバ２において管理される。
【０１１５】
ユーザが所有するビデオ・ゲーム装置３に，２つ前，３つ前のバージョンのコンテンツが記憶されている場合，たとえば，コンテンツの最新バージョンがバージョン４であり，ビデオ・ゲーム装置３にはバージョン１のコンテンツが記憶されている場合には，上述のバージョン・アップ処理を複数回繰返すことによって，すなわち，バージョン１をバージョン２にバージョン・アップし，バージョン２をバージョン３にバージョン・アップし，さらにバージョン３をバージョン４にバージョン・アップすることによって，ビデオ・ゲーム装置３のコンテンツを最新バージョンとすることができる。もちろん，バージョン１のコンテンツとバージョン４のコンテンツとを用いて，バージョン１からバージョン４へのバージョン・アップを行うためのパッチ・データをサーバ２において作成して，ビデオ・ゲーム装置３に送信するようにしてもよい。１回のバージョン・アップ処理によって，バージョン１からバージョン４へのバージョン・アップを図ることができる。
【図面の簡単な説明】
【図１】パッチ・データ作成処理（圧縮処理）とバージョン・アップ処理（伸張処理）を概念的に示している。
【図２】パッチ・データ作成処理の流れを示すフローチャートである。
【図３】(A) から(D) はパッチ・データ作成処理の流れを具体的に示している。
【図４】(A) から(D) はパッチ・データ作成処理の流れを具体的に示している。
【図５】バージョン・アップ処理の流れを具体的に示している。
【図６】ネットワークを利用したビデオ・ゲーム・システムのブロック図である。
【図７】ビデオ・ゲーム装置の全体的構成を示している。
【図８】ビデオ・ゲーム装置の電気的構成を示すブロック図である。
【図９】サーバの電気的構成を示すブロック図である。
【図１０】ビデオ・ゲーム装置とサーバとの間のデータ通信の流れを示すフローチャートである。
【図１１】サーバにおいて実行されるパッチ・データ作成処理およびビデオ・ゲーム装置において実行されるバージョン・アップ処理の様子を示している。
【図１２】パッチ・データのデータ構造の一例を示している。
【図１３】ビデオ・ゲーム装置とサーバとの間のデータ通信の流れの他の例を示すフローチャートである。
【図１４】バージョン管理データベースの一例を示している。
【図１５】(A) および(B) は従来のＬＺ方式にもとづくデータ圧縮の考え方を示すもので，(A) は圧縮対象の文字列を，(B) は圧縮処理後のデータ列をそれぞれ示している。
【図１６】(A) から(G) は従来のＬＺ方式にもとづくデータ圧縮の具体的な処理の流れを示している。
【図１７】(A) から(F) は従来のＬＺ方式にもとづくデータ圧縮の具体的な処理の流れを示している。
【符号の説明】
１  ネットワーク
２  サーバ・コンピュータ
３  ビデオ・ゲーム装置
51，61  ＣＰＵ
59，66  ハードディスク
【図１】
2004201144.tif 000003
【図２】
2004201144.tif 000004
【図３】
2004201144.tif 000005
【図４】
2004201144.tif 000006
【図５】
2004201144.tif 000007
【図６】
2004201144.tif 000008
【図７】
2004201144.tif 000009
【図８】
2004201144.tif 000010
【図９】
2004201144.tif 000011
【図１０】
2004201144.tif 000012
【図１１】
2004201144.tif 000013
【図１２】
2004201144.tif 000014
【図１３】
2004201144.tif 000015
【図１４】
2004201144.tif 000016
【図１５】
2004201144.tif 000017
【図１６】
2004201144.tif 000018
【図１７】
2004201144.tif 000019