JP2010086472A - クエリ候補提示装置 - Google Patents

Abstract

【課題】画面サイズ、検索対象データの読みの偏り等に応じた適切なクエリ候補を提示することで、ユーザの検索用キーワードの入力効率を向上させることを目的とする。
【解決手段】検索対象データ１０２に基づいて生成された読みトライ構造索引から、クエリ候補抽出部１０６がクエリ候補の文字列を抽出する。スコア計算部１０７は、クエリ候補を提示することによって節約できる打鍵数、ユーザのクエリ候補選択後に残りの文字列を入力するときに予測される打鍵数削減を示す確定後スコア、一画面に表示できる項目数等を考慮して、クエリ候補のスコアを計算する。クエリ候補選択部１０９がスコアに応じたクエリ候補を登録してクエリ候補辞書１０３を生成する。入力部１１２を介してユーザから検索用キーワードの読み文字列が一文字ずつ入力されると、クエリ候補表示部１１３がクエリ候補辞書１０３を参照して読み文字列に応じたクエリ候補を提示する。
【選択図】図１

Description

この発明は、数文字の読みを入力すると検索用キーワードの候補を提示するクエリ候補提示装置に関するものである。

近年、各種の電子機器の高機能化が進み、電子マニュアル等を機器上で閲覧および検索したいというニーズが高まっている。また、環境問題の側面からも、従来の紙の説明書を電子化したいというニーズが大きい。
しかしながら、カーナビゲーション装置およびＦＡ用表示器等のキーボードをもたない機器では、検索用キーワードの入力がしにくく操作の手間がかかるため、機器上の電子化文書を充分に活用できないという問題があった。

そこで、この問題を解決するために、特許文献１では入力操作の手間を軽減するための技術が提案されている。特許文献１に開示の文字列予測装置は、ユーザが入力した文字に基づいて、ユーザが入力しようとする所望の文字列を予測するものである。この文字列予測装置は、ユーザが候補リストの中から候補文字列を選択するために必要な第１操作コストと、ユーザが次の文字を入力することによって絞り込まれる候補文字列を選択するために必要な第２操作コストとを比較し、第１操作コストが第２操作コストよりも大きい候補文字列を候補リストから除外して不要な候補文字列の提示を減らすことにより、入力効率を高めていた。

特開２００８−４６７７５号公報

従来の文字列予測装置は以上のように構成されているので、第１操作コストが第２操作コストよりも大きい候補文字列を候補リストから削除するのみであるため、削除されない候補文字列が多数存在する場合には、結局入力に手間がかかってしまうという課題があった。

また、候補リストに大量の候補文字列が存在する場合には、候補文字列をグループ化して階層的に入力することができないため、ユーザに提示する候補数が多くなってしまうという課題があった。

さらに、一画面に表示可能な候補数が限られている機器に対して、表示可能な候補数を考慮したコスト計算がなされていないため、対象機器または対象画面に対して個別に適切な候補文字列の提示を行うことができないという課題があった。

この発明は、上記のような課題を解決するためになされたもので、画面サイズ、検索対象データの読みの偏り等に応じた適切なクエリ候補を提示することができ、ユーザの検索用キーワードの入力効率を向上させることを目的とする。

この発明に係るクエリ候補提示装置は、一文字ずつ入力される検索用キーワードの読み文字で始まるクエリ候補をクエリ候補辞書から取得して、当該検索用キーワードの候補として提示するクエリ候補表示部を備えるクエリ候補提示装置であって、検索対象データから抽出された語句を当該語句の読み文字に基づいて階層構造化したデータから、クエリ候補となる文字列を抽出するクエリ候補抽出部と、検索用キーワードの読み文字で始まる文字列をクエリ候補とすることによって得られる当該検索用キーワードの入力手間軽減の効果を示すスコアを計算するスコア計算部と、検索対象データから抽出された語句の読み文字毎に、スコア計算部で計算されたスコアに基づいて文字列をクエリ候補としてクエリ候補辞書に登録するクエリ候補選択部とを備えるようにしたものである。

この発明によれば、階層構造化したデータからクエリ候補となる文字列を抽出し、検索用キーワードの読み文字で始まる文字列をクエリ候補とすることによって得られる当該検索用キーワードの入力手間軽減の効果を示すスコアを計算して、検索対象データから抽出された語句の読み文字毎にスコアに基づいて文字列をクエリ候補としてクエリ候補辞書に登録するようにしたので、画面サイズ、検索対象データの読みの偏り等に応じた適切なクエリ候補を提示することができ、ユーザの検索用キーワードの入力効率を向上できる。

実施の形態１．
図１は、この発明の実施の形態１に係るクエリ候補提示装置の構成を示すブロック図である。本実施の形態のクエリ候補提示装置は、検索対象データ１０２をもとにクエリ候補辞書１０３を生成するクエリ候補辞書生成部１０１と、ユーザによって読みが一文字ずつ入力されると、その読みで始まる検索用キーワードの候補、即ちクエリ候補をクエリ候補辞書１０３から選択して提示するクエリ候補提示部１１０とから構成される。

先ず、クエリ候補辞書生成部１０１を説明する。クエリ候補辞書生成部１０１は、検索対象データ１０２を解析してクエリ候補の対象とすべき重要語句を抽出する重要語句抽出部１０４、抽出した重要語句を読みで構造化した読みトライ構造索引を生成するトライ構造索引生成部１０５、読みトライ構造索引からクエリ候補にする文字列を抽出するクエリ候補抽出部１０６、抽出したクエリ候補のスコアを計算するスコア計算部１０７、スコアに基づき最適なクエリ候補の組合わせを選択してクエリ候補辞書データを生成するクエリ候補選択部１０９を備える。
なお、クエリ候補提示装置は、検索対象データ１０２として施設名、説明書等のデータを用いる。

重要語句抽出部１０４は、検索対象データ１０２を解析し、フォントサイズ等の画面レイアウト情報および章節構造等の文書構造情報等を手掛りに、クエリ候補とすべき重要な語句を抽出する。この処理は、例えば特開２００１−５２０３２号公報の「要約文作成方法及び装置及び要約文作成プログラムを格納した記憶媒体」等、公知の技術を用いて実現可能であるので、詳細な説明は省略する。
図２は、重要語句抽出部１０４がクエリ候補として抽出した重要語句の例を示す説明図である。重要語句抽出部１０４はクエリ候補となる重要語句を検索対象データ１０２から抽出して見出しとし、この見出しを単語毎に区切った単語区切り、およびこの見出しの読みを単語毎に区切った読み区切りの情報を生成する。そして、重要語句抽出部１０４は少なくともこれら３種類の情報を重要語句データに含めてトライ構造索引生成部１０５へ出力する。なお、重要語句データには、これら３種類の情報の他に、語句の重要度を示す情報等を含めてもよい。

トライ構造索引生成部１０５は見出し、単語区切りおよび読み区切りの情報をもつ重要語句データを入力として、各重要語句の読みを木構造として整理した読みトライ構造索引を生成する。
図３は、トライ構造索引生成部１０５が生成した読みトライ構造索引を示す説明図である。図３では、図２に示す１４個の重要語句を用いて生成された読みトライ構造索引を示す。読みトライ構造は、各重要語句の読みをノードＮ_xとし、ルートノードＮ_rを基点にして読みのうちの先頭一致する共通部分を木構造としてまとめあげて階層構造化したデータであり、自然言語処理における辞書検索処理等で多用される公知のデータ構造である。
同データ構造の高速な実装方式としてダブル配列（「ダブル配列におけるキー削除の効率化手法」情報処理学会自然言語処理研究会、Ｖｏｌ．２００３ Ｎｏ．２３ ２００２−ＮＬ−１５４）がよく知られており、トライ構造索引生成部１０５がダブル配列によって読みトライ構造索引データを生成してもよい。

クエリ候補抽出部１０６は読みトライ構造索引データを入力とし、クエリ候補選択条件１０８に従って、読みトライ構造索引からクエリ候補辞書１０３に登録するクエリ候補をノード毎に抽出する。具体的には、図３に示す読みトライ構造索引の各ノードＮ_xに対して、ノードＮ_xの子孫ノードＮ_yのうちの単語区切りの末端であるノードを全て抽出し、ルートノードＮ_rから子孫ノードＮ_yに至る各ノードに対応する読みをつなげた語句を、クエリ候補とする。ただし、図３の読みトライ構造索引は、説明を簡便にするために図を簡略化してあるため、単語区切りの末端であるノードを区別して示してはいない。

検索対象データ１０２が大規模なデータである場合には、クエリ候補選択条件１０８として「子孫ノードＮ_yはノードＮ_xからＷ単語以内に限定」、「子孫ノードＮ_yはノードＮ_xからＬ文字以内に限定」、「子孫ノードＮ_yはノードＮ_xからの経路における分岐数をＢ個以内に限定」等の条件を指定しておくことにより、クエリ候補抽出部１０６によるクエリ候補抽出のための探索範囲を限定することができる。

ここで、ノード間のショートカットについて説明する。クエリ候補辞書生成部１０１では、読みトライ構造索引の各ノードに対して、ノードＮ_xからこのノードＮ_xの子孫ノードＮ_y中のショートカット先のノードであるショートカットノードＮ_iへ、ノード間をショートカットするリンクを生成する。
図４は、読みトライ構造索引のショートカットを示す説明図である。例えば検索用キーワードの読み「とうきょうこ」が入力された場合、即ちルートノードＮ_rからノードＮ６に注目ノードが遷移した状態（以下、読みＮ_r〜Ｎ６と呼ぶ）のとき、詳細は後述するが、クエリ候補提示装置は「東京国際空港第一」、「東京国際空港第二」、「東京国際空港第三駐車場」をクエリ候補としてユーザに提示する。例えば「東京国際空港第一」というクエリ候補は、ユーザが入力した読み「とうきょうこ」の「こ」に対応するノードＮ６からノードＮ１７へノード間をショートカットしたものといえる。
ユーザによりこれらのクエリ候補の中から「東京国際空港第一」が選択されると、クエリ候補提示装置は注目ノードをＮ６からショートカット先のノードＮ１７に遷移させて（以下、ショートカットＮ６→Ｎ１７と呼ぶ）、ショートカット経路中のノードＮ７，Ｎ８，・・・，Ｎ１６に対応する読みを自動的に表示し、ユーザの入力手間を軽減させる。

スコア計算部１０７はクエリ候補のデータを入力とし、検索用キーワード入力途中の読みに対応するクエリ候補を提示することによって得られる入力手間軽減の効果を定式化したスコアを、クエリ候補選択条件１０８に従って計算する。そして、スコア計算部１０７はクエリ候補に関するスコアデータをクエリ候補選択部１０９へ出力する。
スコア計算部１０７へ入力されるクエリ候補選択条件１０８として、一画面あたりに表示可能なクエリ候補数を示す最大表示候補数Ｄ_maxがある。

図５は、スコア計算部１０７の詳細構成を示すブロック図である。スコア計算部１０７は、打鍵数短縮スコア計算部１１、確定後スコア計算部１２、スコア集計部１３を備える。また、図６は、スコア計算部１０７が用いるスコアの定義を示す説明図である。
図５に示す打鍵数短縮スコア計算部１１は、読みＮ_r〜Ｎ_xに対応するクエリ候補（「読みＮ_r〜Ｎ_x」＋「ショートカットＮ_x→Ｎ_i」に対応する読みをつなげた語句）の打鍵数短縮スコアＣ₁（Ｎ_x，Ｎ_i）を計算する。打鍵数短縮スコアは、ユーザが検索用キーワードの読み入力途中で提示されたクエリ候補を選択することによって、クエリ候補の読みを入力する場合と比較して何回少ない打鍵数で同じクエリ候補を入力できるかを示す。

図７は、スコア計算部１０７のスコア計算例を示す説明図であり、読みとして「とうきょうとり」（読みＮ_r〜Ｎ６６）が入力された場合のスコアを示す。図７では、クエリ候補選択条件１０８の最大表示候補数Ｄ_maxは３と定義する。
ここで、図７に示す打鍵数短縮スコアＣ₁（Ｎ６６，Ｎ_i）について、図４および図６を用いて説明する。読みＮ_r〜Ｎ６６に対応するショートカットＮ６６→Ｎ７１のクエリ候補「東京都立第一」の場合、Ｎ６６→Ｎ７１の経路途中にあるノードＮ_jのうち、葉の数（「ちゅうがく」および「こうこう」）がＤ_max以下、かつ、Ｄｅｐｔｈ（Ｎ_j）が最小となるノードＮ_zはＮ７０である。よって、「東京都立第一」の打鍵数短縮スコアＣ₁（Ｎ６６，Ｎ７１）は、Ｎ_zが存在する場合の計算式から「６」となる。
他方、読みＮ_r〜Ｎ６６に対応するショートカットＮ６６→Ｎ８１のクエリ候補「東京都立第二」の場合、Ｎ６６→Ｎ８１の経路途中に葉の数がＤ_max以下となるノードＮ_zが存在しない。よって、「東京都立第二」の打鍵数短縮スコアＣ₁（Ｎ６６，Ｎ８１）は、Ｎ_zが存在しない場合の計算式から「６」となる。
打鍵数短縮スコア計算部１１は、ノードＮ６６に対応するショートカットのクエリ候補「東京都立第三」および「東京都立産業」についても上記同様に打鍵数短縮スコアを計算する。

図５に示す確定後スコア計算部１２は、読みＮ_r〜Ｎ_xに対応するショートカットＮ_x→Ｎ_iのクエリ候補がユーザによって選択され、検索用キーワードの一部であることが確定した場合に、このクエリ候補に続く次のショートカットＮ_i→Ｎ_iiに対応したクエリ候補の打鍵数削減効果を予測して確定後スコアＣ₂（Ｎ_i）とする。ここで、Ｎ_iiは、ショートカットノードＮ_iを基点にしたときのショートカット先のノードである。

図８は、確定後スコア計算部１２の確定後スコア計算例を示す説明図であり、クエリ候補として「東京国際空港」が選択された場合を示す。クエリ候補「東京国際空港」のショートカットノードＮ１３を新たな基点のノードと仮定した場合の次のショートカットノードＮ_iiは例えばＮ１７、Ｎ３１，Ｎ５４，Ｎ６４がある。このとき、次のショートカットＮ_i→Ｎ_iiの組合わせは、Ｎ１３→Ｎ１７，Ｎ１３→Ｎ４１，Ｎ１３→Ｎ５４，Ｎ１３→Ｎ６４である。確定後スコア計算部１２は、これらショートカットの組合わせのスコアＳ_c（Ｎ_i，｛Ｎ_y｝）を計算する。ここで、｛Ｎ_y｝は次のショートカットノードＮ_iiの集合を表しており、要素数はクエリ候補選択条件１０８で定義される一画面あたりの最大表示候補数Ｄ_max以下とする。またスコアＳ_cについては後述する。
Ｎ_iに対する次のショートカットノードＮ_iiがＤ_max以上存在すると、ショートカットＮ_i→Ｎ_iiの組合わせも多数存在する。そのような場合には、確定後スコア計算部１２がそれら多数のショートカットＮ_i→Ｎ_iiのクエリ候補をＤ_max以下ずつ組合わせたスコアＳ_c（Ｎ_i，｛Ｎ_y｝）を計算し、そのうち最大のもの（Ｍａｘ（Ｓ_c（Ｎ_i，｛Ｎ_y｝））をショートカットノードＮ_iの確定後スコアＣ₂（Ｎ_i）とする。

図８の確定後スコア計算例では、｛Ｎ_y｝の選び方の代表例としてパターン８Ａおよび８Ｂの２種類を示す。パターン８Ａは、ショートカットＮ１３→Ｎ１７，Ｎ１３→Ｎ４１，Ｎ１３→Ｎ５４の組合わせを示し、パターン８Ｂはその組合わせをＮ１３→Ｎ１７，Ｎ１３→Ｎ５４，Ｎ１３→Ｎ６４にした場合を示す。確定後スコア計算部１２は、各パターンのスコアＳ_c（Ｎ１３，｛Ｎ_y｝）を比較して、最大となるパターン８Ａのスコアを、クエリ候補「東京国際空港」（ノードＮ１３）に対応する確定後スコアＣ₂（Ｎ１３）とする。

図７のスコア計算例では、「東京都立第一」等のクエリ候補に対して次のショートカットノードＮ_iiを考えた場合、いずれのショートカットノードＮ_iiでもクエリ候補数が最大表示候補数Ｄ_max以下となる。確定後スコア計算部１２は、図６に示す定義に従えば、確定後スコアＣ₂（Ｎ７１）はスコアＳ_c（Ｎ７１，｛Ｎ_y｝）で与えられるが、この場合はノードＮ_zがＮ７１となるため、打鍵数短縮スコアＣ₁（Ｎ７１，Ｎ_ii）はいずれも０となる。そのため、Ｄ_max個以下の次のショートカットノードＮ_iiについてのＣ₁（Ｎ７１，Ｎ_ii）を加算したものである、クエリ候補「東京都立第一」の確定後スコアＣ₂（Ｎ７１）も０となる。

図５に示すスコア集計部１３は、打鍵数短縮スコア計算部１１が計算した打鍵数短縮スコアと確定後スコア計算部１２が計算した確定後スコアを用いて各クエリ候補のショートカットスコアＳ_e（Ｎ_x，Ｎ_y）を計算し、ショートカットスコアを用いて各クエリ候補の組合わせに応じたスコアＳ_c（Ｎ_x，｛Ｎ_y｝）を計算する。｛Ｎ_y｝はショートカットノードＮ_iの集合を表しており、要素数は最大表示候補数Ｄ_max以下とする。

図７のスコア計算例では、｛Ｎ_y｝の選び方の代表例としてパターン７Ａおよび７Ｂの２種類を示す。パターン７Ａは、読みＮ_r〜Ｎ６６に対して、一画面あたりに表示するクエリ候補の組合わせを「東京都立第一」、「東京都立第二」および「東京都立第三」にした場合を示し、パターン７Ｂはその組合わせを「東京都立第一」、「東京都立第二」および「東京都立産業」にした場合を示す。スコア集計部１３は、ショートカットにより入力を効率化できる葉の数Ｌ_zが同一であれば、ショートカットにより短縮できる読みの長さ（Ｄｅｐｔｈ（Ｎ_z）−Ｄｅｐｔｈ（Ｎ_x）およびＤｅｐｔｈ（Ｎ_i）−Ｄｅｐｔｈ（Ｎ_x））がより大きいパターン７Ａに高いスコアを与える。
従来技術ではクエリ候補の提示により短縮できる読みの長さに応じてクエリ候補間の優先順位を決定することができなかったため、これらのパターン７Ａおよび７Ｂに優劣をつけられず、表示候補数を適切な３種類に絞り込むことができなかった。これに対して、本実施の形態では最大表示候補数Ｄ_maxに応じてクエリ候補を優先させることができる。
なお、同一パターン内のクエリ候補間の優劣は、ショートカットスコアに準じればよく、高いショートカットスコアのクエリ候補を優先させる。

図９は、スコア計算部１０７のスコア計算例を示す説明図であり、読みとして「とうきょうこ」（読みＮ_r〜Ｎ６）が入力された場合のスコアを示す。図９においても、クエリ候補選択条件１０８の最大表示候補数Ｄ_maxは３と定義する。パターン９Ａは、読みＮ_r〜Ｎ６に対して、クエリ候補の組合わせを「東京国際空港第一」、「東京国際空港第二」および「東京国際空港第三駐車場」にした場合を示し、パターン９Ｂはその組合わせを「東京国際空港第一」、「東京国際空港第三駐車場」および「東京国際空港第四駐車場」とした場合を示す。この例では、スコア集計部１３は、ショートカットにより短縮できる読みの長さ（Ｄｅｐｔｈ（Ｎ_z）−Ｄｅｐｔｈ（Ｎ_x）およびＤｅｐｔｈ（Ｎ_i）−Ｄｅｐｔｈ（Ｎ_x））が同一であれば、葉の数Ｌ_zがより多いパターン９Ａに高いスコアを与える。
従来技術では葉の数を考慮したスコア計算をしていなかったため、これらのパターン９Ａおよび９Ｂに優劣をつけられず、表示候補数を適切な３種類に絞り込むことができなかった。これに対して、本実施の形態ではより多くの葉を含むクエリ候補を優先させることができる。

また、図１０に、確定後スコアがスコアに寄与する例を示す。図１０は、スコア計算部１０７のスコア計算例を示す説明図であり、読みとして「とうきょう」（読みＮ_r〜Ｎ５）が入力された場合のスコアを示す。パターン１０Ａではクエリ候補数が最大表示候補数Ｄ_maxに満たないにもかかわらず、パターン１０Ａとパターン１０Ｂのスコアは同値となる。これは、スコア集計部１３が確定後スコアを考慮してスコアを計算したことにより、ユーザによりクエリ候補が選択された後に予測される打鍵数節減の効果をスコアに反映したためである。
ここで、パターン１０Ａおよび１０Ｂにおけるクエリ候補「東京国際空港」の確定後スコアＣ₂（Ｎ１３）は、図８において確定後スコア計算部１２が計算した確定後スコアである。この確定後スコアは、パターン８ＡのスコアＳ_c（Ｎ１３，｛Ｎ１７，Ｎ３１，Ｎ５４｝）に相当する。

また、上記のようなスコア計算部１０７のスコア計算により、読みトライ構造索引において木構造が偏った部分についても、検索対象データ１０２および最大表示候補数Ｄｍａで定義される画面の大きさに応じた適切なクエリ候補選択が可能となる。例えば、図１１に最大表示候補数Ｄ_maxを５と定義した場合のスコア計算部１０７のスコア計算例を示す。ここでは読みとして「とうきょうとり」（読みＮ_r〜Ｎ６６）が入力されたときの、｛Ｎ_y｝の組合わせの代表例としてパターン１１Ａおよび１１Ｂの各スコアを示す。この例では、スコア集計部１３は、より広い範囲の葉をカバーできるパターン１１Ｂを優先して高いスコアを与える。

図１のクエリ候補選択部１０９は、クエリ候補選択条件１０８の最大表示候補数Ｄ_maxとスコアデータを入力とし、スコアＳ_c（Ｎ_x，｛Ｎ_y｝）に基づいてスコアが最大となるクエリ候補の組合わせを選択して、ショートカット情報を生成する。クエリ候補選択部１０９は、生成したショートカット情報を、重要語句抽出部１０４で抽出された重要語句データと、トライ構造索引生成部１０５で生成された読みトライ構造索引データとをあわせてクエリ候補辞書データを生成し、クエリ候補辞書１０３へ登録する。

図１２は、クエリ候補提示装置のクエリ候補辞書１０３の構成を示すブロック図であり、クエリ候補辞書１０３は、見出し一覧２１、読みトライ構造索引２２およびショートカット情報２３を備える。図１３にクエリ候補辞書１０３に登録された見出し一覧２１の例を示し、図１４にクエリ候補辞書１０３に登録されたショートカット情報２３の例を示す。読みトライ構造索引２２の例は図３および図４に示す。

図１３の見出し一覧２１は、読みトライ構造索引２２およびショートカット情報２３等の他データから参照するためのレコード番号およびクエリ候補としてユーザに提示される見出しからなる。
図１４のショートカット情報２３ａ，２３ｂ，２３ｃは、ノードＮ_xに対するショートカットの情報をリスト情報で表現している。リストの要素は（ア）〜（エ）からなり、それぞれ、「（ア）リストの次要素へのポインタ」、「（イ）ショートカットノードＮ_i」、「（ウ）見出し一覧を参照するレコード番号」、「（エ）ショートカットスコアＳ_e（Ｎ_x，Ｎ_y）」である。

クエリ候補選択部１０９は、スコア計算部１０７で計算されたノードＮ_xに対するクエリ候補の全組合わせからスコアが最大となるクエリ候補の組合わせを選択し、それらクエリ候補のショートカットに関する情報を図１４に示すようにノードＮ_xにリンクさせる。図１４ではノードＮ６にリンクするショートカット情報を示しているが、このショートカット情報は図９のパターン９Ａの組合わせに相当する。

図１５は、実施の形態１に係るクエリ候補提示装置のクエリ候補辞書生成部１０１の動作を示すフローチャートである。以下、図１〜図１５を適宜用いて、クエリ候補辞書生成部１０１の動作を説明する。
ステップＳＴ１は重要語句抽出処理であり、重要語句抽出部１０４が検索対象データ１０２を解析して、画面レイアウト情報および文書構造情報等を利用して重要語句を抽出すると共に、単語分割および読み付与を実行する。そして、重要語句抽出部１０４は図２に示す重要語句データをトライ構造索引生成部１０５へ出力する。

ステップＳＴ２はトライ構造索引生成処理であり、トライ構造索引生成部１０５がステップＳＴ１で抽出された重要語句の情報を用いて、図３に示す読みトライ構造索引を生成する。そして、トライ構造索引生成部１０５は読みトライ構造索引データをクエリ候補抽出部１０６へ出力する。
ステップＳＴ３はクエリ候補抽出処理であり、クエリ候補抽出部１０６はクエリ候補選択条件１０８およびステップＳＴ２で生成された読みトライ構造索引を用いて、クエリ候補辞書１０３に登録するためのクエリ候補を全て抽出する。そして、クエリ候補抽出部１０６は生成したクエリ候補データをスコア計算部１０７へ出力する。

ステップＳＴ４はスコア計算処理であり、スコア計算部１０７が、ステップＳＴ３で抽出された各クエリ候補に対するスコアを計算する。クエリ候補毎に、打鍵数短縮スコア計算部１１が打鍵数短縮スコアを計算し、確定後スコア計算部１２が確定後スコアを計算する。そして、スコア集計部１３が打鍵数短縮スコアおよび確定後スコアを用いて、クエリ候補の組合わせ毎にスコアを計算し、クエリ候補選択部１０９へスコアデータを出力する。

ステップＳＴ５はクエリ候補選択処理であり、ステップＳＴ４で計算されたスコアデータを用いて、クエリ候補選択部１０９がスコアが最大となるクエリ候補の組合わせを選択し、図１２〜図１４に示す見出し一覧２１、読みトライ構造索引２２およびショートカット情報２３を含むクエリ候補辞書データを生成してクエリ候補辞書１０３へ登録する。
全てのノードについて同様のスコア計算が行われ、各ノードに対してスコア最大となるクエリ候補の組合わせが登録されると（ステップＳＴ６“Ｙｅｓ”）、クエリ候補辞書生成処理は終了する。クエリ候補の組合わせが決まっていないノードが存在しているうちは、処理はステップＳＴ３のクエリ候補抽出処理へ戻り（ステップＳＴ６“Ｎｏ”）、クエリ候補抽出部１０６が次のノードに対応するクエリ候補を抽出する。

次に、クエリ候補提示部１１０を説明する。図１に示すクエリ候補提示部１１０は、クエリ候補辞書生成部１０１で生成したクエリ候補辞書１０３、ユーザが入力した検索用キーワードの読み文字列１１１を受け付ける入力部１１２、検索用キーワードの読み文字列１１１をもとにクエリ候補辞書１０３を参照して次のクエリ候補を表示するクエリ候補表示部１１３を備える。
なお、検索用キーワードの読み文字列１１１は、ユーザが入力した検索用キーワードの読み文字列、またはクエリ候補表示部１１３で表示したクエリ候補に対するユーザの選択結果である。入力はタッチパネル上に表示したソフトウェアキーボード、テンキー等によって行うこととし、入力部１１２およびクエリ候補表示部１１３をこのタッチパネルによって実現する。上述したクエリ候補選択条件１０８の最大表示候補数Ｄ_maxは、クエリ候補表示部１１３を実現するタッチパネルの表示画面の大きさに応じて定義されたものである。

入力部１１２は、ユーザから検索用キーワードの読み文字列１１１およびクエリ候補選択結果１１１ａの入力を受け付けて、その情報をクエリ候補表示部１１３へ出力する。
クエリ候補表示部１１３は、検索用キーワードの読み文字列１１１およびクエリ候補選択結果１１１ａの情報を受けると、クエリ候補辞書１０３を参照して読みトライ構造索引の注目ノードを遷移させる。そして、遷移先のノードに対するショートカット情報をクエリ候補辞書１０３から取得してクエリ候補のリストを作成して提示する。

具体的には、検索用キーワードの読み文字列１１１が何も入力されていない初期状態では、クエリ候補表示部１１３は、クエリ候補辞書１０３の読みトライ構造索引２２においてルートノードＮ_rを注目ノードとする。読みが入力されると、クエリ候補表示部１１３は入力された読みを一文字ずつ読み込み、注目ノードを、その注目ノードの子孫ノードのうちの入力された読みに合致するノードに遷移して、これを新たな注目ノードとする。
他方、クエリ候補表示部１１３は、提示した複数のクエリ候補の中からユーザが選択した選択結果を示すクエリ候補選択結果１１１ａが入力された場合には、図１４に示すショートカット情報の「（イ）ショートカットノードＮ_i」を参照し、該当するノード番号に遷移する。
続いて、クエリ候補表示部１１３は、遷移した先のノード番号にリンクする全てのショートカット情報をもとに、各ショートカット情報の「（ウ）見出し一覧を参照するレコード番号」を参照し、さらに図１３に示す見出し一覧からそのレコード番号の見出しを取得して、この見出しをクエリ候補としてユーザに提示する。このとき、クエリ候補表示部１１３は、ショートカット情報の「（エ）ショートカットスコアＳ_e（Ｎ_x，Ｎ_y）」が高いクエリ候補の表示順位が高くなるように、表示順位を制御する。

次に、クエリ候補提示部１１０の動作を説明する。図１６は、この発明の実施の形態１に係るクエリ候補提示装置のクエリ候補提示部１１０の動作を示すフローチャートである。
ステップＳＴ１１は文字入力処理またはクエリ候補選択処理である。クエリ候補提示処理の開始直後、即ち初期状態のステップＳＴ１１において、入力部１１２はユーザから入力される検索用キーワードの読み文字列１１１を受ける。

ステップＳＴ１２は読みトライ構造索引における状態遷移処理であり、ステップＳＴ１１で受け付けた検索用キーワードの読み文字列１１１の情報に従って、クエリ候補表示部１１３が図３に示す読みトライ構造索引の注目ノードを更新する。例えば、読みＮ_r〜Ｎ６の「とうきょうこ」が入力された場合、クエリ候補表示部１１３は注目ノードをルートノードＮ_rからＮ６へ遷移させる。

ステップＳＴ１３は終了判定処理であり、ステップＳＴ１２において注目ノードの子孫ノードのうち、入力された読みに合致する遷移先のノードがない場合は、ユーザが入力した読みに対応するクエリ候補が存在しないということなので、クエリ候補表示部１１３はクエリ候補提示処理を終了する（ステップＳＴ１３“Ｎｏ”）。
遷移先のノードがあれば、クエリ候補表示部１１３は処理を次へ進める（ステップＳＴ１３“Ｙｅｓ”）。読み「とうきょうこ」が入力された場合、遷移先のノードＮ６が存在するため次の処理へ進む。

ステップＳＴ１４はクエリ候補取得表示処理であり、クエリ候補表示部１１３が遷移先のノードに対応したショートカット情報を参照して、クエリ候補のリストを取得する。
読み「とうきょうこ」が入力された場合、遷移先の注目ノードＮ６に対応するショートカット情報は、図１４に示すとおりである。クエリ候補表示部１１３は、先ずＮ６に対応するショートカット情報２３ａ（ショートカットＮ６→Ｎ１７）、ショートカット情報２３ｂ（ショートカットＮ６→Ｎ３１）およびショートカット情報２３ｃ（ショートカットＮ６→Ｎ５４）を参照して見出し一覧のレコード番号Ｒ３、Ｒ６およびＲ９を取得する。クエリ候補表示部１１３は次に、図１３の見出し一覧２１から同一レコード番号のクエリ候補「東京国際空港第一」、「東京国際空港第二」および「東京国際空港第三駐車場」を取得して、画面に表示する。

図１７は、クエリ候補提示装置のクエリ候補表示部１１３がユーザの入力に対して表示するクエリ候補提示の画面例を示す説明図である。図１７（ａ）に示すように、クエリ候補表示部１１３が取得したクエリ候補を画面上のクエリ候補文字列として表示している。
そして、処理は再びステップＳＴ１１に戻る。

検索用キーワードの読み文字列１１１として「と」、「う」、「き」、「ょ」、「う」、「こ」が入力されるとき、クエリ候補提示部１１０はステップＳＴ１１〜ステップＳＴ１３の処理を繰り返し、注目ノードがルートノードＮ_rからＮ１，Ｎ２，Ｎ３，Ｎ４，Ｎ５，Ｎ６まで遷移する。このとき、クエリ候補表示部１１３の表示画面は図１７（ａ）の状態となる。ここで、処理がステップＳＴ１１に戻り、図１７（ｂ）に示すようにユーザがクエリ候補「東京国際空港第二」を選択する入力を入力部１１２に対して行うと、入力部１１２がその入力をクエリ候補選択結果１１１ａとして受け付けるクエリ候補選択処理を行う。

そして、ステップＳＴ１２において、クエリ候補表示部１１３が、クエリ候補「東京国際空港第二」に対するショートカット情報に従って注目ノードをショートカットノードＮ３１に遷移させる。同時に、クエリ候補表示部１１３は、選択されたクエリ候補のショートカット経路（Ｎ６→Ｎ３１）にある読み文字列「くさいくうこうだいに」を読み入力として補って画面表示する（図１７（ｃ））。
遷移先ノードが存在するので処理は進み（ステップＳＴ１３“Ｙｅｓ”）、続くステップＳＴ１４にて、クエリ候補表示部１１３はクエリ候補「東京国際空港第二」のショートカットノードＮ３１に応じた次のクエリ候補「東京国際空港第二ターミナル」および「東京国際空港第二駐車場」を取得して画面表示する。

再び処理がステップＳＴ１１に戻り、クエリ候補「東京国際空港第二ターミナル」または「東京国際空港第二駐車場」のいずれか一方がユーザにより選択されると、ステップＳＴ１３の終了判定において、遷移先のノードが存在しないことが確認されるため、ここでクエリ候補提示処理が終了する。

図１８は、最大表示候補数Ｄ_maxを５に設定した場合のクエリ候補提示の画面例であり、読みＮ_r〜Ｎ６６の「とうきょうとり」が入力された場合を示す。クエリ候補提示部１１０は、図１１に示すパターン１１Ｂのスコア計算例に基づいて生成されたクエリ候補辞書１０３を用いてクエリ候補提示処理を行うことによって、図１８の画面例のように項目数とその表示順位を制御して、クエリ候補を表示することができる。

以上のように、実施の形態１によれば、クエリ候補を提示してユーザに選択させることによって節約できる打鍵数、ユーザのクエリ候補選択後に残りの文字列を入力するときに予測される打鍵数削減を示す確定後スコア、一画面に表示できる項目数である最大表示候補数等を考慮してスコア計算を行うスコア計算部１０７を用いてクエリ候補辞書１０３を生成し、クエリ候補提示部１１０がこのクエリ候補辞書１０３を参照してクエリ候補を提示するように構成した。そのため、画面サイズ、検索対象データの読みの偏り等に応じた適切なクエリ候補を提示することができ、ユーザの検索用キーワードの入力効率を向上できるという効果が得られる。

実施の形態２．
図１９は、この発明の実施の形態２に係るクエリ候補提示装置のスコア計算部の詳細構成を示すブロック図である。本実施の形態のスコア計算部１０７は、図１９に示すように、打鍵数短縮スコア計算部１１、確定後スコア計算部１２、スコア集計部１３、候補選択スコア計算部１４を備える。
本実施の形態に係るクエリ候補提示装置の構成は、スコア計算部１０７の内部構成以外は図１に示した実施の形態１に係るクエリ候補提示装置の構成と同じであるため、スコア計算部１０７以外の図示および詳細な説明は省略する。

図２０は、スコア計算部１０７が用いるスコアの定義を示す説明図である。本実施の形態のスコア計算部１０７は、候補選択スコア計算部１４が候補選択スコアＣ_sel（Ｎ_i）を計算し、打鍵数短縮スコア計算部１１が候補選択スコアＣ_sel（Ｎ_i）を用いて打鍵数短縮スコアＣ₁（Ｎ_x，Ｎ_i）を計算する点で、上記実施の形態１のスコア計算部１０７とは異なる。

上記実施の形態１では、クエリ候補選択条件１０８として一画面に表示可能なクエリ候補数である最大表示候補数Ｄ_maxを設定していたが、一画面に表示できる項目数以上のクエリ候補数をＤ_maxとして設定しておくことも可能である。このような場合には、クエリ候補提示部１１０は数ページにわたってクエリ候補を表示することになり、ユーザはスクロールバーまたはページ送りボタン等によってページを送り、クエリ候補を選択する。
候補選択スコア計算部１４は、このようにスクロールバーまたはページ送りボタン等によって複数ページにわたってクエリ候補を提示する場合に、ページ数に応じて増大するユーザの入力手間を表す候補選択スコアＣ_sel（Ｎ_i）を計算する。

打鍵数短縮スコア計算部１１は、候補選択スコア計算部１４の候補選択スコアを反映した打鍵数短縮スコアを算出する。スコア計算部１０７のスコアの定義を図２０のように拡張することによって、クエリ候補提示部１１０がスクロールバーまたはページ送りボタン等によって複数ページにわたってクエリ候補を提示する場合であっても、スコア計算部１０７は、２ページ目、３ページ目で表示されるクエリ候補の打鍵数低減に対する貢献度を考慮したスコア計算が可能となる。

以上のように、実施の形態２によれば、クエリ候補を提示してユーザに選択させることによって節約できる打鍵数、ユーザのクエリ候補選択後に残りの文字列を入力するときに予測される打鍵数削減を示す確定後スコア、一画面に表示できる項目数である最大表示候補数等を考慮してスコア計算を行うスコア計算部１０７に、候補選択スコア計算部１４を設けるように構成した。このため、スコア計算部１０７は、クエリ候補提示部１１０が複数ページにわたってクエリ候補を提示する場合の入力の手間を考慮した適切なスコア計算を行ってクエリ候補辞書１０３を生成できる。そして、クエリ候補提示部１１０が、このクエリ候補辞書１０３を参照してクエリ候補を提示するように構成したので、画面サイズ、検索対象データの読みの偏り等に応じた適切なクエリ候補を提示することができ、ユーザの入力効率を向上できるという効果が得られる。

実施の形態３．
図２１は、この発明の実施の形態３に係るクエリ候補提示装置のスコア計算部の詳細構成を示すブロック図である。本実施の形態のスコア計算部１０７は、図１９に示した実施の形態２のスコア計算部１０７の構成に、候補重要度スコア計算部１５を追加したものである。
本実施の形態に係るクエリ候補提示装置の構成は、スコア計算部１０７の内部構成以外は図１に示した実施の形態１に係るクエリ候補提示装置の構成と同じであるため、スコア計算部１０７以外の図面および詳細な説明は省略する。

図２２は、スコア計算部１０７が用いるスコアの定義を示す説明図である。本実施の形態のスコア計算部１０７は、候補重要度スコア計算部１５が候補重要度スコアＣ_L（Ｎ_i）を計算し、打鍵数短縮スコア計算部１１が候補重要度スコアＣ_L（Ｎ_i）を用いて打鍵数短縮スコアＣ₁（Ｎ_x，Ｎ_i）を計算する点で、上記実施の形態１および２のスコア計算部１０７とは異なる。

例えば、図２に示すような地名または施設名をクエリ候補としてクエリ候補辞書１０３を生成する場合、重要語句抽出処理において重要語句抽出部１０４が有名な地名または施設名に高い重要度を付与し（説明書の場合には画面レイアウト情報等を手掛りとした重要度を付与すればよい）、トライ構造索引生成処理においてトライ構造索引生成部１０５が各ノードに語句の重要度を反映した重み（図２２のＷｇｔ（Ｎ_j））を与えておく。
候補重要度スコア計算部１５は、ショートカットノードＮ_iの子孫である葉ノードＮ_jに対応する語句の重要度Ｗｇｔ（Ｎ_j）を用いて、クエリ候補の重要度を示す候補重要度スコアＣ_L（Ｎ_i）を計算する。

打鍵数短縮スコア計算部１１は、候補重要度スコア計算部１５の候補重要度スコアを反映した打鍵数短縮スコアを算出する。スコア計算部１０７のスコアの定義を図２２のように拡張することによって、読み文字数や葉ノード数にかかわらず、特に重要な語句を優先的にクエリ候補として表示することが可能となる。

以上のように、実施の形態３によれば、クエリ候補を提示してユーザに選択させることによって節約できる打鍵数、ユーザのクエリ候補選択後に残りの文字列を入力するときに予測される打鍵数削減を示す確定後スコア、一画面に表示できる項目数である最大表示候補数等を考慮してスコア計算を行うスコア計算部１０７に、候補重要度スコア計算部１５を設けるように構成した。このため、スコア計算部１０７は、読み文字数や葉ノード数にかかわらず特に重要な語句に高い優先順位を付けるスコア計算を行ってクエリ候補辞書１０３を生成できる。そして、クエリ候補提示部１１０が、このクエリ候補辞書１０３を参照してクエリ候補を提示するように構成したので、画面サイズ、検索対象データの読みの偏り、語句の重要度等に応じた適切なクエリ候補を提示することができ、ユーザの入力効率を向上できるという効果が得られる。

この発明の実施の形態１に係るクエリ候補提示装置の構成を示すブロック図である。 この発明の実施の形態１に係るクエリ候補提示装置の重要語句抽出部が抽出した重要語句の例を示す説明図である。 この発明の実施の形態１に係るクエリ候補提示装置のトライ構造索引生成部が生成した読みトライ構造索引を示す説明図である。 この発明の実施の形態１に係るクエリ候補提示装置の読みトライ構造索引のショートカットを示す説明図である。 この発明の実施の形態１に係るクエリ候補提示装置のスコア計算部の詳細構成を示すブロック図である。 この発明の実施の形態１に係るクエリ候補提示装置のスコア計算部が用いるスコアの定義を示す説明図である。 この発明の実施の形態１に係るクエリ候補提示装置のスコア計算部のスコア計算例を示す説明図である。 この発明の実施の形態１に係るクエリ候補提示装置の確定後スコア計算部の確定後スコア計算例を示す説明図である。 この発明の実施の形態１に係るクエリ候補提示装置のスコア計算部のスコア計算例を示す説明図である。 この発明の実施の形態１に係るクエリ候補提示装置のスコア計算部のスコア計算例を示す説明図である。 この発明の実施の形態１に係るクエリ候補提示装置のスコア計算部のスコア計算例を示す説明図であり、最大表示候補数Ｄ_maxが５のときを示す。 この発明の実施の形態１に係るクエリ候補提示装置のクエリ候補辞書の構成を示すブロック図である。 この発明の実施の形態１に係るクエリ候補提示装置のクエリ候補辞書に登録された見出し一覧の例を示す説明図である。 この発明の実施の形態１に係るクエリ候補提示装置のクエリ候補辞書に登録されたショートカット情報の例を示す説明図である。 この発明の実施の形態１に係るクエリ候補提示装置のクエリ候補辞書生成部の動作を示すフローチャートである。 この発明の実施の形態１に係るクエリ候補提示装置のクエリ候補提示部の動作を示すフローチャートである。 この発明の実施の形態１に係るクエリ候補提示装置のクエリ候補表示部がユーザの入力に対して表示するクエリ候補提示の画面例を示す説明図である。 この発明の実施の形態１に係るクエリ候補提示装置のクエリ候補表示部が表示する最大表示候補数Ｄ_maxが５のときのクエリ候補提示の画面例を示す説明図である。 この発明の実施の形態２に係るクエリ候補提示装置のスコア計算部の詳細構成を示すブロック図である。 この発明の実施の形態２に係るクエリ候補提示装置のスコア計算部が用いるスコアの定義を示す説明図である。 この発明の実施の形態３に係るクエリ候補提示装置のスコア計算部の詳細構成を示すブロック図である。 この発明の実施の形態３に係るクエリ候補提示装置のスコア計算部が用いるスコアの定義を示す説明図である。

符号の説明

１１ 打鍵数短縮スコア計算部、１２ 確定後スコア計算部、１３ スコア集計部、１４ 候補選択スコア計算部、１５ 候補重要度スコア計算部、２１ 見出し一覧、２２ 読みトライ構造索引、２３，２３ａ，２３ｂ，２３ｃ ショートカット情報、１０１ クエリ候補辞書生成部、１０２ 検索対象データ、１０３ クエリ候補辞書、１０４ 重要語句抽出部、１０５ トライ構造索引生成部、１０６ クエリ候補抽出部、１０７ スコア計算部、１０８ クエリ候補選択条件、１０９ クエリ候補選択部、１１０ クエリ候補提示部、１１１ 検索用キーワードの読み文字列、１１１ａ クエリ候補選択結果、１１２ 入力部、１１３ クエリ候補表示部。

Claims (5)

1. 一文字ずつ入力される検索用キーワードの読み文字で始まるクエリ候補をクエリ候補辞書から取得して、当該検索用キーワードの候補として提示するクエリ候補表示部を備えるクエリ候補提示装置において、
   検索対象データから抽出された語句を当該語句の読み文字に基づいて階層構造化したデータから、前記クエリ候補となる文字列を抽出するクエリ候補抽出部と、
   前記検索用キーワードの読み文字で始まる前記文字列をクエリ候補とすることによって得られる当該検索用キーワードの入力手間軽減の効果を示すスコアを計算するスコア計算部と、
   前記検索対象データから抽出された語句の読み文字毎に、前記スコア計算部で計算されたスコアに基づいて前記文字列をクエリ候補として前記クエリ候補辞書に登録するクエリ候補選択部とを備えることを特徴とするクエリ候補提示装置。
2. スコア計算部は、
   検索用キーワードの読み文字で始まる文字列をクエリ候補とすることによって削減される当該検索用キーワードの打鍵数を示す打鍵数短縮スコアを計算する打鍵数短縮スコア計算部と、
   前記文字列が前記検索用キーワードの一部であることが確定した場合に当該文字列で始まる新たなクエリ候補を提示することによって予測される当該検索用キーワードの打鍵数削減の効果を示す確定後スコアを計算する確定後スコア計算部と、
   前記打鍵数短縮スコアおよび前記確定後スコアを用いて、前記文字列をクエリ候補とすることによって得られる前記検索用キーワードの入力手間軽減の効果を示すスコアを計算するスコア集計部とを備えることを特徴とする請求項１記載のクエリ候補提示装置。
3. スコア計算部は、
   検索用キーワードの読み文字で始まる文字列をクエリ候補とすることによって削減される当該検索用キーワードの打鍵数を示す打鍵数短縮スコアを計算する打鍵数短縮スコア計算部と、
   前記文字列が前記検索用キーワードの一部であることが確定した場合に当該文字列で始まる新たなクエリ候補を提示することによって予測される当該検索用キーワードの打鍵数削減の効果を示す確定後スコアを計算する確定後スコア計算部と、
   クエリ候補表示部が同時に提示可能なクエリ候補数に基づいて、複数ページにわたってクエリ候補を提示することによって増大する前記検索用キーワードの入力手間を示す候補選択スコアを計算する候補選択スコア計算部を備え、
   スコア集計部は、前記打鍵数短縮スコア、前記確定後スコアおよび前記候補選択スコアを用いて、前記文字列をクエリ候補として提示することによって得られる前記検索用キーワードの入力手間軽減の効果を示すスコアを計算することを特徴とする請求項１記載のクエリ候補提示装置。
4. スコア計算部は、
   検索用キーワードの読み文字で始まる文字列をクエリ候補とすることによって削減される当該検索用キーワードの打鍵数を示す打鍵数短縮スコアを計算する打鍵数短縮スコア計算部と、
   前記文字列が前記検索用キーワードの一部であることが確定した場合に当該文字列で始まる新たなクエリ候補を提示することによって予測される当該検索用キーワードの打鍵数削減の効果を示す確定後スコアを計算する確定後スコア計算部と、
   クエリ候補表示部が同時に提示可能なクエリ候補数に基づいて、複数ページにわたってクエリ候補を提示することによって増大する前記検索用キーワードの入力手間を示す候補選択スコアを計算する候補選択スコア計算部と、
   検索対象データから抽出された語句の重要度に基づいて、前記文字列の重要度を示す候補重要度スコアを計算する候補重要度スコア計算部を備え、
   スコア集計部は、前記打鍵数短縮スコア、前記確定後スコア、前記候補選択スコアおよび前記候補重要度スコアを用いて、前記文字列をクエリ候補とすることによって得られる前記検索用キーワードの入力手間軽減の効果を示すスコアを計算することを特徴とする請求項１記載のクエリ候補提示装置。
5. クエリ候補選択部は、検索対象データから抽出された語句の読み文字毎に、クエリ候補表示部が同時に提示可能なクエリ候補数に応じた数の文字列をクエリ候補としてクエリ候補辞書に登録することを特徴とする請求項１から請求項４のうちのいずれか１項記載のクエリ候補提示装置。

Images