(57)【特許請求の範囲】
【請求項１】
２分探索木を用いた情報検索方法において、
各ノードに対応するデータの記憶領域を、キーを示すデータを格納する第１の記憶領域と、１つの他のノードへのリンクポインタを格納する第２の記憶領域と、第２の記憶領域に格納したリンクポインタのリンク方向を示すデータを格納する第３の記憶領域と、第１の記憶領域に格納したデータの中の検査対象となるデータの位置を示すデータを格納する第４の記憶領域とから構成し、
前記各ノードに対応するデータのうち、共通のノードを上位のノードとする１対の下位ノードに対応する１組のデータを連続した記憶領域に格納し、
各ノードについて検索処理を行う際に、
第３の記憶領域に格納されている値が第１の所定の値である場合、第２の記憶領域に格納されているリンクポインタが示すノードが検索対象となるノードであると判定し、
第３の記憶領域に格納されている値が第１の所定の値と異なる第２の所定の値である場合、第１の記憶領域中のデータの第４の記憶領域中のデータで指定される位置のデータと、第２の記憶領域に格納されているリンクポインタとに基づいて次に処理を行う下位ノードへのリンクポインタを決定する
ことを特徴とする情報検索方法。
【請求項２】
各ノードについて検索処理を行う際に、前記第３の記憶領域に格納されている値が前記第１の所定の値である場合で、前記第２の記憶領域にリンクポインタが格納されていないときは、検索失敗であると判定することを特徴とする請求項１記載の情報検索方法。
【請求項３】
次に処理を行う下位ノードへのリンクポインタを決定する際に、前記第１の記憶領域中のデータの前記第４の記憶領域中のデータで指定される位置のデータが第３の所定の値である場合に第２の記憶領域に格納されているリンクポインタを下位ノードへのリンクポインタとし、前記第１の記憶領域中のデータの前記第４の記憶領域中のデータで指定される位置のデータが第３の所定の値と異なる第４の所定の値である場合に第２の記憶領域に格納されているリンクポインタに予め決められた第５の所定の値を加えた値を下位ノードへのリンクポインタとする
ことを特徴とする請求項１又は２記載の情報検索方法。
【請求項４】
前記各ノードに対応するデータの記憶領域が、さらに各ノード固有情報へのポインタを格納する第５の記憶領域を有し、
前記第３の記憶領域に格納されている値が前記第１の所定の値であって、かつ前記第１の記憶領域にキーを示すデータを格納するノードに対応する第５の記憶領域にノード固有情報へのポインタが格納されていることを特徴とする請求項１〜３のいずれか１項に記載の情報検索方法。
【請求項５】
さらに、前記第３の記憶領域に格納されている値が前記第２の所定の値であって、かつ前記第２の記憶領域に、前記第１の記憶領域にキーを示すデータを格納されているノードに対応するリンクポインタが格納されているノードに対応する前記第５の記憶領域に、リンク先ノードと同一のノード固有情報へのポインタが格納されていることを特徴とする請求項４記載の情報検索方法。
【請求項６】
２分探索木を用いた情報検索装置において、
キーを示すデータを格納する第１の記憶領域と、１つの他のノードへのリンクポインタを格納する第２の記憶領域と、第２の記憶領域に格納したリンクポインタのリンク方向を示すデータを格納する第３の記憶領域と、第１の記憶領域に格納したデータの中の検査対象となるデータの位置を示すデータを格納する第４の記憶領域とから構成された各ノードに対応するデータの記憶領域を有するものであって、かつ  前記各ノードに対応するデータのうち、共通のノードを上位のノードとする１対の下位ノードに対応する１組のデータを連続した記憶領域に格納する記憶手段と、
各ノードについて検索処理を行う際に、
第３の記憶領域に格納されている値が第１の所定の値である場合、第２の記憶領域に格納されているリンクポインタが示すノードが検索対象となるノードであると判定する手段と、
第３の記憶領域に格納されている値が第１の所定の値と異なる第２の所定の値である場合、第１の記憶領域中のデータの第４の記憶領域中のデータで指定される位置のデータと、第２の記憶領域に格納されているリンクポインタとに基づいて次に処理を行う下位ノードへのリンクポインタを決定する手段と
を備えることを特徴とする情報検索装置。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、２分探索木の１種であるパトリシアツリーを用いた情報検索に用いて好適な情報検索方法及び装置に関する。
【０００２】
【従来の技術】
情報検索システムは、所定の形式で蓄積した大量の情報の中から、目的とする情報を探し出すためのシステムである。情報検索システムで用いられる検索方式の１つにパトリシアツリー方式と呼ばれるものがある。パトリシア（Ｐａｔｒｉｃｉａ，“Ｐｒａｃｔｉｃａｌ  Ａｌｇｏｒｉｔｈｍ  Ｔｏ  Ｒｅｔｒｉｅｖｅ  Ｉｎｆｏｒｍａｔｉｏｎ  Ｃｏｄｅ  Ｉｎ  Ａｌｐｈａｎｕｍｅｒｉｃ”）ツリーは良く知られた２分探索木の１種であり、パトリシアツリー方式の情報検索システムでは、あらかじめパトリシアツリーによって各情報のインデックスを作成しておき、このインデックスを検索することによって該当する情報が抽出される。例えば、パトリシアツリー方式の全文検索システムでは、各文書内の全ての位置の文字を始点とする半無限部分文字列が文字コード順に並べ替えられてインデックスが作成され、検索キーの文字列がどの半無限部分文字列と一致するかを判定することで検索が行われる。この際、実際の検索処理では文字列はビット列として扱われる。
【０００３】
図７を参照してパトリシアツリー方式による情報検索方法の一例を説明する。図７はパトリシアツリーの一例を示す図であり、この場合、パトリシアツリーはルートＮ０およびノードＮ１〜Ｎ７と、各ノードにおいて比較されるビット位置の値“０”と“１”に対応する各１対のリンク（あるいはエッジ）Ｌ１，Ｌ２，Ｌ３，Ｌ４，…，Ｌ１６を有して形成されている。この場合、各ノードＮ１，Ｎ２，Ｎ３，…，Ｎ７には、各４ビットのデータ“００００”，“００１０”，“０１００”，…，“０１１１”が検索キーとして登録されている。例えば、検索対象のデータが“００１０”である場合、ルートＮ０では次のノードとして検索対象データ“００１０”の最も左側のビット値“０”に対応するリンクＬ１でつながれているノードＮ１が選択される。ノードＮ１では、データ“００１０”の左から２番目のビット値“０”に対応するリンクＬ２でつながれているノードＮ２が選択される。ノードＮ２では、左から３番目のビット値“１”に対応するリンクＬ６でつながれているノードＮ５が選択される。そして、ノードＮ５では、左から４番目のビット値“０”に対応するリンクＬ１１でつながれているノードＮ２が再び選択されて、ノードＮ２に対応する値が探索結果として抽出される。図７に示すように、パトリシアツリー方式では、各ノードに検索キーを置くことで、検索中の検索キー全体の比較を、実質１回におさめることができるようになっている。
【０００４】
【発明が解決しようとする課題】
しかしながら、上述したような従来技術には次のような問題点があった。第１の問題点は、各ノードに下位ノードへのリンクポインタを必ず２つ持つということである。その理由は、２分木を形成するため検索キーのある部分のビット値“０”、“１”それぞれに対応するノードをリンクする必要があるためである。第２の問題点は、検索終了を判定するために同時に複数のノードの情報を参照する必要があるということである。その理由は、パトリシアでは当該ノードから次のノードへのリンクが上向きになった場合に検索成功となるが、リンク先の次ノードの検索キーの検査位置と当該ノードの検索キーの検査位置を比較するため、当該ノードの情報を保存しておく必要があるためである。これらの問題点はパトリシアツリーを構成する際のメモリ使用量の増大、および複数のノードの情報へアクセスするための処理手順の増加という影響を及ぼす。
【０００５】
本発明は、上記の問題点を考慮してなされたものであって、従来に比べ、処理手順を減少させてノード検索の高速化を図るとともに、メモリ使用量を低減することができる情報検索方法及び装置を提供することを目的とする。
【０００６】
【課題を解決するための手段】
上記課題を解決するため、請求項１記載の発明は、２分探索木を用いた情報検索方法において、各ノードに対応するデータの記憶領域を、キーを示すデータを格納する第１の記憶領域と、１つの他のノードへのリンクポインタを格納する第２の記憶領域と、第２の記憶領域に格納したリンクポインタのリンク方向を示すデータを格納する第３の記憶領域と、第１の記憶領域に格納したデータの中の検査対象となるデータの位置を示すデータを格納する第４の記憶領域とから構成し、前記各ノードに対応するデータのうち、共通のノードを上位のノードとする１対の下位ノードに対応する１組のデータを連続した記憶領域に格納し、各ノードについて検索処理を行う際に、第３の記憶領域に格納されている値が第１の所定の値である場合、第２の記憶領域に格納されているリンクポインタが示すノードが検索対象となるノードであると判定し、第３の記憶領域に格納されている値が第１の所定の値と異なる第２の所定の値である場合、第１の記憶領域中のデータの第４の記憶領域中のデータで指定される位置のデータと、第２の記憶領域に格納されているリンクポインタとに基づいて次に処理を行う下位ノードへのリンクポインタを決定することを特徴とする。請求項２記載の発明は、各ノードについて検索処理を行う際に、前記第３の記憶領域に格納されている値が前記第１の所定の値である場合で、前記第２の記憶領域にリンクポインタが格納されていないときは、検索失敗であると判定することを特徴とする。
【０００７】
請求項３記載の発明は、次に処理を行う下位ノードへのリンクポインタを決定する際に、前記第１の記憶領域中のデータの前記第４の記憶領域中のデータで指定される位置のデータが第３の所定の値である場合に第２の記憶領域に格納されているリンクポインタを下位ノードへのリンクポインタとし、前記第１の記憶領域中のデータの前記第４の記憶領域中のデータで指定される位置のデータが第３の所定の値と異なる第４の所定の値である場合に第２の記憶領域に格納されているリンクポインタに予め決められた第５の所定の値を加えた値を下位ノードへのリンクポインタとすることを特徴とする。請求項４記載の発明は、前記各ノードに対応するデータの記憶領域が、さらに各ノード固有情報へのポインタを格納する第５の記憶領域を有し、前記第３の記憶領域に格納されている値が前記第１の所定の値であって、かつ前記第１の記憶領域にキーを示すデータを格納するノードに対応する第５の記憶領域にノード固有情報へのポインタが格納されていることを特徴とする。請求項５記載の発明は、さらに、前記第３の記憶領域に格納されている値が前記第２の所定の値であって、かつ前記第２の記憶領域に、前記第１の記憶領域にキーを示すデータを格納されているノードに対応するリンクポインタが格納されているノードに対応する前記第５の記憶領域に、リンク先ノードと同一のノード固有情報へのポインタが格納されていることを特徴とする。
【０００８】
請求項６記載の発明は、２分探索木を用いた情報検索装置において、キーを示すデータを格納する第１の記憶領域と、１つの他のノードへのリンクポインタを格納する第２の記憶領域と、第２の記憶領域に格納したリンクポインタのリンク方向を示すデータを格納する第３の記憶領域と、第１の記憶領域に格納したデータの中の検査対象となるデータの位置を示すデータを格納する第４の記憶領域とから構成された各ノードに対応するデータの記憶領域を有するものであって、かつ  前記各ノードに対応するデータのうち、共通のノードを上位のノードとする１対の下位ノードに対応する１組のデータを連続した記憶領域に格納する記憶手段と、各ノードについて検索処理を行う際に、第３の記憶領域に格納されている値が第１の所定の値である場合、第２の記憶領域に格納されているリンクポインタが示すノードが検索対象となるノードであると判定する手段と、第３の記憶領域に格納されている値が第１の所定の値と異なる第２の所定の値である場合、第１の記憶領域中のデータの第４の記憶領域中のデータで指定される位置のデータと、第２の記憶領域に格納されているリンクポインタとに基づいて次に処理を行う下位ノードへのリンクポインタを決定する手段とを備えることを特徴とする。
【０００９】
【発明の実施の形態】
以下、図面を参照して本発明の実施の形態について説明する。図１は、本実施の形態におけるパトリシアツリーのノードの構造を示す説明図である。図１を参照すると、本発明ではパトリシアツリーのノード２ａは検索キー２ａ１、リンクポインタ２ａ２、リンク方向ビット２ａ３、キー検査位置２ａ４、ノード（エントリ）固有情報へのポインタ２ａ５を含んでいる。また、他の各ノード２ｂ１，２ｂ２も、同様に、検索キー２ｂ１１，２ｂ２１、リンクポインタ２ｂ１２，２ｂ２２、リンク方向ビット２ｂ１３，２ｂ２３、キー検査位置２ｂ１４，２ｂ２４、ノード固有情報へのポインタ２ｂ１５，２ｂ２５をそれぞれ含んでいる。パトリシアツリーはまた、定数としてノード長２９を所定の記憶領域に保持する。
【００１０】
検索キー２ａ１，２ｂ１１，２ｂ２１はそれぞれパトリシアツリーを構成する検索キーとして使用される。リンクポインタ２ａ２，２ｂ１２，２ｂ２２はそれぞれ上位ノードまたは下位ノードへのポインタを格納する。リンク方向ビット２ａ３，２ｂ１３，２ｂ２３はそれぞれリンクポインタ２ａ２，２ｂ１２，２ｂ２２に格納されたポインタの性質を規定し、リンク方向ビット２ａ３，２ｂ１３，２ｂ２３が“０”の場合はリンクポインタ２ａ２，２ｂ１２，２ｂ２２がＮＵＬＬまたは上位ノードの先頭ポインタを格納し、リンク方向ビット２ａ３，２ｂ１３，２ｂ２３が“１”の場合はリンクポインタ２ａ２，２ｂ１２，２ｂ２２が左下位ノードの先頭ポインタを格納する。図１に示す例では、ノード２ａは、検索キー２ａ１としてパトリシアツリーを構成する検索キーを保持し、リンクポインタ２ａ２として左下位ノード２ｂ１へのポインタを格納している。この場合リンク方向ビット２ａ３には“１”が格納されている。
【００１１】
キー検査位置２ａ４，２ｂ１４，２ｂ２４はそれぞれパトリシアツリーの各ノードにおける検索対象２８の中の左側を起点とした検査位置（ビット位置）を格納する。ノード固有情報へのポインタ２ａ５，２ｂ１，２ｂ２はそれぞれ検索成功で終了した後の処理で使用する管理情報へのポインタを格納する。ノード固有情報へのポインタ２ａ５，２ｂ１，２ｂ２が検索処理の途中で参照されることはない。本実施の形態では、ｒｏｏｔ（ルート）ノードを除き各ノードは図１の左下位ノード２ｂ１と右下位ノード２ｂ２のように常に２つのノードが記憶領域中で連続した領域を占めるように配置される。したがって、左下位ノード２ｂ１へのポインタを格納しているリンクポインタ２ａ２に、ノード長２９を加えることで、右下位ノード２ｂ２のポインタの値を得ることができる。検索対象２８は検索キー２ａ１，２ｂ１１，２ｂ２１と同一の大きさで検索の対象となる値を格納する。ここでは、各データがビット列として扱われている。ノード長２９はノード２ａ，２ｂ１，２ｂ２の長さ（データ長）を格納する。ただし、２つのノードの配置の仕方は上記のものに限定されず、例えば、右下位ノードと左下位ノードの位置を入れ替えたり、リンクポインタの値を右下位ノードに対応するものとしてそこからノード長を減じることで左下位ノードに対応する値を得るようにしてもよい。
【００１２】
次に図２に示すノード２ａに関する検索動作について図４に示すフローチャートを参照して説明する。本実施の形態における検索処理は、所定の記憶装置を備えたＣＰＵ（中央処理装置）によって実行される。検索対象、各ノード、およびノード長のデータは、検索処理の際、その記憶装置内に格納される。また、ＣＰＵによって実行されるプログラムは、コンピュータ読み取り可能な記録媒体あるいは通信回線を介して頒布することが可能である。図２の構成において、検索対象２８とノード２ａについての検索動作は、まずノード２ａのリンク方向ビット２ａ３を調べることから開始される（図４のステップＳ１）。リンク方向ビット２ａ３が“０”の場合は次にリンクポインタ２ａ２を調べる（ステップＳ６）。リンク方向ビット２ａ３が“０”の場合でリンクポインタ２ａ２がＮＵＬＬのときは該当するノードが存在しないことになるので検索失敗となり検索動作を終了する。リンク方向ビット２ａ３が“０”の場合でリンクポインタ２ａ２がＮＵＬＬ以外のときはそのポインタの指すノードが検索対象２８と一致する検索キーを持つノードなので、リンクポインタ２ａ２の指すノード（この場合図示していない上位のノード）の内容を読み込んで（ステップＳ７）、ノード固有情報へのポインタの指すノード固有情報を得て（ステップＳ８）検索成功となり検索動作を終了する。
【００１３】
一方、図４において、ステップＳ１でリンク方向ビット２ａ３が“１”の場合は検索続行となる。検索対象２８の左側を起点としたキー検査位置２ａ４の示す位置の値を調べる（ステップＳ２，Ｓ３）。検査対象２８の中のキー検査位置２ａ４の示す位置の値が“１”ならば、パトリシアツリーの右下位ノードをたどる事を意味するので、リンクポインタ２ａ２にノード長２９を加えた値をポインタとして、そのポインタの指す内容を右下位ノードの内容として新しく読み込む（ステップＳ４）。検索対象２８のキー検査位置２ａ４の示す位置の値が“０”ならばパトリシアツリーの左下位ノードをたどる事を意味するので、リンクポインタ２ａ２の指す内容を左下位ノードの内容として読み込む（ステップＳ５）。ステップＳ１からステップＳ５までの検索動作をリンク方向ビット２ａ３，２ｂ１３，２ｂ２３，…が“０”になるまで繰り返す。
【００１４】
次に、図２と図３に示すパトリシアツリー表現、及び図４のフローチャートを参照して本実施の形態の動作について具体例を示して詳細に説明する。この例では、パトリシアツリーのうち、３つの下位ノードが図２、図３のように構成されているものとする。図２は各ノードの持つ値と相互の位置関係、図３はそのパトリシアツリー表現である。また図１の検索対象２８に対応する検査対象３０のキーには“００１１０”が、図１のノード長２９に対応するノード長３１には各ノードのノード長が設定されている。図２に示すノード３ａ１およびノード３ａ２は図示していない上位のノードからリンクされた左下位および右下位のノードである。ただしノード３ａ２は図３では図示を省略している。
【００１５】
図２において、ノード３ａ１では、検索キー３ａ１１にデータ“００１００”が、リンクポインタ３ａ１２にノード３ｂ１へのポインタ（図２および図３のリンクＬ１）が、リンク方向ビット３ａ１３に“１”が、キー検索位置３ａ１４に“３”が、そして、ノード固有情報へのポインタ３ａ１５にノード固有情報４ａへのポインタが、それぞれ格納されている。ノード３ｂ１では、リンクポインタ３ｂ１２にＮＵＬＬが、リンク方向ビット３ｂ１３に“０”がそれぞれ格納されている。ノード３ｂ２では、検索キー３ｂ２１にデータ“００１１０”が、リンクポインタ３ｂ２２にノード３ｃ１へのポインタ（リンクＬ２）が、リンク方向ビット３ｂ２３に“１”が、キー検索位置３ｂ２４に“４”が、そして、ノード固有情報へのポインタ３ｂ２５にノード固有情報４ａへのポインタが、それぞれ格納されている。
【００１６】
ノード３ｃ１では、リンクポインタ３ｃ１２にノード３ａ１へのポインタ（リンクＬ３）が、リンク方向ビット３ｃ１３に“０”が、それぞれ格納されている。ノード３ｃ２では、検索キー３ｂ２１にデータ“００１１１”が、リンクポインタ３ｃ２２にノード３ｄ１へのポインタ（リンクＬ４）が、リンク方向ビット３ｃ２３に“１”が、キー検索位置３ｃ２４に“５”が、そして、ノード固有情報へのポインタ３ｃ２５にノード固有情報４ｃへのポインタが、それぞれ格納されている。ノード３ｄ１では、リンクポインタ３ｄ１２にノード３ｂ２へのポインタ（リンクＬ６）が、リンク方向ビット３ｄ１３に“０”が、それぞれ格納されている。ノード３ｄ２では、リンクポインタ３ｄ２２にノード３ｃ２へのポインタ（リンクＬ５）が、リンク方向ビット３ｄ２３に“０”が、それぞれ格納されている。
【００１７】
次に、図４に示すフローチャートを参照して、図２および図３に示すノードに関する検索動作について説明する。今、与えられた検索対象３０“００１１０”についてノード３ａ１との比較を行うとする。この場合、まずリンク方向ビット３ａ１３を調べる（ステップＳ１）。この値は“１”なので検索続行となる。下位ノードをたどるため、次にキー検索位置３ａ１４を調べると値が“３”なので、検索対象３０の左から３番目の値を調べる（ステップＳ２、Ｓ３）。すると値は“１”なので、右下位ノード３ｂ２をたどるために、リンクポインタ３ａ１２にノード長３１の値を加えた値を次のノードへのポインタとして内容を読み込み、新しいノードとしてノード３ｂ２を得る（ステップＳ５）。
【００１８】
次にリンク方向ビット３ｂ２３を調べ（ステップＳ１）、値が“１”なので検索続行となる。キー検索位置３ｂ２４の値が“４”なので、検索対象３０の左から４番目の値を調べる（ステップＳ２、Ｓ３）。すると値は“１”なので、右下位ノード３ｃ２をたどるためにリンクポインタ３ｂ２２にノード長３１の値を加えた値を次のノードへのポインタとして内容を読み込み、新しいノードとしてノード３ｃ２を得る（ステップＳ５）。
【００１９】
以下同様に検索対象３０とキー検査位置３ｃ２４から左下位ノード３ｄ１を得るが、このノードのリンク方向ビット３ｄ１３を調べると（ステップＳ１）値が“０”なので次にリンクポインタ３ｄ１２を調べる（ステップＳ６）。すると値はＮＵＬＬではないのでリンクポインタ３ｄ１２の指すノード３ｂ２が検索対象ノードとなり、ノード３ｂ２の内容を読み込む（ステップＳ７）。最後にノード固有情報へのポインタ３ｂ２５の指すノード固有情報を得て（ステップＳ８）検索を終了する。
【００２０】
次に、本発明の他の実施の形態について図５および図６を参照して詳細に説明する。図５を参照すると、本実施の形態は、上記実施の形態と比較して、リンク方向ビットが“１”であって、検索キーを持っているノード３ａ１、３ｂ２、３ｃ２がそれぞれノード固有情報４ａ，４ｂ，４ｃへのポインタ３ａ１５、３ｂ２５、３ｃ２５を持つとともに、他のノードへのリンクポインタ３ａ１２，３ｂ２２，３ｃ２２を持つ点では一致しているものの、リンク方向ビットが“０”であって、検索キーを持っているノード３ａ１、３ｂ２、３ｃ２をリンク先とするノード３ｃ１，３ｄ１，３ｄ２もそれぞれリンク先のノード３ａ１、３ｂ２、３ｃ２と同じノード固有情報４ａ，４ｂ，４ｃを指すポインタ３ｃ１５，３ｄ１５，３ｄ２５を有する点で異なっている。
【００２１】
図５と図６のフローチャートを参照して本実施の形態の全体の動作について詳細に説明する。図６のステップＳ１〜Ｓ５で示される本実施の形態における動作は、図２〜図４で示された上記の実施の形態のステップＳ１〜Ｓ５と同一のため、説明は省略する。図６に示すフローチャートは、図５に示すフローチャートのステップＳ７の処理を省略したものである。図２に示された実施の形態では、リンク方向ビットが“０”でかつリンクポインタがＮＵＬＬでない場合はさらにリンクポインタの指す検索対象ノードを読み込んだ後にノード固有情報を得ていた。本実施の形態ではリンク方向ビットが“０”でかつリンクポインタがＮＵＬＬでないノードにもノード固有情報へのポインタを設定する。
【００２２】
次に、具体例を用いて説明する。図５に示すフローにおいて図２と同様に検索対象３０のキー“００１１０”について検索処理を行っていくと、ノード３ｄ１を得たところでリンク方向ビット３ｄ１３が“０”となるなので、リンクポインタ３ｄ１２を調べる（図６のステップＳ１、Ｓ６）。するとリンクポインタ３ｄ１２の値はＮＵＬＬでないのでノード３ｄ１は検索対象ノードを指すリンクポインタを持つことになる。そこで、検索対象ノードと同じ値をもつノード固有情報へのポインタ３ｄ１５の指すノード固有情報４ｂを読み込んで（ステップＳ７）検索成功となる。
【００２３】
本実施の形態は、リンク方向ビットが“０”でかつリンクポインタがＮＵＬＬでないノードが、リンクポインタが示すノードと同一のノード固有情報へのポインタを持つよう構成する必要があるが、検索成功時のノード読み込み処理を１ステップ減らせるため、より高速に検索処理が行えるという新たな効果を有する。
【００２４】
以上説明したように、本発明によれば、２分探索木の１種であるパトリシアツリーにおいて従来に比べノード検索を高速に行える構成を提供できる。本発明についてその特徴をまとめると以下のようになる。図１において、本発明ではパトリシアツリーを構成するノード２ａについて、通常の２分木では２つ必要となる下位ノードへのリンクポインタを１つだけリンクポインタ２ａ２として持たせる。リンクポインタ２ａ２は左方向の下位ノードのポインタであり、かつノード長２８を加えて右方向の下位ノードのポインタとしても解釈される。リンク先の選択は、検索キー２ａ１の中の、左を起点としたキー検査位置２ａ４の示す値によって区別される。
【００２５】
検索処理においては、まずリンクポインタ２ａ２を調べ、ＮＵＬＬならば検索失敗となり処理を終了する。ＮＵＬＬ以外ならば次にリンク方向ビット２ａ３を調べ、“０”ならばそのポインタの示すノードが検索対象となるノードであり検索成功となる。“１”ならば検索を続行し、検索対象２８の中のキー検査位置２ａ４の示す位置の値とリンクポインタ２ａ３の組み合わせにより次の下位ノードへのポインタを決定する。このように当該ノード以外の記憶領域の参照、およびノードの内容の退避処理などを行うことなく当該ノード上の情報だけでパトリシアツリー検索の続行／成功／失敗を判定することができるため、メモリ読み込み時間の短縮および複数記憶領域の使用に伴う処理手順の削減によりノード検索を高速に行うことを可能にする。
【００２６】
【発明の効果】
本発明による第１の効果は、パトリシアツリーにおいてノード検索が高速に行えることにある。その理由は、各ノードでリンク方向ビットを持つことにより該ノード上の情報のみで検索続行／成功／失敗が判定できるためである。第２の効果は、パトリシアツリーを構成する際のメモリ使用量が低減できることにある。その理由は、左右下位ノードが常に連続した記憶領域を占めるよう構成されるため、ノード長情報を独立して保持しておくことにより各ノードに左右下位ノードへのポインタを１つだけ持てばよいためである。
【図面の簡単な説明】
【図１】本発明の情報検索方法におけるパトリシアツリーのノードの構造例を示す説明図。
【図２】本発明の一実施の形態による各ノードの持つ値と相互の位置関係を示す説明図。
【図３】図２に示す各ノードをパトリシアツリー表現で示す説明図。
【図４】本発明の一実施の形態における情報検索の動作を示すフローチャート。
【図５】図２に示す各ノードの構成の変形例を示す説明図。
【図６】図６に示すノードの構成を用いた情報検索の動作を示すフローチャート。
【図７】従来の情報検索方法におけるパトリシアツリーのノードの構造例を示す説明図。
【符号の説明】
２ａ，２ｂ１，２ｂ２，３ａ１，３ａ２，３ｂ１，３ｂ２，３ｃ１，３ｃ２，３ｄ１，３ｄ２…ノード
２ａ１，２ｂ１１，２ｂ２１，３ａ１１，３ｂ２１，３ｃ２１…検索キー
２ａ２，２ｂ１２，２ｂ２２，３ａ１２，３ｂ２２，３ｃ１２，３ｃ２２，３ｄ１２，３ｄ２２…リンクポインタ
２ａ３，２ｂ１３，２ｂ２３，３ａ１３，３ｂ１３，３ｂ２３，３ｃ１３，３ｃ２３，３ｄ１３，３ｄ２３…リンク方向ビット
２ａ４，２ｂ１４，２ｂ２４，３ａ１４，３ｂ２４，３ｃ２４…キー検査位置
２ａ５，２ｂ１５，２ｂ２５，３ａ１５，３ｂ２５，３ｃ２５…ノード固有情報へのポインタ
２８，３０…検索対象
２９，３１…ノード長
【図１】
0003601416.tif 000002
【図２】
0003601416.tif 000003
【図３】
0003601416.tif 000004
【図４】
0003601416.tif 000005
【図５】
0003601416.tif 000006
【図６】
0003601416.tif 000007
【図７】
0003601416.tif 000008