(57)【要約】【課題】辞書を検索する際に要する検索時間を短縮する。【解決手段】登録文字列の区分数に対応して設けられた複数のハッシュテーブル１１Ｂと１または複数の平衡２分探索木テーブル１１Ｃとを辞書１１に設け、辞書検索時には、検索処理部１３が、検索文字列の区分数に対応するハッシュテーブル１１Ｂを選択して、検索文字列の検索ハッシュ値に基づき当該ハッシュテーブル１１Ｂを検索し、検索文字列の検索ハッシュ値に対応する平衡２分探索木が構築されている場合には、辞書探索処理部１４が、平衡２分探索木テーブル１１Ｃのうち対応する平衡２分探索木から検索文字列を探索する。【選択図】  図１
2018081611.tif 000002
【特許請求の範囲】
【請求項１】
入力された検索指示に応じて、辞書に登録されている登録文字列を、これら登録文字列のハッシュ値に基づいて検索する辞書検索方法であって、
前記辞書は、複数のハッシュテーブルと１または複数の平衡２分探索木テーブルとを有し、
前記ハッシュテーブルのそれぞれは、登録文字列を１または複数の文字列で複数に区分して得られた区分数に対応して設けられて、これら登録文字列のハッシュ値ごとに、前記登録文字列のうち当該ハッシュ値を有する唯一の登録文字列と、前記登録文字列のうち当該ハッシュ値を共有する複数の衝突登録文字列をノードとする平衡２分探索木のうちルートノードを参照するための参照先ポインタ値との、いずれか一方が登録されており、
前記平衡２分探索木テーブルは、前記衝突登録文字列と当該衝突登録文字列を識別するためのインデックス値とが、当該衝突登録文字列のハッシュ値に関する平衡２分探索木のノードとして、規定の文字整列順序に基づいて登録されており、
辞書検索の際、前記ハッシュテーブルのうちから前記検索指示で指定された検索文字列の区分数に応じたハッシュテーブルを選択して前記検索文字列のハッシュ値に基づいて検索し、当該ハッシュ値に対応する登録文字列が登録されている場合には、当該検索文字列の登録ありと判定して当該検索文字列と対応する出力値を出力する検索処理ステップと、
前記検索文字列のハッシュ値に対応する登録文字列が前記ハッシュテーブルに登録されていない場合には、当該ハッシュ値の参照先ポインタ値に基づいて前記平衡２分探索木テーブルを参照し、当該参照先ポインタ値が示す前記インデックス値と対応する前記衝突登録文字列をルートノードとする前記平衡２分探索木のノードから、前記検索文字列と一致する衝突登録文字列を探索し、得られた探索結果に応じて当該検索文字列の登録あり／なしを判定し、当該検索文字列の登録ありの場合には当該検索文字列と対応する出力値を出力し、当該参照先ポインタ値が登録されていない場合には、当該検索文字列の登録なしと判定する探索処理ステップと
を備えることを特徴とする辞書検索方法。
【請求項２】
請求項１に記載の辞書検索方法において、
前記辞書が有する前記ハッシュテーブルのうちから、入力された登録指示で指定された指定文字列の区分数に応じたハッシュテーブルを選択して、前記指定文字列のハッシュ値に基づいて前記ハッシュテーブルを参照し、当該ハッシュ値に対応する登録文字列が登録されている場合には、当該登録文字列および当該指定文字列からなる衝突登録文字列を、前記文字整列順序に従って当該ハッシュ値に関する平衡２分探索木のノードとして前記平衡２分探索木テーブルに登録し、当該平衡２分探索木のルートノードとなった衝突登録文字列のインデックス値を当該ハッシュ値の参照先ポインタ値として前記ハッシュテーブルに登録するとともに、当該ハッシュ値の登録文字列を前記ハッシュテーブルから削除する登録処理ステップをさらに備え、
前記登録処理ステップは、前記指定文字列のハッシュ値に対応する登録文字列が前記ハッシュテーブルに登録されておらず、当該ハッシュ値の参照先ポインタ値が登録されている場合には、当該指定文字列からなる衝突登録文字列を、前記文字整列順序に従って当該ハッシュ値に関する平衡２分探索木の新たなノードとして前記平衡２分探索木テーブルに追加登録するとともに、当該ハッシュ値に関する平衡２分探索木のルートノードとなった衝突登録文字列のインデックス値を当該ハッシュ値の参照先ポインタ値として前記ハッシュテーブルに登録し、当該ハッシュ値の登録文字列および参照先ポインタ値が登録されていない場合には、当該指定文字列を当該ハッシュ値の登録文字列として前記ハッシュテーブルに登録する
ことを特徴とする辞書検索方法。
【請求項３】
請求項１または請求項２に記載の辞書検索方法において、
前記検索処理ステップは、前記検索文字列のハッシュ値を計算する際、予め設定されている複数のハッシュ関数のうちから、当該検索文字列の区分数に基づき当該検索文字列に対応するハッシュ関数を選択し、当該ハッシュ関数に基づき当該検索文字列のハッシュ値を計算することを特徴とする辞書検索方法。
【請求項４】
請求項２に記載の辞書検索方法において、
前記登録処理ステップは、前記指定文字列のハッシュ値を計算する際、予め設定されている複数のハッシュ関数のうちから、当該指定文字列の区分数に基づき当該指定文字列に対応するハッシュ関数を選択し、当該ハッシュ関数に基づき当該指定文字列のハッシュ値を計算することを特徴とする辞書検索方法。
【請求項５】
入力された検索指示に応じて、辞書に登録されている登録文字列を、これら登録文字列のハッシュ値に基づいて検索する辞書検索装置であって、
前記辞書は、複数のハッシュテーブルと１または複数の平衡２分探索木テーブルとを有し、
前記ハッシュテーブルのそれぞれは、登録文字列を１または複数の文字列で複数に区分して得られた区分数に対応して設けられて、これら登録文字列のハッシュ値ごとに、前記登録文字列のうち当該ハッシュ値を有する唯一の登録文字列と、前記登録文字列のうち当該ハッシュ値を共有する複数の衝突登録文字列をノードとする平衡２分探索木のうちルートノードを参照するための参照先ポインタ値との、いずれか一方が登録されており、
前記平衡２分探索木テーブルは、前記衝突登録文字列と当該衝突登録文字列を識別するためのインデックス値とが、当該衝突登録文字列のハッシュ値に関する平衡２分探索木のノードとして、規定の文字整列順序に基づいて登録されており、
辞書検索の際、前記ハッシュテーブルのうちから前記検索指示で指定された検索文字列の区分数に応じたハッシュテーブルを選択して前記検索文字列のハッシュ値に基づいて検索し、当該ハッシュ値に対応する登録文字列が登録されている場合には、当該検索文字列の登録ありと判定して当該検索文字列と対応する出力値を出力する検索処理部と、
前記検索文字列のハッシュ値に対応する登録文字列が前記ハッシュテーブルに登録されていない場合には、当該ハッシュ値の参照先ポインタ値に基づいて前記平衡２分探索木テーブルを参照し、当該参照先ポインタ値が示す前記インデックス値と対応する前記衝突登録文字列をルートノードとする前記平衡２分探索木のノードから、前記検索文字列と一致する衝突登録文字列を探索し、得られた探索結果に応じて当該検索文字列の登録あり／なしを判定し、当該検索文字列の登録ありの場合には当該検索文字列と対応する出力値を出力し、当該参照先ポインタ値が登録されていない場合には、当該検索文字列の登録なしと判定する探索処理部と
を備えることを特徴とする辞書検索装置。
【請求項６】
コンピュータを、請求項１〜請求項４のいずれかに記載の辞書検索方法を構成する各ステップとして機能させるためのプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、ルータにおいてルーティングを行う際に用いる辞書を検索するための辞書検索技術に関する。
【背景技術】
【０００２】
従来のクラウドサービスは、通信ネットワーク上に存在するコンピュータ（サーバ）とユーザ端末との間でデータ通信を行う形式が一般的であるが、複数のユーザが同時に同じサービスを要求した場合、一部のコンピュータに負荷が集中するという問題がある。この問題を解決する次世代ネットワークとしてＣＣＮ（Content Centric Networking）が提案されている（非特許文献１）。このＣＣＮでは、ネットワーク上に配置されたルータがコンテンツを保持することでキャッシュ機能を果たすため、分散処理によるサーバ負荷の低減と応答時間の削減が可能となる。
【０００３】
ＣＣＮにおけるルータ（ＣＣＮルータ）は、Ｄａｔａパケットを媒体として通信されるコンテンツを格納するＣＳ（Content Store）と、コンテンツ名に基づくＩｎｔｅｒｅｓｔパケットの転送に用いられるＦＩＢ（Forwarding Information Base）と、Ｉｎｔｅｒｅｓｔパケットに呼応するＤａｔａパケットの送信に用いられるＰＩＴ（Pending Interest Table）から構成される。中でもＦＩＢは大規模なテーブルであることが多く、ＣＣＮルータの処理を高速化するためにはＦＩＢに対する検索を効率化することが有効である。
【先行技術文献】
【非特許文献】
【０００４】
【非特許文献１】V. Jacobson, D. Smetters, J. Thornton, and M. Plass，"Net-working named content"，in Proc. of ACM CoNEXT’09，2009，pp. 1-12
【非特許文献２】島崎健太 et al.，"CCNルータのためのハッシュテーブルと平衡木の併用によるメモリアクセスを削減したFIBの構築"，信学技報 115(338)，243-248，2015-12-01
【発明の概要】
【発明が解決しようとする課題】
【０００５】
従来のＦＩＢに関するテーブル検索技術として、多分木を利用した手法、ハッシュテーブルを利用した手法などが報告されている（非特許文献２）。しかし、多分木はコンテンツ名が長くなるほど節点が多くなり（＝メモリアクセス回数が増加する）、検索時間が長くなる。一方、ハッシュテーブルはハッシュ値の衝突が起こらない場合は１回のメモリアクセスで検索を行うことができるが、ハッシュ値が衝突した際にどのようにコンテンツをメモリに格納するかが問題となる。
【０００６】
すなわち、多分木を用いたＦＩＢでは、コンテンツ名が長くなるほどメモリアクセス回数が増加し、検索時間が長くなる問題がある。そのためメモリアクセス回数を最小化する観点からハッシュテーブル用いたＦＩＢが望ましい。
ハッシュ関数では入力値が出力値（ハッシュ値）よりも長い場合、複数の異なる入力値から同じハッシュ値が得られるため、結果を一意に定めることができない。そのため、ハッシュ値が衝突した際は線形リストや平衡木を用いることで一意に定まることを保障する手法が考えられる。しかし、ハッシュ値の衝突が多く発生した場合、深いリストが生成されるため、検索時間が長くなる問題がある。
【０００７】
本発明はこのような課題を解決するためのものであり、辞書を検索する際に要する検索時間を短縮できる辞書検索技術を提供することを目的としている。
【課題を解決するための手段】
【０００８】
このような目的を達成するために、本発明にかかる辞書検索方法は、入力された検索指示に応じて、辞書に登録されている登録文字列を、これら登録文字列のハッシュ値に基づいて検索する辞書検索方法であって、前記辞書は、複数のハッシュテーブルと１または複数の平衡２分探索木テーブルとを有し、前記ハッシュテーブルのそれぞれは、登録文字列を１または複数の文字列で複数に区分して得られた区分数に対応して設けられて、これら登録文字列のハッシュ値ごとに、前記登録文字列のうち当該ハッシュ値を有する唯一の登録文字列と、前記登録文字列のうち当該ハッシュ値を共有する複数の衝突登録文字列をノードとする平衡２分探索木のうちルートノードを参照するための参照先ポインタ値との、いずれか一方が登録されており、前記平衡２分探索木テーブルは、前記衝突登録文字列と当該衝突登録文字列を識別するためのインデックス値とが、当該衝突登録文字列のハッシュ値に関する平衡２分探索木のノードとして、規定の文字整列順序に基づいて登録されており、辞書検索の際、前記ハッシュテーブルのうちから前記検索指示で指定された検索文字列の区分数に応じたハッシュテーブルを選択して前記検索文字列のハッシュ値に基づいて検索し、当該ハッシュ値に対応する登録文字列が登録されている場合には、当該検索文字列の登録ありと判定して当該検索文字列と対応する出力値を出力する検索処理ステップと、前記検索文字列のハッシュ値に対応する登録文字列が前記ハッシュテーブルに登録されていない場合には、当該ハッシュ値の参照先ポインタ値に基づいて前記平衡２分探索木テーブルを参照し、当該参照先ポインタ値が示す前記インデックス値と対応する前記衝突登録文字列をルートノードとする前記平衡２分探索木のノードから、前記検索文字列と一致する衝突登録文字列を探索し、得られた探索結果に応じて当該検索文字列の登録あり／なしを判定し、当該検索文字列の登録ありの場合には当該検索文字列と対応する出力値を出力し、当該参照先ポインタ値が登録されていない場合には、当該検索文字列の登録なしと判定する探索処理ステップとを備えている。
【０００９】
また、本発明にかかる上記辞書検索方法の一構成例は、前記辞書が有する前記ハッシュテーブルのうちから、入力された登録指示で指定された指定文字列の区分数に応じたハッシュテーブルを選択して、前記指定文字列のハッシュ値に基づいて前記ハッシュテーブルを参照し、当該ハッシュ値に対応する登録文字列が登録されている場合には、当該登録文字列および当該指定文字列からなる衝突登録文字列を、前記文字整列順序に従って当該ハッシュ値に関する平衡２分探索木のノードとして前記平衡２分探索木テーブルに登録し、当該平衡２分探索木のルートノードとなった衝突登録文字列のインデックス値を当該ハッシュ値の参照先ポインタ値として前記ハッシュテーブルに登録するとともに、当該ハッシュ値の登録文字列を前記ハッシュテーブルから削除する登録処理ステップをさらに備え、  前記登録処理ステップは、前記指定文字列のハッシュ値に対応する登録文字列が前記ハッシュテーブルに登録されておらず、当該ハッシュ値の参照先ポインタ値が登録されている場合には、当該指定文字列からなる衝突登録文字列を、前記文字整列順序に従って当該ハッシュ値に関する平衡２分探索木の新たなノードとして前記平衡２分探索木テーブルに追加登録するとともに、当該ハッシュ値に関する平衡２分探索木のルートノードとなった衝突登録文字列のインデックス値を当該ハッシュ値の参照先ポインタ値として前記ハッシュテーブルに登録し、当該ハッシュ値の登録文字列および参照先ポインタ値が登録されていない場合には、当該指定文字列を当該ハッシュ値の登録文字列として前記ハッシュテーブルに登録するようにしたものである。
【００１０】
また、本発明にかかる上記辞書検索方法の一構成例は、前記検索処理ステップが、前記検索文字列のハッシュ値を計算する際、予め設定されている複数のハッシュ関数のうちから、当該検索文字列の区分数に基づき当該検索文字列に対応するハッシュ関数を選択し、当該ハッシュ関数に基づき当該検索文字列のハッシュ値を計算するようにしたものである。
【００１１】
また、本発明にかかる上記辞書検索方法の一構成例は、前記登録処理ステップが、前記指定文字列のハッシュ値を計算する際、予め設定されている複数のハッシュ関数のうちから、当該指定文字列の区分数に基づき当該指定文字列に対応するハッシュ関数を選択し、当該ハッシュ関数に基づき当該指定文字列のハッシュ値を計算するようにしたものである。
【００１２】
また、本発明にかかる辞書検索装置は、入力された検索指示に応じて、辞書に登録されている登録文字列を、これら登録文字列のハッシュ値に基づいて検索する辞書検索装置であって、前記辞書は、複数のハッシュテーブルと１または複数の平衡２分探索木テーブルとを有し、前記ハッシュテーブルのそれぞれは、登録文字列を１または複数の文字列で複数に区分して得られた区分数に対応して設けられて、これら登録文字列のハッシュ値ごとに、前記登録文字列のうち当該ハッシュ値を有する唯一の登録文字列と、前記登録文字列のうち当該ハッシュ値を共有する複数の衝突登録文字列をノードとする平衡２分探索木のうちルートノードを参照するための参照先ポインタ値との、いずれか一方が登録されており、前記平衡２分探索木テーブルは、前記衝突登録文字列と当該衝突登録文字列を識別するためのインデックス値とが、当該衝突登録文字列のハッシュ値に関する平衡２分探索木のノードとして、規定の文字整列順序に基づいて登録されており、辞書検索の際、前記ハッシュテーブルのうちから前記検索指示で指定された検索文字列の区分数に応じたハッシュテーブルを選択して前記検索文字列のハッシュ値に基づいて検索し、当該ハッシュ値に対応する登録文字列が登録されている場合には、当該検索文字列の登録ありと判定して当該検索文字列と対応する出力値を出力する検索処理部と、前記検索文字列のハッシュ値に対応する登録文字列が前記ハッシュテーブルに登録されていない場合には、当該ハッシュ値の参照先ポインタ値に基づいて前記平衡２分探索木テーブルを参照し、当該参照先ポインタ値が示す前記インデックス値と対応する前記衝突登録文字列をルートノードとする前記平衡２分探索木のノードから、前記検索文字列と一致する衝突登録文字列を探索し、得られた探索結果に応じて当該検索文字列の登録あり／なしを判定し、当該検索文字列の登録ありの場合には当該検索文字列と対応する出力値を出力し、当該参照先ポインタ値が登録されていない場合には、当該検索文字列の登録なしと判定する探索処理部とを備えている。
【００１３】
また、本発明にかかるプログラムは、コンピュータを、前述したいずれかの辞書検索方法を構成する各ステップとして機能させるためのプログラムである。
【発明の効果】
【００１４】
本発明によれば、各平衡２分探索木には、検索文字列の区分数に対応する衝突登録文字列のみがノードとして登録されることになり、平衡２分探索木をより浅い構造とすることができる。したがって、辞書を検索する際に要する検索時間を短縮することが可能となる。
【図面の簡単な説明】
【００１５】
【図１】辞書検索装置の構成を示すブロック図である。
【図２】１つのハッシュテーブルを用いた平衡２分探索木の探索例である。
【図３】衝突登録文字列の整列順序関係を示す説明図である。
【図４】２つのハッシュテーブルを用いた平衡２分探索木の探索例である。
【図５】ハッシュテーブルの構成例である。
【図６】平衡２分探索木テーブルの構成例である。
【図７】辞書検索動作の概略を示す説明図である。
【図８】検索処理を示すフローチャートである。
【図９】探索処理を示すフローチャートである。
【図１０】登録処理を示すフローチャートである。
【発明を実施するための形態】
【００１６】
次に、本発明の一実施の形態について図面を参照して説明する。
［辞書検索装置］
まず、図１を参照して、本実施の形態にかかる辞書検索装置１０について説明する。図１は、辞書検索装置の構成を示すブロック図である。
この辞書検索装置１０は、全体としてサーバ装置などの情報処理装置からなり、外部から入力された検索指示に応じて、辞書１１に登録されている登録文字列を、これら登録文字列のハッシュ値に基づいて検索する機能を有している。
【００１７】
辞書検索装置１０には、主な機能部として、辞書１１、ハッシュ値計算部１２、検索処理部１３、探索処理部１４、および登録処理部１５が設けられている。これら機能部のうち、ハッシュ値計算部１２、検索処理部１３、探索処理部１４、および登録処理部１５については、ＣＰＵでプログラムを実行することにより実現してもよく、これらの一部をＦＰＧＡの論理回路で実現してもよい。
【００１８】
ここで、本発明の原理について説明する。文字には、コード順、アルファベット順、五十音順など、規定の文字整列順序が存在する。したがって、このような文字整列順序に基づいて、異なる２つの文字列に整列順位を与えることができる。例えば、Ｊａｖａ（登録商標）言語における「str0.compareTo(str1)」といったメソッド（関数）を用いると、この場合には変数ｓｔｒ０に格納されている文字列オブジェクトと、変数ｓｔｒ１に格納されている文字列オブジェクトとの間において、同一の場合を含めた大小関係（全順序関係）を得ることができ、これに基づき文字列の整列順位を特定することができる。
【００１９】
本発明は、このような文字列間の整列順位に着目し、ハッシュ値と対応付けて登録文字列を辞書１１に登録する際、同一ハッシュ値を有する複数の衝突登録文字列を当該ハッシュ値に対応する平衡２分探索木のノードとして登録しておき、検索時において、検索文字列の検索ハッシュ値に対応する平衡２分探索木が構築されている場合には、当該平衡２分探索木から検索文字列を探索することにより、検索処理の簡素化および所要時間の短縮を実現するようにしたものである。
【００２０】
また、検索文字列が長い場合、それよりも短い文字列を内包して共通要素が多くなるため、ハッシュ値の衝突が起こる可能性が高くなり、結果して平衡２分探索木が深い構造となる。
図２は、１つのハッシュテーブルを用いた平衡２分探索木の探索例である。ここでは、同一ハッシュ値Ｈ＝「２」（＝Ｈ［２］）を持つ４つの衝突登録文字列「com/foo/map」,「com/foo」,「com/foo/map/version2」,「com/foo/map/version1」が、アルファベット順という文字整列順序に基づいて、ノードとして登録されている。
【００２１】
図３は、衝突登録文字列の整列順序関係を示す説明図である。
各衝突登録文字列「com/foo/map」,「com/foo」,「com/foo/map/version2」,「com/foo/map/version1」は、アルファベット順という文字整列順序に基づいた場合、図３に示すような整列順序となり、「com/foo」が最上位ノードとなり、次に「com/foo/map」で、続いて「com/foo/map/version1」となり、「com/foo/map/version2」が最下位ノードとなる。
【００２２】
したがって、図２の平衡２分探索木では、「com/foo/map」がルートノードとなり、その直近上位ノードが「com/foo」でその直近下位ノードが「com/foo/map/version2」となる。また、「com/foo/map/version2」の直近上位ノードが「com/foo/map/version1」となっている。これにより、この平衡２分探索木の例では、「com/foo/map/version1」のノードが最も深く、探索時には、検索文字列と各ノードの登録文字列とを最大で３回の比較する必要がある。
【００２３】
図４は、２つのハッシュテーブルを用いた平衡２分探索木の探索例である。前述した４つの登録文字「com/foo/map」,「com/foo」,「com/foo/map/version2」,「com/foo/map/version1」は、スラッシュ文字「/」で区分して得られる区分数が、それぞれ「３」，「２」，「４」，「４」となる。したがって、これら登録文字を区分数が「４」より小さいグループＡと、「４」以上のグループＢとに分けて、２つのハッシュテーブルに登録した場合、図４に示すような２つの平衡２分探索木が構築される。
【００２４】
すなわち、グループＡの平衡２分探索木は、「com/foo/map」がルートノードとなり、その直近上位ノードが「com/foo」となる。また、グループＢの平衡２分探索木は、「com/foo/map/version2」がルートノードとなり、その直近上位ノードが「com/foo/map/version1」となる。
これにより、これらグループＡ，Ｂの平衡２分探索木の深さはいずれも「２」となり、探索時における検索文字列と各ノードの登録文字列との最大比較数を「２」に低減することができる。本発明は、このような検索文字列の区分数と平衡２分探索木の深さとの関係に着目し、ハッシュテーブルを、検索文字列の区分数に応じた複数のハッシュテーブルで構成することにより、平衡２分探索木がより浅い構造となるようにしたものである。
【００２５】
次に、図１を参照して、本実施の形態にかかる辞書検索装置１０を構成する各機能部について詳細に説明する。
辞書１１は、ハードディスクや半導体メモリなどの記憶装置からなり、複数の登録文字列が電子化データに変換され、それぞれのハッシュ値と関連付けて登録されているデータベースである。図１では、辞書１１が辞書検索装置１０に設けられている場合を例として説明するが、これに限定されるものではない。例えば、通信回線を介して辞書検索装置１０に辞書１１を外部接続する構成であってもよい。
【００２６】
辞書１１には、主な辞書データとして、ブルームフィルタ１１Ａ、複数のハッシュテーブル１１Ｂ、および１または複数の平衡２分探索木テーブル１１Ｃが設けられている。
ブルームフィルタ１１Ａは、一般的なブルームフィルタからなり、ハッシュテーブル１１Ｂに対する検索文字列の登録有無を判定する機能を有している。なお、検索文字列の登録有無を効率よく判定できるフィルタであれば、ブルームフィルタ以外の公知のフィルタを用いてもよい。ブルームフィルタ１１Ａは、本発明にかかる必須の構成ではないが、ブルームフィルタ１１Ａを設けることにより、無駄な検索処理を省くことができる。
【００２７】
ハッシュテーブル１１Ｂは、検索文字列のハッシュ値に基づいて、対応する登録文字列または平衡２分探索木を特定する機能を有しており、予め設定されている区分方法に基づいて、それぞれ登録文字列を１または複数の文字列で複数に区分して得られた区分数（区分長）に対応して設けられている。この際、区分数がＮ（Ｎは正整数）種類存在する場合、これら区分数ごとにハッシュテーブル１１Ｂを構築してもよく、あるいは、これらＮ種類の区分数をＭ（Ｎ＞Ｍ＞０）個のグループに分類し、これらグループごとにハッシュテーブル１１Ｂを構築してもよい。
【００２８】
図５は、ハッシュテーブルの構成例である。本実施の形態では、区分数を２つのグループＡ，Ｂに分類して、それぞれハッシュテーブル１１Ｂを構築した場合を例として説明する。ここでは、区分数４未満からなるグループＡの登録文字列が図５（ａ）のハッシュテーブル１１Ｂに登録されており、区分数４以上からなるグループＢの登録文字列が図５（ｂ）のハッシュテーブル１１Ｂに登録されているものとする。
【００２９】
これらハッシュテーブル１１Ｂには、登録文字列のハッシュ値Ｈ（ＨＡ，ＨＢ）ごとに、登録文字列のうち当該ハッシュ値Ｈを有する唯一の登録文字列ＳＨ、または、登録文字列のうち当該ハッシュ値Ｈを共有する複数の衝突登録文字列をノードとする平衡２分探索木のうちルートノードを参照するための参照先ポインタ値ＰＨＳと、検索結果を示す出力値ＲＨとが、組としてが登録されている。
【００３０】
なお、ハッシュ関数については、各ハッシュテーブル１１Ｂで同じ関数を用いてもよいが、各ハッシュテーブル１１Ｂは、独立したテーブルであるため、それぞれ予め割り当てられている個別のハッシュ関数Ｈａ，Ｈｂを用いて、それぞれ固有のハッシュ値ＨＡ，ＨＢを求めるようにしてもよい。これにより、各ハッシュテーブル１１Ｂに登録される区分数に合わせて、それぞれの登録文字列を分類するのに過不足のない最適なハッシュ関数を利用することができる。
【００３１】
本実施の形態は、辞書１１において、任意のハッシュ値Ｈに対して、当該ハッシュ値Ｈを持つ登録文字列ＳＨを１つしか登録していない場合、当該ハッシュ値Ｈを有する唯一の登録文字列ＳＨをハッシュテーブル１１Ｂにのみ登録するようにしたものである。また、当該ハッシュ値Ｈを共有する複数の衝突登録文字列を辞書１１に登録する場合には、これら衝突登録文字列をハッシュテーブル１１Ｂに登録するのではなく、平衡２分探索木テーブル１１Ｃに当該ハッシュ値Ｈに関する平衡２分探索木を形成し、この平衡２分探索木のノードとしてこれらの衝突登録文字列を連携させて登録するようにしたものである。
【００３２】
図６は、平衡２分探索木テーブルの構成例である。平衡２分探索木テーブル１１Ｃには、衝突登録文字列ＳＴを識別するためのインデックス値Ｉごとに、当該インデックス値Ｉと対応する衝突登録文字列ＳＴ、規定の文字整列順序に従って当該衝突登録文字列ＳＴの直近上位に位置する衝突登録文字列のインデックス値を示す上位探索先ポインタ値ＰＵと、同じく規定の文字整列順序に従って当該衝突登録文字列ＳＴの直近下位に位置する衝突登録文字列のインデックス値を示す下位探索先ポインタ値ＰＬと、探索結果を示す出力値ＲＴとが、組としてが登録されている。なお、平衡２分探索木テーブル１１Ｃについては、１つに限定されるものではなく、例えば衝突登録文字列の登録数など、状況に応じて複数の平衡２分探索木テーブル１１Ｃを設けて衝突登録文字列を分散登録してもよい。また、平衡２分探索木の具体的な生成処理や更新処理については、非特許文献１など公知の技術を適用すればよい。
【００３３】
ハッシュ値計算部１２は、予め設定されているハッシュ関数に基づいて文字列に関するハッシュ値を計算する機能を有している。
【００３４】
検索処理部１３は、入力された検索指示で指定された検索文字列をブルームフィルタ１１Ａでフィルタリング処理することにより、ハッシュテーブル１１Ｂにおける登録有無を確認する機能と、登録なしの場合には当該検索文字列を１区分だけ短縮して繰り返しフィルタリング処理する機能と、短縮不可能な場合には、当該検索文字列の登録なしと判定する機能と、登録ありの場合には、当該検索文字列の区分数と対応する検索用ハッシュ関数およびハッシュテーブル１１Ｂを選択する機能と、検索用ハッシュ関数で計算した当該検索文字列のハッシュ値に基づいて、選択したハッシュテーブル１１Ｂを検索し、当該ハッシュ値に対応する登録文字列が登録されている場合には、当該登録文字列の登録ありと判定して当該検索文字列と対応する出力値を出力する機能を有している。
【００３５】
探索処理部１４は、入力された検索指示で指定された検索文字列のハッシュ値に対応する登録文字列が選択したハッシュテーブル１１Ｂに登録されていない場合には、当該ハッシュ値の参照先ポインタ値に基づいて平衡２分探索木テーブル１１Ｃを参照する機能と、当該参照先ポインタ値が示すインデックス値と対応する衝突登録文字列をルートノードとする平衡２分探索木のノードから、当該検索文字列と一致する衝突登録文字列を探索する機能と、得られた探索結果に応じて当該検索文字列の登録あり／なしを判定する機能と、当該検索文字列の登録ありの場合には当該検索文字列と対応する出力値を出力する機能と、当該参照先ポインタ値が登録されていない場合には、当該検索文字列の登録なしと判定する機能とを有している。
【００３６】
また、探索処理部１４は、平衡２分探索木テーブル１１Ｃのうち参照先ポインタ値と対応するインデックス値に基づいて、検索文字列のハッシュ値に関する平衡２分探索木のルートノードを最初の探索ノードとして選択する機能と、選択した探索ノードの探索を行う際、当該探索ノードの衝突登録文字列が検索文字列と一致した場合には、当該検索文字列の登録ありと判定して当該検索文字列と対応する出力値を出力した後に探索を終了する機能と、当該衝突登録文字列が当該検索文字列と一致しない場合には、文字整列順序に応じた当該衝突登録文字列と当該検索文字列との順序位関係に基づき、当該インデックス値の上位探索先ポインタ値または下位探索先ポインタ値と対応するインデックス値のノードを新たな探索ノードとして選択して探索を繰り返す機能と、当該順序位関係に応じた当該上位探索先ポインタ値または当該下位探索先ポインタ値が登録されていない場合には、当該検索文字列の登録なしと判定する機能とを有している。
【００３７】
登録処理部１５は、入力された登録指示で指定された指定文字列をブルームフィルタ１１Ａに追加登録する機能と、指定文字列の区分数と対応するハッシュ関数およびハッシュテーブル１１Ｂを選択する機能と、選択したハッシュ関数で計算した指定文字列の指定ハッシュ値に基づいて、選択したハッシュテーブル１１Ｂを参照し、当該指定ハッシュ値に対応する登録文字列が登録されている場合には、当該登録文字列および当該指定文字列からなる衝突登録文字列を、文字整列順序に従って当該指定ハッシュ値に関する平衡２分探索木のノードとして平衡２分探索木テーブル１１Ｃに登録する機能と、当該平衡２分探索木のルートノードとなった衝突登録文字列のインデックス値を当該指定ハッシュ値の参照先ポインタ値として選択したハッシュテーブル１１Ｂに登録するとともに、当該指定ハッシュ値の登録文字列をハッシュテーブル１１Ｂから削除する機能とを有している。
【００３８】
また、登録処理部１５は、当該指定ハッシュ値の登録文字列が選択したハッシュテーブル１１Ｂに登録されておらず当該指定ハッシュ値の参照先ポインタ値が登録されている場合には、当該指定文字列からなる衝突登録文字列を、文字整列順序に従って当該指定ハッシュ値に関する平衡２分探索木の新たなノードとして平衡２分探索木テーブル１１Ｃに追加登録する機能と、当該指定ハッシュ値に関する平衡２分探索木のルートノードとなった衝突登録文字列のインデックス値を当該指定ハッシュ値の参照先ポインタ値としてハッシュテーブル１１Ｂに登録する機能と、当該指定ハッシュ値の登録文字列および参照先ポインタ値が登録されていない場合には、当該指定文字列を当該指定ハッシュ値の登録文字列としてハッシュテーブル１１Ｂに登録する機能とを有している。
【００３９】
［本実施の形態の動作］
次に、図７を参照して、本実施の形態にかかる辞書検索装置１０の動作として、外部から入力された検索指示の検索文字列が辞書１１に登録されているか否かを判定する際における辞書検索動作の概略について説明する。図７は、辞書検索動作の概略を示す説明図である。
【００４０】
まず、検索処理部１３により、ブルームフィルタ１１Ａを用いて、各ハッシュテーブル１１Ｂに検索文字列が存在するか否か判定される。ここで、検索文字列が存在した場合、検索文字列の区分数に基づいて、対応するハッシュ関数とハッシュテーブル１１Ｂとが選択される。
【００４１】
図７の例では、前述した図５と同様にして、区分数が４未満である登録文字列がグループＡのハッシュテーブル１１Ｂに登録されており、ハッシュ関数としてＨａが割り当てられている。また、区分数が「４」以上である登録文字列がグループＢのハッシュテーブル１１Ｂに登録されており、ハッシュ関数としてＨｂが割り当てられている。
したがって、検索文字列として「com/foo/map/version2」が指定された場合、この区分数が「４」であることから、グループＢのハッシュテーブル１１Ｂが選択されるとともに、ハッシュ関数としてＨｂが選択される。
【００４２】
この後、検索処理部１３により、ハッシュ関数Ｈｂに基づき検索文字列「com/foo/map/version2」のハッシュ値が計算され、このハッシュ値に基づきグループＢのハッシュテーブル１１Ｂを検索される。
ここで、ハッシュ値ＨＢが０（ＨＢ［０］）であって、図５（ｂ）に示すようにグループＢのハッシュテーブル１１Ｂに、ＨＢ［０］と対応する登録文字列ＳＴが登録されておらず（Ｎｕｌｌ）、参照先ポインタ値ＰＨ＝「５」が登録されている場合、探索処理部１４に対して、平衡２分探索木を用いた探索指示が出力される。
【００４３】
これに応じて、探索処理部１４により、平衡２分探索木テーブル１１Ｃのうち、参照先ポインタ値ＰＨと対応するインデックス値Ｉを持つエントリをルートノードとする平衡２分探索木が選択され、この平衡２分探索木に基づき、各ノードの衝突登録文字列ＳＴと検索文字列とが順に比較される。
【００４４】
ここで、平衡２分探索木テーブル１１Ｃが前述した図６のような構成である場合、参照先ポインタ値ＰＨと対応するインデックス値Ｉ＝５の衝突登録文字列ＳＴが検索文字列と一致するため、その出力値ＲＴ＝３が探索結果として検索処理部１３に出力される。
これにより、検索処理部１３は、検索結果として、検索文字列「com/foo/map/version2」が辞書１１に登録されており、対応する出力値が３であることを出力する。
【００４５】
［検索処理］
次に、図８を参照して、本実施の形態にかかる辞書検索装置１０の動作として、検索処理部１３による検索指示に応じたハッシュテーブル１１Ｂでの検索処理について、詳細に説明する。図８は、検索処理を示すフローチャートである。
検索処理部１３は、外部から入力された検索指示に応じて辞書１１を検索する際、当該検索指示で指定された検索文字列が辞書１１に登録されているか否かを確認する処理として、図８の検索処理を実行する。
【００４６】
検索処理部１３は、まず、ブルームフィルタ１１Ａを参照して、各ハッシュテーブル１１Ｂのいずれかに検索文字列が登録されているか否か判定する（ステップ１００）。ここで、検索文字列が登録されている場合（ステップ１００：ＹＥＳ）、検索処理部１３は、検索文字列の区分数に基づき、検索文字列と対応するハッシュ関数とハッシュテーブル１１Ｂとを選択する（ステップ１０１）。
【００４７】
続いて、検索処理部１３は、検索文字列のハッシュ値である検索ハッシュ値を、選択したハッシュ関数を用いてハッシュ値計算部１２により計算し（ステップ１０２）、選択したハッシュテーブル１１Ｂを参照して、検索ハッシュ値に対応する登録文字列ＳＨの登録有無を確認する（ステップ１０３）。
【００４８】
ここで、検索ハッシュ値に対応する登録文字列ＳＨがハッシュテーブル１１Ｂに登録されている場合（ステップ１０３：ＹＥＳ）、検索処理部１３は、その登録文字列ＳＨと検索文字列とを比較し（ステップ１０４）、得られた比較結果すなわち一致／不一致に応じて、検索文字列の登録有無を判定して検索結果として出力し（ステップ１０５）、一連の検索処理を終了する。
【００４９】
一方、検索ハッシュ値に対応する登録文字列ＳＨがハッシュテーブル１１Ｂに登録されていない場合（ステップ１０３：ＮＯ）、検索処理部１３は、ハッシュテーブル１１Ｂを参照して、検索ハッシュ値に対応する参照先ポインタ値の登録有無を確認する（ステップ１０６）。
【００５０】
ここで、検索ハッシュ値に対応する参照先ポインタ値がハッシュテーブル１１Ｂに登録されている場合（ステップ１０６：ＹＥＳ）、検索処理部１３は、探索処理部１４に対して検索文字列に関する探索指示を出力し（ステップ１０７）、これに応じて探索処理部１４から通知された探索結果すなわち平衡２分探索木テーブル１１Ｃにおける登録有無に基づいて、検索文字列の登録有無を判定して検索結果として出力し（ステップ１０８）、一連の検索処理を終了する。
【００５１】
一方、検索ハッシュ値に対応する参照先ポインタ値がハッシュテーブル１１Ｂに登録されていない場合（ステップ１０６：ＮＯ）、検索処理部１３は、検索文字列の登録なしを検索結果として出力し（ステップ１０９）、一連の検索処理を終了する。
【００５２】
これにより、検索文字列の区分数により選択されたハッシュテーブル１１Ｂの内容が、図５（ａ）に示す状態にあり、検索ハッシュ値ＨＡ＝「１」の場合、これに対応する登録文字列ＳＨおよび参照先ポインタ値ＰＨが「（ｎｕｌｌ）」であり、いずれも未登録であることから、検索文字列の登録なしと判定される。
一方、検索ハッシュ値ＨＡ＝「０」の場合、登録文字列ＳＨが登録されていることから、検索文字列の登録ありと判定される。
【００５３】
また、検索ハッシュ値ＨＡ＝「２」の場合、これに対応する登録文字列ＳＨが登録されておらず参照先ポインタ値ＰＨが登録されていることから、当該参照先ポインタ値ＰＨ＝「１」に基づいて、平衡２分探索木テーブル１１Ｃのうちから対応する平衡２分探索木が選択されて、平衡２分探索木において検索文字列の探索処理が実行され、得られた探索結果に基づいて検索文字列の登録有無が判定される。
【００５４】
また、ステップ１００において、ブルームフィルタ１１Ａにより検索文字列がハッシュテーブル１１Ｂのいずれにも登録されていないと判定された場合（ステップ１００：ＮＯ）、検索処理部１３は、検索文字列の区分数を確認し（ステップ１１０）、区分数が「１」より大きい場合には（ステップ１１０：ＹＥＳ）、検索文字列を末尾から１区分だけ削除して短縮した後（ステップ１１１）、ステップ１００へ戻る。また、区分数が「１」以下の場合（ステップ１１０：ＮＯ）、ステップ１０９へ移行して、検索文字列の登録なしを検索結果として出力し（ステップ１０９）、一連の検索処理を終了する。
【００５５】
［探索処理］
次に、図９を参照して、探索処理部１４での探索処理について説明する。図９は、探索処理を示すフローチャートである。
探索処理部１４は、検索処理部１３からの探索指示に応じて平衡２分探索木テーブル１１Ｃを探索する際、当該探索指示で指定された検索文字列が平衡２分探索木テーブル１１Ｃに登録されているか否かを確認する処理として、図９の探索処理を実行する。
【００５６】
探索処理部１４は、まず、指定された検索文字列の検索ハッシュ値に対応する参照先ポインタ値ＰＨからなるインデックス値Ｉに基づいて平衡２分探索木テーブル１１Ｃを参照し、インデックス値Ｉと対応する平衡２分探索木のルートノードを最初の探索ノードとして選択する（ステップ１２０）。
【００５７】
続いて、探索処理部１４は、当該衝突登録文字列と検索文字列とを比較し（ステップ１２１）、衝突登録文字列と検索文字列とが一致した場合（ステップ１２１：ＹＥＳ）、探索処理部１４は、探索結果として検索文字列の登録ありを出力し（ステップ１２８）、一連の探索処理を終了する。
また、衝突登録文字列と検索文字列とが一致しない場合（ステップ１２１：ＮＯ）、探索処理部１４は、規定の文字整列順序に基づいて衝突登録文字列と検索文字列との整列順を確認する（ステップ１２２）。
【００５８】
この際、検索文字列の整列順序が衝突登録文字列より上位である場合（ステップ１２２：ＹＥＳ）、探索処理部１４は、探索ノードに対して上位探索先ポインタ値ＰＵが登録されているか確認し（ステップ１２３）、上位探索先ポインタ値ＰＵが登録されている場合には（ステップ１２３：ＹＥＳ）、その上位探索先ポインタ値ＰＵが示すインデックス値Ｉに対応するノードを新たな探索ノードとして選択した後（ステップ１２４）、ステップ１２１へ戻って探索を繰り返し実施する。
【００５９】
一方、検索文字列の整列順序が衝突登録文字列ＳＴより下位である場合（ステップ１２２：ＮＯ）、探索処理部１４は、探索ノードに対して下位探索先ポインタ値ＰＬが登録されているか確認し（ステップ１２５）、下位探索先ポインタ値ＰＬが登録されている場合には（ステップ１２５：ＹＥＳ）、その下位探索先ポインタ値ＰＬが示すインデックス値Ｉに対応するノードを新たな探索ノードとして選択した後（ステップ１２６）、ステップ１２１へ戻って探索を繰り返し実施する。
【００６０】
また、ステップ１２３において、上位探索先ポインタ値ＰＵが登録されていない場合（ステップ１２３：ＮＯ）、並びに、ステップ１２５において、下位探索先ポインタ値ＰＬが登録されていない場合（ステップ１２５：ＮＯ）、探索処理部１４は、ステップ１２７へ移行して、探索結果として検索文字列の登録なしを出力し（ステップ１２７）、一連の探索処理を終了する。
【００６１】
これにより、検索文字列の区分数により選択されたハッシュテーブル１１Ｂと平衡２分探索木テーブル１１Ｃの内容が、それぞれ前述した図５（ａ）および図６に示す状態にあり、検索文字列が「com/foo」であり、検索ハッシュ値ＨＡ＝「２」の場合、参照先ポインタ値ＰＨ＝「１」に基づいて平衡２分探索木テーブル１１Ｃのうちハッシュ値ＨＡ＝「２」に対応する平衡２分探索木が参照され、平衡２分探索木における探索が開始される。
【００６２】
ハッシュ値ＨＡ＝「２」に対応する平衡２分探索木において、まず、インデックス値Ｉ「１」のルートノードが探索ノードとして選択され、衝突登録文字列ＳＴ「com/foo/map」と検索文字列「com/foo」とが比較される。ここで、両者が不一致であり、検索文字列の整列順が衝突登録文字列ＳＴより上位であることから、当該探索ノードの上位探索先ポインタ値ＰＵ＝「０」に基づき、インデックス値＝「０」のノードが新たな探索ノードとして選択される。
【００６３】
インデックス値＝「０」の探索ノードでは、衝突登録文字列ＳＴ「com/foo」と検索文字列「com/foo」とが比較される。ここで、両者が一致していることから、検索文字列の登録ありを示す探索結果が出力される。
【００６４】
［登録処理］
次に、図１０を参照して、登録処理部１５での登録処理について説明する。図１０は、登録処理を示すフローチャートである。
登録処理部１５は、外部から入力された登録指示に応じて指定文字列を辞書１１に登録する際、図１０の登録処理を実行する。なお、ブルームフィルタ１１Ａに対する指定文字列の登録、平衡２分探索木テーブル１１Ｃに対する平衡２分探索木の新規登録、平衡２分探索木へのノード追加、規定の文字整列順序に基づく平衡２分探索木の平衡化処理など、平衡２分探索木に関する詳細処理については公知の技術を用いればよく、ここでの説明は省略する。
【００６５】
登録処理部１５は、まず、登録指示で指定された指定文字列をブルームフィルタ１１Ａに登録し（ステップ１３０）、指定文字列の区分数に基づきハッシュ関数とハッシュテーブル１１Ｂとを選択する（ステップ１３１）。
続いて、登録処理部１５は、指定文字列のハッシュ値である指定ハッシュ値を、選択したハッシュ関数を用いてハッシュ値計算部１２により計算し（ステップ１３２）、選択したハッシュテーブル１１Ｂを参照して、指定ハッシュ値に対応する登録文字列ＳＨの登録有無を確認する（ステップ１３３）。
【００６６】
ここで、指定ハッシュ値に対応する登録文字列ＳＨがハッシュテーブル１１Ｂに登録されている場合（ステップ１３３：ＹＥＳ）、登録処理部１５は、当該指定ハッシュ値に対応する平衡２分探索木を平衡２分探索木テーブル１１Ｃに新規登録し（ステップ１３４）、登録文字列ＳＨおよび指定文字列からなる衝突登録文字列ＳＴを当該平衡２分探索木のノードとして追加する（ステップ１３５）。
【００６７】
この後、登録処理部１５は、当該平衡２分探索木のルートノードを示すインデックス値Ｉ（ルートインデックス）を、指定ハッシュ値の参照先ポインタ値ＰＨとしてハッシュテーブル１１Ｂに登録し（ステップ１３６）、指定ハッシュ値の登録文字列ＳＨをハッシュテーブル１１Ｂから削除し（ステップ１３７）、一連の登録処理を終了する。
【００６８】
一方、ステップ１３３において、指定ハッシュ値に対応する登録文字列ＳＨがハッシュテーブル１１Ｂに登録されていない場合（ステップ１３３：ＮＯ）、登録処理部１５は、指定ハッシュ値に対応する参照先ポインタ値ＰＨがハッシュテーブル１１Ｂに登録されているか否か確認する（ステップ１３８）。
【００６９】
ここで、指定ハッシュ値に対応する参照先ポインタ値ＰＨがハッシュテーブル１１Ｂに登録されている場合（ステップ１３８：ＹＥＳ）、登録処理部１５は、当該参照先ポインタ値ＰＨからなるインデックス値Ｉに基づいて平衡２分探索木テーブル１１Ｃを参照し、指定ハッシュ値に対応する平衡２分探索木の新たなノードとして、指定文字列からなる衝突登録文字列ＳＴを追加するとともに当該平衡２分探索木を平衡化し（ステップ１３９）、当該平衡２分探索木のルートノードを示すインデックス値Ｉ（ルートインデックス）を、指定ハッシュ値の参照先ポインタ値ＰＨとしてハッシュテーブル１１Ｂに登録した後（ステップ１４０）、一連の登録処理を終了する。
【００７０】
また、ステップ１３８において、指定ハッシュ値に対応する参照先ポインタ値ＰＨがハッシュテーブル１１Ｂに登録されていない場合（ステップ１３８：ＮＯ）、登録処理部１５は、指定文字列を指定ハッシュ値に対応する登録文字列ＳＨとしてハッシュテーブル１１Ｂに登録し（ステップ１４１）、一連の登録処理を終了する。
【００７１】
これにより、指定文字列の区分数により選択されたハッシュテーブル１１Ｂの内容が前述した図５（ａ）に示す状態にあり、指定文字列の検索ハッシュ値が「１」の場合、ハッシュ値ＨＡ＝「１」の登録文字列ＳＨおよび参照先ポインタ値ＰＨがともに「（ｎｕｌｌ）」であり、未登録であることから、ハッシュ値ＨＡ＝「１」の登録文字列ＳＨとして指定文字列が新規に登録される。
【００７２】
また、指定文字列の検索ハッシュ値が「０」の場合、ハッシュ値ＨＡ＝「０」に登録文字列ＳＨが登録されていることから、ハッシュ値ＨＡ＝「０」と対応する平衡２分探索木が平衡２分探索木テーブル１１Ｃに新規登録され、そのノードとしてハッシュ値ＨＡ＝「０」に対応して登録されていた登録文字列ＳＨと指定文字列からなる衝突登録文字列ＳＴが、ハッシュ値ＨＡ＝「０」と対応する平衡２分探索木のノードとして登録される。また、当該平衡２分探索木のルートノードを示すインデックス値Ｉがハッシュ値ＨＡ＝「０」の参照先ポインタ値ＰＨとして登録され、ハッシュ値ＨＡ＝「０」の登録文字列ＳＨが削除されて「（ｎｕｌｌ）」となる。
【００７３】
また、指定文字列の検索ハッシュ値が「２」の場合、ハッシュ値ＨＡ＝「２」に登録文字列ＳＨが登録されておらず参照先ポインタ値ＰＨが登録されていることから、平衡２分探索木テーブル１１Ｃのうちハッシュ値ＨＡ＝「２」と対応する平衡２分探索木の新たなノードとして、指定文字列の衝突登録文字列ＳＴが登録される。また、必要に応じて、平衡２分探索木は平衡化され、更新されたルートノードのインデックス値Ｉによりハッシュ値ＨＡ＝「２」と対応する参照先ポインタ値ＰＨが更新される。
【００７４】
［本実施の形態の効果］
このように、本実施の形態は、登録文字列の区分数に対応して設けられた複数のハッシュテーブル１１Ｂと１または複数の平衡２分探索木テーブル１１Ｃとを辞書１１に設け、辞書検索時には、検索処理部１３が、検索文字列の区分数に対応するハッシュテーブル１１Ｂを選択して、検索文字列の検索ハッシュ値に基づき当該ハッシュテーブル１１Ｂを検索し、検索文字列の検索ハッシュ値に対応する平衡２分探索木が構築されている場合には、辞書探索処理部１４が、平衡２分探索木テーブル１１Ｃのうち対応する平衡２分探索木から検索文字列を探索するようにしたものである。
【００７５】
これにより、各平衡２分探索木には、検索文字列の区分数に対応する衝突登録文字列のみがノードとして登録されることになり、平衡２分探索木をより浅い構造とすることができる。したがって、辞書１１を検索する際に要する検索時間を短縮することが可能となる。
【００７６】
［実施の形態の拡張］
以上、実施形態を参照して本発明を説明したが、本発明は上記実施形態に限定されるものではない。本発明の構成や詳細には、本発明のスコープ内で当業者が理解しうる様々な変更をすることができる。また、各実施形態については、矛盾しない範囲で任意に組み合わせて実施することができる。
【符号の説明】
【００７７】
１０…辞書検索装置、１１…辞書、１１Ａ…ブルームフィルタ、１１Ｂ…ハッシュテーブル、１１Ｃ…２分探索木テーブル、１２…ハッシュ値計算部、１３…検索処理部、１４…探索処理部、１５…登録処理部。
【図１】
2018081611.tif 000003
【図２】
2018081611.tif 000004
【図３】
2018081611.tif 000005
【図４】
2018081611.tif 000006
【図５】
2018081611.tif 000007
【図６】
2018081611.tif 000008
【図７】
2018081611.tif 000009
【図８】
2018081611.tif 000010
【図９】
2018081611.tif 000011
【図１０】
2018081611.tif 000012