"第1のデータ要素列に基づいて第2のデータ要素列を検索する際の当該第1のデータ要素列における検索開始点を決定する装置であって、前記第2のデータ要素列を構成する複数のデータ要素の各データ要素を、当該第2のデータ要素列における当該各データ要素の位置に応じたアドレスに記憶し、検索データ要素が与えられた場合に、当該検索データ要素に一致する一致データ要素を当該複数のデータ要素の1つとして記憶していれば、当該一致データ要素が記憶されているアドレスを出力する連想メモリと、各生成回路が、前記検索データ要素が前記連想メモリに与えられた場合に、それまでに与えられた検索データ要素の列のうちの当該各生成回路に対して決められた個別開始点で始まる列に一致する一致データ要素の列が当該連想メモリに記憶されていれば、当該連想メモリから出力される前記アドレスに基づいて、当該一致データ要素の列が記憶されていることを示す列存在情報を生成する生成回路である複数の生成回路と、前記第1のデータ要素列を構成するデータ要素を前記検索データ要素として順次前記連想メモリに与えることによって前記複数の生成回路の各々により順次生成された複数の列存在情報に基づいて、前記検索開始点を決定する決定部とを含む、装置。前記決定部は、前記複数の生成回路のうちの特定の生成回路による前記列存在情報の連続生成回数が、当該連続生成回数が多いと認められるための所定の条件を満たす場合に、当該特定の生成回路に対して決められた前記個別開始点を、前記検索開始点として決定する、請求項1の装置。前記所定の条件は、前記特定の生成回路による前記列存在情報の連続生成回数が、前記複数の生成回路のうちの他の生成回路による前記列存在情報の連続生成回数の何れよりも多いという条件を含む、請求項2の装置。データ要素列の第1の部分データ要素列を、当該データ要素列の第2の部分データ要素列の位置及び長さの情報で置換することにより、当該データ要素列を圧縮する装置であって、前記データ要素列の少なくとも一部を構成する複数のデータ要素の各データ要素を、当該データ要素列における当該各データ要素の位置に応じたアドレスに記憶し、検索データ要素が与えられた場合に、当該検索データ要素に一致する一致データ要素を当該複数のデータ要素の1つとして記憶していれば、当該一致データ要素が記憶されているアドレスを出力する連想メモリと、各生成回路が、前記検索データ要素が前記連想メモリに与えられた場合に、それまでに与えられた検索データ要素の列のうちの当該各生成回路に対して決められた個別開始点で始まる列に一致する一致データ要素の列が当該連想メモリに記憶されていれば、当該連想メモリから出力される前記アドレスに基づいて、当該一致データ要素の列が記憶されていることを示す列存在情報と、当該一致データ要素の列が記憶されているアドレスを示す列アドレス情報とを生成する生成回路である複数の生成回路と、前記第1の部分データ要素列を構成するデータ要素を前記検索データ要素として順次前記連想メモリに与えることによって前記複数の生成回路の各々により順次生成された複数の列存在情報及び複数の列アドレス情報に基づいて、前記第2の部分データ要素列の位置及び長さを決定する決定部とを含む、装置。前記決定部は、前記複数の生成回路のうちの特定の生成回路による前記列存在情報の連続生成回数が、当該連続生成回数が多いと認められるための所定の条件を満たす場合に、当該特定の生成回路により前記列存在情報が生成されなくなる直前に当該特定の生成回路により生成された前記列アドレス情報に応じて、前記第2の部分データ要素列の位置を決定し、当該連続生成回数に応じて、前記第2の部分データ要素列の長さを決定する、請求項4の装置。前記所定の条件は、前記特定の生成回路による前記列存在情報の連続生成回数が、前記複数の生成回路のうちの他の生成回路による前記列存在情報の連続生成回数の何れよりも多いという条件を含む、請求項5の装置。データ要素列の第1の部分データ要素列を、当該データ要素列の第2の部分データ要素列の位置及び長さの情報で置換することにより、当該データ要素列を圧縮する装置であって、前記データ要素列の少なくとも一部を構成する複数のデータ要素の各データ要素を、当該データ要素列における当該各データ要素の位置に応じたアドレスに記憶し、検索データ要素が与えられた場合に、当該検索データ要素に一致する一致データ要素を当該複数のデータ要素の1つとして記憶していれば、当該一致データ要素が記憶されているアドレスを出力する連想メモリと、前記検索データ要素が前記連想メモリに与えられた場合に、それまでに与えられた検索データ要素の列のうちの基準データ要素で始まる列に一致する一致データ要素の列が当該連想メモリに記憶されていれば、当該連想メモリから出力される前記アドレスに基づいて、当該一致データ要素の列が記憶されていることを示す第1の列存在情報と、当該一致データ要素の列が記憶されているアドレスを示す第1の列アドレス情報とを生成する基本生成回路と、J番目の拡張生成回路が、前記検索データ要素が前記連想メモリに与えられた場合に、それまでに与えられた検索データ要素の列のうちの前記基準データ要素からJ番目のデータ要素で始まる列に一致する一致データ要素の列が当該連想メモリに記憶されていれば、当該連想メモリから出力される前記アドレスに基づいて、当該一致データ要素の列が記憶されていることを示す第1の列存在情報と、当該一致データ要素の列が記憶されているアドレスを示す第1の列アドレス情報とを生成する拡張生成回路であるK個の拡張生成回路Kは自然数、JはK以下の自然数と、前記検索データ要素が前記連想メモリに与えられた場合に、前記基本生成回路及び前記K個の拡張生成回路の何れかにより前記第1の列存在情報が生成されていれば、それまでに与えられた検索データ要素の列のうちの前記基準データ要素以降の何れかのデータ要素で始まる列に一致する一致データ要素の列が当該連想メモリに記憶されていることを示す第2の列存在情報を出力する第1の出力回路と、前記検索データ要素が前記連想メモリに与えられた場合に、前記基本生成回路及び前記K個の拡張生成回路のうち、前記第1の列存在情報を生成している少なくとも1つの生成回路が生成する前記第1の列アドレス情報を、第2の列アドレス情報として出力する第2の出力回路と、前記第1の部分データ要素列を構成するデータ要素を前記検索データ要素として順次前記連想メモリに与え、前記第1の出力回路から前記第2の列存在情報が出力されなくなる直前に前記第2の出力回路から出力された前記第2の列アドレス情報に応じて、前記第2の部分データ要素列の位置を決定し、前記第1の出力回路からの前記第2の列存在情報の連続出力回数に応じて、前記第2の部分データ要素列の長さを決定する決定部とを含む、装置。第1のデータ要素列に基づいて第2のデータ要素列を検索する際の当該第1のデータ要素列における検索開始点を決定する方法であって、前記第2のデータ要素列を構成する複数のデータ要素の各データ要素を、当該第2のデータ要素列における当該各データ要素の位置に応じたアドレスに記憶し、検索データ要素が与えられた場合に、当該検索データ要素に一致する一致データ要素を当該複数のデータ要素の1つとして記憶していれば、当該一致データ要素が記憶されているアドレスを出力する連想メモリを含み、複数の生成回路の各生成回路が、前記検索データ要素が前記連想メモリに与えられた場合に、それまでに与えられた検索データ要素の列のうちの当該各生成回路に対して決められた個別開始点で始まる列に一致する一致データ要素の列が当該連想メモリに記憶されていれば、当該連想メモリから出力される前記アドレスに基づいて、当該一致データ要素の列が記憶されていることを示す列存在情報を生成するステップと、前記第1のデータ要素列を構成するデータ要素を前記検索データ要素として順次前記連想メモリに与えることによって前記複数の生成回路の各々により順次生成された複数の列存在情報に基づいて、前記検索開始点を決定するステップとを含む、方法。ところで、特許文献1~3に記載された文字列検索装置では、1文字以上の文字列の一致を、最初に一致した文字からトレースすることにより判断する。多くの圧縮対象データに対してこの方法は有効である。しかしながら、同一部分を有する長さの異なる複数の文字列がオーバーラップして存在し、この複数の文字列に同一部分が末尾にある文字列と先頭にある文字列とが含まれ、後者の方が長いケースもある。このようなケースに対応するには、文字列の複数のトレースを並行して行う必要がある。本発明の目的は、同一部分を有する長さの異なる複数の文字列が存在する検索対象から長い方の文字列を効果的に検出することにある。かかる目的のもと、本発明は、第1のデータ要素列に基づいて第2のデータ要素列を検索する際の第1のデータ要素列における検索開始点を決定する装置であって、第2のデータ要素列を構成する複数のデータ要素の各データ要素を、第2のデータ要素列における各データ要素の位置に応じたアドレスに記憶し、検索データ要素が与えられた場合に、検索データ要素に一致する一致データ要素を複数のデータ要素の1つとして記憶していれば、一致データ要素が記憶されているアドレスを出力する連想メモリと、各生成回路が、検索データ要素が連想メモリに与えられた場合に、それまでに与えられた検索データ要素の列のうちの各生成回路に対して決められた個別開始点で始まる列に一致する一致データ要素の列が連想メモリに記憶されていれば、連想メモリから出力されるアドレスに基づいて、一致データ要素の列が記憶されていることを示す列存在情報を生成する生成回路である複数の生成回路と、第1のデータ要素列を構成するデータ要素を検索データ要素として順次連想メモリに与えることによって複数の生成回路の各々により順次生成された複数の列存在情報に基づいて、検索開始点を決定する決定部とを含む、装置を提供する。ここで、決定部は、複数の生成回路のうちの特定の生成回路による列存在情報の連続生成回数が、連続生成回数が多いと認められるための所定の条件を満たす場合に、特定の生成回路に対して決められた個別開始点を、検索開始点として決定する、ものであってよい。そして、所定の条件は、特定の生成回路による列存在情報の連続生成回数が、複数の生成回路のうちの他の生成回路による列存在情報の連続生成回数の何れよりも多いという条件を含む、ものであってよい。また、本発明は、データ要素列の第1の部分データ要素列を、データ要素列の第2の部分データ要素列の位置及び長さの情報で置換することにより、データ要素列を圧縮する装置であって、データ要素列の少なくとも一部を構成する複数のデータ要素の各データ要素を、データ要素列における各データ要素の位置に応じたアドレスに記憶し、検索データ要素が与えられた場合に、検索データ要素に一致する一致データ要素を複数のデータ要素の1つとして記憶していれば、一致データ要素が記憶されているアドレスを出力する連想メモリと、各生成回路が、検索データ要素が連想メモリに与えられた場合に、それまでに与えられた検索データ要素の列のうちの各生成回路に対して決められた個別開始点で始まる列に一致する一致データ要素の列が連想メモリに記憶されていれば、連想メモリから出力されるアドレスに基づいて、一致データ要素の列が記憶されていることを示す列存在情報と、一致データ要素の列が記憶されているアドレスを示す列アドレス情報とを生成する生成回路である複数の生成回路と、第1の部分データ要素列を構成するデータ要素を検索データ要素として順次連想メモリに与えることによって複数の生成回路の各々により順次生成された複数の列存在情報及び複数の列アドレス情報に基づいて、第2の部分データ要素列の位置及び長さを決定する決定部とを含む、装置も提供する。更に、本発明は、データ要素列の第1の部分データ要素列を、データ要素列の第2の部分データ要素列の位置及び長さの情報で置換することにより、データ要素列を圧縮する装置であって、データ要素列の少なくとも一部を構成する複数のデータ要素の各データ要素を、データ要素列における各データ要素の位置に応じたアドレスに記憶し、検索データ要素が与えられた場合に、検索データ要素に一致する一致データ要素を複数のデータ要素の1つとして記憶していれば、一致データ要素が記憶されているアドレスを出力する連想メモリと、検索データ要素が連想メモリに与えられた場合に、それまでに与えられた検索データ要素の列のうちの基準データ要素で始まる列に一致する一致データ要素の列が連想メモリに記憶されていれば、連想メモリから出力されるアドレスに基づいて、一致データ要素の列が記憶されていることを示す第1の列存在情報と、一致データ要素の列が記憶されているアドレスを示す第1の列アドレス情報とを生成する基本生成回路と、J番目の拡張生成回路が、検索データ要素が連想メモリに与えられた場合に、それまでに与えられた検索データ要素の列のうちの基準データ要素からJ番目のデータ要素で始まる列に一致する一致データ要素の列が連想メモリに記憶されていれば、連想メモリから出力されるアドレスに基づいて、一致データ要素の列が記憶されていることを示す第1の列存在情報と、一致データ要素の列が記憶されているアドレスを示す第1の列アドレス情報とを生成する拡張生成回路であるK個の拡張生成回路Kは自然数、JはK以下の自然数と、検索データ要素が連想メモリに与えられた場合に、基本生成回路及びK個の拡張生成回路の何れかにより第1の列存在情報が生成されていれば、それまでに与えられた検索データ要素の列のうちの基準データ要素以降の何れかのデータ要素で始まる列に一致する一致データ要素の列が連想メモリに記憶されていることを示す第2の列存在情報を出力する第1の出力回路と、検索データ要素が連想メモリに与えられた場合に、基本生成回路及びK個の拡張生成回路のうち、第1の列存在情報を生成している少なくとも1つの生成回路が生成する第1の列アドレス情報を、第2の列アドレス情報として出力する第2の出力回路と、第1の部分データ要素列を構成するデータ要素を検索データ要素として順次連想メモリに与え、第1の出力回路から第2の列存在情報が出力されなくなる直前に第2の出力回路から出力された第2の列アドレス情報に応じて、第2の部分データ要素列の位置を決定し、第1の出力回路からの第2の列存在情報の連続出力回数に応じて、第2の部分データ要素列の長さを決定する決定部とを含む、装置も提供する。更にまた、本発明は、第1のデータ要素列に基づいて第2のデータ要素列を検索する際の第1のデータ要素列における検索開始点を決定する方法であって、第2のデータ要素列を構成する複数のデータ要素の各データ要素を、第2のデータ要素列における各データ要素の位置に応じたアドレスに記憶し、検索データ要素が与えられた場合に、検索データ要素に一致する一致データ要素を複数のデータ要素の1つとして記憶していれば、一致データ要素が記憶されているアドレスを出力する連想メモリを含み、複数の生成回路の各生成回路が、検索データ要素が連想メモリに与えられた場合に、それまでに与えられた検索データ要素の列のうちの各生成回路に対して決められた個別開始点で始まる列に一致する一致データ要素の列が連想メモリに記憶されていれば、連想メモリから出力されるアドレスに基づいて、一致データ要素の列が記憶されていることを示す列存在情報を生成するステップと、第1のデータ要素列を構成するデータ要素を検索データ要素として順次連想メモリに与えることによって複数の生成回路の各々により順次生成された複数の列存在情報に基づいて、検索開始点を決定するステップとを含む、方法も提供する。本発明によれば、同一部分を有する長さの異なる複数の文字列が存在する検索対象から長い方の文字列を効果的に検出することができる。以下、添付図面を参照して、本発明の実施の形態について詳細に説明する。図1は、本実施の形態が適用されるマイクロコンピュータ10の構成一部を示す。マイクロコンピュータ10は、CPU12、ROM14、RAM16を備えており、これらはアドレスバス、データバス、コントロールバス等からなるバス18を介して互いに接続されている。また、マイクロコンピュータ10は、本実施の形態における複数の繰り返しデータ検索装置20a、20b、...を備えており、これらは、繰り返しデータ検索装置の作動を制御するデータ圧縮コントローラ22を介してバス18に接続されている。尚、繰り返しデータ検索装置20a、20b、...は各々同一の構成であり、本実施の形態ではP1個の繰り返しデータ検索装置が設けられている。以下ではP1個の繰り返しデータ検索装置を繰り返しデータ検索装置20と総称してその構成を説明すると共に、個々の繰り返しデータ検索装置についてはブロック0~ブロックPと称して区別する。図2は、本実施の形態における繰り返しデータ検索装置20のベースとなる繰り返しデータ検索回路21を示した図である。繰り返しデータ検索回路21は、図に○で示す多数の連想メモリセル以下、連想メモリをCAMという28がマトリクス状に配置されて構成されたCAMセルアレイ26を備えている。CAMセルアレイ26にはN1本のワード線WL0~WLN、N1本のマッチ線MATCH0~MATCHN、M1組のビット線対BL0BL0~BLMBLMが各々マトリクス状に配置されており、各CAMセル28は、ワード線WL0~WLNの何れか、マッチ線MATCH0~MATCHNの何れか、及び、ビット線対BL0BL0~BLMBLMの何れかに各々接続されている。多数のCAMセル28は、各々同一の構成を有している。図3に示すように、CAMセル28は、互いの入力端と出力端とが接続された2個のNOT回路30、32を備えている。このNOT回路30、32のループが、1ビットのデータを記憶する記憶回路SRAM型を構成する。NOT回路30の出力端はN-MOSFET34のソースに、NOT回路32の出力端は同じくN-MOSFET36のソースに各々接続されており、N-MOSFET34、36のゲートは各々ワード線WLに接続されている。また、N-MOSFET34、36のドレインは各々ビット線BLBLに接続されている。ここで、CAMセル28に1ビットのデータを書き込む場合には、ワード線WLはハイレベルとされ、ビット線BLは書き込むデータDに対応したレベルDが1の場合はハイレベル、0の場合はローレベルとされ、ビット線BLはビット線BLのレベルに対して反転したレベルビット線BLがハイレベルの場合はローレベル、ビット線BLがローレベルの場合はハイレベルとされる。これにより、N-MOSFET34、36がオンし、ビット線BL又はBLを介して供給されたデータがNOT回路30、32のループに保持される。また、NOT回路30の出力端はN-MOSFET38のゲートに、NOT回路32の出力端はN-MOSFET40のゲートに各々接続されている。尚、NOT回路32からはデータDを反転したデータQ’が出力され、NOT回路30からはデータQ’を反転したデータQ=Dが出力される。N-MOSFET38、40のドレインは各々ビット線BLBLに接続されており、ソースはN-MOSFET42のゲートに接続されている。N-MOSFET42のドレインはマッチ線MATCHに接続され、ソースは接地されている。尚、本実施の形態では、同一のワード線及びマッチ線に、一例としてM1個のCAMセル28を接続しており、同一のワード線及びマッチ線に接続された複数のCAMセル28以下、これらをCAMセル列というにM1ビットのデータを記憶できるようにしている。また、CAMセルアレイ26では、CAMセル列毎にアドレスが付与されている。再び図2を参照すると、繰り返しデータ検索回路21はタイミングコントローラ50を備えている。タイミングコントローラ50はデータ圧縮コントローラ22に接続されている。データ圧縮コントローラ22からタイミングコントローラ50に検索指示SEARCHが入力されると、繰り返しデータ検索回路21は、入力された検索データをCAMセルアレイ26の各CAMセル列に記憶されたデータと比較し、次に検索データをCAMセルアレイ26の何れかのCAMセル列に書き込むことを繰り返す検索モードを実行する。タイミングコントローラ50にはデータ圧縮コントローラ22からシステムクロックCLOCKが入力され、システムクロックCLOCKと同期したクロックSRを生成し出力する。クロックSRはタイミングコントローラ50に接続された書込みバッファ56に出力される。書込みバッファ56はデータ圧縮コントローラ22に接続されており、コントーラ22から検索データが順次入力される。書込みバッファ56にはビット線対BL0BL0~BLMBLMが各々接続されており、入力された検索データを保持すると共に、タイミングコントローラ50から入力されたクロックSRに同期したタイミングで、保持している検索データの値に応じてビット線対BL0BL0~BLMBLMのレベルを変化させるビット線対を駆動する。書込みバッファ56が所定の検索データに応じて各ビット線対を駆動している間に、各CAMセル列に記憶されたデータとその所定の検索データとの比較、及び、所定のCAMセル列への所定の検索データの書込みが行われる。タイミングコントローラ50にはアドレスデコーダ52も接続されており、クロックSRはアドレスデコーダ52にも出力される。アドレスデコーダ52はデータ圧縮コントローラ22に接続されており、データ圧縮コントローラ22から検索データの書込みを行うCAMセル列のアドレス書込みアドレスWADRが指定される。アドレスデコーダ52にはワード線WL0~WLNが接続されており、クロックSRと同期したタイミングで、より詳しくは書込みバッファ56が所定の検索データに応じて各ビット線対を駆動している期間内で、かつ、各CAMセル列に記憶されたデータと所定の検索データとの比較が行われた後に、指定された書込みアドレスWADRに対応するCAMセル列のワード線をアサートしイネーブルとし、所定の検索データを指定されたアドレスに対応するCAMセル列に書き込む。また、タイミングコントローラ50には、各々マッチ線MATCH0~MATCHNに接続されたN1個のマッチ線コントローラ580~58Nも各々接続されており、クロックSRはマッチ線コントローラ580~58Nの各々にも出力される。マッチ線コントローラ580~58Nは、入力されたクロックSRに基づき各CAMセル列に記憶されたデータと検索データとの比較に先立ってマッチ線MATCH0~MATCHNをハイレベルにチャージプリチャージする。このマッチ線コントローラ580~58Nによるマッチ線のプリチャージは、書込みバッファ56が所定の検索データに応じた各ビット線対の駆動を終了してから、次の検索データに応じた各ビット線対の駆動を開始するまでの期間内に行われる。また、マッチ線MATCH0~MATCHNは、比較結果制御回路60に各々接続されている。図4に示すように、比較結果制御回路60は、ラッチ620~62N、信号生成回路640~64N、ラッチ660~66Nを備えている。尚、図4では、マッチ線コントローラ580~58Nの図示を省略している。また、図4では信号生成回路640~64Nのうち、マッチ線MATCH1に接続された信号生成回路641についてのみ具体的な構成を示しているが、他の信号生成回路も各々同一の構成であり、以下では比較結果制御回路60のうちマッチ線MATCH1に対応する回路部分についてのみ説明する。マッチ線MATCH1はラッチ621の入力端に接続されており、ラッチ621の出力端は信号生成回路641のAND回路681、701に各々2個設けられた入力端の一方に各々接続されている。AND回路681の2個の入力端の他方にはOR回路721の出力端が接続されており、OR回路721の2個の入力端の一方、及び、AND回路701の2個の入力端の他方は、前段のラッチ660の出力端に各々接続されている。AND回路681の出力端はラッチ661の入力端に接続されており、ラッチ661の出力端は前記と同様に、次段の信号生成回路642の図示しないOR回路722及びAND回路702の入力端に各々接続されている。また、ラッチ661の出力端は第1プライオリティエンコーダ74の入力端にも接続されている。更に、AND回路701の出力端はOR回路78の1個の入力端に接続されており、OR回路78の他の入力端には図示しないAND回路700、702~70Nの出力端が接続されている。OR回路78の出力端はOR回路80の1個の入力端に接続されており、OR回路80の他の入力端には、他の繰り返しデータ検索回路21のOR回路78の出力端が接続されている。OR回路80の出力端は、信号生成回路640~64NのOR回路720~72Nの入力端に図示しないインバータを介して接続されておりOR回路721のみ図示、OR回路720~72Nには、OR回路80から出力されたフィードバック信号ORFBが反転されて入力される。また、OR回路80から出力されたフィードバック信号ORFBはデータ圧縮コントローラ22にも出力される図2も参照。尚、図4にはブロック0の繰り返しデータ検索回路21の比較結果制御回路60を示しており、信号生成回路640のOR回路720の2個の入力端の一方は、ブロックPの比較結果制御回路60のラッチ66Nの出力端に接続されている。また、ブロック0の比較結果制御回路60のラッチ66Nの出力端は、ブロック1の比較結果制御回路60のOR回路720の2個の入力端の一方に接続されている図2も参照。第1プライオリティエンコーダ74の出力端は第2プライオリティエンコーダ76の入力端に接続されている。第1プライオリティエンコーダ74は、比較結果制御回路60の660~66Nから各々入力された信号のうち検索動作を行った後に入力信号がハイレベルとなっている信号に対応するアドレスをエンコードして一致アドレスMADR0として第2プライオリティエンコーダ76に出力すると共に、ラッチ660~66Nから各々入力された信号の論理和を一致信号MSIG0として第2プライオリティエンコーダ76に出力する。尚、ラッチ660~66Nから入力された信号のうちの複数の信号がハイレベルであった場合には、一致アドレスMADR0として、予め定められた基準に従って優先順位の高い連想メモリセル列のアドレス、例えば、最も低いアドレス、又は、その時点の書込みアドレスWADRに最も近いアドレスを出力する。尚、後者のアドレスを出力するのは、圧縮に用いる距離情報が小さくてすむので、結果として圧縮率が高くなるという理由による。また、第2プライオリティエンコーダ76の入力端には、他の繰り返しデータ検索回路21の第1プライオリティエンコーダ74から出力された一致アドレスMADR及び一致信号MSIGも入力される。第2プライオリティエンコーダ76の出力端はデータ圧縮コントローラ22に接続されている。第2プライオリティエンコーダ76は第1プライオリティエンコーダ74とほぼ同様の構成であり、複数の第1プライオリティエンコーダ74から各々入力されたアドレスMADR0~MADRPのうち、MSIG0~MSIGPがハイレベルであるものの中から予め定められた基準に従い優先順位の高いアドレス、例えば、最も低いアドレスにそのブロックのアドレス複数の繰り返しデータ検索装置に各々付与されたアドレスを付加したアドレス、又は、その時点の書込みアドレスWADRに最も近いアドレスを一致アドレスMADRとしてデータ圧縮コントローラ22に出力すると共に、複数の第1プライオリティエンコーダ74から各々入力された一致信号MSIG0~MSIGPの論理和を表す信号を一致信号MSIGとしてデータ圧縮コントローラ22に出力する。次に、本実施の形態の作用として、まず、繰り返しデータ検索回路21における比較動作について説明する。被圧縮データ元データの圧縮を行う場合、データ圧縮コントローラ22は後述するように元データから所定ビット長の単位データを検索データとして順次取り出し、検索指示SEARCH、書込みアドレスWADRと共に繰り返しデータ検索回路21に順次出力する。検索指示SEARCHが入力されると、繰り返しデータ検索回路21ではタイミングコントローラ50から書込みバッファ56、アドレスデコーダ52及びマッチ線コントローラ580~58NにクロックSRが出力され、マッチ線コントローラ58ではCAMセルアレイ26における比較動作に先立ってマッチ線MATCH0~MATCHNのプリチャージを行い、書込みバッファ56では入力された検索データを保持すると共に、検索データに応じてビット線対BL0BL0~BLMBLMを駆動する。CAMセルアレイ26の各CAMセル28では、NOT回路30から出力されるデータQが1ハイレベルであればN-MOSFET38がオンしており、NOT回路32から出力されるデータQ’が1であればN-MOSFET40がオンしている。従って、NOT回路30、32のループに保持されているデータQQ’とビット線対BLBLを介して供給されるデータDDとが一致している場合にはN-MOSFET42はオンしないが、不一致の場合にはN-MOSFET38、40のうちオンしている方のN-MOSFETのドレインからソースに電流が流れ、N-MOSFET42がオンする。これにより、プリチャージされたマッチ線MATCHのレベルはローレベルに低下されるディスチャージ。上記のデータの比較はCAMセル28の各々で同時に行なわれる。ところで、1本のマッチ線MATCHには複数のCAMセル28CAMセル列が接続されているので、クロックSRの1周期のほぼ前半で、CAMセル列に記憶されている文字データと入力された文字データとを比較する比較動作が完了し、各マッチ線は、接続されている全てのCAMセル28でN-MOSFET42がオンしなかった場合、即ちCAMセル列に記憶されている文字データと書込みバッファ56に入力された文字データとが一致していた場合にのみハイレベルの状態で維持され、不一致であった場合にはローレベルとされることになる。クロックSRの1周期の後半には、入力された書込みアドレスWADRに対応するCAMセル列のワード線がアドレスデコーダ52によりアサートされイネーブルとされ、そのCAMセル列に検索データが書き込まれる。そして、CAMセル列への検索データの書込みが終了しワード線がローレベルにされると共に書込みバッファ56による各ビット線対の駆動が停止されると、マッチ線コントローラ58により各マッチ線のプリチャージが再び行われる。以上の動作比較動作はクロックSRの1周期の間に行われ、データ圧縮コントローラ22からの検索データ、検索指示SEARCH、書込みアドレスWADRの入力に同期して繰り返される。尚、上記説明において、文字データはデータ要素の一例である。また、ORFBが1である場合の信号は、一致データ要素の列が記憶されていることを示す列存在情報、第1の列存在情報の一例であり、MADRは、一致データ要素の列が記憶されているアドレスを示す列アドレス情報、第1の列アドレス情報の一例であり、信号生成回路64、ラッチ66、第1プライオリティエンコーダ74、第2プライオリティエンコーダ76、OR回路78からなる部分は生成回路、特に基本生成回路の一例である。更に、データ圧縮コントローラ22は、検索開始点、データ要素列の位置及び長さを決定する決定部の一例である。次に、比較結果制御回路60の動作について、図5を参照して説明する。尚、図5では元データがテキストデータであり、アドレス0~5のCAMセル列に既にABABBCの文字データ列が順に記憶されており、かつ、検索データとしてABBBC...の順に文字データが入力された場合を例として示しており、ラッチ620~625をML0~ML5、ラッチ660~665をPS0~PS5と称している。また、以下では他の繰り返しデータ検索装置においては比較動作の結果が連続して不一致となっているものとする。図5aに示すように、検索データとして、まずAの文字データが入力されると、アドレス0及び2のCAMセル列図5では太枠で示すで比較結果が一致となり、マッチ線MATCH0~MATCH5のうちマッチ線MATCH0及びMATCH2以外はローレベルにディスチャージされ、マッチ線MATCH0及びMATCH2のみがハイレベルのまま維持される。各マッチ線MATCH0~MATCH5のレベルは比較結果制御回路60のラッチML0~ML5に各々保持された後に、次の周期で信号生成回路640~645に各々出力される。図5aに示すように、このときはラッチPS0~PS5に保持されているレベルがローレベル図5では0:図示していないラッチPS6~PSN、及び、他のブロックのラッチPS0~PSNについても同様とするであるので、AND回路700~705から出力される信号は何れもローレベルとなり、OR回路78から出力されるフィードバック信号ORFB0及びOR回路80から出力されるフィードバック信号ORFBもローレベルとなる。このように本実施の形態では、1文字のみ一致したのみ、即ち1回の比較動作で比較結果が一致となったCAMセル列があったのみではフィードバック信号ORFBはハイレベルとはならない。またフィードバック信号ORFBがローレベルであるので、OR回路720~725の出力は何れもハイレベルとなり、ラッチML0~ML5から出力された信号のレベルはラッチPS0~PS5にそのまま保持される図5b参照。図5bに示すように、次の検索データとしてBの文字データが入力されると、アドレス1、3、4のCAMセル列で比較結果が一致となり、各マッチ線のレベルマッチ線MATCH135のみがハイレベルはラッチML0~ML5に各々保持される。そして次の周期では、ラッチML1、ML3、ML5の出力が各々ハイレベルになると共に、ラッチPS0、PS2即ちラッチML1、ML3の前段のラッチPSの出力が各々ハイレベルとなるので、図5bに示すようにAND回路701、703から出力される信号がハイレベルとなり、OR回路78から出力されるフィードバック信号ORFB0、OR回路80から出力されるフィードバック信号ORFBが各々ハイレベルになる。このように、フィードバック信号ORFBは2文字以上連続して一致した場合、即ち続けて入力された複数の検索データからなるデータ列がCAMセルアレイ26に記憶されていた場合にのみハイレベルとなる。尚、第1プライオリティエンコーダ74が一致アドレスMADR0として最も低いアドレスを出力するものであるとすると、一致アドレスMADR0はPS0に対応するアドレス0となる。また、第2プライオリティエンコーダ76から出力される一致アドレスMADRについては、他の繰り返しデータ検索装置から入力される一致アドレスの値にも依存するが、他の繰り返しデータ検索装置でデータが一致していない場合には、一致アドレスMADRの下位側のビットの値は一致アドレスMADR0の値に等しくなる。また一致アドレスMADRの上位側のビットの値は、一致したエンコーダブロックのアドレス複数の繰り返しデータ検索装置の各々に付与されたアドレスとなるが、この場合はアドレス0のブロックなので全て0となる。図5cに示すように、次の検索データとしてBの文字データが入力されると、前回と同じマッチ線がハイレベルとなり、各マッチ線のレベルがラッチML0~ML5に各々一旦保持された後に、信号生成回路640~645に各々出力される。このときには、出力がハイレベルとなるラッチML1、ML3、ML4のうち前段のラッチPSの出力もハイレベルであるラッチはラッチML4のみであるので、AND回路701、703、704から出力される信号のうちAND回路704から出力される信号のみがハイレベルとなる。従って、OR回路78から出力されるフィードバック信号ORFB0はハイレベルで維持され、一致アドレスMADR0はPS4に対応するアドレス4となる。また、フィードバック信号ORFBがハイレベルで維持されるので、現在のサイクルをmとすると、アドレスnのラッチPSには、アドレスnのラッチMLの出力MLと、前段のラッチPSの出力PSとの論理積に相当する信号が出力される。この結果、ラッチPS4のみハイレベルを保持することになる。続いて図5dに示すように、次の検索データとしてBの文字データが入力される。この場合、ラッチML0~ML5に各々一旦保持された後に信号生成回路640~645に各々入力される各マッチ線のレベルは前回と同じであるが、ハイレベルの信号を出力するラッチML1、ML3、ML4の何れについても、前段のラッチPSから出力される信号がローレベルであるので、AND回路700~705から出力される信号は何れもローレベルとなり、フィードバック信号ORFB0及びフィードバック信号ORFBもローレベルとなる。またフィードバック信号ORFBがローレベルになると、各信号生成回路640~645のOR回路720~725の出力信号が各々ハイレベルとなるので、ラッチML1~ML5から出力された信号のレベルはラッチPS0~PS5にそのまま保持される。更に、図5eに示すように次の検索データとしてCの文字データが入力されるとマッチ線MATCH5のみがハイレベルとなり、各マッチ線のレベルがラッチML0~ML5に各々一旦保持された後に、信号生成回路640~645に各々出力される。このときには、ラッチML5からのみハイレベルの信号が出力され、前段のラッチPS4からもハイレベルの信号が出力されるので、AND回路700~705から出力される信号のうちAND回路705から出力される信号のみがハイレベルとなる。従って、OR回路78から出力されるフィードバック信号ORFB0はハイレベルで維持され、一致アドレスMADR0はPS1に対応するアドレス1となる。このように、繰り返しデータ検索回路21は、1文字入力されるごとにCAMセルアレイ26全体からその文字に一致する文字を検索する機能と、一致する文字があった文字についてその直前までの文字列が一致していたかの情報を保持する機能とを有しており、他の方法に比べ圧倒的に高速な文字列検索を可能にするものである。ここで、問題となるのは、文字列のトレースをどのように開始するかという点である。通常は最初の1文字が一致した位置で文字列のトレースを開始する。そうすることで、ある程度効果的な文字列圧縮を行うことは可能である。しかしながら、圧縮対象文字列によっては、最初の1文字が一致した位置でトレースを開始することが、必ずしも最良の圧縮に結び付くわけではない。図6に、このような文字列検索の例を示す。この例では、図6aに示すように、AからYまで10文字枠で囲んで示すが入力された状態で、この10文字からなる文字列を対象として、新たに入力される文字列ABCDEFに一致する文字列を検索する。このとき、最初に一致した文字からトレースすると、図6bのような圧縮結果が得られる。即ち、まず、文字列ABCに一致する文字列太枠で囲んで示すが見つかり、次に、新たに入力された文字列のうちの残りの文字列DEFに一致する文字列太枠で囲んで示すが見つかる。これにより、文字列ABCDEFは<10,3><7,3>に置き換えられ、圧縮が実現される。これに対し、最初に一致した文字を捨てて、2文字目が一致した位置からトレースすると、図6cのような圧縮結果が得られる。即ち、文字列BCDEFに一致する文字列太枠で囲んで示すが見つかる。これにより、文字列ABCDEFはA<7,5>に置き換えられ、図6bよりも高い圧縮率となっている。この場合に、最初の文字の一致を捨てた方がよいのかどうかや、何文字目までの一致を捨てるのが最良なのかは、圧縮対象データの属性次第である。従って、実際の適用には、複数のトレースを同時に行い、文字列の一致が途切れたトレースは切り捨て、文字列の一致が最も長く続いているトレースを選択する必要がある。そこで、本実施の形態では、図2~図5で述べたバイトの一致検出機構をそのまま利用し、この機能に複数の文字列トレース機構をカスケード接続した。これにより、複数の文字列トレース機構は、トレースの開始を各機構の段数分遅らせた文字列の一致検索を効果的に同時進行させ、全てのトレースの中から文字列一致が最長のものを選択する。言い換えると、図2~図5で述べた装置の大部分の面積を占める一致文字検出機構はそのまま利用し、文字列のトレース機構のみを複数個実装することで、ハードウェアリソースの増加を最小限に保ち、スループットを低下させることなく、文字列検索機能を強化する。図7-1及び図7-2は、本実施の形態における繰り返しデータ検索装置20の構成例を示したものである。図7-1に示すように、繰り返しデータ検索装置20は、繰り返しデータ検索回路21と、トレース回路1001、1002、...、100Kとを含む。繰り返しデータ検索回路21は、内部構成については図2~図4で説明したものと同様であるが、トレース回路1001、1002、...、100Kを接続したことにより、外部の回路との間で信号の入出力を行う構成について若干構成が異なっているので、その構成が異なる部分のみを説明する。尚、図では、図4のラッチ620~62Nをまとめてラッチ62とし、図4のラッチ660~66Nをまとめてラッチ66としている。また、図4と同様、AND回路680~68N、AND回路700~70N、OR回路720~72Nのうち、AND回路681、AND回路701、OR回路721のみを示している。但し、添字は省略している。図7-1に示すように、繰り返しデータ検索回路21は、OR回路78と、JKフリップフロップ1021とを更に含む。OR回路78の出力端はOR回路84の1個の入力端に接続され、OR回路84の出力端はインバータを介してOR回路72の2個の入力端の一方に接続されている。また、OR回路78の出力端はJKフリップフロップ1021のJ入力端にも接続され、OR回路84の出力端はJKフリップフロップ1021のK入力端にインバータを介して接続されている。また、図4では、第1プライオリティエンコーダ74及び第2のプライオリティエンコーダ76を設けていたが、ここでは、第2プライオリティエンコーダ76に相当するプライオリティエンコーダ82のみを設けている。即ち、図4では、CAMセルアレイ26から第1プライオリティエンコーダ74までが繰り返しデータ検索回路21であったが、この図では、CAMセルアレイ26から第2プライオリティエンコーダ76に相当するプライオリティエンコーダ82までが繰り返しデータ検索回路21になっている。トレース回路1001、1002、...、100Kは各々同一の構成であるので、トレース回路100Jで代表して述べるJ=1,2,...,K。トレース回路100Jは、繰り返しデータ検索回路21のCAMセルアレイ26及びラッチ62を除く部分とほぼ同様の構成である。即ち、トレース回路100Jは、ラッチ106J0~106JN、AND回路108J0~108JN、AND回路110J0~110JN、OR回路112J0~112JN、OR回路114J、プライオリティエンコーダ116Jを有しており、これらは各々、繰り返しデータ検索回路21のラッチ660~66N、AND回路680~68N、AND回路700~70N、OR回路720~72N、OR回路78、プライオリティエンコーダ82に相当する。尚、トレース回路100Jについても、ラッチ106J0~106JNをまとめてラッチ106Jとしている。また、AND回路108J0~108JN、AND回路110J0~110JN、OR回路112J0~112JNのうち、AND回路108J1、AND回路110J1、OR回路112J1のみを示している。但し、2つ目の添字CAMセル列のアドレスを表す添字は省略している。図7-1に示すように、トレース回路100Jは、OR回路114Jと、JKフリップフロップ102J1と、AND回路104Jとを含む。OR回路114Jの出力端はOR回路84の1個の入力端に接続されている。また、OR回路114Jの出力端はJKフリップフロップ102J1のJ入力端にも接続され、OR回路84の出力端はJKフリップフロップ102J1のK入力端にインバータを介して接続されているJ=Kのときは除く。更に、OR回路84の出力端はAND回路104Jの2個の入力端の一方に接続され、AND回路104Jの2個の入力端の他方にはJKフリップフロップ102J-1の出力端が接続されている。また、図7-2に示すように、繰り返しデータ検索装置20は、タイミング調整回路群86と、フリップフロップ群88と、OR回路90と、デコーダ92と、フリップフロップ群94と、セレクタ96とを更に含む。タイミング調整回路群86は、AND回路1180~118Kと、Dフリップフロップ1200~120Kとを含む。AND回路1180の2個の入力端の一方は繰り返しデータ検索回路21のOR回路78の出力端に接続され、AND回路1180の2個の入力端の他方はDフリップフロップ1200の出力端に接続されている。また、Dフリップフロップ1200のデータ入力端は接地されており、クロック入力端はOR回路78の出力端に接続されている。AND回路118Jの2個の入力端の一方はトレース回路100JのOR回路114Jの出力端に接続され、AND回路118Jの2個の入力端の他方はDフリップフロップ120Jの出力端に接続されている。また、Dフリップフロップ120Jのデータ入力端は接地されており、クロック入力端はOR回路114Jの出力端に接続されているJ=1,2,...,K。フリップフロップ群88は、フリップフロップ12201~1220K、12211~1221K-1、...、122K-11を含む。フリップフロップ122J1~122JK-JはK-J段フリップフロップを構成し、フリップフロップ122JK-Jの入力端はAND回路118Jの出力端に接続され、フリップフロップ122J1の出力端はOR回路90及びデコーダ92の入力端に接続されているJ=1,2,...,K-1。尚、AND回路118Kの出力端は直接OR回路90及びデコーダ92の入力端に接続されている。フリップフロップ群94は、フリップフロップ12401~1240K、12411~1241K-1、...、124K-11を含む。フリップフロップ12401~1240KはK段フリップフロップを構成し、フリップフロップ1240Kの入力端は繰り返しデータ検索回路21のプライオリティエンコーダ82の出力端に接続され、フリップフロップ12401の出力端はセレクタ96の入力端に接続されている。また、フリップフロップ124J1~124JK-JはK-J段フリップフロップを構成し、フリップフロップ124JK-Jの入力端はトレース回路100Jのプライオリティエンコーダ116Jの出力端に接続され、フリップフロップ124J1の出力端はセレクタ96の入力端に接続されているJ=1,2,...,K-1。尚、プライオリティエンコーダ116Kの出力端は直接セレクタ96の入力端に接続されている。尚、上記説明において、ラッチ106J、AND回路108J、AND回路110J、OR回路112J、OR回路114J、プライオリティエンコーダ116Jからなる部分は生成回路、特にJ番目の拡張生成回路の一例である。また、OR回路90は第1の出力回路の一例であり、セレクタ96は第2の出力回路の一例である。次に、本実施の形態における繰り返しデータ検索装置20の動作について、図8-1~図8-3を参照して説明する。尚、図8-1~図8-3では元データがテキストデータであり、アドレス0~9のCAMセル列に既にABCXBCDEFYの文字データ列が順に記憶されており、かつ、検索データとしてABCDEFの順に文字データが入力された場合を例として示しており、トレース回路100の数を5としている。また、ラッチ620~629をML0~ML9、ラッチ660~669をPS00~PS09、ラッチ10610~10619をPS10~PS19、ラッチ10620~10629をPS20~PS29、...、ラッチ10650~10659をPS50~PS59と称している。更に、繰り返しデータ検索回路21、トレース回路1001、1002、...、100Jの各々において、複数のPSに1が保持されていた場合、プライオリティエンコーダ82、1161、1162、...、116Kは、最も低いアドレスを選択して出力するものとする。図8-1aに示すように、検索データとして、まずAの文字データが入力されると、アドレス0のCAMセル列で比較結果が一致となるので、ラッチML0に保持されるレベルがハイレベルとなる。このとき、ラッチPS00~PS09に保持されているレベルがローレベルであるので、AND回路700~709から出力される信号は何れもローレベルとなり、OR回路78から出力されるフィードバック信号ORFB0もローレベルとなる。ラッチPS10~PS19、...、PS50~PS59に保持されているレベルがローレベルであるので、AND回路11010~11019、...、11050~11059から出力される信号は何れもローレベルとなり、OR回路1141、...、1145から出力されるフィードバック信号ORFB1、...、ORFB5もローレベルとなる。このようにフィードバック信号ORFB0、ORFB1、...、ORFB5がローレベルであることから、OR回路84から出力される信号はローレベルとなるので、OR回路720~729の出力は何れもハイレベルとなり、ラッチML0~ML9から出力された信号のレベルはラッチPS00~PS09にそのまま保持される。これにより、ラッチPS00~PS09のうち、ラッチPS00が保持するレベルのみがハイレベルとなっているので、プライオリティエンコーダ82は、一致アドレスMADR0としてアドレス0を出力する図8-1b参照。また、OR回路78から出力されるローレベルの信号がJKフリップフロップ1021のJ入力端に入力され、OR回路84から出力されるローレベルの信号を反転したハイレベルの信号がJKフリップフロップ1021のK入力端に入力されることにより、JKフリップフロップ1021に保持されるレベルはローレベルとなる。図8-1bに示すように、次の検索データとしてBの文字データが入力されると、アドレス1、4のCAMセル列で比較結果が一致となるので、ラッチML1、ML4に保持されるレベルがハイレベルとなる。このとき、ラッチPS00に保持されているレベルがハイレベルであるので、AND回路701から出力される信号はハイレベルとなり、OR回路78から出力されるフィードバック信号ORFB0もハイレベルとなる。ラッチPS10~PS19、...、PS50~PS59に保持されているレベルがローレベルであるので、AND回路11010~11019、...、11050~11059から出力される信号は何れもローレベルとなり、OR回路1141、...、1145から出力されるフィードバック信号ORFB1、...、ORFB5もローレベルとなる。このようにフィードバック信号ORFB0がハイレベルであることから、OR回路84から出力される信号もハイレベルとなるので、ラッチML0~ML9から出力された信号のレベルと前段のラッチPSから出力された信号との論理積がラッチPS00~PS09に保持される。これにより、ラッチPS00~PS09のうち、ラッチPS1が保持するレベルのみがハイレベルとなっているので、プライオリティエンコーダ82は、一致アドレスMADR0としてアドレス1を出力する図8-2cのPS0欄参照。JKフリップフロップ1021に保持されていたレベルはローレベルであり、AND回路1041から出力される信号もローレベルとなるので、OR回路11210~11219の出力は何れもハイレベルとなり、ラッチML0~ML9から出力された信号のレベルはラッチPS10~PS19にそのまま保持される。これにより、ラッチPS10~PS19のうち、ラッチPS11、PS14が保持するレベルがハイレベルとなっているので、プライオリティエンコーダ1161は、一致アドレスMADR1としてアドレス1を出力する図8-2cのPS1欄参照。また、OR回路78から出力されるハイレベルの信号がJKフリップフロップ1021のJ入力端に入力され、OR回路84から出力されるハイレベルの信号を反転したローレベルの信号がJKフリップフロップ1021のK入力端に入力されることにより、JKフリップフロップ1021に保持されるレベルはハイレベルとなる。OR回路1141から出力されるローレベルの信号がJKフリップフロップ1022のJ入力端に入力され、OR回路84から出力されるローレベルの信号を反転したハイレベルの信号がJKフリップフロップ1022のK入力端に入力されることにより、JKフリップフロップ1022に保持されるレベルはローレベルとなる。図8-2cに示すように、次の検索データとしてCの文字データが入力されると、アドレス2、5のCAMセル列で比較結果が一致となるので、ラッチML2、ML5に保持されるレベルがハイレベルとなる。このとき、ラッチPS01に保持されているレベルがハイレベルであるので、AND回路701から出力される信号はハイレベルとなり、OR回路78から出力されるフィードバック信号ORFB0もハイレベルとなる。ラッチPS11、PS14に保持されているレベルがハイレベルであるので、AND回路11011、11014から出力される信号はハイレベルとなり、OR回路1141から出力されるフィードバック信号ORFB1もハイレベルとなる。ラッチPS20~PS29、...、PS50~PS59に保持されているレベルがローレベルであるので、AND回路11020~11029、...、11050~11059から出力される信号は何れもローレベルとなり、OR回路1142、...、1145から出力されるフィードバック信号ORFB2、...、ORFB5もローレベルとなる。このようにフィードバック信号ORFB0、ORFB1がハイレベルであることから、OR回路84から出力される信号もハイレベルとなるので、ラッチML0~ML9から出力された信号のレベルと前段のラッチPS0から出力された信号との論理積がラッチPS00~PS09に保持される。これにより、ラッチPS00~PS09のうち、ラッチPS02が保持するレベルのみがハイレベルとなっているので、プライオリティエンコーダ82は、一致アドレスMADR0としてアドレス2を出力する図8-2dのPS0欄参照。JKフリップフロップ1021に保持されていたレベル及びOR回路84から出力される信号はハイレベルであり、AND回路1041から出力される信号もハイレベルとなるので、ラッチML0~ML9から出力された信号のレベルと前段のラッチPS1から出力された信号との論理積がラッチPS10~PS19に保持される。これにより、ラッチPS10~PS19のうち、ラッチPS12、PS15が保持するレベルがハイレベルとなっているので、プライオリティエンコーダ1161は、一致アドレスMADR1としてアドレス2を出力する図8-2dのPS1欄参照。JKフリップフロップ1022に保持されていたレベルはローレベルであり、AND回路1042から出力される信号もローレベルとなるので、OR回路11220~11229の出力は何れもハイレベルとなり、ラッチML0~ML9から出力された信号のレベルはラッチPS10~PS19にそのまま保持される。これにより、ラッチPS20~P29のうち、ラッチPS22、PS25が保持するレベルがハイレベルとなっているので、プライオリティエンコーダ1162は、一致アドレスMADR2としてアドレス2を出力する図8-2dのPS2欄参照。また、OR回路78から出力されるハイレベルの信号がJKフリップフロップ1021のJ入力端に入力され、OR回路84から出力されるハイレベルの信号を反転したローレベルの信号がJKフリップフロップ1021のK入力端に入力されることにより、JKフリップフロップ1021に保持されるレベルはハイレベルとなる。OR回路1141から出力されるハイレベルの信号がJKフリップフロップ1022のJ入力端に入力され、OR回路84から出力されるハイレベルの信号を反転したローレベルの信号がJKフリップフロップ1022のK入力端に入力されることにより、JKフリップフロップ1022に保持されるレベルはハイレベルとなる。OR回路1142から出力されるローレベルの信号がJKフリップフロップ1023のJ入力端に入力され、OR回路84から出力されるハイレベルの信号を反転したローレベルの信号がJKフリップフロップ1023のK入力端に入力されることにより、JKフリップフロップ1023に保持されるレベルはローレベルとなる。図8-2dに示すように、次の検索データとしてDの文字データが入力されると、アドレス6のCAMセル列で比較結果が一致となるので、ラッチML6に保持されるレベルがハイレベルとなる。このとき、ラッチML6の前段のラッチPS05に保持されているレベルはローレベルであり、また、ラッチPS02に保持されているレベルはハイレベルであるが後段のラッチML3に保持されているレベルはローレベルであるので、AND回路700~709から出力される信号は何れもローレベルとなり、OR回路78から出力されるフィードバック信号ORFB0もローレベルとなる。ラッチPS12、PS15、PS22、PS25に保持されているレベルがハイレベルであるので、AND回路11010~11019、11020~11029から出力される信号は何れもハイレベルとなり、OR回路1141、1142から出力されるフィードバック信号ORFB1、ORFB2もハイレベルとなる。ラッチPS30~PS39、...、PS50~PS59に保持されているレベルがローレベルであるので、AND回路11030~11039、...、11050~11059から出力される信号は何れもローレベルとなり、OR回路1143、...、1145から出力されるフィードバック信号ORFB3、...、ORFB5もローレベルとなる。このようにフィードバック信号ORFB1、ORFB2がハイレベルであることから、OR回路84から出力される信号もハイレベルとなるので、ラッチML0~ML9から出力された信号のレベルと前段のラッチPS0から出力された信号との論理積がラッチPS00~PS09に保持される図8-3eのPS0欄参照。即ち、検索データとの一致がここで途切れたので、ラッチPS00~PS09に保持されているレベルはローレベルとなっている。JKフリップフロップ1021、1022に保持されていたレベル及びOR回路84から出力される信号はハイレベルであり、AND回路1041、1042から出力される信号もハイレベルとなるので、ラッチML0~ML9から出力された信号のレベルと前段のラッチPS1、PS2から出力された信号の各々との論理積がラッチPS10~PS19、PS20~PS29に保持される。これにより、ラッチPS10~PS19、PS20~PS29のうち、ラッチPS16、PS26が保持するレベルがハイレベルとなっているので、プライオリティエンコーダ1161、1162は、一致アドレスMADR1、MADR2としてアドレス6を出力する図8-3eのPS1欄、PS2欄参照。JKフリップフロップ1023に保持されていたレベルはローレベルであり、AND回路1043から出力される信号もローレベルとなるので、OR回路11230~11239の出力は何れもハイレベルとなり、ラッチML0~ML9から出力された信号のレベルはラッチPS30~PS39にそのまま保持される。これにより、ラッチPS30~PS39のうち、ラッチPS36が保持するレベルがハイレベルとなっているので、プライオリティエンコーダ1163は、一致アドレスMADR3としてアドレス6を出力する図8-3eのPS3欄参照。また、OR回路78から出力されるローレベルの信号がJKフリップフロップ1021のJ入力端に入力され、OR回路84から出力されるハイレベルの信号を反転したローレベルの信号がJKフリップフロップ1021のK入力端に入力されることにより、JKフリップフロップ1021に保持されるレベルはハイレベルとなる。OR回路1141、1142から出力されるハイレベルの信号がJKフリップフロップ1022、1023のJ入力端に入力され、OR回路84から出力されるハイレベルの信号を反転したローレベルの信号がJKフリップフロップ1022、1023のK入力端に入力されることにより、JKフリップフロップ1022、1023に保持されるレベルはハイレベルとなる。OR回路1143から出力されるローレベルの信号がJKフリップフロップ1024のJ入力端に入力され、OR回路84から出力されるハイレベルの信号を反転したローレベルの信号がJKフリップフロップ1024のK入力端に入力されることにより、JKフリップフロップ1024に保持されるレベルはローレベルとなる。図8-3eに示すように、次の検索データとしてEの文字データが入力されると、アドレス7のCAMセル列で比較結果が一致となるので、ラッチML6に保持されるレベルがハイレベルとなる。このとき、ラッチPS00~PS09に保持されているレベルがローレベルであるので、AND回路700~709から出力される信号は何れもローレベルとなり、OR回路78から出力されるフィードバック信号ORFB0もローレベルとなる。ラッチPS16、PS26、PS36に保持されているレベルがハイレベルであるので、AND回路11010~11019、11020~11029、11030~11039から出力される信号は何れもハイレベルとなり、OR回路1141、1142、1143から出力されるフィードバック信号ORFB1、ORFB2、ORFB3もハイレベルとなる。ラッチPS40~PS49、PS50~PS59に保持されているレベルがローレベルであるので、AND回路11040~11049、11050~11059から出力される信号は何れもローレベルとなり、OR回路1144、1145から出力されるフィードバック信号ORFB4、ORFB5もローレベルとなる。このようにフィードバック信号ORFB1、ORFB2、ORFB3がハイレベルであることから、OR回路84から出力される信号もハイレベルとなるので、ラッチML0~ML9から出力された信号のレベルと前段のラッチPS0から出力された信号との論理積がラッチPS00~PS09に保持される図8-3fのPS0欄参照。JKフリップフロップ1021、1022、1023に保持されていたレベル及びOR回路84から出力される信号はハイレベルであり、AND回路1041、1042、1043から出力される信号もハイレベルとなるので、ラッチML0~ML9から出力された信号のレベルと前段のラッチPS1、PS2、PS3から出力された信号の各々との論理積がラッチPS10~PS19、PS20~PS29、PS30~PS39に保持される。これにより、ラッチPS10~PS19、PS20~PS29、PS30~PS39のうち、ラッチPS17、PS27、PS37が保持するレベルがハイレベルとなっているので、プライオリティエンコーダ1161、1162、1163は、一致アドレスMADR1、MADR2、MADR3としてアドレス7を出力する図8-3fのPS1欄、PS2欄、PS3欄参照。JKフリップフロップ1024に保持されていたレベルはローレベルであり、AND回路1044から出力される信号もローレベルとなるので、OR回路11240~11249の出力は何れもハイレベルとなり、ラッチML0~ML9から出力された信号のレベルはラッチPS40~PS49にそのまま保持される。これにより、ラッチPS40~PS49のうち、ラッチPS47が保持するレベルがハイレベルとなっているので、プライオリティエンコーダ1164は、一致アドレスMADR4としてアドレス7を出力する図8-3fのPS4欄参照。以上の動作で文字データが入力されるごとに出力されたORFB0~ORFBK上記例ではK=5はAND回路1180~118Kを経由してデコーダ92へと出力される。ここで、本実施の形態では、OR回路84からのフィードバック信号ORFBがローレベルになると、Dフリップフロップ1200~120Kがハイレベルに設定され、ORFB0~ORFBKがAND回路1180~118Kを通過できるようになっている。一方で、ORFB0~ORFBKのレベルが一旦ハイレベルになった後にローレベルになると、Dフリップフロップ1200~120Kのクロック入力端から入力されるレベルがローレベルからハイレベルになり、ORFB0~ORFBKがAND回路1180~118Kを通過できないようになる。また、同じく文字データが入力されるごとに出力されたMADR0~MADR5はセレクタ96へと出力される。但し、本実施の形態では、ORFBJを伝える経路上のデコーダ92の前にK-J段のフリップフロップ122を設け、MADRJを伝える経路上のセレクタ96の前にK-J段のフリップフロップ124を設けているJ=1,2,...,K-1。また、ORFBK、MADRKを伝える経路上のデコーダ92、セレクタ96の前にはフリップフロップを設けていない。これにより、ORFB0~ORFB5及びMADR0~MADR5は、上記動作で基準とした文字データの入力タイミングに同期したタイミングでデコーダ92及びセレクタ96に届くのではなく、フリップフロップの段数分ずれたタイミングでデコーダ92及びセレクタ96に届くようになっている。そこで、次に、デコーダ92及びセレクタ96が信号を受け取るタイミングを基準として、繰り返しデータ検索装置20の動作を説明する。尚、図8-1~図8-3には示していないが、以下では、図8-3fの文字データFで文字列の一致は終了することを前提にする。即ち、文字データFの次の文字データが入力されると、ORFB0~ORFB5はローレベルになるものとする。また、デコーダ92は、ORFB0~ORFB5のうちハイレベルになっているORFBの番号をセレクタ96に伝え、セレクタ96は、デコーダ92から伝えられた番号のMADRのうち、最小の番号のMADRを選択するものとする。まず、デコーダ92が図8-1bで出力されたORFB0をフリップフロップ12201から受け取る時点を考える。この時点において、デコーダ92は、図8-2cで出力されたORFB1をフリップフロップ12211から、図8-2dで出力されたORFB2をフリップフロップ12221から、図8-3eで出力されたORFB3をフリップフロップ12231から、図8-3fで出力されたORFB4をフリップフロップ12241から、図8-3f以降に出力されたORFB5ローレベルをプライオリティエンコーダ1165から受け取る。この場合、ORFB0~ORFB4がハイレベルなので、OR回路90からデータ圧縮コントローラ22へ出力されるConsolidatedORFB以下、CORFBと略記するはハイレベルとなる。また、デコーダ92は、ORFB0~ORFB4がハイレベルであることをセレクタ96に伝え、セレクタ96は、MADR0を選択し、アドレス0をデータ圧縮コントローラ22に出力する。次に、デコーダ92は、図8-2cで出力されたORFB0をフリップフロップ12201から、図8-2dで出力されたORFB1をフリップフロップ12211から、図8-3eで出力されたORFB2をフリップフロップ12221から、図8-3fで出力されたORFB3をフリップフロップ12231から、図8-3f以降に出力されたORFB4、ORFB5何れもローレベルを各々、フリップフロップ12241、プライオリティエンコーダ1165から受け取る。この場合、ORFB0~ORFB3がハイレベルなので、OR回路90からデータ圧縮コントローラ22へ出力されるCORFBはハイレベルとなる。また、デコーダ92は、ORFB0~ORFB3がハイレベルであることをセレクタ96に伝え、セレクタ96は、MADR0を選択し、アドレス1をデータ圧縮コントローラ22に出力する。次に、デコーダ92は、図8-2dで出力されたORFB0をフリップフロップ12201から、図8-3eで出力されたORFB1をフリップフロップ12211から、図8-3fで出力されたORFB2をフリップフロップ12221から、図8-3f以降に出力されたORFB3~ORFB5何れもローレベルを各々、フリップフロップ12231、フリップフロップ12241、プライオリティエンコーダ1165から受け取る。この場合、ORFB1、ORFB2がハイレベルなので、OR回路90からデータ圧縮コントローラ22へ出力されるCORFBはハイレベルとなる。また、デコーダ92は、ORFB1、ORFB2がハイレベルであることをセレクタ96に伝え、セレクタ96は、MADR1を選択し、アドレス6をデータ圧縮コントローラ22に出力する。図8-1~図8-3の例では、Aからトレースした場合、この時点で文字列の一致が途切れるので、デコーダ92はORFB0をセレクタ96に伝えず、セレクタ96がORFB0を選択しないようにしている。次に、デコーダ92は、図8-3eで出力されたORFB0をフリップフロップ12201から、図8-3fで出力されたORFB1をフリップフロップ12211から、図8-3f以降に出力されたORFB2~ORFB5何れもローレベルを各々、フリップフロップ12221、フリップフロップ12231、フリップフロップ12241、プライオリティエンコーダ1165から受け取る。この場合、ORFB1がハイレベルなので、OR回路90からデータ圧縮コントローラ22へ出力されるCORFBはハイレベルとなる。また、デコーダ92は、ORFB1がハイレベルであることをセレクタ96に伝え、セレクタ96は、MADR1を選択し、アドレス7をデータ圧縮コントローラ22に出力する。次に、デコーダ92は、図8-3fで出力されたORFB0をフリップフロップ12201から、図8-3f以降に出力されたORFB1~ORFB5何れもローレベルを各々、フリップフロップ12211、フリップフロップ12221、フリップフロップ12231、フリップフロップ12241、プライオリティエンコーダ1165から受け取る。この場合、ORFB1~ORFB5は何れもローレベルなので、OR回路90からデータ圧縮コントローラ22へ出力されるCORFBはローレベルとなる。従って、データ圧縮コントローラ22は、CORFBがローレベルになる直前にセレクタ96から受け取った7を一致アドレスとして用いることになる。次に、本実施の形態におけるデータ圧縮コントローラ22の動作について説明する。図9は、データ圧縮コントローラ22における処理を示したフローチャートである。尚、この処理は、データ圧縮コントローラ22にバス18を介して圧縮すべきデータ元データが転送され、CPU12から元データの圧縮が指示されると実行される。データ圧縮コントローラ22は、まず、繰り返しデータ検索装置20の比較結果制御回路60のラッチ620~62N、ラッチ660~66Nを各々リセットするステップ200。次に、一致長MLENを1に、書込みアドレスWADRを0に各々初期設定するステップ202。そして、繰り返しデータ検索装置20への元データの出力が終了したか否か判定するステップ204。判定が否定された場合には、元データから先頭の1文字に対応する文字C0のデータを検索データとして取り出し、繰り返しデータ検索装置20に検索指示SEARCH、書込みアドレスWADRと共に出力するステップ206。これにより、繰り返しデータ検索装置20では前述した検索動作が行われる。次に、データ圧縮コントローラ22は、繰り返しデータ検索装置20から出力される文字列一致信号CORFBがハイレベルになったか否か判定するステップ208。このときには、先のステップ200で各ラッチ62及び各ラッチ66をリセットしたことに伴って文字列一致信号CORFBはローレベルで維持されるので、判定が否定されてステップ210へ移行する。そこで、データ圧縮コントローラ22は、今回の比較動作が所定の元データに対する第1回目の比較動作であるか否か判定しステップ210、判定が肯定された場合はステップ212で圧縮データの出力処理を行うことなくステップ214へ移行する。前述したORFBと同様、文字列一致信号CORFBも2文字以上連続して一致しないとハイレベルにならないため、比較結果不一致が続いている場合は後述するように圧縮データとして前回検索した文字を出力する。従って、この時点では圧縮データとして出力すべきデータがないためステップ212を実行しない。その後、データ圧縮コントローラ22は、一致長MLENに1を代入しステップ214、ステップ218へ移行する。そして、前々回検索文字C2に前回検索文字C1のデータを、前回検索文字C1に今回の文字C0のデータを、各々設定しステップ218、現在の書込みアドレスWADR第1回目の比較動作では0に対応するCAMセル列に文字C0のデータを書き込むステップ220。この書込み処理は、実際にはアドレスデコーダ52によって書込みアドレスWADRに対応するCAMセル列のワード線をアサートするイネーブルにすることにより行われる。また、データ圧縮コントローラ22は、次の書込みアドレスWADRとして、書込みアドレスWADRに1を加算し従って文字データはCAMセル列のアドレスの昇順に書き込まれる、CAMセルアレイ26のサイズN1で除した余りを設定するステップ222。これにより全てのCAMセル列にデータを書き込んだ後は、アドレス0のCAMセル列にデータが書き込まれるので、CAMセルアレイ26が所謂リングバッファとして用いられ、CAMセルアレイ26のオーバフロー等が発生することはない。ステップ222の処理を行った後はステップ204へ戻る。ステップ204の判定が否定された場合にはステップ206以降の処理を再度実行するが、ステップ206では前回検索文字C1に続く文字C0のデータが検索データとして元データから取り出され、検索指示SEARCH、書込みアドレスWADRと共に繰り返しデータ検索装置20へ出力される。そしてステップ208の判定が否定された場合はステップ210へ移行し、この判定が否定されることによりステップ212の圧縮データ出力処理が行われる。図10に示すように、データ圧縮コントローラ22は、この圧縮データ出力処理で、一致長MLENが2か否か判定するステップ230。前回の比較結果は一致であるが、前々回の比較結果が一致でない場合は判定が肯定され、圧縮データとして、前々回検索文字C2のデータを出力しステップ236、次いで前回検索文字C1のデータを出力しステップ238、その後に図9のフローチャートのステップ214へ移行する。ステップ230で判定が否定された場合、データ圧縮コントローラ22は、一致長MLENが1か否かを判定するステップ232。前回の比較結果が一致でない場合は判定が肯定され、圧縮データとして前回検索文字C1のデータを出力しステップ238、その後に図9のフローチャートのステップ214へ移行する。ところで、図9のフローチャートにおいてステップ208の判定が肯定された場合には、一致長MLENをカウントアップしステップ216、その後にステップ218へ移行する。従って、文字列一致信号CORFBがハイレベルとなっている間は圧縮データの出力は行われない。また、前回の比較動作でハイレベルとなっていた文字列一致信号CORFBがローレベルに変化してステップ210の判定が否定された場合は、2文字以上の長さの繰り返し文字列の末尾が検出された場合であるので、ステップ212で圧縮データ出力処理が行われる。このときは、前回及び前々回の比較結果が共に一致であれば、先に説明したステップ216で一致長MLENがカウントアップされて3以上になっているので、ステップ230及びステップ232の判定が共に否定され、ステップ234へ移行する。そこで、データ圧縮コントローラ22は、繰り返し文字列を圧縮するための圧縮コードを求める。本実施の形態では、繰り返し文字列と同一の文字列の位置を指し示すポインタを表す第1のコードと、繰り返し文字列の長さを表す第2のコードとで構成された圧縮コードを用いており、第1のコードとして一致アドレスMADRと一致長MLENとの差に1を加えた値MADR-MLEN1を、第2のコードとして一致長MLENを各々設定し、出力するステップ234。これにより、データ圧縮コントローラ22から出力される圧縮データの長さは、元データよりも短くなる。尚、この圧縮コードを出力するにあたり、圧縮した文字列を復元する際に圧縮コードと文字データとを区別できるようにするために、データ圧縮コントローラ22は文字データと圧縮コードとの間に区切りを表すコードも挿入する。このように、繰り返し文字列が発見される毎にステップ234が実行され、発見された繰り返し文字列が圧縮コードに変換されて出力されることにより、元データの冗長性が取り除かれ、元データが圧縮データに圧縮されることになる。上述の処理を繰り返し、元データからの文字Cのデータの取り出し位置が元データの末尾に到達するとステップ204の判定が肯定され、データ圧縮コントローラ22は、圧縮データ出力処理を再び行うステップ224。このとき、一致長MLENの値が3以上であれば、ステップ234で圧縮コードの出力が行われるが、一致長MLENの値が2の場合には、ステップ236及びステップ238で圧縮データとして前々回検索文字C2のデータ及び前回検索文字C1のデータを、一致長MLENの値が1の場合には、ステップ238で圧縮データとして前回検索文字C1のデータを、それぞれ出力し、処理を終了する。尚、この動作例では、圧縮コードのうち第1のコードとして、繰り返し文字列と同一の文字列の位置を指し示すポインタを用いたが、前述した例に従い、繰り返し文字列と同一の文字列の位置と繰り返し文字列の位置との距離を用いてもよい。この場合、データ圧縮コントローラ22は、繰り返しデータ検索回路21及びトレース回路1001、1002、...、100Kのうち、ハイレベルのORFBを最も長く出力し続けていた回路を、繰り返しデータ検索装置20からのDecodeOutput信号図7-2参照に基づいて認識し、その回路におけるトレース開始文字の位置から上記繰り返し文字列と同一の文字列の位置を減算して得られた値を第1のコードとすればよい。以上、本発明の実施の形態について説明した。このように、本実施の形態では、入力された文字データに一致する文字データをCAMセルアレイ26から検出して文字列としての一致を判定する繰り返しデータ検索回路21に、1文字ずつずらした検索開始点から文字列としての一致を判定する複数のトレース回路100を接続した。これにより、同一部分を有する長さの異なる複数の文字列が存在する検索対象から長い方の文字列を効果的に検出することが可能となり、圧縮率を向上できるようになった。ここで、本実施の形態による有効性の検証について述べる。データ圧縮アルゴリズムの評価用の一般的なデータセットとして、CanterburyCorpusの一連のデータがあるが、例えばその中のkennedyxls1029744バイトに関する本実施の形態の有効性を示すデータを以下に示す。尚、このデータは、32KBのCAMを用いてLZ77圧縮を行ったものをFixedHuffmanTableで圧縮し、ハードウェアの振る舞いと等価なソフトウェアモデルで検証することにより得られたものである。1LZ77に繰り返しデータ検索回路21のみを適用した場合、圧縮後のバイト数は417599となり、圧縮率は041となった。2LZ77に繰り返しデータ検索回路21及び1バイト遅らせてトレースする1つのトレース回路100からなる回路を適用した場合、圧縮後のバイト数は302140ととなり、圧縮率は029となった。繰り返しデータ検索回路21では、各アドレスに10ビットCAMセルアレイ26に8ビット、ラッチ62に1ビット、ラッチ66に1ビットの情報が保持されるが、上記では各アドレスに1ビットを追加することで圧縮率が飛躍的に向上することが分かる。尚、本実施の形態では、文字列のある部分を別の部分の位置及び長さの情報で置換することにより文字列を圧縮することを前提にしたが、文字列のある部に基づいて別の部分を検索する際の検索開始点を決定することを前提にしてもよい。その場合、繰り返しデータ検索回路21及びトレース回路1001、1002、...、100Kのうち、ハイレベルのORFBの連続生成回数が最も多い回路が分かればよいので、必ずしもORFBの論理和をとってCORFBを求めたり、CORFBの連続出力回数をカウントしたりする必要はない。また、本実施の形態では、ハイレベルのORFBの連続生成回数が最も多い回路に対して予め決められた個別開始点を検索開始点に決定したが、これには限らない。例えば、ハイレベルのORFBの連続生成回数が閾値を超えた時点でトレースを終了し、その時点でハイレベルのORFBを生成している何れかの回路を選択して、その選択された回路に対して予め決められた個別開始点を検索開始点に決定してもよい。即ち、より一般的に言うと、ハイレベルのORFBの連続生成回数が所定の条件を満たす回路に対して予め決められた個別開始点を検索開始点に決定するようなものでよい。更に、本実施の形態では、繰り返しデータ検索回路21及びトレース回路1001、1002、...、100Kに対して個別開始点を1文字ずつずらして設定したが、これには限らない。各回路の間で個別開始点が異なってさえいれば、何文字ずつずらして設定してもよい。以上、本発明を実施の形態を用いて説明したが、本発明の技術的範囲は上記実施の形態には限定されない。本発明の精神及び範囲から逸脱することなく様々に変更したり代替態様を採用したりすることが可能なことは、当業者に明らかである。"