JP4556766B2

JP4556766B2 - 文字列検索回路及び文字列検索方法

Info

Publication number: JP4556766B2
Application number: JP2005149713A
Authority: JP
Inventors: 寿幸廣瀬
Original assignee: Sony Corp
Current assignee: Sony Corp
Priority date: 2005-05-23
Filing date: 2005-05-23
Publication date: 2010-10-06
Anticipated expiration: 2025-05-23
Also published as: CN1870131B; CN1870131A; US7221291B2; JP2006332775A; US20060261988A1

Description

本発明は、例えばＬＺ７７法を採用したデータ圧縮回路内に設けられる文字列検索回路に関し、特に、文字列検索処理の高速化を図ったものに関する。

辞書型のデータ圧縮アルゴリズムの一種として、ＬＺ（Lempel-Ziv）７７法が存在している。ＬＺ７７法は、例えばＡＩＴフォーマット，Ｓ−ＡＩＴフォーマットまたはＬＴＯフォーマットのテープドライブ内のＡＬＤＣ（Adaptive Lossless Data Compression）エンコーダなど、各種のデータ記録装置内のデータ圧縮回路に採用されている（例えば、特許文献１参照。）。

ＬＺ７７法の圧縮原理は、過去に入力された文字列（データ列）のうちの直近の所定サイズの文字列を辞書に登録し、新たに入力された（すなわち、圧縮しようとする）文字列と一致する文字列をその辞書から検索して、当該新たに入力された文字列をその一致する文字列のアドレス情報で置き換えるというものである。この辞書は、静的なものではなく、圧縮が進むにつれて、今まさに圧縮しようとする文字列の直前の文字列を追加して古い文字列を除外するようにアップデートされるので、スライド辞書とも呼ばれる。

図７は、この辞書からの文字列の検索の様子を例示する図である。通常は辞書のサイズは５１２バイト，１０２４バイトまたは２０４８バイトであることが多いが、ここでは説明の都合上１６バイトとしている。過去に入力された文字列のうちの直近の１６文字の文字列「ＡＢＣＣＡＢ…ＢＣＣ」（各文字Ａ，Ｂ，Ｃは１バイト）が辞書として登録されている。１６バイト前に入力された文字「Ａ」にはアドレス０が付与されており、１５バイト前に入力された文字「Ｂ」にはアドレス１が付与されており、１バイト前に入力された文字「Ｃ」にはアドレス１５が付与されている。

例えば、新たに入力された文字列が「ＡＢＣＡ」である場合には、辞書内のアドレス９〜１２の文字列が「ＡＢＣＡ」と一致する。そこで、この場合には、マッチアドレス（一致する文字列の最後のアドレスとして定義されるアドレス）として１２を出力する。（最終的には、文字列「ＡＢＣＡ」を先頭アドレス９と一致長４とで置換することにより、４バイトの文字列「ＡＢＣＡ」が２バイトに圧縮される。）

また例えば、新たに入力された文字列が「ＡＢＣ」である場合には、辞書内のアドレス０〜２，４〜６，９〜１１，１２〜１４の文字列がそれぞれ「ＡＢＣ」と一致する。そこで、この場合には、マッチアドレス（一致する文字列の最後のアドレスとして定義されるアドレス）として２，６，１１及び１４を出力する。

このように、ＬＺ７７法では、圧縮しようとする文字列に一致する文字列を辞書から検索することによって圧縮を行う。そのため、ＬＺ７７法を採用したデータ圧縮回路内には、この検索処理を行う文字列検索回路が設けられる。

図８は、ＬＺ７７法を採用したデータ圧縮回路内に従来設けられていた文字列検索回路の構成を示すブロック図である。図示しないメモリ（例えばＳＲＡＭ）内のバイト数Ｎの辞書の各アドレスｉ（ｉ＝０〜Ｎ−１）に対応して、比較回路５１（ｉ），２入力１出力のアンド回路５２（ｉ），２入力１出力のマルチプレクサ５３（ｉ）及びＤ型フリップ・フロップ５４（ｉ）から成るＮ組の回路群が設けられている。また、Ｎ入力１出力のオア回路５５が設けられている。

各比較回路５１（ｉ）は、検索対象の文字と辞書の対応するアドレスｉの文字とを比較し、比較結果ｍ［ｉ］（一致するとき‘１’になり不一致のとき‘０’になる信号）を出力する。このｍ［ｉ］は、同じ組のアンド回路５２（ｉ）の一方の入力端に供給されるとともに、同じ組のマルチプレクサ５３（ｉ）の入力端Ｓ２に供給される。

各アンド回路５２（ｉ）のもう一方の入力端には、辞書の１つ手前のアドレスに対応する組のフリップ・フロップ５４（ｉ）の出力であるｐｓ［ｉ−１］が供給される（例えばアンド回路５２（Ｎ−１）であれば、フリップ・フロップ５４（Ｎ−２）の出力であるｐｓ［Ｎ−２］が供給される）。各アンド回路５２（ｉ）の出力ｐｓ＿ａｎｄ＿ｍ［ｉ］（ｍａｔｃｈとも呼ぶことにする）は、同じ組のマルチプレクサ５３（ｉ）の入力端Ｓ１に供給されるとともに、オア回路５５に供給される。

オア回路５５の出力ｏｒｆｂ（or feed back）は、各組のマルチプレクサ５３（ｉ）の選択制御端子Ｃに供給される。このｏｒｆｂは、ｐｓ＿ａｎｄ＿ｍ［０］〜ｐｓ＿ａｎｄ＿ｍ［Ｎ−１］のうちのいずれか１つのｍａｔｃｈが‘１’であるとき（今回の検索対象の文字列に一致する文字列が辞書に１つでも存在するとき）に‘１’になり、ｐｓ＿ａｎｄ＿ｍ［０］〜ｐｓ＿ａｎｄ＿ｍ［Ｎ−１］が全て‘０’であるとき（今回の検索対象の文字列に一致する文字列が辞書に存在しないとき）に‘０’になる。すなわち、ｏｒｆｂは、各クロック周期において、検索対象に一致する文字が辞書に存在するか否かを示す一致／不一致信号である。

各マルチプレクサ５３（ｉ）は、このｏｒｆｂが‘１’のときには、入力端Ｓ１に供給されたｐｓ＿ａｎｄ＿ｍ［ｉ］を選択して出力端Ｄから出力し、他方、このｏｒｆｂが‘０’のときには、入力端Ｓ２に供給されたｍ［ｉ］を選択して出力端Ｄから出力する。各マルチプレクサ５３（ｉ）の出力は、同じ組のフリップ・フロップ５４（ｉ）のＤ入力端に供給されて、次の入力があるまで出力端Ｑに保持される。各フリップ・フロップ５４（ｉ）の出力端Ｑに保持されている出力ｐｓ［ｉ］は、前述のように、辞書の１つ後のアドレスに対応する組のアンド回路５２（ｉ）にｐｓ［ｉ−１］として供給される。

なお、図８にはブロック図を示したが、ＡＳＩＣ（特定用途向けＬＳＩ）やプログラマブル・ロジック・デバイス（ＦＰＧＡ等）として設計する場合には、この文字列検索回路は、ハードウェア記述言語の一種であるVerilog ＨＤＬを用いて図９のように表記することができる。

この文字列検索回路では、１回（動作クロックの１周期）毎に、入力された文字列の１文字ずつについて、その文字に一致する文字を辞書から検索し、且つ、検索対象と一致する文字が辞書に存在するか否かを示すｏｒｆｂを作成する。そして、検索対象と一致する文字が辞書に存在する場合には、検索結果を次回のクロック周期で利用して、検索対象の文字数を１文字ずつ増やしていく。

すなわち、新たに入力された文字列が例えば「ＡＢＣＡ」であれば、この文字列検索回路は、次の手順で検索を行う。
・１回目：１文字目の「Ａ」と一致する文字を辞書から検索する。
・２回目：「Ａ」と一致する文字が辞書に存在する場合、２文字目の「Ｂ」と一致する文字を辞書から検索し、前回の「Ａ」の検索結果を利用して、「ＡＢ」と一致する文字列を検索する。
・３回目：「ＡＢ」と一致する文字列が辞書に存在する場合、３文字目の「Ｃ」と一致する文字を辞書から検索し、前回の「ＡＢ」の検索結果を利用して、「ＡＢＣ」と一致する文字列を検索する。
・４回目：「ＡＢＣ」と一致する文字列が辞書に存在する場合、４文字目の「Ａ」と一致する文字を辞書から検索し、前回の「ＡＢＣ」の検索結果を利用して、「ＡＢＣＡ」と一致する文字列を検索する。

図１０は、この文字列検索回路の動作を、図７の辞書から「ＡＢＣＡ」を検索する過程において、「ＡＢＣ」の検索結果を利用して「ＡＢＣＡ」を検索する場合（前述の４回目の検索）を例にとって示す図である。アドレスｉ＝０，４，９，１２の文字が「Ａ」に一致するので、アドレスｉ＝０，４，９，１２に対応する組の比較回路５１（ｉ）の比較結果ｍ［ｉ］は‘１’になり、残りのアドレスに対応する組の比較回路５１（ｉ）の比較結果ｍ［ｉ］は‘０’になる。

また、前述の３回目の検索（３文字目の「Ｃ」の検索）ではアドレスｉ＝２，６，１１，１４に対応する組のフリップ・フロップ５４（ｉ）の出力ｐｓ［ｉ］が‘１’になっているので、アドレスｉ＝２，６，１１，１４よりも１つ後のアドレスｉ＝３，７，１２，１５に対応する組のアンド回路５２（ｉ）に供給されるｐｓ［ｉ−１］は‘１’になり、残りの組のアンド回路５２（ｉ）に供給されるｐｓ［ｉ−１］は‘０’になる。

その結果、アドレスｉ＝１２に対応する組のアンド回路５２（ｉ）の出力ｐｓ＿ａｎｄ＿ｍ［ｉ］（ｍａｔｃｈ）のみが‘１’になり、残りの組のアンド回路５２（ｉ）の出力ｐｓ＿ａｎｄ＿ｍ［ｉ］（ｍａｔｃｈ）は‘０’になる。

そして、１つのｐｓ＿ａｎｄ＿ｍ［ｉ］が‘１’であることからオア回路５５の出力ｏｒｆｂが‘１’になるので、各マルチプレクサ５３（ｉ）でｐｓ＿ａｎｄ＿ｍ［ｉ］が選択されて、それらのｐｓ＿ａｎｄ＿ｍ［ｉ］が各フリップ・フロップ５４（ｉ）の出力端Ｑに保持される。このようにして、既に図７を用いて説明したようにして、文字列「ＡＢＣＡ」と一致する文字列のマッチアドレス１２が求められる。

図１０には文字列「ＡＢＣＡ」と一致する文字列が存在する例を示したが、文字列「ＡＢＣＡ」と一致する文字列が存在しない場合（全ての組のアンド回路５２（ｉ）の出力ｐｓ＿ａｎｄ＿ｍ［ｉ］が‘０’になった場合）には、オア回路５５の出力ｏｒｆｂが‘０’になるので、各マルチプレクサ５３（ｉ）でｍ［ｉ］が選択されて、それらのｍ［ｉ］が各フリップ・フロップ５４（ｉ）の出力端Ｑに保持される。これにより、４文字目の「Ａ」から、前述のような１文字ずつの手順で再検索が開始される。

図８の文字列検索回路は、オア回路５５の出力ｏｒｆｂを遅延させることなく各組のマルチプレクサ５３（ｉ）に供給するので、「遅延０」の回路と呼ぶ。

国際公開番号Ｗ０２００３／０３２２９６の再公表特許公報（第１２〜１３頁、第３図、第４図）

ところで、図８の文字列検索回路は、次のような理由から、文字列検索処理を高速化するのに不向きであった。すなわち、この文字列検索回路は、各フリップ・フロップ５４（ｉ）の出力ｐｓ［ｉ］がアンド回路５２（ｉ）やオア回路５５での処理を経て再びフリップ・フロップ５４（ｉ）に入力するループ構造になっているので、このループが高速に動作することが文字列検索処理の高速化の必要条件になる。しかるに、ｏｒｆｂを出力するオア回路５５は、複雑な組み合わせ回路であり遅延量が大きいため、このループがクリティカルパス（遅延の最も大きい経路）になる。そのため、このループによって動作クロックの最大周波数が制限されるので、高速化に不向きであった。

ここで、回路の動作速度を上げる一般的な方法としては、回路中にフリップ・フロップのような遅延手段を挿入することによって処理をパイプライン化するという方法が知られている。しかし、図８の文字列検索回路において、単純にオア回路５５の後段にフリップ・フロップを挿入してｏｒｆｂを遅延させたのでは、「各クロック周期における検索結果を次回のクロック周期に利用する」というアルゴリズムが別のアルゴリズムに変わってしまうので、本来の動作をしなくなってしまう。

本発明は、上述の点に鑑み、ＬＺ７７法を採用したデータ圧縮回路内に設けられる文字列検索回路のように、動作クロックの１周期毎に、入力された文字列の１文字ずつについて、その文字に一致する文字を辞書から検索し、且つ、検索対象と一致する文字が辞書に存在するか否かを示す一致／不一致信号を作成し、検索対象と一致する文字が辞書に存在する場合には、検索結果を次回のクロック周期で利用して、検索対象の文字数を１文字ずつ増やすようにした文字列検索回路において、パイプライン処理による文字列検索の高速化を実現することを課題としてなされたものである。

この課題を解決するために、本発明に係る文字列検索回路は、動作クロックの１周期毎に、入力された文字列の１文字ずつについて、その文字に一致する文字を辞書から検索し、且つ、検索対象と一致する文字が辞書に存在するか否かを示す一致／不一致信号を作成し、検索対象と一致する文字が辞書に存在する場合には、検索結果を次回のクロック周期で利用して、検索対象の文字数を１文字ずつ増やすようにした文字列検索回路において、この一致／不一致信号を、この動作クロックのｎ周期分（ｎは１以上の整数）遅延させる遅延手段と、或るクロック周期における検索結果を予測する信号として、そのクロック周期よりもｎ−１周期前からそのクロック周期までのｎ個の周期の各々（ただしｎ＝１の場合はそのクロック周期の１周期のみ）について、検索対象と一致する文字が辞書に存在する状態と辞書に存在しない状態との２つの状態をそれぞれ仮定し、この２つの状態をこのｎ個の周期分組み合わせた２^ｎ通りの信号を予め作成する作成手段と、この遅延手段によって遅延された一致／不一致信号に従い、この作成手段によって作成された２^ｎ通りの信号のうち仮定が正しかった信号を選択する選択手段とを備え、この選択手段によって選択された信号を、次回のクロック周期において利用するようにしたことを特徴とする。

この文字列検索回路では、各クロック周期において作成される、検索対象と一致する文字が辞書に存在するか否かを示す一致／不一致信号（前出の図８のｏｒｆｂのような信号）が、ｎクロック周期分遅延される。また、或るクロック周期における検索結果を予測する信号として、そのクロック周期よりもｎ−１周期前からそのクロック周期までのｎ個の周期の各々（ただしｎ＝１の場合はそのクロック周期の１周期のみ）について、検索対象と一致する文字が辞書に存在する状態と辞書に存在しない状態との２つの状態をそれぞれ仮定し、この２つの状態をこのｎ個の周期分組み合わせた２^ｎ通りの信号が、予め作成される。

そして、この遅延された一致／不一致信号に従い、この２^ｎ通りの信号のうち仮定が正しかった１つの信号が選択され、その選択された信号が、次回のクロック周期において利用される。

これにより、「各クロック周期における検索結果を次回のクロック周期に利用する」というアルゴリズムを変えることなく、前出の図８の出力ｏｒｆｂのような一致／不一致の結果を示す信号を遅延させて、パイプライン処理による文字列検索の高速化を実現することができる。

次に、本発明に係る文字列検索方法は、動作クロックの１周期毎に、入力された文字列の１文字ずつについて、その文字に一致する文字を辞書から検索し、且つ、検索対象と一致する文字が辞書に存在するか否かを示す一致／不一致信号を作成し、検索対象と一致する文字が辞書に存在する場合には、検索結果を次回のクロック周期で利用して、検索対象の文字数を１文字ずつ増やすようにした文字列検索方法において、この一致／不一致信号を、この動作クロックのｎ周期分（ｎは１以上の整数）遅延させる第１のステップと、或るクロック周期における検索結果を予測する信号として、そのクロック周期よりもｎ−１周期前からそのクロック周期までのｎ個の周期の各々（ただしｎ＝１の場合はそのクロック周期の１周期のみ）について、検索対象と一致する文字が辞書に存在する状態と辞書に存在しない状態との２つの状態をそれぞれ仮定し、この２つの状態をこのｎ個の周期分組み合わせた２^ｎ通りの信号を予め作成する第２のステップと、この第１のステップによって遅延された一致／不一致信号に従い、この第２のステップによって作成された２^ｎ通りの信号のうち仮定が正しかった信号を選択する第３のステップとを有し、この第３のステップによって選択された信号を、次回のクロック周期において利用するようにしたことを特徴とする。

この文字列検索方法によれば、前述の、本発明に係る文字列検索回路について述べたのと全く同様にして、「各クロック周期における検索結果を次回のクロック周期に利用する」というアルゴリズムを変えることなく、前出の図８の出力ｏｒｆｂのような一致／不一致の結果を示す信号を遅延させて、パイプライン処理による文字列検索の高速化を実現することができる。

本発明によれば、入力された文字列に一致する文字列を辞書から検索する処理を、動作クロックの１周期毎に、前回のクロック周期における検索結果を利用して１文字ずつ文字数を増やして行う文字列検索回路において、パイプライン処理による文字列検索の高速化を実現できるという効果が得られる。

以下、ＬＺ７７法を採用したデータ圧縮回路内に設けられる文字列検索回路に本発明を適用した例について、図面を用いて具体的に説明する。

〔遅延１の回路〕
最初に、図８の文字列検索回路を前提として、各クロック周期に作成されるｏｒｆｂを１クロック周期だけ遅延させる文字列検索回路（「遅延１」の回路）について説明する。

図１は、この「遅延１」の回路による文字列検索の高速化の原理を示す図である。ｏｒｆｂは‘１’か‘０’か（一致する文字列が存在するか否か）の２つの状態しかとらないので、或るクロック周期における検索結果ｐｓ［ｉ］を予測する信号として、そのクロック周期にはｏｒｆｂ＝‘１’になると仮定したｐｓ１［ｉ］と、そのクロック周期にはｏｒｆｂ＝‘０’になると仮定したｐｓ０［ｉ］との２通りの信号を予め作成しておく。（時刻ｔは、この或るクロック周期内の時刻を表しており、時刻ｔ−１は、ｐｓ１［ｉ］，ｐｓ０［ｉ］を作成するクロック周期内の時刻を表している。）

そして、時刻ｔにはｏｒｆｂ＝‘１’，ｏｒｆｂ＝‘０’とのうちのどちらの仮定が正しかったのかが判明するので、検索結果予測ｐｓ１［ｉ］，ｐｓ０［ｉ］のうち正しかったほうを選択し、その選択した信号を次回のクロック周期において利用する。（図１の例ではｏｒｆｂ＝‘０’が正しかったことが判明するので、ｐｓ０［ｉ］を選択する）。

これにより、動作クロックの各周期におけるｏｒｆｂを１クロック周期だけ遅延させて、パイプライン処理による文字列検索の高速化を実現することができる。

図２は、この「遅延１」の文字列検索回路の構成を示すブロック図である。図示しないメモリ（例えばＳＲＡＭ）内のバイト数Ｎの辞書の各アドレスｉ（ｉ＝０〜Ｎ−１）に対応して、比較回路１（ｉ），２入力１出力のアンド回路２（ｉ），２入力１出力のアンド回路３（ｉ），２入力１出力のマルチプレクサ４（ｉ），Ｄ型フリップ・フロップ５（ｉ）及びＤ型フリップ・フロップ６（ｉ）から成るＮ組の回路群が設けられている。

また、Ｎ入力１出力のオア回路７と、Ｎ入力１出力のオア回路８と、オア回路７及び８の出力が供給される２入力１出力のマルチプレクサ９と、マルチプレクサ９の出力が供給されるＤ型フリップ・フロップ１０とが設けられている。

各比較回路１（ｉ）は、検索対象の文字と辞書の対応するアドレスｉの文字とを比較し、一致するとき‘１’になり不一致のとき‘０’になる信号ｍ［ｉ］を出力する。この出力ｍ［ｉ］は、同じ組のアンド回路２（ｉ）及び３（ｉ）の一方の入力端に供給されるとともに、同じ組のＤ型フリップ・フロップ６（ｉ）のＤ入力端に供給されて、次の入力があるまで出力端Ｑに保持される。

各アンド回路２（ｉ）のもう一方の入力端には、辞書の１つ手前のアドレスに対応する組のフリップ・フロップ５（ｉ）の出力であるｐｓ１［ｉ−１］が供給される（例えばアンド回路２（Ｎ−１）であれば、フリップ・フロップ５（Ｎ−２）の出力であるｐｓ１［Ｎ−２］が供給される）。各アンド回路２（ｉ）の出力ｐｓ１＿ａｎｄ＿ｍ［ｉ］は、同じ組のマルチプレクサ４の入力端Ｓ１に供給されるとともに、オア回路７に供給される。

各アンド回路３（ｉ）のもう一方の入力端には、辞書の１つ手前のアドレスに対応する組のフリップ・フロップ６（ｉ）の出力であるｐｓ０［ｉ−１］が供給される（例えばアンド回路２（Ｎ−１）であれば、フリップ・フロップ５（Ｎ−２）の出力であるｐｓ０［Ｎ−２］が供給される）。各アンド回路３（ｉ）の出力ｐｓ０＿ａｎｄ＿ｍ［ｉ］は、同じ組のマルチプレクサ４の入力端Ｓ２に供給されるとともに、オア回路８に供給される。

オア回路７，８の出力は、それぞれマルチプレクサ９の入力端Ｓ１，Ｓ２に供給される。マルチプレクサ９の出力端Ｄから出力された信号は、Ｄ型フリップ・フロップ１０のＤ入力端に供給されて、次の入力があるまで出力端Ｑに保持される。このＤ型フリップ・フロップ１０の出力は、各クロック周期におけるｏｒｆｂ（検索対象の文字列と一致する文字列が辞書に存在するか否かを示す信号）を１クロック周期だけ遅延させたｏｒｆｂ＿ｄとして、マルチプレクサ９の選択制御端子Ｃに供給されるとともに、各組のマルチプレクサ４（ｉ）の選択制御端子Ｃに供給される。

マルチプレクサ９は、この出力ｏｒｆｂ＿ｄが‘１’であるとき（すなわち、１クロック周期前の検索対象の文字列に一致する文字列が辞書中に１つでも存在したとき）には、入力端Ｓ１に供給されたオア回路７の出力を、今回のクロック周期における検索結果として選択して、出力端Ｄから出力する。他方、この出力ｏｒｆｂ＿ｄが‘０’であるとき（すなわち、１クロック周期前の検索対象の文字列に一致する文字列が辞書中に存在しなかったとき）には、入力端Ｓ２に供給されたオア回路８の出力を、今回のクロック周期における検索結果として選択して、出力端Ｄから出力する。

各マルチプレクサ４（ｉ）は、この出力ｏｒｆｂ＿ｄが‘１’であるとき（１クロック周期前の検索対象の文字列に一致する文字列が辞書中に１つでも存在したとき）には、入力端Ｓ１に供給されたｐｓ１＿ａｎｄ＿ｍ［ｉ］を選択して出力端Ｄから出力する。他方、この出力ｏｒｆｂ＿ｄが‘０’のとき（１クロック周期前の検索対象の文字列に一致する文字列が辞書中に存在しなかったとき）には、入力端Ｓ２に供給されたｐｓ０＿ａｎｄ＿ｍ［ｉ］を選択して出力端Ｄから出力する。

各マルチプレクサ４（ｉ）の出力は、同じ組のフリップ・フロップ５（ｉ）のＤ入力端に供給されて、次の入力があるまで出力端Ｑに保持される。各フリップ・フロップ５（ｉ）の出力端Ｑに保持されている出力ｐｓ１［ｉ］は、前述のように、辞書の１つ後のアドレスに対応する組のアンド回路２（ｉ）にｐｓ１［ｉ−１］として供給される。

各フリップ・フロップ６（ｉ）の出力端Ｑに保持されている出力ｐｓ０［ｉ］は、前述のように、辞書の１つ後のアドレスに対応する組のアンド回路２（ｉ）にｐｓ０［ｉ−１］として供給される。

なお、図２にはブロック図を示したが、ＡＳＩＣ（特定用途向けＬＳＩ）やプログラマブル・ロジック・デバイス（ＦＰＧＡ等）として設計する場合には、この文字列検索回路は、ハードウェア記述言語の一種であるVerilog ＨＤＬを用いて図３のように表記することができる。

この文字列検索回路では、動作クロックの各周期におけるｏｒｆｂを、１クロック周期だけ遅延させる。そして、或るクロック周期における文字列の検索結果を予測する信号として、そのクロック周期にはｏｒｆｂ＝‘１’になる仮定した検索結果予測（各フリップ・フロップ５（ｉ）の出力ｐｓ１［ｉ］）と、そのクロック周期にはｏｒｆｂ＝‘０’になる仮定した検索結果予測（各フリップ・フロップ６（ｉ）の出力ｐｓ０［ｉ］）との２通りの信号を、そのクロック周期の１周期前に予め作成して、辞書の１つ後のアドレスに対応する組のアンド回路２（ｉ），３（ｉ）にそれぞれｐｓ１［ｉ−１］，ｐｓ０［ｉ−１］として供給する。

そして、どちらの仮定が正しかったのかが１クロック周期後にｏｒｆｂ＿ｄとして判明すると、各マルチプレクサ４（ｉ）で、アンド回路２（ｉ），３（ｉ）のうち正しかったほうの検索結果予測が供給されたほうの出力を選択する（マルチプレクサ９でも、オア回路７，８のうち正しかった検索結果予測に対応するほうの出力を選択する）。

そして、各マルチプレクサ４（ｉ）で選択した信号を、フリップ・フロップ５を介して辞書の１つ後のアドレスに対応する組のアンド回路２（ｉ）にｐｓ１［ｉ−１］として供給することにより、次回のクロック周期において利用する。

具体的には、新たに入力された文字列が例えば「ＡＢＣＡ」であれば、この文字列検索回路では、１回（動作クロックの１周期）毎に、次の手順で検索を行う。
＜１周期目＞
各比較回路１（ｉ）で、１文字目の「Ａ」についての比較結果ｍ［ｉ］を求める。このｍ［ｉ］は、フリップ・フロップ６（ｉ）からｐｓ０［ｉ］として出力される（次の周期に、辞書の１つ後のアドレスに対応する組のアンド回路３（ｉ）にｐｓ０［ｉ−１］として供給される）。

＜２周期目＞
各比較回路１（ｉ）で、２文字目の「Ｂ」についての比較結果ｍ［ｉ］を求める。このとき、各アンド回路３（ｉ）の出力は、「Ａ」と一致する文字が辞書に存在すると仮定した、「ＡＢ」の検索結果を予測する信号となる。そして、各マルチプレクサ４（ｉ）にはまだｏｒｆｂ＿ｄが供給されていない（‘０’の信号が供給されている）ので、この「ＡＢ」の検索結果予測が、マルチプレクサ４（ｉ）で選択され、フリップ・フロップ５（ｉ）からｐｓ１［ｉ］として出力される（次の周期に、辞書の１つ後のアドレスに対応する組のアンド回路２（ｉ）にｐｓ１［ｉ−１］として供給される）。

また、比較結果ｍ［ｉ］は、フリップ・フロップ６（ｉ）からｐｓ０［ｉ］として出力される（次の周期に、辞書の１つ後のアドレスに対応する組のアンド回路３（ｉ）にｐｓ０［ｉ−１］として供給される）。このｐｓ０［ｉ］は、「Ａ」と一致する文字が辞書に存在しないと仮定して、２文字目の「Ｂ」から再検索を行った結果を示す信号となる。

＜３周期目＞
各比較回路１（ｉ）で、３文字目の「Ｃ」についての比較結果ｍ［ｉ］を求める。
このとき、各アンド回路２（ｉ）の出力は、「ＡＢ」と一致する文字が辞書に存在すると仮定した、「ＡＢＣ」の検索結果を予測する信号となる。
また、各アンド回路３（ｉ）の出力は、「ＡＢ」と一致する文字列が辞書に存在しないと仮定した、「ＢＣ」の検索結果を予測する信号となる。

この３周期目には、「Ａ」と一致する文字列が辞書に存在するか否かを示すｏｒｆｂ＿ｄが、フリップ・フロップ１０から出力される。
このｏｒｆｂ＿ｄが‘１’であれば、「Ａ」と一致する文字が辞書に存在するという仮定が正しかったので、各マルチプレクサ４（ｉ）でアンド回路２（ｉ）の出力（「ＡＢＣ」の検索結果予測）を選択する（マルチプレクサ９でもオア回路７の出力を選択する）。
この「ＡＢＣ」の検索結果予測は、フリップ・フロップ５（ｉ）からｐｓ１［ｉ］として出力される（次の周期に、辞書の１つ後のアドレスに対応する組のアンド回路２（ｉ）にｐｓ１［ｉ−１］として供給される）。

他方、このｏｒｆｂ＿ｄが‘０’であれば、「Ａ」と一致する文字が辞書に存在しないという仮定が正しかったので、各マルチプレクサ４（ｉ）でアンド回路３（ｉ）の出力（「ＢＣ」の検索結果予測）を選択する（マルチプレクサ９でもオア回路８の出力を選択する）。
この「ＢＣ」の検索結果予測は、フリップ・フロップ５（ｉ）からｐｓ１［ｉ］として出力される（次の周期に、辞書の１つ後のアドレスに対応する組のアンド回路２（ｉ）にｐｓ１［ｉ−１］として供給される）。

また、比較結果ｍ［ｉ］は、フリップ・フロップ６（ｉ）からｐｓ０［ｉ］として出力される（次の周期に、辞書の１つ後のアドレスに対応する組のアンド回路２（ｉ）にｐｓ１［ｉ−１］として供給される）。このｐｓ０［ｉ］は、「Ｂ」と一致する文字が辞書に存在しないと仮定して、３文字目の「Ｃ」から再検索を行った結果を示す信号となる。

＜４周期目＞
各比較回路１（ｉ）で、４文字目の「Ａ」についての比較結果ｍ［ｉ］を求める。
このとき、各アンド回路３（ｉ）の出力は、「ＡＢＣ」と一致する文字列が辞書に存在しないと仮定した、「ＣＡ」の検索結果を予測する信号となる。
また、３周期目においてｏｒｆｂ＿ｄが‘１’であった場合には、この４周期目には、各アンド回路２（ｉ）の出力は、「ＡＢＣ」と一致する文字が辞書に存在すると仮定した、「ＡＢＣＡ」の検索結果を予測する信号となる。そして、この４周期目に、「ＡＢ」と一致する文字列が辞書に存在するか否かを示すｏｒｆｂ＿ｄが、フリップ・フロップ１０から出力される。

このｏｒｆｂ＿ｄが‘１’であれば、「ＡＢ」と一致する文字が辞書に存在するという仮定が正しかったので、各マルチプレクサ４（ｉ）でアンド回路２（ｉ）の出力（「ＡＢＣＡ」の検索結果予測）を選択する（マルチプレクサ９でもオア回路７の出力を選択する）。
この「ＡＢＣＡ」の検索結果予測は、フリップ・フロップ５（ｉ）からｐｓ１［ｉ］として出力される（次の周期に、辞書の１つ後のアドレスに対応する組のアンド回路２（ｉ）にｐｓ１［ｉ−１］として供給される）。

他方、このｏｒｆｂ＿ｄが‘０’であれば、「ＡＢ」と一致する文字が辞書に存在しないという仮定が正しかったので、各マルチプレクサ４（ｉ）でアンド回路３（ｉ）の出力（「ＣＡ」の検索結果予測）を選択する（マルチプレクサ９でもオア回路８の出力を選択する）。
この「ＣＡ」の検索結果予測は、フリップ・フロップ５（ｉ）からｐｓ１［ｉ］として出力される（次の周期に、辞書の１つ後のアドレスに対応する組のアンド回路２（ｉ）にｐｓ１［ｉ−１］として供給される）。

また、比較結果ｍ［ｉ］は、フリップ・フロップ６（ｉ）からｐｓ０［ｉ］として出力される（次の周期に、辞書の１つ後のアドレスに対応する組のアンド回路２（ｉ）にｐｓ１［ｉ−１］として供給される）。このｐｓ０［ｉ］は、「Ｃ」と一致する文字が辞書に存在しないと仮定して、４文字目の「Ａ」から再検索を行った結果を示す信号となる。

図４は、前出の図７の辞書を例にとって、この４周期目における検索動作（「ＡＢＣ」の検索結果予測を利用して「ＡＢＣＡ」を検索する場合）を示す図である。

アドレスｉ＝０，４，９，１２の文字が「Ａ」に一致するので、アドレスｉ＝０，４，９，１２に対応する組の比較回路１（ｉ）の比較結果ｍ［ｉ］は‘１’になり、残りの組の比較回路１（ｉ）の比較結果ｍ［ｉ］は‘０’になる。

また、「ＡＢＣ」と一致する文字が辞書に存在するか否かはまだ判明していないが、ｐｓ１［ｉ−１］は「ＡＢＣ」と一致する文字が辞書に存在する（３周期目の検索でアドレスｉ＝２，６，１１，１４に対応する組のフリップ・フロップ５（ｉ）の出力ｐｓ１［ｉ］が‘１’になっている）と仮定した検索結果予測なので、図９に示したｐｓ［ｉ−１］と同じく、アドレスｉ＝２，６，１１，１４よりも１つ後のアドレスｉ＝３，７，１２，１５に対応する組のアンド回路２（ｉ）に供給されるｐｓ１［ｉ−１］は‘１’になり、残りの組のアンド回路２（ｉ）に供給されるｐｓ１［ｉ−１］は‘０’になる。

その結果、図９に示したｐｓ［ｉ］と同じく、アドレスｉ＝１２に対応する組のアンド回路２（ｉ）の出力は‘１’になり、残りの組のアンド回路２（ｉ）の出力は‘０’になる。そして、ｏｒｆｂ＿ｄが‘１’であった場合には、アンド回路２（ｉ）がフリップ・フロップ５（ｉ）の出力ｐｓ１［ｉ］になるので、アドレスｉ＝１２に対応する組のフリップ・フロップ５（ｉ）の出力ｐｓ１［ｉ］は‘１’になり、残りの組のフリップ・フロップ５（ｉ）の出力ｐｓ１［ｉ］は‘０’になる。

ｐｓ０［ｉ−１］は、１つ前のアドレスに対応する組における３文字目の「Ｃ」の再検索結果である。ｐｓ０［ｉ］は、４文字目の「Ａ」の再検索結果である。

なお、３周期目においてｏｒｆｂ＿ｄが‘０’であった場合には、この４周期目には、各アンド回路２（ｉ）の出力は、「ＢＣＡ」の検索結果を予測する信号となる。そして、この４周期目に、「Ｂ」と一致する文字列が辞書に存在するか否かを示すｏｒｆｂ＿ｄが、フリップ・フロップ１０から出力される。

このｏｒｆｂ＿ｄが‘１’であれば、各マルチプレクサ４（ｉ）でアンド回路２（ｉ）の出力（「ＢＣＡ」の検索結果予測）を選択する（マルチプレクサ９でもオア回路７の出力を選択する）。
この「ＢＣＡ」の検索結果予測は、フリップ・フロップ５（ｉ）からｐｓ１［ｉ］として出力される（次の周期に、辞書の１つ後のアドレスに対応する組のアンド回路２（ｉ）にｐｓ１［ｉ−１］として供給される）。

他方、このｏｒｆｂ＿ｄが‘０’であれば、各マルチプレクサ４（ｉ）でアンド回路３（ｉ）の出力（「ＣＡ」の検索結果予測）を選択する（マルチプレクサ９でもオア回路８の出力を選択する）。
この「ＣＡ」の検索結果予測は、フリップ・フロップ５（ｉ）からｐｓ１［ｉ］として出力される（次の周期に、辞書の１つ後のアドレスに対応する組のアンド回路２（ｉ）にｐｓ１［ｉ−１］として供給される）。

この４周期目に続く５周期目には、「ＡＢＣ」と一致する文字列が辞書に存在するか否かを示すｏｒｆｂ＿ｄがフリップ・フロップ１０から出力される。「ＡＢＣＡ」の後にも入力文字列が続いている場合には、５周期以降の各周期にも、ｏｒｆｂ＿ｄの値に応じて同様な処理を繰り返す。

このようにして、この文字列検索回路によれば、「各クロック周期における検索結果を次回のクロック周期に利用する」というアルゴリズムを変えることなく、各クロック周期において作成されるｏｒｆｂ（検索対象に一致する文字が辞書に存在するか否かを示す一致／不一致信号）を遅延させて、パイプライン処理による文字列検索の高速化を実現することができる。

しかも、検索結果を予測する信号は２通り作成するだけであり、ｏｒｆｂも１クロック周期遅延させるだけなので、回路構成を簡素化することができる（ハードウェア記述言語を用いてＡＳＩＣやプログラマブル・ロジック・デバイスとして設計する場合には、ロジックを簡素化することができる）。

〔遅延２の回路〕
次に、図８の文字列検索回路を前提として、出力ｏｒｆｂを２クロック周期遅延させる文字列検索回路（「遅延２」の回路）について説明する。

図５は、この「遅延２」の回路による文字列検索の高速化の原理を示す図である。ｏｒｆｂは‘１’か‘０’か（一致する文字列が存在するか否か）の２つの状態しかとらないので、或るクロック周期における検索結果ｐｓ［ｉ］を予測する信号として、そのクロック周期にはｏｒｆｂ＝‘１’となり１周期前のクロック周期にもｏｒｆｂ＝‘１’となると仮定したｐｓ１１［ｉ］と、そのクロック周期にはｏｒｆｂ＝‘０’となり１周期前のクロック周期にはｏｒｆｂ＝‘１’となると仮定したｐｓ１０［ｉ］と、そのクロック周期にはｏｒｆｂ＝‘１’となり１周期前のクロック周期にはｏｒｆｂ＝‘０’となると仮定したｐｓ０１［ｉ］と、そのクロック周期にはｏｒｆｂ＝‘０’となり１周期前のクロック周期にもｏｒｆｂ＝‘０’となると仮定したｐｓ００［ｉ］との４通りの信号を予め作成しておく。（時刻ｔは、この或るクロック周期内の時刻を表しており、時刻ｔ−１は、そのクロック周期の１周期前のクロック周期内の時刻を表しており、時刻ｔ−２は、ｐｓ１１［ｉ］〜ｐｓ００［ｉ］を作成するクロック周期内の時刻を表している。）

そして、時刻ｔにはどの仮定が正しかったのかが判明するので、検索結果予測ｐｓ１１［ｉ］及びｐｓ１０［ｉ］の組とｐｓ０１［ｉ］及びｐｓ００［ｉ］の組とのうち正しかったほうを選択し、その選択した信号を次回のクロック周期において利用する。（図６の例では、１つ目のクロック周期についてｏｒｆｂ＝‘０’が正しかったことが判明するので、ｐｓ０１［ｉ］及びｐｓ００［ｉ］の組を選択する。）

これにより、各クロック周期におけるｏｒｆｂを２クロック周期遅延させて、パイプライン処理による文字列検索の高速化を実現することができる。

ＡＳＩＣ（特定用途向けＬＳＩ）やプログラマブル・ロジック・デバイス（ＦＰＧＡ等）として設計する場合には、この「遅延２」の文字列検索回路は、ハードウェア記述言語の一種であるVerilog ＨＤＬを用いて図６のように表記することができる。

以上の各例では、ｏｒｆｂを１クロック周期または２クロック周期遅延させる文字列検索回路について説明した。しかし、より一般的には、或るクロック周期における検索結果を予測する信号として、そのクロック周期よりもｎ−１周期前（ｎは１以上の整数）のクロック周期からそのクロック周期までの各周期におけるｏｒｆｂの値の仮定を組み合わせた２^ｎ通りの信号を予め作成するようにすれば、各クロック周期におけるｏｒｆｂをｎクロック周期遅延させて、パイプライン処理による文字列検索の高速化を実現することができる。

また、以上の例では、ＬＺ７７法を採用したデータ圧縮回路内に設けられる文字列検索回路に本発明を適用した例について説明した。しかし、本発明は、これに限らず、入力された文字列に一致する文字列を辞書から検索する処理を、動作クロックの１周期毎にこの文字列の１文字ずつ行い、各クロック周期における検索結果を次回のクロック周期に利用するようにしたあらゆる文字列検索回路において、文字列検索の高速化のために適用することができる。

「遅延１」の文字列検索回路による文字列検索の高速化の原理を示す図である。本発明を適用した文字列検索回路の構成を示すブロック図である。図２の文字列検索回路をハードウェア記述言語を用いて表記した図である。図２の文字列検索回路の動作を例示する図である。「遅延２」の文字列検索回路による文字列検索の高速化の原理を示す図である。「遅延２」の文字列検索回路をハードウェア記述言語を用いて表記した図である。ＬＺ７７法における辞書からの文字列の検索の様子を例示する図である。ＬＺ７７法を採用したデータ圧縮回路内に従来設けられていた文字列検索回路の構成を示すブロック図である。図８の文字列検索回路をハードウェア記述言語を用いて表記した図である。図８の文字列検索回路の動作を例示する図である。

符号の説明

１（ｉ）比較回路
２（ｉ），３（ｉ）アンド回路
４（ｉ），９マルチプレクサ
５（ｉ），６（ｉ），１０Ｄ型フリップ・フロップ
７，８オア回路

Claims

動作クロックの１周期毎に、入力された文字列の１文字ずつについて、該文字に一致する文字を辞書から検索し、且つ、検索対象と一致する文字が前記辞書に存在するか否かを示す一致／不一致信号を作成し、検索対象と一致する文字が前記辞書に存在する場合には、検索結果を次回のクロック周期で利用して、検索対象の文字数を１文字ずつ増やすようにした文字列検索回路において、
前記一致／不一致信号を、前記動作クロックのｎ周期分（ｎは１以上の整数）遅延させる遅延手段と、
或るクロック周期における検索結果を予測する信号として、該クロック周期よりも前記ｎ−１周期前から該クロック周期までのｎ個の周期の各々（ただしｎ＝１の場合は該クロック周期の１周期のみ）について、検索対象と一致する文字が前記辞書に存在する状態と前記辞書に存在しない状態との２つの状態をそれぞれ仮定し、前記２つの状態を前記ｎ個の周期分組み合わせた２^ｎ通りの信号を予め作成する作成手段と、
前記遅延手段によって遅延された前記一致／不一致信号に従い、前記作成手段によって作成された前記２^ｎ通りの信号のうち仮定が正しかった信号を選択する選択手段と
を備え、
前記選択手段によって選択された信号を、次回のクロック周期において利用する
文字列検索回路。
請求項１に記載の文字列検索回路において、
前記遅延手段は、前記一致／不一致信号を、前記動作クロックの１周期分遅延させ、
前記作成手段は、或るクロック周期における検索結果を予測する信号として、該クロック周期には検索対象と一致する文字が辞書に存在すると仮定した信号と、該クロック周期には検索対象と一致する文字が辞書に存在しないと仮定した信号との２通りの信号を作成する
文字列検索回路。
動作クロックの１周期毎に、入力された文字列の１文字ずつについて、該文字に一致する文字を辞書から検索し、且つ、検索対象と一致する文字が前記辞書に存在するか否かを示す一致／不一致信号を作成し、検索対象と一致する文字が前記辞書に存在する場合には、検索結果を次回のクロック周期で利用して、検索対象の文字数を１文字ずつ増やすようにした文字列検索方法において、
前記一致／不一致信号を、前記動作クロックのｎ周期分（ｎは１以上の整数）遅延させる第１のステップと、
或るクロック周期における検索結果を予測する信号として、該クロック周期よりも前記ｎ−１周期前から該クロック周期までのｎ個の周期の各々（ただしｎ＝１の場合は該クロック周期の１周期のみ）について、検索対象と一致する文字が前記辞書に存在する状態と前記辞書に存在しない状態との２つの状態をそれぞれ仮定し、前記２つの状態を前記ｎ個の周期分組み合わせた２^ｎ通りの信号を予め作成する第２のステップと、
前記第１のステップによって遅延された前記一致／不一致信号に従い、前記第２のステップによって作成された前記２^ｎ通りの信号のうち仮定が正しかった信号を選択する第３のステップと
を有し、
前記第３のステップによって選択された信号を、次回のクロック周期において利用する
文字列検索方法。