特許

J-GLOBAL ID：201703006594520404

辞書検索方法および装置

発明者： 青木 孝 ,  羽田野 孝裕 ,  大塚 卓哉 ,  宮崎 昭彦 ,  島▲崎▼ 健太 ,  戸川 望 ,  朴 容震 ,  津田 俊隆
出願人/特許権者： 日本電信電話株式会社 ,  学校法人早稲田大学
代理人 (3件)： 山川 政樹 ,  山川 茂樹 ,  小池 勇三
公報種別：公開公報
出願番号（国際出願番号）：特願2015-224490
公開番号（公開出願番号）：特開2017-091432
出願日： 2015年11月17日
公開日（公表日）： 2017年05月25日
要約：

【課題】多数の衝突登録文字列が登録されていても短時間で検索文字列を検索する。【解決手段】ハッシュ値ごとに、登録文字列のうち当該ハッシュ値を有する唯一の登録文字列、または、登録文字列のうち当該ハッシュ値を共有する複数の衝突登録文字列をノードとする平衡2分探索木のうちルートノードを参照するための参照先ポインタ値が登録されているハッシュテーブル11Aと、衝突登録文字列と当該衝突登録文字列を識別するためのインデクス値とが、当該衝突登録文字列のハッシュ値に関する平衡2分探索木のノードとして、規定の文字整列順序に基づいて登録されている平衡2分探索木テーブル11Bとを辞書11に設け、検索時において、検索文字列の検索ハッシュ値に対応する平衡2分探索木が構築されている場合には、辞書探索処理部14により、対応する平衡2分探索木から検索文字列を探索する。【選択図】 図1

請求項（抜粋）：

入力された検索指示に応じて、辞書に登録されている登録文字列を、これら登録文字列のハッシュ値に基づいて検索する辞書検索方法であって、 前記辞書は、前記ハッシュ値ごとに、前記登録文字列のうち当該ハッシュ値を有する唯一の登録文字列、または、前記登録文字列のうち当該ハッシュ値を共有する複数の衝突登録文字列をノードとする平衡2分探索木のうちルートノードを参照するための参照先ポインタ値が登録されているハッシュテーブルと、前記衝突登録文字列と当該衝突登録文字列を識別するためのインデクス値とが、当該衝突登録文字列のハッシュ値に関する平衡2分探索木のノードとして、規定の文字整列順序に基づいて登録されている平衡2分探索木テーブルとを有し、 前記検索指示で指定された検索文字列のハッシュ値に基づいて前記ハッシュテーブルを検索し、当該ハッシュ値に対応する登録文字列が登録されている場合には、当該検索文字列の登録ありと判定する辞書検索処理ステップと、 前記検索文字列のハッシュ値に対応する登録文字列が前記ハッシュテーブルに登録されていない場合には、当該ハッシュ値の参照先ポインタ値に基づいて前記平衡2分探索木テーブルを参照し、当該参照先ポインタ値が示す前記インデクス値と対応する前記衝突登録文字列をルートノードとする前記平衡2分探索木のノードから、当該検索文字列と一致する衝突登録文字列を探索し、得られた探索結果に応じて当該検索文字列の登録あり/なしを判定し、当該参照先ポインタ値が登録されていない場合には、当該検索文字列の登録なしと判定する辞書探索処理ステップと を備えることを特徴とする辞書検索方法。

IPC (1件)：

G06F 17/30

FI (2件)：

G06F17/30 170J ,  G06F17/30 412