(57)【特許請求の範囲】
【請求項１】
コンテンツ情報が格納された第１の記憶手段と、前記第１の記憶手段に格納されたコンテンツ情報を指定するための第１の情報が格納された複数の第２の記憶手段とを少なくとも有し、前記コンテンツ情報を検索するために与えられた検索キーが前記第２の記憶手段の数分に分割され、分割された検索キーのそれぞれが前記第２の記憶手段に格納された前記第１の情報と比較され、両者が一致した場合に該第１の情報が格納された前記第２の記憶手段内のアドレスを用いて前記第１の記憶手段から前記コンテンツ情報が検索される情報検索装置において、
前記第１の記憶手段内のアドレスを指定するための第２の情報が格納された第３の記憶手段と、
前記検索キーと一致する第１の情報が格納された複数の第２の記憶手段内のアドレスを用いて、前記第３の記憶手段から前記分割された検索キー毎に前記第２の情報を検索する制御手段と、
前記分割された検索キー毎に検索された前記第２の情報を加算する加算手段と、
前記加算手段における加算結果を用いて前記第１の記憶手段から前記コンテンツ情報を検索する検索結果送受信手段とを有し、
前記第１の記憶手段は、前記検索キーによって指定された前記第３の記憶手段内のアドレスに格納された前記第２の情報が加算された場合に該加算結果によって指定されるアドレスに前記検索キーによって検索されるべきコンテンツ情報を格納していることを特徴とする情報検索装置。
【請求項２】
コンテンツ情報が格納された第１の記憶手段と、前記第１の記憶手段に格納されたコンテンツ情報を指定するための第１の情報が格納された第２の記憶手段とを少なくとも有し、前記コンテンツ情報を検索するために与えられた検索キーが分割され、分割された検索キーのそれぞれが前記第２の記憶手段に格納された前記第１の情報と比較され、両者が一致した場合に該第１の情報が格納された前記第２の記憶手段内のアドレスを用いて前記第１の記憶手段から前記コンテンツ情報が検索される情報検索装置において、
前記第１の記憶手段内のアドレスを指定するための第２の情報が格納された第３の記憶手段と、
前記検索キーと一致する第１の情報が格納された前記第２の記憶手段内のアドレスを用いて、前記第３の記憶手段から前記分割された検索キー毎に前記第２の情報を検索する制御手段と、
前記分割された検索キー毎に検索された前記第２の情報を加算する加算手段と、
前記加算手段における加算結果を用いて前記第１の記憶手段から前記コンテンツ情報を検索する検索結果送受信手段とを有し、
前記第１の記憶手段は、前記検索キーによって指定された前記第３の記憶手段内のアドレスに格納された前記第２の情報が加算された場合に該加算結果によって指定されるアドレスに前記検索キーによって検索されるべきコンテンツ情報を格納していることを特徴とする情報検索装置。
【請求項３】
コンテンツ情報が格納された第１の記憶手段と、前記第１の記憶手段に格納されたコンテンツ情報を指定するための第１の情報が格納された第２の記憶手段とを少なくとも有し、前記コンテンツ情報を検索するために与えられた検索キーが分割され、分割された検索キーのそれぞれが前記第２の記憶手段に格納された前記第１の情報と比較され、両者が一致した場合に該第１の情報が格納された前記第２の記憶手段内のアドレスを用いて前記第１の記憶手段から前記コンテンツ情報が検索される情報検索装置において、
前記第１の記憶手段は、前記コンテンツ情報が格納されたアドレスを指定するための第２の情報が格納された領域を具備し、
前記検索キーと一致する第１の情報が格納された前記第２の記憶手段内のアドレスを用いて、前記第１の記憶手段から前記分割された検索キー毎に前記第２の情報を検索する制御手段と、
前記分割された検索キー毎に検索された前記第２の情報を加算する加算手段と、
前記加算手段における加算結果を用いて前記第１の記憶手段から前記コンテンツ情報を検索する検索結果送受信手段とを有し、
前記第１の記憶手段は、前記検索キーによって指定された当該第１の記憶手段内のアドレスに格納された前記第２の情報が加算された場合に該加算結果によって指定されるアドレスに前記検索キーによって検索されるべきコンテンツ情報を格納していることを特徴とする情報検索装置。
【請求項４】
コンテンツ情報が格納された第１の記憶手段と、前記第１の記憶手段に格納されたコンテンツ情報を指定するための第１の情報が格納された第２の記憶手段とを少なくとも有し、前記コンテンツ情報を検索するために与えられた検索キーが分割され、分割された検索キーによって指定される前記第２の記憶手段内のアドレスを用いて前記第１の記憶手段から前記コンテンツ情報が検索される情報検索装置において、
前記第１の記憶手段内のアドレスを指定するための第２の情報が格納された第３の記憶手段と、
前記検索キーと一致する第１の情報が格納された前記第２の記憶手段内のアドレスを用いて、前記第３の記憶手段から前記第２の情報を検索する制御手段と、前記第３の記憶手段から検索された前記第２の情報と前記分割された検索キーのうち前記第２の情報の検索に用いられない検索キーとを加算する加算手段と、前記加算手段における加算結果を用いて前記第１の記憶手段から前記コンテンツ情報を検索する検索結果送受信手段とを有し、
前記第１の記憶手段は、前記検索キーによって指定された前記第３の記憶手段内のアドレスに格納された前記第２の情報と前記分割された検索キーの前記第２の情報の検索に用いられない検索キーとが加算された場合に該加算結果によって指定されるアドレスに前記検索キーによって検索されるべきコンテンツ情報を格納していることを特徴とする情報検索装置。
【請求項５】
コンテンツ情報が格納された第１の記憶手段と、前記第１の記憶手段に格納されたコンテンツ情報を指定するための第１の情報が格納された第２の記憶手段とを少なくとも有し、前記コンテンツ情報を検索するために与えられた検索キーが分割され、分割された検索キーによって指定される前記第２の記憶手段内のアドレスを用いて前記第１の記憶手段から前記コンテンツ情報が検索される情報検索装置において、
前記第１の記憶手段は、前記コンテンツ情報が格納されたアドレスを指定するための第２の情報が格納された領域を具備し、
前記検索キーと一致する第１の情報が格納された前記第２の記憶手段内のアドレスを用いて、前記第１の記憶手段から前記第２の情報を検索する制御手段と、前記第１の記憶手段から検索された前記第２の情報と前記分割された検索キーのうち前記第２の情報の検索に用いられない検索キーとを加算する加算手段と、前記加算手段における加算結果を用いて前記第１の記憶手段から前記コンテンツ情報を検索する検索結果送受信手段とを有し、
前記第１の記憶手段は、前記検索キーによって指定された当該第１の記憶手段内のアドレスに格納された前記第２の情報と前記分割された検索キーの前記第２の情報の検索に用いられない検索キーとが加算された場合に該加算結果によって指定されるアドレスに前記検索キーによって検索されるべきコンテンツ情報を格納していることを特徴とする情報検索装置。
【請求項６】
コンテンツ情報が格納された第１の記憶手段と、前記第１の記憶手段に格納されたコンテンツ情報を指定するための第１の情報が格納された第２の記憶手段とを少なくとも有し、前記コンテンツ情報を検索するために与えられた検索キーが分割され、分割された検索キーのそれぞれが前記第２の記憶手段に格納された前記第１の情報と比較され、両者が一致した場合に該第１の情報が格納された前記第２の記憶手段内のアドレスを用いて前記第１の記憶手段から前記コンテンツ情報が検索される情報検索装置において、
前記検索キーと一致する第１の情報が格納された前記第２の記憶手段内のアドレスを加算する加算手段と、
前記加算手段における加算結果を用いて前記第１の記憶手段から前記コンテンツ情報を検索する検索結果送受信手段とを有することを特徴とする情報検索装置。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、入力された検索キーを用いて情報の検索を行う情報検索装置に関し、特に、多ビットからなる検索キーが入力された場合に該検索キーを複数に分割して情報の検索を行う情報検索装置に関する。
【０００２】
【従来の技術】
従来より、メモリに格納されたコンテンツ情報を高速に検索する手段としてＣＡＭ（Contents Addressable Memory）が用いられている。このＣＡＭを用いた情報検索においては、所望の検索キーを入力すると、入力された検索キーと同一あるいは類似する情報やそのアドレス等がメモリから検索される。ここで、１回の検索処理で検索し得る検索キーのビット幅は、設計上定まっている１ワ−ド当りのビット幅により制限を受けてしまう。そこで、１ワ−ドを越えるような多ビットからなる検索キーを用いて情報を検索する場合は、多ビットからなる検索キーを複数に分割し、ＣＡＭへの検索を複数回行うことにより、多ビットからなる検索キーを用いた情報の検索が行われている。検索キーとＣＡＭに登録されるコンテンツは一対一対応であり、ＣＡＭに登録されるコンテンツの管理方法や、ＣＡＭの検索結果から、コンテンツ情報が格納された検索結果格納メモリにアクセスするためのアドレスを決定する方法の工夫が必要となる。例えば特開平１１−２７３３６３号公報には、２つのＣＡＭとこの２つのＣＡＭのアドレスを比較するアドレス一致比較部とを設け、２つのＣＡＭのアドレスの比較結果に基づいて検索結果格納メモリのアドレスを決定する方法が開示されている。
【０００３】
図１６は、従来の情報検索装置の一構成例を示すブロック図である。
【０００４】
本従来例は図１６に示すように、検索キーが入力されるデータ入力部１０１と、コンテンツ情報が格納された検索結果格納メモリ１０４と、検索結果格納メモリ１０４に格納されたコンテンツ情報を指定するための情報が検索結果格納メモリ１０４の該コンテンツ情報のアドレスと同一のアドレスに格納されたＣＡＭ１０２ａ，１０２ｂと、データ入力部１０１を介して入力された検索キーに基づいてＣＡＭ１０２ａ，１０２ｂから抽出されたアドレスを比較するアドレス一致比較部１０５と、ＣＡＭ１０２ａ，１０２ｂから抽出されたアドレスを保持するアドレス保持部１０３とから構成されている。
【０００５】
以下に、上記のように構成された情報検索装置における情報検索方法について説明する。
【０００６】
図１７は、図１６に示した情報検索装置における情報検索方法を説明するためのタイミングチャートである。また、図１８は、図１６に示した情報検索装置において入力された検索キーに基づいて検索結果格納メモリ１０４のアドレスを検索する処理を説明するための図である。なお、本従来例においては、ＣＡＭ１０２ａ，１０２ｂの１ワ−ド当りのビット幅をそれぞれｍ，ｎとし、デ−タ入力部１０１に入力される検索キーのビット幅をＮ（Ｎ＝ｍ＋ｎ）とする。
【０００７】
デ−タ入力部１０１を介してＮビットの検索キーが入力されると、まず、入力されたＮビットの検索キーが、ｍ，ｎビットに分割され、前半部のｍビットの検索キーがＣＡＭ１０２ａに入力され、後半部のｎビットの検索キーがＣＡＭ１０２ｂに入力される。ここで、本従来例においては、ＣＡＭ１０２ａ，１０２ｂに対する情報の登録は、検索キーの前半部及び後半部に対応した情報をそれぞれＣＡＭ１０２ａ，１０２ｂの同一のアドレスに登録することが前提条件となっている。
【０００８】
データ入力部１０１を介して入力される検索キーを、例えば“ＣＣａａ”（“ＣＣ”が検索キーの前半部、“ａａ”が検索キーの後半部）とすると、まず、ＣＡＭ１０２ａに対して検索キー“ＣＣ”で検索を行う。
【０００９】
すると、図１８に示すように、アドレス“ｋ＋１”において検索キー“ＣＣ”がヒットする。
【００１０】
次に、ＣＡＭ１０２ａにてヒットしたアドレス“ｋ＋１”がアドレス一致比較部１０５及びＣＡＭ１０２ｂに通知され、ＣＡＭ１０２ｂに対して検索キー“ａａ”でアドレス“ｋ＋１”以降を検索する。
【００１１】
すると、図１８に示すように、アドレス“ｋ＋２”において検索キー“ａａ”がヒットする。
【００１２】
ＣＡＭ１０２ｂにてヒットしたアドレス“ｋ＋２”はＣＡＭ１０２ａ及びアドレス一致比較部１０５に通知され、アドレス一致比較部１０５において、ＣＡＭ１０２ａにてヒットしたアドレス“ｋ＋１”とＣＡＭ１０２ｂにてヒットしたアドレス“ｋ＋２”とが比較される。
【００１３】
ＣＡＭ１０２ａにてヒットしたアドレス“ｋ＋１”とＣＡＭ１０２ｂにてヒットしたアドレス“ｋ＋２”とは一致していないため、ＣＡＭ１０２ａに対してＣＡＭ１０２ｂから通知されたアドレス“ｋ＋２”以降において検索キー“ＣＣ”で検索を行う。
【００１４】
すると、図１８に示すように、アドレス“ｋ＋３”において検索キー“ＣＣ”がヒットする。
【００１５】
次に、ＣＡＭ１０２ａにてヒットしたアドレス“ｋ＋３”がアドレス一致比較部１０５及びＣＡＭ１０２ｂに通知され、ＣＡＭ１０２ｂに対して検索キー“ａａ”でアドレス“ｋ＋３”以降を検索する。
【００１６】
すると、図１８に示すように、アドレス“ｋ＋４”において検索キー“ａａ”がヒットする。
【００１７】
ＣＡＭ１０２ｂにてヒットしたアドレス“ｋ＋４”はＣＡＭ１０２ａ及びアドレス一致比較部１０５に通知され、アドレス一致比較部１０５において、ＣＡＭ１０２ａにてヒットしたアドレス“ｋ＋３”とＣＡＭ１０２ｂにてヒットしたアドレス“ｋ＋４”とが比較される。
【００１８】
ＣＡＭ１０２ａにてヒットしたアドレス“ｋ＋３”とＣＡＭ１０２ｂにてヒットしたアドレス“ｋ＋４”とは一致していないため、ＣＡＭ１０２ａに対してＣＡＭ１０２ｂから通知されたアドレス“ｋ＋４”以降において検索キー“ＣＣ”で検索を行う。
【００１９】
すると、図１８に示すように、アドレス“ｋ＋５”において検索キー“ＣＣ”がヒットする。
【００２０】
次に、ＣＡＭ１０２ａにてヒットしたアドレス“ｋ＋５”がアドレス一致比較部１０５及びＣＡＭ１０２ｂに通知され、ＣＡＭ１０２ｂに対して検索キー“ａａ”でアドレス“ｋ＋５”以降を検索する。
【００２１】
すると、図１８に示すように、アドレス“ｋ＋５”において検索キー“ａａ”がヒットする。
【００２２】
ＣＡＭ１０２ｂにてヒットしたアドレス“ｋ＋５”はＣＡＭ１０２ａ及びアドレス一致比較部１０５に通知され、アドレス一致比較部１０５において、ＣＡＭ１０２ａにてヒットしたアドレス“ｋ＋５”とＣＡＭ１０２ｂにてヒットしたアドレス“ｋ＋５”とが比較される。
【００２３】
ＣＡＭ１０２ａにてヒットしたアドレス“ｋ＋５”とＣＡＭ１０２ｂにてヒットしたアドレス“ｋ＋５”とは一致しているため、このアドレス“ｋ＋５”を用いて検索結果格納メモリ１０４にアクセスし、所望のコンテンツ情報を得る。
【００２４】
ここで、複数のＣＡＭを用いてコンテンツ情報を検索する場合、通常のＣＡＭではアドレスの０番地から検索が行われるため、同じ内容の情報が２つ以上のアドレスに登録されていると、若番のアドレスだけがＣＡＭの出力となってしまい、本来出力されるべき老番のアドレスが出力されなくなってしまうが、本従来例においては、ＣＡＭ１０２ａにて検索キーにヒットしたアドレスがＣＡＭ１０２ｂに通知されてＣＡＭ１０２ｂに対する検索開始アドレスとされ、また、ＣＡＭ１０２ｂにて検索キーにヒットしたアドレスがＣＡＭ１０２ａに通知されてＣＡＭ１０２ａに対する検索開始アドレスとされるので、本来出力されるべきアドレスが出力されるようになる。
【００２５】
【発明が解決しようとする課題】
しかしながら、上述したような従来の情報検索装置においては、一方のＣＡＭに対する検索を行うためには他方のＣＡＭでの検索結果が必要となるため、所望のコンテンツ情報が格納された検索結果格納メモリにアクセスするためのアドレスを得るまでに最短でも２回の検索を行わなければならない。このため、１回目の検索開始から検索結果格納メモリにアクセスするためのアドレスを得るまでの処理遅延が大きくなってしまうという問題点がある。さらに、図１８に示したような検索においては、検索結果格納メモリのアドレスを得るまでに６回の検索を行わなければならず、検索処理が完結するまでの時間が一定ではなく、処理遅延を見積もることができないという問題点がある。
【００２６】
また、分割前の検索キーを用いて検索されるコンテンツ情報を指定するための情報を２つのＣＡＭの同一のアドレスに登録する必要があるため、１つのＣＡＭにおいて、登録する情報が同一のものにおいても、他方のＣＡＭに登録される情報によって該情報を別アドレスにそれぞれ登録しなければならず、ＣＡＭのメモリ資源を無駄に使用してしまうという問題点がある。
【００２７】
本発明は、上述したような従来の技術が有する問題点に鑑みてなされたものであって、ＣＡＭが持つ１ワード当たりのビット幅制限を超えた多ビット検索を行うことを可能としながらも、その検索時間を一定に、かつ短縮することができるとともに、ＣＡＭのメモリ資源を有効に活用することができる情報検索装置を提供することを目的とする。
【００２８】
【課題を解決するための手段】
上記目的を達成するために本発明は、
コンテンツ情報が格納された第１の記憶手段と、前記第１の記憶手段に格納されたコンテンツ情報を指定するための第１の情報が格納された複数の第２の記憶手段とを少なくとも有し、前記コンテンツ情報を検索するために与えられた検索キーが前記第２の記憶手段の数分に分割され、分割された検索キーのそれぞれが前記第２の記憶手段に格納された前記第１の情報と比較され、両者が一致した場合に該第１の情報が格納された前記第２の記憶手段内のアドレスを用いて前記第１の記憶手段から前記コンテンツ情報が検索される情報検索装置において、
前記第１の記憶手段内のアドレスを指定するための第２の情報が格納された第３の記憶手段と、
前記検索キーと一致する第１の情報が格納された複数の第２の記憶手段内のアドレスを用いて、前記第３の記憶手段から前記分割された検索キー毎に前記第２の情報を検索する制御手段と、
前記分割された検索キー毎に検索された前記第２の情報を加算する加算手段と、
前記加算手段における加算結果を用いて前記第１の記憶手段から前記コンテンツ情報を検索する検索結果送受信手段とを有し、
前記第１の記憶手段は、前記検索キーによって指定された前記第３の記憶手段内のアドレスに格納された前記第２の情報が加算された場合に該加算結果によって指定されるアドレスに前記検索キーによって検索されるべきコンテンツ情報を格納していることを特徴とする。
【００２９】
また、コンテンツ情報が格納された第１の記憶手段と、前記第１の記憶手段に格納されたコンテンツ情報を指定するための第１の情報が格納された第２の記憶手段とを少なくとも有し、前記コンテンツ情報を検索するために与えられた検索キーが分割され、分割された検索キーのそれぞれが前記第２の記憶手段に格納された前記第１の情報と比較され、両者が一致した場合に該第１の情報が格納された前記第２の記憶手段内のアドレスを用いて前記第１の記憶手段から前記コンテンツ情報が検索される情報検索装置において、
前記第１の記憶手段内のアドレスを指定するための第２の情報が格納された第３の記憶手段と、
前記検索キーと一致する第１の情報が格納された前記第２の記憶手段内のアドレスを用いて、前記第３の記憶手段から前記分割された検索キー毎に前記第２の情報を検索する制御手段と、
前記分割された検索キー毎に検索された前記第２の情報を加算する加算手段と、
前記加算手段における加算結果を用いて前記第１の記憶手段から前記コンテンツ情報を検索する検索結果送受信手段とを有し、
前記第１の記憶手段は、前記検索キーによって指定された前記第３の記憶手段内のアドレスに格納された前記第２の情報が加算された場合に該加算結果によって指定されるアドレスに前記検索キーによって検索されるべきコンテンツ情報を格納していることを特徴とする。
【００３０】
また、コンテンツ情報が格納された第１の記憶手段と、前記第１の記憶手段に格納されたコンテンツ情報を指定するための第１の情報が格納された第２の記憶手段とを少なくとも有し、前記コンテンツ情報を検索するために与えられた検索キーが分割され、分割された検索キーのそれぞれが前記第２の記憶手段に格納された前記第１の情報と比較され、両者が一致した場合に該第１の情報が格納された前記第２の記憶手段内のアドレスを用いて前記第１の記憶手段から前記コンテンツ情報が検索される情報検索装置において、
前記第１の記憶手段は、前記コンテンツ情報が格納されたアドレスを指定するための第２の情報が格納された領域を具備し、
前記検索キーと一致する第１の情報が格納された前記第２の記憶手段内のアドレスを用いて、前記第１の記憶手段から前記分割された検索キー毎に前記第２の情報を検索する制御手段と、
前記分割された検索キー毎に検索された前記第２の情報を加算する加算手段と、
前記加算手段における加算結果を用いて前記第１の記憶手段から前記コンテンツ情報を検索する検索結果送受信手段とを有し、
前記第１の記憶手段は、前記検索キーによって指定された当該第１の記憶手段内のアドレスに格納された前記第２の情報が加算された場合に該加算結果によって指定されるアドレスに前記検索キーによって検索されるべきコンテンツ情報を格納していることを特徴とする。
【００３１】
また、コンテンツ情報が格納された第１の記憶手段と、前記第１の記憶手段に格納されたコンテンツ情報を指定するための第１の情報が格納された第２の記憶手段とを少なくとも有し、前記コンテンツ情報を検索するために与えられた検索キーが分割され、分割された検索キーによって指定される前記第２の記憶手段内のアドレスを用いて前記第１の記憶手段から前記コンテンツ情報が検索される情報検索装置において、
前記第１の記憶手段内のアドレスを指定するための第２の情報が格納された第３の記憶手段と、
前記検索キーと一致する第１の情報が格納された前記第２の記憶手段内のアドレスを用いて、前記第３の記憶手段から前記第２の情報を検索する制御手段と、前記第３の記憶手段から検索された前記第２の情報と前記分割された検索キーのうち前記第２の情報の検索に用いられない検索キーとを加算する加算手段と、前記加算手段における加算結果を用いて前記第１の記憶手段から前記コンテンツ情報を検索する検索結果送受信手段とを有し、
前記第１の記憶手段は、前記検索キーによって指定された前記第３の記憶手段内のアドレスに格納された前記第２の情報と前記分割された検索キーの前記第２の情報の検索に用いられない検索キーとが加算された場合に該加算結果によって指定されるアドレスに前記検索キーによって検索されるべきコンテンツ情報を格納していることを特徴とする。
【００３２】
また、コンテンツ情報が格納された第１の記憶手段と、前記第１の記憶手段に格納されたコンテンツ情報を指定するための第１の情報が格納された第２の記憶手段とを少なくとも有し、前記コンテンツ情報を検索するために与えられた検索キーが分割され、分割された検索キーによって指定される前記第２の記憶手段内のアドレスを用いて前記第１の記憶手段から前記コンテンツ情報が検索される情報検索装置において、
前記第１の記憶手段は、前記コンテンツ情報が格納されたアドレスを指定するための第２の情報が格納された領域を具備し、
前記検索キーと一致する第１の情報が格納された前記第２の記憶手段内のアドレスを用いて、前記第１の記憶手段から前記第２の情報を検索する制御手段と、前記第１の記憶手段から検索された前記第２の情報と前記分割された検索キーのうち前記第２の情報の検索に用いられない検索キーとを加算する加算手段と、前記加算手段における加算結果を用いて前記第１の記憶手段から前記コンテンツ情報を検索する検索結果送受信手段とを有し、
前記第１の記憶手段は、前記検索キーによって指定された当該第１の記憶手段内のアドレスに格納された前記第２の情報と前記分割された検索キーの前記第２の情報の検索に用いられない検索キーとが加算された場合に該加算結果によって指定されるアドレスに前記検索キーによって検索されるべきコンテンツ情報を格納していることを特徴とする。
【００３３】
また、コンテンツ情報が格納された第１の記憶手段と、前記第１の記憶手段に格納されたコンテンツ情報を指定するための第１の情報が格納された第２の記憶手段とを少なくとも有し、前記コンテンツ情報を検索するために与えられた検索キーが分割され、分割された検索キーのそれぞれが前記第２の記憶手段に格納された前記第１の情報と比較され、両者が一致した場合に該第１の情報が格納された前記第２の記憶手段内のアドレスを用いて前記第１の記憶手段から前記コンテンツ情報が検索される情報検索装置において、
前記検索キーと一致する第１の情報が格納された前記第２の記憶手段内のアドレスを加算する加算手段と、
前記加算手段における加算結果を用いて前記第１の記憶手段から前記コンテンツ情報を検索する検索結果送受信手段とを有することを特徴とする。
【００３４】
（作用）
上記のように構成された本発明においては、第１の記憶手段に格納されたコンテンツ情報を検索する場合、該コンテンツ情報を検索するための検索キーを入力すると、入力された検索キーが複数に分割され、コンテンツ情報を指定するための第１の情報が格納された第２の記憶手段において、分割された検索キーと第１の情報とが比較される。分割された検索キーと第１の情報とが一致した場合、該第１の情報が格納された第２の記憶手段内のアドレスを用いて、第１の記憶手段内のアドレスを指定するための第２の情報が格納された第３の記憶手段にアクセスが行われる。その後、第３の記憶手段に格納された第２の情報が分割された検索キー毎に抽出されてこれらが加算され、この加算結果をアドレスとして第１の記憶手段にアクセスが行われ、それにより、所望のコンテンツ情報が第１の記憶手段から抽出される。
【００３５】
これにより、第１の記憶手段に格納されたコンテンツ情報を検索するために与えられる検索キーのビット幅が第２の記憶手段の１ワ−ド当りのビット幅を超える多ビット検索において、分割された検索キー毎に独立して検索が行われることになり、処理遅延の短縮、処理遅延の一定化及びＣＡＭメモリ資源の有効活用が図られる。
【００３６】
【発明の実施の形態】
以下に、本発明の実施の形態について図面を参照して説明する。
【００３７】
図１は、本発明の情報検索装置の実施の一形態を示すブロック図である。
【００３８】
本形態は図１に示すように、検索キーが入力されるデータ入力部１と、コンテンツ情報が格納された検索結果格納メモリ４と、検索結果格納メモリ４に格納されたコンテンツ情報を指定するための情報が格納されたＣＡＭ２ａ，２ｂと、データ入力部１を介して入力された検索キーによってＣＡＭ２ａ，２ｂから検索された情報のアドレスに基づいて、検索結果格納メモリ４にアクセスするためのアドレスを決定するアドレス決定部３とから構成されている。
【００３９】
以下に、上記のように構成された情報検索装置における情報検索方法について説明する。
【００４０】
図２は、図１に示した情報検索装置における情報検索方法を説明するためのタイミングチャートである。なお、本形態においては、ＣＡＭ２ａ，２ｂの１ワ−ド当りのビット幅をそれぞれｍ，ｎとし、デ−タ入力部１に入力される検索キーのビット幅をＮ（Ｎ＝ｍ＋ｎ）とする。
【００４１】
デ−タ入力部１を介してＮビットの検索キーが入力されると、まず、入力されたＮビットの検索キーが、ｍ，ｎビットに分割され、前半部のｍビットの検索キーがＣＡＭ２ａに入力され、後半部のｎビットの検索キーがＣＡＭ２ｂに入力される。
【００４２】
ここで、本形態においては、データ入力部１を介して入力される検索キーに対して一対一対応でＣＡＭ２ａ，２ｂに情報が登録されておらず、ｍ，ｎビットに分割された後の検索キーのそれぞれについて一対一対応でＣＡＭ２ａ，２ｂに情報が登録されている。そのため、検索キーの前半部のｍビットの検索キーでＣＡＭ２ａに対する情報の検索が行われ、また、検索キーの後半部のｎビットの検索キーでＣＡＭ２ｂに対する情報の検索が行われ、これらは互いに独立して行われることになる。
【００４３】
ＣＡＭ２ａにて検索された情報のアドレスはベースアドレスとしてアドレス決定部３に通知され、また、ＣＡＭ２ｂにて検索された情報のアドレスはオフセットアドレスとしてアドレス決定部３に通知され、アドレス決定部３において、ＣＡＭ２ａから通知されたベースアドレスとＣＡＭ２ｂから通知されたオフセットアドレスとに基づいて、検索結果格納メモリ４にアクセスするためのアドレスが決定される。
【００４４】
その後、検索結果格納メモリ４に対して、アドレス決定部３にて決定したアドレスを用いてアクセスし、それにより、データ入力部１を介して入力した検索キーにて検索されたコンテンツ情報を得る。
【００４５】
上述したように本形態においては、従来の情報検索装置のように分割前の検索キーについて一対一対応でＣＡＭに情報を登録するのではなく、分割後の検索キーについて一対一対応でＣＡＭの情報を登録し、２つのＣＡＭの検索結果を、検索結果格納メモリにアクセスするためのベ−スアドレス、オフセットアドレスといったポインタ情報と考えることにより、２つのＣＡＭでの検索処理を互いに独立して行うことができる。そのため、一方のＣＡＭでの検索結果を待つことなく他方のＣＡＭの検索処理を実行することができ、検索開始から検索結果格納メモリにアクセスするためのアドレスを得るまでの処理遅延を短縮することができ、かつ必ず一定時間で検索が完結し、処理遅延を一定に保つことができる。例えば、パイプライン検索が可能なＣＡＭを用いれば１回目と２回目の検索を連続で実行することが可能となり、スル−プットを落とさずに検索結果を得ることが可能となる。
【００４６】
また、従来の情報検索装置のように分割前の検索キーについて一対一対応でＣＡＭに情報が登録されているのではなく、分割後の検索キーについて一対一対応でＣＡＭに情報が登録されているので、ＣＡＭメモリ資源を有効に活用することができる。
【００４７】
なお、本形態においては、データ入力部１を介して入力される検索キーを２つに分割した場合を例に挙げて説明したが、本発明は、これに限らず、分割数を３あるいは４とした場合においても、３回目あるいは４回目の検索の結果解決されるベ−スアドレス、オフセットアドレスといったポインタ情報を上手に管理すれば、更なる多ビット検索においても検索が可能となる。
【００４８】
（第１の実施の形態）
図３は、本発明の情報検索装置の第１の実施の形態を示す図であり、図１に示したものをさらに具体化したものである。
【００４９】
本形態は図３に示すように、コンテンツ情報が格納された第１の記憶手段である検索結果格納メモリ３０ｂと、検索結果格納メモリ３０ｂ内のアドレスを指定するための第２の情報であるポインタ情報が格納された第３の記憶手段である検索結果格納メモリ３０ａと、検索結果格納メモリ３０ｂに格納されたコンテンツ情報を指定するための第１の情報が格納された第２の記憶手段であるＣＡＭ２０ａ，２０ｂと、検索結果格納メモリ３０ｂに格納されたコンテンツ情報を検索するための情報が入力され、該情報に基づいてＣＡＭ２０ａ，２０ｂに対する検索を行い、該検索結果に基づいて検索結果格納メモリ３０ａからポインタ情報を抽出し、該ポインタ情報によって検索結果格納メモリ３０ｂにアクセスすることにより検索結果格納メモリ３０ｂから所望のコンテンツ情報を抽出して出力する検索コントローラー１０とから構成されている。また、検索コントローラ１０は、入力された情報から検索キーを抽出する検索キー抽出回路１１と、検索キー抽出回路１１にて抽出された検索キーをビット列方向に前半部と後半部との２つに分割する検索キー分割回路１２と、検索キー分割回路１２にて分割された検索キーをそれぞれ保持する検索キー保持回路１３ａ，１３ｂと、検索キー保持回路１３ａ，１３ｂに保持されている検索キーによってＣＡＭ２０ａ，２０ｂに対する検索を行い、ＣＡＭ２０ａ，２０ｂから検索されたアドレスを用いて検索結果格納メモリ３０ａからポインタ情報を抽出する制御手段であるＣＡＭコントローラ１４ａ，１４ｂと、検索結果格納メモリ３０ａから抽出されたポインタ情報を加算する加算器１５と、加算器１５にて加算されたポインタ情報をアドレスとして検索結果格納メモリ３０ｂにアクセスすることにより所望のコンテンツ情報を検索結果格納メモリ３０ｂから抽出して外部に出力する検索結果送受信回路１６とから構成されている。なお、図１に示したデータ入力部１及びアドレス決定部３が検索コントローラ１０に相当し、図１に示したＣＡＭ２ａ，２ｂがＣＡＭ２０ａ，２０ｂにそれぞれ相当し、図１に示した検索結果格納メモリ４が検索結果格納メモリ３０ｂに相当する。
【００５０】
以下に、上記のように構成された情報検索装置における情報検索方法について説明する。
【００５１】
図４は、図３に示した情報検索装置に入力される検索キーの一例を示す図であり、図５は、図３に示した情報検索装置における情報検索方法を説明するためのＣＡＭ２０ａ，２０ｂ及び検索結果格納メモリ３０ａ，３０ｂのメモリ構成例を示す図である。
【００５２】
検索コントローラ１０に外部から情報が入力されると、まず、検索キー抽出回路１１において、入力された情報から検索キーが抽出される。ここで、本形態において検索コントローラ１０に入力され、検索キー抽出回路１１にて抽出される検索キーは図４に示すようにＮビット幅とする。
【００５３】
次に、検索キー分割回路１２において、検索キー抽出回路１１にて抽出された検索キーが所定の数に分割される。本形態においては、検索キー抽出回路１１にて抽出されたＮビット幅の検索キーがｍビットとｎビット（Ｎ＝ｍ＋ｎ）とに２つに分割されるものとする。
【００５４】
検索キー分割回路１２にて分割された検索キーのうちｍビットの検索キーは検索キー保持回路１３ａにて保持され、ｎビットの検索キーは検索キー保持回路１３ｂにて保持される。例えば、検索キー抽出回路１１にて抽出された検索キーが図４に示す検索キー１である場合は、検索キー１のｍビットからなる検索キー“ＡＡ”が検索キー保持回路１２ａに保持され、また、検索キー１のｎビットからなる検索キー“ａａ”が検索キー保持回路１２ｂに保持される。
【００５５】
その後、ｍビットからなる検索キー“ＡＡ”を用いてＣＡＭ２０ａに対する検索が行われ、また、ｎビットからなる検索キー“ａａ”を用いてＣＡＭ２０ｂに対する検索が行われることになるが、以下の説明においては、便宜上、検索キー“ＡＡ”を用いた検索を１回目の検索、検索キー“ａａ”を用いた検索を２回目の検索と称し、図３及び図５において、太線矢印は１回目の検索処理を示し、破線矢印は２回目の検索処理を示す。
【００５６】
ＣＡＭ２０ａ，２０ｂには、検索結果格納メモリ３０ｂに格納されたコンテンツ情報を指定するための情報が格納されている。例えば、図５に示すように、ＣＡＭ２０ａには、検索結果格納メモリ３０ｂに格納されたコンテンツ情報を指定するための情報“ＡＡ”，“ＢＢ”，“ＣＣ”，…がそれぞれ格納されており、また、ＣＡＭ２０ｂには、検索結果格納メモリ３０ｂに格納されたコンテンツ情報を指定するための情報“ａａ”，“ｂｂ”，“ｃｃ”，…がそれぞれ格納されている。
【００５７】
１回目の検索として、ＣＡＭコントローラ１４ａにおいて、検索キー保持回路１３ａに保持されている検索キーを用いてＣＡＭ２０ａに対する検索が行われる。ＣＡＭ２０ａは、ＣＡＭ２０ａに格納されている情報と与えられた検索キーとを比較して、一致した情報が格納されているアドレスを出力する。例えば、図５において、検索キー保持回路１３ａに保持され、検索に用いられる検索キーとして検索キー“ＡＡ”がＣＡＭ２０ａに与えられた場合、ＣＡＭ２０ａ内の情報“ＡＡ”が格納されたアドレス“ａ１”がＣＡＭコントローラ１４ａによって読み出される。
【００５８】
次に、検索結果格納メモリ３０ａに格納されたポインタ情報のうちＣＡＭコントローラ１４ａによって読み出されたアドレス“ａ１”に格納されているポインタ情報“Ａ’”が、検索結果格納メモリ３０ｂから所望のコンテンツ情報を読み出すためのベースアドレスとして読み出される。
【００５９】
また、２回目の検索として、ＣＡＭコントローラ１４ｂにおいて、検索キー保持回路１３ｂに保持されている検索キーを用いてＣＡＭ２０ｂに対する検索が行われる。ＣＡＭ２０ｂは、ＣＡＭ２０ｂに格納されている情報と与えられた検索キーとを比較して、一致した情報が格納されているアドレスを出力する。例えば、図５において、検索キー保持回路１３ｂに保持され、検索に用いられる検索キーとして検索キー“ａａ”がＣＡＭ２０ｂに与えられた場合、ＣＡＭ２０ｂ内の情報“ａａ”が格納されたアドレス“ａ２”がＣＡＭコントローラ１４ｂによって読み出される。
【００６０】
次に、ＣＡＭ２０ｂから読み出されたアドレス“ａ２”に、検索結果格納メモリ３０ａにおけるベースアドレス領域分の“γ”が加算され、検索結果格納メモリ３０ａに格納されたポインタ情報のうちＣＡＭコントローラ１４ｂによって読み出されたアドレス“ａ２”に“γ”が加算された“ａ２＋γ”に格納されているポインタ情報“ａ’”が、検索結果格納メモリ３０ｂから所望のコンテンツ情報を読み出すためのオフセットアドレスとして読み出される。
【００６１】
次に、加算器１５において、検索結果格納メモリ３０ａから読み出されたベースアドレス“Ａ’”とオフセットアドレス“ａ’”とが加算される。
【００６２】
その後、検索結果送受信回路１６において、検索結果格納メモリ３０ｂに格納されているコンテンツ情報の中から、加算器１５にて加算されたアドレス“Ａ’＋ａ’”に格納されたコンテンツ情報が読み出され、出力される。
【００６３】
このように、検索結果格納メモリ３０ｂには、ＣＡＭ２０ａ，２０ｂに入力された検索キーによって指定された検索結果格納メモリ３０ａ内のアドレスに格納されたポインタ情報が加算された場合に、その加算結果によって決定するアドレスに、ＣＡＭ２０ａ，２０ｂに入力された検索キーによって検索されるべきコンテンツ情報が格納されている。
【００６４】
（第２の実施の形態）
図６は、本発明の情報検索装置の第２の実施の形態を示すブロック図である。
【００６５】
本形態は図６に示すように、図３に示したものに対して、検索結果格納メモリ３０ｂに格納された情報を指定するための情報が格納されたＣＡＭ２０を１つとし、それに伴って、ＣＡＭコントローラ１４も１つとした点のみが異なるものであり、その他の構成については、図３に示したものと同様である。
【００６６】
以下に、上記のように構成された情報検索装置における情報検索方法について説明する。
【００６７】
図７は、図６に示した情報検索装置における情報検索方法を説明するためのＣＡＭ２０及び検索結果格納メモリ３０ａ，３０ｂのメモリ構成例を示す図である。
【００６８】
検索コントローラ１１０に外部から情報が入力されると、まず、検索キー抽出回路１１において、入力された情報から検索キーが抽出される。ここで、本形態において検索コントローラ１０に入力され、検索キー抽出回路１１にて抽出される検索キーは図４に示すようにＮビット幅とする。
【００６９】
次に、検索キー分割回路１２において、検索キー抽出回路１１にて抽出された検索キーが所定の数に分割される。本形態においては、検索キー抽出回路１１にて抽出されたＮビット幅の検索キーがｍビットとｎビット（Ｎ＝ｍ＋ｎ）とに２つに分割されるものとする。なお、本形態においては、分割される２つの検索キーのビット幅は等しいものとする（ｍ＝ｎ）。
【００７０】
検索キー分割回路１２にて分割された検索キーのうちｍビットの検索キーは検索キー保持回路１３ａにて保持され、ｎビットの検索キーは検索キー保持回路１３ｂにて保持される。
【００７１】
その後、ｍビットからなる検索キー“ＡＡ”を用いてＣＡＭ２０に対する検索が行われ、また、ｎビットからなる検索キー“ａａ”を用いてＣＡＭ２０に対する検索が行われることになるが、以下の説明においては、便宜上、検索キー“ＡＡ”を用いた検索を１回目の検索、検索キー“ａａ”を用いた検索を２回目の検索と称し、図６及び図７において、太線矢印は１回目の検索処理を示し、破線矢印は２回目の検索処理を示す。
【００７２】
ＣＡＭ２０には、検索結果格納メモリ３０ｂに格納されたコンテンツ情報を指定するための情報が格納されている。例えば、図７に示すように、ＣＡＭ２０には、検索結果格納メモリ３０ｂに格納されたコンテンツ情報を指定するための情報“ＡＡ”，“ａａ”，“ｂｂ”，…，“ｆｆ”，“ＢＢ”，“ＣＣ”，“ｇｇ”，…が格納されている。
【００７３】
１回目の検索として、ＣＡＭコントローラ１４において、検索キー保持回路１３ａに保持されている検索キーを用いてＣＡＭ２０に対する検索が行われる。ＣＡＭ２０は、ＣＡＭ２０に格納されている情報と与えられた検索キーとを比較して、一致した情報が格納されているアドレスを出力する。例えば、図７において、検索キー保持回路１３ａに保持され、検索に用いられる検索キーとして検索キー“ＡＡ”がＣＡＭ２０に与えられた場合、ＣＡＭ２０内の情報“ＡＡ”が格納されたアドレス“ａ”がＣＡＭコントローラ１４によって読み出される。
【００７４】
次に、検索結果格納メモリ３０ａに格納されたポインタ情報のうちＣＡＭコントローラ１４によって読み出されたアドレス“ａ”に格納されているポインタ情報“Ａ’”が、検索結果格納メモリ３０ｂから所望のコンテンツ情報を読み出すためのベースアドレスとして読み出される。
【００７５】
また、２回目の検索として、ＣＡＭコントローラ１４において、検索キー保持回路１３ｂに保持されている検索キーを用いてＣＡＭ２０に対する検索が行われる。例えば、図７において、検索キー保持回路１３ｂに保持され、検索に用いられる検索キーとして検索キー“ａａ”がＣＡＭ２０に与えられた場合、ＣＡＭ２０内の情報“ａａ”が格納されたアドレス“ｂ”がＣＡＭコントローラ１４によって読み出される。
【００７６】
次に、検索結果格納メモリ３０ａに格納されたポインタ情報のうちＣＡＭコントローラ１４によって読み出されたアドレス“ｂ”に格納されているポインタ情報“ａ’”が、検索結果格納メモリ３０ｂから所望のコンテンツ情報を読み出すためのオフセットアドレスとして読み出される。
【００７７】
次に、加算器１５において、検索結果格納メモリ３０ａから読み出されたベースアドレス“Ａ’”とオフセットアドレス“ａ’”とが加算される。
【００７８】
その後、検索結果送受信回路１６において、検索結果格納メモリ３０ｂに格納されているコンテンツ情報の中から、加算器１５にて加算されたアドレス“Ａ’＋ａ’”に格納されたコンテンツ情報が読み出され、出力される。
【００７９】
このように本形態においては、図３に示したものに対して、検索結果格納メモリ３０ｂに格納された情報を指定するための情報が格納されたＣＡＭ２０を１つとし、それに伴って、ＣＡＭコントローラ１４も１つとしたたため、ＣＡＭ、並びにその制御回路、制御ロジック及びデータバスが共有化され、それにより、回路規模を縮小することができ、コスト低減を図ることができる。
【００８０】
（第３の実施の形態）
図８は、本発明の情報検索装置の第３の実施の形態を示すブロック図である。
【００８１】
本形態は図８に示すように、図６に示したものに対して、コンテンツ情報が格納された検索結果格納メモリとこの検索結果格納メモリ内のアドレスを指定するためのポインタ情報が格納された検索結果格納メモリとを１つの検索結果格納メモリ３０に共有化した点のみが異なるものであり、その他の構成については、図６に示したものと同様である。
【００８２】
以下に、上記のように構成された情報検索装置における情報検索方法について説明する。
【００８３】
図９は、図８に示した情報検索装置における情報検索方法を説明するためのＣＡＭ２０及び検索結果格納メモリ３０のメモリ構成例を示す図である。
【００８４】
検索コントローラ１１０に外部から情報が入力されると、まず、検索キー抽出回路１１において、入力された情報から検索キーが抽出される。ここで、本形態において検索コントローラ１０に入力され、検索キー抽出回路１１にて抽出される検索キーは図４に示すようにＮビット幅とする。
【００８５】
次に、検索キー分割回路１２において、検索キー抽出回路１１にて抽出された検索キーが所定の数に分割される。本形態においては、検索キー抽出回路１１にて抽出されたＮビット幅の検索キーがｍビットとｎビット（Ｎ＝ｍ＋ｎ）とに２つに分割されるものとする。なお、本形態においては、分割される２つの検索キーのビット幅は等しいものとする（ｍ＝ｎ）。
【００８６】
検索キー分割回路１２にて分割された検索キーのうちｍビットの検索キーは検索キー保持回路１３ａにて保持され、ｎビットの検索キーは検索キー保持回路１３ｂにて保持される。
【００８７】
その後、ｍビットからなる検索キー“ＡＡ”を用いてＣＡＭ２０に対する検索が行われ、また、ｎビットからなる検索キー“ａａ”を用いてＣＡＭ２０に対する検索が行われることになるが、以下の説明においては、便宜上、検索キー“ＡＡ”を用いた検索を１回目の検索、検索キー“ａａ”を用いた検索を２回目の検索と称し、図８及び図９において、太線矢印は１回目の検索処理を示し、破線矢印は２回目の検索処理を示す。
【００８８】
ＣＡＭ２０には、検索結果格納メモリ３０に格納されたコンテンツ情報を指定するための情報が格納されている。例えば、図９に示すように、ＣＡＭ２０には、検索結果格納メモリ３０に格納されたコンテンツ情報を指定するための情報“ＡＡ”，“ａａ”，“ｂｂ”，…，“ｆｆ”，“ＢＢ”，“ＣＣ”，“ｇｇ”，…が格納されている。
【００８９】
１回目の検索として、ＣＡＭコントローラ１４において、検索キー保持回路１３ａに保持されている検索キーを用いてＣＡＭ２０に対する検索が行われる。ＣＡＭ２０は、ＣＡＭ２０に格納されている情報と与えられた検索キーとを比較して、一致した情報が格納されているアドレスを出力する。例えば、図９において、検索キー保持回路１３ａに保持され、検索に用いられる検索キーとして検索キー“ＡＡ”がＣＡＭ２０に与えられた場合、ＣＡＭ２０内の情報“ＡＡ”が格納されたアドレス“ａ”がＣＡＭコントローラ１４によって読み出される。
【００９０】
次に、検索結果格納メモリ３０に格納されたポインタ情報のうちＣＡＭコントローラ１４によって読み出されたアドレス“ａ”に格納されているポインタ情報“Ａ’”が、検索結果格納メモリ３０から所望のコンテンツ情報を読み出すためのベースアドレスとして読み出される。
【００９１】
また、２回目の検索として、ＣＡＭコントローラ１４において、検索キー保持回路１３ｂに保持されている検索キーを用いてＣＡＭ２０に対する検索が行われる。例えば、図９において、検索キー保持回路１３ｂに保持され、検索に用いられる検索キーとして検索キー“ａａ”がＣＡＭ２０に与えられた場合、ＣＡＭ２０内の情報“ａａ”が格納されたアドレス“ｂ”がＣＡＭコントローラ１４によって読み出される。
【００９２】
次に、検索結果格納メモリ３０に格納されたポインタ情報のうちＣＡＭコントローラ１４によって読み出されたアドレス“ｂ”に格納されているポインタ情報“ａ’”が、検索結果格納メモリ３０から所望のコンテンツ情報を読み出すためのオフセットアドレスとして読み出される。
【００９３】
次に、加算器１５において、検索結果格納メモリ３０から読み出されたベースアドレス“Ａ’”とオフセットアドレス“ａ’”とが加算される。
【００９４】
その後、検索結果送受信回路１６において、検索結果格納メモリ３０に格納されているコンテンツ情報の中から、加算器１５にて加算されたアドレス“Ａ’＋ａ’”に格納されたコンテンツ情報が読み出され、出力される。
【００９５】
このように本形態においては、図７に示したものに対して、コンテンツ情報が格納された検索結果格納メモリとこの検索結果格納メモリ内のアドレスを指定するためのポインタ情報が格納された検索結果格納メモリとが１つの検索結果格納メモリ３０に共有化されているので、検索結果格納メモリ、並びにその制御回路、制御ロジック及びデータバスが共有化され、それにより、回路規模を縮小することができ、コスト低減を図ることができる。
【００９６】
（第４の実施の形態）
図１０は、本発明の情報検索装置の第４の実施の形態を示すブロック図である。
【００９７】
本形態は図１０に示すように、図６に示したものに対して、検索キー保持回路１３ｂに保持された検索キーを用いてＣＡＭ内の検索を行わず、検索キー保持回路１３ｂに保持された検索キー自体を加算器にてベースアドレスに加算されるオフセットアドレスとして用いる点のみが異なるものであり、その他の構成については、図６に示したものと同様である。
【００９８】
以下に、上記のように構成された情報検索装置における情報検索方法について説明する。
【００９９】
図１１は、図１０に示した情報検索装置における情報検索方法を説明するためのＣＡＭ２２０及び検索結果格納メモリ２３０ａ，２３０ｂのメモリ構成例を示す図である。
【０１００】
検索コントローラ２１０に外部から情報が入力されると、まず、検索キー抽出回路１１において、入力された情報から検索キーが抽出される。ここで、本形態において検索コントローラ１０に入力され、検索キー抽出回路１１にて抽出される検索キーはＮビット幅とする。
【０１０１】
次に、検索キー分割回路１２において、検索キー抽出回路１１にて抽出された検索キーが所定の数に分割される。本形態においては、検索キー抽出回路１１にて抽出されたＮビット幅の検索キーがｍビットとｎビット（Ｎ＝ｍ＋ｎ）とに２つに分割されるものとする。なお、本形態においては、分割される２つの検索キーのビット幅はｍに対してｎが非常に小さなものとする（ｍ≫ｎ）。
【０１０２】
検索キー分割回路１２にて分割された検索キーのうちｍビットの検索キーは検索キー保持回路１３ａにて保持され、ｎビットの検索キーは検索キー保持回路１３ｂにて保持される。
【０１０３】
その後、ｍビットからなる検索キー“ＡＡ”を用いてＣＡＭ２２０に対する検索が行われる。
【０１０４】
ＣＡＭ２２０には、検索結果格納メモリ２３０ｂに格納されたコンテンツ情報を指定するための情報が格納されている。例えば、図１１に示すように、ＣＡＭ２２０には、検索結果格納メモリ２３０ｂに格納されたコンテンツ情報を指定するための情報“ＡＡ”，“ＢＢ”，“ＣＣ”，…，“ＦＦ”，“ＧＧ”，…が格納されている。
【０１０５】
ＣＡＭコントローラ２１４において、検索キー保持回路１３ａに保持されている検索キーを用いてＣＡＭ２２０に対する検索が行われる。ＣＡＭ２２０は、ＣＡＭ２２０に格納されている情報と与えられた検索キーとを比較して、一致した情報が格納されているアドレスを出力する。例えば、図１１において、検索キー保持回路１３ａに保持され、検索に用いられる検索キーとして検索キー“ＡＡ”がＣＡＭ２２０に与えられた場合、ＣＡＭ２２０内の情報“ＡＡ”が格納されたアドレス“ａ”がＣＡＭコントローラ２１４によって読み出される。
【０１０６】
次に、検索結果格納メモリ２３０ａに格納されたポインタ情報のうちＣＡＭコントローラ２１４によって読み出されたアドレス“ａ”に格納されているポインタ情報“Ａ’”が、検索結果格納メモリ２３０ｂから所望のコンテンツ情報を読み出すためのベースアドレスとして読み出される。
【０１０７】
次に、加算器２１５において、検索結果格納メモリ２３０ａから読み出されたベースアドレス“Ａ’”と検索キー保持回路１３ｂに保持されている検索キー“ａａ”とが加算される。
【０１０８】
その後、検索結果送受信回路１６において、検索結果格納メモリ２３０ｂに格納されているコンテンツ情報の中から、加算器２１５にて加算されたアドレス“Ａ’＋ａａ”に格納されたコンテンツ情報が読み出され、出力される。
【０１０９】
このように本形態においては、図３、図６及び図８に示したものに対して、分割された検索キーのうち一方の検索キーをそのままオフセットアドレスとして用いているため、ＣＡＭに対する検索回数を削減することができ、それにより、高速処理が可能となる。
【０１１０】
なお、本形態においては、検索キー保持回路１３ｂに保持されたｎビットの検索キーがそのままオフセットアドレスとして用いられるが、ビット幅ｎが大きすぎると検索結果格納メモリ２３０ｂの実メモリ領域以外のアドレスを参照することになってしまうため、検索キー保持回路１３ｂに保持される検索キーのビット幅ｎはオフセットアドレスとして成り得るサイズに分割する必要がある。
【０１１１】
（第５の実施の形態）
図１２は、本発明の情報検索装置の第５の実施の形態を示すブロック図である。
【０１１２】
本形態は図１２に示すように、図１０に示したものに対して、コンテンツ情報が格納された検索結果格納メモリとこの検索結果格納メモリ内のアドレスを指定するためのポインタ情報が格納された検索結果格納メモリとを１つの検索結果格納メモリ２３０に共有化した点のみが異なるものであり、その他の構成については、図１０に示したものと同様である。
【０１１３】
以下に、上記のように構成された情報検索装置における情報検索方法について説明する。
【０１１４】
図１３は、図１２に示した情報検索装置における情報検索方法を説明するためのＣＡＭ２２０及び検索結果格納メモリ２３０のメモリ構成例を示す図である。
【０１１５】
検索コントローラ２１０に外部から情報が入力されると、まず、検索キー抽出回路１１において、入力された情報から検索キーが抽出される。ここで、本形態において検索コントローラ１０に入力され、検索キー抽出回路１１にて抽出される検索キーはＮビット幅とする。
【０１１６】
次に、検索キー分割回路１２において、検索キー抽出回路１１にて抽出された検索キーが所定の数に分割される。本形態においては、検索キー抽出回路１１にて抽出されたＮビット幅の検索キーがｍビットとｎビット（Ｎ＝ｍ＋ｎ）とに２つに分割されるものとする。なお、本形態においては、分割される２つの検索キーのビット幅はｍに対してｎが非常に小さなものとする（ｍ≫ｎ）。
【０１１７】
検索キー分割回路１２にて分割された検索キーのうちｍビットの検索キーは検索キー保持回路１３ａにて保持され、ｎビットの検索キーは検索キー保持回路１３ｂにて保持される。
【０１１８】
その後、ｍビットからなる検索キー“ＡＡ”を用いてＣＡＭ２２０に対する検索が行われる。
【０１１９】
ＣＡＭ２２０には、検索結果格納メモリ２３０に格納されたコンテンツ情報を指定するための情報が格納されている。例えば、図１３に示すように、ＣＡＭ２２０には、検索結果格納メモリ２３０に格納されたコンテンツ情報を指定するための情報“ＡＡ”，“ＢＢ”，“ＣＣ”，…，“ＦＦ”，“ＧＧ”，…が格納されている。
【０１２０】
ＣＡＭコントローラ２１４において、検索キー保持回路１３ａに保持されている検索キーを用いてＣＡＭ２２０に対する検索が行われる。ＣＡＭ２２０は、ＣＡＭ２２０に格納されている情報と与えられた検索キーとを比較して、一致した情報が格納されているアドレスを出力する。例えば、図１３において、検索キー保持回路１３ａに保持され、検索に用いられる検索キーとして検索キー“ＡＡ”がＣＡＭ２２０に与えられた場合、ＣＡＭ２２０内の情報“ＡＡ”が格納されたアドレス“ａ”がＣＡＭコントローラ２１４によって読み出される。
【０１２１】
次に、検索結果格納メモリ２３０に格納されたポインタ情報のうちＣＡＭコントローラ２１４によって読み出されたアドレス“ａ”に格納されているポインタ情報“Ａ’”が、検索結果格納メモリ２３０から所望のコンテンツ情報を読み出すためのベースアドレスとして読み出される。
【０１２２】
次に、加算器２１５において、検索結果格納メモリ２３０から読み出されたベースアドレス“Ａ’”と検索キー保持回路１３ｂに保持されている検索キー“ａａ”とが加算される。
【０１２３】
その後、検索結果送受信回路１６において、検索結果格納メモリ２３０に格納されているコンテンツ情報の中から、加算器２１５にて加算されたアドレス“Ａ’＋ａａ”に格納されたコンテンツ情報が読み出され、出力される。
【０１２４】
このように本形態においては、図１０に示したものに対して、コンテンツ情報が格納された検索結果格納メモリとこの検索結果格納メモリ内のアドレスを指定するためのポインタ情報が格納された検索結果格納メモリとが１つの検索結果格納メモリ２３０に共有化されているので、検索結果格納メモリ、並びにその制御回路、制御ロジック及びデータバスが共有化され、それにより、高速処理を可能としながら、回路規模を縮小することができ、コスト低減を図ることができる。
【０１２５】
（第６の実施の形態）
図１４は、本発明の情報検索装置の第６の実施の形態を示す図である。
【０１２６】
本形態は図１４に示すように、コンテンツ情報が格納された検索結果格納メモリ３０ｂと、検索結果格納メモリ３０ｂに格納されたコンテンツ情報を指定するための情報が格納されたＣＡＭ２０と、検索結果格納メモリ３０ｂに格納されたコンテンツ情報を検索するための情報が入力され、該情報に基づいてＣＡＭ２０に対する検索を行い、該検索結果によって検索結果格納メモリ３０ｂにアクセスすることにより検索結果格納メモリ３０ｂから所望のコンテンツ情報を抽出して出力する検索コントローラー３１０とから構成されている。また、検索コントローラ３１０は、入力された情報から検索キーを抽出する検索キー抽出回路１１と、検索キー抽出回路１１にて抽出された検索キーをビット列方向に前半部と後半部との２つに分割する検索キー分割回路１２と、検索キー分割回路１２にて分割された検索キーをそれぞれ保持する検索キー保持回路１３ａ，１３ｂと、検索キー保持回路１３ａ，１３ｂに保持されている検索キーによってＣＡＭ２０に対する検索を行うＣＡＭコントローラ３１４と、ＣＡＭ２０から検索されたアドレスを所定のビット分上位にシフトしてベースアドレスのポインタ情報として出力するシフト回路１７と、ＣＡＭ２０から検索されたアドレスのうち所定の下位ビットをオフセットアドレスのポインタ情報として出力するマスク回路１８と、シフト回路１７から出力されたベースアドレスとマスク回路１８から出力されたオフセットアドレスとを加算する加算器３１５と、加算器３１５にて加算されたポインタ情報をアドレスとして検索結果格納メモリ３０ｂにアクセスすることにより所望のコンテンツ情報を検索結果格納メモリ３０ｂから抽出して外部に出力する検索結果送受信回路１６とから構成されている。
【０１２７】
以下に、上記のように構成された情報検索装置における情報検索方法について説明する。
【０１２８】
図１５は、図１４に示した情報検索装置における情報検索方法を説明するためのＣＡＭ２０及び検索結果格納メモリ３０ｂのメモリ構成例を示す図である。
【０１２９】
検索コントローラ３１０に外部から情報が入力されると、まず、検索キー抽出回路１１において、入力された情報から検索キーが抽出される。ここで、本形態において検索コントローラ１０に入力され、検索キー抽出回路１１にて抽出される検索キーはＮビット幅とする。
【０１３０】
次に、検索キー分割回路１２において、検索キー抽出回路１１にて抽出された検索キーが所定の数に分割される。本形態においては、検索キー抽出回路１１にて抽出されたＮビット幅の検索キーがｍビットとｎビット（Ｎ＝ｍ＋ｎ）とに２つに分割されるものとする。なお、本形態においては、分割される２つの検索キーのビット幅は等しいものとする（ｍ＝ｎ）。
【０１３１】
検索キー分割回路１２にて分割された検索キーのうちｍビットの検索キーは検索キー保持回路１３ａにて保持され、ｎビットの検索キーは検索キー保持回路１３ｂにて保持される。
【０１３２】
その後、ｍビットからなる検索キー“ＡＡ”を用いてＣＡＭ２０に対する検索が行われ、また、ｎビットからなる検索キー“ａａ”を用いてＣＡＭ２０に対する検索が行われることになるが、以下の説明においては、便宜上、検索キー“ＡＡ”を用いた検索を１回目の検索、検索キー“ａａ”を用いた検索を２回目の検索と称し、図１４及び図１５において、太線矢印は１回目の検索処理を示し、破線矢印は２回目の検索処理を示す。
【０１３３】
ＣＡＭ２０には、検索結果格納メモリ３０ｂに格納されたコンテンツ情報を指定するための情報が格納されている。例えば、図１５に示すように、ＣＡＭ２０には、検索結果格納メモリ３０ｂに格納されたコンテンツ情報を指定するための情報“ＡＡ”，“ＢＢ”，“ＣＣ”，…，“ＦＦ”，“ａａ”，“ｂｂ”，…がそれぞれ格納されている。
【０１３４】
１回目の検索として、ＣＡＭコントローラ３１４において、検索キー保持回路１３ａに保持されている検索キーを用いてＣＡＭ２０に対する検索が行われる。ＣＡＭ２０は、ＣＡＭ２０に格納されている情報と与えられた検索キーとを比較して、一致した情報が格納されているアドレスを出力する。例えば、図１５において、検索キー保持回路１３ａに保持され、検索に用いられる検索キーとして検索キー“ＡＡ”がＣＡＭ２０に与えられた場合、ＣＡＭ２０内の情報“ＡＡ”が格納されたアドレス“ａ”がＣＡＭコントローラ３１４によって読み出される。
【０１３５】
次に、シフト回路１７において、ＣＡＭ２０から検索されたアドレス“ａ”が所定のビット分上位にシフトされてベースアドレスのポインタ情報“Ａ''”として出力される。
【０１３６】
また、２回目の検索として、ＣＡＭコントローラ３１４において、検索キー保持回路１３ｂに保持されている検索キーを用いてＣＡＭ２０に対する検索が行われる。例えば、図１５において、検索キー保持回路１３ｂに保持され、検索に用いられる検索キーとして検索キー“ａａ”がＣＡＭ２０に与えられた場合、ＣＡＭ２０内の情報“ａａ”が格納されたアドレス“ｇ”がＣＡＭコントローラ３１４によって読み出される。
【０１３７】
次に、マスク回路１８において、ＣＡＭ２０から検索されたアドレス“ｇ”のうち所定の下位ビットがオフセットアドレスのポインタ情報“ａ''”として出力される。例えば、ｐビット幅のアドレスがマスク回路１８に入力された場合、マスク回路１８において、入力されたｐビット幅のデータから任意の下位ｑビットのみが有効として出力される。
【０１３８】
次に、加算器１５において、シフト回路１７から出力されたベースアドレス“Ａ''”とマスク回路１８から出力されたオフセットアドレス“ａ''”とが加算される。
【０１３９】
その後、検索結果送受信回路１６において、検索結果格納メモリ３０ｂに格納されているコンテンツ情報の中から、加算器１５にて加算されたアドレス“Ａ''＋ａ''”に格納されたコンテンツ情報が読み出され、出力される。
【０１４０】
このように本形態においては、コンテンツ情報が格納されたアドレスを指定するためのポインタ情報を格納するための物理メモリを削除することができ、さらに物理メモリには検索対象となるコンテンツ情報のみを格納すればよいので、必要なメモリ容量を低減することができる。
【０１４１】
【効果の説明】
本発明は、以上説明したように構成されているので、以下に記載するような効果を奏する。
【０１４２】
（１）多ビット検索キーを任意のビット幅に分割し、それぞれの検索キーで検索を行い、最終的に分割前の多ビット検索キーから一意的な検索結果を得る構成としたため、ＣＡＭが持つ１ワ−ド当りのビット幅制限を越えた多ビット検索を行うことができる。
【０１４３】
（２）分割した検索キーに対して一対一対応でコンテンツ情報を検索するための第１の情報を第２の記憶手段に格納し、分割した検索キーを用いた検索を互いに独立して行う構成としたため、１つの検索結果を待つことなく、他の検索を行うことができ、検索開始から最終的な検索結果を得るまでの処理遅延を短縮できるとともに一定時間で検索を完結させることができる。
【０１４４】
また、処理動作がよりパイプライン処理に適しているので、パイプライン可能なＣＡＭを使用することで複数の検索を連続して処理することが可能となり、スル−プットを落とすことなく処理を行うことができる。
【０１４５】
（３）分割した検索キーに対して一対一対応でコンテンツ情報を検索するための第１の情報を第２の記憶手段に格納しているため、第２の記憶手段における登録エントリの数を削減することができる。
【０１４６】
例えば、図４に示した２つの検索キー１，３が与えられた場合、検索キー１の１回目の検索キーは“ＡＡ”であり、２回目の検索キーは“ａａ”である。検索キー３の１回目の検索キーは“ＢＢ”であり、２回目の検索キーは“ａａ”である。ここで、従来のものにおいては、分割前の検索キーのそれぞれに対応して、第１の情報を第２の記憶手段となるＣＡＭに登録する必要がある。そのため２回目の検索キーが共通（ここでは“ａａ”）であったとしても、２回目の検索キーのためのエントリを重複してＣＡＭに登録する必要がある。１回目の検索キーの種類数をＰ、２回目の検索キーの種類数をＱとすると、登録される情報数は２×Ｐ（ただし、Ｐ＞Ｑ）となる。それに対して本発明においては、１回目の検索と２回目の検索に依存性が無いため、２回目の検索キーが共通（ここでは“ａａ”）であれば、ＣＡＭには１つの情報を登録すれば良いことになる。登録すべき情報の情報数は、Ｐ＋Ｑとなり、従来のものに比べ、ＣＡＭに登録する情報数を削減することができる。
【０１４７】
（４）第２の記憶手段内を検索した結果を用いて第３の記憶手段内を検索して第２の情報を得て、この第２の情報を用いて第１の記憶手段内からコンテンツ情報を検索するため、第２の記憶手段に格納された第１の情報には依存性が無く、第１の情報の登録順序を考える必要は無い。それにより、第２の記憶手段となるＣＡＭへの第１の情報の登録処理の簡素化を図ることができる。
【０１４８】
（５）上述したように第２の記憶手段に格納する第１の情報数が削減できるため、第２の記憶手段となるＣＡＭのメモリ容量として少容量のものを使用することができ、その結果、コストを低減することができる。
【図面の簡単な説明】
【図１】本発明の情報検索装置の実施の一形態を示すブロック図である。
【図２】図１に示した情報検索装置における情報検索方法を説明するためのタイミングチャートである。
【図３】本発明の情報検索装置の第１の実施の形態を示す図である。
【図４】図３に示した情報検索装置に入力される検索キーの一例を示す図である。
【図５】図３に示した情報検索装置における情報検索方法を説明するためのＣＡＭ及び検索結果格納メモリのメモリ構成例を示す図である。
【図６】本発明の情報検索装置の第２の実施の形態を示すブロック図である。
【図７】図６に示した情報検索装置における情報検索方法を説明するためのＣＡＭ及び検索結果格納メモリのメモリ構成例を示す図である。
【図８】本発明の情報検索装置の第３の実施の形態を示すブロック図である。
【図９】図８に示した情報検索装置における情報検索方法を説明するためのＣＡＭ及び検索結果格納メモリのメモリ構成例を示す図である。
【図１０】本発明の情報検索装置の第４の実施の形態を示すブロック図である。
【図１１】図１０に示した情報検索装置における情報検索方法を説明するためのＣＡＭ及び検索結果格納メモリのメモリ構成例を示す図である。
【図１２】本発明の情報検索装置の第５の実施の形態を示すブロック図である。
【図１３】図１２に示した情報検索装置における情報検索方法を説明するためのＣＡＭ及び検索結果格納メモリのメモリ構成例を示す図である。
【図１４】本発明の情報検索装置の第６の実施の形態を示す図である。
【図１５】図１４に示した情報検索装置における情報検索方法を説明するためのＣＡＭ及び検索結果格納メモリのメモリ構成例を示す図である。
【図１６】従来の情報検索装置の一構成例を示すブロック図である。
【図１７】図１６に示した情報検索装置における情報検索方法を説明するためのタイミングチャートである。
【図１８】図１６に示した情報検索装置において入力された検索キーに基づいて検索結果格納メモリのアドレスを検索する処理を説明するための図である。
【符号の説明】
１    データ入力部
２ａ，２ｂ，２０，２０ａ，２０ｂ，２２０    ＣＡＭ
３    アドレス決定部
４，３０，３０ａ，３０ｂ，２３０ａ，２３０ｂ    検索結果格納メモリ
１０，１１０，２１０，３１０    検索コントローラ
１１    検索キー抽出回路
１２    検索キー分割回路
１３ａ，１３ｂ    検索キー保持回路
１４，１４ａ，１４ｂ，２１４，３１４    ＣＡＭコントローラ
１５，２１５，３１５    加算器
１６    検索結果送受信回路
１７    シフト回路
１８    マスク回路
【図１】
0003644494.tif 000002
【図２】
0003644494.tif 000003
【図３】
0003644494.tif 000004
【図４】
0003644494.tif 000005
【図５】
0003644494.tif 000006
【図６】
0003644494.tif 000007
【図７】
0003644494.tif 000008
【図８】
0003644494.tif 000009
【図９】
0003644494.tif 000010
【図１０】
0003644494.tif 000011
【図１１】
0003644494.tif 000012
【図１２】
0003644494.tif 000013
【図１３】
0003644494.tif 000014
【図１４】
0003644494.tif 000015
【図１５】
0003644494.tif 000016
【図１６】
0003644494.tif 000017
【図１７】
0003644494.tif 000018
【図１８】
0003644494.tif 000019