(57)【要約】      （修正有）【課題】不一致の判定時間を短縮することによって平均検索時間を短くする。【解決手段】入力データと一致登録データとを比較し、入力データと一致する一致登録データを検出した場合に一致検出信号を出力する一致検出手段と、入力データの一部と予め登録した不一致登録データの一部とを比較し、あるいは入力データの全部と不一致登録データの全部とを比較し、入力データと一致または一致とみなす不一致登録データを検出した場合に不一致検出信号を出力する不一致検出手段と、一致検出信号および不一致検出信号をそれぞれ入力し、先に入力した信号が一致検出信号であれば一致判定の判定信号を出力し、不一致検出信号であれば不一致判定の判定信号を出力する判定手段とを備える。【選択図】図１
2010165102.tif 000002
【特許請求の範囲】
【請求項１】
入力データが予め登録した一致登録データに一致するか否かを判定するデータ検索装置において、
前記入力データと前記一致登録データとを比較し、前記入力データと一致する前記一致登録データを検出した場合に一致検出信号を出力する一致検出手段と、
前記入力データの一部と予め登録した不一致登録データの一部とを比較し、あるいは前記入力データの全部と前記不一致登録データの全部とを比較し、前記入力データと一致または一致とみなす前記不一致登録データを検出した場合に不一致検出信号を出力する不一致検出手段と、
前記一致検出信号および前記不一致検出信号をそれぞれ入力し、先に入力した信号が前記一致検出信号であれば一致判定の判定信号を出力し、前記不一致検出信号であれば不一致判定の判定信号を出力する判定手段と
を備えたことを特徴とするデータ検索装置。
【請求項２】
請求項１に記載のデータ検索装置において、
前記一致検出手段は、前記不一致検出手段が前記不一致検出信号を出力したときに、前記判定手段または前記不一致検出手段からの通知により検索処理を中止して次の入力データの検索処理を行う構成であり、
前記不一致検出手段は、前記一致検出手段が前記一致検出信号を出力したときに、前記判定手段または前記一致検出手段からの通知により検索処理を中止して次の入力データの検索処理を行う構成である
ことを特徴とするデータ検索装置。
【請求項３】
請求項１に記載のデータ検索装置において、
前記不一致検出手段は、前記入力データに対して前記一致検出手段が前記一致検出信号を出力しないときに、当該入力データを不一致登録データとして追加登録する構成である
ことを特徴とするデータ検索装置。
【請求項４】
請求項１に記載のデータ検索装置において、
前記不一致検出手段または前記一致検出手段は、
前記不一致登録データまたは前記一致登録データの値に対応した数値のアドレスに当該データの有無情報を記憶したメモリ手段と、
前記入力データの値を前記メモリ手段の読み出しアドレスに変換して前記有無情報の読み出しを行い、有情報に対して前記不一致検出信号または前記一致検出信号を出力する一致比較手段と
を備えたことを特徴とするデータ検索装置。
【請求項５】
請求項１に記載のデータ検索装置において、
前記不一致検出手段は、前記入力データと前記一致登録データをそれぞれ複数の分割データと複数の分割一致登録データに分割し、対応する分割データと分割一致登録データとをそれぞれ比較し、その少なくとも１組が不一致であれば前記不一致検出信号を出力する構成である
ことを特徴とするデータ検索装置。
【請求項６】
請求項１に記載のデータ検索装置において、
前記不一致検出手段は、前記入力データに対して前記不一致検出信号を出力しないときに検索指示信号を前記一致検出手段に出力する構成であり、
前記一致検出手段は、前記検索指示信号を入力したときに前記入力データに対する検索処理を行う構成である
ことを特徴とするデータ検索装置。
【請求項７】
請求項６に記載のデータ検索装置において、
前記一致検出手段は、前記入力データを保持し、前記一致検出信号を出力するときに検索対象となった前記入力データも出力する構成であり、
前記不一致検出手段は、前記入力データを保持し、前記不一致検出信号を出力するときに検索対象となった前記入力データも出力し、前記不一致検出信号または前記検索指示信号を出力した後に次の入力データに対する検索処理に移行する構成であり、
前記判定手段は、前記一致検出信号または前記不一致検出信号とともに入力する前記入力データを、前記判定信号とともに出力する構成である
ことを特徴とするデータ検索装置。
【請求項８】
入力データが予め登録した一致登録データに一致するか否かを判定するデータ検索方法において、
一致検出手段で前記入力データと前記一致登録データとを比較し、前記入力データと一致する前記一致登録データを検出した場合に一致検出信号を出力し、
不一致検出手段で前記入力データの一部と予め登録した不一致登録データの一部とを比較し、あるいは前記入力データの全部と前記不一致登録データの全部とを比較し、前記入力データと一致または一致とみなす前記不一致登録データを検出した場合に不一致検出信号を出力し、
判定手段で前記一致検出信号および前記不一致検出信号をそれぞれ入力し、先に入力した信号が前記一致検出信号であれば一致判定の判定信号を出力し、前記不一致検出信号であれば不一致判定の判定信号を出力する
ことを特徴とするデータ検索方法。
【請求項９】
請求項８に記載のデータ検索方法において、
前記一致検出手段は、前記不一致検出手段が前記不一致検出信号を出力したときに、前記判定手段または前記不一致検出手段からの通知により検索処理を中止して次の入力データの検索処理を行い、
前記不一致検出手段は、前記一致検出手段が前記一致検出信号を出力したときに、前記判定手段または前記一致検出手段からの通知により検索処理を中止して次の入力データの検索処理を行う
ことを特徴とするデータ検索方法。
【請求項１０】
請求項８に記載のデータ検索方法において、
前記不一致検出手段は、前記入力データに対して前記一致検出手段が前記一致検出信号を出力しないときに、当該入力データを不一致登録データとして追加登録する
ことを特徴とするデータ検索方法。
【請求項１１】
請求項１〜請求項７のいずれかに記載のデータ検索装置の各手段を、コンピュータで実行するプログラムで実現したことを特徴とするデータ検索プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、入力データが登録データに一致するか否かを判定するデータ検索装置、データ検索方法およびデータ検索プログラムに関する。
【背景技術】
【０００２】
データ処理を行う電子機器等には、受信データにフィルタリングなどの処理を行うためにデータ検索装置を搭載しているものがある。このデータ検索装置は、受信データの一部または全部を入力データとして入力し、入力データが事前に登録した複数のデータ（登録データ）のいずれかに一致するか否かを判定し、その判定結果を出力する構成である。
【０００３】
インターネットを利用する各ユーザが取り扱うデータ量が増加すると、データ検索装置には多種大量の受信データを短時間で処理するために、１つの入力データが入力されてから判定結果を出力するまでに要する平均的な時間（平均検索時間）の短縮が求められている。ここで、データ検索装置において、総数Ｎ（Ｎは自然数）の入力データをＴ秒（Ｔは自然数）で処理する場合の平均検索時間はＴ／Ｎで表される。
【０００４】
データ検索方法の１つである線形検索方法は、登録データを１つずつ順番に入力データと比較し、入力データと一致する登録データを検出した場合に一致と判定する。逆に、入力データと全登録データとを比較して一致する登録データを検出できない場合に不一致と判定する。すなわち、線形検索方法では一致を判定するとともに、一致を判定できないとき（未登録の場合）に不一致と判定している（非特許文献１）。
【０００５】
他のデータ検索方法である２分探索木方法は、異なる値をもつ複数の登録データを昇順または降順に並べ替え、並べ替えた登録データ群の中央の登録データと入力データとを比較し、その大小関係から次の検索対象を半分に絞りこんでいく。そして、検索対象を絞り込んでいく過程で、入力データと一致する登録データを検出した場合に一致と判定し、比較対象がなくなった場合に不一致と判定する。すなわち、２分探索木方法においても、線形検索方法と同様に一致を判定するとともに、一致を判定できないとき（未登録の場合）に不一致と判定している（特許文献１，非特許文献２）。
【０００６】
図１９は、従来のデータ検索装置の代表的な構成例を示す。
図において、データ検索装置は、一致検出部１０および判定部３２から構成される。一致検出部１０は、入力データ１と一致登録データとを比較し、入力データ１と一致する一致登録データを検出した場合に一致検出信号２を出力し、入力データ１と一致する一致登録データがない場合に比較終了信号３を出力する。判定部３２は、一致検出信号２または比較終了信号３を入力すると、表１に示すように、一致検出信号２に対して一致判定の判定信号５を出力し、比較終了信号３に対して不一致判定の判定信号５を出力する。
【０００７】
【表１】
2010165102.tif 000003
【０００８】
図２０は、一致検出部１０の構成例を示す。
図において、一致検出部１０は、レジスタ４０、一致比較回路５０および一致登録データ格納部６０から構成される。一致検出部１０に入力する入力データ１は、レジスタ４０で一時的に保持され、一致比較回路５０に比較データ１１１として出力される。一致比較回路５０は比較データ１１１を入力すると、複数の一致登録データを格納した一致登録データ格納部６０に要求信号１１２を出力し、一致登録データ格納部１３から１つずつ読み出した一致登録データ１１３と比較データ１１１とを比較する。このとき、一致登録データ１１３と比較データ１１１が一致すれば、一致比較回路５０は一致検出信号２を出力する。一方、登録データ格納部１３から読み出す一致登録データがなくなれば、一致比較回路１２は比較終了信号３を出力する。
【発明の概要】
【発明が解決しようとする課題】
【０００９】
従来のデータ検索装置は、一致と判定できない場合に不一致と判定するため、入力データとすべての一致登録データを比較した後でなければ不一致を判定することができない。したがって、不一致判定する場合が最も検索に長い時間を要することになり、入力データの多くが不一致となる状況では平均検索時間が長くなる。
【００１０】
本発明は、不一致の判定時間を短縮することによって平均検索時間を短くするデータ検索装置、データ検索方法およびデータ検索プログラムを提供することを目的とする。
【課題を解決するための手段】
【００１１】
第１の発明は、入力データが予め登録した一致登録データに一致するか否かを判定するデータ検索装置において、入力データと一致登録データとを比較し、入力データと一致する一致登録データを検出した場合に一致検出信号を出力する一致検出手段と、入力データの一部と予め登録した不一致登録データの一部とを比較し、あるいは入力データの全部と不一致登録データの全部とを比較し、入力データと一致または一致とみなす不一致登録データを検出した場合に不一致検出信号を出力する不一致検出手段と、一致検出信号および不一致検出信号をそれぞれ入力し、先に入力した信号が一致検出信号であれば一致判定の判定信号を出力し、不一致検出信号であれば不一致判定の判定信号を出力する判定手段とを備える。
【００１２】
第１の発明のデータ検索装置における一致検出手段は、不一致検出手段が不一致検出信号を出力したときに、判定手段または不一致検出手段からの通知により検索処理を中止して次の入力データの検索処理を行う構成であり、不一致検出手段は、一致検出手段が一致検出信号を出力したときに、判定手段または一致検出手段からの通知により検索処理を中止して次の入力データの検索処理を行う構成としてもよい。
【００１３】
第１の発明のデータ検索装置における不一致検出手段は、入力データに対して一致検出手段が一致検出信号を出力しないときに、当該入力データを不一致登録データとして追加登録する構成としてもよい。
【００１４】
第１の発明のデータ検索装置における不一致検出手段または一致検出手段は、不一致登録データまたは一致登録データの値に対応した数値のアドレスに当該データの有無情報を記憶したメモリ手段と、入力データの値をメモリ手段の読み出しアドレスに変換して有無情報の読み出しを行い、有情報に対して不一致検出信号または一致検出信号を出力する一致比較手段とを備える構成としてもよい。
【００１５】
第１の発明のデータ検索装置における不一致検出手段は、入力データと一致登録データをそれぞれ複数の分割データと複数の分割一致登録データに分割し、対応する分割データと分割一致登録データとをそれぞれ比較し、その少なくとも１組が不一致であれば不一致検出信号を出力する構成としてもよい。
【００１６】
第１の発明のデータ検索装置における不一致検出手段は、入力データに対して不一致検出信号を出力しないときに検索指示信号を一致検出手段に出力する構成であり、一致検出手段は、検索指示信号を入力したときに入力データに対する検索処理を行う構成としてもよい。
【００１７】
また、一致検出手段は、入力データを保持し、一致検出信号を出力するときに検索対象となった入力データも出力する構成であり、不一致検出手段は、入力データを保持し、不一致検出信号を出力するときに検索対象となった入力データも出力し、不一致検出信号または検索指示信号を出力した後に次の入力データに対する検索処理に移行する構成であり、判定手段は、一致検出信号または不一致検出信号とともに入力する入力データを、判定信号とともに出力する構成としてもよい。
【００１８】
第２の発明は、入力データが予め登録した一致登録データに一致するか否かを判定するデータ検索方法において、一致検出手段で入力データと一致登録データとを比較し、入力データと一致する一致登録データを検出した場合に一致検出信号を出力し、不一致検出手段で入力データの一部と予め登録した不一致登録データの一部とを比較し、あるいは入力データの全部と不一致登録データの全部とを比較し、入力データと一致または一致とみなす不一致登録データを検出した場合に不一致検出信号を出力し、判定手段で一致検出信号および不一致検出信号をそれぞれ入力し、先に入力した信号が一致検出信号であれば一致判定の判定信号を出力し、不一致検出信号であれば不一致判定の判定信号を出力する。
【００１９】
第２の発明のデータ検索方法における一致検出手段は、不一致検出手段が不一致検出信号を出力したときに、判定手段または不一致検出手段からの通知により検索処理を中止して次の入力データの検索処理を行い、不一致検出手段は、一致検出手段が一致検出信号を出力したときに、判定手段または一致検出手段からの通知により検索処理を中止して次の入力データの検索処理を行うようにしてもよい。
【００２０】
第２の発明のデータ検索方法における不一致検出手段は、入力データに対して一致検出手段が一致検出信号を出力しないときに、当該入力データを不一致登録データとして追加登録するようにしてもよい。
【００２１】
第３の発明は、第１の発明のデータ検索装置の各手段を、コンピュータで実行するプログラムで実現したことを特徴とする。
【発明の効果】
【００２２】
本発明は、入力データと一致登録データとの一致を検出する一致検出手段と、不一致登録データとの一致（入力データと一致登録データとの不一致）を検出する不一致検出手段を備え、いずれか先に出力された検索結果を一致／不一致判定出力とする。これにより、入力データとすべての一致登録データを比較することなく、不一致判定を行うことができる。したがって、入力データの多くが不一致判定するような場合でも、短時間で検索結果を出力することができ、従来装置に比べて平均検索時間を短縮することができる。
【図面の簡単な説明】
【００２３】
【図１】本発明のデータ検索装置の実施例１の構成例を示す図である。
【図２】実施例１における不一致検出部２０の構成例を示す図である。
【図３】本発明のデータ検索装置の実施例２の構成例を示す図である。
【図４】本発明のデータ検索装置の実施例２の他の構成例を示す図である。
【図５】本発明のデータ検索装置の実施例３の構成例を示す図である。
【図６】実施例４における不一致検出部２１の構成例を示す図である。
【図７】不一致登録データ格納部６２の構成例を示す図である。
【図８】メモリ８０に格納する不一致登録データの作成方法を説明する図である。
【図９】本発明のデータ検索装置の実施例４の変形例を示す図である。
【図１０】実施例５における不一致検出部２２の構成例を示す図である。
【図１１】分割データの形態を示す図である。
【図１２】分割一致登録データの形態を示す図である。
【図１３】分割不一致検出部２３の構成例を示す図である。
【図１４】本発明のデータ検索装置の実施例６の構成例を示す図である。
【図１５】実施例６における一致検出部１１の構成例を示す図である。
【図１６】本発明のデータ検索装置の実施例７の構成例を示す図である。
【図１７】実施例７における一致検出部１２の構成例を示す図である。
【図１８】本発明のデータ検索装置の実施例７の動作例を示すタイミングチャートである。
【図１９】従来のデータ検索装置の代表的な構成例を示す図である。
【図２０】一致検出部１０の構成例を示す図である。
【発明を実施するための形態】
【００２４】
以下、本発明のデータ検索装置、データ検索方法およびデータ検索プログラムの実施の形態について、実施例１〜実施例８に基づいて詳細に説明する。
【実施例１】
【００２５】
実施例１のデータ検索装置は、入力データと一致する一致登録データおよび不一致登録データを検索し、一致判定または不一致判定を並列に行うことを特徴とする。
【００２６】
図１は、本発明のデータ検索装置の実施例１の構成例を示す。
図において、実施例１のデータ検索装置は、一致検出部１０、不一致検出部２０および判定部３０から構成される。データ検索装置に入力する入力データ１は、一致検出部１０および不一致検出部２０に入力する。一致検出部１０は、入力データ１と一致登録データとを比較し、入力データ１と一致する一致登録データを検出した場合に一致検出信号２を出力し、入力データ１と一致する一致登録データがない（未登録の）場合に比較終了信号３を出力する。不一致検出部２０は、入力データ１と不一致登録データとを比較し、入力データ１と一致する不一致登録データを検出した場合に不一致検出信号４を出力する。
【００２７】
判定部３０は、一致検出信号２または比較終了信号３または不一致検出信号４を入力すると、表２に示すように、一致検出信号２に対して一致判定の判定信号５を出力し、比較終了信号３または不一致検出信号４に対して不一致判定の判定信号５を出力する。
【００２８】
【表２】
2010165102.tif 000004
【００２９】
なお、判定部３０は、一致検出部１０と不一致検出部２０のいずれかから最も早く入力する信号に対応する判定信号５を出力し、その後に入力する信号は無視する構成である。すなわち、一致検出部１０が出力する一致検出信号２または比較終了信号３、または不一致検出部２０が出力する不一致検出信号４のいずれか早い信号に応じて、表２に示すような判定結果を出力する。これにより、実施例１のデータ検索装置では、一致検出部１０のみで検索処理を行う従来構成よりも平均的に早く判定結果を出力することができ、平均検索時間を短縮することができる。
【００３０】
次に、一致検出部１０および不一致検出部２０の構成例について説明するが、一致検出部１０は図２０に示す従来のデータ検索装置における一致検出部１０と同様の構成であるので説明は省略する。
【００３１】
図２は、実施例１における不一致検出部２０の構成例を示す。
図において、不一致検出部２０は、レジスタ４０、一致比較回路５１および不一致登録データ格納部６１から構成される。不一致検出部２０に入力する入力データ１は、レジスタ４０で一時的に保持され、一致比較回路５１に比較データ１１１として出力される。一致比較回路５１は比較データ１１１を入力すると、複数の不一致登録データを格納した不一致登録データ格納部６１に要求信号１１２を出力し、不一致登録データ格納部６１から１つずつ読み出した不一致登録データ１１４と比較データ１１１とを比較する。このとき、不一致登録データ１１４と比較データ１１１が一致すれば、一致比較回路５１は不一致検出信号４を出力する。なお、入力データ１に一致する不一致登録データが未登録であれば、一致比較回路５１はなにも出力しない。
【００３２】
ここで、実施例１の変形例について説明する。この変形例は、以下に示す他の実施例においても同様に適用可能である。
【００３３】
実施例１で説明した一致検出部１０および不一致検出部２０は、線形検索方法に対応する構成を想定しているが、これに限定されるものではなく、例えば２分探索木方法に対応する構成であってもよい。また、一致検出部１０と不一致検出部２０は、互いに異なる検索方法に対応する構成であってもよい。
【００３４】
不一致検出部２０は、不一致検出信号４だけでなく、全種類の不一致登録データを保持している場合に、入力データ１と一致する不一致登録データがない（未登録の）場合に比較終了信号を出力し、判定部３０がこの比較終了信号に対して一致判定の判定信号５を出力するようにしてもよい。
【００３５】
不一致検出部２０の不一致登録データ格納部６１は、全種類の不一致登録データを保持せず、例えば利用頻度の高い不一致登録データのみを保持する構成としてもよい。また、ｎビットの不一致登録データのうち、例えば上位（ｎ−１）ビットを不一致登録データとして保持し、入力データ１の上位（ｎ−１）ビットの比較データ１１１と比較する構成としてもよい。また、不一致登録データのビット数を単純に切り捨てるだけでなく、ハッシュ関数等を用いて不一致登録データのビット数を小さくしてもよい。これにより、不一致登録データの数またはデータ量を減らすことができ、平均検索時間の短縮効果を確保しながら、メモリ容量の削減、動作速度の向上、消費電力の削減の各効果を得ることができる。
【００３６】
一致検出部１０および不一致検出部２０は、一致登録データおよび不一致登録データごとの一致回数をカウントし、カウント数の大きいものから順番に検索を行う構成としてもよい。また、一致登録データおよび不一致登録データを並べ替える機能や、利用頻度の低い一致登録データおよび不一致登録データを消去する機能を備えてもよい。これにより、複数の入力データが連続して入力する場合に平均検索時間を短縮することができる。
【００３７】
一致登録データを追加する場合には、事前に当該一致登録データを不一致検出部２０に入力して不一致検出信号４が出力される場合には、当該一致登録データを不一致登録データから削除してから一致検出部１０の一致登録データ格納部６０に格納する。不一致登録データを追加する場合にも同様の処理を行ってもよい。これにより、一致登録データと不一致登録データの重複を回避することができる。
【００３８】
実施例１のデータ検索装置は、一致判定または不一致判定の判定信号５を出力するが、一致判定の判定信号５に代えて関連データを出力するようにしてもよい。例えば、関連データを出力ポートとすればルータとしての機能を付加することができ、関連データを出力キューとすれば優先制御としての機能を付加することができる。なお、この関連データは、一致検出部１０の一致登録データ格納部（図２０の６０）から一致登録データ（図２０の１１３）とともに出力され、一致検出信号２とともに判定部３０に出力され、判定部３０が一致判定を行うときに判定信号５に代わって出力される。
【実施例２】
【００３９】
実施例２のデータ検索装置は、入力データと一致する一致登録データおよび不一致登録データを検索し、一致判定または不一致判定を行った後に一致検出部１０および不一致検出部２０の検索動作を終了させ、次の入力データに対する検索を可能にすることを特徴とする。
【００４０】
図３は、本発明のデータ検索装置の実施例２の構成例を示す。
図において、実施例２のデータ検索装置は、基本的機能が実施例１と同様の一致検出部１０、不一致検出部２０および判定部３０から構成される。実施例２の判定部３０は、不一致検出信号４の入力に対する判定信号５を出力するとともに、一致検出部１０に対して入力データと一致登録データとの比較を中止させる比較中止信号６を出力する。また、実施例２の判定部３０は、一致検出信号２または比較終了信号３の入力に対する判定信号５を出力するとともに、不一致検出部２０に対して入力データと不一致登録データとの比較を中止させる比較中止信号７を出力する。
【００４１】
このように実施例２では、入力データに対して一致判定または不一致判定を行った後に、データ検索処理を速やかに終了して次の入力データに対する検索処理に移行することができる。これにより、複数の入力データが連続して入力する場合に平均検索時間を短縮することができる。
【００４２】
なお、図３に示す実施例２では、判定部３０が一致検出部１０または不一致検出部２０に比較中止信号を出力する構成であるが、図４に示すように、一致検出部１０と不一致検出部２０との間で相互に比較中止信号を出力する構成でもよい。すなわち、不一致検出部２０は、不一致検出信号４を出力するとともに、一致検出部１０に対して比較中止信号８を出力する。一致検出部１０は、一致検出信号２または比較終了信号３を出力するとともに、不一致検出部２０に対して比較中止信号９を出力する。
【実施例３】
【００４３】
実施例３のデータ検索装置は、入力データと一致する一致登録データを検索し、当該入力データが一致登録データとして未登録のときに、当該入力データを不一致登録データとして不一致検出部２０に登録する不一致データの学習機能を特徴とする。
【００４４】
図５は、本発明のデータ検索装置の実施例３の構成例を示す。
図において、実施例３のデータ検索装置は、基本的機能が実施例１と同様の一致検出部１０、不一致検出部２０および判定部３０から構成される。ここでは、不一致判定される入力データが不一致検出部２０の不一致登録データとして登録されていない場合を想定する。すなわち、この入力データに対して、不一致検出部２０から不一致検出信号４が出力されず、一致検出部１０が比較終了信号３を出力し、判定部３０が不一致判定の判定信号５を出力する場合である。
【００４５】
一致検出部１０は、比較終了信号３を出力するとともに、更新信号２０１を不一致検出部２０に出力する。不一致検出部２０は、この更新信号２０１に応じて入力データ１を不一致登録データとして登録し、次の入力データ１に対して登録済みの不一致登録データおよび前回新たに登録した不一致登録データを用いて検索する。このように、実際に不一致判定したデータを不一致登録データとして用いるため、登録する不一致登録データの数が少ない場合でも短時間で不一致判定が可能になり、平均検索時間を短縮することができる。また、不一致登録データの数を減らすことができるので、メモリ容量の削減、動作速度の向上、消費電力の削減の各効果を得ることができる。
【００４６】
なお、入力データが不一致検出部２０の不一致登録データとして既に登録されている場合には、不一致検出部２０が不一致検出信号４を出力するとともに、一致検出部１０が比較終了信号３および更新信号２０１を出力することになる。この場合、不一致検出部２０は更新信号２０１を無視する。あるいは、実施例２に示すように、比較中止信号を用いて更新信号２０１の出力を停止するか、更新信号２０１に対応する動作を停止するようにしてもよい。
【実施例４】
【００４７】
実施例１の不一致検出部２０は、不一致登録データ格納部から不一致登録データを読み出して入力データと比較し、一致する場合に不一致登録信号４を出力した。実施例４の不一致検出部は、不一致登録データ格納部から入力データと一致する不一致登録データが登録されているか否かを示す有無信号を読み出し、有無信号が「有」を示す場合に不一致検出信号４を出力することを特徴とする。
【００４８】
図６は、実施例４における不一致検出部２１の構成例を示す。
図において、不一致検出部２１は、レジスタ４０、一致比較回路５２および不一致登録データ格納部６２から構成される。不一致検出部２１に入力する入力データ１は、レジスタ４０で一時的に保持され、一致比較回路５２に比較データ１１１として出力される。一致比較回路５２は比較データ１１１を入力すると、不一致登録データ格納部６２を構成するメモリのアドレスに変換した比較データ１１５を出力する。不一致登録データ格納部６２は、メモリのアドレスと不一致登録データを対応させて登録／未登録の有無情報を保持しており、比較データ１１５で示されるアドレスから不一致登録データの有無に応じた有無信号１１６を読み出し、一致比較回路５２に出力する。一致比較回路５２は、有無信号１１６が「有」を示していれば不一致検出信号４を出力する。
【００４９】
図７は、不一致登録データ格納部６２の構成例を示す。
図において、不一致登録データ格納部６２はメモリ８０で構成される。メモリ８０は、不一致登録データの値と等しいアドレスに「有」を示す情報を格納し、それ以外のアドレスに「無」を示す情報を格納している。不一致登録データ格納部６２に入力する比較データ１１５は、メモリ８０の読み出しアドレスとなり、比較データ１１５の値に対応する不一致登録データの有無を示す有無信号１１６を出力する。
【００５０】
図８は、メモリ８０に格納する不一致登録データの作成方法を示す。ここでは、一致登録データから不一致登録データを作成する例を示す。一致登録データとして、20，35， 198，248 の４種類の数値が与えられているときに、メモリ８０の一致登録データの値と等しいアドレスに「無」を示す情報を格納し、それ以外のアドレスに「有」を示す情報を格納する。不一致登録データの更新は、一致登録データを更新する際に行う。すなわち、一致登録データを追加するときに、追加する一致登録データの値と等しいアドレスに「無」を示す情報を書き込む。一方、一致登録データを削除するときに、削除する一致登録データの値と等しいアドレスに「有」を示す情報を書き込む。
【００５１】
なお、一致登録データの値をハッシュ値に変換し、ハッシュ値に対応するアドレスに「無」を示す情報を格納してもよい。この場合の一致比較回路５２は、比較データ１１１をハッシュ値に変換した比較データ１１５を出力する。
【００５２】
このような図６〜図８に示す不一致登録データ格納部６２の構成により、入力データ１が不一致判定される場合には有無信号１１６は「有」を示し、一致比較回路５２は不一致検出信号４を出力する。逆に、入力データ１が一致判定される場合には有無信号１１６は「無」を示し、一致比較回路５２は不一致検出信号４を出力せず、入力データ１に対する検索処理を終了する。
【００５３】
なお、当該メモリ８０は、いわゆるＣＡＭ（連想メモリ）ではなく、一般のＲＡＭで構成することができるので、回路規模および消費電力の削減によるコスト低減効果を見込むことができる。
【００５４】
また、比較データ１１５を読み出しアドレスとして有無信号１１６を出力する不一致登録データ格納部６２は、例えばＣ言語等のプログラム言語で記述したソフトウェアに実施例４を適用する場合には、配列とポインタを使う方式であってもよい。
【００５５】
また、実施例４の不一致検出部２１は、１回のメモリ読み出し時間で、不一致登録データに一致する入力データを検出することができるので、平均検索時間を大幅に短縮することができる。以下、具体例を用いて説明する。
【００５６】
メモリからデータを読み出すのに１サイクルの時間を要し、一致登録データ数をＭとし、総数Ｎの入力データを検索する場合を想定する。また、Ｎ個の入力データには、ｃサイクルの時間で一致となる入力データがｐ個あるとすると、既存の検索方法による合計検索時間Ｖサイクルは、不一致を判定するまでＭサイクルかかるため、
Ｖ＝（ｐ＊ｃ＋Ｍ＊(Ｎ−ｐ))／Ｎ
となる。
【００５７】
一方、一致検出部１０を線形探索方法で実現し、不一致検出部２１を実施例４の方法で実現する場合、不一致を１サイクルで判定できる入力データがｚ個存在すると、合計検索時間Ｗサイクルは、
Ｗ＝（ｐ＊ｃ＋ｚ＋Ｍ＊(Ｎ−ｐ−ｚ))／Ｎ
となる。ここで、ｚ≧０かつＮ≧１の場合、
Ｖ−Ｗ＝ｚ＊(Ｍ−１)／Ｎ≧０
が常に成立するため、実施例４の構成により検索時間を短縮できることがわかる。
【００５８】
また、実施例４の不一致検出部２１のメモリ８０を用いた構成は、一致検出部２０にも同様に適用することができる。この場合、一致検出部２０の一致登録データ格納部を構成するメモリと、不一致検出部２１の不一致登録データ格納部６２を構成するメモリ８０のデータは、各アドレスの情報が「有」と「無」で逆になる。
【００５９】
また、図６に示す一致比較回路５２において、有無信号１１６が「有」を示すときは不一致検出信号４を出力し、有無信号１１６が「無」を示すときは一致検出信号２を出力する構成とすれば、一致検出部１０と不一致検出部２１の共用が可能となる。すなわち、図９に示すように、不一致検出部２１と一致検出部１０の機能を１つのメモリを含む構成で実現した一致／不一致検出部１５と判定部３０でデータ検索装置を構成することができる。
【実施例５】
【００６０】
実施例５の不一致検出部は、入力データと一致登録データをそれぞれ複数に分割し、分割した入力データのいずれかで不一致となれば不一致検出信号４を出力することを特徴とする。
【００６１】
図１０は、実施例５における不一致検出部２２の構成例を示す。
図において、不一致検出部２２は、データ分割回路４１、複数ｔ個の分割不一致検出部２３−１〜２３−ｔ、集計部９０から構成される。不一致検出部２２に入力するｎビットの入力データ１は、データ分割回路４１において、図１１に示すようにｍビットの分割データ１−１〜１−ｔにｔ分割され（ｎ＝ｍ×ｔ）、分割不一致検出部２３−１〜２３−ｔにそれぞれ入力する。分割不一致検出部２３−１〜２３−ｔは、図１２に示すようにｎビットの一致登録データ１１３をｔ分割したｍビットの分割一致登録データ１１３−１〜１１３−ｔをそれぞれ有し、それぞれ分割データ１−１〜１−ｔと不一致の場合に分割不一致検出信号４−１〜４−ｔを出力する。各分割不一致検出信号４−１〜４−ｔは集計部９０で集計され、分割不一致検出信号４−１〜４−ｔの少なくとも１つを入力した場合に不一致検出信号４を出力する。
【００６２】
なお、入力データおよび一致登録データは均等分割でなくてもよく、分割した入力データと一致登録データが互いに対応するビット数であればよい。
【００６３】
図１１および図１２に示す例では、分割データ１−２が「０」、分割一致登録データ１１３−２が「１２０」であるので、分割不一致検出部２３−２から分割不一致検出信号４−２が出力され、入力データ１は一致登録データ１１３と一致していないとして集計部９０から不一致検出信号４が出力される。
【００６４】
図１３は、分割不一致検出部２３の構成例を示す。
図において、分割不一致検出部２３−１〜２３−ｔは、実施例４と同様にメモリで構成された一致登録データ格納部８１−１〜８１−ｔを備える。一致登録データ１１３をｔ分割し、それぞれの値と等しいアドレスに「有」、その他のアドレスに「無」を示す情報が書き込まれる。分割データ１−１〜１−ｔをアドレスとして入力し、対応する情報が「無」であれば分割不一致検出信号４−１〜４−ｔを出力する。
【００６５】
実施例５の不一致検出部２２は、実施例４の不一致検出部２１に比べて保持する不一致登録データ数を削減することができ、メモリ容量の削減、動作速度の向上、消費電力の削減によるコスト低減効果を見込むことができる。
【実施例６】
【００６６】
実施例１のデータ検索装置は、一致検出部１０と不一致検出部２０が並列に入力データに対する検索処理を実施していた。実施例６のデータ検索装置は、初めに不一致検出部が入力データに対する検索処理を行い、入力データと不一致登録データが一致しないときに一致検出部で検索処理を行うことを特徴とする。
【００６７】
図１４は、本発明のデータ検索装置の実施例６の構成例を示す。
図において、実施例６のデータ検索装置は、一致検出部１１、不一致検出部２２および判定部３０から構成される。不一致検出部２２は、入力データ１に一致する不一致登録データが未登録であり、不一致検出信号４を判定部３０に出力しないときに、検索指示信号２０２を一致検出部１１に出力する。一致検出部１１は、この検索指示信号２０２を入力したときに検索を開始し、一致検出信号２または比較終了信号３を判定部３０に出力する。
【００６８】
図１５は、実施例６における一致検出部１１の構成例を示す。
図において、一致検出部１１は、レジスタ４０、一致比較回路５３および一致登録データ格納部６０から構成される。一致検出部１１に入力する入力データ１は、レジスタ４０で一時的に保持され、一致比較回路５３に比較データ１１１として出力される。一致比較回路５３は、検索指示信号２０２および比較データ１１１を入力したときに、一致登録データ格納部６０に要求信号１１２を出力し、一致登録データ格納部６０から１つずつ読み出した一致登録データ１１３と比較データ１１１とを比較する。このとき、一致登録データ１１３と比較データ１１１が一致すれば、一致比較回路５３は一致検出信号２を出力する。一方、一致登録データ格納部６０から読み出す一致登録データがなくなった場合には、一致比較回路５３は比較終了信号３を出力する。
【００６９】
このように、実施例６のデータ検索装置は、不一致検出部２２で不一致を検出しない場合のみ一致検出部１１が処理を実行する。判定部３０は、不一致検出部２２から不一致検出信号４を入力すれば不一致判定の判定信号５を出力し、不一致検出信号４を入力しない場合には、一致検出部１１から出力される一致検出信号２または比較終了信号３によって一致判定または不一致判定の判定信号５を出力する。これにより、一致検出部１１と不一致検出部２２の並列動作に比べて消費電力の削減が可能となる。
【００７０】
なお、不一致検出部２２が不一致検出信号４を出力した場合には、実施例２のように判定部３０または不一致検出部２２が一致検出部１１の動作を停止するように制御してもよい。
【実施例７】
【００７１】
実施例７のデータ検索装置は、実施例６のデータ検索装置の機能に加えて、入力データを一時的に保持し、一致判定または不一致判定の判定信号５とともに、検索対象の入力データを被検索データとして出力することを特徴とする。
【００７２】
図１６は、本発明のデータ検索装置の実施例７の構成例を示す。
図において、実施例７のデータ検索装置は、一致検出部１２、不一致検出部２３および判定部３１から構成される。不一致検出部２３は、入力データ１と不一致登録データの一致を検出したときに不一致検出信号４を出力し、同時に検索対象の入力データ１を被検索データ２０４として出力する。また、不一致検出部２３は、入力データ１に一致する不一致登録データが未登録であり、不一致検出信号４を判定部３１に出力しないときに検索指示信号２０２を一致検出部１２に出力する。
【００７３】
一致検出部１２は、検索指示信号２０２を入力したときの入力データ１について検索を開始し、一致検出信号２または比較終了信号３を判定部３１に出力する。また、一致検出部１２は、一致検出信号２または比較終了信号３を出力するときに、検索対象の入力データ１を被検索データ２０３として出力する。
【００７４】
判定部３１は、一致検出信号２に応じて一致判定の判定信号５を出力するか、比較終了信号３または不一致検出信号４に応じて不一致判定の判定信号５を出力するとともに、被検索データ２０３または被検索データ２０４をそのまま被検索データ２０５として出力する。
【００７５】
図１７は、実施例７における一致検出部１２の構成例を示す。
図において、一致検出部１２は、レジスタ４０、バッファ回路７０、バッファ制御回路７１、一致比較回路５４および一致登録データ格納部６０から構成される。一致検出部１１に入力する入力データ１は、レジスタ４０で一時的に保持され、バッファ回路７０に比較データ１１１として出力される。バッファ回路７０は、検索指示信号２０２を入力したときの比較データ１１１を記憶し、バッファ制御回路７１から読み出し信号１２３を入力したときに記憶したデータを比較データ１２４としてバッファ制御回路７１に出力する。
【００７６】
バッファ制御回路７１は、一致比較回路５４から比較イネーブル信号１２５を入力したときに、バッファ回路７０に読み出し信号１２３を出力し、バッファ回路７０に記憶したデータを比較データ１２４として読み出す。さらに、バッファ制御回路７１は、比較データ１２４を比較データ１２６として一致比較回路５４に出力し、次の比較イネーブル信号１２５を入力するまで比較データ１２６を保持する。
【００７７】
一致比較回路５４は、比較データ１２６を入力すると一致登録データ格納部６０に要求信号１１２を出力し、一致登録データ格納部６０から１つずつ読み出した一致登録データ１１３と比較データ１２６とを比較する。このとき、一致登録データ１１３と比較データ１２６が一致すれば、一致比較回路５４は一致検出信号２を出力する。一方、一致登録データ格納部６０から読み出す一致登録データがなくなった場合には、一致比較回路５４は比較終了信号３を出力する。また、一致比較回路５４は、一致検出信号２または比較終了信号３を出力するときに、検索対象の比較データ１２６を被検索データ２０３として出力し、次の比較イネーブル信号１２５をバッファ制御回路７１に出力する。
【００７８】
ここで、図１８のタイミングチャートを参照して実施例７のデータ検索装置の動作例について説明する。
入力データ１は、一致検出部１２および不一致検出部２３に入力され、初めに不一致検出部２３で検索が実行される。ここでは、入力データ１をａ，ｂ，ｃとし、入力データａ，ｃが一致判定され、入力データｂが不一致判定されるものとする。
【００７９】
不一致検出部２３は、入力データａをレジスタに一時的に保持し、レジスタから出力された入力データａと不一致登録データの一致を検出したときに不一致検出信号４を出力するとともに、入力データａを被検索データ２０４として出力する。判定部３１は、入力データａに対して、不一致判定の判定信号５および被検索データ２０５を出力する。次に、不一致検出部２３は入力データｂについて同様に検索し、不一致登録データとの一致を検出しない場合は、検索指示信号２０２を一致検出部１２に出力する。次に、不一致検出部２３は入力データｃについて同様に検索を開始する。このように、不一致検出部２３は、不一致を検出した場合でも、不一致を検出しない場合でも、入力データ１に対する処理が終了すると、ただちに次の入力データの検索処理を開始する。
【００８０】
一方、一致検出部１２のレジスタ４０は、入力データａ，ｂ，ｃを入力して比較データ１１１としてバッファ回路７０に出力しているが、バッファ回路７０は検索指示信号２０２を入力したときの入力データｂを記憶する。このとき、バッファ制御回路７１は比較イネーブル信号１２５を入力し、バッファ回路７０は読み出し信号１２３を入力しているので、バッファ回路７０は入力データｂを読み出し、比較データ１２４としてバッファ制御回路７１に出力し、さらにバッファ制御回路７１は一致比較回路５４に比較データ１２６として出力する。バッファ制御回路７１は比較データ１２６として入力データｂを出力すると、バッファ回路７０に対する読み出し信号１２３はオフとなり、入力データｂが保持される。
【００８１】
一致比較回路５４は、要求信号１１２を一致登録データ格納部６０に出力して読み出される一致登録データ１１３と入力データｂが一致するか否か検索を開始すると、比較イネーブル信号１２５をオフとする。ここで、一致比較回路５４が一致登録データ１１３と入力データｂの一致を検出すると、一致検出信号２とともに被検索データ２０３として入力データｂを出力する。なお、比較終了信号３を出力する場合も同様に被検索データ２０３として入力データｂを出力する。また、一致比較回路５４は検索処理が終了すると、比較イネーブル信号１２５をオンとし、バッファ制御回路７１を介してバッファ回路７０に記憶されている比較データ１２４の読み出しを行う。この比較データ１２４は、不一致検出部２３で不一致を検出しなかった入力データであり、同様に一致登録データとの検索処理に入る。
【００８２】
判定部３１は、一致検出部１２と不一致検出部２３から出力される信号により一致判定または不一致判定の判定信号５を出力するとともに、被検索データ２０３または被検索データ２０４を被検索データ２０５として出力する。
【００８３】
図１８に示すタイミングチャートでは、入力データａ，ｃに対する不一致判定の判定信号５が先に出力され、遅れて入力データｂに対する一致判定の判定信号５が出力される。すなわち、入力データの入力順番と、判定結果が出力される順番が異なることになるが、被検索データ２０５とともに出力されるので後段処理部で一致、不一致の判定結果に基づく処理には特に支障ない。あるいは、判定部３１にバッファ回路を備え、入力データの入力順番で判定結果を出力するようにしてもよい。
【００８４】
また、一致検出部１２と不一致検出部２３は、上記のように検索動作は互いに独立であるので、判定部３１に対して同時に、異なる入力データに対する検索結果を出力することがある。この場合には、例えば判定部３１で不一致検出部２３からの出力を一時的に記憶し、一致検出部１２からの信号を優先的に選択して判定処理を行い、その後に不一致検出部２３からの信号に対する判定処理を行ってもよい。なお、一致検出部１２と不一致検出部２３の出力に対する処理順番は逆でもよい。
【００８５】
実施例６では、不一致検出部２２で不一致を検出できない場合に、一致検出部１２の処理が終了するまで不一致検出部２２は次の入力データを処理することができなかった。実施例７では、一致検出部１２が入力データｂに対する検索処理を行っている場合でも、不一致検出部２３は次の入力データｃに対する検索処理が可能である。そのため、実施例７の構成では、入力データの大部分が不一致判定される場合に、他の実施例に比べてさらに平均検索時間を短縮し、消費電力の削減が可能である。
【実施例８】
【００８６】
以上説明した実施例１〜実施例７の構成および機能はハードウェアで実現するだけでなく、プログラム言語で記述したソフトウェアとコンピュータで実現することもできる。また、当該プログラムを記録媒体に記録することも、ネットワークを通して提供することも可能である。
【産業上の利用可能性】
【００８７】
本発明は、入力データの多くが不一致判定されるような場合に、平均検索時間を短縮するデータ検索装置および方法として有用である。
【符号の説明】
【００８８】
１０，１１，１２  一致検出部
１５  一致／不一致検出部
２０，２１，２２，２３  不一致検出部
２３  分割不一致検出部
３０，３１  判定部
４０  レジスタ
４１  データ分割回路
５１，５２，５３，５４  一致比較回路
６１，６２  不一致登録データ格納部
７０  バッファ回路
７１  バッファ制御回路
８０，８１  メモリ
９０  集計部
【先行技術文献】
【特許文献】
【００８９】
【特許文献１】特開平１０−１２６４４２号公報
【非特許文献】
【００９０】
【非特許文献１】David E.Taylor,"Survey and Taxonomy of Packet Classification Techniques", ACM Computing Surveys,Vol.37, No.3，September 2005,pp.238-275
【非特許文献２】弓場、星、「木構造を用いた見出し探索の技法」、情報処理、Vol.21, No.1, January 1980, pp.28-49
【図１】
2010165102.tif 000005
【図２】
2010165102.tif 000006
【図３】
2010165102.tif 000007
【図４】
2010165102.tif 000008
【図５】
2010165102.tif 000009
【図６】
2010165102.tif 000010
【図７】
2010165102.tif 000011
【図８】
2010165102.tif 000012
【図９】
2010165102.tif 000013
【図１０】
2010165102.tif 000014
【図１１】
2010165102.tif 000015
【図１２】
2010165102.tif 000016
【図１３】
2010165102.tif 000017
【図１４】
2010165102.tif 000018
【図１５】
2010165102.tif 000019
【図１６】
2010165102.tif 000020
【図１７】
2010165102.tif 000021
【図１８】
2010165102.tif 000022
【図１９】
2010165102.tif 000023
【図２０】
2010165102.tif 000024