特許

J-GLOBAL ID：201803003235177727

辞書検索方法、装置、およびプログラム

発明者： 右近 祐太 ,  宮崎 昭彦 ,  島▲崎▼ 健太 ,  多和田 雅師 ,  津田 俊隆 ,  中里 秀則 ,  戸川 望
出願人/特許権者： 日本電信電話株式会社 ,  学校法人早稲田大学
代理人 (3件)： 山川 茂樹 ,  小池 勇三 ,  山川 政樹
公報種別：公開公報
出願番号（国際出願番号）：特願2016-224819
公開番号（公開出願番号）：特開2018-081611
出願日： 2016年11月18日
公開日（公表日）： 2018年05月24日
要約：

【課題】辞書を検索する際に要する検索時間を短縮する。【解決手段】登録文字列の区分数に対応して設けられた複数のハッシュテーブル11Bと1または複数の平衡2分探索木テーブル11Cとを辞書11に設け、辞書検索時には、検索処理部13が、検索文字列の区分数に対応するハッシュテーブル11Bを選択して、検索文字列の検索ハッシュ値に基づき当該ハッシュテーブル11Bを検索し、検索文字列の検索ハッシュ値に対応する平衡2分探索木が構築されている場合には、辞書探索処理部14が、平衡2分探索木テーブル11Cのうち対応する平衡2分探索木から検索文字列を探索する。【選択図】 図1

請求項（抜粋）：

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

IPC (1件)：

G06F 17/30

FI (2件)：

G06F17/30 412 ,  G06F17/30 419A