(57)【要約】【課題】ホストインターフェースの通信速度に制限されることなく、転置ファイルの管理及びブール演算を高速に行うことができるストレージ装置を提供する。【解決手段】コンテンツの検索要求が入力可能なインターフェース１１と、ファイル１２１と、ファイルが含むコンテンツに対応する転置ファイル１２２とを格納する第１のメモリブロック１２と、ファイル検索テーブル１３１を格納する第２のメモリブロック１３と、インターフェース１１と第１のメモリブロック１２と第２のメモリブロック１３の信号送受信を制御するコントローラ１４とを備える。コントローラ１４は、転置ファイルにコンテンツを含むファイルの識別子を格納し、コンテンツの検索により求めたファイルの識別子をファイル検索テーブル１３１に格納し、コンテンツの検索要求に対する検索結果として、テーブル１３１に格納されたファイルの識別子をインターフェース１１から出力する。【選択図】図１
2011215835.tif 000002
【特許請求の範囲】
【請求項１】
コンテンツの検索要求が入力可能なインターフェースと、
ファイルと、前記ファイルが含むコンテンツに対応する転置ファイルとを格納する第１のメモリブロックと、
ファイル検索テーブルを格納する第２のメモリブロックと、
前記インターフェースと前記第１のメモリブロックと前記第２のメモリブロックの相互の信号送受信を制御するコントローラと、
を具備し、前記コントローラは、
前記転置ファイルに前記コンテンツを含む前記ファイルの識別子を格納し、
前記コンテンツの検索により求めた前記ファイルの識別子を前記ファイル検索テーブルに格納し、
前記コンテンツの検索要求に対する検索結果として、前記ファイル検索テーブルに格納された前記ファイルの識別子を前記インターフェースから出力することを特徴とするストレージ装置。
【請求項２】
前記インターフェースは複数のコンテンツの検索結果に対するブール演算の要求を受け取り、前記コントローラは、前記ファイル検索テーブルを用いて前記ブール演算を行い、前記ブール演算の結果を前記インターフェースから出力することを特徴とする請求項１に記載のストレージ装置。
【請求項３】
任意長ビットデータをハッシュ関数によって固定長ビットデータに変換するハッシュ生成器をさらに具備し、
前記ファイルの識別子と前記転置ファイルの識別子の少なくともいずれか１つが、前記ハッシュ生成器によって固定長ビットデータに変換されたものであることを特徴とする請求項１または２に記載のストレージ装置。
【請求項４】
前記インターフェースと前記第１のメモリブロックと前記第２のメモリブロックと前記コントローラとに接続され、前記転置ファイルの識別子と前記転置ファイルの格納位置との組を要素とする転置ファイル割り当てテーブルを格納する第３のメモリブロックをさらに具備し、
前記転置ファイル割り当てテーブルの前記要素の格納位置は、前記要素の前記転置ファイルの識別子が含む情報によって決まることを特徴とする請求項３に記載のストレージ装置。
【請求項５】
前記ファイル検索テーブルは、前記ファイルの識別子とブール演算の結果を格納する変数との組を要素とするテーブルであることを特徴とする請求項３または４に記載のストレージ装置。
【請求項６】
前記ファイル検索テーブルの前記要素の格納位置は、前記要素の前記ファイルの識別子が含む情報によって決まることを特徴とする請求項５に記載のストレージ装置。
【請求項７】
第２のメモリブロックの前記ファイル検索テーブルは、コンテンツ連想メモリ(ＣＡＭ)を含むことを特徴とする請求項３または４に記載のストレージ装置。
【請求項８】
前記コントローラから前記第２のメモリブロックへのアクセス速度は、前記コントローラから第１のメモリブロックへのアクセス速度よりも高速であることを特徴とする請求項１乃至７のいずれかに記載のストレージ装置。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、ホストシステムによりアクセスされるストレージ装置に関し、例えばストレージ装置のアクセス方式およびデータ管理方式に関するものである。
【背景技術】
【０００２】
一般的なホストシステム、例えばコンピュータシステムは、磁気式のハードディスクドライブ（ＨＤＤ）や不揮発性半導体メモリを搭載する固体ドライブ（ＳＳＤ）などの不揮発・大規模なストレージ装置を備える。
【０００３】
ストレージ装置は、例えばインターフェースと、第１のメモリブロックと、第２のメモリブロックと、コントローラからなる（例えば、特許文献１参照）。
【０００４】
第１のメモリブロックはファイルを格納し、第２のメモリブロックは書き込み/読み出し時におけるバッファメモリである。第１のメモリブロックは、第２のメモリブロックよりも、不揮発・大容量であるがアクセス速度が遅い。第２のメモリブロックは、インターフェースの通信速度と、第１のメモリブロックの書き込み/読み出し速度との速度差を補うために使用される。例えば、第１のメモリブロックは不揮発性のFlash memoryアレイであり、第２のメモリブロックは揮発性のＤＲＡＭもしくはＳＲＡＭである。
【０００５】
従来のストレージ装置の問題点は、全文検索機能を自ら持たない点である。全文検索機能とは、コンテンツ検索要求に対して、格納しているファイルのうち、検索対象のコンテンツを含むファイルを探し出して、そのリストを出力する機能である。ここでコンテンツとは、通常、単語のことである。また、さらに高度な機能として、複数のコンテンツの検索結果に対するＡＮＤ、ＯＲ、ＮＯＴを含むブール演算の要求を入力として受け、そのブール演算の結果となるファイルリストを出力する機能を持つことが望ましい。
【０００６】
全文検索機能の実現法の一つに、転置インデックス法がある（例えば、非特許文献１参照）。転置インデックス法では、コンテンツ毎にそのコンテンツを含むファイルのリストを格納する転置ファイルと呼ばれる索引データファイルを予め作成し、ファイルの追加/削除の都度、転置ファイルの内容を更新する。コンテンツ検索要求に対しては、その検索対象のコンテンツに対応する転置ファイルの内容を検索結果として出力すればよい。そのため、全文検索の都度、すべてのファイルの内容を調べる必要がない。
【０００７】
従来、ストレージ装置を使って全文検索機能を実現するには、ストレージ内に格納された転置ファイルの管理や複数のコンテンツの検索結果に対するブール演算を、ホストシステムの中央演算装置（ＣＰＵ）や主記憶装置（ＤＲＡＭ）を使用して実施する必要がある。
【０００８】
しかし、ホストシステムとストレージ装置との通信速度がホストインターフェースの通信速度に制限されるため、転置ファイルの管理やブール演算を高速に行うことができないという問題がある。
【先行技術文献】
【特許文献】
【０００９】
【特許文献１】USP 6,377,500
【非特許文献】
【００１０】
【非特許文献１】J. Zobel, A. Moffat and K. Ramamohanarao, Inverted files versus signature files for text indexing. ACM Transactions on Database Systems (TODS), Volume 23, Issue 4 (December 1998), Pages: 453-490.
【発明の概要】
【発明が解決しようとする課題】
【００１１】
本発明は、ホストインターフェースの通信速度に制限されることなく、転置ファイルの管理及びブール演算を高速に行うことができるストレージ装置を提供する。
【課題を解決するための手段】
【００１２】
本発明の一実施態様のストレージ装置は、コンテンツの検索要求が入力可能なインターフェースと、ファイルと、前記ファイルが含むコンテンツに対応する転置ファイルとを格納する第１のメモリブロックと、ファイル検索テーブルを格納する第２のメモリブロックと、前記インターフェースと前記第１のメモリブロックと前記第２のメモリブロックの相互の信号送受信を制御するコントローラとを具備し、前記コントローラは、前記転置ファイルに前記コンテンツを含む前記ファイルの識別子を格納し、前記コンテンツの検索により求めた前記ファイルの識別子を前記ファイル検索テーブルに格納し、前記コンテンツの検索要求に対する検索結果として、前記ファイル検索テーブルに格納された前記ファイルの識別子を前記インターフェースから出力することを特徴とする。
【発明の効果】
【００１３】
本発明によれば、ホストインターフェースの通信速度に制限されることなく、転置ファイルの管理を高速に行うことができるストレージ装置を提供可能である。
【図面の簡単な説明】
【００１４】
【図１】本発明の第１実施形態に係るストレージ装置のハードウェア構成を示すブロック図である。
【図２】第１実施形態のストレージ装置におけるファイルの書き込み処理を示すフローチャートである。
【図３】第１実施形態のストレージ装置におけるファイルの削除処理を示すフローチャートである。
【図４】第１実施形態のストレージ装置におけるファイルの更新処理を示すフローチャートである。
【図５】第１実施形態のストレージ装置におけるコンテンツの検索処理を示すフローチャートである。
【図６】本発明の第２実施形態のストレージ装置におけるコンテンツの検索処理を示すフローチャートである。
【図７】第２実施形態のストレージ装置におけるコンテンツの検索処理を示すフローチャートである。
【図８】第２実施形態のストレージ装置におけるコンテンツの検索処理を示すフローチャートである。
【図９】本発明の第３実施形態のストレージ装置のハードウェア構成を示すブロック図である。
【図１０Ａ】ハッシュテーブルデータ構造の第１例を示す図である。
【図１０Ｂ】ハッシュテーブルデータ構造の第２例を示す図である。
【図１１】第３実施形態における要素登録手続(第１例)を示すフローチャートである。
【図１２】第３実施形態における要素検索手続(第１例)を示すフローチャートである。
【図１３】第３実施形態における要素登録手続(第２例)を示すフローチャートである。
【図１４】第３実施形態における要素検索手続(第２例)を示すフローチャートである。
【図１５】第３実施形態のストレージ装置におけるコンテンツの検索処理を示すフローチャートである。
【図１６】第３実施形態のストレージ装置におけるコンテンツの検索処理を示すフローチャートである。
【図１７】第３実施形態のストレージ装置におけるコンテンツの検索処理を示すフローチャートである。
【図１８】本発明の第４実施形態のストレージ装置のハードウェア構成を示すブロック図である。
【図１９】ＣＡＭ−ＲＡＭシステムの一例を示す図である。
【発明を実施するための形態】
【００１５】
実施形態を説明する前に、本願明細書で用いる用語について説明する。
【００１６】
コンテンツ(Content)とは、多くの場合、自然言語における単語や、数のことである。例えば、“This is a book”というテキストにおいては、This、is、a、bookがそれぞれコンテンツである。なお、前述したように、コンテンツとは、多くの場合、自然言語における単語や、数のことであるが、用途に応じて任意に定義してよい。例えば、バイナリファイルにおいて、特定のビットパターンをコンテンツと定義しても良い。また、動画ファイルにおいて、人物などの特定画像パターンをコンテンツと定義しても良い。また、音声ファイルにおいて、場面切り替え時に特徴的な音声パターンなどの特定音声パターンをコンテンツと定義してもよい。
【００１７】
ファイル(File)とは、コンテンツを含む一般のファイルである。例えば、テキストからなるファイルや、テキストとその他アプリケーション特有の情報を含むファイルである。
【００１８】
形態素分析(Morphological Analysis)とは、ファイルからコンテンツを抽出して、コンテンツ毎に分離する処理のことである。
【００１９】
ファイル識別子(File ID)とは、ストレージ装置においてそのファイルを特定できる識別子である。例としては、階層的ディレクトリ構造におけるフルパスのファイル名、多くのファイルシステムで使用されるファイル識別子であるinode番号などが含まれる。また、任意長ビットデータをハッシュ関数によって固定長ビットデータに変換するハッシュ生成器を使い、ファイルを特定できる任意長ビットデータから生成した固定長ビットデータをファイル識別子としても良い。
【００２０】
転置ファイル(Inverted File)とは、コンテンツ毎に作成され、そのコンテンツを含むファイルの識別子を格納するファイルである。転置ファイルは、ファイル内におけるコンテンツの位置情報を含んでいても良い。
【００２１】
次に、転置ファイルの一例を示す。File 1: ”This is a book”、File 2: “This is a bag”という二つのファイルがある場合を考える。File 1のFile IDを0x001、File 2のFile IDを0x002とする。ファイル内におけるコンテンツの位置(pos)は、ゼロを基点とするコンテンツの出現順番とする。転置ファイルは、File IDとファイル内におけるコンテンツの位置情報の組、(File ID, pos)を格納する。このとき、“This”に対応する転置ファイルの内容は、{(0x001, 1), (0x002,1)}となる。この転置ファイルは、”This”というコンテンツが、0x001というFile IDのファイルの１番目の位置と、0x002というFile IDのファイルの１番目の位置にあることを意味している。
【００２２】
転置ファイル識別子(Inverted File ID)とは、ストレージ装置においてその転置ファイルを特定できる識別子である。例えば、任意長ビットデータをハッシュ関数によって固定長ビットデータに変換するハッシュ生成器を使い、コンテンツから生成した固定長ビットデータである。
【００２３】
以下、図面を参照して本発明の実施形態について説明する。説明に際し、全図にわたり、共通する部分には共通する参照符号を付す。
【００２４】
［１］第１実施形態
［１−１］ハードウェア構成
まず、本発明の第１実施形態のストレージ装置のハードウェア構成について説明する。
【００２５】
図１は、第１実施形態のストレージ装置のハードウェア構成を示すブロック図である。
【００２６】
図示するように、ストレージ装置１０は、ホストインターフェース１１、第１のメモリブロック１２、第２のメモリブロック１３、及びコントローラ１４から構成されている。なお、ストレージ装置１０には、ＣＰＵ１０１、及びメインメモリ１０２を含むホストシステムが接続されている。ホストシステムとしては、例えばパーソナルコンピュータ、携帯電話、デジタルカメラ、携帯情報端末（ＰＤＡ）等がある。
【００２７】
ホストインターフェース１１は、ホストシステムからコンテンツの検索要求を入力として受け取り、コンテンツの検索結果をホストシステムに出力する。また、ホストインターフェース１１は、アドレスを指定したファイルの書き込み/読み出しの要求を入力として受け取る。書き込み要求の際には、さらにファイルを入力として受け取る。また、読み出し要求の際には、アドレス指定されたファイルを出力する。
【００２８】
第１のメモリブロック１２は、ファイル１２１、ファイル１２１のコンテンツリスト、及びコンテンツに対応する転置ファイル１２２を格納する。転置ファイル１２２は、コンテンツを含むファイル１２１のファイル識別子のリストを格納する。転置ファイル１２２は、ファイル１２１内におけるコンテンツの位置情報を含んでいても良い。
【００２９】
第２のメモリブロック１３は、ファイル検索テーブル１３１を格納する。ファイル検索テーブル１３１は、コンテンツの検索で得られたファイル１２１のファイル識別子のリストを格納する。第２のメモリブロック１３は、書き込み/読み出し時におけるバッファメモリを有している。
【００３０】
第１のメモリブロック１２は、第２のメモリブロック１３に比べて、不揮発・大容量であるがアクセス速度が遅い。第２のメモリブロック１３は、ホストインターフェース１１の通信速度と、第１のメモリブロック１２のアクセス速度の速度差を補うために使用できる。例えば、第１のメモリブロック１２は不揮発性のFlash memoryアレイであり、第２のメモリブロックは揮発性のＤＲＡＭもしくはＳＲＡＭである。
【００３１】
コントローラ１４は、ホストインターフェース１１と第１のメモリブロック１２と第２のメモリブロック１３との間の相互の信号送受信を制御する。コントローラ１４は、ホストインターフェース１１に入力されたコンテンツの検索要求に対して、コンテンツの検索処理を実行する。そして、ホストインターフェース１１を介してコンテンツの検索結果を出力する。また、コントローラ１４は、書き込み要求の際には、第１のメモリブロック１２内のアドレス指定の位置にファイル１２１を書き込む。読み出しの際には、アドレス指定の位置のファイル１２１を読み出す。
【００３２】
［１−２］ファイル管理及びコンテンツ検索処理
次に、第１実施形態のストレージ装置におけるファイル管理及びコンテンツ検索処理について説明する。
【００３３】
ストレージ装置１０には、ホストシステムからホストインターフェース１１を介してファイルの書き込み、削除、及び更新の要求が入力される。そして、随時、ホストシステムからストレージ装置１０に、ホストインターフェース１１を介してコンテンツの検索要求が入力される。コンテンツの検索要求が入力されると、ストレージ装置１０においてコンテンツの検索処理が行われ、コンテンツの検索結果がホストインターフェース１１を介してホストシステムに出力される。
【００３４】
以下に、ストレージ装置１０における処理を、検索対象のファイルの書き込み、検索対象のファイルの削除、検索対象のファイルの更新、及びコンテンツの検索の順で述べる。
【００３５】
［１−２−１］ファイルの書き込み・削除・更新
（ファイルの書き込み）
図２は、第１実施形態のストレージ装置におけるファイルの書き込み処理を示すフローチャートである。
【００３６】
（１）ホストインターフェース１１は、ホストシステムからファイルの書き込み要求を受け取る（ステップＳ１１）。ホストシステムからホストインターフェース１１に、ファイル、及びそのファイルの格納アドレスが入力される。すると、コントローラ１４は、ホストシステムから入力されたファイルの形態素分析を行い、コンテンツのリストを得る（ステップＳ１２）。ここで、形態素分析とは、ファイルをコンテンツに分解する処理のことである。
【００３７】
（２）コントローラ１４は、第１のメモリブロック１２に、ファイル１２１と、ファイル１２１から得たコンテンツリストを格納する（ステップＳ１３）。
【００３８】
（３）コントローラ１４は、コンテンツリストのコンテンツ毎に、第１のメモリブロック１２にそのコンテンツに対応する転置ファイル１２２があるか否かを調べる（ステップＳ１４）。転置ファイルが既にある場合は、転置ファイル１２２にそのコンテンツを含むファイル１２１のファイル識別子を追記する（ステップＳ１５）。一方、転置ファイルがない場合は、転置ファイルを作成する（ステップＳ１６）。そして、作成した転置ファイルにそのコンテンツを含むファイル１２１のファイル識別子を記入する（ステップＳ１５）。
【００３９】
また、前述した例では、ファイルの形態素分析をコントローラ１４にて行ったが、ホストシステムのＣＰＵ１０１にて形態素分析を行っても良い。この場合、以下のような処理となる。
【００４０】
（１）ホストシステムは、ファイルの形態素分析を行い、コンテンツのリストを得る。ホストシステムは、ストレージ装置１０に、ファイル、そのファイルの格納アドレス、及びコンテンツのリストを入力する。
【００４１】
（２）コントローラ１４は、第１のメモリブロック１２に、ファイル１２１とそのファイルから取得したコンテンツリストを格納する。
【００４２】
（３）コントローラ１４は、コンテンツリストのコンテンツ毎に、第１のメモリブロック１２にそのコンテンツに対応する転置ファイル１２２があるか否かを調べる。転置ファイルが既にある場合は、転置ファイル１２２にそのコンテンツを含むファイル１２１のファイル識別子を追記する。一方、転置ファイルがない場合は、転置ファイルを作成する。そして、作成した転置ファイルにそのコンテンツを含むファイル１２１のファイル識別子を記入する。
【００４３】
（ファイルの削除）
図３は、第１実施形態のストレージ装置におけるファイルの削除処理を示すフローチャートである。
【００４４】
（１）ホストインターフェース１１は、ホストシステムからファイルの削除要求を受け取る（ステップＳ２１）。すると、コントローラ１４は、第１のメモリブロック１２に格納された削除対象のファイルから得たコンテンツリストに従い、コンテンツ毎に対応する転置ファイル１２２から削除対象ファイルのファイル識別子を削除する（ステップＳ２２）。
【００４５】
（２）コントローラ１４は、第１のメモリブロック１２から削除対象ファイルとコンテンツリストを削除する（ステップＳ２３）。
【００４６】
(ファイルの更新)
図４は、第１実施形態のストレージ装置におけるファイルの更新処理を示すフローチャートである。
【００４７】
（１）ホストインターフェース１１は、ホストシステムからファイルの更新要求を受け取る（ステップＳ３１）。ホストシステムからホストインターフェース１１に、更新ファイル、及び更新ファイルの格納アドレスが入力される。
【００４８】
（２）コントローラ１４は、第１のメモリブロック１２に格納された更新前のファイルから得たコンテンツリストに従い、コンテンツ毎に対応する転置ファイルから更新前のファイルのファイル識別子を削除する（ステップＳ３２）。
【００４９】
（３）コントローラ１４は、ホストシステムから入力された更新ファイルの形態素分析を行い、コンテンツのリストを得る（ステップＳ３３）。
【００５０】
（４）コントローラ１４は、第１のメモリブロック１２に、更新ファイルとその更新ファイルから得たコンテンツリストを格納する（ステップＳ３４）。
【００５１】
（５）コントローラ１４は、コンテンツリストのコンテンツ毎に、第１のメモリブロック１２にそのコンテンツに対応する転置ファイル１２２があるか否かを調べる（ステップＳ３５）。転置ファイルが既にある場合は、その転置ファイル１２２にそのコンテンツを含むファイル１２１のファイル識別子を追記する（ステップＳ３６）。一方、転置ファイルがない場合は、転置ファイルを作成する（ステップＳ３７）。そして、作成した転置ファイルにそのコンテンツを含むファイル１２１のファイル識別子を記入する（ステップＳ３６）。
【００５２】
［１−２−２］コンテンツ検索処理
次に、第１実施形態のストレージ装置におけるコンテンツ検索処理（全文検索機能）について説明する。
【００５３】
図５は、第１実施形態のストレージ装置におけるコンテンツの検索処理を示すフローチャートである。
【００５４】
（１）ホストインターフェース１１は、ホストシステムからコンテンツの検索要求を受け取る（ステップＳ４１）。コントローラ１４は、検索対象のコンテンツに対応する転置ファイルに格納されたファイル識別子のリストを、第２のメモリブロック１３のファイル検索テーブル１３１に格納する（ステップＳ４２）。
【００５５】
（２）コントローラ１４は、ファイル検索テーブル１３１に格納されているファイル識別子のリストを、コンテンツ検索結果としてホストインターフェース１１を介して出力する（ステップＳ４３）。
【００５６】
第１実施形態によれば、ストレージ装置内のコントローラが転置ファイルの管理及びコンテンツの検索処理を行うため、それらの処理をホストインターフェースの通信速度に制限されることなく高速に行うことができる。コンテンツ検索の際には、転置ファイルにアクセスすることにより、検索の都度、全ファイルを走査することなく、コンテンツ検索結果を得ることができる。すなわち、従来のストレージ装置の機能に加えて、全文検索機能を自らもつストレージ装置を実現することができる。
【００５７】
従来、ストレージ装置を管理するホストシステムのリソース（ＣＰＵやＤＲＡＭ）を使って、転置ファイルの管理やブール演算による検索を行うソフトウェアが存在している。しかし、次の３点の問題があった。
【００５８】
（１）ホストシステムのリソースに負荷がかかる。これは、特にホスト機器のリソースが限られるモバイル用途で問題になる。（２）スケーラビリティが無い。ホストシステムにおけるリソースの負荷が、ストレージ装置の数の増大とともに増大する。（３）可搬性が低い。取り外し可能なストレージ装置であっても、転置ファイルの管理やブール演算による検索の実現法がホストシステムに依存する場合、任意のホストシステムで全文検索機能を使用することができない。
【００５９】
本実施形態では、これらの問題を解決することができる。すなわち、ホスト機器にてコンテンツの検索を行う際に、ホストシステムのリソースにかかる負荷を低減することができる。また、コンテンツ検索に関し、ストレージ装置の数が増大しても、ホストシステムにおけるリソースの負荷が増大しない。ストレージ装置で転置ファイルの管理やブール演算による検索を行うため、任意のホストシステムで全文検索機能を使用することができる。
【００６０】
［２］第２実施形態
次に、本発明の第２実施形態のストレージ装置について説明する。
【００６１】
第２実施形態のストレージ装置では、第１実施形態の処理にさらに加えて、複数のコンテンツの検索結果に対するＡＮＤ、ＯＲ、ＮＯＴを含むブール演算の処理を行うことができる。
【００６２】
ホストインターフェースを介して複数のコンテンツの検索結果に対するＡＮＤ、ＯＲ、ＮＯＴを含むブール演算の要求が入力されると、コントローラは、ブール演算要求の結果となるように、ファイル検索テーブルの内容を書き換える。そして、ホストインターフェースを介してブール演算の結果、すなわちコンテンツの検索結果を出力する。
【００６３】
［２−１］ハードウェア構成
第２実施形態のストレージ装置のハードウェア構成は、前記第１実施形態と同様であるため、記載は省略する。
【００６４】
［２−２］コンテンツ検索処理（ブール演算検索要求に対する処理）
第２実施形態のストレージ装置におけるコンテンツのＡＮＤ、ＯＲ、ＮＯＴの検索処理について説明する。
【００６５】
図６、図７及び図８は、第２実施形態のストレージ装置におけるコンテンツの検索処理を示すフローチャートである。
【００６６】
（１）ホストインターフェース１１は、ホストシステムからコンテンツのＡＮＤ、ＯＲ、ＮＯＴの検索要求を受け取る（ステップＳ５１）。
【００６７】
（２）コントローラ１４は、検索対象の第１のコンテンツに対応する転置ファイルに格納されたファイル識別子のリストを、第２のメモリブロック１３のファイル検索テーブル１３１に格納する（ステップＳ５２）。
【００６８】
（３）コントローラ１４は、検索対象の第２のコンテンツに対応する転置ファイルに格納されたファイル識別子毎に、ブール演算子に応じて、次の通りファイル検索テーブル１３１の内容を書き換える。
【００６９】
ＡＮＤ演算を図６中の処理２１に示す。第２のコンテンツに対応する転置ファイルに格納されたファイル識別子が、ファイル検索テーブル１３１に既にあるか否かを調べる（ステップＳ５３）。
【００７０】
そのファイル識別子があれば、バッファにそのファイル識別子を書き出す（ステップＳ５４）。バッファ領域としては、第２のメモリブロック１３の一部を割り当てる。一方、そのファイル識別子がなければ、なにもしない（ステップＳ５５）。
【００７１】
最後に、ファイル検索テーブル１３１を初期化する（ステップＳ５６）。そして、バッファに書き込まれたファイル識別子のリストを、ファイル検索テーブル１３１に格納する（ステップＳ５７）。
【００７２】
ＯＲ演算を図７中の処理２２に示す。第２のコンテンツに対応する転置ファイルに格納されたファイル識別子が、ファイル検索テーブル１３１に既にあるか否かを調べる（ステップＳ６１）。
【００７３】
そのファイル識別子があれば、何もしない（ステップＳ６２）。一方、そのファイル識別子がなければ、ファイル検索テーブル１３１にそのファイル識別子を追加する（ステップＳ６３）。
【００７４】
ＮＯＴ演算を図８中の処理２３に示す。第２のコンテンツに対応する転置ファイルに格納されたファイル識別子が、ファイル検索テーブル１３１に既にあるか否かを調べる（ステップＳ７１）。
【００７５】
そのファイル識別子があれば、ファイル検索テーブル１３１からファイル識別子を削除する（ステップＳ７２）。一方、ファイル識別子がなければ、なにもしない（ステップＳ７３）。
【００７６】
（４）コントローラ１４は、ファイル検索テーブル１３１に格納されているファイル識別子のリストを、コンテンツ検索結果としてホストインターフェース１１を介して出力する（ステップＳ５８）。
【００７７】
第２実施形態によれば、ストレージ装置内のコントローラが転置ファイルの管理やブール演算を行うため、それらの処理をホストインターフェースの通信速度に制限されることなく高速に行うことができる。すなわち、第１の実施形態における効果に加えて、複数のコンテンツの検索結果に対するＡＮＤ、ＯＲ、ＮＯＴを含むブール演算機能を備えるストレージ装置を実現することができる。その他の構成及び効果は前記第１実施形態と同様である。
【００７８】
［３］第３実施形態
次に、本発明の第３実施形態のストレージ装置について説明する。
【００７９】
第３実施形態のストレージ装置では、第２実施形態の処理にさらに加えて、コンテンツに対応する転置ファイルのアドレスの高速検索機能、及び複数のコンテンツの検索結果に対するＡＮＤ、ＯＲ、ＮＯＴを含むブール演算の高速化が実現できる。
【００８０】
［３−１］ハードウェア構成
本発明の第３実施形態のストレージ装置のハードウェア構成について説明する。
【００８１】
図９は、第３実施形態のストレージ装置のハードウェア構成を示すブロック図である。
【００８２】
図示するように、ストレージ装置３０は、ホストインターフェース１１、第１のメモリブロック１２、第２のメモリブロック１５、第３のメモリブロック１６、第４のメモリブロック１７、及びコントローラ１８から構成されている。
【００８３】
コントローラ１８は、ハッシュ生成器１８１を含む。ハッシュ生成器１８１は、任意長ビットデータをハッシュ関数によって固定長ビットデータに変換する。ここでは、この機能を用いて、ハッシュ生成器１８１は、任意長ビットデータのコンテンツから、固定長ビットデータの転置ファイルの識別子を生成する。また、ハッシュ生成器１８１は、ファイルを特定できる任意長ビットデータから、固定長ビットデータのファイルの識別子を生成する。
【００８４】
ハッシュ関数としては、なるべく均一かつ疎な暗号学的ハッシュ関数(cryptologic hash)が好ましい。例えば、ＣＲＣ(Cyclic Redundancy Check)、もしくはＳＨＡ−１(Secure Hash Algorithm-1)、ＳＨＡ−２(Secure Hash Algorithm-1)、ＭＤ４（MessageDigest4)、ＭＤ５（MessageDigest5)を使用する。
【００８５】
ハッシュ生成器１８１は、ハッシュ関数に従い生成したある固定長ビットのビット列を、所望のビット長（BitLength）にする機能を有していても良い。例えば、次式の除算機能を有する。  <Key ID>= cryptologic_hash(<Key>) mod BitLength
また、第２のメモリブロック１５は、ホストインターフェース１１と第１のメモリブロック１２と第３のメモリブロック１６と第４のメモリブロック１７とコントローラ１８とに接続されている。第２のメモリブロック１５は、ファイル識別子とブール演算の結果を格納する変数の組を要素とする配列であるファイル検索テーブル１５１を格納する。ファイル検索テーブル１５１中の各要素の格納位置は、各要素のファイル識別子が自ら含む情報によって決まっている。言い換えると、各ファイル識別子は、ファイル検索テーブル１５１中の各要素の格納位置情報を含んでいる。
【００８６】
第３のメモリブロック１６は、ホストインターフェース１１と第１のメモリブロック１２と第２のメモリブロック１５と第４のメモリブロック１７とコントローラ１８とに接続されている。第３のメモリブロック１６は、転置ファイルの識別子とその転置ファイルの格納位置の組を要素とする配列である転置ファイル割り当てテーブル１６１を格納する。転置ファイル割り当てテーブル１６１中の各要素の格納位置は、各要素の転置ファイル識別子が自ら含む情報によって決まっている。言い換えると、各転置ファイル識別子は、転置ファイル割り当てテーブル１６１中の各要素の格納位置情報を含んでいる。
【００８７】
第４のメモリブロック１７は、ホストインターフェース１１と第１のメモリブロック１２と第２のメモリブロック１５と第３のメモリブロック１６とコントローラ１８とに接続されている。第４のメモリブロック１７は、ファイルの識別子とそのファイルの格納位置の組を要素とする配列であるファイル割り当てテーブル１７１を格納する。ファイル割り当てテーブル１７１中の各要素の格納位置は、各要素のファイル識別子が自ら含む情報によって決まっている。言い換えると、各ファイル識別子は、ファイル割り当てテーブル１７１中の各要素の格納位置情報を含んでいる。
【００８８】
また、ファイル識別子と転置ファイル識別子のいずれかもしくは両方が、ハッシュ生成器１８１によって固定長ビットデータとされている。
【００８９】
［３−２］ハッシュテーブルデータ構造
ハッシュテーブルデータ構造は、転置ファイル割り当てテーブル１６１やファイル検索テーブル１５１、ファイル割り当てテーブル１７１に適用することができる。ハッシュテーブルデータ構造は、キー識別子とそれに対応する値の組を要素として格納する。
【００９０】
ハッシュテーブルデータ構造の特徴は、登録する各要素の格納位置が、各要素のキー識別子が自ら含む情報によって決まることである。このデータ構造の特徴により、検索対象のキー識別子が登録されているかの有無判定、登録されているならば検索対象のキー識別子に対応する値の取得(キー識別子から値への変換)を、高速に行うことができる。これを用いることにより、本実施形態ではコンテンツに対応する転置ファイルのアドレスの高速な検索、及び複数のコンテンツの検索結果に対するＡＮＤ、ＯＲ、ＮＯＴを含むブール演算の高速化、ファイルの識別子に対応するファイルのアドレスの高速な検索、が実現できる。
【００９１】
［３−２−１］ハッシュテーブルデータ構造の第１例
図１０Ａ（ａ）は、ハッシュテーブルデータ構造の第１例を示す図である。
【００９２】
ハッシュテーブルデータ構造は、図１０Ａ（ａ）に示すように、有効フラグとキー識別子とそれに対応する値の組を要素とする配列である。配列における各要素の位置をスロット識別子で表す。
【００９３】
スロット識別子は、コントローラによりキー識別子から生成されたものである。ここでは、図１０Ａ（ｂ）に示すように、キー識別子の接頭部１２ビットをスロット識別子としている。キー識別子をｍビットとし、スロット識別子をｎビットとすると、ｍ＞ｎが成り立つ（ｍ，ｎは１以上の整数）。図１０Ａ（ｃ）は登録待ちのキー識別子を示し、図１０Ａ（ａ）は図１０Ａ（ｃ）に示した登録待ちのキー識別子がハッシュテーブルデータ構造に登録された状態を示す。
【００９４】
以下に、ハッシュテーブルデータ構造（第１例）における要素登録及び要素検索の手順を説明する。
【００９５】
（要素登録手順）
ここでは、ハッシュテーブルデータ構造にキー識別子とそれに対応する値の組を登録する手続きを述べる。
【００９６】
図１１は、第３実施形態における要素登録手続(第１例)を示すフローチャートである。
【００９７】
コントローラ１８は、候補スロット識別子を保持する記憶領域を有し、候補スロット識別子の変数を管理する。
【００９８】
（１）（初期化）コントローラ１８は、２ｎ個の要素を持つ配列を用意し、すべての要素の有効フラグをFalseにする（ステップＳ８１）。
【００９９】
（２）（候補スロット識別子）コントローラ１８は、登録するｍビットのキー識別子の一部からｎビットのスロット識別子を生成する（ステップＳ８２）。例えば、図１０Ａ（ｂ）に示すように、２４ビットのキー識別子の接頭部１２ビットをスロット識別子とする。そのスロット識別子を、候補スロット識別子の変数に代入する（ステップＳ８３）。
【０１００】
（３）（次期登録スロットの特定）コントローラ１８は、候補スロット識別子で特定される要素の有効フラグがFalseか否かを判定する（ステップＳ８４）。有効フラグがFalseのとき（Yes）、ステップＳ８５に移行する。一方、有効フラグがFalseでなくTrueのとき（No）、候補スロット識別子をインクリメントして（ステップＳ８６）、再度、ステップＳ８４に戻る。
【０１０１】
（４）（登録）コントローラ１８は、候補スロット識別子で特定される要素に、登録するキー識別子と値を格納し、有効フラグをTrueに変える（ステップＳ８５）。
【０１０２】
（要素検索手順）
ここでは、検索対象のキー識別子に対して、対応する値を得る手続きを述べる。
【０１０３】
図１２は、第３実施形態における要素検索手続(第１例)を示すフローチャートである。
【０１０４】
（１）（候補スロット識別子）コントローラ１８は、図１１に示した登録手順と同じ手続きで、検索するｍビットのキー識別子の一部からｎビットの候補スロット識別子を生成する（ステップＳ９１、Ｓ９２）。
【０１０５】
（２）（検索キー対応スロットの特定）コントローラ１８は、候補スロット識別子で特定される要素の有効フラグがTrueか否かを判定する（ステップＳ９３）。有効フラグがTrueでなくFalseのとき（No）、コントローラ内部状態をUNMATCHとして検索手続き終了する（ステップＳ９４、Ｓ９５）。一方、有効フラグがTrueのとき（Yes）、ステップＳ９６へ移行する。
【０１０６】
コントローラ１８は、候補スロット識別子で特定される要素のキー識別子が、検索対象のキー識別子と同じか判定する（ステップＳ９６）。検索対象のキー識別子と同じとき（Yes）、ステップＳ９７に移行する。一方、検索対象のキー識別子と違うとき（No）、候補スロット識別子をインクリメントして（ステップＳ９８）、再度、ステップＳ９３へ戻る。
【０１０７】
（３）（出力）コントローラ１８は、候補スロット識別子で特定される要素の値を、目的の値として得る（ステップＳ９７）。
【０１０８】
［３−２−２］ハッシュテーブルデータ構造の第２例
図１０Ｂ（ａ）は、ハッシュテーブルデータ構造の第２例を示す図である。
【０１０９】
ハッシュテーブルデータ構造は、図１０Ｂ（ａ）に示すように、ポインタを要素とするポインタ配列と、ポインタとキー識別子とそれに対応する値の組を要素とする連結リストからなる。ポインタ配列における各要素の位置をスロット識別子で表す。
【０１１０】
第１例と同様に、スロット識別子は、コントローラによりキー識別子から生成されたものである。ここでは、図１０Ｂ（ｂ）に示すように、キー識別子の接頭部１２ビットをスロット識別子としている。キー識別子をｍビットとし、スロット識別子をｎビットとすると、ｍ＞ｎが成り立つ。図１０Ｂ（ａ）は、図１０Ａ（ｃ）に示した登録待ちのキー識別子がハッシュテーブルデータ構造に登録された状態を示す。
【０１１１】
以下に、ハッシュテーブルデータ構造（第２例）における要素登録及び要素検索の手順を説明する。
【０１１２】
（要素登録手順）
ここでは、キー識別子とそれに対応する値の組を登録する手続きを述べる。
【０１１３】
図１３は、第３実施形態における要素登録手続(第２例)を示すフローチャートである。
【０１１４】
コントローラ１８は、候補スロット識別子と候補ポインタを保持する記憶領域を有し、候補スロット識別子及び候補ポインタの変数を管理する。
【０１１５】
（１）（初期化）コントローラ１８は、２ｎ個の要素を持つポインタ配列を用意し、すべての要素のポインタをＮＵＬＬにする（ステップＳ１０１）。
【０１１６】
（２）（スロット識別子）コントローラ１８は、登録するｍビットのキー識別子の一部からｎビットのスロット識別子を生成する（ステップＳ１０２）。例えば、図１０Ｂ（ｂ）に示すように、２４ビットのキー識別子の接頭部１２ビットを抽出し、それを候補スロット識別子とする（ステップＳ１０３）。
【０１１７】
（３）（次期登録エントリの特定）コントローラ１８は、候補スロット識別子で特定されるポインタ配列の要素がＮＵＬＬか否かを判定する（ステップＳ１０４）。ポインタ配列の要素がＮＵＬＬのとき（Yes）、連結リストの要素を１つ作成し、そのポインタを、候補スロット識別子で特定されるポインタ配列の要素と、候補ポインタとに格納して（ステップＳ１０５）、ステップＳ１１０に移行する。一方、ポインタ配列の要素がＮＵＬＬでないとき（No）、そのポインタを候補ポインタにセットして（ステップＳ１０６）、ステップＳ１０７に移行する。
【０１１８】
候補ポインタで特定される連結リストの要素のポインタがＮＵＬＬか否かを判定する（ステップＳ１０７）。ポインタがＮＵＬＬのとき（Yes）、連結リストの要素を１つ作成し、そのポインタを、候補ポインタで特定される連結リストの要素のポインタと、候補ポインタに格納して（ステップＳ１０８）、ステップＳ１１０に移行する。一方、ポインタがＮＵＬＬでないとき（No）、そのポインタを候補ポインタにセットして（ステップＳ１０９）、ステップＳ１０７に戻る。
【０１１９】
（４）（登録）コントローラ１８は、候補ポインタで特定される連結リストの要素にキー識別子と値を格納する（ステップＳ１１０）。
【０１２０】
（要素検索手順）
ここでは、検索対象のキー識別子に対して、対応する値を得る手続きを述べる。
【０１２１】
図１４は、第３実施形態における要素検索手続(第２例)を示すフローチャートである。
【０１２２】
（１）（候補スロット識別子）コントローラ１８は、図１３に示した登録手順と同じ手続きで、検索するｍビットのキー識別子の一部からｎビットの候補スロット識別子を生成する（ステップＳ１１１、Ｓ１１２）。
【０１２３】
（２）（検索キー対応スロットの特定）コントローラ１８は、候補スロット識別子で特定されるポインタ配列の要素のポインタがＮＵＬＬか否かを判定する（ステップＳ１１３）。ポインタがＮＵＬＬのとき（Yes）、コントローラ内部状態をUNMATCHとして検索手続きを終了する（ステップＳ１１４、Ｓ１１５）。一方、ポインタがＮＵＬＬでないとき（No）、そのポインタを候補ポインタに格納して（ステップＳ１１６）、ステップＳ１１７に移行する。
【０１２４】
ステップＳ１１７では、候補ポインタで特定される連結リストの要素のキー識別子が、検索対象のキー識別子と同じか否かを判定する。キー識別子と同じとき（Yes）、ステップＳ１２２に移行する。
【０１２５】
一方、キー識別子と違うとき（No）、候補ポインタで特定される連結リストの要素のポインタがＮＵＬＬか否かを判定する（ステップＳ１１８）。ポインタがＮＵＬＬのとき（Yes）、コントローラ内部状態をUNMATCHとして検索手続きを終了する（ステップＳ１１９、Ｓ１２０）。一方、ポインタがＮＵＬＬでないとき（No）、そのポインタを候補ポインタに格納して（ステップＳ１２１）、ステップＳ１１７に戻る。
【０１２６】
（３）（出力）ステップＳ１２２では、コントローラ１８は、候補ポインタで特定される要素の値を、目的の値として得る。
【０１２７】
なお、ハッシュテーブルデータ構造の作成に必要な記憶容量を少なくするために、連結リストに格納するキー識別子の換わりに、キー識別子のうちのスロット識別子に使われなかった残りのｍ−ｎビットの部分を用いても良い。
【０１２８】
［３−３］転置ファイル割り当てテーブル
第３のメモリブロック１６の転置ファイル割り当てテーブル１６１に、ハッシュテーブルデータ構造を適用する場合の処理は以下のようになる。
【０１２９】
ハッシュテーブルデータ構造におけるキー識別子と値を、それぞれ転置ファイル割り当てテーブル１６１内の転置ファイル識別子と転置ファイル格納位置にセットする。
【０１３０】
（１）コントローラ１８は、ハッシュ生成器１８１により、コンテンツが持つデータから転置ファイル識別子を生成する。
【０１３１】
（２）コントローラ１８は、転置ファイル割り当てテーブル１６１に従い、転置ファイル識別子を転置ファイル格納位置に変換する。すなわち、転置ファイル識別子から転置ファイルの格納位置を求める。これにより、コントローラ１８は、コンテンツに対応する転置ファイルに高速にアクセスすることができる。
【０１３２】
［３−４］ファイル割り当てテーブル
第４のメモリブロック１７のファイル割り当てテーブル１７１に、ハッシュテーブルデータ構造を適用する場合の処理は以下のようになる。
【０１３３】
ハッシュ生成器１８１により、ファイルを特定できる任意長ビットデータから生成された固定長ビットデータをファイル識別子として使用する場合、その逆にファイル識別子から元のファイルを特定できる必要がある。そのために、本実施形態ではファイル割り当てテーブル１７１を、第４のメモリブロック１７に用意する。
【０１３４】
既に説明したハッシュテーブルデータ構造におけるキー識別子と値を、それぞれファイル割り当てテーブル１７１内のファイル識別子とファイル格納位置にセットする。
【０１３５】
（１）コントローラ１８は、ハッシュ生成器１８１により、ファイルを特定できる任意長ビットデータからファイル識別子を生成する。
【０１３６】
（２）コントローラ１８は、ファイル割り当てテーブル１７１に従い、ファイル識別子からファイル格納位置を求める。このように、ファイル格納位置を求めることにより、コントローラ１８は、ファイル識別子に対応するファイルに高速にアクセスすることができる。
【０１３７】
［３−５］ファイル検索テーブル
第２のメモリブロック１５のファイル検索テーブル１５１に、ハッシュテーブルデータ構造を適用する場合の処理は以下のようになる。
【０１３８】
図１５、図１６及び図１７は、第３実施形態のストレージ装置におけるコンテンツの検索処理を示すフローチャートである。
【０１３９】
既に説明したハッシュテーブルデータ構造におけるキー識別子と値を、それぞれ第２のメモリブロック１５内のファイル識別子とブール演算の結果の変数(以下、ブール変数と記す)にセットする。コントローラ１８は、ブール演算結果の判定値(以下、ブール判定値と記す)を保持する記憶領域を有し、ブール判定値を管理する。
【０１４０】
（１）コントローラ１８は、検索対象の第１のコンテンツに対応する転置ファイルに格納されたファイル識別子のリストから、ファイル識別子を一つずつ取り出す。既に述べた登録手順に従い、各ファイル識別子を、ブール変数値を１としてファイル検索テーブル１５１に登録する。また、ブール判定値は１とする（ステップＳ１３１）。
【０１４１】
（２）コントローラ１８は、検索対象の第２のコンテンツに対応する転置ファイルに格納されたファイル識別子毎に、ブール演算子に応じて、次の通りファイル検索テーブル１５１の内容を書き換える。
【０１４２】
ＡＮＤ演算を図１５中の処理２４に示す。第２のコンテンツに対応する転置ファイルに格納されたファイル識別子が、ファイル検索テーブル１５１に既に登録されているか否かを調べる（ステップＳ１３２）。ファイル識別子が登録されていれば（Yes）、対応するブール変数値をインクリメントする。さらに、ブール判定値をインクリメントする（ステップＳ１３３）。一方、ファイル識別子が登録されていなければ（No）、なにもせず（ステップＳ１３４）、ステップＳ１３５に移行する。
【０１４３】
ＯＲ演算を図１６中の処理２５に示す。第２のコンテンツに対応する転置ファイルに格納されたファイル識別子が、ファイル検索テーブル１５１に既に登録されているか否かを調べる（ステップＳ１４１）。ファイル識別子が登録されていれば（Yes）、なにもせず（ステップＳ１４２）、ステップＳ１３５に移行する。一方、ファイル識別子が登録されていなければ（No）、そのファイル識別子対応するブール変数値を現在のブール判定値として登録する（ステップＳ１４３）。
【０１４４】
ＮＯＴ演算を図１７中の処理２６に示す。第２のコンテンツに対応する転置ファイルに格納されたファイル識別子が、ファイル検索テーブル１５１に既に登録されているか否かを調べる（ステップＳ１５１）。ファイル識別子が登録されていれば（Yes）、そのファイル識別子に対応するブール変数値をデクリメントする（ステップＳ１５２）。一方、ファイル識別子が登録されていなければ（No）、なにもせず（ステップＳ１５３）、ステップＳ１３５に移行する。
【０１４５】
（３）ステップＳ１３５では、コントローラ１８は、第２のコンテンツに対応する転置ファイルに格納されたファイル識別子をすべて処理したか判定する。ファイル識別子をすべて処理したならば（Yes）、ブール変数値がブール判定値と等しい要素のファイル識別子を出力する（ステップＳ１３６）。一方、ファイル識別子をすべて処理していなければ（No）、ＡＮＤ演算ではステップＳ１３２に戻り、ＯＲ演算ではステップＳ１４１に、ＮＯＴ演算ではステップＳ１５１にそれぞれ戻る。
【０１４６】
第３実施形態によれば、第２実施形態の効果にさらに加えて、検索対象のコンテンツに対応する転置ファイルのアドレスを、転置ファイル割り当てテーブル１６１を用いて高速に検索することができる。さらに、複数のコンテンツの検索結果に対するＡＮＤ、ＯＲ、ＮＯＴを含むブール演算を、ファイル検索テーブル１５１を用いて高速化に実行することができる。その他の構成及び効果は前記第１，第２実施形態と同様である。
【０１４７】
［４］第４実施形態
次に、本発明の第４実施形態のストレージ装置について説明する。
【０１４８】
第４実施形態のストレージ装置では、第３実施形態の処理にさらに加えて、複数のコンテンツの検索結果に対するＡＮＤ、ＯＲ、ＮＯＴを含むブール演算のさらなる高速化が実現できる。
【０１４９】
［４−１］ハードウェア構成
本発明の第４実施形態のストレージ装置のハードウェア構成について説明する。
【０１５０】
図１８は、第４実施形態のストレージ装置のハードウェア構成を示すブロック図である。
【０１５１】
図示するように、ストレージ装置４０は、インターフェース１１、第１のメモリブロック１２、第２のメモリブロック１９、第３のメモリブロック１６、第４のメモリブロック１７、及びコントローラ１８から構成されている。
【０１５２】
第２のメモリブロック１９は、コンテンツ連想メモリ(ＣＡＭ: Content-Addressable Memory)とＲＡＭを組み合わせたＣＡＭ−ＲＡＭシステムによって構成されている。
【０１５３】
図１９を用いて、ＣＡＭ−ＲＡＭシステムについて説明する。図１９はＣＡＭ−ＲＡＭシステムの一例を示す。
【０１５４】
コンテンツ連想メモリ(ＣＡＭ)とは、アドレスの入力に対してそのアドレスが指定するデータを出力する通常メモリとは異なり、検索データの入力に対して、その検索データと全ての格納データとの一致・不一致の比較演算を同時並列に行い、一致した格納データのアドレスを出力する機能を持つ高速検索用途の特殊メモリである。また、ＣＡＭは、データの一致検索に対して、一致データの有無をMatch Flagとして出力する。
【０１５５】
ＣＡＭ−ＲＡＭシステムとは、前述したＣＡＭとアドレス指定アクセスのＲＡＭを組み合わせたシステムである。ＣＡＭの１つのエントリとＲＡＭの１つのエントリとが一対一対応するように、ＣＡＭのアドレスデコーダーとＲＡＭのアドレスエンコーダーが設計されている。
【０１５６】
キー識別子(Key ID)とそれに対応する値(value)の組をＣＡＭ−ＲＡＭシステムに格納する。すなわち、キー識別子と対応する値を、それぞれＣＡＭのエントリと対応するＲＡＭのエントリに格納する。
【０１５７】
このようなＣＡＭ−ＲＡＭシステムを用いれば、検索対象のキー識別子が登録されているかの有無判定、登録されているならば検索対象のキー識別子に対応する値の取得（キー識別子から値への変換）を、既に述べたハッシュテーブルデータ構造の場合よりも、さらに高速に行うことができる。
【０１５８】
［４−２］コンテンツ検索処理
第２のメモリブロック１９のファイル検索テーブル１９１にＣＡＭ−ＲＡＭシステムを適用した場合、以下のようになる。
【０１５９】
ＣＡＭ−ＲＡＭシステムにおけるキー識別子と値を、それぞれファイル検索テーブル１９１内のファイル識別子とブール変数にセットする。
【０１６０】
コントローラ１８は、ブール判定値を保持する記憶領域を有し、ブール判定値を管理する。そして、コントローラ１８は、第３実施形態の場合と同じ手順により、複数のコンテンツの検索結果に対するＡＮＤ、ＯＲ、ＮＯＴを含むブール演算を実施する。
【０１６１】
第４実施形態では、ファイル検索テーブル１９１にＣＡＭ−ＲＡＭシステムを用いることにより、検索対象のキー識別子が登録されているかの有無判定や、登録されているならば検索対象のキー識別子に対応する値の取得を、第３実施形態で述べたハッシュテーブルデータ構造を用いた場合よりも、さらに高速に行うことができる。これにより、複数のコンテンツの検索結果に対するＡＮＤ、ＯＲ、ＮＯＴを含むブール演算のさらなる高速化が実現できる。
【０１６２】
なおここでは、ファイル検索テーブル１９１にＣＡＭ−ＲＡＭシステムを用いる例を示したが、転置ファイル割り当てテーブル１６１やファイル割り当てテーブル１７１にＣＡＭ−ＲＡＭシステムを用いることももちろん可能である。この場合、転置ファイル割り当てテーブル１６１やファイル割り当てテーブル１７１にハッシュテーブルデータ構造を用いた場合よりも、さらに高速にコンテンツの検索処理を行うことができる。その他の構成及び効果は前記第３実施形態と同様である。
【０１６３】
以上説明したように本発明の実施形態によれば、ホストインターフェースの通信速度に制限されることなく、転置ファイルの管理及びブール演算を高速に行うことができるストレージ装置を提供できる。また、従来のストレージ装置が備えるアドレス指定書き込み/読み出し機能だけでなく、全文検索機能も備えるストレージ装置およびその効率的な実現法を提供できる。
【０１６４】
なお、前述した各実施形態はそれぞれ、単独で実施できるばかりでなく、適宜組み合せて実施することも可能である。さらに、前述した各実施形態には種々の段階の発明が含まれており、各実施形態において開示した複数の構成要件の適宜な組み合わせにより、種々の段階の発明を抽出することも可能である。
【符号の説明】
【０１６５】
１０，３０，４０…ストレージ装置、１１…ホストインターフェース、１２…第１のメモリブロック、１３，１５，１９…第２のメモリブロック、１４，１８…コントローラ、１６…第３のメモリブロック、１７…第４のメモリブロック、１０１…ＣＰＵ、１０２…メインメモリ、１２１…ファイル、１２２…転置ファイル、１３１…ファイル検索テーブル、１５１…ファイル検索テーブル、１６１…転置ファイル割り当てテーブル、１７１…ファイル割り当てテーブル、１８１…ハッシュ生成器、１９１…ファイル検索テーブル。
【図１】
2011215835.tif 000003
【図２】
2011215835.tif 000004
【図３】
2011215835.tif 000005
【図４】
2011215835.tif 000006
【図５】
2011215835.tif 000007
【図６】
2011215835.tif 000008
【図７】
2011215835.tif 000009
【図８】
2011215835.tif 000010
【図９】
2011215835.tif 000011
【図１０Ａ】
2011215835.tif 000012
【図１０Ｂ】
2011215835.tif 000013
【図１１】
2011215835.tif 000014
【図１２】
2011215835.tif 000015
【図１３】
2011215835.tif 000016
【図１４】
2011215835.tif 000017
【図１５】
2011215835.tif 000018
【図１６】
2011215835.tif 000019
【図１７】
2011215835.tif 000020
【図１８】
2011215835.tif 000021
【図１９】
2011215835.tif 000022