JPH07297728A

JPH07297728A - パターン一致を探索するための方法およびシステム

Info

Publication number: JPH07297728A
Application number: JP7050774A
Authority: JP
Inventors: Joe-Ming Cheng; ジョ＝ミン・チェン; Yancy Cheng; ヤンシー・チェン
Original assignee: International Business Machines Corp
Current assignee: International Business Machines Corp
Priority date: 1994-04-15
Filing date: 1995-03-10
Publication date: 1995-11-10
Anticipated expiration: 2015-09-04
Also published as: JP3084201B2; US5525982A; EP0677927A3; EP0677927A2

Abstract

(57)【要約】【目的】新キャラクタの列と最近の過去に処理された
列内のキャラクタとの間の最長パターン一致を確認する
際の１サイクルあたりのキャラクタ数を増加する。【構成】本発明によれば、パイプライン式並行データ
フロー・モデルを使用し、短縮された時間でキャラクタ
列の間のＫキャラクタ毎サイクルの最大長パターン一致
を確認するための手段および方法が提供される。このデ
ータフロー・モデルでは、一貫した方向での列間の再帰
的な網羅的貪欲比較照合によって、最長一致の解析がも
たらされる。この再帰は、固定長Ｋ、一致長Ｌおよび追
跡変数Ｊの間の関係によって制約され、この制約は、あ
る列から別の列への接頭部拡張と列内パターン一致を確
認するそれ以降の再帰を支配する。１時に１キャラク
タ、２キャラクタまたは３キャラクタに等しいＫを処理
する実施例が可能である。

Description

【発明の詳細な説明】

【０００１】

【産業上の利用分野】本発明は、適応辞書キャラクタ列
（ストリング）圧縮または、たとえばZiv-Lempel（Ｌ
Ｚ）１９７７タイプの圧縮コーダによって表現される圧
縮などで使用するための１対のキャラクタ列の間の最長
パターン一致を確認するための時間の最小化に関する。

【０００２】

【従来の技術】この節では、辞書ベース圧縮のパターン
照合態様に重点を置いて、圧縮方法を簡単に要約する。
従来技術では、部分列（サブストリング）の照合をデー
タフロー分析における問題として見ることを含めて、パ
ターン照合の高速化が試みられてきた。

【０００３】本発明の目的に関して、用語「キャラク
タ」は、コードブック内の情報の標準単位または「バイ
ト」、「ニブル」、「ワード」などと同じ意味で使用さ
れる。

【０００４】＜統計的圧縮方法および辞書圧縮方法＞圧
縮とは、データの表現を最小にするためのデータの符号
化である。無損失(Lossless)圧縮とは、原テキストまた
は原キャラクタ列が圧縮された列から得られ、逆も同様
であるような完全に可逆的な機能である。当技術分野で
は、統計的方法、辞書方法または混合方法のいずれかが
使用される。

【０００５】統計的圧縮方法では、キャラクタ単位で、
長いデータ列をより短い列に置換する。この圧縮プロセ
スでは、キャラクタの列が、識別可能な順序のマルコフ
（確率的）ソースによって生成されることと、そのソー
スを正確にモデル化でき、コード化できることを前提と
している。「マルコフ・ソース」とは、記号またはキャ
ラクタの出現確率とその条件確率（記号間影響（inters
ymbol influence）と称する場合もある）をなんらかの
信頼性のある一貫した形でソースから計算できるか推論
できる、キャラクタ列生成機構を指す。これに関して、
モデルとは、テキストを生成する過程の近似である。統
計的圧縮では、モデルを使用して、テキスト列内のキャ
ラクタの出現の予測を形成する。テキストは、入力キャ
ラクタに対するコードの置換の結果として圧縮される。
これに関連して、コードの長さは、そのキャラクタの出
現の推定確率の逆関数として決定される。

【０００６】辞書方法では、連続するキャラクタのグル
ープ（句）を、ある辞書への指標と置換することによっ
て圧縮を達成する。これに関して、キャラクタは、アル
ファベットのメンバであり、アルファベットとは、テキ
スト内で出現する可能性がある全ての可能なキャラクタ
の集合である。圧縮は、辞書にトークンのリストが含ま
れ、このトークンが、平均するとそれによってコード化
されるキャラクタ列（句）より少ない空間を占めるよう
に選択されているという事実によって達成される。

【０００７】＜適応辞書ポインタ・ベース符号化、Ziv-
Lempelコードの諸態様および設計トレードオフ＞適応符
号化とは、圧縮方法のうち、辞書（符号化に使用される
モデル）が、既にコード化されているテキストに基づく
種類のものを指す。これは、「動的符号化」とも称す
る。適応符号化の原理は、Ziv-Lempel（ＬＺ１９７７）
適応辞書符号化に見られる。

【０００８】ＬＺ１９７７符号化においては、句または
キャラクタのサブシーケンスが、そのテキスト列内の前
の出現（occurrence）に対するポインタとして符号化さ
れる。この方法で圧縮されたテキストの復号には、ポイ
ンタを、そのポインタが参照する復号済みのテキストに
単純に置換することだけが必要である。

【０００９】現キャラクタがある列に前に出現したかど
うかを確認するためには、近い過去のキャラクタの一部
と現キャラクタを比較するか、テーブル内でキャラクタ
を表引きするかのいずれかが必要である。単一のポイン
タによって参照できる近い過去の列との一致を見出すこ
とのできる現キャラクタの列が長ければ長いほど、圧縮
率が高くなる。比較の数は、比較される列の長さが増え
るにつれて増加する。

【００１０】適応辞書圧縮は、ポインタによって後ろ向
きに参照できる長さの限界と、この限界内で部分列のど
れかがポインタの目標になりうるかとのトレードオフを
表す。ポインタの到達範囲は、無制限に増大するウィン
ドウとするか、固定サイズのウィンドウとすることがで
きる。固定サイズ・ウィンドウの場合、ポインタは、所
定の数の前キャラクタに制限される。ウィンドウが大き
ければ大きいほど、比較の数が多くなり、パターン一致
が見つかる確度が高くなる。しかし、ウィンドウ・サイ
ズが増大するにつれて、コード化が遅くなり、ポインタ
が大きくなるので圧縮率が低下する可能性がある。

【００１１】テキスト列内の最近の過去のキャラクタを
記憶するための固定サイズ・ウィンドウの利点の１つ
が、ポインタ・サイズが制限されることである。また、
比較の数が制限されるので、パターン一致長が制限さ
れ、コード化速度が高まる。

【００１２】＜ジャクソン（Jackson）特許＞ジャクソ
ン他の米国特許第４０５４９５１号明細書（以下、ジャ
クソン特許と呼称する）には、前に出現したデータ列の
それぞれの出現が、出力ストリームに４次式＜ｉ，ｊ，
ｋ，ｌ＞として付加される、データ・ストリームの辞書
復元方法が開示されている。このｉはフラグまたはトー
クンであり、ｊは部分列の記憶域アドレス、ｋはセクシ
ョンの長さ、ｌは繰り返しの回数である。圧縮されたデ
ータは、ビーム制御装置を駆動するバッファに記憶され
る。原理的に、ジャクソン特許は、ポインタのコード化
と使用されるフィールドに詳細な相違を有するＬＺ１９
７７タイプ辞書圧縮を記載したものである。

【００１３】＜Ziv-Lempelの１９７７と１９７８のコー
ド＞ＬＺ１９７７辞書圧縮コードは、ジブおよびレンペ
ル（Ziv and Lempel）著、"A Universal Algorithm For
Sequential Data Compression", IEEE Trans. Informa
tion Theory, IT-24(3), pages 337-343、１９７７年５
月に記載された。ジブ他による第２の論文、"Compressi
on Of Individual Sequences Via VariableRate Codin
g", IEEE Trans. Information Theory, IT-24 (5), pag
es 530-536、１９７８年９月には、多少異なる辞書圧縮
方法（ＬＺ１９７８コード）が記載されている。

【００１４】ＬＺ１９７８コードでは、最近の過去のテ
キスト列が句（phrase）に解析される。この各句は、前
に見られた最長の一致句に１キャラクタを加えたもので
ある。その後、各句は、その接頭部（prefix）への指標
＋余分のキャラクタとしてコード化される。その後、句
は、たとえばメモリ内でハッシュ化されたアドレスとし
てアドレッシングできる句のリストに追加される。これ
は、前に現れたすべての列の参照にポインタを使用する
ＬＺ１９７７圧縮符号化の代替案である。

【００１５】＜ホワイティング（Whiting）特許とパタ
ーン照合のバック・トゥ・バック問題＞ホワイティング
他の米国特許第５００３３０７号明細書（以下、ホワイ
ティング特許と呼称する）では、修正ＬＺ１９７７圧縮
符号化方法が開示されている。ホワイティング特許で
は、入力キャラクタのそれぞれが、最近の過去のキャラ
クタを含むスライディング・ウィンドウ・タイプのシフ
ト・レジスタ内の各項目に同報通信され、同時に比較さ
れる。一致または不一致は、１キャラクタ位置のシフト
をもたらし、次の入力の同報通信が、レジスタ内容の全
てと比較される。

【００１６】一致する列がシフト・レジスタ内で見つか
った場合、タグ、パターン一致の長さおよび一致する列
のシフト・レジスタ内の位置を差すポインタからなる３
つ組が、圧縮出力列に付加される。一致する列が見つか
らない場合、生データ・タグとそのキャラクタが、出力
列に付加される。

【００１７】ホワイティング特許の１実施例では、探索
を１時に所定の数の入力データ・キャラクタに制限する
ことでポインタが短くなり、もって高速コード化を達成
し、一致したパターンの全てに関して圧縮を保証する。
これは、２キャラクタのパターン一致の確度が、３つ以
上のキャラクタのパターン一致の確度より高いことに基
づいている。

【００１８】ホワイティング特許に関する問題点の１つ
は、パターンが終了し、新しいパターンが始まる時のパ
ターン照合処理にある。すなわち、現一致パターン
（「接頭部（prefix）」とも称する）をさらに拡張する
ことが不可能であり、圧縮エンコーダが、新しい一致パ
ターンまたは接頭部を別の位置から開始させなければな
らない時に、余分な検査とサイクルが必要になる。これ
は、入力キャラクタ・シーケンスが、記憶された記録と
連続的に一致しなくなった時に、一致長を追跡する回路
をリセットして、新しいパターンを追跡できるようにす
る必要があるという事実から派生する。この遅延を、
「バック・トゥ・バック」問題と称する。

【００１９】＜最長パターン一致（「接頭部拡張」とも
称する）の解析と発見＞本明細書の目的に関して、「貪
欲な（greedy）」アルゴリズムとは、大域的な最適とは
異なるという予想が正当な場合であっても、アルゴリズ
ムの繰り返しまたは段のそれぞれで局所的な最適を解と
して選択する、最適化に関する戦略である。貪欲な解析
では、エンコーダが、１つまたは複数の入力キャラクタ
の次の列と一致する、ヒストリ・バッファ、シフト・レ
ジスタなどにある最長の列を探索する。コード化は、パ
ターン比較において最初の不一致が検出された時点で行
われる。

【００２０】下記は、ＬＺ１９７７圧縮方法に見られる
貪欲な解析を示す例である。

【００２１】この方法では、左シフト・レジスタ内のＮ
個のキャラクタの「スライディング・ウィンドウ」を使
用すると仮定する。もちろん、最初の（Ｎ−Ｆ）個のキ
ャラクタが、コード化されており、最後のＦ個のキャラ
クタが、「ルックアヘッド・バッファ」を構成する。

【００２２】実例として、列"abcabcbacbababcab..."
が、Ｎ＝１１およびＦ＝４というパラメータの下でＬＺ
１９７７によってコード化される場合、位置１２のキャ
ラクタが、次にコード化されるキャラクタになる。

【表１】

【００２３】（ａ）次キャラクタをコード化するには、
表１に示されたウィンドウの最初の（Ｎ−Ｆ）個のキャ
ラクタを探索して、ルックアヘッド・バッファとの最長
の一致部分（最長一致）を見つける。この一致は、バッ
ファとオーバーラップしてよいが、バッファ自体になる
ことはできない。（ｂ）次に、最長一致を３つ組＜ｉ，ｊ，ａ＞に符号化
する。ここで、ｉは、ルックアヘッド・バッファからの
最長一致のオフセット、ｊは、一致の長さ、ａは、ウィ
ンドウ内の部分列に一致しなかった最初のキャラクタで
ある。（ｃ）次に、ウィンドウを右にｊ＋１位置またはキャラ
クタだけシフトして、次の符号化ステップに備える。各
ポインタに明示的な最初の非一致キャラクタを付加する
ことによって、ルックアヘッド・バッファ内の最初のキ
ャラクタに関して一致が存在しない場合であっても、コ
ード化を進行できることが保証される。

【００２４】この例では、「ルックアヘッド」・バッフ
ァ内容"babc"に対する「ヒストリ・バッファ」内の最長
一致が、"bab"である。これは、列の位置１０から始ま
る。３つ組＜ｉ，ｊ，ａ＞は、＜２，３，ｃ＞になるは
ずであり、この場合、オフセットは２単位であり、ルッ
クアヘッド・バッファから除去される（一致は位置１０
から始まる）。一致の長さは、３キャラクタを含み（オ
ーバーラップが許される）、ルックアヘッド・バッファ
内の最初の非一致キャラクタは、"c"である。

【００２５】＜パターン照合を拡張するためのデータ・
フロー・モデルと並列性＞計算（すなわちパターン照
合）の並行データ・フロー・モデルで、制御ではなくデ
ータが処置を駆動するという概念が使用されることは既
知である。データ・フロー・モデルとは、データの到着
の際またはデータが使用可能になった際の、値の連続的
な変換を写像したモデルである。したがって、実行の順
序は、データの使用可能性によって記述され、同時使用
可能性が並行実行をもたらすという事実が含まれる。し
たがって、ある計算を、有向非循環グラフ（データ依存
性グラフと称する）に射影して、同時に使用可能なデー
タ要素を識別することができる。

【００２６】また、従来技術では、有限状態機械によっ
て規定される並行データ・フロー・モデルを、ＬＺ１９
７７辞書エンコーダに適用できることが既知である。こ
れによって、前に処理された入力列キャラクタを記憶す
るためのスライディング・ウィンドウとして、内容アド
レス可能メモリ（ＣＡＭ：content addressable memor
y）を使用できるようになる。複数のレジスタと状態制
御式論理機構とＣＡＭを組み合わせる時、入力キャラク
タとスライディング・ウィンドウ内のすべてのキャラク
タの並列の比較照合が容易になる。このような比較は、
キャラクタの一致する列の接頭部拡張または終了のいず
れかを示す。短所は、コード化サイクルあたりに照合す
ることのできるキャラクタの数が限られていることと、
あるパターンが終了し、別のパターン一致が始まる時の
システムのリセットに固有の遅延があることにある。後
者を、「バック・トゥ・バック」問題と称する。

【００２７】

【発明が解決しようとする課題】本発明の目的は、新キ
ャラクタの列と最近の過去に処理された列内のキャラク
タとの間の最長パターン一致を確認する際の１サイクル
あたりのキャラクタ数を増加するための方法および手段
を考案することである。

【００２８】関連目的は、上記の方法および手段を、順
方向また逆方向の再帰的な網羅的貪欲探索（exhaustive
greedy searching）または照合の下で動作可能にする
ことである。ここで「網羅的」とは、組合せ的に全ての
比較対の照合を行う（使い果たす）再帰的あるいは入れ
子式の比較動作をいい、また「貪欲」とは、上述のよう
に、大域的な最適解より局所的な最適解を選択すること
をいう。比較照合を「貪欲」アルゴリズムで行う場合、
最初のもしくは最も近い不一致の時点で２つの列間の最
大長が決定される。

【００２９】もう１つの関連目的は、上記の手段および
方法が、パイプライン・ストールなしにパターン照合の
パイプライン処理と並列組合せ演算子を使用することで
ある。

【００３０】もう１つの関連目的は、上記の手段および
方法を、Ziv-Lempel（ＬＺ１９７７）タイプの連続する
多相（multi-phase）の辞書圧縮および復元方法および
手段の１相として使用することである。

【００３１】

【課題を解決するための手段】原形のＬＺ１９７７符号
化規範（パラダイム）には、下記が含まれる。（１）照合アルゴリズムを使用して、２つの部分列の最
長一致を見つけるステップ。このアルゴリズムは、部分
列の一方がヒストリ・バッファ内の接頭部（prefix：そ
の時点で処理されている部分列に付加される部分列）を
有し、部分列の他方が、ルックアヘッド・バッファ内で
部分的に順序付けられた列の次キャラクタとして接頭部
拡張（prefix extention）を有する場合に動作可能であ
る（この場合、処理の方向自体はルックアヘッド・バッ
ファからヒストリ・バッファである点に注意された
い）。（２）ヒストリ・バッファなどに含まれる列の最近の過
去の部分での相対アドレスなど、より少ないビット数を
用いて一致した最長部分列をコード化するステップ。

【００３２】対照的に、本発明のパラダイムには、
（ａ）複数の最長部分列を解析し、必要な場合にはそれ
らをコード化するステップと、（ｂ）前の列の接頭部を
継続するか打ち切るステップと、（ｃ）次のサイクルの
ための新しい接頭部を決定するステップとが含まれる。

【００３３】本発明では、単一の符号化サイクル中に、
スライディング・ウィンドウ・ヒストリ・バッファに記
憶された第１キャラクタ列のキャラクタが、ルックアヘ
ッド・バッファに記憶された第２キャラクタ列のＮのキ
ャラクタとパターン照合される。しかし、長さＫのキャ
ラクタのパターン照合は、１符号化サイクル中に、下記
によって達成される。（ａ）前記第２列と第１列の間でのキャラクタの部分列
に対する逆方向または順方向の網羅的貪欲比較照合を再
帰的に実行するステップ。この再帰には、第１列から第
２列への接頭部拡張のすべてと、第１列内のすべての部
分列が含まれる。（ｂ）確認されたすべての最大部分列パターン一致のル
ックアヘッド・バッファおよびヒストリ・バッファにお
ける位置を指示し、ルックアヘッド・バッファからヒス
トリ・バッファへＮキャラクタを転送するステップ。

【００３４】再帰的な逆方向または順方向の網羅的貪欲
パターン照合には、関連する２組の制約が使用される。
これらを、パート１制約およびパート２制約と表す。パ
ート２制約では、順方向照合制約に、逆方向照合制約に
対するわずかな相違が含まれる。

【００３５】パート１制約では、逆方向または順方向の
貪欲比較照合が、一致長Ｌ＝Ｋ＋１をもたらす場合に、
接頭部レジスタをＫ＋１の拡張によって更新することが
指定されている。一致長がＬ＜Ｋ＋１であり、最長一致
Ｌ＝１の場合、見つかった最長一致を用いて接頭部レジ
スタを更新し、追跡変数ＪにＪ＝（Ｋ−Ｌ）を割り当
て、パート２制約に従って逆方向または順方向の貪欲パ
ターン照合の処理を継続する。

【００３６】パート２制約では、先行条件として、パー
ト１制約が部分的に処理されたか、逆方向の場合にＪ＞
０、順方向の場合にＪ＜Ｋであることのいずれかが必要
である。パート２には、第１列と第２列の間の最長パタ
ーン一致長Ｌ'を識別するための逆方向または順方向の
貪欲な再帰の実行が含まれる。Ｌ'＝Ｊ＋１の場合、パ
ターン一致が終了する。そうでない場合、追跡変数Ｊ'
を、Ｊ−Ｌ＞０にセットし、パート２に基づいてパター
ン照合を再帰実行する

【００３７】逆方向および順方向の網羅的貪欲パターン
照合ステップは、対象のキャラクタ列の順序が対称であ
る場合を除いて「可換ではない」。したがって、"a,a,
a,a,a,a,..a"や"able was i ere i saw elba"は、同一
の照合結果をもたらすはずである。しかし、順方向再帰
と逆方向再帰の間に大きな圧縮の差が存在することを示
す証拠はない。

【００３８】重要なことは、パート１制約に従って制限
された再帰は、次の符号化サイクルのための列の接頭部
をもたらし、パート２によって支配された再帰は、さま
ざまな長さの部分列の仮の一致のすべての終了を生成す
る。

【００３９】あるパターン一致が終わり別のパターン一
致が始まる場合に従来技術の方法によって引き起こされ
る遅延（バック・トゥ・バック）は、本発明の方法およ
び手段の変形において回避される。この変形では、１対
のシフト・レジスタ内でマークされ、適当なＡＮＤ／Ｏ
Ｒ論理回路を介して表現される継続的な一致終了状況表
示が生成される。

【００４０】例として、１キャラクタ毎コード化サイク
ルの変形では、（ａ）ルックアヘッド・バッファに記憶
されたＮキャラクタの列ａ＝ａ₁、ａ₂、…、ａ_iの部分
列と、接頭部拡張を含むスライディング・ウィンドウ・
ヒストリ・バッファに記憶された列ｂ＝ｂ₁、ｂ₂、…の
キャラクタの部分列との逆方向または順方向の網羅的貪
欲比較照合を再帰的に実行する。これは、（ｂ）ルック
アヘッド・バッファ内の各キャラクタａ_i+1を、複数の
サブステップを同時に利用して処理する点が異なる。こ
の並行サブステップは、（１）スライディング・ウィン
ドウ・ヒストリ・バッファ内の対応位置でのａ_i+1との
一致であるブール値ｍ_i+1を第１シフト・レジスタに書
き込むサブステップと、（２）第１シフト・レジスタの
各段から、所定の段数だけオフセットされた第２シフト
・レジスタの対応段へ、第１レジスタに書き込まれたヒ
ストリ・バッファの対応位置でのａ_iとの一致であるブ
ール値ｍ_iを、同時に書き込むステップと、（３）第１
の種類のブール値がパターン一致継続を表し、第２の種
類のブール値がパターン一致終了を表すように、第１お
よび第２のレジスタの段の各対に対して合計される離接
（ｍ_i ＡＮＤｍ_i+1）として、ブール値信号（一致ル
ックアヘッド：ＭＬＡ信号）を形成するステップとから
なる。

【００４１】この変形は、パート１およびパート２の制
約に従う順方向または逆方向の探索を使用して、１符号
化サイクルあたり１時に２つ以上のキャラクタの照合に
拡張することができる。

【００４２】

【実施例】ここで図１を参照すると、従来技術による内
容アドレス可能メモリ（ＣＡＭ）型ＬＺ１９７７圧縮
エンコーダのパターン照合論理機構が示されている。パ
ターン照合論理機構には、キャラクタ列内の最近の過去
のキャラクタを記憶するためのスライディング・ウィン
ドウ・ヒストリ・バッファとして動作可能なＣＡＭアレ
イ、入力キャラクタをＣＡＭ内のシフト位置に入力する
ための書込選択（ＷＳ）シフト・チェーン、および、対
応する一致出力とさまざまなカウンタおよびバッファに
よってリセットされる際に非同期にセットされる回転可
能な（ＰＳ）シフト・チェーンおよびレジスタが含まれ
る。以下にその主処理ループの擬似コードを示す。

【００４３】

【表２】

【００４４】図１に示された論理機構と上記の制御の擬
似コード・フローを参照すると、これは、照合動作の開
始時に、第１のリエントラント・シフト・レジスタ（Ｐ
Ｓ）に、第１の種類（論理１）のブール値を供給して、
ＣＡＭ内で可能な列一致が発生するすべての場所をマー
クする場合である。状態標識（ＰＳ＿ＳＥＴ信号）を、
論理１にセットする。この標識は、第１レジスタ（Ｐ
Ｓ）内で少なくとも１つの論理１がセットされている限
り、維持される。後続バイトを処理する際に、一致が発
生しても、第１レジスタＰＳに新しいマーカ（論理１）
はセットされない。その代わりに、不一致が発生する
と、対応する第１レジスタ（ＰＳ）のマーカ・ビットが
リセット（破壊）される。これが、状態標識（ＰＳ＿Ｓ
ＥＴ）を論理１から論理０にリセットさせる。これは、
列パターン一致が終了したことを意味する。それと同時
に、一致列の末尾が第２シフト・レジスタ（ＳＳ）内で
論理１によってマークされる。

【００４５】一致長が２以上であったならば、圧縮され
たトークンを生成する。圧縮されたトークンは、接頭部
「１」、オフセット・アドレス、ポインタ長コードから
なる。オフセットは、第２レジスタ（ＳＳ）に記憶され
た第１レジスタ（ＰＳ）最後の活動マーカのうちの１つ
のアドレスから列長を減じたアドレスの剰余減算として
計算される（１未満）。

【００４６】もう一度図１を参照し、かつ上記の擬似コ
ード・ステートメント５ないし７を参照されたい。ステ
ートメント５ないし７は、クリティカルなバック・トゥ
・バック一致動作と呼ばれる。これは、第１レジスタ
（ＰＳ）が、対応する一致によって非同期にリセットさ
れることを必要とする。状態標識（ＰＳ＿ＳＥＴ）は０
であるから、第１レジスタ（ＰＳ）の全ビットが０であ
る。この時、新しい一致がＣＡＭ内の異なる位置で始ま
る可能性があるので、第１レジスタを再ロードしなけれ
ばならない。これは、第１レジスタ（ＰＳ）が、次のコ
ード化サイクルの前にシフト（回転）を必要とすること
を意味する。このような再ロードとシフトが、バック・
トゥ・バック照合での遅延を構成する。

【００４７】＜本発明によるパターン照合論理機構＞こ
こで図２を参照すると、本発明の方法および手段によ
る、パターン照合用の論理配置が示されている。この配
置では、ルックアヘッド・バッファ（図示せず）からの
各キャラクタが、比較論理ゲート５、７および９の組と
一致ルックアサイド論理およびバッファ・ユニット１１
への１入力として、経路１に並列に印加される。スライ
ディング・ウィンドウ・ヒストリ・バッファ３は、それ
に対応する段のそれぞれから比較論理ゲートと一致ルッ
クアサイド論理およびバッファ・ユニット１１へ、経路
１７を介してキャラクタ出力を供給する。

【００４８】比較論理ゲートの出力によって、ヒストリ
・バッファ内の一致位置が識別される。これらの一致表
示は、経路２３を介して一致拡張論理機構１３に印加さ
れる一致ルックアサイド論理およびバッファ・ユニット
１１の状態によって制御される一致拡張論理機構１３内
の位置に、経路２９、３１および３３を介して適用され
る。一致拡張論理機構１３の状態によって、パターン照
合列終了情報が提供される。さらに、一致拡張論理機構
１３は、拡張される接頭部の接頭部レジスタ１５の記憶
を制御するとともに、終了時に経路１９を介して１つま
たは複数の一致列を他所へ転送することを制御する。

【００４９】＜パターン照合論理機構のデータフロー特
性＞図１に関して説明した従来技術は、コード化または
圧縮されるキャラクタごとに複数のマイナー・サイクル
を制御するために有限状態機械を必要とする。対照的
に、本発明の方法および手段では、並行データ・フロー
（ＣＤＦ）の可変マイナー・サイクルが、固定サイクル
のパイプライン式並行データ・フロー（ＰＣＤＦ）に変
換される。具体的な論理実施態様および制御／データ・
フローに関して後で説明するように、ＰＣＤＦは、圧縮
効率の維持する一方でシステム・オーバーヘッドをなく
し、複雑さも適度であるといったＣＤＦに対して複数の
利点を提供する。

【００５０】ここで図３を参照すると、ＬＺ１９７７圧
縮用のパイプライン式並行データフロー（ＰＣＤＦ）高
水準パターン照合論理機構として表現された、図２に示
された配置が示されている。

【００５１】ＰＣＤＦは、機能的には、（１）入力キャ
ラクタのヒストリバッファでの位置を識別する一致レジ
スタ（Ｍ）を形成するヒストリ・バッファ２０３および
比較器２０５と、（２）Ｍに応答し再入経路２１５を有
する主選択（ＰＳ）レジスタ２０７と、（３）Ｍおよび
ＰＳレジスタ２０７からの信号に応答する一致ルックア
ヘッド（ＭＬＡ）ユニット２１７と、（４）一致長カウ
ンタ２１１と、（５）一致長カウンタ２１１と、ＭＬＡ
ユニット２１７からの経路２１９上のＭＬＡ信号とに応
答するオフセット・アドレス計算ユニット２０９とに区
分することができる。

【００５２】ＰＳレジスタ２０７は、シフトおよび並列
ロード（shift-and-parallel-load）のレジスタであ
り、下記の条件実行を行う。ＩＦＭＬＡ＝０Ｔ
ＨＥＮＭをＰＳに並列ロードする、ＥＬＳＥＰＳ内容
をシフトし回転し、シフトされた入力をＭＬによってゲ
ーティングする。

【００５３】ＭＬＡユニット２１７は、ＰＳレジスタ２
０７に対する並列ロードまたは循環シフトを含むフロー
決定をもたらす。これによって、ＰＳが、ＣＤＦ構成で
必要な動作である２つまたは３つの動作を行う必要が１
つに減る。ＭＬＡのフロー決定によって、バック・トゥ
・バック一致の場合であってもパイプライン化されたフ
ローのギャップがなくなる。ＭＬＡには、多入力ＯＲゲ
ート２２５が含まれる。各ＯＲ入力は、ヒストリ・バッ
ファ２０３の位置ｉでの一致のＡＮＤゲート２２１およ
び２２３などの２入力ＡＮＤゲートであり、入力キャラ
クタが、そのＰＳレジスタ出力とＡＮＤされる。

【００５４】オフセット・アドレス計算ユニット２０９
は、ＰＳレジスタ２０７内の最後に残っているマーカの
うちの１つのアドレスを解決する。その後、一致長から
１を減じた値（Ｌ−１）をアドレスから減算して、オフ
セット・アドレスとも称する一致開始位置を得る。最後
に、エッジ検出回路（図示せず）が、経路２１９上のＭ
ＬＡ信号から列一致の終りを導出する。

【００５５】＜新しいパラダイムを使用するパターン照
合と例＞このパラダイムには、スライディング・ウィン
ドウ・ヒストリ・バッファと固定長Ｋのルックアヘッド
・バッファに区分されたシフト・レジスタが包摂され
る。この方法および手段では、（１）必要であれば、キ
ャラクタ列を１つまたは複数の最長部分列に解析して、
複数の最長部分列を見つけ、（２）前の列の接頭部を継
続するか打ち切り、（３）次のコード化サイクルのため
の新しい接頭部を決定する。

【００５６】下記の最大パターン照合の３つの例では、
Ｋ＝５のキャラクタ・ルックアヘッド・バッファと、逆
方向網羅的貪欲パターン照合アルゴリズムを仮定する。

【００５７】

【表３】＜例１＞

【００５８】表３は、本発明のパート１制約に従う接頭
部拡張（一致長）に関する逆方向貪欲探索を示す表であ
る。

【００５９】パート１制約では、下記が提示される。（ａ）逆方向または順方向の貪欲比較照合が、一致長Ｌ
＝Ｋ＋１をもたらす場合、そのＫ＋１拡張で接頭部レジ
スタを更新する。（ｂ）一致長Ｌ＜Ｋ＋１であり、最長一致Ｌ＝１の場
合、見つかった最長一致で接頭部レジスタを更新し、追
跡変数Ｊ＝（Ｋ−Ｌ）を割り当て、パート２に従う逆方
向または順方向の貪欲パターン照合の処理を継続する。

【００６０】この制約を表３に適用すると、逆方向探索
での最長部分列は、"ab"である。Ｌ＝２であるから、Ｌ
＜Ｋ＋１である。この"ab"と一致したルックアヘッドバ
ッファまたはヒストリ・バッファ内の位置は、図２の接
頭部レジスタ１５に記憶される。Ｊ＝Ｋ−Ｌ＝５−２＝
３＞０であるから、逆方向再帰は、パート２制約に従っ
て継続される。

【００６１】

【表４】

【００６２】表４は、本発明のパート２制約に従う接頭
部拡張（一致長）に関する逆方向貪欲探索を示す表であ
る。

【００６３】パート２制約では、先行条件として、パー
ト１が部分的に処理されたか、逆方向の場合にＪ＞０、
順方向の場合にＪ＜Ｋであることのいずれかが必要であ
る。パート２には、第１列と第２列の間の最長パターン
一致長Ｌ'を識別するための逆方向または順方向の貪欲
な再帰の実行が含まれる。Ｌ'＝Ｌ＋１の場合、パター
ン一致が終了する。そうでない場合、追跡変数Ｊ'を、
Ｊ'−Ｌ＞０にセットし、パート２に基づいてパターン
照合を再帰実行する

【００６４】想起されるとおり、追跡変数Ｊ＝Ｋ−Ｌ＝
５−２＝３である。表４では、逆方向再帰が、ルックア
ヘッド・バッファ内で左にＬ＝２キャラクタだけシフト
された点から始まる。したがって、この場合にはＫ＝３
である。この再帰では、逆方向探索の最長部分列が"b"
になる。これは、Ｌ＝１であり、Ｊ＝Ｋ−Ｌ＝３−１＝
２であることを意味する。Ｊ＞０であるから、パート２
制約の下でのもう１つの再帰が呼び出される。

【００６５】

【表５】

【００６６】表５では、再帰が、最後の位置から左に１
位置だけシフトされた点すなわち、Ｋ＝２から始まる。
逆方向探索の最長部分列は、"a"である。Ｌ＝１である
から、Ｊ＝Ｋ−Ｌ＝２−１＝１である。これは、パート
２制約によれば、Ｊ＞０を意味する。したがって、この
制約の下で、もう１つの再帰が行われる。

【００６７】

【表６】

【００６８】この再帰は、最後の位置から左に１位置シ
フトされた点またはＫ＝１から始まる。この再帰の間に
識別される部分列は、"x"である。この部分列は、前の
列の接頭部"xxx"の拡張である。なぜならば、Ｊ＝Ｋ−
Ｌ＝１−１＝０だからである。パート２制約の下でのこ
れ以上の再帰は必要ない。

【００６９】逆方向網羅的貪欲パターン照合アルゴリズ
ムに従って決定される部分列は、"ab"、"b"、"a"およ
び"x"である。これに関して、"ab"は、次のエンコーダ
・サイクルの列接頭部拡張であり、その結果、これはエ
ンコーダに解放されなくなる。しかし、部分列"b"およ
び"a"はエンコーダに解放することができ、その後、"xx
xx"の拡張としての"x"が解放される。

【００７０】パート１に従って制約される再帰は、次の
符号化サイクルのための列接頭部をもたらし、パート２
によって支配される再帰は、さまざまな長さの部分列の
仮の一致のすべての終了を生成することを想起された
い。

【００７１】

【表７】＜例２＞

【００７２】この例では、表７のルックアヘッド・バッ
ファが、Ｋ−１キャラクタ一致で満たされている。具体
的に言うと、逆方向貪欲照合再帰の実行時の最長部分列
が"aaaa"である。"aaaa"と一致する位置は、図２の接頭
部レジスタ１５に記憶される。Ｌ＝４であるから、パー
ト１制約によればＪ＝Ｋ−Ｌ＝５−４＝１であり、Ｊ＞
０という事実に鑑みて、パート２制約に従って再帰が継
続される。

【００７３】

【表８】

【００７４】表８によれば、再帰は左に４位置シフトし
た点から始まる。したがって、Ｋ＝１である。逆方向探
索での最長部分列は、"a"である。したがって、Ｊ＝Ｋ
−Ｌ＝１−１＝０になる。Ｊ＝０であるから、再帰が打
ち切られ、パート２が終了し、ヒストリ・バッファ内の
接頭部"xxx"は拡張できない。

【００７５】逆方向貪欲アルゴリズムによって照合され
た部分列は、"aaaa"、"a"および"xxx"である。これらの
うちで、部分列"aaaa"は、次の符号化サイクルの接頭部
拡張になり、コーダに解放されない。対照的に、部分
列"a"および"xxx"は、コーダに解放される。

【００７６】

【表９】＜例３＞

【００７７】表９では、逆方向再帰貪欲パターン照合か
ら、最大長部分列として一致"aaaaaaaa"またはＬ＝８が
導出される。パート１制約によれば、Ｊ＝Ｋ−Ｌ≦０の
場合に、最長部分列が、前の列接頭部"aaa"の拡張とし
て処理される。これは、再帰の終りであり、列接頭部
は、"aaaaaaaa"に拡張される。

【００７８】＜１コード化サイクルあたり１キャラクタ
のパターン照合論理機構＞ここで図４を参照すると、１
キャラクタ毎サイクルのＬＺ１９７７圧縮コード化を実
現するための、本発明による最大長パターン照合論理配
置が示されている。この構成には、ヒストリ・バッファ
５０５とＡＮＤゲート５０９への入力キャラクタ・アク
セスをゲーティングする書込み選択（ＷＳ）レジスタ５
０３が含まれる。ＷＳには、「０」が１つだけ含まれ、
それ以外のビットは全て「１」である。この単一の
「０」は、キャラクタが書き込まれつつあるヒストリ・
バッファ５０５内の現在位置を表す。各サイクルの後
に、ＷＳレジスタを１位置だけ回転する。ＷＳレジスタ
５０３とヒストリ・バッファ５０５の組合せが、スライ
ディング・ウィンドウに影響を与える。すなわち、ヒス
トリ・バッファは、入力キャラクタ列の最近の過去の部
分から連続して処理された固定された個数のキャラクタ
だけを保持する。新キャラクタがバッファに書き込まれ
るごとに、最も古いキャラクタがバッファから削除され
る。

【００７９】新入力キャラクタが、ＷＳレジスタの
「０」位置によって指定されるヒストリ・バッファ５０
５の位置に書き込まれる時に、その入力キャラクタは、
バッファの全ての位置に記憶されている現キャラクタと
比較される。バッファ内の各段は、比較回路５０７の対
応する１つを駆動する出力を有することに留意された
い。比較回路への入力キャラクタは、経路５０１を介し
て供給される。対応する比較回路５０７に結合されたＡ
ＮＤゲート５０９は、ヒストリ・バッファ５０５内の書
き込まれつつある位置をゲート・アウトする。これによ
って、その位置との比較が強制的に「０」にされる。そ
の後、一致状態を一致レジスタ５１１に記憶する。

【００８０】一致レジスタ５１１は、ＡＮＤゲート５１
３とＯＲゲート５２１によって形成される一致ルックア
ヘッド回路を駆動する。ＡＮＤゲート５１３は、主選択
（ＰＳ）レジスタ５２７の対応位置への負荷経路（経路
５３１、経路５３３ないし５４５とゲート５２５）も駆
動する。ＰＳレジスタ５２７は、ＭＬＡ信号が「０」の
場合には一致レジスタ５１１の内容、ＭＬＡ信号が
「１」の場合には一致ルックアヘッド状態のいずれかを
ロードされる。

【００８１】＜本発明の図４の実施態様による１サイク
ルあたり１キャラクタのパターン照合の例＞もう一度図
４を参照すると、このエンコーダのパターン照合部分に
は、３２キャラクタ項目のＣＡＭ（ＷＳレジスタ５０
３、ヒストリ・バッファ５０５、比較回路５０７および
ＡＮＤゲート５０９）と、対応する３２ビットＭＲ（一
致レジスタ５１１）と、３２ビットＰＳ（ＰＳレジスタ
５２７）が含まれる。このＣＡＭには、左から右へ、位
置０が左端位置の状態で符号が付されている。位置０
は、最初に書き込まれる位置であり、その後、１、２、
…、３１、０、１、…の順で書き込まれる。入力ストリ
ームは下記のとおりであると仮定する。 "abcdefgabcdewxyzabcdxyzabcda..."

【００８２】第１サイクルの後には、レジスタ状態は次
のようになる。 CAM: a_______________________________ MR: 00000000000000000000000000000000 テ゛ータ: a PS: 00000000000000000000000000000000 テ゛ータ: _

【００８３】サイクル２の後には、レジスタ状態は次の
ようになる。 CAM: ab______________________________ MR: 00000000000000000000000000000000 テ゛ータ: b PS: 00000000000000000000000000000000 テ゛ータ: a

【００８４】ＭＲとＰＳに連続する'１'が存在しないの
で、最初の'a'は、符号化ユニットに送られ、そこで生
バイトとして符号化される。サイクル３の後には、レジ
スタ状態は次のようになる。 CAM: abc_____________________________ MR: 00000000000000000000000000000000 テ゛ータ: c PS: 00000000000000000000000000000000 テ゛ータ: b

【００８５】やはり、最初の'b'が符号化ユニットに送
られ、生バイトとして符号化される。この処理は、サイ
クル７の後まで継続し、その時点で、レジスタ状態は次
のようになる。 CAM: abcdefg_________________________ MR: 00000000000000000000000000000000 テ゛ータ: g PS: 00000000000000000000000000000000 テ゛ータ: f

【００８６】サイクル８の後には、レジスタ状態は次の
ようになる。 CAM: abcdefga________________________ MR: 10000000000000000000000000000000 テ゛ータ: a PS: 00000000000000000000000000000000 テ゛ータ: g

【００８７】この時、ＭＲには、既にＣＡＭ内にある最
初の'a'と一致する第２の'a'の位置が格納される。バイ
ト'g'は、符号化ユニットに送られ、生バイトとして符
号化される。サイクル９の後には、レジスタ状態は次の
ようになる。 CAM: abcdefgab_______________________ MR: 01000000000000000000000000000000 テ゛ータ: b PS: 10000000000000000000000000000000 テ゛ータ: a

【００８８】この時、ＭＲには、位置１に'１'が格納さ
れ、ＰＳには、位置０に'１'が格納される。これらの位
置は１つだけオフセットしているので、これは一致する
列が見つかった場合である。

【００８９】一致が継続するか終了するかを判定するた
めには、まずＭＲ（ｉ）とＰＳ（ｉ−１）のＡＮＤをと
る必要がある。すなわち、(Match_Load(0) = MR(0) AND
PS(31), Match_Load(1) = MR(1) AND PS(0), Match_Lo
ad(2) = MR(2) AND PS(1), ..., Match_Load(31) = MR
(31) AND PS(30))を行い、その後、これらのＯＲをと
る。

【００９０】このＯＲゲートの出力を、ＭＬＡ（一致ル
ックアヘッド）と称する。 MLA = Match_Load(0) OR Match_Load(1) OR ... OR Mat
ch_Load(31)

【００９１】ＭＬＡが'１'の場合、列一致が継続する。
この場合、Ｍａｔｃｈ＿Ｌｏａｄ（一致ロード）ビット
がＰＳにロードされる。

【００９２】その一方で、ＭＬＡが'０'の場合、一致が
終了しており、次サイクルで列照合処理を開始するため
にＭＲの内容をＰＳにロードしなければならない。上の
例では、ＭＬＡが'１'であり、したがって、ＰＳにはＭ
ａｔｃｈ＿Ｌｏａｄがロードされる。それと同時に、Ｃ
ＡＭの内容が、次の入力バイトと比較される。

【００９３】最後に、一致の長さを追跡する必要があ
る。これを行うために、一致長カウンタを当初は１にセ
ットする。このカウンタは、ＭＬＡが１になるたびに１
つ増分され、ＭＬＡが０になるたびに１にリセットされ
る。サイクル１０の後に、レジスタ状態は次のようにな
る。 CAM: abcdefgabc______________________ MR: 00100000000000000000000000000000 テ゛ータ: c PS: 01000000000000000000000000000000 テ゛ータ: b

【００９４】やはりＭＬＡは１であり、一致長カウンタ
が１つ増分され、ＰＳにＭａｔｃｈ＿Ｌｏａｄビットが
ロードされる。サイクル１１の後に、レジスタ状態は次
のようになる。 CAM: abcdefgabcd_____________________ MR: 00010000000000000000000000000000 テ゛ータ: d PS: 00100000000000000000000000000000 テ゛ータ: c

【００９５】やはりＭＬＡは１であり、一致長カウンタ
が１つ増分され、ＰＳにＭａｔｃｈ＿Ｌｏａｄビットが
ロードされる。サイクル１２の後に、レジスタ状態は次
のようになる。 CAM: abcdefgabcde____________________ MR: 00001000000000000000000000000000 テ゛ータ: e PS: 00010000000000000000000000000000 テ゛ータ: d

【００９６】サイクル１３の後に、レジスタ状態は次の
ようになる。 CAM: abcdefgabcdew___________________ MR: 00000000000000000000000000000000 テ゛ータ: w PS: 00001000000000000000000000000000 テ゛ータ: e

【００９７】この時点で、ＭＬＡが'０'になる。ＭＬＡ
が'０'であるから、ＰＳに、最長列の最後の一致位置が
格納され、ＭＲに、新列の一致状態が格納される。した
がって、この場合、ＰＳの内容と一致長カウンタの内容
（この場合では５）が符号化ユニットに送られ、圧縮さ
れたトークンが生成される。また、一致長カウンタを１
にリセットする必要があり、ＭＲの内容をＰＳに転送す
る必要がある。これが行われた後に、照合処理の次のサ
イクルを再開することができる。したがって、サイクル
１４の後には、レジスタ状態は次のようになる。 CAM: abcdefgabcdewx__________________ MR: 00000000000000000000000000000000 テ゛ータ: x PS: 00000000000000000000000000000000 テ゛ータ: w

【００９８】この処理は、サイクル１７の後まで継続す
る。 CAM: abcdefgabcdewxyza_______________ MR: 10000001000000000000000000000000 テ゛ータ: a PS: 00000000000000000000000000000000 テ゛ータ: z

【００９９】サイクル１８の後に、レジスタ状態は次の
ようになる。 CAM: abcdefgabcdewxyzab______________ MR: 01000000100000000000000000000000 テ゛ータ: b PS: 10001001000000000000000000000000 テ゛ータ: a

【０１００】ここでもＭＬＡは１であるから、ＰＳにＭ
ａｔｃｈ＿Ｌｏａｄビットがロードされ、一致長カウン
タが１つ増分される。この処理は、サイクル２１の後ま
で継続する。 CAM: abcdefgabcdewxyzabcdx___________ MR: 00000000000001000000000000000000 テ゛ータ: x PS: 00010000001000000000000000000000 テ゛ータ: d

【０１０１】ここでＭＬＡが０になる。そこで、ＰＳと
一致長カウンタが符号化ユニットに送られる。２つの等
しい列（位置０と位置７から始まる列"abcd"）があるの
で、符号化ユニットは、そのうちの１つを選択して、圧
縮されたトークンを生成する。それと同時に、ＰＳにＭ
Ｒの内容がロードされ、一致長カウンタは１にリセット
される。サイクル２２の後には、レジスタ状態は次のよ
うになる。 CAM: abcdefgabcdewxyzabcdxy__________ MR: 00000000000000100000000000000000 テ゛ータ: y PS: 00000000000001000000000000000000 テ゛ータ: x

【０１０２】ＭＬＡは１であるから、もう１つの一致す
る列が見つかっている。この列は、サイクル２８の後ま
で継続する（ＭＬＡが１になる）。 CAM: abcdefgabcdewxyzabcdxyzabcda____ MR: 10000001000000001000000100000000 テ゛ータ: a PS: 00000000000000000001000000000000 テ゛ータ: d

【０１０３】現在ＭＬＡは０であるから、ＰＳと一致長
カウンタの内容が、符号化ユニットに送られ、そこで、
圧縮されたトークンが生成される。次のサイクルでは、
ＣＡＭ用の制御論理機構が、Ｅｎｄ＿Ｏｆ＿Ｆｉｌｅ
（ファイルの終り）信号を生成して、これ以上データ・
バイトが存在せず、列照合処理を終了しなければならな
いことをＭＬＡ回路に伝える。したがって、サイクル２
９の後には、レジスタ状態は次のようになる。 CAM: abcdefgabcdewxyzabcdxyzabcda____ MR: 00000000000000000000000000000000 テ゛ータ: _ PS: 10010001001000001000000000000000 テ゛ータ: a

【０１０４】この時点で、最後の'a'が符号化ユニット
に送られ、生バイトとして符号化される。サイクル３０
の後には、符号化ユニットがＥｎｄ＿Ｏｆ＿Ｆｉｌｅ信
号を受け取り、Ｅｎｄ＿Ｏｆ＿Ｆｉｌｅマーカーの生成
に進み、そのマーカーを出力データ・ストリームの末尾
に付加する。

【０１０５】この１バイト毎サイクル・コード化処理を
一般化して、２バイト毎サイクル、３バイト毎サイクル
などを扱うことができる。

【０１０６】＜新パラダイムの変形を使用する２キャラ
クタ毎コード化サイクル＞ここで図５ないし図７を参照
すると、２キャラクタ毎サイクルのＬＺ１９７７圧縮コ
ード化を実現する、もう１つの最大長パターン照合論理
配置が示されている。２キャラクタ毎サイクルの圧縮で
は、１キャラクタ毎コード化サイクルで説明した逆方向
探索の代わりに、順方向網羅的貪欲パターン照合再帰を
使用して列拡張を行うことができる。重要なことに、こ
の順方向探索は、逆方向探索に適用されたものと実質的
に同一のパート１制約とパート２制約の対象となる。

【０１０７】パターン照合論理機構に、Ｋ＝３キャラク
タ・バイトのルックアヘッド・バッファが含まれると仮
定する。この機構では、下記の順方向制約付き探索が使
用されるはずである。

【０１０８】

【表１０】

【０１０９】表１０では、順方向探索が、パート１制約
の下で２つの処置をもたらす。ヒストリ・バッファ内の
接頭部"xxx"は、第１の再帰の間にルックアヘッド・バ
ッファから"x"を付加することによって打ち切られる。
Ｌ＝１であり、Ｌ＜Ｋ＋１であるから、パート２制約に
従う順方向探索の処理を継続する。

【０１１０】

【表１１】

【０１１１】表１１では、右に１位置シフトした位置か
ら再帰を開始する。最初の最長の一致は、"yz"である。
したがって、Ｋ＝２、Ｌ＝２であり、Ｊ＝Ｋ−（−Ｌ）
＝Ｋ＋Ｌ＝２−（−２）＝４である。ＪはＫ未満ではな
いので、パート２再帰はこれ以上必要ない。部分列"yz"
は、さらに拡張可能な接頭部であることに留意された
い。

【０１１２】

【表１２】

【０１１３】表１２から、逆方向探索が、"xxx"の終了
と新接頭部"xyz"をもたらすことは明らかである。対照
的に、順方向探索は、"xxxx"の終了と新接頭部"yz"をも
たらす。

【０１１４】＜１コード化サイクルあたり２キャラクタ
のパターン照合論理機構＞もう一度図５ないし図７を参
照すると、ＣＡＭは、ヒストリ・バッファを構成する。
また、用語「ルックアサイド」と「ルックアヘッド」
は、交換可能に使用される。

【０１１５】図５の実施例には、スライディング・ウィ
ンドウ・ヒストリ・バッファ（以下、バッファと呼称す
る）６０５と比較論理機構６０７が含まれる。複数の要
素が、図２に示された一致ルックアサイド論理およびバ
ッファ・ユニット１１に関与する。図５からわかるよう
に、これには、書込み選択（ＷＳ）レジスタ６０３と、
バッファ６０５と、ゲート・レジスタ６０４と、図７
の、一致結果を生成する比較回路ＡＮＤ／ＯＲ論理機構
６７７、６７９および６８１が含まれる。この回路に
は、Ｔ１ＢＹＴＥ（ｔ１バイト）およびＴ２ＢＹＴ
Ｅ（ｔ２バイト）と記された２つの入力がある。単一バ
イト圧縮ハードウェアを使用してこれら２バイトを処理
する場合、ｔ１バイトが第１サイクルで処理され、ｔ２
バイトが第２サイクルで処理される。

【０１１６】当初は、ＷＳレジスタ６０３のＷＳ（０）
だけに１つの'０'が格納され、ＷＳアドレスの残りに
は、'１'が格納される。この'０'の位置は、２バイトが
書き込まれる記憶レジスタ内の２つの現在位置を表す。
ＷＳ（ｉ）が０の場合、ＣＡＭ（２×ｉ）にｔ１バイト
が書き込まれ、ＣＡＭ（２×ｉ＋１）にｔ２バイトが書
き込まれる。したがって、ＷＳ内のビット数は、ＣＡＭ
内の位置の数の１／２である。各サイクルの後に、ＷＳ
が１つだけ回転される。

【０１１７】本発明の目的のために、ＣＡＭは、バッフ
ァ６０５、比較論理機構６０７、ゲート・レジスタ６０
４および付随するＷＳレジスタ６０３を含むものとみな
される。

【０１１８】ゲート・レジスタ（Ｇ）は、ＣＡＭのどの
位置に有効なデータが格納されるかを追跡するのに使用
される。当初、Ｇは０にセットされ、各サイクルの後
に、Ｇに「１」がシフトされる。また、各サイクルに２
バイトが書き込まれるので、Ｇのビット数は、ＣＡＭの
位置の数の１／２である。Ｇ（ｉ）が'０'の場合、ＣＡ
Ｍ（２×ｉ）とＣＡＭ（２×ｉ＋１）にはまだ有効なデ
ータが格納されておらず、これら２つの位置の一致結果
をマスクする必要がある。

【０１１９】ｔ１バイトは、必ずＣＡＭの偶数位置に書
き込まれ、ｔ１バイトは、書き込まれている間に、ＣＡ
Ｍ内のすべての位置と比較され、一致状態が生成され
る。ＣＡＭのすぐ右にある比較器の組が、ｔ１バイトと
ＣＡＭの比較に使用される。しかし、この比較結果は、
マスクする必要がある場合があり、比較器の後のＡＮＤ
ゲートの組が、ｔ１比較結果のゲーティングを表す。し
かし、偶数一致と奇数一致のゲーティングは、わずかに
異なる。 t1_match(2×i+1) <= compare(CAM(2×i+1), t1_byte)
AND G(i); t1_match(2×i) <= compare(CAM(2×i), t1_byte)
AND WS(i) AND G(i);

【０１２０】ｔ１バイトは、ＣＡＭ内の奇数位置には絶
対に書き込まれないので、比較結果は、これらの位置に
前に書き込まれたデータが格納されている（Ｇ＝'１'）
場合に有効になる。しかし、偶数位置に関しては、これ
らの位置に前に書き込まれたデータが格納されており
（Ｇ＝'１'）、現在の比較位置が書き込まれていない
（ＷＳ＝'１'）場合に限って有効である。

【０１２１】ｔ２バイトは、必ずＣＡＭの奇数位置に書
き込まれ、ｔ２バイトも、ＣＡＭ内の全ての位置と比較
する必要がある。しかし、ｔ２バイトについては、わず
かな変更がある。単一バイトＣＡＭの場合、ｔ２バイト
が位置２×ｉ＋１に書き込まれる時までに、２×ｉ番目
の位置に既にｔ１バイトが格納されている。したがっ
て、ｔ２バイトは、ｔ２バイトが書き込まれつつある位
置の真下の位置を除く（この場合、ｔ２バイトは、ｔ１
バイトと比較する必要がある）、ＣＡＭ内の全ての位置
と比較する必要がある。

【０１２２】下記を仮定する。

【０１２３】これが必要な理由を知るためには、ｔ１バ
イトがサイクル１で処理され、ｔ２バイトがサイクル２
で処理される単一バイト／サイクルＣＡＭを検討された
い。ｔ２バイトが処理される時までに、ＣＡＭにa a b
c a e f gが格納される。

【０１２４】ｔ１バイトはＣＡＭの奇数位置に絶対に書
き込まれないので、ｔ２バイトは、変更なしでＣＡＭの
奇数位置と比較することができる。偶数ＣＡＭ位置の場
合、ＭＵＸ（マルチプレクサ）を使用して、ｔ２バイト
をＣＡＭの内容と比較するのか、ｔ１バイトと比較する
のかを選択する。ＷＳ（ｉ）＝'１'の場合、ｔ２バイト
はＣＡＭ（２×ｉ）と比較され、ＷＳ（ｉ）＝'０'の場
合、ｔ２バイトはｔ１バイトと比較される。 location(2×i) <= CAM(2×i) when (WS(i) = '1') e
lse t1_byte; location(2×i+1) <= CAM(2×i+1);

【０１２５】最後に、ｔ２バイト一致結果も、マスクす
る必要がある可能性がある。

【０１２６】奇数位置の場合、比較結果は、その位置に
前に書き込まれたデータが格納され（Ｇ＝'１'）、現在
位置が書込み中でない（ＷＳ＝'１'）場合に有効にな
る。偶数位置の場合、比較結果は、ＣＡＭの前の偶数位
置に有効なデータが格納されている場合に有効である。
Ｇ（ｉ）＝０の時には、ＣＡＭ（２×ｉ）とＣＡＭ（２
×ｉ＋１）がまだ書き込まれていないのでこうなる可能
性があり、さもなければ、現在ＣＡＭ（２×ｉ）にｔ１
バイトを書込み中で、ＣＡＭ（２×ｉ＋１）にｔ２バイ
トを書込み中である可能性がある。第１の場合では、ｔ
２ｍａｔｃｈ（２×ｉ＋１）をマスクしなければなら
ないが、第２の場合には、ｔ２ｍａｔｃｈ（２×ｉ＋
１）をマスクしてはならない。しかし、前のＧビットを
調べることによって、どちらの場合であるかを判定する
ことができる。前のＧビットが'０'の場合、ＣＡＭ位置
２×ｉと２×ｉ＋１に有効なデータが格納されている可
能性はなく、比較結果をマスクしなければならない。

【０１２７】しかし、前のＧビットが'１'の場合、これ
は、ＣＡＭ位置２×ｉと２×ｉ＋１に有効なデータが格
納されているか、これらが現在書込み中であるかのいず
れかであることを意味し、このｔ２＿ｍａｔｃｈ（２×
ｉ）とｔ２＿ｍａｔｃｈ（２×ｉ＋１）の両方をマスク
しなければならない。必要なもう１つの変更は、ｔ２＿
ｍａｔｃｈ（０）の場合である。この位置の場合、ゲー
ティングは必要ない。 t2_match(2×i) <= compare(location(2×i), t2_byt
e) AND G (i-1); t2_match(2×i+1) <= compare(location(2×i+1), t2_b
yte) AND G (i) ANDWS (i); t2_match(0) <= compare(location(0), t2_byte);

【０１２８】＜１サイクルあたり２キャラクタの例１＞
１６バイトのＣＡＭが存在し、左が位置０、右が位置１
５であると仮定する。このＣＡＭは、ラップ・アラウン
ドを使用して左から右に書き込まれる。したがって、最
初のサイクルでは位置０および位置１が書き込まれ、次
のサイクルでは位置２および位置３、その次は位置４お
よび位置５、…、位置１４および１５、その次には再び
位置０および位置１が書き込まれる。また、入力ストリ
ームは、"therefore the theme then"であると仮定す
る。ｔ１ＭＲｅｇとｔ２ＭＲｅｇは、一致条件にあ
るラッチされたバージョンである（すなわちレジスタの
出力である）。

【０１２９】サイクル１の後には CAM: th______________ er t2 MReg: 0000000000000000 t1 MReg: 0000000000000000

【０１３０】サイクル２の後には CAM: ther____________ ef t2 MReg: 0000000000000000 t1 MReg: 0000000000000000

【０１３１】サイクル３の後には CAM: theref__________ or t2 MReg: 0000000000000000 t1 MReg: 0010000000000000

【０１３２】サイクル４の後には CAM: therefor________ e t2 MReg: 0000000000000000 t1 MReg: 0000000000000000

【０１３３】サイクル５の後には CAM: therefore ______ th t2 MReg: 0000000000000000 t1 MReg: 0010100000000000

【０１３４】サイクル６の後には CAM: therefore th____ e t2 MReg: 0100000000000000 t1 MReg: 1000000000000000

【０１３５】サイクル７の後には CAM: therefore the __ th t2 MReg: 0000000001000000 t1 MReg: 0010100010000000

【０１３６】サイクル８の後には CAM: therefore the th em t2 MReg: 0100000000010000 t1 MReg: 1000000000100000

【０１３７】サイクル９の後には CAM: emerefore the th e t2 MReg: 0000000000000000 t1 MReg: 0010100010001000

【０１３８】サイクル１０の後には CAM: eme efore the th th t2 MReg: 0000000001000100 t1 MReg: 0000100010001000

【０１３９】サイクル１１の後には CAM: eme thore the th en t2 MReg: 0000000000010001 t1 MReg: 0000000000100010

【０１４０】サイクル１２の後には CAM: eme thene the th __ t2 MReg: 0000000000000000 t1 MReg: 1010000010001000 となる。

【０１４１】＜１サイクルあたり２キャラクタの例２＞
１６キャラクタＣＡＭが入力列"abaaaaaa"と共に使用さ
れると仮定する。

【０１４２】サイクル１の後には CAM: ab______________ aa t2 MReg: 0000000000000000 t1 MReg: 0000000000000000

【０１４３】この場合、ｔ１バイトから見たＣＡＭ
は、"ab______________"を含むように見える。

【０１４４】ｔ２バイトからは、実際には"aba________
_____"を含むＣＡＭが見えなければならない。

【０１４５】この２番目の'a'は、ｔ１バイトに起因す
るものである。図５の比較器６１７に供給するマルチプ
レクサ６１５の組は、この目的のためにある。このマル
チプレクサの組と、それに対応するゲーティング論理機
構６１０が、ルックアヘッド論理機構またはルックアサ
イド論理機構を形成する。ルックアヘッド・バッファ
は、入力バイトを参照するが、ルックアヘッド論理機構
は、ｔ２バイトのために正しい一致状態を生成する論理
機構を指すことに留意されたい。

【０１４６】サイクル２の後には CAM: abaa____________ aa t2 MReg: 1010000000000000 t1 MReg: 1000000000000000

【０１４７】サイクル３の後には CAM: abaaaa__________ aa t2 MReg: 1011100000000000 t1 MReg: 1011000000000000

【０１４８】サイクル４の後には CAM: abaaaaaa________ __ t2 MReg: 1011111000000000 t1 MReg: 1011110000000000 になる。

【０１４９】＜１サイクルあたり２キャラクタのパター
ン照合ルックアヘッド＞第１段の出力（ｔ１＿ｍａｔｃ
ｈとｔ２＿ｍａｔｃｈ）は、ラッチされ、次の段の論理
機構に供給され、そこで、一致ルックアヘッド（ＭＬ
Ａ）状態が生成される。ＭＬＡ信号の生成を、図７に示
す。これらは、単一バイトの場合のＭＬＡの単純な拡張
であり、３ＭＬＡの場合の式は、下記のとおりである
（８バイトＣＡＭの場合）。

【０１５０】 M3Load(0) <= PS(6) AND t1MReg(7) AND t2MReg(0); M3Load(1) <= PS(7) AND t1MReg(0) AND t2MReg(1); M3Load(2) <= PS(0) AND t1MReg(1) AND t2MReg(2); M3Load(3) <= PS(1) AND t1MReg(2) AND t2MReg(3); M3Load(4) <= PS(2) AND t1MReg(3) AND t2MReg(4); M3Load(5) <= PS(3) AND t1MReg(4) AND t2MReg(5); M3Load(6) <= PS(4) AND t1MReg(5) AND t2MReg(6); M3Load(7) <= PS(5) AND t1MReg(6) AND t2MReg(7); MLA3 <= M3Load(0) OR M3Load(1) OR M3Load(2) OR M3L
oad(3) ORM3Load(4) OR M3Load(5) OR M3Load(6) OR M3
Load(7); M2Load(0) <= t1Mreg(7) AND t2MReg(0); M2Load(1) <= t1Mreg(0) AND t2MReg(1); M2Load(2) <= t1Mreg(1) AND t2MReg(2); M2Load(3) <= t1Mreg(2) AND t2MReg(3); M2Load(4) <= t1Mreg(3) AND t2MReg(4); M2Load(5) <= tlMreg(4) AND t2MReg(5); M2Load(6) <= tlMreg(5) AND t2MReg(6); M2Load(7) <= tlMreg(6) AND t2MReg(7); MLA2 <= M2Load(0) OR M2Load(1) OR M2Load(2) OR M2L
oad(3) ORM2Load(4) OR M2Load(5) OR M2Load(6) OR M2
Load(7); M1Load(0) <= PS(7) AND t1MReg(0); M1Load(1) <= PS(0) AND tlMReg(1); M1Load(2) <= PS(1) AND t1MReg(2); M1Load(3) <= PS(2) AND t1MReg(3); M1Load(4) <= PS(3) AND t1MReg(4); M1Load(5) <= PS(4) AND t1MReg(5); M1Load(6) <= PS(5) AND t1MReg(6); MlLoad(7) <= PS(6) AND t1MReg(7); MLA1 <= M1Load(0) OR M1Load(1) OR M1Load(2) OR M1L
oad(3) ORM1Load(4) OR M1Load(5) OR M1Load(6) OR M1
Load(7); MLA3 = MLA(0, 2), MLA2 = MLA(1, 2), MLA1 = MLA(0,
1)

【０１５１】ＰＳは、接頭部拡張または主選択レジスタ
であり、ｔ１ＭＲｅｇおよびｔ２ＭＲｅｇは、ｔ１一致
状態とｔ２一致状態の格納に使用されるレジスタであ
る。ＭＬＡは、どのサイズのＣＡＭについても生成可能
である。下の例では、列照合処理が、順方向で行われ
る。

【０１５２】＜１サイクルあたり２キャラクタの例３＞
ＣＡＭが１６キャラクタ・バイトを記憶し、入力列が"x
yzxxxxxxxyz"であると仮定する。

【０１５３】一致長が１にプリセットされ、ｔ１バイト
がｔ１ＢＲｅｇレジスタに格納され、ｔ２バイトがｔ
２ＢＲｅｇレジスタに格納されることに留意された
い。

【０１５４】サイクル１の後には CAM: xy______________ zx t2 MReg: 0000000000000000 t2 BReg: y t1 MReg: 0000000000000000 t1 BReg: x PS: 0000000000000000 PS Byte: _ Length: 1 になる。

【０１５５】この場合、ＭＬＡ３−１は、全ビット０で
あり、したがって、ＰＳに記憶される列は、これまでに
見つかった最長の列であり、ｔ１ＢＲｅｇは生バイト
である。ＰＳＢｙｔｅには、有効なデータが格納され
ていないので、これをコード化する必要はない。また、
ｔ１ＢＲｅｇは、生バイトとして符号化ユニットに送
られたばかりである。次に、ｔ２ＢｒｅｇをＰＳＢ
ｙｔｅへ、ｔ２ＭＲｅｇをＰＳへコピーする。という
のは、'y'が新列の始まりを表すからである。

【０１５６】サイクル２の後には CAM: xyzx____________ xx t2 MReg: 1000000000000000 t2 BReg: x t1 MReg: 0000000000000000 t1 BReg: z PS: 0000000000000000 PS Byte: y Length: 1 になる。

【０１５７】この場合、ＭＬＡ３−１は全ビット０であ
り、したがって、ＰＳ、ＰＳＢｙｔｅおよびＬｅｎｇ
ｔｈが符号化ユニットに送られ、符号化ユニットでは、
Ｌｅｎｇｔｈが１であるから、ＰＳＢｙｔｅが生バイ
トとして符号化される。また、ｔ１ＢＲｅｇは、生キ
ャラクタまたは生バイトとして符号化ユニットに送られ
る。ここで、ｔ２ＭＲｅｇがＰＳにコピーされ、ｔ２
ＢＲｅｇがＰＳＢｙｔｅにコピーされるように、レ
ジスタ内容をコピーする。

【０１５８】サイクル３の後には CAM: xyzxxx__________ xx t2 MReg: 1001100000000000 t2 BReg: x t1 MReg: 1001000000000000 t1 BReg: x PS: 1000000000000000 PS Byte: x Length: 1 になる。

【０１５９】この場合、ＭＬＡ３＝０であるから、ｔ１
ＢＲｅｇとｔ２Ｂｒｅｇは、どちらも現在ＰＳに記
憶されている列の一部ではない。探索は順方向で実行さ
れているので、ｔ１ＢＲｅｇがＰＳに記憶された列の
一部であるかどうかを判定することが望ましい。しか
し、ＭＬＡ１は０であるから、ｔ１ＢＲｅｇはＰＳに
ある列の一部ではない。したがって、ＰＳに記憶された
列が終了したことがわかり、ＰＳ、ＰＳＢｙｔｅおよ
びＬｅｎｇｔｈが符号化ユニットに送られ、その結果、
ＰＳＢｙｔｅを正しく符号化できるようになる。ここ
で、ＭＬＡ２に対する検査を実行するが、ＭＬＡ２は１
である。これによって、ｔ１ＢＲｅｇとｔ２ＢＲｅ
ｇが、少なくとも２キャラクタ長の列を形成することが
明らかになる。この列は拡張される可能性があるので、
Ｌｅｎｇｔｈを２にセットし、ｔ２ＢＲｅｇをＰＳＢ
ｙｔｅにコピーし、Ｍ２ＬｏａｄをＰＳにコピーする。

【０１６０】サイクル４の後には CAM: xyzxxxxx________ xx t2 MReg: 1001111000000000 t2 BReg: x t1 MReg: 1001110000000000 t1 BReg: x PS: 0000100000000000 PS Byte: x Length: 2 になる。

【０１６１】この場合、ＭＬＡ３＝１であり、これは、
ｔ１ＢＲｅｇとｔ２ＢＲｅｇがＰＳに記憶された列
の一部であることを意味する。Ｌｅｎｇｔｈを２つ増分
し、ｔ２ＢＲｅｇをＰＳＢｙｔｅにコピーし、Ｍ３
ＬｏａｄをＰＳにコピーする。列の終りがまだ見つかっ
ていないので、符号化ユニットにはキャラクタを送らな
い。また、この場合、ＭＬＡ１とＭＬＡ２も１である
が、最長一致を探しているので、ＭＬＡ３がＭＬＡ１や
ＭＬＡ２より高い優先順位を有する。

【０１６２】サイクル５の後には CAM: xyzxxxxxxx______ yz t2 MReg: 1001111110000000 t2 BReg: x t1 MReg: 1001111100000000 t1 BReg: x PS: 0000001000000000 PS Byte: x Length: 4 になる

【０１６３】この場合、ＭＬＡ３がやはり１であるか
ら、Ｌｅｎｇｔｈを２つ増分し、ｔ２ＢＲｅｇをＰＳ
Ｂｙｔｅにコピーし、Ｍ３ＬｏａｄをＰＳにコピーす
る。

【０１６４】サイクル６の後には CAM: xyzxxxxxxxyz____ __ t2 MReg: 0010000000000000 t2 BReg: z t1 MReg: 0100000000000000 t1 BReg: y PS 0000000010000000 PS Byte: x Length: 6 になる。

【０１６５】この時、ＭＬＡ３とＭＬＡ１の両方が０で
あるから、ＰＳに記憶された列が終了した。ここで、Ｐ
Ｓ、ＰＳＢｙｔｅおよびＬｅｎｇｔｈを、符号化ユニ
ットに送る。ＭＬＡ２は１であるから、この列は、少な
くとも２の長さを有する。したがって、Ｌｅｎｇｔｈは
２になり、ｔ２ＢＲｅｇがＰＳＢｙｔｅへ、Ｍ２Ｌ
ｏａｄがＰＳへコピーされる。

【０１６６】サイクル７の後には CAM: xyzxxxxxxxyz____ __ t2 MReg: 0000000000000000 t2 BReg: _ t1 MReg: 0000000000000000 t1 BReg: _ PS: 0010000000000000 PS Byte: z Length: 2 になる。

【０１６７】ここでＭＬＡ３−１は０であるから、ＰＳ
に記憶された列が終了した。ここで、ＰＳ、ＰＳＢｙ
ｔｅおよびＬｅｎｇｔｈを符号化ユニットに送る。入力
キャラクタ／バイトの列を使い果たしたので、ここで処
理を終了する。

【０１６８】１バイトＣＡＭでのように２バイトにまた
がって探すのではなく、２バイトＣＡＭの場合、一致ル
ックアヘッドは、３バイトにまたがって行わなければな
らない。ＭＬＡが生成された後に、ＰＳレジスタのロー
ドを下記に従って制御することができる。ＭＬＡと制御
信号の生成は、図４に示された一致拡張論理機構に対応
する。

【０１６９】ここで図７を参照すると、ＰＳラッチと一
致長カウンタのロードに必要なデータ経路と処理論理機
構が示されている。図５ないし図７に示された論理配置
は、図４の一致拡張論理機構および接頭部レジスタのデ
ータ・フロー論理の回路論理実施態様である。

【０１７０】ここで図８および図９を参照すると、１サ
イクルあたり２キャラクタのパターン照合の実施例で一
致ルックアヘッド（ＭＬＡ）信号の形成に含まれる制御
の流れと選択されたレジスタの状態が示されている。こ
れらの図には、２キャラクタ処理の場合に使用されるス
テップが示され、ＭＬＡ信号の状態が示されている。

【０１７１】＜順方向または逆方向の網羅的貪欲再帰探
索＞１サイクルあたり複数バイトを処理するためには、
ＭＬＡ信号の完全な組を生成しなければならない。ＭＬ
Ａ信号の完全な組が使用可能であるから、ＭＬＡ信号を
テストする順序を変更することによって、順方向または
逆方向のいずれかで探索を行うことができる。

【０１７２】たとえば、１サイクルあたり２キャラクタ
を処理する場合、３つのＭＬＡ信号すなわち、ＭＬＡ
３、ＭＬＡ２およびＭＬＡ１が存在する。まず、ＭＬＡ
３が１であるかどうかを調べるためにテストを行う必要
がある。ＭＬＡ３が１であるならば、最長一致が見つか
っており、ＭＬＡ１やＭＬＡ２をテストする必要はな
い。ＭＬＡ３が０であるならば、ＭＬＡ１とＭＬＡ２を
テストする必要がある。

【０１７３】ＭＬＡ２を先にテストする場合、逆方向探
索が行われている。逆に、ＭＬＡ１を先にテストする場
合、順方向探索が行われている。

【０１７４】＜拡張＞本発明の方法および手段に対する
拡張の１つが、１サイクルあたりに処理されるキャラク
タの数であるキャラクタ容量Ｋを３以上にセットするこ
とである。また、順方向探索を拡張して、この範囲を含
めることができる。これに関しては、図１０を参照され
たい。この図には、１コード化サイクルあたり３キャラ
クタの実施態様での制御の流れと選択されたＭＬＡ信号
の状態が示されている。

【０１７５】まとめとして、本発明の構成に関して以下
の事項を開示する。

【０１７６】（１）ヒストリ・バッファに記憶された第
１キャラクタ列の部分列とルックアヘッド・バッファに
記憶された第２キャラクタ列の部分列との間のパターン
一致を探索するための方法であって、（ａ）順序付けら
れた１組の再帰間隔に沿って順方向または逆方向のいず
れか１つの方向で一貫してバッファ内の第１および第２
のキャラクタ列に対して再帰的比較照合を実行すること
によって、第１キャラクタ列から第２キャラクタ列へ拡
張される部分列接頭部を含む１つまたは複数の最長部分
列を解析するステップと、（ｂ）キャラクタが上記組の
次の再帰間隔にわたって一致を継続するかどうかに従っ
て、ステップ（ａ）の間に解析された前の列の接頭部を
継続するかまたは打ち切るステップと、（ｃ）解析され
た部分列から次サイクル用の新しい接頭部を決定するス
テップとを各サイクル中に含む探索方法。（２）ステップ（ａ）で、再帰的比較照合が、逆方向で
あることを特徴とし、さらに、ルックアヘッド・バッフ
ァ内のすべての部分列を解析するステップを含む、上記
（１）に記載の方法。（３）ヒストリ・バッファに記憶された第１キャラクタ
列の部分列とルックアヘッド・バッファに記憶された第
２キャラクタ列の部分列との間でのパターン一致を探索
するための方法であって、（ａ）第１キャラクタ列と第
２キャラクタ列に対してこれらの間でのキャラクタの部
分列に対して同一の再帰方向で一貫して比較照合を再帰
的に実行することによって、第１キャラクタ列から第２
キャラクタ列に拡張されるどんな接頭部をも含む、第２
列のキャラクタと第１列のキャラクタとの間の最大部分
列パターン一致をすべて確認するステップと、（ｂ）確
認された全ての最大部分列パターン一致のルックアヘッ
ド・バッファおよびヒストリ・バッファでの位置を指示
し、そのサイクル中にルックアヘッド・バッファからヒ
ストリ・バッファへの接頭部拡張を終了するキャラクタ
を転送するステップと、（ｃ）第２キャラクタ列が使い
果たされるまで、ステップ（ａ）およびステップ（ｂ）
を繰り返すステップとを各サイクル中に含む、探索方
法。（４）ステップ（ａ）で、再帰方向が逆方向であり、ヒ
ストリ・バッファ内の第１列のキャラクタを含みこれを
通って延びるキャラクタの数が増加する入れ子式順序で
ルックアヘッド・バッファ内の第２列のキャラクタを出
す、上記（３）に記載の方法。（５）ステップ（ａ）で、再帰方向が逆方向であり、ル
ックアヘッド・バッファ内の第２列のキャラクタを含み
これを通って延びるキャラクタの数が増加する入れ子式
順序でヒストリ・バッファ内の第１列のキャラクタを出
す、上記（３）に記載の方法。（６）第１キャラクタ列と第２キャラクタ列との間のパ
ターン一致を探索するための方法であって、（ａ）各サイクル中に、（１）ヒストリ・バッファ（Ｃ
ＡＭ）に記憶される前記第１キャラクタ列とルックアヘ
ッド・バッファに記憶される前記第２キャラクタ列に対
してこれらの間でキャラクタの部分列に対して逆方向の
網羅的貪欲比較照合を再帰的に実行することによって、
第１キャラクタ列から第２キャラクタ列へ拡張されるど
んな接頭部をも含む、第２列のキャラクタと第１列のキ
ャラクタとの間の最大部分列パターン一致をすべて確認
するステップと、（２）確認された全ての最大部分列パ
ターン一致のルックアヘッド・バッファおよびヒストリ
・バッファでの位置を指示し、そのサイクル中にルック
アヘッド・バッファからヒストリ・バッファへ処理され
たキャラクタを転送するステップと、（ｂ）第２列が使い果たされるまで、ステップ（ａ）を
繰り返すステップとを含む方法。（７）前記方法のステップ（ａ）が、さらに、（３）最
大パターン一致の終了位置を示す信号に応答して、ヒス
トリ・バッファ内での以前に出現した一致したパターン
を示すポインタを出力列に付加し、空のパターン列一致
をトークンおよび生キャラクタとして出力列に付加する
ステップを含む、上記（３）または上記（６）のいずれ
かに記載の方法。（８）ステップ（ａ）の（１）が、さらに、逆方向の網
羅的貪欲探索を再帰的に実行することによって、ルック
アヘッド・バッファ内の第２列のキャラクタの間の最大
部分列パターン一致を確認するステップを含む、上記
（６）に記載の方法。（９）ヒストリ・バッファ（ＣＡＭ）に記憶された第１
キャラクタ列ｂ＝ｂ₁、ｂ₂、…、ｂ_kと、入力列ａ＝
ａ₁、ａ₂、…、ａ_i、ａ_i+1、…との間のパターン一致を
探索するための方法であって、前記方法が、１再帰処理
ごとに１キャラクタの速度で動作可能であり、（ａ）第
ｉ回目の再帰処理中に、ヒストリ・バッファの内容ｂと
入力列からのａ_iを並列に比較照合し、第１シフト・レ
ジスタの各対応段にキャラクタの一致または不一致を示
すブール値ｍ_iを書き込み、前記ヒストリ・バッファに
ａ_iを書き込むステップと、（ｂ）第（ｉ＋１）回目の
再帰処理中に、ａ_i+1を次の入力列キャラクタとして、
ステップ（ａ）を繰り返し、所定の段数だけオフセット
された第２シフト・レジスタの対応段に、第１シフト・
レジスタの各段からのブール値ｍ_iを同時に書き込み、
第１シフト・レジスタにブール値ｍ_i+1を書き込み、第
１の種類のブール値がパターン一致の継続を表し、第２
の種類のブール値がパターン一致の終了を表すように、
第１および第２のシフト・レジスタの段の対のそれぞれ
に対して加算される離接（ｍ_i ＡＮＤｍ_i+1）として
ブール信号を形成するステップと、（ｃ）入力キャラク
タ列が終了するまで、ステップ（ａ）およびステップ
（ｂ）を繰り返すステップとを含む方法。（１０）コード化サイクルごとに１キャラクタの速度
で、部分的に順序付けられた出力列に入力列ａ＝ａ₁、
ａ₂、…、ａ_i、ａ_i+1、…を圧縮するための方法であっ
て、（ａ）第ｉ回目の再帰処理中に、ヒストリ・バッフ
ァ（ＣＡＭ）の内容ｂ＝ｂ₁、ｂ₂、…、ｂ_kと入力列か
らのａ_iを並列に比較照合し、第１シフト・レジスタの
対応段のそれぞれに一致または不一致を示すブール値ｍ
_iを書き込み、ヒストリ・バッファ中にａ_iをシフトする
ステップと、（ｂ）第（ｉ＋１）回目の再帰処理中に、
次の入力キャラクタａ_i+1に関してステップ（ａ）を繰
り返し、それと同時に、所定の段数だけオフセットされ
た第２シフト・レジスタの対応段に第１シフト・レジス
タから内容ｍ_iを書き込み、第１レジスタにブール値ｍ
_i+1を書き込み、第１の種類のブール値がパターン一致
の継続を表し、第２の種類のブール値がパターン一致の
終了を表すように、第１および第２のレジスタの段のそ
れぞれに対して加算される離接（ｍ_i ＡＮＤｍ_i+1）と
してブール信号を形成するステップと、（ｃ）パターン
一致終了を示す信号に応答して、ヒストリ・バッファ内
で一致したパターンが以前に出現したことを示すポイン
タを出力列に付加し、空長のパターン列一致をトークン
および生キャラクタとして出力列に付加するステップ
と、（ｄ）入力キャラクタ列を使い果たすまで、ステッ
プ（ａ）ないしステップ（ｃ）を繰り返すステップとを
含む方法。（１１）キャラクタの入力列の現部分が、ルックアヘッ
ド・バッファ内に置かれており、さらに、ステップ
（ａ）およびステップ（ｂ）が、それぞれの再帰処理を
逆方向で実行するサブステップと、ヒストリ・バッファ
に置かれる列のキャラクタを含みこれを通って延びるキ
ャラクタの数が増加する入れ子式順序でルックアヘッド
・バッファ内の入力列のキャラクタを出すサブステップ
とを含む、上記（１０）に記載の方法。（１２）ヒストリ・バッファに記憶された第１キャラク
タ列の部分列と、ルックアヘッド・バッファに記憶され
た第２キャラクタ列の部分列との間の長さＫのキャラク
タ・パターンの一致を探索するための方法であって、各
サイクル中に、（ａ）順序付けられた１組の再帰間隔に沿って順方向ま
たは逆方向のうち選択されたいずれか１つの方向で一貫
してバッファ内の第１および第２のキャラクタ列に対し
て再帰的に比較照合を実行することによって、第１キャ
ラクタ列から第２キャラクタ列へ拡張される部分列接頭
部を含む１つまたは複数の最長部分列を解析するステッ
プであって、さらに（１）逆方向または順方向の比較照
合が一致長Ｌ＝Ｋ＋１をもたらす場合に、Ｋ＋１のキャ
ラクタ接頭部拡張を用いて接頭部レジスタを更新するサ
ブステップと、（２）一致長Ｌ＜Ｋ＋１であり、最長一
致Ｌ＝１である場合に、見つかった最長の一致を用いて
接頭部レジスタを更新し、追跡変数Ｊ＝（Ｋ−Ｌ）を割
り当てるサブステップと、（３）逆方向の再帰的比較照
合に関してＪ＞０の場合、または順方向の比較照合に関
してＪ＜Ｋの場合に、第１および第２の列の間の最長パ
ターン一致長Ｌ'がＬ'＝Ｊ＋１となって、パターン一致
が終了するか、あるいはこのサブステップでパターン照
合を再帰呼出しするまで、元々実行されたのと同じ方向
でバッファ内の第１および第２の列に対して再帰的比較
照合を再実行することによって、Ｌ'を識別するサブス
テップとを含む前記解析ステップと（ｂ）確認された全ての最大部分列パターン一致のルッ
クアヘッド・バッファおよびヒストリ・バッファでの位
置を指示し、そのサイクル中にルックアヘッド・バッフ
ァからヒストリ・バッファへ延びる接頭部で終了するキ
ャラクタを転送し、接頭部レジスタ内容をこの方法の外
部での処理のために使用可能にするステップと、（ｃ）第２キャラクタ列を使い果たすまでステップ
（ａ）およびステップ（ｂ）を繰り返すステップとを含
む方法。（１３）前記Ｋが、第２キャラクタ列の長さ未満の任意
の正の整数のキャラクタ数を構成する、上記（１２）に
記載の方法。（１４）前記方法がさらに、（ｄ）接頭部レジスタに常
駐する最大パターン一致終了の位置を示す信号に応答し
て、ヒストリ・バッファ内での一致したパターンが前に
出現したことを示すポインタを出力列に付加し、空長の
パターン列一致をトークンおよび生キャラクタとして出
力列に付加するステップを含む、上記（１２）に記載の
方法。（１５）ヒストリ・バッファに記憶された第１キャラク
タ列の部分列とルックアヘッド・バッファに記憶された
第２キャラクタ列の部分列との間のパターン一致を探索
するためのシステムであって、ルックアヘッド・バッフ
ァから所定の数のキャラクタを転送し、ヒストリ・バッ
ファ内で最も古い同数のキャラクタを排除する手段を含
み、さらに、順序付けられた１組の再帰間隔に沿って順
方向または逆方向のいずれか１つの方向で一貫してバッ
ファ内の第１および第２のキャラクタ列に対して再帰的
比較照合を実行することによって、第１キャラクタ列か
ら第２キャラクタ列へ拡張される部分列接頭部を含む１
つまたは複数の最長部分列を解析する手段と、キャラク
タが上記組の次の再帰間隔にわたって一致を継続するか
どうかに従って、前記解析手段によって解析された前の
列の接頭部を継続するかまたは打ち切り、また、ルック
アヘッド・バッファ内の第２のキャラクタ列の接頭部拡
張で終了する複数のキャラクタをヒストリ・バッファに
転送する手段を含む手段と、解析された部分列から次サ
イクルのための新しい接頭部を決定する手段とを含むシ
ステム。（１６）列内の最近の過去のキャラクタを記憶するため
の記憶装置（ＣＡＭ）と、現在処理中のキャラクタを記
憶するためのルックアヘッド・バッファと、ルックアヘ
ッド・バッファ内のキャラクタのパターンに一致する最
近の過去のキャラクタのパターンを有するＣＡＭ内の位
置を確認するための手段とを有するパターン一致の探索
システムにおいて、（ａ）ルックアヘッド・バッファ内
に置かれたキャラクタ列とＣＡＭに置かれたキャラクタ
列とに対して再帰的に逆方向の比較照合を実行すること
によって、ルックアヘッド・バッファ内のどんな部分列
をもまたルックアヘッド・バッファからＣＡＭに延びる
キャラクタのどんな部分列接頭部をも含む１つまたは複
数の最大長部分列を解析するためのパターン照合手段を
含む手段と、（ｂ）確認された全ての最大部分列パター
ン一致のルックアヘッド・バッファおよびＣＡＭでの位
置を指示し、そのサイクル中にルックアヘッド・バッフ
ァからＣＡＭへ延びる接頭部で終了するキャラクタを転
送し、接頭部レジスタ内容をこのシステムの外部での処
理のために使用可能にする手段と、（ｃ）第２キャラク
タ列を使い果たすまで、解析手段と位置指示手段を呼び
出す手段とを含むシステム。

【０１７７】

【発明の効果】本発明は、新キャラクタの列と最近の過
去に処理された列内のキャラクタとの間の最長パターン
一致を確認する際の１サイクルあたりのキャラクタ数を
増加する。本発明によれば、パイプライン式並行データ
フロー・モデルを使用し、短縮された時間でキャラクタ
列の間のＫキャラクタ毎サイクルの最大長パターン一致
を確認するための手段および方法が提供される。このデ
ータフロー・モデルでは、一貫した方向での列間の再帰
的な網羅的貪欲比較照合によって、最長一致の解析がも
たらされる。この再帰は、固定長Ｋ、一致長Ｌおよび追
跡変数Ｊの間の関係によって制約され、この制約は、あ
る列から別の列への接頭部拡張と列内パターン一致を確
認するそれ以降の再帰を支配する。１時に１キャラク
タ、２キャラクタまたは３キャラクタに等しいＫを処理
する実施例が可能である。

【図面の簡単な説明】

【図１】従来技術によるＣＡＭ型ＬＺ１９７７圧縮エン
コーダのパターン照合論理機構と主処理ループを示す図
である。

【図２】複数キャラクタ毎サイクルＬＺ１９７７圧縮コ
ード化を実行するための一致ルックアサイド論理を含む
最大長パターン照合ネットワークに関する、本発明によ
る全般的な論理配置を示す図である。

【図３】ＬＺ１９７７圧縮用のパイプライン式並行デー
タフロー（ＰＣＤＦ）高水準パターン照合論理機構とし
ての図２に示された配置を示す図である。

【図４】１サイクルあたり１キャラクタのＬＺ１９７７
圧縮コード化を実現するための、本発明による最大長パ
ターン照合論理配置を示す図である。

【図５】１サイクルあたり２キャラクタのＬＺ１９７７
圧縮コード化を実現するための、もう１つの最大長パタ
ーン照合論理配置を示す図である。

【図６】１サイクルあたり２キャラクタのＬＺ１９７７
圧縮コード化を実現するための、もう１つの最大長パタ
ーン照合論理配置を示す図である。

【図７】１サイクルあたり２キャラクタのＬＺ１９７７
圧縮コード化を実現するための、もう１つの最大長パタ
ーン照合論理配置を示す図である。

【図８】１サイクルあたり２キャラクタのパターン照合
実施例で一致ルックアヘッド（ＭＬＡ）信号の形成に含
まれる制御の流れと選択されたレジスタの状態を示す図
である。

【図９】１サイクルあたり２キャラクタのパターン照合
実施例で一致ルックアヘッド（ＭＬＡ）信号の形成に含
まれる制御の流れと選択されたレジスタの状態を示す図
である。

【図１０】１サイクルあたり３キャラクタのＬＺ１９７
７圧縮コード化を処理するために拡張された順方向網羅
的貪欲パターン照合から一致ルックアヘッド信号を形成
する際の制御の流れと選択されたレジスタの状態を示す
図である。

【符号の説明】

２０３ヒストリ・バッファ２０５比較器２０７主選択（ＰＳ）レジスタ２０９オフセット・アドレス計算ユニット２１１一致長カウンタ２１７一致ルックアヘッド（ＭＬＡ）ユニット２２１ＡＮＤゲート２２３ＡＮＤゲート２２５多入力ＯＲゲート

───────────────────────────────────────────────────── フロントページの続き (72)発明者ヤンシー・チェンアメリカ合衆国95120 カリフォルニア州サンノゼマウント・パクロン・ドライブ 6654

Claims

【特許請求の範囲】

【請求項１】ヒストリ・バッファに記憶された第１キャ
ラクタ列の部分列とルックアヘッド・バッファに記憶さ
れた第２キャラクタ列の部分列との間のパターン一致を
探索するための方法であって、（ａ）順序付けられた１組の再帰間隔に沿って順方向ま
たは逆方向のいずれか１つの方向で一貫してバッファ内
の第１および第２のキャラクタ列に対して再帰的比較照
合を実行することによって、第１キャラクタ列から第２
キャラクタ列へ拡張される部分列接頭部を含む１つまた
は複数の最長部分列を解析するステップと、（ｂ）キャラクタが上記組の次の再帰間隔にわたって一
致を継続するかどうかに従って、ステップ（ａ）の間に
解析された前の列の接頭部を継続するかまたは打ち切る
ステップと、（ｃ）解析された部分列から次サイクル用の新しい接頭
部を決定するステップとを各サイクル中に含む探索方
法。
【請求項２】ステップ（ａ）で、再帰的比較照合が、逆
方向であることを特徴とし、さらに、ルックアヘッド・
バッファ内のすべての部分列を解析するステップを含
む、請求項１に記載の方法。
【請求項３】ヒストリ・バッファに記憶された第１キャ
ラクタ列の部分列とルックアヘッド・バッファに記憶さ
れた第２キャラクタ列の部分列との間でのパターン一致
を探索するための方法であって、（ａ）第１キャラクタ列と第２キャラクタ列に対してこ
れらの間でのキャラクタの部分列に対して同一の再帰方
向で一貫して比較照合を再帰的に実行することによっ
て、第１キャラクタ列から第２キャラクタ列に拡張され
るどんな接頭部をも含む、第２列のキャラクタと第１列
のキャラクタとの間の最大部分列パターン一致をすべて
確認するステップと、（ｂ）確認された全ての最大部分列パターン一致のルッ
クアヘッド・バッファおよびヒストリ・バッファでの位
置を指示し、そのサイクル中にルックアヘッド・バッフ
ァからヒストリ・バッファへの接頭部拡張を終了するキ
ャラクタを転送するステップと、（ｃ）第２キャラクタ列が使い果たされるまで、ステッ
プ（ａ）およびステップ（ｂ）を繰り返すステップとを
各サイクル中に含む、探索方法。
【請求項４】ステップ（ａ）で、再帰方向が逆方向であ
り、ヒストリ・バッファ内の第１列のキャラクタを含み
これを通って延びるキャラクタの数が増加する入れ子式
順序でルックアヘッド・バッファ内の第２列のキャラク
タを出す、請求項３に記載の方法。
【請求項５】ステップ（ａ）で、再帰方向が逆方向であ
り、ルックアヘッド・バッファ内の第２列のキャラクタ
を含みこれを通って延びるキャラクタの数が増加する入
れ子式順序でヒストリ・バッファ内の第１列のキャラク
タを出す、請求項３に記載の方法。
【請求項６】第１キャラクタ列と第２キャラクタ列との
間のパターン一致を探索するための方法であって、（ａ）各サイクル中に、（１）ヒストリ・バッファ（Ｃ
ＡＭ）に記憶される前記第１キャラクタ列とルックアヘ
ッド・バッファに記憶される前記第２キャラクタ列に対
してこれらの間でキャラクタの部分列に対して逆方向の
網羅的貪欲比較照合を再帰的に実行することによって、
第１キャラクタ列から第２キャラクタ列へ拡張されるど
んな接頭部をも含む、第２列のキャラクタと第１列のキ
ャラクタとの間の最大部分列パターン一致をすべて確認
するステップと、（２）確認された全ての最大部分列パ
ターン一致のルックアヘッド・バッファおよびヒストリ
・バッファでの位置を指示し、そのサイクル中にルック
アヘッド・バッファからヒストリ・バッファへ処理され
たキャラクタを転送するステップと、（ｂ）第２列が使い果たされるまで、ステップ（ａ）を
繰り返すステップとを含む方法。
【請求項７】前記方法のステップ（ａ）が、さらに、
（３）最大パターン一致の終了位置を示す信号に応答し
て、ヒストリ・バッファ内での以前に出現した一致した
パターンを示すポインタを出力列に付加し、空のパター
ン列一致をトークンおよび生キャラクタとして出力列に
付加するステップを含む、請求項３または請求項６のい
ずれかに記載の方法。
【請求項８】ステップ（ａ）の（１）が、さらに、逆方
向の網羅的貪欲探索を再帰的に実行することによって、
ルックアヘッド・バッファ内の第２列のキャラクタの間
の最大部分列パターン一致を確認するステップを含む、
請求項６に記載の方法。
【請求項９】ヒストリ・バッファ（ＣＡＭ）に記憶され
た第１キャラクタ列ｂ＝ｂ₁、ｂ₂、…、ｂ_kと、入力列
ａ＝ａ₁、ａ₂、…、ａ_i、ａ_i+1、…との間のパターン一
致を探索するための方法であって、前記方法が、１再帰
処理ごとに１キャラクタの速度で動作可能であり、（ａ）第ｉ回目の再帰処理中に、ヒストリ・バッファの内容ｂと入力列からのａ_iを並列
に比較照合し、第１シフト・レジスタの各対応段にキャラクタの一致ま
たは不一致を示すブール値ｍ_iを書き込み、前記ヒスト
リ・バッファにａ_iを書き込むステップと、（ｂ）第（ｉ＋１）回目の再帰処理中に、ａ_i+1を次の入力列キャラクタとして、ステップ（ａ）
を繰り返し、所定の段数だけオフセットされた第２シフト・レジスタ
の対応段に、第１シフト・レジスタの各段からのブール
値ｍ_iを同時に書き込み、第１シフト・レジスタにブール値ｍ_i+1を書き込み、第１の種類のブール値がパターン一致の継続を表し、第
２の種類のブール値がパターン一致の終了を表すよう
に、第１および第２のシフト・レジスタの段の対のそれ
ぞれに対して加算される離接（ｍ_i ＡＮＤｍ_i+1）と
してブール信号を形成するステップと、（ｃ）入力キャラクタ列が終了するまで、ステップ
（ａ）およびステップ（ｂ）を繰り返すステップとを含
む方法。
【請求項１０】コード化サイクルごとに１キャラクタの
速度で、部分的に順序付けられた出力列に入力列ａ＝ａ
₁、ａ₂、…、ａ_i、ａ_i+1、…を圧縮するための方法であ
って、（ａ）第ｉ回目の再帰処理中に、ヒストリ・バッファ
（ＣＡＭ）の内容ｂ＝ｂ₁、ｂ₂、…、ｂ_kと入力列から
のａ_iを並列に比較照合し、第１シフト・レジスタの対
応段のそれぞれに一致または不一致を示すブール値ｍ_i
を書き込み、ヒストリ・バッファ中にａ_iをシフトする
ステップと、（ｂ）第（ｉ＋１）回目の再帰処理中に、次の入力キャ
ラクタａ_i+1に関してステップ（ａ）を繰り返し、それ
と同時に、所定の段数だけオフセットされた第２シフト
・レジスタの対応段に第１シフト・レジスタから内容ｍ
_iを書き込み、第１レジスタにブール値ｍ_i+1を書き込
み、第１の種類のブール値がパターン一致の継続を表
し、第２の種類のブール値がパターン一致の終了を表す
ように、第１および第２のレジスタの段のそれぞれに対
して加算される離接（ｍ_i ＡＮＤｍ_i+1）としてブール
信号を形成するステップと、（ｃ）パターン一致終了を示す信号に応答して、ヒスト
リ・バッファ内で一致したパターンが以前に出現したこ
とを示すポインタを出力列に付加し、空長のパターン列
一致をトークンおよび生キャラクタとして出力列に付加
するステップと、（ｄ）入力キャラクタ列を使い果たすまで、ステップ
（ａ）ないしステップ（ｃ）を繰り返すステップとを含
む方法。
【請求項１１】キャラクタの入力列の現部分が、ルック
アヘッド・バッファ内に置かれており、さらに、ステッ
プ（ａ）およびステップ（ｂ）が、それぞれの再帰処理
を逆方向で実行するサブステップと、ヒストリ・バッフ
ァに置かれる列のキャラクタを含みこれを通って延びる
キャラクタの数が増加する入れ子式順序でルックアヘッ
ド・バッファ内の入力列のキャラクタを出すサブステッ
プとを含む、請求項１０に記載の方法。
【請求項１２】ヒストリ・バッファに記憶された第１キ
ャラクタ列の部分列と、ルックアヘッド・バッファに記
憶された第２キャラクタ列の部分列との間の長さＫのキ
ャラクタ・パターンの一致を探索するための方法であっ
て、各サイクル中に、（ａ）順序付けられた１組の再帰間隔に沿って順方向ま
たは逆方向のうち選択されたいずれか１つの方向で一貫
してバッファ内の第１および第２のキャラクタ列に対し
て再帰的に比較照合を実行することによって、第１キャ
ラクタ列から第２キャラクタ列へ拡張される部分列接頭
部を含む１つまたは複数の最長部分列を解析するステッ
プであって、さらに（１）逆方向または順方向の比較照
合が一致長Ｌ＝Ｋ＋１をもたらす場合に、Ｋ＋１のキャ
ラクタ接頭部拡張を用いて接頭部レジスタを更新するサ
ブステップと、（２）一致長Ｌ＜Ｋ＋１であり、最長一
致Ｌ＝１である場合に、見つかった最長の一致を用いて
接頭部レジスタを更新し、追跡変数Ｊ＝（Ｋ−Ｌ）を割
り当てるサブステップと、（３）逆方向の再帰的比較照
合に関してＪ＞０の場合、または順方向の比較照合に関
してＪ＜Ｋの場合に、第１および第２の列の間の最長パ
ターン一致長Ｌ'がＬ'＝Ｊ＋１となって、パターン一致
が終了するか、あるいはこのサブステップでパターン照
合を再帰呼出しするまで、元々実行されたのと同じ方向
でバッファ内の第１および第２の列に対して再帰的比較
照合を再実行することによって、Ｌ'を識別するサブス
テップとを含む前記解析ステップと（ｂ）確認された全ての最大部分列パターン一致のルッ
クアヘッド・バッファおよびヒストリ・バッファでの位
置を指示し、そのサイクル中にルックアヘッド・バッフ
ァからヒストリ・バッファへ延びる接頭部で終了するキ
ャラクタを転送し、接頭部レジスタ内容をこの方法の外
部での処理のために使用可能にするステップと、（ｃ）第２キャラクタ列を使い果たすまでステップ
（ａ）およびステップ（ｂ）を繰り返すステップとを含
む方法。
【請求項１３】前記Ｋが、第２キャラクタ列の長さ未満
の任意の正の整数のキャラクタ数を構成する、請求項１
２に記載の方法。
【請求項１４】前記方法がさらに、（ｄ）接頭部レジスタに常駐する最大パターン一致終了
の位置を示す信号に応答して、ヒストリ・バッファ内で
の一致したパターンが前に出現したことを示すポインタ
を出力列に付加し、空長のパターン列一致をトークンお
よび生キャラクタとして出力列に付加するステップを含
む、請求項１２に記載の方法。
【請求項１５】ヒストリ・バッファに記憶された第１キ
ャラクタ列の部分列とルックアヘッド・バッファに記憶
された第２キャラクタ列の部分列との間のパターン一致
を探索するためのシステムであって、ルックアヘッド・
バッファから所定の数のキャラクタを転送し、ヒストリ
・バッファ内で最も古い同数のキャラクタを排除する手
段を含み、さらに、順序付けられた１組の再帰間隔に沿って順方向または逆
方向のいずれか１つの方向で一貫してバッファ内の第１
および第２のキャラクタ列に対して再帰的比較照合を実
行することによって、第１キャラクタ列から第２キャラ
クタ列へ拡張される部分列接頭部を含む１つまたは複数
の最長部分列を解析する手段と、キャラクタが上記組の次の再帰間隔にわたって一致を継
続するかどうかに従って、前記解析手段によって解析さ
れた前の列の接頭部を継続するかまたは打ち切り、ま
た、ルックアヘッド・バッファ内の第２のキャラクタ列
の接頭部拡張で終了する複数のキャラクタをヒストリ・
バッファに転送する手段を含む手段と、解析された部分列から次サイクルのための新しい接頭部
を決定する手段とを含むシステム。
【請求項１６】列内の最近の過去のキャラクタを記憶す
るための記憶装置（ＣＡＭ）と、現在処理中のキャラク
タを記憶するためのルックアヘッド・バッファと、ルッ
クアヘッド・バッファ内のキャラクタのパターンに一致
する最近の過去のキャラクタのパターンを有するＣＡＭ
内の位置を確認するための手段とを有するパターン一致
の探索システムにおいて、（ａ）ルックアヘッド・バッファ内に置かれたキャラク
タ列とＣＡＭに置かれたキャラクタ列とに対して再帰的
に逆方向の比較照合を実行することによって、ルックア
ヘッド・バッファ内のどんな部分列をもまたルックアヘ
ッド・バッファからＣＡＭに延びるキャラクタのどんな
部分列接頭部をも含む１つまたは複数の最大長部分列を
解析するためのパターン照合手段を含む手段と、（ｂ）確認された全ての最大部分列パターン一致のルッ
クアヘッド・バッファおよびＣＡＭでの位置を指示し、
そのサイクル中にルックアヘッド・バッファからＣＡＭ
へ延びる接頭部で終了するキャラクタを転送し、接頭部
レジスタ内容をこのシステムの外部での処理のために使
用可能にする手段と、（ｃ）第２キャラクタ列を使い果たすまで、解析手段と
位置指示手段を呼び出す手段とを含むシステム。