(57)【要約】  現在の状態をインデックスとするデフォルト遷移先情報を保持するデフォルト用メモリと、前記現在の状態と入力に基づく情報をインデックスとして前記現在の状態と前記入力が特定できるタグおよび遷移先情報を保持するイベント用メモリと、を有する検索装置であって、前記デフォルト用メモリは、ｎ枚のデフォルト用メモリユニットを備え、１つの前記現在の状態に対してｎ個の前記デフォルト遷移先情報を前記ｎ枚のデフォルト用メモリユニットに登録する。これにより、決定性有限オートマトンのメモリサイズをより一層小さくすることができる。
2009093307.tif 000002
【特許請求の範囲】
【請求項１】
現在の状態をインデックスとするデフォルト遷移先情報を保持するデフォルト用メモリと、
前記現在の状態と入力に基づく情報をインデックスとして前記現在の状態と前記入力が特定できるタグおよび遷移先情報を保持するイベント用メモリと、を有する検索装置であって、
前記デフォルト用メモリは、ｎ枚のデフォルト用メモリユニットを備え、１つの前記現在の状態に対してｎ個の前記デフォルト遷移先情報を前記ｎ枚のデフォルト用メモリユニットに登録する検索装置。
【請求項２】
請求項１に記載の検索装置において、
前記各デフォルト用メモリユニットは、入力ビットパターンに従って選択される検索装置。
【請求項３】
請求項２に記載の検索装置において、
さらに、前記入力ビットパターンをインデックスとして対応する前記デフォルト用メモリユニットの番号を得ることができるマッピングテーブルを備える検索装置。
【請求項４】
請求項２または３に記載の検索装置において、
前記入力ビットパターンは、無視文字を含む検索装置。
【請求項５】
請求項１〜４のいずれか１項に記載の検索装置において、
さらに、前記デフォルト用メモリユニットに対応したタグおよびヒット情報を登録するタグおよびヒット情報登録部を備える検索装置。
【請求項６】
請求項１〜５のいずれか１項に記載の検索装置において、
前記検索装置は、構造化文書のデータから所定の文字列を検索する検索装置。
【請求項７】
請求項６に記載の検索装置において、
前記構造化文書は、ＸＭＬ文書である検索装置。
【請求項８】
請求項１〜７のいずれか１項に記載の検索装置において、
前記各デフォルト用メモリユニットは、多重化して連想度を有する検索装置。
【請求項９】
請求項１〜８のいずれか１項に記載の検索装置において、
前記検索装置は、半導体チップ内に設けられた検索コアであり、且つ、
前記デフォルト用メモリおよび前記イベント用メモリは、前記検索コアに設けられたキャシュメモリである検索装置。
【請求項１０】
請求項９に記載の検索装置を複数結合すると共に、該各検索装置がアクセス可能な主記憶装置を備える検索サーバ。
【請求項１１】
請求項１０に記載の検索サーバと、
検索対象のデータが格納されたストレージサーバと、
前記検索サーバおよび前記ストレージサーバを管理するディレクタサーバと、を備える検索システム。
【請求項１２】
現在の状態をインデックスとするデフォルト遷移先情報をデフォルト用情報メモリに格納し、
前記現在の状態と入力に基づく情報をインデックスとして前記現在の状態と前記入力が特定できるタグおよび遷移先情報をイベント用メモリに格納する検索方法であって、
前記デフォルト用メモリへの前記デフォルト遷移先情報の格納は、１つの前記現在の状態に対してｎ個のデフォルト遷移先を登録する検索方法。
【請求項１３】
コンピュータに、
現在の状態をインデックスとするデフォルト遷移先情報をデフォルト用情報メモリに格納させる手順と、
前記現在の状態と入力に基づく情報を生成させる手順と、
前記情報をインデックスとして前記現在の状態と前記入力が特定できるタグおよび遷移先情報をイベント用メモリに格納させる手順とを実行させる検索プログラムであって、
前記デフォルト用メモリへの前記デフォルト遷移先情報の格納を、１つの前記現在の状態に対してｎ個のデフォルト遷移先を登録する検索プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本出願は、検索装置および検索方法に関し、特に、オートマトン処理技術を適用して与えられた入力文字列であるテキストから任意の文字列であるパターンを検索する検索装置および検索方法に関する。
【背景技術】
【０００２】
近年、さまざまな分野で情報量が爆発的に増加している。そして、分野によっては、情報量がギガバイトオーダーからテラバイトオーダーになりつつあり、その莫大なデータから所望のデータを短時間で取り出すことが困難になりつつある。【０００３】
与えられたテキストから任意の種類のパターンを検索するパターンマッチングは、ワープロソフトやデータベースの検索など様々な分野で応用されている。【０００４】
従来、パターンマッチングによる検索は様々な手法が知られており、例えば、決定性有限オートマトンを用いてＸＭＬ（eXtensible Markup Language）のような構造化文書のデータを検索する装置および方法が提案されている（例えば、特許文献１参照）。【０００５】
さらに、従来、テキストにハッシュ関数を適用することにより、オートマトンのメモリサイズを削減してスループットを向上する検索装置および検索方法も提案されている（例えば、特許文献２参照）。【０００６】
【特許文献１】特開２００５−０７０９１１号公報
【特許文献２】特開２００５−２４２６６８号公報
【発明の開示】
【発明が解決しようとする課題】
【０００７】
従来のオートマトンを利用した検索装置および検索方法では、検索式が多い場合や検索式が複雑な場合には、オートマトンのサイズが非常に大きくなるという問題がある。すなわち、オートマトンのサイズが大きくなると、メモリの使用量が増加し、プロセッサなどで処理する際にキャッシュミスを多発して検索速度が低下し、或いは、検索速度の低下を回避するためのハードウェアコストが大きくなるといった問題が生じる。【０００８】
さらに、特許文献２に記載された方法では、ハッシュ関数を使用するため、マッチしないテキスト文字列でもマッチしたとして検出する可能性があり、さらにオートマトンのメモリサイズを十分に削減できないという問題がある。【０００９】
本出願は、上述した従来および関連技術における課題に鑑み、決定性有限オートマトンのメモリサイズをより一層小さくすることが可能な検索装置および検索方法の提供を目的とする。
【課題を解決するための手段】
【００１０】
第１の実施形態によれば、現在の状態をインデックスとするデフォルト遷移先情報を保持するデフォルト用メモリと、前記現在の状態と入力に基づく情報をインデックスとして前記現在の状態と前記入力が特定できるタグおよび遷移先情報を保持するイベント用メモリと、を有する検索装置であって、前記デフォルト用メモリは、ｎ枚のデフォルト用メモリユニットを備え、１つの前記現在の状態に対してｎ個の前記デフォルト遷移先情報を前記ｎ枚のデフォルト用メモリユニットに登録する検索装置が提供される。【００１１】
第２の実施形態によれば、現在の状態をインデックスとするデフォルト遷移先情報をデフォルト用情報メモリに格納し、前記現在の状態と入力に基づく情報をインデックスとして前記現在の状態と前記入力が特定できるタグおよび遷移先情報をイベント用メモリに格納する検索方法であって、前記デフォルト用メモリへの前記デフォルト遷移先情報の格納は、１つの前記現在の状態に対してｎ個のデフォルト遷移先を登録する検索方法が提供される。
【発明の効果】
【００１２】
各実施形態によれば、決定性有限オートマトンのメモリサイズをより一層小さくすることが可能な検索装置および検索方法を提供することができる。
【図面の簡単な説明】
【００１３】
【図１Ａ】オートマトンによるキーワード検索アルゴリズムの一例であるシグマアルゴリズムを説明する図（その１）である。
【図１Ｂ】オートマトンによるキーワード検索アルゴリズムの一例であるシグマアルゴリズムを説明する図（その２）である。
【図２】検索装置の一例を概略的に説明するための図である。
【図３Ａ】検索装置の動作を説明するための図（その１）である。
【図３Ｂ】検索装置の動作を説明するための図（その２）である。
【図４Ａ】検索装置における処理の一例を示すフローチャート（その１）である。
【図４Ｂ】検索装置における処理の一例を示すフローチャート（その２）である。
【図４Ｃ】検索装置における処理の一例を示すフローチャート（その３）である。
【図５】関連技術としての検索装置の一例を概略的に説明するための図である。
【図６Ａ】図５に示す検索装置の動作を説明するための図（その１）である。
【図６Ｂ】図５に示す検索装置の動作を説明するための図（その２）である。
【図６Ｃ】図５に示す検索装置の動作を説明するための図（その３）である。
【図７】図５に示す検索装置におけるイベント用メモリのデータ例を示す図である。
【図８】第１実施例に係る検索装置を概略的に説明するための図である。
【図９】図８に示す検索装置におけるデフォルト用メモリの構成を説明するための図である。
【図１０Ａ】図８に示す検索装置の動作を説明するための図（その１）である。
【図１０Ｂ】図８に示す検索装置の動作を説明するための図（その２）である。
【図１１】第２実施例に係る検索装置におけるデフォルト用メモリの構成を説明するための図である。
【図１２】各実施例が適用される検索サーバの一例を概略的に示す図である。
【図１３】図１２の検索サーバを含む検索システムの全体構成を概略的に示す図である。
【符号の説明】
【００１４】
１，１１，２１    検索対象文書
２，１２，２２    入力文字
３，１３，２３    現在の状態
４，２４    デフォルト用メモリ
５，２５    次の状態
６，２６    ハッシュ器（ＸＯＲ）
７，２７    イベント用メモリ
８，２８    現在の状態，入力文字＋次の状態
９，２９    レジスタ
１０，３０    判定部
３１，１００    選択回路
ＣＨＩＰ    半導体チップ
Ｄ０〜Ｄｎ；Ｄ００〜Ｄ０３，Ｄ１０〜Ｄ１３，Ｄ２０〜Ｄ２３，    デフォルト用メモリユニット
ＭＥＭ    メモリ
ＰＢ    プロセッサボックス
ＰＧ    プロセッサグループ
ＰＭ    プロセッサモジュール
ＲＳ    ラックシステム
ＳＣ    検索コア（アクセラレータ）
ＳＳ    サーチサーバ
ＴＨ，ＴＨ０〜ＴＨ３    タグおよびヒット情報登録部
【発明を実施するための最良の形態】
【００１５】
まず、検索装置および検索方法の実施例を詳述する前に、関連技術およびその問題点を、図面を参照して説明する。【００１６】
図１Ａおよび図１Ｂはオートマトンによるキーワード検索アルゴリズムの一例であるシグマ（Ｓｉｇｍａ）アルゴリズムを説明するための図である。なお、図１Ａおよび図１Ｂは、検索対象の文書から"ｂｌｕｅ"，"ｇｒｅｅｎ"，"ｒｅｄ"および"ｙｅｌｌｏｗ"のキーワードが存在するか否かを検索する例を示している。【００１７】
まず、図１Ａに示されるように、各キーワード条件に対応したオートマトンを作成する。具体的に、"０"で示す根から、各キーワードの先頭文字"ｂ"、"ｇ"、"ｒ"、"ｙ"に遷移し、さらに、各キーワード列の文字に遷移するオートマトンを作成する。【００１８】
各キーワード列の最後の文字まで一致すれば、そのキーワード列が検索されたことになる。ここで、例えば、"ｇｒｅｅｎ"のキーワード列には、"ｒｅ"が含まれており、その後に"ｄ"があれば"ｒｅｄ"と一致するので、図１Ａに示されるように、"ｇｒｅｅｎ"の途中から"ｒｅｄ"の"ｄ"に遷移する経路が存在する。【００１９】
検索は、根から始まり、オートマトン内のキーワードがあれば順次遷移し、キーワードと関係のない文字が読み込まれたら根に戻る。【００２０】
例えば、図１Ｂに示されるように、"ｂｌａｃｋ"を含む文書が入力されると、"ｂｌｕｅ"の先頭の"ｂ"に遷移し、さらに次の"ｌ"に遷移するが、次が"ａ"であるため根に戻る。【００２１】
このように、文書内にオートマトンのキーワード列があれば、各キーワード列の最後まで到達してヒット（Ｈｉｔ）情報が出力され、キーワード列が存在することが判明する。ここで、オートマトン検索において、各キーワード列の何番目の文字にあるかをノードまたは「状態」で表す。例えば、根が状態１で、"ｂｌｕｅ"の"ｂ"にいれば状態２で、"ｕ"にいれば状態４と称する。【００２２】
図２は検索装置の一例を概略的に説明するための図であり、決定性有限オートマトンを用いた検索装置を説明するためのものである。【００２３】
図２に示されるように、ディスク装置などに格納された検索対象文書１１が流し込まれると、そこから順に文字バイトコード１２が取り出される。以下の説明では、文字バイトコード１２が８ビットで、２５６エントリを形成するものとする。【００２４】
レジスタに保持された現在の状態（現在の状態を示すデータ）１３と、文字バイトコード１２とを合わせたインデックスを、検索キーワードオートマトンを形成するメモリ１５の入力アドレス１４とする。【００２５】
入力アドレス１４が入力されたメモリ１５は出力データ１６を出力するが、この出力データには、次の状態１７およびヒット情報（ヒット値）が含まれる。そして、次の状態１７は、現在の状態１３に置き換わることになる。【００２６】
図３Ａおよび図３Ｂは検索装置の動作を説明するための図であり、図３Ａは遷移状態図を示し、図３Ｂはメモリ（１５）上のデータを概念的に示すものである。なお、ここでは、説明を簡単にするために、"ｆｏ"のキーワード列を検索する場合を例として説明する。【００２７】
まず、図３Ａに示されるように、状態１において、"ｆ"(0x66)が出現すると状態２に進む。状態２では、"ｏ"(0x6F)が出現すると状態３に進んでヒットとなり、再び"ｆ"(0x66)が出現すると状態２を維持し、それ以外の場合は、状態１に戻る。【００２８】
この検索キーワードオートマトンのメモリ上のデータは、図３Ｂに示される。なお、文字バイトコードは８ビットであり、各状態は２５６エントリ（アドレス）を有するものとする。【００２９】
図３Ｂにおいて、参照符号ＭＸは状態１からの遷移先メモリ部分を示し、ＭＹは状態２からの遷移先メモリ部分を示し、そして、ＭＺは状態３からの遷移先メモリ部分を示している。【００３０】
メモリ部分ＭＸは、状態１であることを表す0xXXXX XX部分と、各キーワード列の状態１のエントリを表す00〜ff部分を組み合わせたアドレスに対して、遷移先の次の状態（遷移先次状態）を格納する。【００３１】
具体的に、エントリを表す00〜ffのうち66で状態２に遷移し、それ以外の場合は、再び状態１を維持するので、0xXXXX XX66に状態２のアドレス0xYYYY YY00が格納され、それ以外のアドレスに対しては状態１のアドレス0xXXXX XX00が格納される。ここで、メモリ部分ＭＸのヒット情報は、ヒットしたことを示さないＮ／Ａである。【００３２】
メモリ部分ＭＹは、状態２であることを表すアドレス部分0xYYYY YYと、各キーワード列の状態２のエントリを表す00〜ffを組み合わせたアドレスに対して、遷移先次状態を格納する。【００３３】
具体的に、エントリを表す00〜ffのうち6fで状態３に遷移し、66で状態２を維持し、それ以外の場合は状態１に戻るので、0xYYYY YY6fに状態３のアドレス0xZZZZ ZZ00が格納され、0xYYYY YY66に状態２のアドレス0xYYYY YY00が格納され、それ以外のアドレスに対しては状態１のアドレス0xXXXX XX00が格納される。なお、メモリ部分ＭＹのヒット情報は、ヒットしたことを示さないＮ／Ａである。【００３４】
メモリ部分ＭＺは、状態３であることを表すアドレス部分0xZZZZ ZZと、各キーワード列の状態３のエントリを表す00〜ffを組み合わせたアドレスに対して、遷移先次状態を格納する。【００３５】
具体的に、エントリを表す00〜ffのうち66で状態２に遷移し、それ以外の場合は状態１に戻るので、0xZZZZ ZZ66に状態２のアドレス0xYYYY YY00が格納され、それ以外のアドレスに対して状態１のアドレス0xXXXX XX00が格納される。メモリ部分ＭＺのヒット情報は、ヒットしたことを示すＨＩＴである。従って、状態３のメモリＭＺまで到達すれば、キーワード列が存在することになる。【００３６】
図４Ａ〜図４Ｃは検索装置における処理の一例を示すフローチャートである。
図４Ａに示されるように、上記のようなオートマトンを利用した検索装置の処理が開始すると、まず、ステップＳＴ１において、検索条件の入力を行う。すなわち、図１Ａおよび図１Ｂの例であれば、"ｂｌｕｅ"，"ｇｒｅｅｎ"，"ｒｅｄ"，"ｙｅｌｌｏｗ"を入力し、また、図３Ａおよび図３Ｂの例であれば、"ｆｏ"を入力する。【００３７】
次に、ステップＳＴ２に進んで、入力された検索条件、すなわち、キーワード列に基づいてオートマトンの作成を行って、ステップＳＴ３に進み、メモリ上にオートマトンを構築する。【００３８】
さらに、ステップＳＴ４に進んで、検索対象文書を入力としてメモリ上のオートマトンを用いて検索を行い、ステップＳＴ５に進んで、検索結果を出力して処理を終了する。【００３９】
図４Ｂは、図４ＡのフローチャートにおけるステップＳＴ３のメモリ上にオートマトンを構築する処理を、より詳細に示すものであり、例えば、前述した図３Ｂのようなテーブルをメモリ上に構築する処理を説明するためのものである。【００４０】
まず、ステップＳＴ３１において、オートマトンのノード（状態）ごとにテーブルを作成して、ステップＳＴ３２に進み、オートマトンの辺（遷移先）を表現するために、テーブルのエントリに遷移先ノードのテーブルの先頭ポイント（アドレス）を書き込む。【００４１】
さらに、ステップＳＴ３３に進んで、最後の状態のテーブルにヒットフラグ（ＨＩＴ）を書き込む。【００４２】
図４Ｃは、図４ＡのフローチャートにおけるステップＳＴ４のメモリ上に構築したオートマトンを使用した検索処理を、より詳細に示すものである。【００４３】
まず、ステップＳＴ４１において、検索対象の文書から次の１文字を読み出し、ステップＳＴ４２に進んで、文書が終わりであるか否かを判別する。ステップＳＴ４２において、文書が終わりであると判別されると、図４ＡのステップＳＴ５に進み、文書が終わりではないと判別されると、ステップＳＴ４３に進む。【００４４】
ステップＳＴ４３では、現在の状態と読み出した文字の文字コードを入力アドレスとして、オートマトンを構築したメモリからデータの読み出しを行い、さらに、ステップＳＴ４４に進んで、読み出されたデータでキーワードがヒットするか否かを判別する。【００４５】
ステップＳＴ４４において、読み出されたデータでキーワードがヒットする、すなわち、ヒット情報が含まれる状態に到達すると判別されると、ステップＳＴ４５に進んで、ヒット情報を更新してからステップＳＴ４６に進み、読み出されたデータではキーワードがヒットしないと判別されると、そのままステップＳＴ４６に進む。【００４６】
ステップＳＴ４６では、「現在の状態」を、前述したステップＳＴ４３で読み出したデータに含まれる「次の状態」に更新してステップＳＴ４１に戻る。【００４７】
図５は関連技術としての検索装置の一例を概略的に説明するための図であり、決定性有限オートマトンのメモリサイズを小さくし、メモリ使用量およびキャッシュ利用効率を上げるようにしたものを示している。【００４８】
図５に示されるように、ディスク装置などに格納された検索対象文書２１が流し込まれると、そこから順に入力文字（バイトコード）２２が取り出される。レジスタ（２３）には、現在の状態が保持されている。【００４９】
デフォルト用メモリ２４は、現在の状態２３を入力とし、デフォルトの遷移先、すなわち、根に相当する状態が記憶されており、その状態が次の状態としてレジスタ２５に出力される。【００５０】
入力文字２２と現在の状態２３は、ハッシュ器２６に入力されると共に、レジスタ２９に入力される。なお、ハッシュ器２６は、例えば、ＸＯＲ回路であり、現在の状態２３と入力文字２２の排他的論理和を演算してイベント用メモリ２７へアクセスするためのアドレスを生成する。【００５１】
イベント用メモリ２７は、キーワード列のオートマトンを構成するメモリであり、キーワード列の文字とキーワード列における順番（状態）のＸＯＲの値をアドレスとする位置に、（現在の）状態と文字の組み、次の遷移先である次の状態、および、ヒット（ＨＩＴ）情報が格納されており、それ以外の位置にはゼロが格納されている。【００５２】
ここで、イベント用メモリ２７は、アクセス時のアドレスに応じて記憶しているデータを出力するので、キーワード列の状態と文字のＸＯＲの値がアドレスとして入力されると、キーワード列の状態と文字の組み，次の状態，および，ヒット（ＨＩＴ）情報を含む出力データ（現在の状態，入力文字＋次の状態）２８を出力し、それ以外のアドレスが入力されると、ゼロデータを出力する。ヒット情報が出力された時には、キーワード列が存在することが判明する。【００５３】
なお、デフォルト用メモリ２４およびイベント用メモリ２７は、例えば、半導体チップに内蔵された検索コア（アクセラレータ）におけるキャッシュメモリに適用することができる。このとき、デフォルト用メモリ２４およびイベント用メモリ２７は、検索コアに内蔵されたキャッシュメモリを論理的に分割して割り当てることになる。【００５４】
イベント用メモリ２７の出力データ２８のうち、状態と文字の組みは、レジスタ２９に保持された現在の状態と入力文字の組みと比較され、一致するか否かが判別される。一致すれば、キーワード列内に、現在の状態２３と入力文字２２から決定される根以外の遷移先があることを意味するので、選択回路３１でイベント用メモリ２７の出力データ２８の次の状態が選択される。一致しなければ、キーワード列内に、現在の状態（２３）と入力文字（２２）から決定される根以外の遷移先がないことを意味するので、すなわち、デフォルトの状態であるため、選択回路３１でデフォルト用メモリ２４から出力された次の状態が選択される。選択された次の状態は、現在の状態を格納するレジスタ２３に入力される。これにより、現在の状態は、選択された次の状態に置き換えられる。【００５５】
なお、上述した図５に示す関連技術の検索装置によれば、例えば、前述した図３Ｂに示すメモリ上のデータを次のように、デフォルト用メモリ２４およびイベント用メモリ２７に登録する。なお、図３Ｂにおいて、イベント用メモリ２７に登録する遷移先状態は、ハッチングにより示されている。【００５６】
すなわち、メモリ部分ＭＸにおいて、アドレス0xXXXX XX66に対応する遷移先状態（状態２のアドレス0xYYYY YY00）をイベント用メモリ２７に登録し、他のアドレス（0xXXXX XX00〜0xXXXX XX65, および, 0xXXXX XX67〜0xXXXX XXff）に対応する遷移先状態（状態１のアドレス0xXXXX XX00）をデフォルト用メモリ２４に登録する。【００５７】
また、メモリ部分ＭＹにおいて、アドレス0xYYYY YY66に対応する遷移先状態（状態２のアドレス0xYYYY YY00）およびアドレス0xYYYY YY6fに対応する遷移先状態（状態３のアドレス0xZZZZ ZZ00）をイベント用メモリ２７に登録し、他のアドレス（0xYYYY YY00〜0xYYYY YY65, 0xYYYY YY67〜0xYYYY YY6e, および, 0xYYYY YY70〜0xYYYY YYff）に対応する遷移先状態（状態１のアドレス0xXXXX XX00）をデフォルト用メモリ２４に登録する。【００５８】
さらに、メモリ部分ＭＺにおいて、アドレス0xZZZZ ZZ66に対応する遷移先状態（状態２のアドレス0xYYYY YY00）をイベント用メモリ２７に登録し、他のアドレス（0xZZZZ ZZ00〜0xZZZZ ZZ65, および, 0xZZZZ ZZ67〜0xZZZZ ZZff）に対応する遷移先状態（状態１のアドレス0xXXXX XX00）をデフォルト用メモリ２４に登録する。【００５９】
このように、図５に示す関連技術としての検索装置は、同一遷移先のエントリをデフォルト(default)遷移先として格納するデフォルト用メモリ２４と、キーワードに関連するデフォルトではない遷移先を格納するためのイベント用メモリ２７と、を備えている。なお、デフォルト用メモリ２４では、１エントリまたはある定められた入力ごとにデフォルトの遷移先を格納する。【００６０】
図６Ａ〜図６Ｃは図５に示す検索装置の動作を説明するための図であり、前述した図３Ａと同様に、キーワード"ｆｏ"を検索する場合のオートマトンと、デフォルト用メモリ２４およびイベント用メモリ２７内の格納データの内容と、を示す図である。【００６１】
図６Ａに示されるように、オートマトンの定義されていない（キーワードではない）入力の遷移先を示す点線はすべて0x00ノードに向かっているので、デフォルト用メモリ２４は、１エントリで、図６Ｂに示すような遷移先情報0x00と、ヒットしないことを示すヒット（ＨＩＴ）情報と、を格納する。すなわち、１つのキーワードについて、これだけの情報をデフォルト用メモリ２４に記憶すればよい。【００６２】
イベント用メモリ２７は、例えば、８ビットの２５６エントリの１枚構成とし、ハッシング関数として、「インデックス（アドレス）＝現在の状態のＩＤ ｘｏｒ 入力文字バイトコード」と定義する。タグは、現在の状態のＩＤのみとし、入力文字バイトコードはタグとして保持しない。【００６３】
これは、入力文字バイトコードはインデックス（アドレス）と現在の状態のＩＤから演算可能であるため、図５の構成において、イベント用メモリ２７から出力される現在の状態のＩＤと入力文字バイトコード２２から演算して出力データ２８に挿入する演算機構を設ける。もちろん、イベント用メモリ２７に入力文字バイトコード２２も格納するようにしてもよいが、その分メモリサイズが大きくなる。【００６４】
図６Ｃに示されるように、図６Ａのオートマトンのイベント用メモリ２７の格納データは0x00で示され、"ｆ"は0x66であり、そのハッシング（ＸＯＲ）値は0x66であるため、アドレス0x66には、タグとして0x00が格納され、遷移先情報として0x01が格納され、そして、ヒット情報として０（ヒットしない）が格納される。【００６５】
0x01からは、"ｆ"(0x66)で同じ状態を維持し、すなわち、0x01へ遷移するため、そのＸＯＲ値は0x67となり、アドレス0x67にタグ0x01、および、遷移先情報0x01を格納する。また、0x01からは、"ｏ"(0x6F)で0x02に遷移するため、そのＸＯＲ値は0x6Eとなり、アドレス0x6Eにタグ0x01、遷移先情報0x02を格納する。さらに、0x02からは、"ｆ"(0x66)で0x01へ遷移するため、そのＸＯＲ値は0x64となり、アドレス0x64にタグ0x02、および、遷移先情報0x01を格納する。【００６６】
次に、入力文字列"ａｆａｆｆａｆｏ"があり、この中から"ｆｏ"を検索するオートマトン処理を行う場合を説明する。【００６７】
入力"ａ"(0x61)に対して、イベント用メモリ２７のインデックスは0x61でエントリ未格納であるため、デフォルト用メモリ２４が出力する次の状態（遷移先情報）0x00が選択され、そのヒット情報は０である。現在の状態は、0x00になる。【００６８】
入力"ｆ"(0x66)に対して、イベント用メモリ２７のインデックスは0x66でタグが0x00、次の状態（遷移先情報）が0x01で、そのヒット情報は０である。タグと現在の状態が一致するので、ヒット情報は０で、現在の状態は、0x01になる。【００６９】
次の入力"ａ"(0x61)に対して、イベント用メモリ２７のインデックスは0x60でエントリ未格納であるため、デフォルト用メモリ２４が出力する次の状態（遷移先情報）0x00が選択され、そのヒット情報は０である。現在の状態は、0x00になる。【００７０】
次の入力"ｆ"(0x66)に対して、イベント用メモリ２７のインデックスは0x66でタグが0x00、次の状態（遷移先情報）が0x01で、そのヒット情報は０である。タグと現在の状態が一致するので、ヒット情報は０で、現在の状態は、0x01になる。【００７１】
次の入力"ｆ"(0x66)に対して、イベント用メモリ２７のインデックスは0x67でタグが0x01、次の状態（遷移先情報）が0x01で、そのヒット情報は０である。タグと現在の状態が一致するので、ヒット情報は０で、現在の状態は、0x01になる。【００７２】
次の入力"ａ"(0x61)に対して、イベント用メモリ２７のインデックスは0x60でエントリ未格納であるため、デフォルト用メモリ２４が出力する次の状態（遷移先情報）0x00が選択され、そのヒット情報は０である。現在の状態は、0x00になる。【００７３】
次の入力"ｆ"(0x66)に対して、イベント用メモリ２７のインデックスは0x66でタグが0x00、次の状態（遷移先情報）が0x01で、そのヒット情報は０である。タグと現在の状態が一致するので、ヒット情報は０で、現在の状態は、0x01になる。【００７４】
次の入力"o"(0x6F)に対して、イベント用メモリ２７のインデックスは0x6Eでタグが0x01、次の状態（遷移先情報）が0x01で、そのヒット情報は１である。タグと現在の状態が一致するので、ヒット情報は１で、現在の状態は、0x01になる。【００７５】
以上が、"ｆｏ"を検索する場合の例であるが、多数のキーワードを検索するオートマトンの場合も同様である。【００７６】
図７は図５に示す検索装置におけるイベント用メモリのデータ例を示す図であり、キーワード"ｂｌｕｅ"，"ｒｅｄ"，"ｙｅｌｌｏｗ"，"ｏｒａｎｇｅ"，"ｇｒｅｅｎ"，"ｐｕｒｐｌｅ"，"ｗｈｉｔｅ"を検索するオートマトンを格納したイベント用メモリ２７の利用分布（利用されるインデックス）を示すものである。【００７７】
図７から明らかなように、エントリにまだ余裕があることが分かる。すなわち、例えば、図７のようなオートマトンを実現する場合、約３６ＫＢのメモリサイズが必要であるが、図５に示す関連技術の検索装置であれば、デフォルト用メモリ２４が１４４Ｂ、イベント用メモリ２７が２０４８Ｂの合計２．１９ＫＢで十分であり、メモリサイズを約１／１６に削減することができる。【００７８】
すなわち、文字コードサイズをｎ、キーワード文字数をｋ、状態ＩＤサイズをｍとすると、メモリ容量は２n×（ｋ＋１）×ｍで表される。ｎ＝８（ビット）、ｋ＝１００、ｍ＝４とすれば、メモリ容量は約１００ＫＢになる。【００７９】
これに対して、関連技術の検索装置によれば、タグサイズをｓとすれば、メモリ容量は（ｋ＋１）×ｍ＋（ｋ＋α）×（ｓ＋ｍ）である。ｓ＝１００とすれば、メモリ容量は約２．８ＫＢになる。通常、ハッシュ値に偏りがあるため、必要なメモリ量は上記の数倍と成るが、それでも大幅なメモリ容量の低減が可能である。【００８０】
このように、図５〜図７を参照して説明した関連技術としての検索装置は、各状態の遷移先情報をデフォルト用メモリ（２４）とイベント用メモリ（２７）に分割し、ほとんどの入力の遷移先をデフォルト用メモリ（２４）に登録することでオートマトンの遷移先情報を格納するメモリサイズを削減している。【００８１】
しかしながら、１つの状態に対してそのような遷移先が複数存在する場合が考慮されていなかった。具体的に、例えば、文字照合を行うオートマトンにおいて、照合したい文字列に対応するオートマトンのほぼ全ての状態に、「スペース文字」や「タブ文字」といった無視したい文字（以下、「無視文字」とも称する）の自分自身への遷移があり、多バイト文字に対応するためには中間状態を用意して、それに遷移する必要があった。【００８２】
そのため、仮に、無視文字に１０種類の文字が定義されているとき、デフォルトの遷移先が１つしかない場合でも１０エントリのイベント用メモリが全状態数だけ必要になり、イベント用メモリが無駄に消費されてしまうことになる。
【実施例】
【００８３】
以下、検索装置および検索方法の実施例を、添付図面を参照して詳述する。
図８は第１実施例に係る検索装置を概略的に説明するための図であり、図９は図８に示す検索装置におけるデフォルト用メモリの構成を説明するための図である。【００８４】
図８に示す検索装置と前述した図５に示す関連技術としての検索装置との比較から明らかなように、本実施例の検索装置は、概略的に、デフォルト用メモリ４の構成が関連技術のもの（２４）とは異なっている。【００８５】
すなわち、図８および図９に示されるように、デフォルト用メモリ４は、１状態に複数のデフォルト遷移先を持つことができ、複数枚のデフォルト用メモリユニットＤ０〜Ｄｎ−１、デフォルト用メモリユニットＤ０〜Ｄｎ−１に対応したタグおよびヒット情報登録部ＴＨ、および、マッピングテーブルＭＴを備えている。【００８６】
マッピングテーブルＭＴは、入力ビットパターンとデフォルト用メモリユニットＤ０〜Ｄｎ−１（デフォルト用メモリユニットの番号０〜ｎ−１）との対応表であり、入力ビットパターンをインデックスとして、デフォルト用メモリユニットＤ０〜Ｄｎ−１の番号を得ることができるようになっている。【００８７】
そして、得られたデフォルト用メモリユニットの番号（０〜ｎ−１）に基づいてデフォルト用メモリユニット（Ｄ０〜Ｄｎ−１）の何れかを選択し、そのサイクルにおけるデフォルト遷移先（次の状態）とするようになっている。【００８８】
なお、他の構成は、実質的に前述した図５に示す関連技術としての検索装置と同様なので、その説明は省略する。【００８９】
ここで、デフォルト用メモリ４（デフォルト用メモリユニットＤ０〜Ｄｎ−１）およびイベント用メモリ７は、例えば、半導体チップ（ＣＨＩＰ）に内蔵された検索コア（ＳＣ：アクセラレータ）におけるキャッシュメモリに適用することができる。このとき、デフォルト用メモリ４（デフォルト用メモリユニットＤ０〜Ｄｎ−１）およびイベント用メモリ７は、検索コア（ＳＣ）に内蔵されたキャッシュメモリを論理的に分割して割り当てることになる。【００９０】
図１０Ａおよび図１０Ｂは図８に示す検索装置の動作を説明するための図であり、図１０Ａは遷移状態図を示し、図１０Ｂはメモリ上のデータを概念的に示すものである。なお、ここでは、説明を簡単にするために、"ｆｏ"のキーワード列を検索する場合を例として説明する。すなわち、図１０Ａおよび図１０Ｂは、キーワード"ｆｏ"を検索する場合のオートマトン、並びに、デフォルト用メモリ４およびイベント用メモリ７に格納されるデータの内を示している。【００９１】
図１０Ａに示されるように、オートマトンの定義されていない（キーワードではない）入力の遷移先を示す点線は、すべて0x00ノードに向かっているので、デフォルト用メモリ４は、１エントリで遷移先情報0x00を格納する。また、イベント用メモリ７は、インデックス８ビットの２５６エントリを１枚構成とし、ハッシング関数として「インデックス（アドレス）＝現在の状態のＩＤ ｘｏｒ 入力文字バイトコード」と定義する。タグは、現在の状態のＩＤのみとし、入力バイトコードは、インデックスと現在の状態のＩＤから特定可能であるため、タグとして保持しないこととする。【００９２】
ここで、0x00から0x66の入力で0x01へ遷移するので、ハッシング値は、0x00 xor 0x66 = 0x66となり、インデックス0x66にタグ0x00、遷移先情報0x01を登録する。【００９３】
0x01から0x66の入力で0x01へ遷移するので、ハッシング値は0x01 xor 0x66 = 0x67となり、インデックス0x67にタグ0x01、遷移先情報0x01を登録する。【００９４】
0x01から0x6Fの入力で0x02へ遷移するので、ハッシング値は0x01 xor 0x6F = 0x6Eとなり、インデックス0x6Eにタグ0x01、遷移先情報0x02を登録する。【００９５】
上記の条件に加えて、無視文字（無視したい文字）として次の文字が定義されているものとする。【００９６】
無視文字：
0x20 スペース文字
0x09 水平タブ文字
0x0a 改行文字【００９７】
デフォルト用メモリ４は、第１デフォルト用メモリユニットＤ１および第２デフォルト用メモリユニットＤ２の２枚のメモリユニットを備え、連想度１のキャッシュ構成（ダイレクトマップ）で、１２８個のエントリがあるものとする。なお、説明を簡略化するために、デフォルト用メモリ４が２枚のデフォルト用メモリユニットＤ１およびＤ２で構成された場合を説明するが、図９に示されるように、デフォルト用メモリ４は、ｎ枚のデフォルト用メモリユニットＤ０〜Ｄｎ−１（例えば、Ｄ０〜Ｄ７の８枚）で構成することができるのはいうまでもない。【００９８】
第１デフォルト用メモリユニットＤ１には、初期状態への遷移先が予め書き込まれ、また、第２デフォルト用メモリユニットＤ２には、無視文字の場合の遷移先が予め書き込まれているものとする。すなわち、オートマトンの各状態ビットパターン0x00, 0x01, 0x02により選択されるエントリとして、予め次のような次状態が書き込まれているものとする。【００９９】
状態      Ｄ１      Ｄ２      ヒット値（ヒット情報）
0x00      0x00      0x00            ０
0x01      0x00      0x01            ０
0x02      0x00      0x02            １【０１００】
これに対応して、マッピングテーブルＭＴには、次のように予め書き込まれている。なお、下記のデフォルト用メモリユニットの番号は、第１デフォルト用メモリユニットＤ１を選択する場合は"１"、また、第２デフォルト用メモリユニットＤ２を選択する場合は"２"としている。【０１０１】
入力ビットパターン  デフォルト用メモリユニットの番号
0x00                          １
0x01                          １
...                           １
0x08                          １
0x09                          ２
0x0a                          ２
0x0b                          １
...                           １
0x1f                          １
0x20                          ２
0x21                          １
...                           １
0xff                          １【０１０２】
次に、入力文字列"ａｆ  ａ  ｆｆａｆ  ｏ"に対して、以下のようにオートマトン処理を行う。【０１０３】
まず、初期状態は、0x00である。入力"ａ"(0x61)に対して、イベント用メモリのインデックスは0x61でエントリは未登録となっている。そこで、入力"ａ"(0x61)からマッピングテーブルを引き、第１デフォルト用メモリユニットＤ１を選択する。第１デフォルト用メモリユニットＤ１の遷移先情報は0x00でヒット値は０である。【０１０４】
次に、0x00を現在の状態とする。入力"ｆ"(0x66)に対して、イベント用メモリのインデックスは0x66でタグが0x00となり、イベント用メモリの遷移先情報は0x01となる。なお、ヒット値は０である。【０１０５】
タグと現在の状態が一致しているので、0x01を現在の状態とする。入力"  "(0x20：スペース文字；無視文字)に対して、イベント用メモリのインデックスは0x21でエントリは未登録となっている。入力"  "(0x20)からマッピングテーブルを引き第２デフォルト用メモリユニットＤ２を選択する。第２デフォルト用メモリユニットＤ２の遷移先情報は0x01で、ヒット値は０である。【０１０６】
そして、0x00を現在の状態とする。入力"ａ"(0x61)に対して、イベント用メモリのインデックスは0x60でエントリは未登録である。入力"ａ"(0x61)からマッピングテーブルを引き第１デフォルト用メモリユニットＤ１を選択する。なお、デフォルト用メモリの遷移先情報は0x00でヒット値は０である。【０１０７】
次に、0x00を現在の状態とする。入力"  "(0x20)に対して、イベント用メモリのインデックスは0x20でエントリは未登録である。入力"  "(0x20)からマッピングテーブルを引き第２デフォルト用メモリユニットＤ２を選択する。ここで、デフォルト用メモリの遷移先情報は0x00でヒット値は０である。【０１０８】
また、0x00を現在の状態とする。入力"ｆ#(0x66)に対して、イベント用メモリのインデックスは0x66でタグは0x00、そして、イベント用メモリの遷移先情報は0x01である。なお、ヒット値は０である。【０１０９】
さらに、タグと現在の状態が一致しているので、0x01を現在の状態とする。入力"ｆ"(0x66)に対して、イベント用メモリのインデックスは0x67でタグは0x01、そして、イベント用メモリの遷移先情報は0x01である。なお、ヒット値は０である。【０１１０】
また、タグと現在の状態が一致しているので、0x01を現在の状態とする。入力"ａ"(0x61)に対して、イベント用メモリのインデックスは0x60でエントリは未登録である。入力"ａ"(0x61)からマッピングテーブルを引き第１デフォルト用メモリユニットＤ１を選択する。ここで、デフォルト用メモリの遷移先情報は0x00でヒット値は０である。【０１１１】
さらに、0x00を現在の状態とする。入力"ｆ"(0x66)に対して、イベント用メモリのインデックスは0x66でタグは0x00、そして、イベント用メモリの遷移先情報は0x01である。なお、ヒット値は0である。【０１１２】
ここで、タグと現在の状態が一致しているので、0x01を現在の状態とする。入力"  "(0x20)に対して、イベント用メモリのインデックスは0x21でエントリは未登録である。入力"  "(0x20)からよりマッピングテーブルを引き第２デフォルト用メモリユニットＤ２を選択する。なお、デフォルト用メモリの遷移先情報は0x01でヒット値は０である。【０１１３】
さらに、0x01を現在の状態とする。入力"ｏ"(0x6F)に対して、イベント用メモリのインデックスは0x6Eでタグは0x01、そして、イベント用メモリの遷移先情報は0x02である。なお、ヒット値は０である。【０１１４】
そして、タグと現在の状態が一致しているので、0x02を現在の状態とする。最後に現在の状態0x02からデフォルト用メモリのヒット値(デフォルト用メモリ番号に依存せず一意に決まる)を引き、ヒット値は１でキーワードヒットとなる。【０１１５】
図１１は第２実施例に係る検索装置におけるデフォルト用メモリの構成を説明するための図であり、デフォルト用メモリユニットを多重化して連想度（現在の状態から次の状態を選ぶ）を持たせ、アドレスの衝突が生じ難くしたセットアソシエイティブ構成としたものを示している。【０１１６】
前述した図９に示す第１実施例では、デフォルト用メモリ４がｎ枚のデフォルト用メモリユニットＤ０〜Ｄｎ−１で構成されているのに対して、図１１に示す本第２実施例では、デフォルト用メモリ４を４枚重ね（４ウェイ）の３組のデフォルト用メモリユニットＤ００〜Ｄ０３，Ｄ１０〜Ｄ１３，Ｄ２０〜Ｄ２３で構成するようになっている。【０１１７】
なお、タグおよびヒット情報登録部ＴＨ０〜ＴＨ３は、各組のデフォルト用メモリユニットの重なり枚数（４枚）に応じた構成で、それぞれタグおよびヒット情報を登録できるようになっている。また、図１１では、４枚重ね（４ウェイ）の例が示されているが、この多重化の枚数（ウェイ数）は、例えば、８ウェイまたはさらに多くすることもできる。【０１１８】
ここで、デフォルト用メモリおよびイベント用メモリとして使用するメモリ容量の考察を行う。
まず、デフォルト用メモリの連想度を１、エントリ数１２８〜５１２とすると、デフォルト用メモリおよびイベント用メモリの各エントリサイズは次のようになる。【０１１９】
デフォルト用メモリ：
タグ（２７ビット程度）＋ヒット情報（３２ビット）＋次状態（３２ビット）×枚数
イベント用メモリ：
タグ（３２ビット）＋次状態（３２ビット）＋α（２ビット程度）【０１２０】
全デフォルト用メモリ（１２８〜５１２）の使用を仮定して、全ノードに付加されている遷移がある場合の増加分を比較すると、デフォルト用メモリに登録する場合は、枚数が１増えるため、４Ｂ×エントリ数（１２８〜５１２）＝０．５ＫＢ〜２ＫＢとなる。【０１２１】
イベント用メモリに登録する場合は、各ノードにつき１エントリが占有するため、ノード数×エントリサイズ（約８Ｂ）×遷移文字数＝１ＫＢ〜４ＫＢ×遷移文字数となる。従って、本実施例を適用することにより、その辺を登録するメモリ容量は、最大（遷移文字数＝１の場合）で１／２に減少することが分かる。これにより、イベント用メモリが枯渇するのを避けることができる。【０１２２】
すなわち、本実施例によれば、デフォルト用メモリ（デフォルト用メモリユニット）の容量は増加するものの、イベント用メモリの容量を大幅に低減することができるため、全体としてメモリ容量（例えば、検索コアに設けられたキャッシュメモリの容量）を低減することができる。【０１２３】
すなわち、同じメモリ容量（キャッシュメモリの容量）に対しては、キャッシュミスの頻度を低下させて検索性能を向上させることが可能になり、或いは、同じ検索性能を得る場合には、メモリ容量を削減すること可能になる。【０１２４】
このように、本実施例によれば、例えば、「スペース文字」や「タブ文字」といった無視文字が存在する場合でも、その無視文字に対するメモリの消費を低減することができ、決定性有限オートマトンのメモリサイズをより一層小さくすることが可能になる。【０１２５】
図１２は各実施例が適用される検索装置の一例を概略的に示す図であり、また、図１３は図１２の検索装置を含む検索システムの全体構成を概略的に示す図である。図１２および図１３において、参照符号ＳＳはサーチサーバ、ＲＳはラックシステム、ＰＢはプロセッサボックス、ＰＭはプロセッサモジュール、ＰＧはプロセッサグループを示している。【０１２６】
図１２では、サーチサーバＳＳは、１つのラックシステムＲＳで構成されており、そのラックシステムＲＳは、複数個（例えば、１５個）のプロセッサボックスＰＢを備え、さらに、各プロセッサボックスＰＢは、それぞれ複数枚（例えば、２８枚）のプロセッサモジュールＰＭを備えて構成されている。【０１２７】
また、各プロセッサモジュールＰＭは、それぞれ３つの半導体チップＣＨＩＰと３つのメモリＭＥＭを備え、さらに、各半導体チップＣＨＩＰは、各々が１つの処理装置ＣＰＵと４つの検索コア（アクセラレータ）ＳＣで構成される２つのプロセッサグループＰＧを備えて構成されている。【０１２８】
ここで、上述した各実施例の検索装置は、例えば、プロセッサグループＰＧに設けられた各検索コアＳＣに適用される。すなわち、各検索コアＳＣには、それぞれ高速アクセスが可能なキャシュメモリ（一時キャッシュ）が内蔵されており、このキャッシュメモリに対してオートマトンを作成して格納することになる。【０１２９】
図１３に示されるように、データ管理部は、ディレクタサーバＤＳおよびストレージサーバＳＴＲで構成され、また、検索処理部は、サーチサーバＳＳで構成される。サーチサーバＳＳは、例えば、ＬＡＮ等のネットワークＮＥＴを介してディレクタサーバＤＳに繋がれ、例えば、そのディレクタサーバＤＳに繋がれたＸＭＬのような構造化文書のデータが格納されたストレージサーバＳＴＲにおける文書データを処理する。【０１３０】
なお、図１２および図１３に示す検索装置および検索システムは単なる例であり、適用されるシステムの規模や要求される検索性能等に応じて様々に変化され得るのはいうまでもない。例えば、より大規模なシステムでは、サーチサーバＳＳを複数台のラックシステムＲＳで構成し、また、複数台のディレクタサーバＤＳにより管理を行うといった構成にすることも可能である。【０１３１】
以上、上述した各実施例は、様々に変形することが可能であり、どのような決定性有限オートマトンにも適用することができ、そのようなオートマトンを使用するワープロソフト、或いは、データベース検索などに対して幅広く適用することが可能である。
【図１Ａ】
2009093307.tif 000003
【図１Ｂ】
2009093307.tif 000004
【図２】
2009093307.tif 000005
【図３Ａ】
2009093307.tif 000006
【図３Ｂ】
2009093307.tif 000007
【図４Ａ】
2009093307.tif 000008
【図４Ｂ】
2009093307.tif 000009
【図４Ｃ】
2009093307.tif 000010
【図５】
2009093307.tif 000011
【図６Ａ】
2009093307.tif 000012
【図６Ｂ】
2009093307.tif 000013
【図６Ｃ】
2009093307.tif 000014
【図７】
2009093307.tif 000015
【図８】
2009093307.tif 000016
【図９】
2009093307.tif 000017
【図１０Ａ】
2009093307.tif 000018
【図１０Ｂ】
2009093307.tif 000019
【図１１】
2009093307.tif 000020
【図１２】
2009093307.tif 000021
【図１３】
2009093307.tif 000022
【手続補正書】
【提出日】平成22年2月24日(2010.2.24)
【手続補正１】
【補正対象書類名】特許請求の範囲
【補正対象項目名】全文
【補正方法】変更
【補正の内容】
【特許請求の範囲】
【請求項１】
現在の状態をインデックスとするデフォルト遷移先情報を保持するデフォルト用メモリと、
前記現在の状態と入力に基づく情報をインデックスとして前記現在の状態と前記入力が特定できるタグおよび遷移先情報を保持するイベント用メモリと、を有する検索装置であって、
前記デフォルト用メモリは、ｎ枚のデフォルト用メモリユニットを備え、１つの前記現在の状態に対してｎ個の前記デフォルト遷移先情報を前記ｎ枚のデフォルト用メモリユニットに登録する検索装置。
【請求項２】
請求項１に記載の検索装置において、
前記各デフォルト用メモリユニットは、入力ビットパターンに従って選択される検索装置。
【請求項３】
請求項２に記載の検索装置において、
さらに、前記入力ビットパターンをインデックスとして対応する前記デフォルト用メモリユニットの番号を得ることができるマッピングテーブルを備える検索装置。
【請求項４】
請求項１〜３のいずれか１項に記載の検索装置において、
さらに、前記デフォルト用メモリユニットに対応したタグおよびヒット情報を登録するタグおよびヒット情報登録部を備える検索装置。
【請求項５】
請求項１〜４のいずれか１項に記載の検索装置において、
前記各デフォルト用メモリユニットは、多重化して連想度を有する検索装置。
【請求項６】
請求項１〜５のいずれか１項に記載の検索装置において、
前記検索装置は、半導体チップ内に設けられた検索コアであり、且つ、
前記デフォルト用メモリおよび前記イベント用メモリは、前記検索コアに設けられたキャシュメモリである検索装置。
【請求項７】
請求項６に記載の検索装置を複数結合すると共に、該各検索装置がアクセス可能な主記憶装置を備える検索サーバ。
【請求項８】
請求項７に記載の検索サーバと、
検索対象のデータが格納されたストレージサーバと、
前記検索サーバおよび前記ストレージサーバを管理するディレクタサーバと、を備える検索システム。
【請求項９】
現在の状態をインデックスとするデフォルト遷移先情報をデフォルト用情報メモリに格納し、
前記現在の状態と入力に基づく情報をインデックスとして前記現在の状態と前記入力が特定できるタグおよび遷移先情報をイベント用メモリに格納する検索方法であって、
前記デフォルト用メモリへの前記デフォルト遷移先情報の格納は、１つの前記現在の状態に対してｎ個のデフォルト遷移先を登録する検索方法。
【請求項１０】
コンピュータに、
現在の状態をインデックスとするデフォルト遷移先情報をデフォルト用情報メモリに格納させる手順と、
前記現在の状態と入力に基づく情報を生成させる手順と、
前記情報をインデックスとして前記現在の状態と前記入力が特定できるタグおよび遷移先情報をイベント用メモリに格納させる手順とを実行させる検索プログラムであって、
前記デフォルト用メモリへの前記デフォルト遷移先情報の格納を、１つの前記現在の状態に対してｎ個のデフォルト遷移先を登録する検索プログラム。
【手続補正２】
【補正対象書類名】明細書
【補正対象項目名】全文
【補正方法】変更
【補正の内容】
【発明の詳細な説明】
【技術分野】
【０００１】
本出願は、検索装置および検索方法に関し、特に、オートマトン処理技術を適用して与えられた入力文字列であるテキストから任意の文字列であるパターンを検索する検索装置および検索方法に関する。
【背景技術】
【０００２】
近年、さまざまな分野で情報量が爆発的に増加している。そして、分野によっては、情報量がギガバイトオーダーからテラバイトオーダーになりつつあり、その莫大なデータから所望のデータを短時間で取り出すことが困難になりつつある。
【０００３】
与えられたテキストから任意の種類のパターンを検索するパターンマッチングは、ワープロソフトやデータベースの検索など様々な分野で応用されている。
【０００４】
従来、パターンマッチングによる検索は様々な手法が知られており、例えば、決定性有限オートマトンを用いてＸＭＬ（eXtensible Markup Language）のような構造化文書のデータを検索する装置および方法が提案されている（例えば、特許文献１参照）。
【０００５】
さらに、従来、テキストにハッシュ関数を適用することにより、オートマトンのメモリサイズを削減してスループットを向上する検索装置および検索方法も提案されている（例えば、特許文献２参照）。
【０００６】
【特許文献１】特開２００５−０７０９１１号公報
【特許文献２】特開２００５−２４２６６８号公報
【発明の開示】
【発明が解決しようとする課題】
【０００７】
従来のオートマトンを利用した検索装置および検索方法では、検索式が多い場合や検索式が複雑な場合には、オートマトンのサイズが非常に大きくなるという問題がある。すなわち、オートマトンのサイズが大きくなると、メモリの使用量が増加し、プロセッサなどで処理する際にキャッシュミスを多発して検索速度が低下し、或いは、検索速度の低下を回避するためのハードウェアコストが大きくなるといった問題が生じる。
【０００８】
さらに、特許文献２に記載された方法では、ハッシュ関数を使用するため、マッチしないテキスト文字列でもマッチしたとして検出する可能性があり、さらにオートマトンのメモリサイズを十分に削減できないという問題がある。
【０００９】
本出願は、上述した従来および関連技術における課題に鑑み、決定性有限オートマトンのメモリサイズをより一層小さくすることが可能な検索装置および検索方法の提供を目的とする。
【課題を解決するための手段】
【００１０】
第１の実施形態によれば、現在の状態をインデックスとするデフォルト遷移先情報を保持するデフォルト用メモリと、前記現在の状態と入力に基づく情報をインデックスとして前記現在の状態と前記入力が特定できるタグおよび遷移先情報を保持するイベント用メモリと、を有する検索装置であって、前記デフォルト用メモリは、ｎ枚のデフォルト用メモリユニットを備え、１つの前記現在の状態に対してｎ個の前記デフォルト遷移先情報を前記ｎ枚のデフォルト用メモリユニットに登録する検索装置が提供される。
【００１１】
第２の実施形態によれば、現在の状態をインデックスとするデフォルト遷移先情報をデフォルト用情報メモリに格納し、前記現在の状態と入力に基づく情報をインデックスとして前記現在の状態と前記入力が特定できるタグおよび遷移先情報をイベント用メモリに格納する検索方法であって、前記デフォルト用メモリへの前記デフォルト遷移先情報の格納は、１つの前記現在の状態に対してｎ個のデフォルト遷移先を登録する検索方法が提供される。
【発明の効果】
【００１２】
各実施形態によれば、決定性有限オートマトンのメモリサイズをより一層小さくすることが可能な検索装置および検索方法を提供することができる。
【発明を実施するための最良の形態】
【００１３】
まず、検索装置および検索方法の実施例を詳述する前に、関連技術およびその問題点を、図面を参照して説明する。
【００１４】
図１Ａおよび図１Ｂはオートマトンによるキーワード検索アルゴリズムの一例であるシグマ（Ｓｉｇｍａ）アルゴリズムを説明するための図である。なお、図１Ａおよび図１Ｂは、検索対象の文書から"ｂｌｕｅ"，"ｇｒｅｅｎ"，"ｒｅｄ"および"ｙｅｌｌｏｗ"のキーワードが存在するか否かを検索する例を示している。
【００１５】
まず、図１Ａに示されるように、各キーワード条件に対応したオートマトンを作成する。具体的に、"０"で示す根から、各キーワードの先頭文字"ｂ"、"ｇ"、"ｒ"、"ｙ"に遷移し、さらに、各キーワード列の文字に遷移するオートマトンを作成する。
【００１６】
各キーワード列の最後の文字まで一致すれば、そのキーワード列が検索されたことになる。ここで、例えば、"ｇｒｅｅｎ"のキーワード列には、"ｒｅ"が含まれており、その後に"ｄ"があれば"ｒｅｄ"と一致するので、図１Ａに示されるように、"ｇｒｅｅｎ"の途中から"ｒｅｄ"の"ｄ"に遷移する経路が存在する。
【００１７】
検索は、根から始まり、オートマトン内のキーワードがあれば順次遷移し、キーワードと関係のない文字が読み込まれたら根に戻る。
【００１８】
例えば、図１Ｂに示されるように、"ｂｌａｃｋ"を含む文書が入力されると、"ｂｌｕｅ"の先頭の"ｂ"に遷移し、さらに次の"ｌ"に遷移するが、次が"ａ"であるため根に戻る。
【００１９】
このように、文書内にオートマトンのキーワード列があれば、各キーワード列の最後まで到達してヒット（Ｈｉｔ）情報が出力され、キーワード列が存在することが判明する。ここで、オートマトン検索において、各キーワード列の何番目の文字にあるかをノードまたは「状態」で表す。例えば、根が状態１で、"ｂｌｕｅ"の"ｂ"にいれば状態２で、"ｕ"にいれば状態４と称する。
【００２０】
図２は検索装置の一例を概略的に説明するための図であり、決定性有限オートマトンを用いた検索装置を説明するためのものである。
【００２１】
図２に示されるように、ディスク装置などに格納された検索対象文書１１が流し込まれると、そこから順に文字バイトコード１２が取り出される。以下の説明では、文字バイトコード１２が８ビットで、２５６エントリを形成するものとする。
【００２２】
レジスタに保持された現在の状態（現在の状態を示すデータ）１３と、文字バイトコード１２とを合わせたインデックスを、検索キーワードオートマトンを形成するメモリ１５の入力アドレス１４とする。
【００２３】
入力アドレス１４が入力されたメモリ１５は出力データ１６を出力するが、この出力データには、次の状態１７およびヒット情報（ヒット値）が含まれる。そして、次の状態１７は、現在の状態１３に置き換わることになる。
【００２４】
図３Ａおよび図３Ｂは検索装置の動作を説明するための図であり、図３Ａは遷移状態図を示し、図３Ｂはメモリ（１５）上のデータを概念的に示すものである。なお、ここでは、説明を簡単にするために、"ｆｏ"のキーワード列を検索する場合を例として説明する。
【００２５】
まず、図３Ａに示されるように、状態１において、"ｆ"(0x66)が出現すると状態２に進む。状態２では、"ｏ"(0x6F)が出現すると状態３に進んでヒットとなり、再び"ｆ"(0x66)が出現すると状態２を維持し、それ以外の場合は、状態１に戻る。
【００２６】
この検索キーワードオートマトンのメモリ上のデータは、図３Ｂに示される。なお、文字バイトコードは８ビットであり、各状態は２５６エントリ（アドレス）を有するものとする。
【００２７】
図３Ｂにおいて、参照符号ＭＸは状態１からの遷移先メモリ部分を示し、ＭＹは状態２からの遷移先メモリ部分を示し、そして、ＭＺは状態３からの遷移先メモリ部分を示している。
【００２８】
メモリ部分ＭＸは、状態１であることを表す0xXXXX_XX部分と、各キーワード列の状態１のエントリを表す00〜ff部分を組み合わせたアドレスに対して、遷移先の次の状態（遷移先次状態）を格納する。
【００２９】
具体的に、エントリを表す00〜ffのうち66で状態２に遷移し、それ以外の場合は、再び状態１を維持するので、0xXXXX_XX66に状態２のアドレス0xYYYY_YY00が格納され、それ以外のアドレスに対しては状態１のアドレス0xXXXX_XX00が格納される。ここで、メモリ部分ＭＸのヒット情報は、ヒットしたことを示さないＮ／Ａである。
【００３０】
メモリ部分ＭＹは、状態２であることを表すアドレス部分0xYYYY_YYと、各キーワード列の状態２のエントリを表す00〜ffを組み合わせたアドレスに対して、遷移先次状態を格納する。
【００３１】
具体的に、エントリを表す00〜ffのうち6fで状態３に遷移し、66で状態２を維持し、それ以外の場合は状態１に戻るので、0xYYYY_YY6fに状態３のアドレス0xZZZZ_ZZ00が格納され、0xYYYY_YY66に状態２のアドレス0xYYYY_YY00が格納され、それ以外のアドレスに対しては状態１のアドレス0xXXXX_XX00が格納される。なお、メモリ部分ＭＹのヒット情報は、ヒットしたことを示さないＮ／Ａである。
【００３２】
メモリ部分ＭＺは、状態３であることを表すアドレス部分0xZZZZ_ZZと、各キーワード列の状態３のエントリを表す00〜ffを組み合わせたアドレスに対して、遷移先次状態を格納する。
【００３３】
具体的に、エントリを表す00〜ffのうち66で状態２に遷移し、それ以外の場合は状態１に戻るので、0xZZZZ_ZZ66に状態２のアドレス0xYYYY_YY00が格納され、それ以外のアドレスに対して状態１のアドレス0xXXXX_XX00が格納される。メモリ部分ＭＺのヒット情報は、ヒットしたことを示すＨＩＴである。従って、状態３のメモリＭＺまで到達すれば、キーワード列が存在することになる。
【００３４】
図４Ａ〜図４Ｃは検索装置における処理の一例を示すフローチャートである。
図４Ａに示されるように、上記のようなオートマトンを利用した検索装置の処理が開始すると、まず、ステップＳＴ１において、検索条件の入力を行う。すなわち、図１Ａおよび図１Ｂの例であれば、"ｂｌｕｅ"，"ｇｒｅｅｎ"，"ｒｅｄ"，"ｙｅｌｌｏｗ"を入力し、また、図３Ａおよび図３Ｂの例であれば、"ｆｏ"を入力する。
【００３５】
次に、ステップＳＴ２に進んで、入力された検索条件、すなわち、キーワード列に基づいてオートマトンの作成を行って、ステップＳＴ３に進み、メモリ上にオートマトンを構築する。
【００３６】
さらに、ステップＳＴ４に進んで、検索対象文書を入力としてメモリ上のオートマトンを用いて検索を行い、ステップＳＴ５に進んで、検索結果を出力して処理を終了する。
【００３７】
図４Ｂは、図４ＡのフローチャートにおけるステップＳＴ３のメモリ上にオートマトンを構築する処理を、より詳細に示すものであり、例えば、前述した図３Ｂのようなテーブルをメモリ上に構築する処理を説明するためのものである。
【００３８】
まず、ステップＳＴ３１において、オートマトンのノード（状態）ごとにテーブルを作成して、ステップＳＴ３２に進み、オートマトンの辺（遷移先）を表現するために、テーブルのエントリに遷移先ノードのテーブルの先頭ポイント（アドレス）を書き込む。
【００３９】
さらに、ステップＳＴ３３に進んで、最後の状態のテーブルにヒットフラグ（ＨＩＴ）を書き込む。
【００４０】
図４Ｃは、図４ＡのフローチャートにおけるステップＳＴ４のメモリ上に構築したオートマトンを使用した検索処理を、より詳細に示すものである。
【００４１】
まず、ステップＳＴ４１において、検索対象の文書から次の１文字を読み出し、ステップＳＴ４２に進んで、文書が終わりであるか否かを判別する。ステップＳＴ４２において、文書が終わりであると判別されると、図４ＡのステップＳＴ５に進み、文書が終わりではないと判別されると、ステップＳＴ４３に進む。
【００４２】
ステップＳＴ４３では、現在の状態と読み出した文字の文字コードを入力アドレスとして、オートマトンを構築したメモリからデータの読み出しを行い、さらに、ステップＳＴ４４に進んで、読み出されたデータでキーワードがヒットするか否かを判別する。
【００４３】
ステップＳＴ４４において、読み出されたデータでキーワードがヒットする、すなわち、ヒット情報が含まれる状態に到達すると判別されると、ステップＳＴ４５に進んで、ヒット情報を更新してからステップＳＴ４６に進み、読み出されたデータではキーワードがヒットしないと判別されると、そのままステップＳＴ４６に進む。
【００４４】
ステップＳＴ４６では、「現在の状態」を、前述したステップＳＴ４３で読み出したデータに含まれる「次の状態」に更新してステップＳＴ４１に戻る。
【００４５】
図５は関連技術としての検索装置の一例を概略的に説明するための図であり、決定性有限オートマトンのメモリサイズを小さくし、メモリ使用量およびキャッシュ利用効率を上げるようにしたものを示している。
【００４６】
図５に示されるように、ディスク装置などに格納された検索対象文書２１が流し込まれると、そこから順に入力文字（バイトコード）２２が取り出される。レジスタ（２３）には、現在の状態が保持されている。
【００４７】
デフォルト用メモリ２４は、現在の状態２３を入力とし、デフォルトの遷移先、すなわち、根に相当する状態が記憶されており、その状態が次の状態としてレジスタ２５に出力される。
【００４８】
入力文字２２と現在の状態２３は、ハッシュ器２６に入力されると共に、レジスタ２９に入力される。なお、ハッシュ器２６は、例えば、ＸＯＲ回路であり、現在の状態２３と入力文字２２の排他的論理和を演算してイベント用メモリ２７へアクセスするためのアドレスを生成する。
【００４９】
イベント用メモリ２７は、キーワード列のオートマトンを構成するメモリであり、キーワード列の文字とキーワード列における順番（状態）のＸＯＲの値をアドレスとする位置に、（現在の）状態と文字の組み、次の遷移先である次の状態、および、ヒット（ＨＩＴ）情報が格納されており、それ以外の位置にはゼロが格納されている。
【００５０】
ここで、イベント用メモリ２７は、アクセス時のアドレスに応じて記憶しているデータを出力するので、キーワード列の状態と文字のＸＯＲの値がアドレスとして入力されると、キーワード列の状態と文字の組み，次の状態，および，ヒット（ＨＩＴ）情報を含む出力データ（現在の状態，入力文字＋次の状態）２８を出力し、それ以外のアドレスが入力されると、ゼロデータを出力する。ヒット情報が出力された時には、キーワード列が存在することが判明する。
【００５１】
なお、デフォルト用メモリ２４およびイベント用メモリ２７は、例えば、半導体チップに内蔵された検索コア（アクセラレータ）におけるキャッシュメモリに適用することができる。このとき、デフォルト用メモリ２４およびイベント用メモリ２７は、検索コアに内蔵されたキャッシュメモリを論理的に分割して割り当てることになる。
【００５２】
イベント用メモリ２７の出力データ２８のうち、状態と文字の組みは、レジスタ２９に保持された現在の状態と入力文字の組みと比較され、一致するか否かが判別される。一致すれば、キーワード列内に、現在の状態２３と入力文字２２から決定される根以外の遷移先があることを意味するので、選択回路３１でイベント用メモリ２７の出力データ２８の次の状態が選択される。一致しなければ、キーワード列内に、現在の状態（２３）と入力文字（２２）から決定される根以外の遷移先がないことを意味するので、すなわち、デフォルトの状態であるため、選択回路３１でデフォルト用メモリ２４から出力された次の状態が選択される。選択された次の状態は、現在の状態を格納するレジスタ２３に入力される。これにより、現在の状態は、選択された次の状態に置き換えられる。
【００５３】
なお、上述した図５に示す関連技術の検索装置によれば、例えば、前述した図３Ｂに示すメモリ上のデータを次のように、デフォルト用メモリ２４およびイベント用メモリ２７に登録する。なお、図３Ｂにおいて、イベント用メモリ２７に登録する遷移先状態は、ハッチングにより示されている。
【００５４】
すなわち、メモリ部分ＭＸにおいて、アドレス0xXXXX_XX66に対応する遷移先状態（状態２のアドレス0xYYYY_YY00）をイベント用メモリ２７に登録し、他のアドレス（0xXXXX_XX00〜0xXXXX_XX65, および, 0xXXXX_XX67〜0xXXXX_XXff）に対応する遷移先状態（状態１のアドレス0xXXXX_XX00）をデフォルト用メモリ２４に登録する。
【００５５】
また、メモリ部分ＭＹにおいて、アドレス0xYYYY_YY66に対応する遷移先状態（状態２のアドレス0xYYYY_YY00）およびアドレス0xYYYY_YY6fに対応する遷移先状態（状態３のアドレス0xZZZZ_ZZ00）をイベント用メモリ２７に登録し、他のアドレス（0xYYYY_YY00〜0xYYYY_YY65, 0xYYYY_YY67〜0xYYYY_YY6e, および, 0xYYYY_YY70〜0xYYYY_YYff）に対応する遷移先状態（状態１のアドレス0xXXXX_XX00）をデフォルト用メモリ２４に登録する。
【００５６】
さらに、メモリ部分ＭＺにおいて、アドレス0xZZZZ_ZZ66に対応する遷移先状態（状態２のアドレス0xYYYY_YY00）をイベント用メモリ２７に登録し、他のアドレス（0xZZZZ_ZZ00〜0xZZZZ_ZZ65, および, 0xZZZZ_ZZ67〜0xZZZZ_ZZff）に対応する遷移先状態（状態１のアドレス0xXXXX_XX00）をデフォルト用メモリ２４に登録する。
【００５７】
このように、図５に示す関連技術としての検索装置は、同一遷移先のエントリをデフォルト(default)遷移先として格納するデフォルト用メモリ２４と、キーワードに関連するデフォルトではない遷移先を格納するためのイベント用メモリ２７と、を備えている。なお、デフォルト用メモリ２４では、１エントリまたはある定められた入力ごとにデフォルトの遷移先を格納する。
【００５８】
図６Ａ〜図６Ｃは図５に示す検索装置の動作を説明するための図であり、前述した図３Ａと同様に、キーワード"ｆｏ"を検索する場合のオートマトンと、デフォルト用メモリ２４およびイベント用メモリ２７内の格納データの内容と、を示す図である。
【００５９】
図６Ａに示されるように、オートマトンの定義されていない（キーワードではない）入力の遷移先を示す点線はすべて0x00ノードに向かっているので、デフォルト用メモリ２４は、１エントリで、図６Ｂに示すような遷移先情報0x00と、ヒットしないことを示すヒット（ＨＩＴ）情報と、を格納する。すなわち、１つのキーワードについて、これだけの情報をデフォルト用メモリ２４に記憶すればよい。
【００６０】
イベント用メモリ２７は、例えば、８ビットの２５６エントリの１枚構成とし、ハッシング関数として、「インデックス（アドレス）＝現在の状態のＩＤ ｘｏｒ 入力文字バイトコード」と定義する。タグは、現在の状態のＩＤのみとし、入力文字バイトコードはタグとして保持しない。
【００６１】
これは、入力文字バイトコードはインデックス（アドレス）と現在の状態のＩＤから演算可能であるため、図５の構成において、イベント用メモリ２７から出力される現在の状態のＩＤと入力文字バイトコード２２から演算して出力データ２８に挿入する演算機構を設ける。もちろん、イベント用メモリ２７に入力文字バイトコード２２も格納するようにしてもよいが、その分メモリサイズが大きくなる。
【００６２】
図６Ｃに示されるように、図６Ａのオートマトンのイベント用メモリ２７の格納データは0x00で示され、"ｆ"は0x66であり、そのハッシング（ＸＯＲ）値は0x66であるため、アドレス0x66には、タグとして0x00が格納され、遷移先情報として0x01が格納され、そして、ヒット情報として０（ヒットしない）が格納される。
【００６３】
0x01からは、"ｆ"(0x66)で同じ状態を維持し、すなわち、0x01へ遷移するため、そのＸＯＲ値は0x67となり、アドレス0x67にタグ0x01、および、遷移先情報0x01を格納する。また、0x01からは、"ｏ"(0x6F)で0x02に遷移するため、そのＸＯＲ値は0x6Eとなり、アドレス0x6Eにタグ0x01、遷移先情報0x02を格納する。さらに、0x02からは、"ｆ"(0x66)で0x01へ遷移するため、そのＸＯＲ値は0x64となり、アドレス0x64にタグ0x02、および、遷移先情報0x01を格納する。
【００６４】
次に、入力文字列"ａｆａｆｆａｆｏ"があり、この中から"ｆｏ"を検索するオートマトン処理を行う場合を説明する。
【００６５】
入力"ａ"(0x61)に対して、イベント用メモリ２７のインデックスは0x61でエントリ未格納であるため、デフォルト用メモリ２４が出力する次の状態（遷移先情報）0x00が選択され、そのヒット情報は０である。現在の状態は、0x00になる。
【００６６】
入力"ｆ"(0x66)に対して、イベント用メモリ２７のインデックスは0x66でタグが0x00、次の状態（遷移先情報）が0x01で、そのヒット情報は０である。タグと現在の状態が一致するので、ヒット情報は０で、現在の状態は、0x01になる。
【００６７】
次の入力"ａ"(0x61)に対して、イベント用メモリ２７のインデックスは0x60でエントリ未格納であるため、デフォルト用メモリ２４が出力する次の状態（遷移先情報）0x00が選択され、そのヒット情報は０である。現在の状態は、0x00になる。
【００６８】
次の入力"ｆ"(0x66)に対して、イベント用メモリ２７のインデックスは0x66でタグが0x00、次の状態（遷移先情報）が0x01で、そのヒット情報は０である。タグと現在の状態が一致するので、ヒット情報は０で、現在の状態は、0x01になる。
【００６９】
次の入力"ｆ"(0x66)に対して、イベント用メモリ２７のインデックスは0x67でタグが0x01、次の状態（遷移先情報）が0x01で、そのヒット情報は０である。タグと現在の状態が一致するので、ヒット情報は０で、現在の状態は、0x01になる。
【００７０】
次の入力"ａ"(0x61)に対して、イベント用メモリ２７のインデックスは0x60でエントリ未格納であるため、デフォルト用メモリ２４が出力する次の状態（遷移先情報）0x00が選択され、そのヒット情報は０である。現在の状態は、0x00になる。
【００７１】
次の入力"ｆ"(0x66)に対して、イベント用メモリ２７のインデックスは0x66でタグが0x00、次の状態（遷移先情報）が0x01で、そのヒット情報は０である。タグと現在の状態が一致するので、ヒット情報は０で、現在の状態は、0x01になる。
【００７２】
次の入力"o"(0x6F)に対して、イベント用メモリ２７のインデックスは0x6Eでタグが0x01、次の状態（遷移先情報）が0x01で、そのヒット情報は１である。タグと現在の状態が一致するので、ヒット情報は１で、現在の状態は、0x01になる。
【００７３】
以上が、"ｆｏ"を検索する場合の例であるが、多数のキーワードを検索するオートマトンの場合も同様である。
【００７４】
図７は図５に示す検索装置におけるイベント用メモリのデータ例を示す図であり、キーワード"ｂｌｕｅ"，"ｒｅｄ"，"ｙｅｌｌｏｗ"，"ｏｒａｎｇｅ"，"ｇｒｅｅｎ"，"ｐｕｒｐｌｅ"，"ｗｈｉｔｅ"を検索するオートマトンを格納したイベント用メモリ２７の利用分布（利用されるインデックス）を示すものである。
【００７５】
図７から明らかなように、エントリにまだ余裕があることが分かる。すなわち、例えば、図７のようなオートマトンを実現する場合、約３６ＫＢのメモリサイズが必要であるが、図５に示す関連技術の検索装置であれば、デフォルト用メモリ２４が１４４Ｂ、イベント用メモリ２７が２０４８Ｂの合計２．１９ＫＢで十分であり、メモリサイズを約１／１６に削減することができる。
【００７６】
すなわち、文字コードサイズをｎ、キーワード文字数をｋ、状態ＩＤサイズをｍとすると、メモリ容量は２n×（ｋ＋１）×ｍで表される。ｎ＝８（ビット）、ｋ＝１００、ｍ＝４とすれば、メモリ容量は約１００ＫＢになる。
【００７７】
これに対して、関連技術の検索装置によれば、タグサイズをｓとすれば、メモリ容量は（ｋ＋１）×ｍ＋（ｋ＋α）×（ｓ＋ｍ）である。ｓ＝１００とすれば、メモリ容量は約２．８ＫＢになる。通常、ハッシュ値に偏りがあるため、必要なメモリ量は上記の数倍と成るが、それでも大幅なメモリ容量の低減が可能である。
【００７８】
このように、図５〜図７を参照して説明した関連技術としての検索装置は、各状態の遷移先情報をデフォルト用メモリ（２４）とイベント用メモリ（２７）に分割し、ほとんどの入力の遷移先をデフォルト用メモリ（２４）に登録することでオートマトンの遷移先情報を格納するメモリサイズを削減している。
【００７９】
しかしながら、１つの状態に対してそのような遷移先が複数存在する場合が考慮されていなかった。具体的に、例えば、文字照合を行うオートマトンにおいて、照合したい文字列に対応するオートマトンのほぼ全ての状態に、「スペース文字」や「タブ文字」といった無視したい文字（以下、「無視文字」とも称する）の自分自身への遷移があり、多バイト文字に対応するためには中間状態を用意して、それに遷移する必要があった。
【００８０】
そのため、仮に、無視文字に１０種類の文字が定義されているとき、デフォルトの遷移先が１つしかない場合でも１０エントリのイベント用メモリが全状態数だけ必要になり、イベント用メモリが無駄に消費されてしまうことになる。
【実施例】
【００８１】
以下、検索装置および検索方法の実施例を、添付図面を参照して詳述する。
図８は第１実施例に係る検索装置を概略的に説明するための図であり、図９は図８に示す検索装置におけるデフォルト用メモリの構成を説明するための図である。
【００８２】
図８に示す検索装置と前述した図５に示す関連技術としての検索装置との比較から明らかなように、本実施例の検索装置は、概略的に、デフォルト用メモリ４の構成が関連技術のもの（２４）とは異なっている。
【００８３】
すなわち、図８および図９に示されるように、デフォルト用メモリ４は、１状態に複数のデフォルト遷移先を持つことができ、複数枚のデフォルト用メモリユニットＤ０〜Ｄｎ−１、デフォルト用メモリユニットＤ０〜Ｄｎ−１に対応したタグおよびヒット情報登録部ＴＨ、および、マッピングテーブルＭＴを備えている。
【００８４】
マッピングテーブルＭＴは、入力ビットパターンとデフォルト用メモリユニットＤ０〜Ｄｎ−１（デフォルト用メモリユニットの番号０〜ｎ−１）との対応表であり、入力ビットパターンをインデックスとして、デフォルト用メモリユニットＤ０〜Ｄｎ−１の番号を得ることができるようになっている。
【００８５】
そして、得られたデフォルト用メモリユニットの番号（０〜ｎ−１）に基づいてデフォルト用メモリユニット（Ｄ０〜Ｄｎ−１）の何れかを選択し、そのサイクルにおけるデフォルト遷移先（次の状態）とするようになっている。
【００８６】
なお、他の構成は、実質的に前述した図５に示す関連技術としての検索装置と同様なので、その説明は省略する。
【００８７】
ここで、デフォルト用メモリ４（デフォルト用メモリユニットＤ０〜Ｄｎ−１）およびイベント用メモリ７は、例えば、半導体チップ（ＣＨＩＰ）に内蔵された検索コア（ＳＣ：アクセラレータ）におけるキャッシュメモリに適用することができる。このとき、デフォルト用メモリ４（デフォルト用メモリユニットＤ０〜Ｄｎ−１）およびイベント用メモリ７は、検索コア（ＳＣ）に内蔵されたキャッシュメモリを論理的に分割して割り当てることになる。
【００８８】
図１０Ａおよび図１０Ｂは図８に示す検索装置の動作を説明するための図であり、図１０Ａは遷移状態図を示し、図１０Ｂはメモリ上のデータを概念的に示すものである。なお、ここでは、説明を簡単にするために、"ｆｏ"のキーワード列を検索する場合を例として説明する。すなわち、図１０Ａおよび図１０Ｂは、キーワード"ｆｏ"を検索する場合のオートマトン、並びに、デフォルト用メモリ４およびイベント用メモリ７に格納されるデータの内を示している。
【００８９】
図１０Ａに示されるように、オートマトンの定義されていない（キーワードではない）入力の遷移先を示す点線は、すべて0x00ノードに向かっているので、デフォルト用メモリ４は、１エントリで遷移先情報0x00を格納する。また、イベント用メモリ７は、インデックス８ビットの２５６エントリを１枚構成とし、ハッシング関数として「インデックス（アドレス）＝現在の状態のＩＤ ｘｏｒ 入力文字バイトコード」と定義する。タグは、現在の状態のＩＤのみとし、入力バイトコードは、インデックスと現在の状態のＩＤから特定可能であるため、タグとして保持しないこととする。
【００９０】
ここで、0x00から0x66の入力で0x01へ遷移するので、ハッシング値は、0x00 xor 0x66 = 0x66となり、インデックス0x66にタグ0x00、遷移先情報0x01を登録する。
【００９１】
0x01から0x66の入力で0x01へ遷移するので、ハッシング値は0x01 xor 0x66 = 0x67となり、インデックス0x67にタグ0x01、遷移先情報0x01を登録する。
【００９２】
0x01から0x6Fの入力で0x02へ遷移するので、ハッシング値は0x01 xor 0x6F = 0x6Eとなり、インデックス0x6Eにタグ0x01、遷移先情報0x02を登録する。
【００９３】
上記の条件に加えて、無視文字（無視したい文字）として次の文字が定義されているものとする。
【００９４】
無視文字：
0x20 スペース文字
0x09 水平タブ文字
0x0a 改行文字
【００９５】
デフォルト用メモリ４は、第１デフォルト用メモリユニットＤ１および第２デフォルト用メモリユニットＤ２の２枚のメモリユニットを備え、連想度１のキャッシュ構成（ダイレクトマップ）で、１２８個のエントリがあるものとする。なお、説明を簡略化するために、デフォルト用メモリ４が２枚のデフォルト用メモリユニットＤ１およびＤ２で構成された場合を説明するが、図９に示されるように、デフォルト用メモリ４は、ｎ枚のデフォルト用メモリユニットＤ０〜Ｄｎ−１（例えば、Ｄ０〜Ｄ７の８枚）で構成することができるのはいうまでもない。
【００９６】
第１デフォルト用メモリユニットＤ１には、初期状態への遷移先が予め書き込まれ、また、第２デフォルト用メモリユニットＤ２には、無視文字の場合の遷移先が予め書き込まれているものとする。すなわち、オートマトンの各状態ビットパターン0x00, 0x01, 0x02により選択されるエントリとして、予め次のような次状態が書き込まれているものとする。
【００９７】
状態      Ｄ１      Ｄ２      ヒット値（ヒット情報）
0x00      0x00      0x00            ０
0x01      0x00      0x01            ０
0x02      0x00      0x02            １
【００９８】
これに対応して、マッピングテーブルＭＴには、次のように予め書き込まれている。なお、下記のデフォルト用メモリユニットの番号は、第１デフォルト用メモリユニットＤ１を選択する場合は"１"、また、第２デフォルト用メモリユニットＤ２を選択する場合は"２"としている。
【００９９】
入力ビットパターン  デフォルト用メモリユニットの番号
0x00                          １
0x01                          １
...                           １
0x08                          １
0x09                          ２
0x0a                          ２
0x0b                          １
...                           １
0x1f                          １
0x20                          ２
0x21                          １
...                           １
0xff                          １
【０１００】
次に、入力文字列"ａｆ  ａ  ｆｆａｆ  ｏ"に対して、以下のようにオートマトン処理を行う。
【０１０１】
まず、初期状態は、0x00である。入力"ａ"(0x61)に対して、イベント用メモリのインデックスは0x61でエントリは未登録となっている。そこで、入力"ａ"(0x61)からマッピングテーブルを引き、第１デフォルト用メモリユニットＤ１を選択する。第１デフォルト用メモリユニットＤ１の遷移先情報は0x00でヒット値は０である。
【０１０２】
次に、0x00を現在の状態とする。入力"ｆ"(0x66)に対して、イベント用メモリのインデックスは0x66でタグが0x00となり、イベント用メモリの遷移先情報は0x01となる。なお、ヒット値は０である。
【０１０３】
タグと現在の状態が一致しているので、0x01を現在の状態とする。入力"  "(0x20：スペース文字；無視文字)に対して、イベント用メモリのインデックスは0x21でエントリは未登録となっている。入力"  "(0x20)からマッピングテーブルを引き第２デフォルト用メモリユニットＤ２を選択する。第２デフォルト用メモリユニットＤ２の遷移先情報は0x01で、ヒット値は０である。
【０１０４】
そして、0x00を現在の状態とする。入力"ａ"(0x61)に対して、イベント用メモリのインデックスは0x60でエントリは未登録である。入力"ａ"(0x61)からマッピングテーブルを引き第１デフォルト用メモリユニットＤ１を選択する。なお、デフォルト用メモリの遷移先情報は0x00でヒット値は０である。
【０１０５】
次に、0x00を現在の状態とする。入力"  "(0x20)に対して、イベント用メモリのインデックスは0x20でエントリは未登録である。入力"  "(0x20)からマッピングテーブルを引き第２デフォルト用メモリユニットＤ２を選択する。ここで、デフォルト用メモリの遷移先情報は0x00でヒット値は０である。
【０１０６】
また、0x00を現在の状態とする。入力"ｆ#(0x66)に対して、イベント用メモリのインデックスは0x66でタグは0x00、そして、イベント用メモリの遷移先情報は0x01である。なお、ヒット値は０である。
【０１０７】
さらに、タグと現在の状態が一致しているので、0x01を現在の状態とする。入力"ｆ"(0x66)に対して、イベント用メモリのインデックスは0x67でタグは0x01、そして、イベント用メモリの遷移先情報は0x01である。なお、ヒット値は０である。
【０１０８】
また、タグと現在の状態が一致しているので、0x01を現在の状態とする。入力"ａ"(0x61)に対して、イベント用メモリのインデックスは0x60でエントリは未登録である。入力"ａ"(0x61)からマッピングテーブルを引き第１デフォルト用メモリユニットＤ１を選択する。ここで、デフォルト用メモリの遷移先情報は0x00でヒット値は０である。
【０１０９】
さらに、0x00を現在の状態とする。入力"ｆ"(0x66)に対して、イベント用メモリのインデックスは0x66でタグは0x00、そして、イベント用メモリの遷移先情報は0x01である。なお、ヒット値は0である。
【０１１０】
ここで、タグと現在の状態が一致しているので、0x01を現在の状態とする。入力"  "(0x20)に対して、イベント用メモリのインデックスは0x21でエントリは未登録である。入力"  "(0x20)からよりマッピングテーブルを引き第２デフォルト用メモリユニットＤ２を選択する。なお、デフォルト用メモリの遷移先情報は0x01でヒット値は０である。
【０１１１】
さらに、0x01を現在の状態とする。入力"ｏ"(0x6F)に対して、イベント用メモリのインデックスは0x6Eでタグは0x01、そして、イベント用メモリの遷移先情報は0x02である。なお、ヒット値は０である。
【０１１２】
そして、タグと現在の状態が一致しているので、0x02を現在の状態とする。最後に現在の状態0x02からデフォルト用メモリのヒット値(デフォルト用メモリ番号に依存せず一意に決まる)を引き、ヒット値は１でキーワードヒットとなる。
【０１１３】
図１１は第２実施例に係る検索装置におけるデフォルト用メモリの構成を説明するための図であり、デフォルト用メモリユニットを多重化して連想度（現在の状態から次の状態を選ぶ）を持たせ、アドレスの衝突が生じ難くしたセットアソシエイティブ構成としたものを示している。
【０１１４】
前述した図９に示す第１実施例では、デフォルト用メモリ４がｎ枚のデフォルト用メモリユニットＤ０〜Ｄｎ−１で構成されているのに対して、図１１に示す本第２実施例では、デフォルト用メモリ４を４枚重ね（４ウェイ）の３組のデフォルト用メモリユニットＤ００〜Ｄ０３，Ｄ１０〜Ｄ１３，Ｄ２０〜Ｄ２３で構成するようになっている。
【０１１５】
なお、タグおよびヒット情報登録部ＴＨ０〜ＴＨ３は、各組のデフォルト用メモリユニットの重なり枚数（４枚）に応じた構成で、それぞれタグおよびヒット情報を登録できるようになっている。また、図１１では、４枚重ね（４ウェイ）の例が示されているが、この多重化の枚数（ウェイ数）は、例えば、８ウェイまたはさらに多くすることもできる。
【０１１６】
ここで、デフォルト用メモリおよびイベント用メモリとして使用するメモリ容量の考察を行う。
まず、デフォルト用メモリの連想度を１、エントリ数１２８〜５１２とすると、デフォルト用メモリおよびイベント用メモリの各エントリサイズは次のようになる。
【０１１７】
デフォルト用メモリ：
タグ（２７ビット程度）＋ヒット情報（３２ビット）＋次状態（３２ビット）×枚数
イベント用メモリ：
タグ（３２ビット）＋次状態（３２ビット）＋α（２ビット程度）
【０１１８】
全デフォルト用メモリ（１２８〜５１２）の使用を仮定して、全ノードに付加されている遷移がある場合の増加分を比較すると、デフォルト用メモリに登録する場合は、枚数が１増えるため、４Ｂ×エントリ数（１２８〜５１２）＝０．５ＫＢ〜２ＫＢとなる。
【０１１９】
イベント用メモリに登録する場合は、各ノードにつき１エントリが占有するため、ノード数×エントリサイズ（約８Ｂ）×遷移文字数＝１ＫＢ〜４ＫＢ×遷移文字数となる。従って、本実施例を適用することにより、その辺を登録するメモリ容量は、最大（遷移文字数＝１の場合）で１／２に減少することが分かる。これにより、イベント用メモリが枯渇するのを避けることができる。
【０１２０】
すなわち、本実施例によれば、デフォルト用メモリ（デフォルト用メモリユニット）の容量は増加するものの、イベント用メモリの容量を大幅に低減することができるため、全体としてメモリ容量（例えば、検索コアに設けられたキャッシュメモリの容量）を低減することができる。
【０１２１】
すなわち、同じメモリ容量（キャッシュメモリの容量）に対しては、キャッシュミスの頻度を低下させて検索性能を向上させることが可能になり、或いは、同じ検索性能を得る場合には、メモリ容量を削減すること可能になる。
【０１２２】
このように、本実施例によれば、例えば、「スペース文字」や「タブ文字」といった無視文字が存在する場合でも、その無視文字に対するメモリの消費を低減することができ、決定性有限オートマトンのメモリサイズをより一層小さくすることが可能になる。
【０１２３】
図１２は各実施例が適用される検索装置の一例を概略的に示す図であり、また、図１３は図１２の検索装置を含む検索システムの全体構成を概略的に示す図である。図１２および図１３において、参照符号ＳＳはサーチサーバ、ＲＳはラックシステム、ＰＢはプロセッサボックス、ＰＭはプロセッサモジュール、ＰＧはプロセッサグループを示している。
【０１２４】
図１２では、サーチサーバＳＳは、１つのラックシステムＲＳで構成されており、そのラックシステムＲＳは、複数個（例えば、１５個）のプロセッサボックスＰＢを備え、さらに、各プロセッサボックスＰＢは、それぞれ複数枚（例えば、２８枚）のプロセッサモジュールＰＭを備えて構成されている。
【０１２５】
また、各プロセッサモジュールＰＭは、それぞれ３つの半導体チップＣＨＩＰと３つのメモリＭＥＭを備え、さらに、各半導体チップＣＨＩＰは、各々が１つの処理装置ＣＰＵと４つの検索コア（アクセラレータ）ＳＣで構成される２つのプロセッサグループＰＧを備えて構成されている。
【０１２６】
ここで、上述した各実施例の検索装置は、例えば、プロセッサグループＰＧに設けられた各検索コアＳＣに適用される。すなわち、各検索コアＳＣには、それぞれ高速アクセスが可能なキャシュメモリ（一時キャッシュ）が内蔵されており、このキャッシュメモリに対してオートマトンを作成して格納することになる。
【０１２７】
図１３に示されるように、データ管理部は、ディレクタサーバＤＳおよびストレージサーバＳＴＲで構成され、また、検索処理部は、サーチサーバＳＳで構成される。サーチサーバＳＳは、例えば、ＬＡＮ等のネットワークＮＥＴを介してディレクタサーバＤＳに繋がれ、例えば、そのディレクタサーバＤＳに繋がれたＸＭＬのような構造化文書のデータが格納されたストレージサーバＳＴＲにおける文書データを処理する。
【０１２８】
なお、図１２および図１３に示す検索装置および検索システムは単なる例であり、適用されるシステムの規模や要求される検索性能等に応じて様々に変化され得るのはいうまでもない。例えば、より大規模なシステムでは、サーチサーバＳＳを複数台のラックシステムＲＳで構成し、また、複数台のディレクタサーバＤＳにより管理を行うといった構成にすることも可能である。
【０１２９】
以上、上述した各実施例は、様々に変形することが可能であり、どのような決定性有限オートマトンにも適用することができ、そのようなオートマトンを使用するワープロソフト、或いは、データベース検索などに対して幅広く適用することが可能である。
【０１３０】
以上の実施例を含む実施形態に関し、さらに、以下の付記を開示する。
（付記１）
現在の状態をインデックスとするデフォルト遷移先情報を保持するデフォルト用メモリと、
前記現在の状態と入力に基づく情報をインデックスとして前記現在の状態と前記入力が特定できるタグおよび遷移先情報を保持するイベント用メモリと、を有する検索装置であって、
前記デフォルト用メモリは、ｎ枚のデフォルト用メモリユニットを備え、１つの前記現在の状態に対してｎ個の前記デフォルト遷移先情報を前記ｎ枚のデフォルト用メモリユニットに登録する検索装置。
【０１３１】
（付記２）
付記１に記載の検索装置において、
前記各デフォルト用メモリユニットは、入力ビットパターンに従って選択される検索装置。
【０１３２】
（付記３）
付記２に記載の検索装置において、
さらに、前記入力ビットパターンをインデックスとして対応する前記デフォルト用メモリユニットの番号を得ることができるマッピングテーブルを備える検索装置。
【０１３３】
（付記４）
付記２または３に記載の検索装置において、
前記入力ビットパターンは、無視文字を含む検索装置。
【０１３４】
（付記５）
付記１〜４のいずれか１項に記載の検索装置において、
さらに、前記デフォルト用メモリユニットに対応したタグおよびヒット情報を登録するタグおよびヒット情報登録部を備える検索装置。
【０１３５】
（付記６）
付記１〜５のいずれか１項に記載の検索装置において、
前記検索装置は、構造化文書のデータから所定の文字列を検索する検索装置。
【０１３６】
（付記７）
付記６に記載の検索装置において、
前記構造化文書は、ＸＭＬ文書である検索装置。
【０１３７】
（付記８）
付記１〜７のいずれか１項に記載の検索装置において、
前記各デフォルト用メモリユニットは、多重化して連想度を有する検索装置。
【０１３８】
（付記９）
付記１〜８のいずれか１項に記載の検索装置において、
前記検索装置は、半導体チップ内に設けられた検索コアであり、且つ、
前記デフォルト用メモリおよび前記イベント用メモリは、前記検索コアに設けられたキャシュメモリである検索装置。
【０１３９】
（付記１０）
付記９に記載の検索装置を複数結合すると共に、該各検索装置がアクセス可能な主記憶装置を備える検索サーバ。
【０１４０】
（付記１１）
付記１０に記載の検索サーバと、
検索対象のデータが格納されたストレージサーバと、
前記検索サーバおよび前記ストレージサーバを管理するディレクタサーバと、を備える検索システム。
【０１４１】
（付記１２）
現在の状態をインデックスとするデフォルト遷移先情報をデフォルト用情報メモリに格納し、
前記現在の状態と入力に基づく情報をインデックスとして前記現在の状態と前記入力が特定できるタグおよび遷移先情報をイベント用メモリに格納する検索方法であって、
前記デフォルト用メモリへの前記デフォルト遷移先情報の格納は、１つの前記現在の状態に対してｎ個のデフォルト遷移先を登録する検索方法。
【０１４２】
（付記１３）
コンピュータに、
現在の状態をインデックスとするデフォルト遷移先情報をデフォルト用情報メモリに格納させる手順と、
前記現在の状態と入力に基づく情報を生成させる手順と、
前記情報をインデックスとして前記現在の状態と前記入力が特定できるタグおよび遷移先情報をイベント用メモリに格納させる手順とを実行させる検索プログラムであって、
前記デフォルト用メモリへの前記デフォルト遷移先情報の格納を、１つの前記現在の状態に対してｎ個のデフォルト遷移先を登録する検索プログラム。
【図面の簡単な説明】
【０１４３】
【図１Ａ】オートマトンによるキーワード検索アルゴリズムの一例であるシグマアルゴリズムを説明する図（その１）である。
【図１Ｂ】オートマトンによるキーワード検索アルゴリズムの一例であるシグマアルゴリズムを説明する図（その２）である。
【図２】検索装置の一例を概略的に説明するための図である。
【図３Ａ】検索装置の動作を説明するための図（その１）である。
【図３Ｂ】検索装置の動作を説明するための図（その２）である。
【図４Ａ】検索装置における処理の一例を示すフローチャート（その１）である。
【図４Ｂ】検索装置における処理の一例を示すフローチャート（その２）である。
【図４Ｃ】検索装置における処理の一例を示すフローチャート（その３）である。
【図５】関連技術としての検索装置の一例を概略的に説明するための図である。
【図６Ａ】図５に示す検索装置の動作を説明するための図（その１）である。
【図６Ｂ】図５に示す検索装置の動作を説明するための図（その２）である。
【図６Ｃ】図５に示す検索装置の動作を説明するための図（その３）である。
【図７】図５に示す検索装置におけるイベント用メモリのデータ例を示す図である。
【図８】第１実施例に係る検索装置を概略的に説明するための図である。
【図９】図８に示す検索装置におけるデフォルト用メモリの構成を説明するための図である。
【図１０Ａ】図８に示す検索装置の動作を説明するための図（その１）である。
【図１０Ｂ】図８に示す検索装置の動作を説明するための図（その２）である。
【図１１】第２実施例に係る検索装置におけるデフォルト用メモリの構成を説明するための図である。
【図１２】各実施例が適用される検索サーバの一例を概略的に示す図である。
【図１３】図１２の検索サーバを含む検索システムの全体構成を概略的に示す図である。
【符号の説明】
【０１４４】
１，１１，２１    検索対象文書
２，１２，２２    入力文字
３，１３，２３    現在の状態
４，２４    デフォルト用メモリ
５，２５    次の状態
６，２６    ハッシュ器（ＸＯＲ）
７，２７    イベント用メモリ
８，２８    現在の状態，入力文字＋次の状態
９，２９    レジスタ
１０，３０    判定部
３１，１００    選択回路
ＣＨＩＰ    半導体チップ
Ｄ０〜Ｄｎ；Ｄ００〜Ｄ０３，Ｄ１０〜Ｄ１３，Ｄ２０〜Ｄ２３    デフォルト用メモリユニット
ＭＥＭ    メモリ
ＰＢ    プロセッサボックス
ＰＧ    プロセッサグループ
ＰＭ    プロセッサモジュール
ＲＳ    ラックシステム
ＳＣ    検索コア（アクセラレータ）
ＳＳ    サーチサーバ
ＴＨ，ＴＨ０〜ＴＨ３    タグおよびヒット情報登録部
【国際調査報告】
2009093307.tif 000023
2009093307.tif 000024
2009093307.tif 000025
2009093307.tif 000026