(57)【要約】一致シンボル文字列を得るため、シンボル列のシンボル文字列と辞書中の格納されたシンボル文字列とをマッチさせる探索を実行するための方法及び装置である。本方法において、シンボル列の一致シンボル文字列が見つかった後、一致文字列の第１のシンボルが格納される辞書中の位置から、より長い一致シンボル文字列を見つけることができるかが判定される。対応する位置に格納されるシンボルが選定されたシンボルと一致するかを判定するため、まず、シンボル列中の一致シンボル文字列に続く選定されたシンボルと、辞書において第１のシンボルが格納される別の位置から始まる、辞書中の対応する位置に格納されるシンボルとを比較する。比較が一致に終わらなければ、より長い一致シンボル文字列が見いだされなかったことが直ちに判明し、さらなる比較ステップを省略することが可能になるであろう。本発明は、最長一致探索を行うためのより効率的な手順を提供すると同時に、辞書を容易に更新可能なデータ構造を用いる。
2004537910.tif 000002
【特許請求の範囲】
【請求項１】
一致シンボル文字列を得るため、シンボル列のシンボル文字列と辞書中の格納されたシンボル文字列とをマッチさせる探索を実行するための方法であって、
既知の一致シンボル文字列を得るため、前記シンボル列の選択されたシンボルから始まる、前記シンボル列のシンボル文字列と、前記選択されたシンボルが格納される前記辞書中の第１の位置から始まる、格納されたシンボル文字列とをマッチングするステップと、
前記辞書において、前記選択されたシンボルが格納される別の場所を特定するステップと、
前記シンボル列中の前記既知の一致シンボル文字列に続く、前記シンボル列中のシンボルを選定するステップと、
前記別の位置から始まる前記辞書中の対応する位置に格納されるシンボルと前記シンボル列中の前記選定されたシンボルとが一致するかを判定するため、前記選定されたシンボルと前記対応する位置に格納されるシンボルとを比較するステップと、
前記比較ステップの結果が一致である場合、
前記選択されたシンボルと前記選定されたシンボルの間の調査中シンボル文字列が、前記既知の一致シンボル文字列よりも長いかどうかを判定するため、前記調査中シンボル文字列と、前記別の場所に格納される前記シンボルから始まる前記辞書中に格納されるシンボル文字列とを比較するステップとを有することを特徴とする方法。
【請求項２】
前記選択されるシンボルが前記シンボル列の第１のシンボルを含むことを特徴とする請求項１記載の方法。
【請求項３】
前記第１の位置が、前記辞書において前記選択されるシンボルが直前に出現する位置を含むことを特徴とする請求項１記載の方法。
【請求項４】
前記別の位置が、前記辞書において前記選択されるシンボルが２つ前に出現する位置を含むことを特徴とする請求項３記載の方法。
【請求項５】
前記選定ステップが、
前記既知の一致シンボル文字列直後の次シンボルを前記シンボル列から選定するステップを有し、
前記比較ステップの結果が不一致である場合、前記調査中シンボル文字列が前記既知の一致シンボル文字列よりも長くないことが判明することを特徴とする請求項１記載の方法。
【請求項６】
起こりうる最長の一致シンボル文字列を見いだすため、前記選択されたシンボルが出現する辞書中のすべての位置が特定されるまで前記特定ステップ、選定ステップ及び比較ステップが繰り返されることを特徴とする請求項１記載の方法。
【請求項７】
前記選択されるシンボルが出現するすべての前記位置が、直前の出現位置からそれ以前の出現位置への順番で特定されることを特徴とする請求項６記載の方法。
【請求項８】
複数のシンボル文字列を格納する辞書を用い、シンボル列のシンボル文字列を個別に符号化することによって前記シンボル列を圧縮する辞書圧縮手順において、符号化すべき起こりうる最長のシンボル文字列を見いだすための最長一致探索方法であって、
既知の一致シンボル文字列を得るため、前記シンボル列の選択されたシンボルから始まる、前記シンボル列のシンボル文字列と、前記選択されたシンボルが格納される前記辞書中の第１の位置から始まる、前記辞書中に格納されたシンボル文字列とをマッチングするステップと、
前記辞書において、前記選択されたシンボルが格納される別の場所を特定するステップと、
前記シンボル列中の前記既知の一致シンボル文字列に続く、前記シンボル列中のシンボルを選定するステップと、
前記別の位置から始まる前記辞書中の対応する位置に格納されるシンボルと前記シンボル列中の前記選定されたシンボルとが一致するかを判定するため、前記選定されたシンボルと前記対応する位置に格納されるシンボルとを比較するステップと、
前記比較ステップの結果が一致である場合、
前記選択されたシンボルと前記選定されたシンボルの間の調査中シンボル文字列が、前記既知の一致シンボル文字列よりも長いかどうかを判定するため、前記調査中シンボル文字列と、前記別の場所に格納される前記シンボルから始まる格納されるシンボル文字列とを比較するステップと、
前記選択されたシンボルが前記辞書内で出現するすべての位置が特定されるまで、前記特定ステップ、選定ステップ及び比較ステップが繰り返されることを特徴とする方法。
【請求項９】
前記選択されるシンボルが前記シンボル列の第１のシンボルを含むことを特徴とする請求項８記載の方法。
【請求項１０】
前記第１の位置が、前記辞書において前記選択されるシンボルが直前に出現する位置を含むことを特徴とする請求項８記載の方法。
【請求項１１】
前記別の位置が、前記辞書において前記選択されるシンボルが２つ前に出現する位置を含むことを特徴とする請求項１０記載の方法。
【請求項１２】
前記選定ステップが、
前記既知の一致シンボル文字列直後の次シンボルを前記シンボル列から選定するステップを有し、
前記比較ステップの結果が不一致である場合、前記調査中シンボル文字列が前記既知の一致シンボル文字列よりも長くないことが判明することを特徴とする請求項８記載の方法。
【請求項１３】
前記選択されるシンボルが出現するすべての前記位置が、直前の出現位置からそれ以前の出現位置への順番で特定されることを特徴とする請求項８記載の方法。
【請求項１４】
シンボル列のシンボル文字列と辞書中の格納シンボル文字列との起こりうる最長の一致を見いだすために最長一致探索を実行するための装置であって、
辞書と、
プロセッサとを有し、
前記辞書は第１及び第２の配列並びにテーブルを含み、前記第１の配列は前記辞書に格納される各シンボルを有し、前記第２の配列は前記第１の配列に格納された前記シンボルの各々の以前の位置へのポインタを有し、前記テーブルは前記第１の配列に格納された前記シンボルの各々の、前記第１の配列における最新の出現位置へのポインタを有し、
前記プロセッサは、最長一致探索が効率的に実施できるように前記第１及び第２の配列並びに前記テーブルを有する前記辞書を用いて起こりうる最長の一致シンボル文字列を特定するために最長一致探索を実施することを特徴とする装置。
【請求項１５】
さらに前記辞書を格納するための少なくとも１つのメモリを含むことを特徴とする請求項１４記載の装置。
【請求項１６】
前記装置が前記起こりうる最長の一致シンボル文字列を圧縮するためのシステムに組み込まれていることを特徴とする請求項１４記載の装置。
【発明の詳細な説明】
【技術分野】
【０００１】
本願が同時継続中の米国仮出願第60/309,982（2001年8月2日出願）の恩恵を享受することを求める。
【０００２】
本発明は全体としてデータ圧縮の分野に関し、特にはロスレス辞書圧縮手順における最長一致探索を行うための方法及び装置に関する。
【背景技術】
【０００３】
多くの、繰り返し用いられる特徴文字列(signal strings)を含む大きなアスキー(American Standard Code for Information Interchange)ファイルの圧縮には、Lempel-Zif圧縮（非特許文献１を参照）のような辞書圧縮手順がよく用いられる。辞書圧縮手順は、別個の辞書ファイル又はインデックス、あるいは圧縮中のファイルで既に出願したものを参照してファイル中の連続するシンボルを置き換えることによりファイルを圧縮する。しかし、辞書圧縮技術は、大きな辞書や参照テーブルが利用できる場合を除き、小さなデータファイルやメッセージを圧縮する際の効率が悪い。通常、大きな辞書は小さな辞書よりも効率的な圧縮をもたらす。
【０００４】
インターネット上の信号トラフィックの多くが、例えばＳＩＰ（非特許文献２参照）、ＳＤＰ（非特許文献３参照）、ＨＴＴＰ（非特許文献４参照）、ＲＴＳＰ（非特許文献５参照）といったアスキーベースのプロトコルによって生成されている。これらプロトコルの各々のメッセージサイズは比較的小さい。そしてそれ故に効率的な圧縮を行うには大きな辞書を用いなければならない。これは大きな静的辞書又は、セッション中既に送信されたメッセージを用いて継続的に更新される動的辞書のいずれかを用いることにより達成できる。静的辞書及び動的辞書は、例えば圧縮フレームワークROGER（非特許文献６及び非特許文献７を参照）において、組み合わせて用いることもできる。
【０００５】
辞書圧縮手順においてメモリ及びプロセッサ利用についての効率性を実現するために非常に重要なことは、その圧縮が実行されるやり方、例えば、最長一致探索に用いられる探索アルゴリズムがどのように設計されているかである。Lempel-Ziv又は他の辞書圧縮手法において用いられる標準的な最長一致探索法は一般に線形型(LZ77)であるか、２分木(binary tree)中の探索を伴う(LZSS)（例えば特許文献１を参照のこと）。
【０００６】
線形探索は遅いが、ある程度簡単に実行できる。辞書の変更、例えばテキストの追加又は削除による辞書の更新もまた容易に達成できる。２分木中の探索はずっと高速な方法であるが、２分木を用いると、辞書に対するテキストの加除を行うための動作が比較的遅く、そのため対応する２分木の更新もまた遅くなる。
【０００７】
従って、高速で、辞書が時間の経過とともに変更される際に更新が容易なデータ構造を用いる最長一致探索方法及び装置を含む辞書圧縮手順に対する必要性が存在する。
【０００８】
【非特許文献１】
Salomon, D., Data Compression The Complete Reference, Springer-Verlag, New York, Inc., 1998
【非特許文献２】
Handley, M., Schulzrinne, H., Schooler, E. and Rosenberg, J., SIP: Session Initiation Protocol, IETF RFC 2543, 2000
【非特許文献３】
Handley, M. and Jacobson, V., SDP: Session Description Protocol, IETF RFC 2327, 2000
【非特許文献４】
Fielding, R. et al., Hypertext TransferProtocol-HTTP/1.1, IETFRFC 2616,2000
【非特許文献５】
Schulzrinne, H., Rao, A. and Lanphier, R., Real Time Streaming Protocol (RTSP), IETF RFC 2326, 2000
【非特許文献６】
R. Price, H. Hannu等「Signaling Compression」 (draft-ietf-rohc-sigcomp-06.txt) Internet Draft (策定中), 2002年5月
【非特許文献７】
H. Hannu, J. Christoffersson等、「SigComp-Extended Operations」(draft-ietf-rohc-sigcomp-extended-03.txt) Internet Draft (策定中), 2002年5月
【発明の開示】
【課題を解決するための手段】
【０００９】
本発明は、非常に高速で、辞書に対してテキストの加除を行う際、更新が簡単なデータ構造を用いる、辞書圧縮手順のための最長一致探索方法及び装置を提供する。
【００１０】
本発明によれば、シンボル列(sequence of symbols)のシンボル文字列(string of symbols)を辞書中に格納されたシンボル文字列とマッチさせ、一致シンボル文字列を得るための探索を行う方法であって、既知の一致シンボル文字列を得るため、シンボル列の選択されたシンボル(selected symbol)から始まる前記シンボル列のシンボル文字列を、前記選択されたシンボルが格納される辞書中の第１の位置から始まる第１の格納された文字列とマッチングさせるステップと、前記選択されたシンボルが格納される辞書中の別の場所を特定するステップと、前記シンボル列中の前記既知の一致シンボル文字列に続く、前記シンボル列中のシンボルを選定するステップと、前記シンボル列中の前記選定されたシンボル(chosen symbol)を、前記辞書中の対応する位置に格納されるシンボルであって、前記別の位置から始まるシンボルと、前記対応する位置に格納される前記シンボルが前記選定されたシンボルと一致するかどうかを判定するために比較するステップと、前記比較ステップの結果が一致である場合、前記選択されたシンボル及び前記選定されたシンボルとの間で現在調査中のシンボル文字列が、前記別の場所に格納される前記シンボルから始まる前記辞書に格納されたシンボル文字列と一致するかどうかを、前記調査中のシンボル文字列が前記既知の一致シンボル文字列より長いかを判定するために判定するステップとを有する方法が得られる。
【００１１】
本発明は、まず、調査中のシンボル文字列を規定するために第１の一致シンボル文字列に続くシンボル列中のシンボルを選定し、次いで選定されたシンボルを、選択されたシンボルが格納される別の場所から始まる、辞書中の対応する位置に格納されるシンボルと比較することにより、既知の一致シンボル文字列よりも長い、第２の一致(second matched)シンボル文字列を見いだすために行わねばならない比較の回数を多くの場合削減することが可能であることを認識している。特に、この比較が一致を見なかった場合、調査中の文字列の中間にあるシンボルを比較することは不要であろう。行わねばならない比較の回数を削減することで、一致探索に必要な全体の時間を削減することができる。
【００１２】
本発明の現時点における好適な実施形態によれば、選定されたシンボルは既知の一致シンボル文字列に続く、シンボル列中の第１のシンボルを含む。本発明の現時点における好適な実施形態によれば、選定されたシンボルは既知の一致シンボル文字列に続く、シンボル列中の第１のシンボルを含む。従って、調査中のシンボル文字列の他のシンボルを辞書中の対応位置に格納されるシンボルと比較する必要がない。特に既知の一致シンボル文字列が多くのシンボルからなる場合、本発明による方法は比較をかなりの数削減することが可能であり、従って一致探索方法を完了するために必要となる時間を大幅に短縮することが可能である。
【００１３】
本発明の他の実施形態によれば、一致探索法は最長一致探索法を有し、かつ特定ステップが、選択されたシンボルが格納される辞書中の全ての位置を特定するステップを有する。そして、起こりうる最長の一致シンボル文字列を特定するため、調査中のシンボル文字列は、選択されたシンボルが存在する辞書中の各位置から始まる、辞書中に格納されたシンボル文字列に関してチェックされる。
【００１４】
本発明の他の実施形態によれば、選択されたシンボルはシンボル列中の第１のシンボルを含み、辞書中の第１の位置がこの第１のシンボルが格納される辞書中の最新位置を含む。辞書中の別の場所は、この第１のシンボルが格納される２番目に新しい位置を含む。この方法は第１のシンボルが格納される全ての位置が特定されるまで辞書を通じて継続され、起こりうる最長の一致を特定するための比較が行われる。
【００１５】
本発明のさらに別の実施形態によれば、シンボル列のシンボル文字列と辞書中に格納されたシンボル文字列との間で起こりうる最長の一致を見いだすための最長一致探索を実行するための装置が、辞書とプロセッサを有する。辞書は第１及び第２の配列(array)及びテーブルを含む。第１の配列は辞書に格納される各シンボルを有する。第２の配列は第１の配列に格納される各シンボルの以前の位置へのポインタを有し、テーブルは第１の配列内に格納される各シンボルが第１の配列内で最後に存在した位置へのポインタを有する。プロセッサは起こりうる最長の一致シンボル文字列を第１及び第２の配列及びテーブルを有する辞書を用いて特定するため、最長一致探索を実行する。本発明の装置はより効率的な最長一致探索の実施のみならず、必要な際は辞書を新たなシンボル又はシンボル文字列で簡単に更新することも可能にする。
【００１６】
本発明による一致探索方法及び装置は、全体の圧縮処理を円滑にするため、Lempel-Ziv圧縮といったロスレス辞書圧縮手順に容易に統合することができる。本発明によって得られるこれらの能力は圧縮フレームワークROGERを用いるアプリケーションを含む多くのアプリケーションにおいて重要である。
【００１７】
本発明のさらに別の目的、特徴及び長所は、本発明の現時点で好ましい実施形態の詳細な説明と連動して明らかとなるであろう。
【発明を実施するための最良の形態】
【００１８】
図１は本発明の現時点における好ましい実施形態に係るデータ圧縮装置の模式的なブロック図である。装置は全体を参照数字１０で示されており、プロセッサ１２及び補助辞書(assisted dictionary)１６を有している。当業者には周知の通り、辞書１６は複数の異なるシンボル文字列を、各シンボル文字列に対応する適切なインデックスと共に格納する。各シンボル文字列は１つ又は複数の連続するシンボルからなる。ある特定のシンボル列を圧縮するため、シンボル列は複数のシンボル文字列に分割される。複数のシンボル文字列の各々は、文字列を辞書中に格納されたシンボル文字列とマッチングさせ、一致した文字列をその特定の文字列に対応するインデックスと置き換えることにより個別に符号化される。図１に示すように、プロセッサ１２は圧縮すべき入力シンボル列２６を受信し、辞書１６を用いてシンボル列を圧縮して、圧縮シンボル列２８を出力する。
【００１９】
辞書圧縮手順を用いて効率的な圧縮を実現するためには、シンボル列の各シンボル文字列ができる限り長い状態で圧縮されること、すなわちできるだけ多くのシンボルからなる状態で圧縮されることが重要である。その結果、既知の辞書圧縮手順は、辞書に格納されるシンボル文字列と一致する、シンボル列中で起こりうる最長のシンボル文字列を特定するための”最長一致探索”を含んでいる。しかし、上で述べたように、既知の最長一致探索法は遅く、従って効率的でないか、時折発生する辞書更新時にあまり都合が良くないかのいずれかである。
【００２０】
本発明は、辞書圧縮手順における最長一致探索を行うための方法及び装置であって、高速で、同時に辞書を更新しなければならない時に非常に好都合なデータ構造を用いる方法及び装置を提供する。図１に示すように、辞書は第１及び第２の配列２０及び２２（配列Ａ１及びＡ２と呼ぶこともある）及びテーブル２４からなるデータ構成を含むものと見なすことができる。第１の配列２０は、辞書に格納される第１のシンボルが第１の配列における第１のシンボルであり、辞書に格納される第２のシンボルが第１の配列における第２のシンボルであり、以下同様の関係となるよう、辞書に格納される全てのシンボルを備えている。辞書と第１の配列との対応を図２に示す。ここで、辞書において連続する位置に格納されるシンボル、例えばシンボルａ，ｄ，ｅ，ａ，．．．は第１の配列内の対応する連続位置に格納されているものとして表されている。（ここで、実際には、第１の配列は辞書に格納されるシンボルの複製ではなく、また辞書から第１の配列へ情報を実際にコピーする必要もないことを理解すべきである。辞書と第１の配列は同一構成であり、本明細書において第１の配列は単に本発明の大切な理解を容易にするために説明されている。）
【００２１】
第２の配列は、そのｉ番目の要素が、第１の配列のｉ番目の位置のシンボルが先に存在した位置へのポインタとなるよう、第１の配列中のシンボルの先の位置へのポインタを保持する。特に、第１の配列２０を配列Ａ１として表し、第２の配列２２を配列Ａ２として表すと、配列Ａ１のｉ番目の要素は、Ａ１（ｉ）として表すことができる。配列Ａ２は、そのｉ番目の要素が、配列Ａ１のｉ番目の位置のシンボルが先に存在した位置へのポインタとなるように配列Ａ１中のシンボルの先の位置へのポインタを保持する。つまり、Ａ２（ｉ）は、シンボルＡ１（ｉ）もまた格納される第１の配列における直前の位置へのポインタである。
【００２２】
配列Ａ１及びＡ２の関係を図３に示す。具体的には、図３に示すように、シンボル”ａ”が配列Ａ１の位置４に存在し、またシンボル”ａ”が以前に、かつ直前で存在していたのは配列Ａ１の位置１である。従って、配列Ａ２の位置４におけるポインタは配列Ａ１の位置１を示している。シンボル”ａ”は次に配列Ａ１の位置５で現れる。この時点でシンボル”ａ”が以前に、かつ直前に現れたのは配列Ａ１の位置４となるから、配列Ａ２の位置５におけるポインタは配列Ａ１の位置４を指す。同様にして、配列Ａ１のある特定の位置における各要素は、配列Ａ２の同一位置に対応するポインタを有し、このポインタはその特定のシンボルが配列Ａ１において直前に現れた位置を示す。図３で配列Ａ２の様々な位置になされている”＊”指定は、配列Ａ１で対応する位置に存在するシンボルが過去に出現していないこと、すなわちその位置が、配列Ａ１におけるある特定のシンボルの最初の出現を含んでいることを示している。
【００２３】
テーブル２４は、配列Ａ１に存在する（そして、同様に辞書に存在する）各シンボルの、配列Ａ１における最新位置を特定するポインタを含んでいる。この関係は図２〜図４を参照することで最も良く理解することができる。具体的には、図２に示すように、配列Ａ１におけるシンボル”ａ”の最後の出現は、位置９でのものである。従って、図４に示すように、テーブル２４でのポインタは、配列Ａ１におけるシンボル”ａ”が配列Ａ１の位置９で最後に出現していることを示している。同様に、図４はシンボル”ｂ”が配列Ａ１の位置１０で最後に出現していること、シンボル”ｃ”が配列Ａ１の位置７で最後に出現していることを示し、以下同様にして他のシンボルについても示している。このように、テーブル２４は配列Ａ１に格納される各シンボル（例えばａ，ｂ，ｃ，ｄ，ｅ，等）の最後の出現位置へのポインタを含んでいる。図３において、”＊”指定は、ある特定のシンボルが配列Ａ１のどこにも現れないことを示す。従って、そのシンボルは辞書にも存在しない。以下でより完全に説明するように、テーブル２４は最長一致探索を開始する際に特に有用である。
【００２４】
第１及び第２の配列Ａ１及びＡ２及びテーブルの全ては、シンボル列を効率的に圧縮できるよう、辞書１６に格納されるシンボル文字列と一致しうる、シンボル列２６中で起こりうる最長シンボル文字列を特定するための最長一致探索を実行するために用いられる。例えば、シンボルc(1),c(2),c(3),...,c(j)からなるシンボル列”ｃ”の圧縮を検討する。シンボル列の最初のシンボルはシンボルc(1)であり、従って、辞書においてc(1)が出現する全ての位置が、シンボル列のc(1)から始まるシンボル文字列と、格納されたシンボル文字列との最長一致が始まりうる位置の候補となる。辞書においてc(1)が出現する位置は、テーブル２４及び第２の配列２２のポインタに従って見いだすことができる。圧縮すべきシンボル列のシンボル文字列と一致しうる、辞書に格納された最長の文字列の位置特定を確実なものとするため、これら出現位置の各々は、最長一致探索の間に調査されねばならない。本発明の別の実施形態に係る、図１の装置を用いて最長一致探索を行う方法を以下に説明する。
【００２５】
最初に、テーブル２４中の、配列Ａ１におけるシンボルc(1)の最終出現位置（すなわち、c(1)の辞書における最終出現位置）を特定するポインタを調べる。テーブル２４のポインタが、配列Ａ１中の位置Ａ１(p1)に対応する辞書中の位置p1を、辞書におけるシンボルc(1)の最終出現位置として示しているとする。そして、一致する長さ、すなわち位置p1から始まる辞書中の対応する連続位置に格納されるシンボルと一致する、シンボル列の連続するシンボル数を求めるため、シンボル列のシンボルc(2)が、配列Ａ１の位置Ａ１(p1+1)に対応する辞書の位置(p1+1)のシンボルと比較され、シンボル列のシンボルc(3)が、配列Ａ１の位置Ａ１(p1+2)に対応する辞書の位置(p1+2)のシンボルと比較され、以下同様にして比較が行われる。この一致の長さが３シンボルであり、シンボルc(1),c(2)及びc(3)が位置Ａ１(p1)、Ａ１(p1+1)及びＡ１(p1+2)に格納されているが、シンボル列のシンボルc(4)と位置Ａ１(p1+3)のシンボルは一致しなかったものとする。このようにして、３シンボル長の一致シンボル文字列が見いだされる。
【００２６】
より長い一致が存在するか、すなわち３シンボルより長い一致シンボル文字列を見いだせるかを判定する目的で、辞書においてシンボルc(1)が直前に出現した位置を特定するために配列Ａ２のポインタが用いられる。辞書中のこの位置が位置”p2”と指定されているとすると、この位置へのポインタは第２の配列によってp2＝Ａ２(p1)として与えられる。換言すれば、シンボルc(1)の直前出現位置(p2)は配列Ａ２の位置(p1)に存在する。
【００２７】
次に、シンボル列の、より長いシンボル文字列（すなわち３シンボル長よりも長い文字列）が、辞書の位置p2から始まる辞書に格納されたシンボル列に一致可能であるかどうかが判定される。この、より長いシンボル文字列は調査中シンボル文字列と表すことができ、判定はまず、調査中シンボル文字列の最後のシンボルを、位置p2から始まる辞書中の対応する位置のシンボルと比較することによって行われる。従って、シンボル列の不一致シンボルc(4)は配列Ａ１の位置Ａ１(p2+3)のシンボルと比較される。具体的には、調査中シンボル文字列が４シンボル長である場合、調査中シンボル文字列の４番目のシンボルは、辞書において位置p2から始めて４番目の位置におけるシンボルと、一致するかどうか調べるために比較される。この比較が一致という結果に終わらなければ、少なくとも辞書の位置p2から始まるシンボル文字列に関して調査中シンボル文字列が３シンボル長より長い一致シンボル文字列とはなり得ず、調査中シンボル文字列のそれ以上の調査が不要であることが直ちに判明する。
【００２８】
比較結果が一致であった場合には、調査中シンボル文字列のシンボルc(1)及びc(4)の両方が、位置p2から始まる辞書中の対応位置におけるシンボルと一致したことが判明する。しかし、調査中シンボル文字列が位置p2から始まる辞書中に格納されたシンボル文字列と一致するかどうかが必要であるにもかかわらず、調査中シンボル文字列のシンボルc(2)及びc(3)が辞書中の位置p2+1及びp2+2におけるシンボルと一致するかどうかは依然として不明である。従って、次に、一致が実際に少なくとも４シンボル長であるのかどうかを判定するため、シンボルc(2)及びc(3)が辞書中の位置p2+1及びp2+2におけるシンボルとそれぞれ比較される。
【００２９】
上の説明から、調査中シンボル文字列の中間シンボルを辞書中の対応位置におけるシンボルと比較する前に、調査中シンボル文字列の最後のシンボルと辞書中の対応する位置におけるシンボルとを比較することにより、中間シンボルの比較が不要になる場合には方法から除外することが可能になることが理解されよう。従って、本方法は比較ステップの数を削減することが可能であり、最長一致探索をより高速な実施を実現する。省略可能な比較ステップの数は、調査中シンボル文字列が長い場合特に大きくなる。
【００３０】
調査中シンボル文字列のシンボルc(1)からc(4)と、位置p2から始まる辞書中の対応する位置におけるシンボルとが一致する場合、少なくとも４シンボル長の、より長い一致シンボル文字列が見いだされる。正確な一致長はその後求める必要がある。これには、一致が見いだされなくなるまで、シンボルc(5),c(6),...を辞書中の対応する位置におけるシンボル、すなわち位置p2+4，p2+5，...におけるシンボルと比較することが必要である。
【００３１】
辞書中の位置p2から始まる一致シンボル文字列がｋシンボル長を有するものとする。辞書においてシンボルc(1)が３回前に出現した位置へのポインタに従う。このポインタは第２の配列Ａ２において、p3＝Ａ２(p2)によって与えられる。つまり、シンボルc(1)の３回前の出現位置は辞書の位置p3に存在し、それは配列Ａ１においてシンボルc(1)が２回前に出現した位置に対応する配列Ａ２の位置にあるポインタを用いて見いだすことができる。上述したように、今のところ分かっている最長一致はｋシンボル長であるから、シンボル列のシンボルc(1)からシンボルc(k)へ延びる一致連続シンボル文字列が存在する。再び、まず、新たな調査中シンボル文字列の最後のシンボルを、今回は位置p3から始まる、辞書中の対応する位置に格納されるシンボルと比較することによって新たな調査中シンボル文字列が評価される。従って、新たな調査中シンボル文字列がｋ＋１のシンボル長を有する場合、シンボル列のシンボルc(k+1)と辞書中の位置p3+k（配列Ａ１の位置Ａ１(p3+k)に対応する）に格納されるシンボルとの比較が最初に実行される。繰り返すが、この比較結果が一致であった場合のみ、この新たな調査中シンボル文字列が現時点で見つかっている一致シンボル文字列よりも長い可能性がある。
【００３２】
起こりうる最長の一致シンボル文字列は、辞書中でシンボルc(1)が格納される全ての位置を特定し、調査中シンボル文字列が特定された位置の各々から始まる辞書中のシンボル文字列と一致するかどうかを判定することによって見いだされる。好ましくは、上述したように、これはc(1)が格納される位置を直前の位置からそれ以前の位置へ順番に調べることによって実行される。起こりうる最長の一致シンボル文字列が見いだされると、その起こりうる最長の一致シンボル文字列は符号化され、シンボル列中の次のシンボルから始まる別の起こりうる最長の一致シンボル文字列が探索される。
【００３３】
図５は本発明の別の実施形態に係る最長一致探索方法１００のステップを示すフローチャートである。最初に、圧縮すべきシンボル列の１番目のシンボル(c1)の辞書における直前の出現位置が特定される（ステップ１０５）。そして、１番目のシンボル(c1)から、辞書における直前の出現位置から始まる連続する位置に格納されるシンボルに一致するシンボル列の連続するシンボルの数が判定される（ステップ１１０）。ここで、ステップ１１０で判定される一致シンボル文字列がｋシンボル長であるとする。そして、シンボルc(1)が辞書で２つ前に出現した位置が特定される（ステップ１１５）。２つ前の出現が存在すれば（ステップ１２０でＹ出力）、方法は継続する。
【００３４】
辞書における２つ前の出現位置が位置pであったとする。圧縮すべきシンボル列のシンボルc(k+n)と、位置p+k-1+nのシンボルとが、一致するかを判定するための比較が行われる（ステップ１２５）。なお、前に説明した現時点で好ましい実施形態においてｎ＝１であるが、必要ならｎはより大きな数であってもよい。一致したならば（ステップ１３０でＹ出力）、少なくともｋ＋ｎシンボルが一致しうる。そのような場合、ステップ１３５に示されるように、さらに引き続くシンボルが比較される。まず、シンボルc(k+2n)が位置p+k-1+2nのシンボルと比較される。これらのシンボルが一致したならば（ステップ１４０でＹ出力）、少なくともｋ＋２ｎが一致しうる。そして、比較結果が一致しなくなるまで（ステップ１４０でＮ出力となるまで）、ステップ１３５及び１４０はシンボル列のさらに引き続くシンボル、すなわちシンボルc(k+3n),c(k+4n)等に対して繰り返される。そして、実際により長い一致シンボル文字列が存在するのかを調べるため、シンボル列の中間シンボルが辞書において対応する中間位置を占めるシンボルと比較される（ステップ１４５）。
【００３５】
ステップ１２５における比較結果が一致なしを示す場合（ステップ１３０でＮ出力）、方法はステップ１１５へ戻り、辞書中のシンボルc(1)の別の出現位置が特定される。辞書中にそれ以上c(1)の出現位置がなければ（ステップ１２０でＮ出力）、最長と見込まれる一致が見いだされ、処理は停止する。
【００３６】
図６は上述した探索方法を典型的に示す図である。図６において、文字列a,b,c,dについての一致が探索される。最長一致探索中に行われる比較は、図の２番目の行に示されている。具体的には、文字列a,b,c,dに対する最長一致が比較1,2,...,8を通じて見いだされる。
【００３７】
上述したやり方で前もっていくつかのシンボルを探索することは、例えばＳＩＰ／ＳＤＰからのプロトコルメッセージを圧縮する際に時々起こるような、辞書に１つの非常に長い一致といくつかの短い一致が存在する場合に特に好都合である。本発明は全体として、辞書が時折変更される際に特に都合のよいデータ構造のための高速探索方法を提供する。そのデータ構造の有用性は、そのデータ構造が新しいシンボル又はシンボル文字列によって更新可能な場合に得られる。そのような能力はＲＯＧＥＲを用いる場合のように、多くの状況で特に重要である。
【００３８】
ここで、”有する”という語が本明細書において用いられる際、これは説明された機能、整数(integers)、ステップ又は構成要素の存在を特定するために用いられる。しかし、この語は他の１つ以上の機能、整数、ステップ、構成要素又はそれらのグループの存在又は付加を排除するものではないことを理解すべきである。
【００３９】
ここで説明してきたものは現時点で本発明の好適な実施形態を構成するが、本発明がその範囲を離れることなく多くの方法で変更されうることを理解すべきである。従って、本発明が以下の請求項の範囲によって必要とされる限度でのみ限定されるべきであることを認識すべきである。
【図面の簡単な説明】
【００４０】
【図１】本発明の現時点における好ましい実施形態に係るデータ圧縮装置の模式的なブロック図である。
【図２】図１の辞書及び第１の配列との関係を示す図である。
【図３】図１の第１及び第２の配列の関係を示す図である。
【図４】図１の第１の配列とテーブルとの関係を示す図である。
【図５】本発明の別の実施形態による最長一致探索を用いるデータ圧縮方法のステップを示すフローチャートである。
【図６】本発明の説明を補助する図である。
【図１】
2004537910.tif 000003
【図２】
2004537910.tif 000004
【図３】
2004537910.tif 000005
【図４】
2004537910.tif 000006
【図５】
2004537910.tif 000007
【図６】
2004537910.tif 000008
【国際公開パンフレット】
2004537910.tif 000009
2004537910.tif 000010
2004537910.tif 000011
2004537910.tif 000012
2004537910.tif 000013
2004537910.tif 000014
2004537910.tif 000015
2004537910.tif 000016
2004537910.tif 000017
2004537910.tif 000018
2004537910.tif 000019
2004537910.tif 000020
2004537910.tif 000021
2004537910.tif 000022
2004537910.tif 000023
2004537910.tif 000024
2004537910.tif 000025
2004537910.tif 000026
2004537910.tif 000027
2004537910.tif 000028
2004537910.tif 000029
2004537910.tif 000030
【国際調査報告】
2004537910.tif 000031
2004537910.tif 000032
2004537910.tif 000033