(57)【要約】【課題】多数の衝突登録文字列が登録されていても短時間で検索文字列を検索する。【解決手段】ハッシュ値ごとに、登録文字列のうち当該ハッシュ値を有する唯一の登録文字列、または、登録文字列のうち当該ハッシュ値を共有する複数の衝突登録文字列をノードとする平衡２分探索木のうちルートノードを参照するための参照先ポインタ値が登録されているハッシュテーブル１１Ａと、衝突登録文字列と当該衝突登録文字列を識別するためのインデクス値とが、当該衝突登録文字列のハッシュ値に関する平衡２分探索木のノードとして、規定の文字整列順序に基づいて登録されている平衡２分探索木テーブル１１Ｂとを辞書１１に設け、検索時において、検索文字列の検索ハッシュ値に対応する平衡２分探索木が構築されている場合には、辞書探索処理部１４により、対応する平衡２分探索木から検索文字列を探索する。【選択図】  図１
2017091432.tif 000002
【特許請求の範囲】
【請求項１】
入力された検索指示に応じて、辞書に登録されている登録文字列を、これら登録文字列のハッシュ値に基づいて検索する辞書検索方法であって、
前記辞書は、前記ハッシュ値ごとに、前記登録文字列のうち当該ハッシュ値を有する唯一の登録文字列、または、前記登録文字列のうち当該ハッシュ値を共有する複数の衝突登録文字列をノードとする平衡２分探索木のうちルートノードを参照するための参照先ポインタ値が登録されているハッシュテーブルと、前記衝突登録文字列と当該衝突登録文字列を識別するためのインデクス値とが、当該衝突登録文字列のハッシュ値に関する平衡２分探索木のノードとして、規定の文字整列順序に基づいて登録されている平衡２分探索木テーブルとを有し、
前記検索指示で指定された検索文字列のハッシュ値に基づいて前記ハッシュテーブルを検索し、当該ハッシュ値に対応する登録文字列が登録されている場合には、当該検索文字列の登録ありと判定する辞書検索処理ステップと、
前記検索文字列のハッシュ値に対応する登録文字列が前記ハッシュテーブルに登録されていない場合には、当該ハッシュ値の参照先ポインタ値に基づいて前記平衡２分探索木テーブルを参照し、当該参照先ポインタ値が示す前記インデクス値と対応する前記衝突登録文字列をルートノードとする前記平衡２分探索木のノードから、当該検索文字列と一致する衝突登録文字列を探索し、得られた探索結果に応じて当該検索文字列の登録あり／なしを判定し、当該参照先ポインタ値が登録されていない場合には、当該検索文字列の登録なしと判定する辞書探索処理ステップと
を備えることを特徴とする辞書検索方法。
【請求項２】
請求項１に記載の辞書検索方法において、
前記平衡２分探索木テーブルには、前記インデクス値ごとに、前記文字整列順序に従って前記衝突登録文字列の直近上位に位置する衝突登録文字列のインデクス値を示す上位探索先ポインタ値と、前記文字整列順序に従って当該衝突登録文字列の直近下位に位置する衝突登録文字列のインデクス値を示す下位探索先ポインタ値とが登録されており、
前記辞書探索処理ステップは、前記平衡２分探索木テーブルのうち前記参照先ポインタ値と対応するインデクス値に基づいて、前記検索文字列のハッシュ値に関する前記平衡２分探索木のルートノードを最初の探索ノードとして選択し、選択した探索ノードの探索を行う際、当該探索ノードの衝突登録文字列が前記検索文字列と一致した場合には、当該検索文字列の登録ありと判定して探索を終了し、当該衝突登録文字列が当該検索文字列と一致しない場合には、前記文字整列順序に応じた当該衝突登録文字列と当該検索文字列との順序位関係に基づき、当該インデクス値の上位探索先ポインタ値または下位探索先ポインタ値と対応するインデクス値のノードを新たな探索ノードとして選択して探索を繰り返し、当該順序位関係に応じた当該上位探索先ポインタ値または当該下位探索先ポインタ値が登録されていない場合には、当該検索文字列の登録なしと判定する
ことを特徴とする辞書検索方法。
【請求項３】
請求項１または請求項２に記載の辞書検索方法において、
入力された登録指示で指定された指定文字列のハッシュ値に基づいて前記ハッシュテーブルを参照し、当該ハッシュ値に対応する登録文字列が登録されている場合には、当該登録文字列および当該指定文字列からなる衝突登録文字列を、前記文字整列順序に従って当該ハッシュ値に関する平衡２分探索木のノードとして前記平衡２分探索木テーブルに登録し、当該平衡２分探索木のルートノードとなった衝突登録文字列のインデクス値を当該ハッシュ値の参照先ポインタ値として前記ハッシュテーブルに登録するとともに、当該ハッシュ値の登録文字列を前記ハッシュテーブルから削除する辞書登録処理ステップをさらに備え、
前記辞書登録処理ステップは、前記指定文字列のハッシュ値に基づき前記ハッシュテーブルを参照し、当該ハッシュ値の登録文字列が登録されておらず当該ハッシュ値の参照先ポインタ値が登録されている場合には、当該指定文字列からなる衝突登録文字列を、前記文字整列順序に従って当該ハッシュ値に関する平衡２分探索木の新たなノードとして前記平衡２分探索木テーブルに追加登録するとともに、当該ハッシュ値に関する平衡２分探索木のルートノードとなった衝突登録文字列のインデクス値を当該ハッシュ値の参照先ポインタ値として前記ハッシュテーブルに登録し、当該ハッシュ値の登録文字列および参照先ポインタ値が登録されていない場合には、当該指定文字列を当該ハッシュ値の登録文字列として前記ハッシュテーブルに登録する
ことを特徴とする辞書検索方法。
【請求項４】
入力された検索指示に応じて、辞書に登録されている登録文字列を、これら登録文字列のハッシュ値に基づいて検索する辞書検索装置であって、
前記辞書は、前記ハッシュ値ごとに、前記登録文字列のうち当該ハッシュ値を有する唯一の登録文字列、または、前記登録文字列のうち当該ハッシュ値を共有する複数の衝突登録文字列をノードとする平衡２分探索木のうちルートノードを参照するための参照先ポインタ値が登録されているハッシュテーブルと、前記衝突登録文字列と当該衝突登録文字列を識別するためのインデクス値とが、当該衝突登録文字列のハッシュ値に関する平衡２分探索木のノードとして、規定の文字整列順序に基づいて登録されている平衡２分探索木テーブルとを有し、
前記検索指示で指定された検索文字列のハッシュ値に基づいて前記ハッシュテーブルを検索し、当該ハッシュ値に対応する登録文字列が登録されている場合には、当該検索文字列の登録ありと判定する辞書検索処理部と、
前記検索文字列のハッシュ値に対応する登録文字列が前記ハッシュテーブルに登録されていない場合には、当該ハッシュ値の参照先ポインタ値に基づいて前記平衡２分探索木テーブルを参照し、当該参照先ポインタ値が示す前記インデクス値と対応する前記衝突登録文字列をルートノードとする前記平衡２分探索木のノードから、当該検索文字列と一致する衝突登録文字列を探索し、得られた探索結果に応じて当該検索文字列の登録あり／なしを判定し、当該参照先ポインタ値が登録されていない場合には、当該検索文字列の登録なしと判定する辞書探索処理部と
を備えることを特徴とする辞書検索装置。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、辞書に登録されている登録文字列を、これら登録文字列のハッシュ値に基づいて検索する辞書検索技術に関する。
【背景技術】
【０００２】
辞書に登録されている多くの登録文字列（見出し語）から、指定された検索文字列を高速検索する手法の１つとしてハッシュ値を用いたハッシュ法がある。このハッシュ法は、予め辞書に登録文字列を登録する際、一定の規則すなわちハッシュ関数に基づいて登録文字列のハッシュ値を計算して、登録文字列のインデックスとして辞書に登録しておき、この辞書から検索文字列を検索する場合には、登録時と同じハッシュ関数に基づき計算した検索文字列のハッシュ値に基づき、辞書から同一のハッシュ値を持つ登録文字列を検索するものである。これにより、辞書に登録されている各文字列を検索文字列と逐次比較して検索するより、高速で検索することが可能となる。
【０００３】
このようなハッシュ関数としては、登録文字列や検索文字列ごとに一意なハッシュ値を計算する完全ハッシュ関数が理想的である。しかし、検索速度や辞書サイズという観点からは、比較的少ない桁数のハッシュ値を高速で計算できるハッシュ関数を選択する必要があるため、現実的にはこのような条件を満足する完全ハッシュ関数を実現するのは難しい。したがって、完全ハッシュ関数ではない関数を用いるということは、ハッシュ値と文字列とが１対多で対応する可能性を容認することになり、文字列が異なるにも関わらず同じ値のハッシュ値が計算される、いわゆるハッシュの衝突が発生する場合がある。
【０００４】
従来、このようなハッシュの衝突を解決する技術として、同一ハッシュ値を持つ複数の文字列を線形リストに登録しておき、検索文字列を検索する際には、検索文字列からハッシュ関数により計算したハッシュ値と対応する線形リストに登録されている各文字列と、検索文字列とを逐次比較して一致するものを検索する方法が提案されている（非特許文献１など参照）。これにより、ハッシュ値と文字列とが１対多で対応する可能性があるハッシュ関数であっても、辞書から検索文字列を検索することが可能となる。
【先行技術文献】
【非特許文献】
【０００５】
【非特許文献１】「主要なアルゴリズムとデータ構造」、電子情報通信学会『知識の森、http://www.ieice-hbkb.org/files/06/06gun_03hen_03.pdf
【発明の概要】
【発明が解決しようとする課題】
【０００６】
しかしながら、このような従来技術では、辞書から検索文字列を検索する際、検索文字列のハッシュ値に対して線形リストが構築されている場合には、その線形リストに登録されている複数の文字列と検索文字列とを比較して同一性を逐次確認する必要がある。この際、必要となる同一性の確認回数は、線形リストに登録されている文字列の登録数に依存して増大することになる。したがって、従来技術によれば、検索文字列の検索に要する所要時間は、辞書の大規模化に応じて加速度的に増大するという問題点があった。
【０００７】
本発明はこのような課題を解決するためのものであり、同一ハッシュ値を有する衝突登録文字列が辞書に登録されている場合であっても、短時間で検索文字列を検索できる辞書検索技術を提供することを目的としている。
【課題を解決するための手段】
【０００８】
このような目的を達成するために、本発明にかかる辞書検索方法は、入力された検索指示に応じて、辞書に登録されている登録文字列を、これら登録文字列のハッシュ値に基づいて検索する辞書検索方法であって、前記辞書が、前記ハッシュ値ごとに、前記登録文字列のうち当該ハッシュ値を有する唯一の登録文字列、または、前記登録文字列のうち当該ハッシュ値を共有する複数の衝突登録文字列をノードとする平衡２分探索木のうちルートノードを参照するための参照先ポインタ値が登録されているハッシュテーブルと、前記衝突登録文字列と当該衝突登録文字列を識別するためのインデクス値とが、当該衝突登録文字列のハッシュ値に関する平衡２分探索木のノードとして、規定の文字整列順序に基づいて登録されている平衡２分探索木テーブルとを有し、前記検索指示で指定された検索文字列のハッシュ値に基づいて前記ハッシュテーブルを検索し、当該ハッシュ値に対応する登録文字列が登録されている場合には、当該検索文字列の登録ありと判定する辞書検索処理ステップと、前記検索文字列のハッシュ値に対応する登録文字列が前記ハッシュテーブルに登録されていない場合には、当該ハッシュ値の参照先ポインタ値に基づいて前記平衡２分探索木テーブルを参照し、当該参照先ポインタ値が示す前記インデクス値と対応する前記衝突登録文字列をルートノードとする前記平衡２分探索木のノードから、当該検索文字列と一致する衝突登録文字列を探索し、得られた探索結果に応じて当該検索文字列の登録あり／なしを判定し、当該参照先ポインタ値が登録されていない場合には、当該検索文字列の登録なしと判定する辞書探索処理ステップとを備えている。
【０００９】
また、本発明にかかる上記辞書検索方法の一構成例は、前記平衡２分探索木テーブルには、前記インデクス値ごとに、前記文字整列順序に従って前記衝突登録文字列の直近上位に位置する衝突登録文字列のインデクス値を示す上位探索先ポインタ値と、前記文字整列順序に従って当該衝突登録文字列の直近下位に位置する衝突登録文字列のインデクス値を示す下位探索先ポインタ値とが登録されており、前記辞書探索処理ステップは、前記平衡２分探索木テーブルのうち前記参照先ポインタ値と対応するインデクス値に基づいて、前記検索文字列のハッシュ値に関する前記平衡２分探索木のルートノードを最初の探索ノードとして選択し、選択した探索ノードの探索を行う際、当該探索ノードの衝突登録文字列が前記検索文字列と一致した場合には、当該検索文字列の登録ありと判定して探索を終了し、当該衝突登録文字列が当該検索文字列と一致しない場合には、前記文字整列順序に応じた当該衝突登録文字列と当該検索文字列との順序位関係に基づき、当該インデクス値の上位探索先ポインタ値または下位探索先ポインタ値と対応するインデクス値のノードを新たな探索ノードとして選択して探索を繰り返し、当該順序位関係に応じた当該上位探索先ポインタ値または当該下位探索先ポインタ値が登録されていない場合には、当該検索文字列の登録なしと判定するようにしたものである。
【００１０】
また、本発明にかかる上記辞書検索方法の一構成例は、入力された登録指示で指定された指定文字列のハッシュ値に基づいて前記ハッシュテーブルを参照し、当該ハッシュ値に対応する登録文字列が登録されている場合には、当該登録文字列および当該指定文字列からなる衝突登録文字列を、前記文字整列順序に従って当該ハッシュ値に関する平衡２分探索木のノードとして前記平衡２分探索木テーブルに登録し、当該平衡２分探索木のルートノードとなった衝突登録文字列のインデクス値を当該ハッシュ値の参照先ポインタ値として前記ハッシュテーブルに登録するとともに、当該ハッシュ値の登録文字列を前記ハッシュテーブルから削除する辞書登録処理ステップをさらに備え、前記辞書登録処理ステップは、前記指定文字列のハッシュ値に基づき前記ハッシュテーブルを参照し、当該ハッシュ値の登録文字列が登録されておらず当該ハッシュ値の参照先ポインタ値が登録されている場合には、当該指定文字列からなる衝突登録文字列を、前記文字整列順序に従って当該ハッシュ値に関する平衡２分探索木の新たなノードとして前記平衡２分探索木テーブルに追加登録するとともに、当該ハッシュ値に関する平衡２分探索木のルートノードとなった衝突登録文字列のインデクス値を当該ハッシュ値の参照先ポインタ値として前記ハッシュテーブルに登録し、当該ハッシュ値の登録文字列および参照先ポインタ値が登録されていない場合には、当該指定文字列を当該ハッシュ値の登録文字列として前記ハッシュテーブルに登録するようにしたものである。
【００１１】
また、本発明にかかる辞書検索装置は、入力された検索指示に応じて、辞書に登録されている登録文字列を、これら登録文字列のハッシュ値に基づいて検索する辞書検索装置であって、前記辞書は、前記ハッシュ値ごとに、前記登録文字列のうち当該ハッシュ値を有する唯一の登録文字列、または、前記登録文字列のうち当該ハッシュ値を共有する複数の衝突登録文字列をノードとする平衡２分探索木のうちルートノードを参照するための参照先ポインタ値が登録されているハッシュテーブルと、前記衝突登録文字列と当該衝突登録文字列を識別するためのインデクス値とが、当該衝突登録文字列のハッシュ値に関する平衡２分探索木のノードとして、規定の文字整列順序に基づいて登録されている平衡２分探索木テーブルとを有し、前記検索指示で指定された検索文字列のハッシュ値に基づいて前記ハッシュテーブルを検索し、当該ハッシュ値に対応する登録文字列が登録されている場合には、当該検索文字列の登録ありと判定する辞書検索処理部と、前記検索文字列のハッシュ値に対応する登録文字列が前記ハッシュテーブルに登録されていない場合には、当該ハッシュ値の参照先ポインタ値に基づいて前記平衡２分探索木テーブルを参照し、当該参照先ポインタ値が示す前記インデクス値と対応する前記衝突登録文字列をルートノードとする前記平衡２分探索木のノードから、当該検索文字列と一致する衝突登録文字列を探索し、得られた探索結果に応じて当該検索文字列の登録あり／なしを判定し、当該参照先ポインタ値が登録されていない場合には、当該検索文字列の登録なしと判定する辞書探索処理部とを備えている。
【発明の効果】
【００１２】
本発明によれば、線形リストに登録されている複数の登録文字列と検索文字列とを比較して同一性を逐次確認する場合と比較して、確認回数を大幅に削減でき、辞書検索処理の簡素化および所要時間の短縮を実現することが可能となる。このため、本発明によれば、ハッシュ法を用いた大規模な辞書に対して、同一ハッシュ値を有する衝突登録文字列が多数登録される場合であっても、指定された検索文字列を辞書から短時間で検索することが可能となる。
【図面の簡単な説明】
【００１３】
【図１】辞書検索装置の構成を示すブロック図である。
【図２】ハッシュテーブルの構成例である。
【図３】平衡２分探索木テーブルの構成例である。
【図４】平衡２分探索木を示す説明図である。
【図５】辞書検索処理を示すフローチャートである。
【図６】辞書探索処理を示すフローチャートである。
【図７】辞書登録処理を示すフローチャートである。
【図８】衝突登録文字数と必要確認回数の関係を示すグラフである。
【発明を実施するための形態】
【００１４】
［発明の原理］
まず、本発明の原理について説明する。
文字には、コード順、アルファベット順、五十音順など、規定の文字整列順序が存在する。したがって、このような文字整列順序に基づいて、異なる２つの文字列に整列順位を与えることができる。例えば、Ｊａｖａ（登録商標）言語における「ｓｔｒ０．ｃｏｍｐａｒｅＴｏ（ｓｔｒ１）」といったメソッド（関数）を用いると、この場合には変数ｓｔｒ０に格納されている文字列オブジェクトと、変数ｓｔｒ１に格納されている文字列オブジェクトとの間において、同一の場合を含めた大小関係（全順序関係）を得ることができ、これに基づき文字列の整列順位を特定することができる。
【００１５】
本発明は、このような文字列間の整列順位に着目し、ハッシュ値と対応付けて登録文字列を辞書に登録する際、同一ハッシュ値を有する複数の衝突登録文字列を当該ハッシュ値に対応する平衡２分探索木のノードとして登録しておき、検索時において、検索文字列の検索ハッシュ値に対応する平衡２分探索木が構築されている場合には、当該平衡２分探索木から検索文字列を探索することにより、辞書検索処理の簡素化および所要時間の短縮を実現するようにしたものである。
【００１６】
［辞書検索装置］
次に、本発明の一実施の形態について図面を参照して説明する。
まず、図１を参照して、本実施の形態にかかる辞書検索装置１０について説明する。図１は、辞書検索装置の構成を示すブロック図である。
この辞書検索装置１０は、全体としてサーバ装置などの情報処理装置からなり、外部から入力された検索指示に応じて、辞書１１に登録されている登録文字列を、これら登録文字列のハッシュ値に基づいて検索する機能を有している。
【００１７】
辞書検索装置１０には、主な機能部として、辞書１１、ハッシュ値計算部１２、辞書検索処理部１３、辞書探索処理部１４、および辞書登録処理部１５が設けられている。これら機能部のうち、ハッシュ値計算部１２、辞書検索処理部１３、辞書探索処理部１４、および辞書登録処理部１５については、ＣＰＵでプログラムを実行することにより実現してもよく、これらの一部をＦＰＧＡの論理回路で実現してもよい。
【００１８】
辞書１１は、ハードディスクや半導体メモリなどの記憶装置からなり、複数の登録文字列が電子化データに変換され、それぞれのハッシュ値と関連付けて登録されているデータベースである。図１では、辞書１１が辞書検索装置１０に設けられている場合を例として説明するが、これに限定されるものではない。例えば、通信回線を介して辞書検索装置１０に辞書１１を外部接続する構成であってもよい。
【００１９】
辞書１１には、主なデータ表として、ハッシュテーブル１１Ａと平衡２分探索木テーブル１１Ｂとが設けられている。
【００２０】
図２は、ハッシュテーブルの構成例である。ハッシュテーブル１１Ａには、登録文字列のハッシュ値Ｈごとに、登録文字列のうち当該ハッシュ値Ｈを有する唯一の登録文字列ＳＨ、または、登録文字列のうち当該ハッシュ値Ｈを共有する複数の衝突登録文字列をノードとする平衡２分探索木のうちルートノードを参照するための参照先ポインタ値ＰＨが登録されている。
【００２１】
本実施の形態は、辞書１１において、任意のハッシュ値Ｈに対して、当該ハッシュ値Ｈを持つ登録文字列ＳＨを１つしか登録していない場合、当該ハッシュ値Ｈを有する唯一の登録文字列ＳＨをハッシュテーブル１１Ａにのみ登録するようにしたものである。また、当該ハッシュ値Ｈを共有する複数の衝突登録文字列を辞書１１に登録する場合には、これら衝突登録文字列をハッシュテーブル１１Ａに登録するのではなく、平衡２分探索木テーブル１１Ｂに当該ハッシュ値Ｈに関する平衡２分探索木を形成し、この平衡２分探索木のノードとしてこれらの衝突登録文字列を連携させて登録するようにしたものである。
【００２２】
図３は、平衡２分探索木テーブルの構成例である。平衡２分探索木テーブル１１Ｂには、衝突登録文字列を識別するためのインデクス値Ｉごとに、当該インデクス値Ｉと対応する衝突登録文字列ＳＴ、規定の文字整列順序に従って当該衝突登録文字列ＳＴの直近上位に位置する衝突登録文字列のインデクス値を示す上位探索先ポインタ値ＰＵと、同じく規定の文字整列順序に従って当該衝突登録文字列ＳＴの直近下位に位置する衝突登録文字列のインデクス値を示す下位探索先ポインタ値ＰＬとが登録されている。
【００２３】
図４は、平衡２分探索木を示す説明図であり、図４（ａ）は規定の文字整列順序に基づく衝突登録文字列の順序関係を示し、図４（ｂ）は、平衡２分探索木のツリー構造を示している。
図３に示した各衝突登録文字列「com」,「com/foo」,「com/foo/mail」,「com/foo/map」,「com/foo/map/version1」,「com/foo/map/version2」は、アルファベット順という文字整列順序に基づいた場合、これら衝突登録文字列の整列順序は、図４（ａ）に示すように、「com」が最上位ノードとなり、「com/foo/map/version2」が最下位ノードとなる。
【００２４】
したがって、これら衝突登録文字列を平衡２分探索木で表した場合、図４（ｂ）に示すように、整列順序のうち中央に位置する「com/foo/map」がルートノードとなり、その直近上位ノードが「com/foo」でその直近下位ノードが「com/foo/map/version2」となる。また、「com/foo」の直近上位ノードが「com」でその直近下位ノードが「com/foo/mail」となる。また、「com/foo/map/version2」の直近上位ノードが「com/foo/map/version1」でその直近下位ノードが存在しない(null)となる。なお、平衡２分探索木の具体的な生成処理や更新処理については、非特許文献１など公知の技術を適用すればよい。
【００２５】
ハッシュ値計算部１２は、予め設定されているハッシュ関数に基づいて文字列に関するハッシュ値を計算する機能を有している。
【００２６】
辞書検索処理部１３は、入力された検索指示で指定された検索文字列のハッシュ値に基づいてハッシュテーブル１１Ａを検索し、当該ハッシュ値に対応する登録文字列が登録されている場合には、当該登録文字列の登録ありと判定する機能を有している。
【００２７】
辞書探索処理部１４は、入力された検索指示で指定された検索文字列のハッシュ値に対応する登録文字列がハッシュテーブル１１Ａに登録されていない場合には、当該ハッシュ値の参照先ポインタ値に基づいて平衡２分探索木テーブル１１Ｂを参照する機能と、当該参照先ポインタ値が示すインデクス値と対応する衝突登録文字列をルートノードとする平衡２分探索木のノードから、当該検索文字列と一致する衝突登録文字列を探索する機能と、得られた探索結果に応じて当該検索文字列の登録あり／なしを判定する機能と、当該参照先ポインタ値が登録されていない場合には、当該検索文字列の登録なしと判定する機能とを有している。
【００２８】
また、辞書探索処理部１４は、平衡２分探索木テーブル１１Ｂのうち参照先ポインタ値と対応するインデクス値に基づいて、検索文字列のハッシュ値に関する平衡２分探索木のルートノードを最初の探索ノードとして選択する機能と、選択した探索ノードの探索を行う際、当該探索ノードの衝突登録文字列が検索文字列と一致した場合には、当該検索文字列の登録ありと判定して探索を終了する機能と、当該衝突登録文字列が当該検索文字列と一致しない場合には、文字整列順序に応じた当該衝突登録文字列と当該検索文字列との順序位関係に基づき、当該インデクス値の上位探索先ポインタ値または下位探索先ポインタ値と対応するインデクス値のノードを新たな探索ノードとして選択して探索を繰り返す機能と、当該順序位関係に応じた当該上位探索先ポインタ値または当該下位探索先ポインタ値が登録されていない場合には、当該検索文字列の登録なしと判定する機能とを有している。
【００２９】
辞書登録処理部１５は、入力された登録指示で指定された指定文字列のハッシュ値に基づいてハッシュテーブル１１Ａを参照し、当該ハッシュ値に対応する登録文字列が登録されている場合には、当該登録文字列および当該指定文字列からなる衝突登録文字列を、文字整列順序に従って当該ハッシュ値に関する平衡２分探索木のノードとして平衡２分探索木テーブル１１Ｂに登録する機能と、当該平衡２分探索木のルートノードとなった衝突登録文字列のインデクス値を当該ハッシュ値の参照先ポインタ値としてハッシュテーブル１１Ａに登録するとともに、当該ハッシュ値の登録文字列をハッシュテーブル１１Ａから削除する機能とを有している。
【００３０】
また、辞書登録処理部１５は、指定文字列のハッシュ値に基づきハッシュテーブル１１Ａを参照し、当該ハッシュ値の登録文字列が登録されておらず当該ハッシュ値の参照先ポインタ値が登録されている場合には、当該指定文字列からなる衝突登録文字列を、文字整列順序に従って当該ハッシュ値に関する平衡２分探索木の新たなノードとして平衡２分探索木テーブル１１Ｂに追加登録する機能と、当該ハッシュ値に関する平衡２分探索木のルートノードとなった衝突登録文字列のインデクス値を当該ハッシュ値の参照先ポインタ値としてハッシュテーブル１１Ａに登録する機能と、当該ハッシュ値の登録文字列および参照先ポインタ値が登録されていない場合には、当該指定文字列を当該ハッシュ値の登録文字列としてハッシュテーブル１１Ａに登録する機能とを有している。
【００３１】
［本実施の形態の動作］
次に、本実施の形態にかかる辞書検索装置１０の動作として、辞書検索処理部１３による検索指示に応じたハッシュテーブル１１Ａでの辞書検索処理、辞書探索処理部１４による検索指示に応じた平衡２分探索木テーブル１１Ｂでの辞書探索処理、および辞書登録処理部１５による登録指示に応じたハッシュテーブル１１Ａおよび平衡２分探索木テーブル１１Ｂに対する辞書登録処理について、それぞれ別個に説明する。
【００３２】
［辞書検索処理］
まず、図５を参照して、辞書検索処理部１３での辞書検索処理について説明する。図５は、辞書検索処理を示すフローチャートである。
辞書検索処理部１３は、外部から入力された検索指示に応じて辞書１１を検索する際、当該検索指示で指定された検索文字列が辞書１１に登録されているか否かを確認する処理として、図５の辞書検索処理を実行する。
【００３３】
辞書検索処理部１３は、まず、検索指示で指定された検索文字列のハッシュ値である検索ハッシュ値をハッシュ値計算部１２により計算し（ステップ１００）、ハッシュテーブル１１Ａを参照して、検索ハッシュ値に対応する登録文字列の登録有無を確認する（ステップ１０１）。
【００３４】
ここで、検索ハッシュ値に対応する登録文字列がハッシュテーブル１１Ａに登録されている場合（ステップ１０１：ＹＥＳ）、辞書検索処理部１３は、その登録文字列と検索文字列とを比較し（ステップ１０２）、得られた比較結果すなわち一致／不一致に応じて、検索文字列の登録有無を判定して検索結果として出力し（ステップ１０３）、一連の辞書検索処理を終了する。
【００３５】
一方、検索ハッシュ値に対応する登録文字列がハッシュテーブル１１Ａに登録されていない場合（ステップ１０１：ＮＯ）、辞書検索処理部１３は、ハッシュテーブル１１Ａを参照して、検索ハッシュ値に対応する参照先ポインタ値の登録有無を確認する（ステップ１０４）。
【００３６】
ここで、検索ハッシュ値に対応する参照先ポインタ値がハッシュテーブル１１Ａに登録されている場合（ステップ１０４：ＹＥＳ）、辞書検索処理部１３は、辞書探索処理部１４に対して検索文字列に関する探索指示を出力し（ステップ１０５）、これに応じて辞書探索処理部１４から通知された探索結果すなわち平衡２分探索木テーブル１１Ｂにおける登録有無に基づいて、検索文字列の登録有無を判定して検索結果として出力し（ステップ１０６）、一連の辞書検索処理を終了する。
【００３７】
一方、検索ハッシュ値に対応する参照先ポインタ値がハッシュテーブル１１Ａに登録されていない場合（ステップ１０４：ＮＯ）、辞書検索処理部１３は、検索文字列の登録なしを検索結果として出力し（ステップ１０７）、一連の辞書検索処理を終了する。
【００３８】
これにより、ハッシュテーブル１１Ａの内容が前述した図２に示す状態にあり、検索文字列の検索ハッシュ値が「１」の場合、ハッシュ値Ｈ＝１に登録文字列ＳＨおよび参照先ポインタ値ＰＨが「（ｎｕｌｌ）」であり、いずれも未登録であることから、検索文字列の登録なしと判定される。
一方、検索文字列の検索ハッシュ値が「２」の場合、ハッシュ値Ｈ＝２に登録文字列ＳＨが登録されていることから、検索文字列の登録ありと判定される。
【００３９】
また、検索文字列の検索ハッシュ値が「３」の場合、ハッシュ値Ｈ＝２に登録文字列ＳＨが登録されておらず参照先ポインタ値が登録されていることから、当該参照先ポインタ値に基づいて、平衡２分探索木テーブル１１Ｂのうちハッシュ値Ｈ＝１と対応する平衡２分探索木が選択されて、平衡２分探索木において検索文字列の辞書探索処理が実行され、得られた探索結果に基づいて検索文字列の登録有無が判定される。
【００４０】
［辞書探索処理］
まず、図６を参照して、辞書探索処理部１４での辞書探索処理について説明する。図６は、辞書探索処理を示すフローチャートである。
辞書探索処理部１４は、辞書検索処理部１３からの探索指示に応じて平衡２分探索木テーブル１１Ｂを探索する際、当該探索指示で指定された検索文字列が平衡２分探索木テーブル１１Ｂに登録されているか否かを確認する処理として、図６の辞書探索処理を実行する。
【００４１】
辞書探索処理部１４は、まず、指定された検索文字列の検索ハッシュ値に対応する参照先ポインタ値からなるインデクス値に基づいて平衡２分探索木テーブル１１Ｂを参照し、検索ハッシュ値に関する平衡２分探索木のルートノードを最初の探索ノードとして選択する（ステップ１１０）。
【００４２】
続いて、辞書探索処理部１４は、探索ノードに対して衝突登録文字列が登録されているか確認し（ステップ１１１）、衝突登録文字列が登録されていない場合（ステップ１１１：ＮＯ）、探索結果として検索文字列の登録なしを出力し（ステップ１１８）、一連の辞書探索処理を終了する。
一方、衝突登録文字列が登録されている場合（ステップ１１１：ＹＥＳ）、辞書探索処理部１４は、当該衝突登録文字列と検索文字列とを比較する（ステップ１１２）。
【００４３】
ここで、衝突登録文字列と検索文字列とが一致した場合（ステップ１１２：ＹＥＳ）、辞書探索処理部１４は、探索結果として検索文字列の登録ありを出力し（ステップ１１９）、一連の辞書探索処理を終了する。
また、衝突登録文字列と検索文字列とが一致しない場合（ステップ１１２：ＮＯ）、辞書探索処理部１４は、規定の文字整列順序に基づいて衝突登録文字列と検索文字列との整列順を確認する（ステップ１１３）。
【００４４】
この際、検索文字列の整列順序が衝突登録文字列より上位である場合（ステップ１１３：ＹＥＳ）、辞書探索処理部１４は、探索ノードに対して上位探索先ポインタ値が登録されているか確認し（ステップ１１４）、上位探索先ポインタ値が登録されている場合には（ステップ１１４：ＹＥＳ）、その上位探索先ポインタ値が示すインデクス値に対応するノードを新たな探索ノードとして選択した後（ステップ１１５）、ステップ１１１へ戻って探索を繰り返し実施する。
【００４５】
一方、検索文字列の整列順序が衝突登録文字列より下位である場合（ステップ１１３：ＮＯ）、辞書探索処理部１４は、探索ノードに対して下位探索先ポインタ値が登録されているか確認し（ステップ１１６）、下位探索先ポインタ値が登録されている場合には（ステップ１１６：ＹＥＳ）、その下位探索先ポインタ値が示すインデクス値に対応するノードを新たな探索ノードとして選択した後（ステップ１１７）、ステップ１１１へ戻って探索を繰り返し実施する。
【００４６】
また、ステップ１１４において、上位探索先ポインタ値が登録されていない場合（ステップ１１４：ＮＯ）、並びに、ステップ１１６において、下位探索先ポインタ値が登録されていない場合（ステップ１１６：ＮＯ）、辞書探索処理部１４は、ステップ１１８へ移行して、探索結果として検索文字列の登録なしを出力し（ステップ１１８）、一連の辞書探索処理を終了する。
【００４７】
これにより、ハッシュテーブル１１Ａの内容が前述した図２に示す状態にあるとともに、平衡２分探索木テーブル１１Ｂの内容が前述した図３および図４に示す状態にあり、検索文字列が「com/foo/mail」であり、検索ハッシュ値が「５」の場合、参照先ポインタ値「４」に基づいて平衡２分探索木テーブル１１Ｂのうちハッシュ値＝５に対応する平衡２分探索木が参照され、平衡２分探索木における探索が開始される。
【００４８】
ハッシュ値＝５に対応する平衡２分探索木において、まず、インデクス値「４」のルートノードが探索ノードとして選択され、衝突登録文字列「comm/foo/map」と検索文字列「com/foo/mail」とが比較される。ここで、両者が不一致であり、図４（ａ）に示されているように、検索文字列の整列順が衝突登録文字列より上位であることから、当該探索ノードの上位探索先ポインタ値ＰＵ＝「２」に基づき、インデクス値「２」のノードが新たな探索ノードとして選択される。
【００４９】
インデクス値「２」の探索ノードでは、衝突登録文字列「comm/foo」と検索文字列「com/foo/mail」とが比較される。ここで、両者が不一致であり、図４（ａ）に示されているように、検索文字列の整列順が衝突登録文字列より下位であることから、当該探索ノードの下位探索先ポインタ値ＰＬ＝「３」に基づき、インデクス値「３」のノードが新たな探索ノードとして選択される。
【００５０】
インデクス値「３」の探索ノードでは、衝突登録文字列「comm/foo/mail」と検索文字列「com/foo/mail」とが比較される。ここで、両者が一致していることから、検索文字列の登録ありを示す探索結果が出力される。
【００５１】
［辞書登録処理］
次に、図７を参照して、辞書登録処理部１５での辞書登録処理について説明する。図７は、辞書登録処理を示すフローチャートである。
辞書登録処理部１５は、外部から入力された登録指示に応じて指定文字列を辞書１１に登録する際、図７の辞書登録処理を実行する。なお、平衡２分探索木テーブル１１Ｂに対する平衡２分探索木の新規登録、平衡２分探索木へのノード追加、規定の文字整列順序に基づく平衡２分探索木の平衡化処理など、平衡２分探索木に関する詳細処理については公知の技術を用いればよく、ここでの説明は省略する。
【００５２】
辞書登録処理部１５は、まず、登録指示で指定された指定文字列のハッシュ値である指定ハッシュ値をハッシュ値計算部１２により計算し（ステップ１２０）、ハッシュテーブル１１Ａを参照して、指定ハッシュ値に対応する登録文字列の登録有無を確認する（ステップ１２１）。
【００５３】
ここで、指定ハッシュ値に対応する登録文字列がハッシュテーブル１１Ａに登録されている場合（ステップ１２１：ＹＥＳ）、辞書登録処理部１５は、当該指定ハッシュ値に対応する平衡２分探索木を平衡２分探索木テーブル１１Ｂに新規登録し（ステップ１２２）、登録文字列および指定文字列からなる衝突登録文字列を当該平衡２分探索木のノードとして追加する（ステップ１２３）。
【００５４】
この後、辞書登録処理部１５は、当該平衡２分探索木のルートノードを示すインデクス値（ルートインデクス）を、指定ハッシュ値の参照先ポインタ値としてハッシュテーブル１１Ａに登録し（ステップ１２４）、指定ハッシュ値の登録文字列をハッシュテーブル１１Ａから削除し（ステップ１２５）、一連の辞書登録処理を終了する。
【００５５】
一方、ステップ１２１において、指定ハッシュ値に対応する登録文字列がハッシュテーブル１１Ａに登録されていない場合（ステップ１２１：ＮＯ）、辞書登録処理部１５は、指定ハッシュ値に対応する参照先ポインタ値がハッシュテーブル１１Ａに登録されているか否か確認する（ステップ１２６）。
【００５６】
ここで、指定ハッシュ値に対応する参照先ポインタ値がハッシュテーブル１１Ａに登録されている場合（ステップ１２６：ＹＥＳ）、辞書登録処理部１５は、当該参照先ポインタ値からなるインデクス値に基づいて平衡２分探索木テーブル１１Ｂを参照し、指定ハッシュ値に対応する平衡２分探索木の新たなノードとして、指定文字列からなる衝突登録文字列を追加するとともに当該平衡２分探索木を平衡化し（ステップ１２７）、当該平衡２分探索木のルートノードを示すインデクス値（ルートインデクス）を、指定ハッシュ値の参照先ポインタ値としてハッシュテーブル１１Ａに登録した後（ステップ１２８）、一連の辞書登録処理を終了する。
【００５７】
また、ステップ１２６において、指定ハッシュ値に対応する参照先ポインタ値がハッシュテーブル１１Ａに登録されていない場合（ステップ１２６：ＮＯ）、辞書登録処理部１５は、指定文字列を指定ハッシュ値に対応する登録文字列としてハッシュテーブル１１Ａに登録し（ステップ１２９）、一連の辞書登録処理を終了する。
【００５８】
これにより、ハッシュテーブル１１Ａの内容が前述した図２に示す状態にあり、指定文字列の検索ハッシュ値が「１」の場合、ハッシュ値Ｈ＝１に登録文字列ＳＨおよび参照先ポインタ値ＰＨが「（ｎｕｌｌ）」であり、未登録であることから、ハッシュ値Ｈ＝１の登録文字列ＳＨとして指定文字列が新規に登録される。
【００５９】
また、指定文字列の検索ハッシュ値が「２」の場合、ハッシュ値Ｈ＝２に登録文字列ＳＨが登録されていることから、ハッシュ値Ｈ＝１と対応する平衡２分探索木が平衡２分探索木テーブル１１Ｂに新規登録され、そのノードとしてハッシュ値Ｈ＝１に対応して登録されていた登録文字列と指定文字列からなる衝突登録文字列が、ハッシュ値Ｈ＝１と対応する平衡２分探索木のノードとして登録される。また、当該平衡２分探索木のルートノードを示すインデクス値がハッシュ値Ｈ＝２の参照先ポインタ値として登録され、ハッシュ値Ｈ＝２の登録文字列が削除されて「（ｎｕｌｌ）」となる。
【００６０】
また、指定文字列の検索ハッシュ値が「３」の場合、ハッシュ値Ｈ＝２に登録文字列ＳＨが登録されておらず参照先ポインタ値が登録されていることから、平衡２分探索木テーブル１１Ｂのうちハッシュ値Ｈ＝１と対応する平衡２分探索木の新たなノードとして、指定文字列の衝突登録文字列が登録される。また、必要に応じて、平衡２分探索木は平衡化され、更新されたルートノードのインデクス値が参照先のポインタ値として更新される。
【００６１】
［本実施の形態の効果］
このように、本実施の形態は、辞書１１として、ハッシュ値ごとに、登録文字列のうち当該ハッシュ値を有する唯一の登録文字列、または、登録文字列のうち当該ハッシュ値を共有する複数の衝突登録文字列をノードとする平衡２分探索木のうちルートノードを参照するための参照先ポインタ値が登録されているハッシュテーブル１１Ａと、衝突登録文字列と当該衝突登録文字列を識別するためのインデクス値とが、当該衝突登録文字列のハッシュ値に関する平衡２分探索木のノードとして、規定の文字整列順序に基づいて登録されている平衡２分探索木テーブル１１Ｂとを設け、辞書検索処理部１３が、検索指示で指定された検索文字列のハッシュ値に基づいてハッシュテーブル１１Ａを検索し、当該ハッシュ値に対応する登録文字列が登録されている場合には、当該検索文字列の登録ありと判定するようにしたものである。
【００６２】
また、辞書探索処理部１４が、検索文字列のハッシュ値に対応する登録文字列がハッシュテーブル１１Ａに登録されていない場合には、当該ハッシュ値の参照先ポインタ値に基づいて平衡２分探索木テーブル１１Ｂを参照し、当該参照先ポインタ値が示すインデクス値と対応する衝突登録文字列をルートノードとする平衡２分探索木のノードから、当該検索文字列と一致する衝突登録文字列を探索し、得られた探索結果に応じて当該検索文字列の登録あり／なしを判定し、当該参照先ポインタ値が登録されていない場合には、当該検索文字列の登録なしと判定するようにしたものである。
【００６３】
これにより、検索文字列を検索する際、検索ハッシュ値と同じハッシュ値を有する複数の衝突登録文字列については、ハッシュテーブル１１Ａとは別個の平衡２分探索木テーブル１１Ｂに設けられた、当該ハッシュ値に対応する平衡２分探索木を探索することになる。したがって、前述したように、線形リストに登録されている複数の登録文字列と検索文字列とを比較して同一性を逐次確認する場合と比較して、確認回数を大幅に削減でき、辞書検索処理の簡素化および所要時間の短縮を実現することが可能となる。
【００６４】
例えば、前述した従来技術において、１つの線形リストに登録されている文字列の平均登録数をＮとし、検索文字列が確率的に一様に分布するものとした場合、必要確認回数Ｘ１（期待値）は、次の式（１）で表される。
【数１】
2017091432.tif 000003
【００６５】
一方、本発明においては、１つのデータ構造が平衡２分探索木で構成されているため、１つのデータ構造に登録されている文字列の平均登録数Ｎに比較して、平衡２分探索木を探索して確認する必要確認回数Ｘ２を大幅に削減することができる。
例えば、データ構造が完全平衡な平衡２分探索木である場合、小数点以下を整数に切り上げる切り上げ関数ｃｅｉｌｉｎｇ（）を用いれば、平衡２分探索木の高さｍは、ｍ＝ｃｅｉｌｉｎｇ（ｌｏｇ２（Ｎ））で求められ、必要確認回数Ｘ２（期待値）は、このｍに依存した次の式（２）で表される。
【数２】
2017091432.tif 000004
【００６６】
図８は、衝突登録文字数と必要確認回数の関係を示すグラフである。衝突登録文字数Ｎの増加に応じて、線形リストを用いた場合の必要確認回数Ｘ１は線形関数的に増加するが、平衡２分探索木を用いた場合の必要確認回数Ｘ２は対数関数的に増加しており、衝突登録文字数Ｎが増加すればするほど、平衡２分探索木を用いたほうが必要確認回数は少なくて済むことが分かる。
したがって、本実施の形態によれば、ハッシュ法を用いた大規模な辞書に対して、同一ハッシュ値を有する衝突登録文字列が多数登録される場合であっても、指定された検索文字列を辞書から短時間で検索することが可能となる。
【００６７】
また、本実施の形態において、平衡２分探索木テーブル１１Ｂに、インデクス値ごとに、文字整列順序に従って衝突登録文字列の直近上位に位置する衝突登録文字列のインデクス値を示す上位探索先ポインタ値と、文字整列順序に従って当該衝突登録文字列の直近下位に位置する衝突登録文字列のインデクス値を示す下位探索先ポインタ値とを登録しておき、辞書探索処理部１４が、平衡２分探索木テーブル１１Ｂのうち参照先ポインタ値と対応するインデクス値に基づいて、検索文字列のハッシュ値に関する平衡２分探索木のルートノードを最初の探索ノードとして選択し、選択した探索ノードの探索を行う際、当該探索ノードの衝突登録文字列が検索文字列と一致した場合には、当該検索文字列の登録ありと判定して探索を終了し、当該衝突登録文字列が当該検索文字列と一致しない場合には、文字整列順序に応じた当該衝突登録文字列と当該検索文字列との順序位関係に基づき、当該インデクス値の上位探索先ポインタ値または下位探索先ポインタ値と対応するインデクス値のノードを新たな探索ノードとして選択して探索を繰り返し、当該順序位関係に応じた当該上位探索先ポインタ値または当該下位探索先ポインタ値が登録されていない場合には、当該検索文字列の登録なしと判定するようにしてもよい。
【００６８】
これにより、検索指示で指定された検索文字列の検索ハッシュ値に対して、複数の衝突登録文字列が存在し、これらが平衡２分探索木テーブル１１Ｂに構築された平衡２分探索木に登録されている場合でも、検索文字列に基づいて当該平衡２分探索木を簡素な処理で探索することができる。
【００６９】
また、本実施の形態において、入力された登録指示で指定された指定文字列のハッシュ値に基づいてハッシュテーブル１１Ａを参照し、当該ハッシュ値に対応する登録文字列が登録されている場合には、当該登録文字列および当該指定文字列からなる衝突登録文字列を、文字整列順序に従って当該ハッシュ値に関する平衡２分探索木のノードとして平衡２分探索木テーブル１１Ｂに登録し、当該平衡２分探索木のルートノードとなった衝突登録文字列のインデクス値を当該ハッシュ値の参照先ポインタ値としてハッシュテーブル１１Ａに登録するとともに、当該ハッシュ値の登録文字列をハッシュテーブル１１Ａから削除する辞書登録処理部１５をさらに備え、辞書登録処理部１５が、指定文字列のハッシュ値に基づきハッシュテーブル１１Ａを参照し、当該ハッシュ値の登録文字列が登録されておらず当該ハッシュ値の参照先ポインタ値が登録されている場合には、当該指定文字列からなる衝突登録文字列を、文字整列順序に従って当該ハッシュ値に関する平衡２分探索木の新たなノードとして平衡２分探索木テーブル１１Ｂに追加登録するとともに、当該ハッシュ値に関する平衡２分探索木のルートノードとなった衝突登録文字列のインデクス値を当該ハッシュ値の参照先ポインタ値としてハッシュテーブル１１Ａに登録し、当該ハッシュ値の登録文字列および参照先ポインタ値が登録されていない場合には、当該指定文字列を当該ハッシュ値の登録文字列としてハッシュテーブル１１Ａに登録するようにしてもよい。
【００７０】
これにより、入力された登録指示で指定された指定文字列を辞書１１に登録する場合、指定文字列の指定ハッシュ値と同一のハッシュ値を有する登録文字列がすでにハッシュテーブル１１Ａに登録されている場合であっても、さらには指定文字列の指定ハッシュ値と同一のハッシュ値を有する複数の衝突登録文字列がすでに平衡２分探索木テーブル１１Ｂの平衡２分探索木に登録されている場合であっても、指定文字列を対応する平衡２分探索木に対して適切に登録することができる。
【００７１】
［実施の形態の拡張］
以上、実施形態を参照して本発明を説明したが、本発明は上記実施形態に限定されるものではない。本発明の構成や詳細には、本発明のスコープ内で当業者が理解しうる様々な変更をすることができる。また、各実施形態については、矛盾しない範囲で任意に組み合わせて実施することができる。
【符号の説明】
【００７２】
１０…辞書検索装置、１１…辞書、１１Ａ…ハッシュテーブル、１１Ｂ…平衡２分探索木テーブル、１２…ハッシュ値計算部、１３…辞書検索処理部、１４…辞書探索処理部、１５…辞書登録処理部。
【図１】
2017091432.tif 000005
【図２】
2017091432.tif 000006
【図３】
2017091432.tif 000007
【図４】
2017091432.tif 000008
【図５】
2017091432.tif 000009
【図６】
2017091432.tif 000010
【図７】
2017091432.tif 000011
【図８】
2017091432.tif 000012