(57)【特許請求の範囲】
【請求項１】
比較対象値が格納されるメモリと、このメモリに格納された前記比較対象値と被探索値とを比較する比較器と、この比較器の比較結果にしたがって二つの方路のいずれかに前記被探索値を出力するセレクタとを含むスイッチ手段が設けられ、
このスイッチ手段の一つまたは複数の縦続接続により、二分探索木を互いに相似な複数の部分木に分割したときの一つの部分木に相応するデータ探索手段が構成され、
前記二分探索木の複数の前記部分木には、それぞれアドレスが割当てられ、
前記データ探索手段が前記アドレスにより指定される前記部分木として機能するための比較対象値を前記メモリに設定する手段を備え、
前記被探索値が前記部分木に相応する前記データ探索手段から出力されるときには当該部分木が最終段でない場合は次段の前記部分木のアドレスも併せて出力する手段を備え、
前記設定する手段は、当該出力する手段により出力されたアドレスに基づき次段の前記部分木として機能するための比較対象値を前記メモリに設定するメモリ設定手段を含み、
このメモリ設定手段により前記メモリの比較対象値が次段の前記部分木に相応する値に設定された後に前記データ探索手段から出力された前記被探索値を再び前記データ探索手段に入力する手段を備えた
ことを特徴とする二分探索器。
【請求項２】
前記入力する手段は、前記メモリ設定手段により前記メモリの比較対象値が次段の前記部分木に相応する値に設定されるまで前記データ探索手段から出力された前記被探索値の前記データ探索手段への再入力を遅延させる手段を備えた請求項１記載の二分探索器。
【請求項３】
比較対象値が格納されるメモリと、このメモリに格納された前記比較対象値と被探索値とを比較する比較器と、この比較器の比較結果にしたがって二つの方路のいずれかに前記被探索値を出力するセレクタとを含むスイッチ手段が設けられ、
このスイッチ手段の一つまたは複数の縦続接続により、二分探索木を互いに相似な複数の部分木に分割したときの一つの部分木に相応するデータ探索手段が構成され、
前記二分探索木の複数の前記部分木には、それぞれアドレスが割当てられ、
前記データ探索手段が前記二分探索木と等しい段数Ｎ（Ｎは自然数）で縦続に接続され、
Ｍ（Ｍは自然数、Ｍ＜Ｎ）段目の前記データ探索手段が前記アドレスにより指定される前記部分木として機能するための比較対象値をＭ段目の前記データ探索手段を構成する前記スイッチ手段の前記メモリに設定する手段を備え、
前記被探索値が前記部分木に相応するＭ段目の前記データ探索手段から出力されるときには当該部分木が最終段でない場合は次段の前記部分木のアドレスも併せて出力する手段を備え、
前記設定する手段は、当該出力する手段により出力されたアドレスに基づき次段の前記部分木として機能するための比較対象値をＭ＋１段目の前記データ探索手段を構成する前記スイッチ手段の前記メモリに設定するメモリ設定手段を含み、
このメモリ設定手段により前記メモリの比較対象値が次段の前記部分木に相応する値に設定された後にＭ段目の前記データ探索手段から出力された前記被探索値をＭ＋１段目の前記データ探索手段に入力する手段を備えた
ことを特徴とする二分探索器。
【請求項４】
前記入力する手段は、前記メモリ設定手段により前記メモリの比較対象値が次段の前記部分木に相応する値に設定されるまでＭ段目の前記データ探索手段から出力された前記被探索値のＭ＋１段目の前記データ探索手段への入力を遅延させる手段を備えた請求項３記載の二分探索器。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は二分探索木を用いたデータ分類に利用する。特に、二分探索木をハードウェアにより実装する技術に関する。
【０００２】
【従来の技術】
データを分類するための手法として、あるデータの被探索値を一つの探索器の入力ポートから入力し、この被探索値が所定の経路を辿って複数の出力ポートのいずれかから出力されたときに、そのデータを当該出力ポートによって定まる一つの集合に分類することができる。
【０００３】
従来から知られているデータ探索の一般的な手法として二分探索木を用いたｂｉｎａｒｙ  ｓｅａｒｃｈという手法がある。この手法は、データ数Ｎに対してｌｏｇ（Ｎ）回の探索回数でデータを得ることができる。図８に二分探索木を示す。二分探索木は、複数の部分木に分割することができる。これら複数の部分木は互いに相似している。
【０００４】
【発明が解決しようとする課題】
従来、データ探索はソフトウェアにより実装されている。このようなソフトウェアによるデータ探索に対し、より高速性を求めて、ハードウェアを用いたデータ探索も検討されている。例えば、ハードウェアの例として、ＦＰＧＡ(Field Programmable Gate Array)、ＣＡＭ(Content Addressable Memory)が挙げられる。
【０００５】
しかし、前述した二分探索木を用いたデータ探索手法をＣＡＭまたはＦＰＧＡにより実装することを考えてみると、ＣＡＭは高速であるが、扱えるデータ量に制限があるため、大きなデータを探索することは困難である。二分探索木は、一般に、大きなデータ量となるため、ＣＡＭにより実現することは困難である。また、ＦＰＧＡは論理の自由度が大きく、ＣＡＭほど高速に探索できないため、二分探索木の全体をハードウェアにより実装すると、ハードウェア化する価値が低くなるという問題がある。
【０００６】
本発明は、このような背景に行われたものであって、ハードウェアに実装することができ、処理速度を高速化することができる二分探索器を提供することを目的とする。
【０００７】
【課題を解決するための手段】
本発明は一つの二分探索木が複数の相似した部分木から構成されていることに着目し、二分探索木の全体ではなく、その部分木の一つまたは複数をハードウェアにより実装し、このハードウェアにより実装した部分木に二分探索木を構成するあらゆる部分木に相応する機能をプログラマブルに実現させることにより、仮想的に二分探索木全体をハードウェアによって実装することを特徴とする。
【０００８】
これにより、二分探索木の全体をハードウェアにより実装する場合と比較して少ないハードウェア量によって二分探索木を実装することができ、二分探索木をソフトウェアにより実装した場合と比較して処理速度を高めることができる。例えば、前述したＦＰＧＡによって部分木をハードウェアにより実装することができるが、少ないハードウェア量により実装することができるので、二分探索木の全体をソフトウェアにより実装した場合と比較して処理速度を高めることができる。
【０００９】
すなわち、本発明は、比較対象値が格納されるメモリと、このメモリに格納された前記比較対象値と被探索値とを比較する比較器と、この比較器の比較結果にしたがって二つの方路のいずれかに前記被探索値を出力するセレクタとを含むスイッチ手段が設けられ、このスイッチ手段の一つまたは複数の縦続接続により、二分探索木を互いに相似な複数の部分木に分割したときの一つの部分木に相応するデータ探索手段が構成され、前記二分探索木の複数の前記部分木には、それぞれアドレスが割当てられ、前記データ探索手段が前記アドレスにより指定される前記部分木として機能するための比較対象値を前記メモリに設定する手段を備え、前記被探索値が前記部分木に相応する前記データ探索手段から出力されるときには当該部分木が最終段でない場合は次段の前記部分木のアドレスも併せて出力する手段を備え、前記設定する手段は、当該出力する手段により出力されたアドレスに基づき次段の前記部分木として機能するための比較対象値を前記メモリに設定するメモリ設定手段を含み、このメモリ設定手段により前記メモリの比較対象値が次段の前記部分木に相応する値に設定された後に前記データ探索手段から出力された前記被探索値を再び前記データ探索手段に入力する手段を備えたことを特徴とする二分探索器である。
【００１０】
前記入力する手段は、前記メモリ設定手段により前記メモリの比較対象値が次段の前記部分木に相応する値に設定されるまで前記データ探索手段から出力された前記被探索値の前記データ探索手段への再入力を遅延させる手段を備えることもできる。
【００１１】
あるいは、本発明は、比較対象値が格納されるメモリと、このメモリに格納された前記比較対象値と被探索値とを比較する比較器と、この比較器の比較結果にしたがって二つの方路のいずれかに前記被探索値を出力するセレクタとを含むスイッチ手段が設けられ、このスイッチ手段の一つまたは複数の縦続接続により、二分探索木を互いに相似な複数の部分木に分割したときの一つの部分木に相応するデータ探索手段が構成され、前記二分探索木の複数の前記部分木には、それぞれアドレスが割当てられ、前記データ探索手段が前記二分探索木と等しい段数Ｎ（Ｎは自然数）で縦続に接続され、Ｍ（Ｍは自然数、Ｍ＜Ｎ）段目の前記データ探索手段が前記アドレスにより指定される前記部分木として機能するための比較対象値をＭ段目の前記データ探索手段を構成する前記スイッチ手段の前記メモリに設定する手段を備え、前記被探索値が前記部分木に相応するＭ段目の前記データ探索手段から出力されるときには当該部分木が最終段でない場合は次段の前記部分木のアドレスも併せて出力する手段を備え、前記設定する手段は、当該出力する手段により出力されたアドレスに基づき次段の前記部分木として機能するための比較対象値をＭ＋１段目の前記データ探索手段を構成する前記スイッチ手段の前記メモリに設定するメモリ設定手段を含み、このメモリ設定手段により前記メモリの比較対象値が次段の前記部分木に相応する値に設定された後にＭ段目の前記データ探索手段から出力された前記被探索値をＭ＋１段目の前記データ探索手段に入力する手段を備えたことを特徴とする二分探索器である。
【００１２】
前記入力する手段は、前記メモリ設定手段により前記メモリの比較対象値が次段の前記部分木に相応する値に設定されるまでＭ段目の前記データ探索手段から出力された前記被探索値のＭ＋１段目の前記データ探索手段への入力を遅延させる手段を備えることもできる。
【００１３】
【発明の実施の形態】
本発明実施例を図１ないし図７を参照して説明する。図１は第一実施例の二分探索器の構成図である。図２は本実施例の部分木構成を示す図である。図３は第二実施例の二分探索器の構成図である。図４は第二実施例の二分探索器の動作を説明するための図である。図５は第三実施例の二分探索器の構成図である。図６は第四実施例の二分探索器の構成図である。図７は第五実施例の二分探索器の構成図である。
【００１４】
（第一実施例）
第一実施例を図１および図２を参照して説明する。第一実施例は、図２に示すように、比較対象値が格納されるメモリ１と、このメモリ１に格納された前記比較対象値と被探索値とを比較する比較器２と、この比較器２の比較結果にしたがって二つの方路のいずれかに前記被探索値を出力するセレクタ３とを含むスイッチ回路４が設けられ、図１に示すように、このスイッチ回路４の一つまたは複数の縦続接続により、図８に示す二分探索木を互いに相似な複数の部分木に分割したときの一つの部分木に相応するデータ探索回路５が構成され、前記二分探索木の複数の前記部分木には、それぞれアドレスが割当てられ、データ探索回路５が前記アドレスにより指定される前記部分木として機能するための比較対象値をメモリ１に設定するプログラマブルスイッチ要素６を備え、前記被探索値が前記部分木に相応するデータ探索回路５から出力されるときには当該部分木が最終段でない場合は次段の前記部分木のアドレスも併せて出力するためのメモリ７およびセレクタ８を備え、プログラマブルスイッチ要素６は、セレクタ８により出力されたアドレスに基づき次段の前記部分木として機能するための比較対象値をメモリ１に設定し、このメモリ設定によりメモリ１の比較対象値が次段の前記部分木に相応する値に設定された後にデータ探索回路５から出力された前記被探索値を再びデータ探索回路５に入力することを特徴とする二分探索器である。
【００１５】
すなわち、二分探索木は、図８に示すように、複数の互いに相似な部分木に分割することができる。第一実施例は、この部分木の一つを一つのデータ探索回路５により実装することを特徴とする。
【００１６】
記憶要素９には、各部分木に相応するデータ探索回路５のメモリ１に格納する比較対象値が記録されており、プログラマブルスイッチ要素６の指示により、記憶要素９に記録されている比較対象値はメモリ１に記録される。具体的には、各部分木にはアドレスが設定されており、このアドレスと記憶要素９の記憶領域のアドレスとが対応しており、プログラマブルスイッチ要素６はこのアドレスを用いて記憶要素９の記憶領域に記録されている比較対象値をメモリ１に転送する。このように、アドレスの指定によって、データ探索回路５は、二分探索木を構成するあらゆる部分木として機能することができる。
【００１７】
図８の二分探索木を例にして、第一実施例の二分探索器の動作を説明する。被探索値を入力ポートから入力すると、左から９番目の出力ポートに出力が現れる例を説明する。
【００１８】
ユーザあるいは他装置からプログラマブルスイッチ要素６に対してデータ探索開始を指示すると、プログラマブルスイッチ要素６は、図１に示すデータ探索回路５に、部分木＃１に相応する機能を実現させるため、アドレス＃１を指定して記憶要素９の記憶領域からメモリ１に比較対象値を転送する。これにより、データ探索回路５は、部分木＃１に相応する機能を実現する。このような状況下で、入力ポートから被探索値が入力される。
【００１９】
データ探索回路５が部分木＃１に相応する機能を実現しているときには、図２に示すメモリ７には、部分木＃１の出力方路に当たる全ての部分木のアドレスが格納されている。この例では、部分木＃１の出力は部分木＃２に出力されるので、部分木最終段に相応するスイッチ回路４のメモリ７からアドレス＃２が取り出され、被探索値とともにプログラマブルスイッチ要素６に出力される。
【００２０】
プログラマブルスイッチ要素６では、これを受けると、データ探索回路５に部分木＃２に相応する機能を実現させるため、アドレス＃２を指定して記憶要素９の記憶領域からメモリ１に比較対象値を転送する。これにより、データ探索回路５は、部分木＃２に相応する機能を実現する。このような状況下で、部分木＃２の入力ポートから被探索値が入力される。
【００２１】
データ探索回路５が部分木＃２に相応する機能を実現しているときには、図２に示すメモリ７には、部分木＃２の出力方路に当たる全ての部分木のアドレスが格納されている。この例では、部分木＃２の出力は部分木＃３に出力されるので、部分木最終段に相応するスイッチ回路４のメモリ７からアドレス＃３が取り出され、被探索値とともにプログラマブルスイッチ要素６に出力される。
【００２２】
プログラマブルスイッチ要素６では、これを受けると、データ探索回路５に部分木＃３に相応する機能を実現させるため、アドレス＃３を指定して記憶要素９の記憶領域からメモリ１に比較対象値を転送する。これにより、データ探索回路５は、部分木＃３に相応する機能を実現する。このような状況下で、部分木＃３の入力ポートから被探索値が入力される。
【００２３】
部分木＃３の入力ポートから入力された被探索値は、二分探索木の左から９番目の出力ポートに当たる部分木＃３の出力ポートから出力される。部分木＃３は二分探索木の最終段であるので、アドレスの出力は行われない。プログラマブルスイッチ要素６では、アドレスの出力が行われないことから、部分木＃３が二分探索木の最終段であると認識し、出力結果をユーザまたは他装置に通知する。これにより、データ探索が終了する。
【００２４】
（第二実施例）
第二実施例を図２ないし図４を参照して説明する。第二実施例は、図２に示すように、比較対象値が格納されるメモリ１と、このメモリ１に格納された前記比較対象値と被探索値とを比較する比較器２と、この比較器２の比較結果にしたがって二つの方路のいずれかに前記被探索値を出力するセレクタ３とを含むスイッチ回路４が設けられ、このスイッチ回路４の一つまたは複数の縦続接続により、図８に示す二分探索木を互いに相似な複数の部分木に分割したときの一つの部分木に相応するデータ探索回路５−１〜５−３が構成され、前記二分探索木の複数の前記部分木には、それぞれアドレスが割当てられ、図３に示すように、データ探索回路５が図８に示す二分探索木と等しい段数３で縦続に接続され、図４に示すように、Ｍ（Ｍは自然数、Ｍ＜３）段目のデータ探索回路５−Ｍが前記アドレスにより指定される前記部分木として機能するための比較対象値をＭ段目のデータ探索回路５−Ｍを構成するスイッチ回路４のメモリ１に設定するプログラマブルスイッチ要素６を備え、前記被探索値が前記部分木に相応するＭ段目のデータ探索回路５−Ｍから出力されるときには当該部分木が最終段でない場合は次段の前記部分木のアドレスも併せて出力するためのメモリ７およびセレクタ８を備え、プログラマブルスイッチ要素６は、セレクタ８により出力されたアドレスに基づき次段の前記部分木として機能するための比較対象値をＭ＋１段目のデータ探索回路５−（Ｍ＋１）を構成するスイッチ回路４のメモリ１に設定し、このメモリ設定によりメモリ１の比較対象値が次段の前記部分木に相応する値に設定された後にＭ段目のデータ探索回路５−Ｍから出力された前記被探索値をＭ＋１段目のデータ探索回路５−（Ｍ＋１）に入力することを特徴とする二分探索器である。
【００２５】
第二実施例は、データ探索回路５−１〜５−３を三段縦続に接続した例である。これにより、図８に示す部分木＃１〜＃３に相応する部分木を三段縦続に接続されたデータ探索回路５−１〜５−３により実現する。
【００２６】
図８の二分探索木を例にして、第二実施例の二分探索器の動作を説明する。被探索値を入力ポートから入力すると、左から９番目の出力ポートに出力が現れる例を説明する。
【００２７】
ユーザあるいは他装置からプログラマブルスイッチ要素６−１に対してデータ探索開始を指示すると、プログラマブルスイッチ要素６−１は、データ探索回路５−１に、部分木＃１に相応する機能を実現させるため、図４に示すように、アドレス＃１を指定して記憶要素９の記憶領域からメモリ１に比較対象値を転送する。これにより、データ探索回路５−１は、部分木＃１に相応する機能を実現する。このような状況下で、入力ポートから被探索値が入力される。
【００２８】
データ探索回路５−１が部分木＃１に相応する機能を実現しているときには、図２に示すメモリ７には、部分木＃１の出力方路に当たる全ての部分木のアドレスが格納されている。この例では、部分木＃１の出力は部分木＃２に出力されるので、部分木最終段に相応するスイッチ回路４のメモリ７からアドレス＃２が取り出され、被探索値とともにプログラマブルスイッチ要素６−１に出力される。
【００２９】
プログラマブルスイッチ要素６−１では、これを受けると、データ探索回路５に部分木＃２に相応する機能を実現させるため、アドレス＃２を指定して記憶要素９の記憶領域からメモリ１に比較対象値を転送する。これにより、データ探索回路５−２は、部分木＃２に相応する機能を実現する。このような状況下で、部分木＃２の入力ポートから被探索値が入力される。
【００３０】
データ探索回路５−２が部分木＃２に相応する機能を実現しているときには、図２に示すメモリ７には、部分木＃２の出力方路に当たる全ての部分木のアドレスが格納されている。この例では、部分木＃２の出力は部分木＃３に出力されるので、部分木最終段に相応するスイッチ回路４のメモリ７からアドレス＃３が取り出され、被探索値とともにプログラマブルスイッチ要素６−２に出力される。
【００３１】
プログラマブルスイッチ要素６−２では、これを受けると、データ探索回路５−３に部分木＃３に相応する機能を実現させるため、アドレス＃３を指定して記憶要素９の記憶領域からメモリ１に比較対象値を転送する。これにより、データ探索回路５−３は、部分木＃３に相応する機能を実現する。このような状況下で、部分木＃３の入力ポートから被探索値が入力される。
【００３２】
部分木＃３の入力ポートから入力された被探索値は、二分探索木の左から９番目の出力ポートに当たる部分木＃３の出力ポートから出力される。部分木＃３は二分探索木の最終段であるので、アドレスの出力は行われない。この出力結果をユーザまたは他装置はデータ探索結果として認識する。
【００３３】
（第三実施例）
第三実施例を図５を参照して説明する。第二実施例のデータ探索回路５は、三つのスイッチ回路４により構成されていたが、第三実施例のデータ探索回路５は、六つのスイッチ回路４により構成される。このように、元となる二分探索木の構成によって、スイッチ回路４の数および段数を任意に加減してハードウェアにより実装する。
【００３４】
（段四実施例）
第四実施例を図６を参照して説明する。第四実施例では、プログラマブルスイッチ要素６によりメモリ１の比較対象値が次段の部分木に相応する値に設定されるまでデータ探索回路５から出力された被探索値のデータ探索回路５への再入力を遅延させる遅延素子１０を備える。
【００３５】
これにより、第一実施例で説明した二分探索器のデータ探索回路５のメモリ１の設定が完全に行われるまでの間、被探索値の入力を遅延させることができるため、誤探索の可能性を低減させることができる。
【００３６】
（第五実施例）
第五実施例を図７を参照して説明する。第五実施例では、プログラマブルスイッチ要素６−１、６−２によりメモリ１の比較対象値が次段の部分木に相応する値に設定されるまでＭ段目のデータ探索回路５−Ｍから出力された被探索値のＭ＋１段目のデータ探索回路５−（Ｍ＋１）への入力を遅延させる遅延素子１０−１、１０−２を備える。
【００３７】
これにより、第二または第三実施例で説明した二分探索器のデータ探索回路５−（Ｍ＋１）のメモリ１の設定が完全に行われるまでの間、データ探索回路５−Ｍから出力された被探索値の入力を遅延させることができるため、誤探索の可能性を低減させることができる。
【００３８】
【発明の効果】
以上説明したように、本発明によれば、ハードウェアに実装することができ、処理速度を高速化することができる二分探索器を実現することができる。
【図面の簡単な説明】
【図１】第一実施例の二分探索器の構成図。
【図２】本実施例の部分木構成を示す図。
【図３】第二実施例の二分探索器の構成図。
【図４】第二実施例の二分探索器の動作を説明するための図。
【図５】第三実施例の二分探索器の構成図。
【図６】第四実施例の二分探索器の構成図。
【図７】第五実施例の二分探索器の構成図。
【図８】二分探索木の例を示す図。
【符号の説明】
１、７  メモリ
２  比較器
３、８  セレクタ
４  スイッチ回路
５、５−１〜５−３  データ探索回路
６、６−１、６−２  プログラマブルスイッチ要素
９  記憶要素
１０、１０−１、１０−２  遅延素子
【図１】
0003686379.tif 000002
【図２】
0003686379.tif 000003
【図３】
0003686379.tif 000004
【図４】
0003686379.tif 000005
【図５】
0003686379.tif 000006
【図６】
0003686379.tif 000007
【図７】
0003686379.tif 000008
【図８】
0003686379.tif 000009