(57)【要約】      （修正有）【課題】プロセッサが基本的に備える機能を利用して、高速に検索が可能な検索システムを提供すること。【解決手段】被検索データから検索キーを検索する演算回路を備えた検索システムにおいて、被検索データが演算回路の基本構成の一部である汎用レジスタに記憶される。そして、同時に一致検査されたｎ個までの検索結果を個別に示すフラグを持ち、検査結果がすべて不一致の場合には、代表フラグを持つ。また、前記フラグは、最端フラグの位置を数値化してレジスタに記憶し、不一致の場合は、この最端フラグが不一致を示すように変更する。【選択図】図２
2008027066.tif 000002
【特許請求の範囲】
【請求項１】
被検索データから検索キーを検索する演算回路を備えた検索システムにおいて、
前記被検索データが前記演算回路の基本構成の一部である汎用レジスタに記憶される、
ことを特徴とする検索システム。
【請求項２】
同時に一致検査されたｎ（自然数）個までの検査結果を個別に示すｎ個のフラグを有する、
ことを特徴とする請求項１記載の検索システム。
【請求項３】
ｎ個の前記検査結果が全て不一致である場合に不一致を示す１つの代表フラグを有する、
ことを特徴とする請求項２記載の検索システム。
【請求項４】
ｎ個の前記フラグのうち、前記検査結果が一致を示す最端フラグの位置を数値化してレジスタに記憶すると共に、該最端フラグを不一致を示すように変更する一致位置検出回路を有する、
ことを特徴とする請求項２記載の検索システム。
【請求項５】
前記最端フラグの数値化から不一致を示すように変更するまでの間、割り込みを禁止する割り込み禁止手段を有する、
ことを特徴とする請求項４記載の検索システム。
【請求項６】
前記汎用レジスタの右端又は左端を拡張して前記被検索データを記憶する、ことを特徴とする請求項１記載の検索システム。
【請求項７】
前記検索キーと前記被検索データの相関度を示す係数に基づき一致検査の検査結果を判定する、ことを特徴とする請求項６記載の検索システム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、検索システムに関し、特に、コンピュータにより被検索データから一致又は相関するデータを検索する検索システムに関する。
【背景技術】
【０００２】
データベース等から検索キーに一致するデータを検索することが要求されることがある。例えば、文字列が検索キーの場合、該文字列から部分文字列を切り出して、部分文字列に一致する単語をデータベースから検索する処理が提案されている。しかしながら、この方法では、多数の部分文字列の検索をデータベースに対し繰り返さなければならず検索に時間がかかる。
【０００３】
また、文字列全体を同時にデータベースから取り出す処理が提案されている。この方法では、データベースに記憶された被検索文字列をシフトレジスタに格納しておきシフトレジスタの全文字を一度に１文字ずらすことで、検索キーとの照合位置をずらして検索を進めることができる。しかしながら、この方法では１度に１回の検索結果しか得られず、高速化が困難である。
【０００４】
また、複数の検索キーに一致する単語をデータベースから検索するため、複数の検索キーを記憶するシフトレジスタと複数の文字列比較回路を有する検索装置が提案されている（例えば、特許文献１参照。）。特許文献１の検索装置では、複数の検索キーを一度に処理するので検索処理が高速化できるとしている。
【特許文献１】特開平３−１１０６７６号公報
【発明の開示】
【発明が解決しようとする課題】
【０００５】
しかしながら、特許文献１記載の検索装置は、プロセッサが基本機能として有する検索機能とは別に、検索するための専用の回路を備えるものであるため、回路規模が増大し、コスト増及び消費電力の増大を招くという問題がある。
【０００６】
本発明は、上記課題に鑑み、プロセッサが基本的に備える機能を利用して、高速に検索が可能な検索システムを提供することを目的とする。
【課題を解決するための手段】
【０００７】
上記課題に鑑み、本発明は、被検索データから検索キーを検索する演算回路（例えば、プロセッサ）を備えた検索システムにおいて、被検索データが演算回路の基本構成の一部である汎用レジスタに記憶される、ことを特徴とする。
【０００８】
本発明によれば、演算回路に専用回路を搭載する必要がないため、回路規模及び消費電力の増大を回避できる。
【発明の効果】
【０００９】
プロセッサが基本的に備える機能を利用して、高速に検索が可能な検索システムを提供することができる。
【発明を実施するための最良の形態】
【００１０】
以下、本発明を実施するための最良の形態を、図面を参照しながら実施例を挙げて説明する。
【００１１】
図１は、検索システム１０の概略構成図の一例を示す。検索システム１０は検索を制御するプロセッサ１、被検索データが記憶された記憶手段２、及び、検索キーを入力する外部入力装置３とを有する。
【００１２】
記憶手段２の被検索データは、漢字かな混じり文の文字列、住所や地物情報を含む地図データベース、音声認識のための音声情報と単語とが対応づけられた音声認識辞書、画像データが格納された画像データベース等である。
【００１３】
また、外部入力装置３は、タッチパネル、キーボード、マイクを介し音声情報を抽出する音声処理装置、ＤＶＤ等のメディア読み取り装置等であり、これらから入力された文字列、音声情報、画像データ等が検索キーとなる。
【００１４】
プロセッサ１は、トランジスタや他の回路素子が集積したひとつの大規模集積回路(ＬＳＩ)であり、一例としてはＣＰＵ（Ｃｅｎｔｒａｌ  Ｐｒｏｃｅｃｃｉｎｇ  Ｕｎｉｔ：中央処理装置）である。本実施形態のプロセッサ１は従来から備える基本機能や回路資源を利用した構成を有し、更に、基本機能に若干の回路を追加することで高速な検索を実現する。追加する若干の回路は、そのＣＰＵが従来から備える構成により異なり、また、全く追加することが必要ない場合もある。
【００１５】
プロセッサ１の構成は周知であるので簡単に説明する。データバッファ１２は、被検索データ、検索キー及び処理後の検索結果データを一時的に記憶するメモリである。被検索データと検索キーはデータバス１１を通じて汎用レジスタ１５に記憶される。
【００１６】
アドレスドライバ１３は、プログラムを取り出す番地をプログラムカウンタ１８の内容に応じて指定する。取り出された命令は命令レジスタ２１に記憶され、命令デコーダ２２により解読される。制御回路２３は解読結果に応じてＡＬＵ１９や汎用レジスタ１５等、プロセッサ１内部の各回路に制御信号を送る。ＡＬＵ１９による処理結果は汎用レジスタ１５に送出され、再度演算の対象となったりデータバッファ１２を介して出力される。
【００１７】
ＡＬＵ１９は、算術演算、論理演算する演算装置であり、汎用レジスタ１５の内容をロードして、加算、減算といった算術演算と、論理和、論理積といった論理演算を実行する。本実施形態のＡＬＵ１９は、検索キーと被検索データとが一致するか否かを判定する複数の一致検出回路２５を備える。一致検出回路２５は、例えば、ＥｘＮＯＲ（Exclusive NOR）回路により構成されるが、一致するか否かを出力する回路であればどのような回路であってもよい。
【００１８】
一致検出回路２５は、一般的なＣＰＵであれば備えているものであるため、検索システム１０のために回路資源を追加することなく又は最低限の追加により後述する検索を実行できる。
【００１９】
なお、汎用レジスタ１５として、単なる記憶だけでなく記憶内容に各種の演算を並列に行うことができる演算回路を追加した機能メモリを利用してもよく、この場合も本実施形態の検索を実行できる。
【実施例１】
【００２０】
図２は、検索システム１０から抽出した検索回路の構成図を示す。なお、図２において、図１と同一構成部分には同一の符号を付した。
【００２１】
上記のように、検索キー４と被検索データ５は汎用レジスタ１５に記憶されている。図２の検索キー４は例えば８又は１６ビット（例えば、１ワード）で構成され、アルファベットや漢字など文字である。また、被検索データ５は、検索キー４のｎ倍（ｎは整数）のビット長を有する。
【００２２】
一致検出回路２５はｎ個用意され、各一致検出回路２５ａ〜２５ｈに同じ検索キー４が入力されると共に、被検索データ５の先頭から検索キー４と同じビット長のデータが入力される。
【００２３】
各一致検出回路２５ａ〜ｈには、それぞれ一致検査結果を個別に示すｎ個のフラグ２６ａ〜ｈが接続されている。フラグ２６は、ＡＬＵ１９のレジスタを利用してもよいし、ＡＬＵ１９に新たに追加してもよい。
【００２４】
各フラグ２６ａ〜２６ｈはＯＲ回路２７に接続されている。ＯＲ回路２７は、フラグ２６ａ〜２６ｈの全てが不一致を示す場合に不一致の検査結果を通過させるゲートとなる。
すなわち、フラグ２６ａ〜ｈが全てゼロの場合にゼロを出力する。ＯＲ回路２７は、ＡＬＵ１９の回路を利用してもよいし、ＡＬＵ１９に新たに追加してもよい。
【００２５】
代表フラグ２８は、ｎ個のフラグ２６に対し１つのみ用意される。代表フラグ２８は、ＡＬＵ１９に新たに追加してもよいし、フラグレジスタ１７を利用してもよい。例えば、代表フラグ２８の検査を、条件分岐命令（Ｂｒａｎｃｈ  ｏｎ  Ｅｑｕａｌ、Ｂｒａｎｃｈ  ｏｎ  Ｎｏｔ  Ｅｑｕａｌ）などで実行することとすれば、ｎ個の一致検査を１個の代表フラグ２８の検査により判定できる。条件分岐命令は一般的なＣＰＵが基本命令として備える命令であるので、新たな命令を追加する必要がない。
【００２６】
外部入力装置３から検索キー４が入力され検索が指示されると、検索指示のマクロ命令が、ロード命令、一致検出命令、条件分岐命令等に展開され、被検索データ５が検索キー４に一致するデータ（文字）を有するか否かを検査する。
【００２７】
被検索データ５を、プロセッサ１の基本構成である汎用レジスタ１５に記憶する構成としたことで、被検索データ５を記憶手段２から汎用レジスタ１５に読み込む操作は、プロセッサ１の基本命令であるロード命令を使用することができ、プロセッサ１の基本部分と整合性の高い検索機能が実現できる。すなわち、回路構成の多くの部分をプロセッサ１の基本部分を利用することにより、追加する構成を少なくして検索できる。
【００２８】
また、図２の構成では、一度にｎ個の検索が実行され、ｎ個全てが不一致でなければ代表フラグ２８に一致を示す検査結果が設定される。一般に、被検索データ５から検索キー４と一致するデータが検出されることの方が少ないという経験則があるため、ｎ個のフラグ２６ａ〜２６ｈに１つでも一致を示すフラグがあれば、代表フラグ２８が一致を示す構成とした。
【００２９】
代表フラグ２８の検査結果は条件分岐命令で検査し、一致を示す場合にはプログラムの流れを変えて、一致した被検索データ５の出力等が可能になる。一致が検出されない場合、ｎ個の被検索データに対し１回だけ代表フラグ２８を検査すればよいので、処理速度を向上できる。すなわち、多くの検査結果では代表フラグ２８は不一致を示しその後の処理は必要ないので検索を高速化できる。
【００３０】
ところで、代表フラグ２８に一致が検出された場合、代表フラグ２８では被検索データ５内の一致位置が不明であるので、その一致位置を検出することが好ましい。一致位置を検出する命令をプロセッサ１が本来備えていれば１ステップの処理で、フラグ２６ａ〜ｈのどのフラグが一致を示したか検出できる。しかしながら、一般的なＣＰＵはそのような命令を備えていない。
【００３１】
プログラムにより一致位置を検出することが考えられる。しかしながらこの場合、ｎ個のフラグ２６ａ〜２６ｈの状態を汎用レジスタ１５にコピーし、その汎用レジスタ１５を１ビットずつ抽出して一致／不一致を調べる処理が必要になり、通常プロセッサ１に備わっている基本命令により処理すると、フラグ１個の検査に４ステップ程度必要になるため、処理が遅くなる。
【００３２】
〔一致位置の数値化処理〕
そこで、本実施形態ではｎ個のフラグ２６ａ〜２６ｈから一致位置を検出する回路を設ける。なお、ｎ個のフラグ２６ａ〜２６ｈのうち、複数フラグが一致を示している場合があり得るが、ｎ個のフラグを一度に数値化すると却って回路を複雑化するので、１つずつ一致を示しているフラグの位置を数値化する。
【００３３】
図３はフラグ２６ａ〜２６ｈから一致位置を検出する一致位置検出回路を示す図である。なお、図３において図２と同一構成部分には同一の符号を付した。図３ではＪＫフリップフロップ（以下、ＪＫＦＦという）３０ａ〜３０ｈがフラグ２６ａ〜２６ｈに相当する回路である。
【００３４】
ＡＮＤ回路３１には一致検出回路２５ａの出力と検索実行タイミングにＨとなる信号線が接続される。また、ＡＮＤ回路３２には一致検出回路２５ａの反転出力と検索実行タイミングにＨとなる信号線が接続される。また、ＡＮＤ回路３３には位置取得命令実行タイミングにＨとなる信号線と左端判定回路の出力ＰＳ００が接続される。ＯＲ回路３４にはＡＮＤ回路３２とＡＮＤ回路３３が接続される。そして、ＪＫＦＦ２６ａのＪ入力にはＡＮＤ回路３１が、Ｋ入力にはＯＲ回路３４がそれぞれ接続されている。
【００３５】
検索命令実行タイミングでは、一致を検出した一致検出回路２５ａ〜２５ｈと検索命令実行タイミングのＨ信号により、ＡＮＤ回路３１がＨとなる。この時、ＡＮＤ回路３２とＡＮＤ回路３３はいずれもＬになるので、ＯＲ回路３４もＬになる。したがって、ＪＫＦＦ２６ａ〜２６ｈのうち一致を検出したＪＫＦＦにはＨがセットされる。
【００３６】
左端判定回路３５には、一致が検出された数だけＨを示す信号が入力されるが、左端判定回路３５は、入力されたＨを示す信号のうち最も左端（図では上側）の信号線のみをＨにして、ＰＳ００〜ＰＳ０７のいずれか１つに出力する回路である。
【００３７】
ＨとなったＰＳ００〜ＰＳ０７のいずれか１つは、エンコーダ３６に入力されエンコードにより数値化された後、一致位置を格納する一致位置レジスタ３７に記憶される。そして、所定のタイミングでＰＥ００〜ＰＥ０３の信号線により取り出される。図３ではｎ＝８の場合を想定し、ＰＥ００〜ＰＥ０３を３本にした。
【００３８】
数値化後も、左端判定回路３５にはＪＫＦＦ３０ａ〜３０ｈのいずれか又は複数からＨを示す信号が入力されているため、左端判定回路３５が左端の信号としてエンコーダ３６に出力したら、該ＪＫＦＦをリセットする。
【００３９】
一致を示す左端のＪＫＦＦは相当するＰＳ０ｘ（ｘ：０〜７）をＨにするので、代表フラグ２８が検査され一致が検出されると位置取得命令実行タイミングの信号線がＨになり、ＡＮＤ回路３３がＨになる（したがって、ＯＲ回路３４はＨ）。この時、ＡＮＤ回路３１はＬになるので、一致を示す左端のＪＫＦＦ３０ｘのＪ入力はＬ、Ｋ入力はＨになり、ＪＫＦＦはリセットされる。
【００４０】
リセットされると、順次、左端判定回路３５は、次にＨを示すＪＫＦＦ３０ｘに相当するＰＳ０ｘをＨにして、新たな左端信号をエンコーダ３６に出力する。また、新たなＰＳ０ｘがＨとなることで、当該ＪＫＦＦ３０ｘがリセットされる。
【００４１】
このようにして、図３の一致位置検出回路はＪＫＦＦ３０ａ〜３０ｈのうちＨ信号となっているＪＫＦＦのみを左端から順番にエンコーダ３６に出力することができる。なお、Ｌ信号となっているＪＫＦＦ３０は左端判定回路３５から出力されることはないので、一致検出回路は一致の検出されたフラグの数だけ一致位置を検出する。
【００４２】
左端判定回路３５の代わりに、右端判定回路を設け、右端から一致を示すＪＫＦＦ３０の位置を数値化してもよい。
【００４３】
〔割り込み禁止処理〕
所定のフラグ２６の一致位置を数値化し一致位置レジスタ３７に記憶してから、そのフラグ２６をリセットするまでの間に割り込みが発生すると、検索結果に矛盾をきたすおそれがある。
【００４４】
そこで、本実施例では一致を検出したフラグ位置の数値化と数値化したフラグをリセットするまでの間を割り込み禁止とする。なお、割り込みには、ハードウェア割り込み、ソフトウェア割り込み（例外を含む）があるが、本実施例で禁止とする割り込みはいずれを含んでいてもよく、また、割り込みの優先度によっては割り込みを許可してもよい。
【００４５】
割り込み禁止とするため、数値化する命令とリセットする命令を１つの命令として定義する（以下、数値化＆リセット命令という。特許請求の範囲の割り込み禁止手段に相当する）。
【００４６】
数値化＆リセット命令を定義しておけば、この命令を実行することで割り込みを禁止しながら数値化とリセットが実行されるので、数値化の実行の前に割り込みレジスタ１６を割り込み禁止に設定する処理をしたり、割り込み禁止命令を実行する必要がない。なお、割り込みレジスタ１６や割り込み禁止命令を利用してもよい。
【００４７】
以上の構成に基づき、検索システム１０が被検索データ５から検索キー４を検索する処理の流れを図４のフローチャート図に基づき説明する。
【００４８】
まず、外部入力装置３を介してユーザにより検索キー４が入力され（Ｓ１）、検索実行ボタンが押下される（Ｓ２）。
【００４９】
検索実行の命令がプロセッサ１に入力されるので、例えばロード命令が実行され、検索キー４と被検索データ５が汎用レジスタ１５にロードされる（Ｓ３）。
【００５０】
ついで、一致検出命令が実行され、被検索データ５と検索キー４が一致検出回路２５に送出される（Ｓ４）。一致検出回路２５ａ〜２５ｈは検索キー４と被検索データ５とが一致するか否かを検査し、一致している場合フラグ２６ａ〜２６ｈに一致を示す値をセットすると共に、１つでも一致している場合、代表フラグ２８に一致を示す値をセットする。
【００５１】
ついで、条件分岐命令が実行され代表フラグ２８が一致を示すか否かを判定する（Ｓ５）。代表フラグ２８が一致を示さない場合（Ｓ５のＮｏ）、新たに被検索データを記憶手段２からロードして同様の検索処理を繰り返す。
【００５２】
代表フラグ２８が一致を示す場合（Ｓ５のＹｅｓ）、フラグの位置を数値化する処理に分岐する。
【００５３】
分岐先では、例えば、数値化＆リセット命令が実行され、一致位置検出回路２５ａ〜２５ｈにより一致を示すフラグ２６ａ〜２６ｈのうち左端のフラグの位置を数値化する（Ｓ６）。数値化された一致位置は一致位置レジスタ３７に記憶される。また、位置が数値化された左端のフラグがリセットされる（Ｓ７）。ついで、一致位置レジスタ３７の記憶内容が出力される（Ｓ８）。
【００５４】
一致を示すフラグを左端から順に数値化するので、一致を示した全てのフラグ２６ａ〜２６ｈの位置を数値化したか否かを判定する（Ｓ９）。数値化した後は数値化したフラグ２６ａ〜２６ｈの値がリセットされるので、終了したか否かはフラグ２６（全体）がゼロか否かを検出する１回の処理で判定できる。
【００５５】
一致を示した全てのフラグ２６a〜２６ｈの位置を数値化した場合（Ｓ９のＹｅｓ）、処理が終了する。プロセッサ１は、次のｎ個の被検索データ５を汎用レジスタ１５にロードして同様の処理を繰り返す。
【００５６】
以上のように、本実施例の検索システム１０は、回路構成の多くの部分を一般的なＣＰＵの基本機能を利用して、同時にｎ個の検索を実行するので、少ない回路資源で高速に検索できる。
【実施例２】
【００５７】
実施例１では、検索キー４を８〜１６ビットの１文字としたが、実際には複数文字であることが多い。本実施例では、検索キー４が複数文字の場合の検索システムについて説明する。複数文字とは、いわゆる１ワードより大きいビット長の検索キーの場合をいうが、本実施例では簡単に複数文字という。
【００５８】
図５は、検索キー４が複数文字の場合の検索回路の構成図を示す。なお、図５において図２と同一構成部分には同一の符号を付しその説明は省略する。
【００５９】
検索キー４は例えばｂビット×ｍ（ｍは整数）のビット長を有する。図５では一例とし検索キー４を３（ｍ＝３）文字とした。一致検出回路２５ａ〜２５ｈには、ｂ×ｍビットの被検索データ５が、ｂビットシフトしながら（１文字ずらしながら）ｂ×ｍビットずつ送出される。
【００６０】
一致検出回路２５ａ〜２５ｈは、３文字の検索キー４が被検索データ５に一致するか否かを同時に複数個検査する。フラグ２６、ＯＲ回路２７及び代表フラグ２８の構成は実施例１と同様である。すなわち、代表フラグ２８が一致を示す場合、図３の一致位置検出回路を用いて一致したフラグ２６ａ〜２６ｈの位置を検出する。
【００６１】
本実施例によれば、複数の文字からなる文字列を検索する場合のようにビット長が検索キー４の所定以上の場合でも、回路構成の多くの部分を一般的なＣＰＵの基本機能を利用して複数個の検索を同時に行い、少ない回路資源で高速に検索することができる。
【実施例３】
【００６２】
検索キー４と被検索データ５のいずれも汎用レジスタ１５に記憶した場合、汎用レジスタ１５は固定長（例えば８バイト＝６４又は１２８ビット）であるので検索キー４のデータ長と一致しないことが多い。このため、本実施例では、汎用レジスタ１５に記憶された検索キー４のうち、有意のデータ長のみを有効にするマスクを使用する。
【００６３】
図６は、マスク４２を使用した場合の検索回路の構成図を示す。なお、図６において図２と同一構成部分には同一の符号を付しその説明は省略する。検索キー４、マスク４２及び被検索データ５は、それぞれ汎用レジスタ１５に記憶されている。
【００６４】
マスク４２の内容は検索キー４の有効長に応じて指定される。検索キー４が例えば３文字の場合、汎用レジスタ１５が８文字分であるので、マスクの上位３バイトにはＦＦｈが、残りの下位５バイトには００ｈが記憶される。
【００６５】
一致検出回路２５ａ〜２５ｈには、汎用レジスタ１５のビット長のまま検索キー４、マスク４２及び被検索データ５が１文字ずつシフトして入力される。一致検出回路２５は、例えば論理積回路を２つ有し、一致検出する前に、検索キー４とマスク及び被検索データ５とマスクの論理積を演算し、検索キー４と被検索データ５のそれぞれ上位３バイトのみを抽出する。そして、一致検出回路２５ａ〜２５ｈは、同時に、３バイトが有意で５バイトがゼロの検索キー４と３バイトが有意で５バイトがゼロの２つのデータの一致を検出する。
【００６６】
フラグ２６、ＯＲ回路２７及び代表フラグ２８の構成は実施例１と同様である。すなわち、代表フラグ２８が一致を示す場合、図３の一致位置検出回路を用いて一致したフラグ２６ａ〜２６ｈの位置を検出する。
【００６７】
本実施例によれば、検索キー４が不定長であっても、回路構成の多くの部分を一般的なＣＰＵの基本機能を利用して複数回の検索を同時に行い、少ない回路資源で高速に検索することができる。なお、本実施例の構成は、実施例１〜２、４〜５に好適に適用することができる。
【実施例４】
【００６８】
被検索データ５は汎用レジスタ１５のレジスタ長よりも長いことが多い。このため、実施例２又は３のように検索キー４が複数文字から構成される場合、次のような不具合が生じる。
【００６９】
図５に示した構成図に基づき説明する。図５では、検索キー４が３文字、被検索データ５が格納された汎用レジスタ１５が８文字の大きさを有するが、一致検出回路２５ｇ、２５ｈに入力される被検索データ５はそれぞれ２文字と１文字になっている。したがって、仮に被検索データ５の７番目から始まる３文字が検索キー４に一致している場合、又は、被検索データ５の８番目から始まる３文字が検索キー４に一致している場合、これらを抽出することができない。
【００７０】
そこで、本実施例では、被検索データ５を記憶する汎用レジスタ１５を、別の汎用レジスタ１５に拡張し、２つのレジスタを連結して検索処理を行う。
【００７１】
図７（ａ）は被検索データ５を記憶する汎用レジスタ１５を拡張した検索回路の構成図を示す。なお、図７（ａ）において図５と同一構成部分には同一の符号を付しその説明は省略する。
【００７２】
図７（ａ）は汎用レジスタ１５ａの上位ビット側に別の（好ましくは隣接する）汎用レジスタ１５ｂが連結されている点で図５と異なる。検索キー４がｂビット×ｍのビット長の場合、汎用レジスタ１５ｂは、少なくともｂ×（ｍ−１）ビットのビット長を有し、前回検索処理した時の被検索データ５の下位ｂ×（ｍ−１）を記憶している。
【００７３】
したがって、３文字（ｍ＝３）の場合、次の検索時には、汎用レジスタ１５ｂの下位ｂ×２ビットには前回検索処理した時の被検索データ５が記憶され、汎用レジスタ１５ａには新たに記憶手段２から被検索データ５が記憶される。
【００７４】
汎用レジスタ１５ｂが汎用レジスタ１５ａと同じ大きさであれば、レジスタ間のデータ移動命令（例えば、ｍｏｖｅ）により、前回検索処理した時の被検索データ５を汎用レジスタ１５ｂに記憶できる。なお、データを移動するのでなく処理の対象とするレジスタを被検索データ５のビット長ずつ下位側にシフトしてもよい（汎用レジスタ１５ａが次回の検索の汎用レジスタ１５ｂになる）。
【００７５】
連結して連続したものと扱われたレジスタは、所定の命令により１つの汎用レジスタとして処理の対象とできる。したがって、以降は実施例２と同様に汎用レジスタ１５ｂの下位ｂ×２ビットから、ｂビットずらしながらｂ×３ビット（３文字）ずつ一致検出回路２５ａ〜２５ｈに送出すれば、同時に処理できる検索数を減らすことなく検索キー４と一致するデータを検索することができる。
【００７６】
フラグ２６、ＯＲ回路２７及び代表フラグ２８の構成は実施例２と同様であるので、一致位置検出回路を用いて一致したフラグ２６ａ〜２６ｈの一致位置を検出できる。
【００７７】
ところで、汎用レジスタ１５ａを下位側に拡張してもよい。図７（ｂ）は被検索データ５を記憶する汎用レジスタ１５を下位側に拡張した検索回路の構成図を示す。下位側に拡張することで、汎用レジスタ１５ａの下位ｂ×（ｍ−１）から汎用レジスタ１５ｂの上位ｂ×（ｍ−２）ビットが７番目の被検索データに、汎用レジスタ１５ａの下位ｂ×（ｍ−２）から汎用レジスタ１５ｂの上位ｂ×（ｍ−１）ビットが８番目の被検索データになる。
【００７８】
したがって、同時に処理できる検索数を減らしたり、検索漏れを生じることなく検索キー４と一致するデータを検索することができる。
【００７９】
次回の検索処理時は、汎用レジスタ１５ｂの被検索データ５を汎用レジスタ１５ａに移動すると共に、汎用レジスタ１５ｂに新たな被検索データ５を記憶手段２からロードする。なお、データを移動するのでなく処理の対象とするレジスタを被検索データ５のビット長ずつ下位側にシフトしてもよい（汎用レジスタ１５ｂが次回の検索の汎用レジスタ１５ａになる）。
【００８０】
本実施例によれば、検索キー４と汎用レジスタ１５のビット長に起因する被検索データ５の端数部分を、次回の検索処理時に拡張した汎用レジスタ１５に記憶することで、ｎ個（＝汎用レジスタ１５ａのビット長をｂで除した数）同時に一致検査することができる。したがって、被検索データ５のビット長が、汎用レジスタ１５ａのビット長を超える場合、繰り返して検索を実行することで、拡張した汎用レジスタ１５ｂへ被検索データ５をコピー又はレジスタのシフト等によって簡単に実現でき、効率よく高速な検索が可能となる。
【実施例５】
【００８１】
実施例１ないし４では、被検索データ５が検索キー４と一致するデータを有するか否かを判定したが、完全に一致しなくてもある程度相関する被検索データ５を検索したい場合がある。例えば、音声認識処理において、音声をサンプリングしてデジタルデータに数値化した音声情報に相当する文字列を記憶手段２から検索する場合である。このような場合、音声認識用のデータベースには、単語データ（文字列）に対応づけて音声情報が格納されているが、マイクから数値化された音声情報と完全に一致することは少なく、ある程度相関する音声情報を基に対応する文字列が抽出されることが多い。また、画像データを検索する場合も、圧縮やノイズなど処理の過程で元の画像データと完全には一致しないものとなる場合がある。本実施例では、このような対象を検索する処理に好適な検索システムについて説明する。
【００８２】
図８は相関度に基づき検索する検索回路の構成図を示す。なお、図８において図７（ａ）と同一構成部分には同一の符号を付しその説明は省略する。図８の検索回路は、一致検出回路２５でなく相関度検出回路２９を有する点で図７（ａ）と異なる。相関度検出回路２９は、音声データや画像データを処理するＣＰＵに予め搭載されていることが多い。
【００８３】
相関度検出回路２９ａ〜２９ｈには、検索キー４と、検索キー４と同じビット長の被検索データ５が入力される。そして、各相関度検出回路２９ａ〜２９ｈは、検索キー４と被検索データ５の相関度を示す係数を演算する。相関度を示す係数は、例えば、差分絶対値和や差分２乗和である。
【００８４】
差分絶対値和は、検索キー４（ｂビット×ｍ）と被検索データ５の各桁をｂビットの数値として比較し、各桁の差分絶対値のｍ桁分の和を示す。したがって、検索キー４と被検索データ５の相関が高いほど小さくなり、相関が小さいほど大きくなる。また、一致する場合にはゼロになる。
【００８５】
図８では、相関度検出回路２９ａ〜２９ｈが出力する差分絶対値和がゼロの場合（検索キー４と各被検索データ５が一致する場合）、相関度検出回路２９ａ〜２９ｈは一致検査結果を個別に示すｎ個のフラグ２６ａ〜ｈに一致を示す値をセットする。そして、フラグ２６ａ〜２６ｈのうち１つでも一致を示していれば、代表フラグ２８に一致を示す値がセットされる。
【００８６】
以降は、実施例４と同様であり、一致位置検出回路を用いて一致したフラグ２６ａ〜２６ｈの位置を検出できる。
【００８７】
図８のような検索回路では、完全に一致する被検索データ５のみしか取り出すことができないが、上記のように音声情報や画像データでは差分絶対値和がゼロになる場合は少ないので、差分絶対値を所定の閾値と比較することが好適である。
【００８８】
図９は、差分絶対値和を閾値４３と比較して比較結果をフラグ２６に記憶する検索回路を示す。各相関度検出回路２９ａ〜２９ｈに比較回路４１ａ〜４１ｈが接続されており、比較回路４１ａ〜４１ｈには差分絶対値和と閾値が入力される。比較回路４１ａ〜４１ｈは差分絶対値和と閾値を比較し、差分絶対値和が閾値よりも小さい場合、一致を示す値を出力し、差分絶対値和が閾値以上の場合、不一致を示す値を出力する。比較回路４１ａ〜４１ｈは一般的なＣＰＵが備えていることが多いが、備えていなければ追加する。
【００８９】
閾値は汎用レジスタ１５に記憶されており、検索キー４のビット長、被検索データ５の種別に応じてプログラムが設定してもよいし、ユーザが設定可能でもよい。また、固定であってもよい。
【００９０】
フラグ２６ａ〜２６ｈが全て不一致を示す値でなければ（１つでも差分絶対値和が閾値より小さければ）、ＯＲ回路２７を介して代表フラグ２８に一致を示す値がセットされる。代表フラグ２８が一致を示す場合、図３の一致位置検出回路を用いて一致したフラグ２６ａ〜２６ｈの位置を検出する。
【００９１】
ＣＰＵには音声データや画像データなどの相関を求める回路が予め搭載されていることが多い。したがって、完全に一致する検索結果の抽出が困難な被検索データ５であっても、相関度に基づき検索することで予め備える回路と共通の回路で検索することができ、追加する回路資源なく又は最小限にして検索システム１０を実現できる。
【００９２】
以上のように、本実施形態の検索システム１０は、回路構成の多くの部分を一般的なＣＰＵの基本部分を利用することにより、追加する構成を少なくして回路規模、消費電力及びコストの増大を防止できる。
【００９３】
また、一度にｎ個の検索を実行でき、代表フラグ２８を１回検査するだけでｎ個の検査結果を判定できる。ｎ個の検査結果は多くの場合は不一致を示すので、ｎ個の検索のうち１つでも一致を示す場合に代表フラグ２８が一致を示すようにしても、多くの場合は不一致を示しその後の処理は必要なく検索を高速化できる。
【００９４】
代表フラグ２８が一致を示した場合、一致を示したフラグ２６の位置を一致検出回路で検出するのでプログラムで検出するよりも検索処理を高速化できる。また、一致検出回路により、一致を示すフラグの位置を数値化できる。また、数値化している間は割り込みを防止するので、割り込みにより処理の矛盾が生じることを防止できる。
【００９５】
また、検索キーが所定以上のビット長であっても、汎用レジスタ１５の右端又は左端を拡張することで、検索漏れを防止できる。
【００９６】
また、音声情報や画像データなどを検索する場合、一致するか否かを相関度に基づき検出できるので、検索キー４と完全に一致しないデータを検索することができる。
【図面の簡単な説明】
【００９７】
【図１】検索システムの概略構成図の一例を示す図である。
【図２】検索システムから抽出した検索回路の構成図である。
【図３】各フラグのうち一致を示すフラグの位置を検出する一致位置検出回路を示す図である。
【図４】検索システムが被検索データから検索キーを検索する処理の流れを示すフローチャート図である。
【図５】検索キー４が複数文字の場合の検索回路の構成図である。
【図６】マスクを使用した場合の検索回路の構成図である。
【図７】被検索データを記憶する汎用レジスタを拡張した検索回路の構成図である。
【図８】相関度に基づき検索する検索回路の構成図である。
【図９】差分絶対値和を閾値と比較して比較結果に基づき一致を検出する検索回路である。
【符号の説明】
【００９８】
１      プロセッサ
２      記憶手段
３      外部入力装置
４      検索キー
５      被検索データ
１０    検索システム
１５    汎用レジスタ
２５    一致検出回路
２６    フラグ    
２７    ＯＲ回路
２８    代表フラグ
２９    相関度検出回路
３０    ＪＫフリップフロップ
３５    左端判定回路
４１    比較回路
【図１】
2008027066.tif 000003
【図２】
2008027066.tif 000004
【図３】
2008027066.tif 000005
【図４】
2008027066.tif 000006
【図５】
2008027066.tif 000007
【図６】
2008027066.tif 000008
【図７】
2008027066.tif 000009
【図８】
2008027066.tif 000010
【図９】
2008027066.tif 000011