説明

文字列選択装置、文字列選択方法およびプログラム

【課題】文字列選択装置が、ユーザの入力したい文字列の候補を適切に、かつ、高速に得る。
【解決手段】文字インデックス生成部122が、用語記憶部131が記憶する用語に含まれる文字毎に、当該文字を含む用語を示す文字インデックスを記憶しておく。そして、処理部120は、ユーザにより入力済みの文字列と、用語記憶部131が記憶する用語とのLCSを算出する際に、文字インデックスに基づいて、ユーザにより入力済みの文字列に含まれる文字を含む用語を選択し、選択した文字についてLCSの算出を行う。このように、LCSの算出を行う用語を絞り込むことができるので、ユーザの入力したい文字列の候補を適切に、かつ、高速に得ることができる。

【発明の詳細な説明】
【技術分野】
【0001】
本発明は、文字列選択装置、文字列選択方法およびプログラムに関する。
【背景技術】
【0002】
コンピュータ等においてユーザが用語(文字列)を入力する負担を軽減する用語入力支援方法の1つに、当該コンピュータ等が、予め記憶する用語群の中から、入力済みの文字列に類似する用語を用語候補として選択して表示し、表示した用語候補のいずれかに対するユーザの選択操作を受け付ける方法がある。
例えば、コンピュータの表示画面に表示される診断書に病名を入力する際、図12(a)に示すように、ユーザによる「大腸」の入力に対して、コンピュータは、この「大腸」に類似する用語として、「大腸炎」や「大腸癌」など、「大腸」を含む用語を選択し、入力欄の下方近傍に表示する。そして、カーソルキーあるいはマウスを用いてユーザが「大腸ポリープ」を選択すると、コンピュータは、選択された「大腸ポリープ」を入力欄に表示する。
【0003】
一方、ユーザが用語の選択を行わずに、更に「癌」を入力すると、コンピュータは、同図(b)に示すように、入力された文字列「大腸癌」のうち2文字以上を含む、「大腸炎」や「大腸粘膜内癌」などの用語を選択して表示する。
このように、入力された文字列の全部を含む用語に限らず、一部を含む用語も表示することにより、「大腸炎」を誤って「大腸癌」と入力する文字違いや、「転移性大腸癌」を誤って「転移大腸癌」と入力する入力不足など、入力された文字列に誤りがある場合にもユーザの意図する用語を表示し得る。
【0004】
このような、入力済みの文字列に類似する用語を用語候補として選択する方法として、例えば、特許文献1に示される方法を用いることが考えられる。同文献では、"leucocyte"と"leukocyte"など、同一の事物を示す用語の表記が異なる「表記揺れ」の用語を取得する方法が示されている。この方法では、注目する用語に対する表記揺れの用語を収集するために、まず、予め記憶する用語の各々について、注目する用語とのNグラム(文字数Nの部分文字列)の一致度および文字列長の類似度を比較することにより、類似する用語の絞込みを行う(以下では、この絞込みを「第1の絞込み」と称する)。そして、大文字と小文字との置換は10点、数字の置換は100点など、編集内容毎に設定されたコストで重み付けされた編集距離に基づいて、さらに用語の絞込みを行う(以下では、この絞込みを「第2の絞込み」と称する)。
この方法を、用語候補の選択に用いると、入力済みの文字列と共通の部分文字列を多く含み、入力済みの文字列に文字数が類似し、かつ、入力済みの文字列に対してコストの小さい変換操作を行って得られる文字列を抽出できる。
【先行技術文献】
【特許文献】
【0005】
【特許文献1】特開2005−352888号公報
【発明の概要】
【発明が解決しようとする課題】
【0006】
しかしながら、特許文献1に示される方法を用語候補の選択に用いた場合、第1の絞込みを行う段階で、編集距離が小さい用語が除外されてしまい、最終的に、ユーザが入力したい用語を抽出できなくなるおそれが強くなってしまう。
かかる不都合を回避するために、第1の絞込みを行う段階における絞込み要件を緩和することによって除外する用語の数を少なくすることが考えられる。しかし、第1の絞込みを行う段階で除外する用語の数を少なくすると、第2の絞込みの対象となる用語の数が増大し、処理に要する時間が増大してしまう。ユーザに、用語候補の表示を待つストレスを与えないためには、例えば文字列が入力されてから0.1秒以内に用語候補を表示するなど、高速に用語候補を選択して表示する必要がある(例えば、図12(b)の「癌」が入力された後速やかに、同図(b)に示す用語候補を表示する必要がある)が、処理に要する時間の増大により、高速に用語候補を選択して表示できないおそれがある。
【0007】
本発明は、このような事情を考慮してなされたものであり、その目的は、ユーザの入力したい文字列の候補を適切に、かつ、高速に得られる文字列選択装置、文字列選択方法およびプログラムを提供することにある。
【課題を解決するための手段】
【0008】
[1]この発明は上述した課題を解決するためになされたもので、本発明の一態様による文字列選択装置は、第1の文字列を取得する取得部と、1つ以上の第2の文字列の各々と、当該第2の文字列を識別する文字列識別情報とが対応付けられた識別情報付文字列群を記憶する文字列群記憶部と、前記識別情報付文字列群中の前記第2の文字列に含まれる全ての文字について、異なる前記文字毎に、当該文字と、当該文字を含み前記識別情報付文字列群に含まれる前記第2の文字列の文字列識別情報と、が対応付けられた文字インデックスを記憶する文字インデックス記憶部と、前記第1の文字列に含まれる文字に、前記文字インデックスにて対応付けられた前記文字列識別情報により識別される前記第2の文字列を選択する文字列選択部と、を具備することを特徴とする。
【0009】
[2]また、本発明の一態様による文字列選択装置は、上述の文字列選択装置であって、前記文字列選択部は、前記選択した第2の文字列に含まれる文字と、前記第1の文字列に含まれる文字とに共通する文字の文字数を示す文字数情報を生成することを特徴とする。
【0010】
[3]また、本発明の一態様による文字列選択装置は、上述の文字列選択装置であって、前記文字列選択部は、前記第1の文字列の部分文字列に含まれる文字と、前記第2の文字列に含まれる文字とに共通する文字の文字数を示す文字数情報を生成し、当該文字数情報と、前記第1の文字列に含まれる文字数と前記部分文字列に含まれる文字数との差と、に基づいて定まる値が、予め定められた閾値未満の場合に、前記第1の文字列と当該第2の文字列との前記類似度を示す情報の生成を中止することを特徴とする。
【0011】
[4]また、本発明の一態様による文字列選択方法は、1つ以上の第2の文字列の各々と、当該第2の文字列を識別する文字列識別情報とが対応付けられた識別情報付文字列群を記憶する文字列群記憶部と、前記識別情報付文字列群中の前記第2の文字列に含まれる全ての文字について、異なる前記文字毎に、当該文字と、当該文字を含み前記識別情報付文字列群に含まれる前記第2の文字列の文字列識別情報と、が対応付けられた文字インデックスを記憶する文字インデックス記憶部と、を具備する文字列選択装置の文字列選択方法であって、取得部が、第1の文字列を取得する取得ステップと、文字列選択部が、前記第1の文字列に含まれる文字に、前記文字インデックスにて対応付けられた前記文字列識別情報により識別される前記第2の文字列を選択する文字列選択ステップと、を具備することを特徴とする。
【0012】
[5]また、本発明の一態様によるプログラムは、1つ以上の第2の文字列の各々と、当該第2の文字列を識別する文字列識別情報とが対応付けられた識別情報付文字列群を記憶する文字列群記憶部と、前記識別情報付文字列群中の前記第2の文字列に含まれる全ての文字について、異なる前記文字毎に、当該文字と、当該文字を含み前記識別情報付文字列群に含まれる前記第2の文字列の文字列識別情報と、が対応付けられた文字インデックスを記憶する文字インデックス記憶部と、を具備する文字列選択装置としてのコンピュータに、第1の文字列を取得する取得ステップと、前記第1の文字列に含まれる文字に、前記文字インデックスにて対応付けられた前記文字列識別情報により識別される前記第2の文字列を選択する文字列選択ステップと、を実行させるためのプログラムである。
【発明の効果】
【0013】
この発明によれば、文字列選択部は、第1の文字列に含まれる文字に、文字インデックスにて対応付けられた文字列識別情報により識別される第2の文字列を選択する。
これにより、文字列選択部は、第1の文字列と共通の文字を含まない第2の文字列については、選択の要否を判定することなく第2の文字列を選択できるので、第2の文字列を高速に選択できる。これにより、ユーザの入力したい文字列の候補として、第2の文字列を高速に得られる。
また、文字列選択部は、第1の文字列に含まれる文字に、文字インデックスにて対応付けられた文字列識別情報により識別される第2の文字列を選択することにより、第1の文字列に含まれる文字を含む第2の文字列のみを全て選択できる。この点で、ユーザの入力した文字列の候補として、第2の文字列を適切に得られる。
【0014】
この発明によれば、さらに、選択された第2の文字列を用いて、選択した第2の文字列に含まれる文字と、第1の文字列に含まれる文字とに共通する文字の文字数を示す文字数情報を生成するようにした。これにより、文字数情報の文字数が多い第2の文字列は、第1の文字列と共通度合いが高いものとして把握することができる。
【0015】
この発明によれば、さらに、第1の文字列の部分文字列に含まれる文字と、第2の文字列に含まれる文字とに共通する文字の文字数を示す文字数情報を生成した後、当該文字数情報と、第1の文字列に含まれる文字数と部分文字列に含まれる文字数との差と、に基づいて定まる値が、予め定められた閾値未満の場合に、第1の文字列と当該第2の文字列との前記類似度を示す情報の生成を中止するようにした。これにより、文字数情報が閾値未満となる第2の文字列を除外して、残りの第2の文字列に対して文字数情報を生成することができ、文字数情報を生成する処理を高速に行うことができる。
【図面の簡単な説明】
【0016】
【図1】本発明の一実施形態における文字列入力支援システムの概略構成を示す構成図である。
【図2】同実施形態において、用語記憶部131が記憶する用語リストの例を示す図である。
【図3】同実施形態において、文字インデックス記憶部132が記憶する文字インデックスの例を示す図である。
【図4】LCS長を算出するために用いられる行列の例を示す図である。
【図5】入力文字列と用語とのLCSが用語中に出現する位置を示す文字位置情報を算出するために用いられる行列の例を示す図である。
【図6】同実施形態において、文字インデックス生成部122が文字インデックスを生成する処理手順を示すフローチャートである。
【図7】同実施形態において、処理部120がLCS長を算出し、文字位置情報を生成する処理手順を示すフローチャートである。
【図8】同実施形態において、処理部120がLCS長を算出し、文字位置情報を生成する処理手順を示すフローチャートである。
【図9】同実施形態において、順位決定部125による用語の順位決定の例を示す図である。
【図10】同実施形態において、順位決定部125が生成する指標の例を示す図である。
【図11】同実施形態において、表示部230が用語のリストを表示した例を示す図である。
【図12】ユーザが文字列を入力する際の、ユーザが入力した文字列の候補の表示例を示す図である。
【発明を実施するための形態】
【0017】
以下、図面を参照して、本発明の一実施形態について説明する。
図1は、本発明の一実施形態における文字列入力支援システムの概略構成を示す構成図である。同図において、文字列入力支援システム1は、文字列入力支援装置(文字列選択装置)100と、端末装置200とを具備する。文字列入力支援装置100は、通信部(取得部)110と、処理部(文字列選択部)120と、記憶部130とを具備する。処理部120は、処理制御部121と、文字インデックス生成部122と、LCS長算出部123と、文字位置情報生成部124と、順位決定部125とを具備する。記憶部130は、用語記憶部(文字列群記憶部)131と、文字インデックス記憶部132と、LCS長行列記憶部133と、文字位置情報行列記憶部134とを具備する。端末装置200は、通信部210と、入力部220と、表示部230とを具備する。
【0018】
文字列入力支援システム1は、ユーザが入力済みの文字列(第1の文字列。以下では、「入力文字列」と称する)に基づいて、ユーザが入力したい文字列の候補(文字列候補)を表示する。
文字列入力支援装置100は、入力文字列を端末装置200から取得し、取得した文字列に基づいて、ユーザが入力したい文字列の候補の各々の順位を決定し、ユーザが入力したい文字列の候補を、決定した順位に従って並べたリストを生成して端末装置200に送信する。
通信部110は、端末装置200との間でデータの送受信を行う。
記憶部130は、ユーザが入力したい文字列の候補である用語を予め記憶する。また、記憶部130は、ユーザが入力したい文字列の候補である用語の順位を、文字列入力支援装置100が決定する際のワーキングメモリとして機能する。記憶部130は、文字列入力支援装置100が具備する記憶装置上に実現される。
【0019】
用語記憶部131は、ユーザが入力したい文字列の候補である用語(第2の文字列)をリスト形式にて予め記憶する。
図2は、用語記憶部131が記憶する用語リストの例を示す図である。同図に示すように、用語リストの各行に、ユーザが入力したい文字列の候補である用語と、当該用語の識別番号である用語IDとが対応付けて記憶されている。用語リストは、例えば、ある分野の辞書に含まれる用語の各々に用語IDを付して生成される。同図の例では、用語リストは、病名に用語IDを付して生成されている。
用語IDは、各用語を識別する情報であると共に、用語リスト中における各用語の順序を示す情報でもある。
なお、用語リストに記憶される用語の数は、同図に示す7つに限らず、任意の個数であってよい。
【0020】
文字インデックス記憶部132は、用語記憶部131が記憶する用語に含まれる文字の各々について、当該文字を含む用語を示す文字インデックスを記憶する。
図3は、文字インデックス記憶部132が記憶する文字インデックスの例を示す図である。同図に示すように、文字インデックスの各行には、用語リスト中のいずれかの用語に含まれる文字と、当該文字を含む用語を示す用語IDリストとが格納されている。同図の文字インデックスは、図2の用語リスト中の用語に含まれる文字毎に、当該文字を含む用語を用語IDにて示している。例えば、図2の用語リスト中で用語ID「1」に対応付けられた用語「小腸癌」は、文字「小」と「腸」と「癌」とを含む。したがって、図3の文字インデックスの、文字「小」を含む行と、文字「腸」を含む行と、文字「癌」を含む行とのいずれも、用語IDリスト中に用語ID「1」を含んでいる。
【0021】
LCS長行列記憶部133は、文字列入力支援装置100が用語の順位を決定する際に生成するLCS長行列を記憶するワーキングメモリである。
以下、図4を参照して、LCS長行列記憶部133が記憶するLCS長行列について説明する。
図4は、LCS長を算出するために用いられる行列の例を示す図である。同図(a)と(b)とは、いずれも、LCS長を算出するために用いられる行列の例を示す。
同図(a)の行列は、入力文字列の文字数+1の行、および、用語記憶部131が記憶する用語の文字数+1の列を有する行列であり、各要素には非負整数が格納される。以下では、図4(a)の行列の最上行(初期値に対応する行)を第0行とし、最左列(初期値に対応する列)を第0列とする。
【0022】
ここで、LCS(Longest Common Subsequence、最長共通部分列)は、2つの文字列に共通する部分列(共通部分列、Common Subsequence)のうち、最も長い(文字数の多い)ものである。この共通部分列は、各文字列中に連続して出現する必要はないが、2つの文字列中に同じ順序で出現する必要がある。図4(a)の「大腸粘膜内癌」と「大腸粘液癌」との場合、「大」「腸」「粘」「癌」の各文字が同順序で出現しているので、両者のLCSは「大腸粘癌」であり、LCSの文字数(以下では、「LCS長」と称する)は4である。
このように、LCS長は、2つの文字列に共通する文字の数を示すので、2つの文字列の類似度を示す情報として用いることができる。
【0023】
図4(a)の行列の各要素は、当該要素の位置に対応する、用語またはその部分文字列と、入力文字列またはその部分文字列とのLCS長を示す。例えば、図4(a)の行列の第5行第6列の要素a156は、入力文字列「大腸粘液癌」と、用語「大腸粘膜内癌」とのLCS長「4」を示している。また、図4(a)の行列の第2行第4列の要素a124は、入力文字列の先頭から2文字の部分文字列(すなわち、先頭から2文字を入力した時点での入力文字列)「大腸」と、用語の先頭から4文字の部分文字列「大腸粘膜」とのLCS「大腸」の文字数「2」を示している。
【0024】
この、2つの文字列のLCSは、部分文字列のLCSから再帰的に算出できる。
2つの文字列の末尾の文字が同じ場合は、各文字列から当該末尾の文字を除いた部分文字列のLCSに、当該末尾の文字を加えることによりLCSを得られる。例えば、入力文字列「大腸粘液癌」と用語「大腸粘膜内癌」との末尾の文字は共に「癌」である。そして、「大腸粘液癌」と「大腸粘膜内癌」とのLCS「大腸粘癌」は、入力文字列「大腸粘液癌」から「癌」を除いた「大腸粘液」と、用語「大腸粘膜内癌」から「癌」を除いた「大腸粘膜内」との「大腸粘」に「癌」を加えて得られる。したがって、第5行第6列の要素a156の値「4」(「大腸粘癌」の文字数)は、第4行第5列の要素a145の値「3」(「大腸粘」の文字数)に1(「癌」の文字数)を加えた値となっている。
【0025】
一方、2つの文字列の末尾が異なる場合は、一方の文字列から当該末尾の文字を除いた部分文字列のLCSのうち、文字数の多いほうのLCSと同一(両者の値が等しい場合は、両者の値と同一)である。例えば、「大腸」と「大腸粘膜」との末尾の文字は、それぞれ「腸」と「膜」とであり異なる。ここで、「大腸」と、「大腸粘膜」から末尾の文字「膜」を除いた「大腸粘」とのLCSは「大腸」である。また、「大腸」から末尾の文字「腸」を除いた「大」と、「大腸粘膜」とのLCSは「大」である。そして、「大腸」と「大腸粘膜」とのLCS「大腸」は、この2つのLCS「大腸」および「大」のうち文字数の多いほうである「大腸」と同一である。したがって、第2行第4列の要素a124の値「2」(「大腸」の文字数)は、第2行第3列の要素a123の値「2」(「大腸」の文字数)と、第1行第4列の要素a114の値「1」(「大」の文字数)とのうち、値の大きいほうである「2」と同一である。
【0026】
このように、図4(a)の行列の各要素の値は、入力文字列中の対応する文字と、用語中の対応する文字とが同じ場合は、左上の要素の値に1を加えた値と同一である。一方、入力文字列中の対応する文字と、用語中の対応する文字とが異なる場合は、左隣の要素の値と、上隣の要素の値とのうち大きいほうの値と同一(両者の値が等しい場合は、両者の値と同一)である。
【0027】
ここで、図4(a)の入力文字列「大腸粘液癌」のうち、文字「液」は、用語「大腸粘膜内癌」と共通しておらず、LCS「大腸粘癌」には含まれない。このため、用語「大腸粘膜内癌」またはその部分文字列のいずれについても、入力文字列の部分文字列「大腸粘液」とのLCS長は、文字「液」を除いた「大腸粘」とのLCS長と同一である。例えば、用語の部分文字列「大腸粘膜内」について見ると、この「大腸粘膜内」と「大腸粘液」とのLCSは「大腸粘」であり、LCS長は(要素a145の値)「3」である。そして、「大腸粘膜内」と、「大腸粘液」から「液」を除いた「大腸粘」とのLCSも「大腸粘」であり、LCS長は(要素a135の値)「3」である。
このため、LCS行列の第4行(文字「液」に対応する行)の値は、上隣の第3行(文字「粘」に対応する行)の値と一致する。
【0028】
このように、入力文字列のうち用語に含まれない文字に対応する、図4(a)の行列中の行の値は、上隣の行の値と一致する。そこで、LCS長行列記憶部133は、図4(a)の行列から、用語に含まれない文字に対応する行を削除した行列を、LCS長行列として記憶する。このLCS長行列の最下行最右列の要素の値は、図4(a)の行列の最下行最右列の要素の値と一致する。すなわち、LCS長行列の最下行最右列の要素の値は、入力文字列と用語とのLCS長を示している。
例えば、LCS長行列記憶部133は、図4(a)の行列から、用語に含まれない文字「液」に対応する行を削除した、図4(b)のLCS長行列を記憶する。この行列の最下行最右列の要素a246の値「4」は、入力文字列「大腸粘液癌」と用語「大腸粘膜内癌」とのLCS「大腸粘癌」の文字数、すなわちLCS長を示している。
後述するように、LCS長行列は、文字インデックス記憶部132が記憶する文字インデックスを用いて生成される。
【0029】
図1に戻って、文字位置情報行列記憶部134は、文字列入力支援装置100が用語の順位を決定する際に生成する文字位置情報行列を記憶するワーキングメモリである。
以下、図5を参照して、文字位置情報行列記憶部134が記憶する文字位置情報行列について説明する。
図5は、入力文字列と用語とのLCSが用語中に出現する位置を示す文字位置情報を算出するために用いられる行列の例を示す図である。同図(a)と(b)とは、いずれも、文字位置情報を算出するために用いられる行列の例を示す。
同図(a)の行列は、入力文字列の文字数+1の行数、および、用語記憶部131が記憶する用語の文字数+1の列数を有する行列であり、各要素にはビット列(二進数)が格納される。以下では、図5(a)の行列の最上行(初期値に対応する行)を第0行とし、最左列(初期値に対応する列)を第0列とする。
【0030】
図5(a)の行列の各要素には、入力文字列と、用語記憶部131が記憶する用語とのLCSの各文字が、当該用語中に出現する位置を示す文字位置情報が格納されている。文字位置情報はビット列により構成され、1の位(最右ビット)から順に、入力文字列中の1番目(先頭)から順の各文字の位置を示す。例えば、図5(a)の行列の第5行第6列の要素b156は、最右ビットが入力文字列の先頭の文字「大」の位置を示し、以下同様に、右から2番目のビットが「腸」の位置、3番目が「粘」の位置、・・・、6番目(最左ビット)が「癌」の位置を示す。ここで、入力文字列「大腸粘液癌」と用語「大腸粘膜内癌」とのLCS「大腸粘癌」の各文字は、それぞれ、用語「大腸粘膜内癌」の先頭から1文字目(「大」)と、2文字目(「腸」)と、3文字目(「粘」)と、6文字目(「癌」)とに出現する。したがって、図5(a)の行列の第5行第6列の要素b156は、右から1、2、3、6番目のビットが「1」、4、5番目のビットが「0」となっている。
【0031】
上述したように、2つの文字列のLCSは、部分文字列のLCSから再帰的に算出できる。このため、文字位置情報も、部分文字列の文字位置情報から再帰的に生成できる。
2つの文字列(入力文字列またはその部分文字列、および、用語またはその部分文字列)の末尾の文字が同じ場合、これらの文字列の文字位置情報は、各文字列から当該末尾の文字を除いた部分文字列の文字位置情報に、当該末尾の文字の位置に対応する桁を1とした数を加算した値となる。例えば、図5(a)の行列の、第5行第6列の要素b156の値「100111」(二進数)は、第4行第5列の要素b145の値「111」(二進数。「00111」の先頭の0が省略されている。以下同様に、文字位置情報の先頭の0の表示を省略する)に、末尾の文字「癌」の位置に対応する右から6桁目が1の「100000」(二進数)を加算した値となっている。
【0032】
一方、2つの文字列の末尾が異なる場合、これらの文字列の文字位置情報は、一方の文字列から当該末尾の文字を除いた場合の文字位置情報のうち、LCS長が長いほうの文字列の文字位置情報と同一である。例えば、図5(a)の行列の、第2行第4列の要素b124の値「11」(二進数)は、第2行第3列の要素b123の値「11」(二進数)と、第1行第4列の要素b114の値「1」(二進数)とのうち、LCS長が長い文字列に対応する、第2行第3列の要素b123の値「11」(二進数)と同一である。
いずれの文字列から末尾の文字を除いてもLCS長が同一の場合は、いずれの文字位置情報と同一としてもよい。本実施形態では、値が小さいほうの文字位置情報と同一とする。後述するように、LCSに含まれる文字が先頭に近い位置に出現する用語を上位とするためである。
【0033】
このように、図5(a)の行列の各要素の値は、入力文字列中の対応する文字と、用語中の対応する文字とが同じ場合は、左上の要素の値に、用語の末尾の位置に対応する桁を1とした数を加えた値と同一である。一方、入力文字列中の対応する文字と、用語中の対応する文字とが異なる場合は、左隣の要素の値と、上隣の要素の値とのうち、LCS長が長いほうの値と同一(両者のLCS長が同一の場合は、値が小さいほうの要素の値と同一。さらに両要素の値が同一の場合は、両要素の値と同一)である。
【0034】
ここで、図4で説明したように、入力文字列「大腸粘液癌」のうち、文字「液」は、用語「大腸粘膜内癌」と共通しておらず、LCS「大腸粘癌」には含まれない。このため、図4で説明したLCS長の場合と同様、用語「大腸粘膜内癌」またはその部分文字列のいずれについても、入力文字列の部分文字列「大腸粘液」との文字位置情報は、文字「液」を除いた「大腸粘」との文字位置情報と同一である。例えば、用語の部分文字列「大腸粘膜内」について見ると、この「大腸粘膜内」と「大腸粘液」とのLCSは「大腸粘」であり、文字位置情報は(要素b145の値)「111」(二進数)である。そして、「大腸粘膜内」と、「大腸粘液」から「液」を除いた「大腸粘」とのLCSも「大腸粘」であり、文字位置情報は(要素a135の値)「111」(二進数)である。
このため、図5(a)の行列の第4行(文字「液」に対応する行)の値は、上隣の第3行(文字「粘」に対応する行)の値と一致する。
【0035】
このように、入力文字列のうち、用語に含まれない文字に対応する、図5(a)の行列中の行の値は、上隣の行の値と一致する。そこで、文字位置情報行列記憶部134は、図5(a)の行列から、用語に含まれない文字に対応する行を削除した行列を、文字位置情報行列として記憶する。この文字位置情報行列の最下行最右列の要素の値は、図5(a)の行列の最下行最右列の要素の値と一致する。すなわち、文字位置情報行列の最下行最右列の要素の値は、入力文字列と用語とのLCSが用語中に出現する位置を示す文字位置情報を示している。
例えば、文字位置情報行列記憶部134は、図5(a)の行列から、用語に含まれない文字「液」を削除した図5(b)の文字位置情報行列を記憶する。この行列の最下行最右列の要素b246の値「100111」は、入力文字列「大腸粘液癌」と用語「大腸粘膜内癌」とのLCS「大腸粘癌」に含まれる各文字が、用語「大腸粘膜内癌」中に出現する位置を示している。
後述するように、文字列情報行列は、文字インデックス記憶部132が記憶する文字インデックスを用いて生成される。
【0036】
図1に戻って、処理部120は、通信部110を介して、ユーザが入力済みの文字列を端末装置200から取得し、取得した文字列に基づいて、ユーザが入力したい文字列の候補の各々の順位を決定する。そして、処理部120は、ユーザが入力したい文字列の候補を、決定した順位に従って並べたリストを生成し、通信部110を介して端末装置200に送信する。処理部120は、例えば、文字列入力支援装置100の具備するCPUが、記憶部130からプログラムを読み出して実行することにより実現される。
処理制御部121は、各部を制御して処理を行わせる。文字インデックス生成部122は、用語記憶部131の記憶する用語リストに基づいて文字インデックスを生成する。LCS長算出部123は、入力文字列と、用語記憶部131が記憶する各用語とのLCS長を算出する。文字位置情報生成部124は、入力文字列と、用語記憶部131が記憶する各用語との文字位置情報を生成する。順位決定部125は、LCS長算出部123が算出するLCS長および文字位置情報生成部124が生成する文字位置情報に基づいて、用語記憶部131が記憶する各用語の順位を決定する。
【0037】
端末装置200は、ユーザによる文字列の入力を受け付けて文字列入力支援装置100に送信し、文字列入力支援装置100から送信される用語(ユーザが入力しようとしている文字列の候補)を、文字列入力支援装置100が決定した順位に従って表示する。
通信部210は、文字列入力支援装置100との間でデータの送受信を行う。
入力部220は、キーボードおよびマウスを備え、ユーザによる文字列の入力を受け付けて、入力された文字列を、通信部210を介して文字列入力支援装置100に送信する。表示部230は、液晶ディスプレイ等の表示画面を備え、文字列の入力欄を表示し、ユーザの入力した文字列を入力欄に表示する。また、表示部230は、順位付けされた用語を、通信部210を介して文字列入力支援装置100から受信し、受信した用語を、その順位に従って入力欄の下方近傍に表示する。
【0038】
次に、文字列入力支援システム1の動作について説明する。
文字列入力支援システム1では、文字列入力支援装置100の文字インデックス生成部122が、用語記憶部131の記憶する用語リストに基づいて、予め文字インデックスを生成し、文字インデックス記憶部132に書き込んでおく。
図6は、文字インデックス生成部122が文字インデックスを生成する処理手順を示すフローチャートである。
文字インデックス生成部122は、まず、用語記憶部131が記憶する用語リストの各行に対する処理を行うループL1の処理を開始する。以下では、ループL1にて処理対象となっている用語を「W」にて表示し、用語Wの用語IDリストを「i」にて表示する(以上、ステップS1)。
【0039】
そして、文字インデックス生成部122は、用語Wに含まれる各文字に対する処理を行うループL2の処理を開始する。以下では、ループL2にて処理対象となっている文字を「R」にて表示する(以上、ステップS2)。
そして、文字インデックス生成部122は、文字インデックスの行を示す変数kの値を1に設定する(ステップS3)。
【0040】
次に、文字インデックス生成部122は、文字インデックス記憶部132が記憶する文字インデックスに第k行が存在するか否かを判定する(ステップS4)。存在すると判定した場合(ステップS4:YES)、文字インデックス生成部122は、文字インデックスの第k行に含まれる文字と文字Rとが一致するか否かを判定する。一致しないと判定した場合(ステップS5:NO)、文字インデックス生成部122は、kに1を加え、すなわち文字インデックスの次の行を対象に設定し(ステップS31)、ステップS4に戻る。
【0041】
一方、ステップS5にて一致すると判定した場合(ステップS5:YES)、文字インデックス生成部122は、文字インデックスの第k行に含まれる用語IDリストに、iが含まれるか否かを判定する。このように、既にiが含まれているか否かを判定するのは、重複記載を避けるためである(以上、ステップS6)。含まれないと判定した場合(ステップS6:NO)、文字インデックス生成部122は、文字インデックス記憶部132が記憶する、文字インデックスの第k行に含まれる用語IDリストに、iを追加する(書き込む)(ステップS7)。
【0042】
その後、文字インデックス生成部122は、用語Wの全ての文字に対してループL2の処理を行ったか否かを判定する。未処理の文字があると判定した場合は、ステップS2に戻って、未処理の文字に対して引き続きループL2の処理を行う。一方、全ての文字に対して処理を行ったと判定した場合は、次のステップS9に進む(以上、ステップS8)。
そして、文字インデックス生成部122は、用語リストの全ての行に対してループL1の処理を行ったか否かを判定する。未処理の行があると判定した場合は、ステップS1に戻って、未処理の行に対して引き続きループL1の処理を行う。一方、全ての行に対して処理を行ったと判定した場合は、同図の処理を終了する(以上、ステップS9)。
【0043】
一方、ステップS4において、文字インデックス記憶部132が記憶する文字インデックスに第k行が存在しないと判定した場合(ステップS4:NO)、および、ステップS6において、文字インデックスの第k行に含まれる用語IDリストに、iが含まれていると判定した場合(ステップS6:YES)は、ステップS8に進む。
また、ステップS4において、文字インデックス記憶部132が記憶する文字インデックスに第k行が存在しないと判定した場合(ステップS4:NO)は、文字インデックス記憶部132が記憶する文字インデックスの末尾に、文字Rと、iから成る用語IDリストとを含む行を追加する(書き込む)。
【0044】
文字インデックスの生成を完了すると、端末装置200の表示部230が入力欄を表示し、入力部220がユーザの入力操作を待ち受ける。入力部220は、ユーザの入力操作を受けると、当該操作に基づいて、入力文字列を生成する。すなわち、入力部220は、過去の入力操作に基づく入力文字列を記憶しており、文字の追加や削除等の新たな入力操作を受けると、記憶している入力文字列を当該操作に基づいて更新(編集)する。入力部220は、更新された入力文字列を、表示部230および通信部210に出力する。
表示部230は、入力部220から出力された入力文字列を入力欄に表示(既に入力文字列を表示しているときは更新)する。また、通信部210は、入力部220から出力された入力文字列を、文字列入力支援装置100の通信部110に送信する。
通信部110は、通信部210からの入力文字列を受信すると、受信した入力文字列を処理部120に出力する。
【0045】
処理部120は、通信部110から出力される入力文字列と、用語記憶部131の記憶する各用語とのLCS長の算出および文字位置情報の生成を行う。
図7および図8は、処理部120がLCS長を算出し、文字位置情報を生成する処理手順を示すフローチャートである。処理部120は、通信部110から入力文字列が出力されると同図の処理を開始する。
まず、処理部120の処理制御部121は、LCS長行列記憶部133のLCS長行列を初期化するようLCS長算出部123を制御し、文字位置情報行列記憶部134の文字位置情報行列を初期化するよう文字位置情報生成部124を制御する。
【0046】
LCS長算出部123は、用語記憶部131が記憶する用語の各々について、LCS長行列の行数を入力文字列の文字数+1とし、列数を当該用語の文字数+1とする。そして、最上行(図4の例で、「初期値」に対応する行)の各要素の値と、最左列(図4の例で、「初期値」に対応する列)の各要素の値とを、いずれも「0」とする。他の要素の値は、この時点では未定である。
また、文字位置情報生成部124は、用語記憶部131が記憶する用語の各々について、文字位置情報行列の行数を入力文字列の文字数+1とし、列数を当該用語の文字数+1とする。そして、最上行(図5の例で、「初期値」に対応する行)の各要素の値と、最左列(図5の例で、「初期値」に対応する列)の各要素の値とを、いずれも「0」とする。他の要素の値は、この時点では未定である(以上、ステップS101)。
【0047】
次に、処理制御部121は、入力文字列の各文字について先頭から順に処理を行うループL11の処理を開始する。以下では、ループL11にて処理対象となっている文字の位置を「j」(先頭から順に、1、2、・・・とする)にて表示する。(以上、ステップS102)。
次に、処理制御部121は、文字インデックス記憶部132が記憶する文字インデックスの中から、入力文字列の先頭からj番目の文字と同じ行に格納されている用語IDリスト(文字インデックス中に、該当する行が無い場合は空のリスト)を読み出す(ステップS103)。
そして、処理制御部121は、ステップS103で取得した用語IDリストに含まれる用語IDに対応する各用語について処理を行うループL12の処理を開始する。以下では、ループL12にて処理対象となっている用語を「W」にて表示する(以上、ステップS104)。
【0048】
次に、処理制御部121は、算出済みのLCS長、すなわち、LCS長行列記憶部133の記憶するLCS長行列のうち、用語Wに対応するLCS長行列の、値が確定している行の最右の要素の値を読み出す。後述するように、この算出済みのLCS長は、入力文字列の部分文字列と、用語WとのLCS長である。また、処理制御部121は、入力文字列に含まれる文字のうち、処理が終わっていない文字の数(入力文字列の文字数−k+1)を算出する。そして、処理制御部121は、算出済みのLCS長と、入力文字列に含まれる文字のうち処理が終わっていない文字の数との合計値が、予め定められた閾値以上か否かを判定する。
この閾値は、入力文字列と用語とのLCS長に対する閾値であり、LCS長が閾値以上の用語のみが、ユーザの入力したい文字列の候補として端末装置200の表示部230に表示される。この閾値は、例えばユーザによって予め設定される(以上、ステップS105)。
算出済みのLCS長と、入力文字列に含まれる文字のうち処理が終わっていない文字の数との合計値が、閾値以上であると判定した場合(ステップS105:YES)、処理制御部121は、用語Wの各文字について先頭から順に処理を行うループL13の処理を開始する。以下では、ループL11にて処理対象となっている文字の位置を「k」(先頭から順に、1、2、・・・とする)にて表示する。(以上、ステップS106)。
【0049】
そして、処理制御部121は、入力文字列のj番目の文字と、用語Wのk番目の文字とが同一か否かを判定する(ステップS107)。同一であると判定した場合(ステップS107:YES)、処理制御部121は、文字が同一であることを示す信号を、LCS長算出部123に出力する。
文字が同一であることを示す信号が処理制御部121から出力されると、LCS長算出部123は、LCS長行列の第j行第k列の要素の値として、第j−1行第k−1列の要素の値+1を書き込む。すなわち、図4で説明したように、左上の要素の値に1を加えた値とする(以上、ステップS111)。
【0050】
また、ステップS107において文字が同一であると判定した(ステップS107:YES)処理制御部121は、文字が同一であることを示す信号を、文字位置情報生成部124にも出力する。
文字が同一であることを示す信号が処理制御部121から出力されると、文字位置情報生成部124は、文字位置情報行列の第j行第k列の要素の値として、第j−1行第k−1列の要素の値+2k−1を書き込む。すなわち、図5で説明したように、左上の要素の値に、用語の末尾の位置に対応する桁を1とした数を加えた値とする(以上、ステップS112)。
【0051】
その後、処理制御部121は、用語Wの全ての文字に対してループL13の処理を行ったか否かを判定する。未処理の文字があると判定した場合は、ステップS106に戻って、未処理の文字に対して引き続きループL13の処理を行う。一方、全ての文字に対して処理を行ったと判定した場合は、次のステップS142に進む。
この、ループL13の終了時点では、入力文字列の先頭からj文字目までの部分文字列と、用語WとのLCSが算出されている。例えば、入力文字列が「大腸粘膜癌」、用語Wが「大腸粘膜内癌」で、j=2の場合、図4に示したLCS長行列のうち上3行(初期値の行と、入力文字列「大」および「腸」に対応する行)が生成されている。このLCS長行列の最下行最右列の要素の値「2」は、入力文字列の先頭から2文字の部分文字列「大腸」と用語W「大腸粘膜内癌」とのCLS長(CLSは「大腸」であり、CLS長は「2」)を示している(以上、ステップS141)。
【0052】
そして、処理制御部121は、用語記憶部131の記憶する全ての用語に対してループL12の処理を行ったか否かを判定する。未処理の用語があると判定した場合は、ステップS104に戻って、未処理の用語に対して引き続きループL12の処理を行う。一方、全ての用語に対して処理を行ったと判定した場合は、次のステップS143に進む(以上、ステップS142)。
そして、処理制御部121は、入力文字列の全ての文字に対してループL11の処理を行ったか否かを判定する。未処理の文字があると判定した場合は、ステップS102に戻って、未処理の文字に対して引き続きループL11の処理を行う。一方、全ての文字に対して処理を行ったと判定した場合は、同図の処理を終了する(以上、ステップS143)。
【0053】
一方、ステップS105において、閾値未満であると判定した場合(ステップS105:NO)、処理制御部121は、ステップS141に進む。すなわち、入力文字列に含まれる文字のうち、まだLCS長算出に用いられていない文字が全てLCSを構成すると仮定しても処理対象の用語のLCS長が閾値未満である場合、残りの文字について処理をするまでもなく、この用語のLCS長が最終的に閾値未満となることが明らかである。すなわち、この用語は端末装置200の表示部230には表示されないことが確定している。そこで、処理部120は、この用語に対するLCS長の算出および文字位置情報の生成を中止して、全体の処理の迅速化を図る。
【0054】
また、ステップS107において文字が異なると判定した場合(ステップS107:NO)、処理制御部121は、LCS長行列の第j−1行第k列の要素の値が、第j行第k−1列の要素の値以上か否かを判定する(ステップS121)。第j−1行第k列の要素の値が、第j行第k−1列の要素の値以上であると判定した場合(ステップS121:YES)、処理制御部121は、第j−1行第k列の要素の値が、第j行第k−1列の要素の値以上であることを示す信号を、LCS長算出部123に出力する。
当該信号が処理制御部121から出力されると、LCS長算出部123は、LCS長行列の第j行第k列の要素の値として、第j−1行第k列の要素の値を書き込む。すなわち、図4で説明したように、左隣の値と、上隣の値とのうち大きいほう(ここでは、上隣の要素)の値と同一(両者の値が等しい場合は、両者の値と同一)とする(以上、ステップS122)。
【0055】
また、ステップS121において、第j−1行第k列の要素の値が、第j行第k−1列の要素の値以上であると判定した(ステップS121:YES)処理制御部121は、LCS長行列の第j−1行第k列の要素の値が、第j行第k−1列の要素の値と等しいか否かを判定する(ステップS123)。値が等しいと判定した場合(ステップS123:YES)、処理制御部121は、さらに、文字位置情報行列の第j−1行第k列の要素の値が、第j行第k−1列の要素の値以下か否かを判定する(ステップS124)。
ステップS123において両者の値が異なると判定した場合(ステップS123:NO)、および、ステップS124において、第j−1行第k列の要素の値が、第j行第k−1列の要素の値以下であると判定した場合(ステップS124:YES)、処理制御部121は、上隣の要素を書き込むよう指示する信号を、文字位置情報生成部124に出力する。
当該信号が処理制御部121から出力されると、文字位置情報生成部124は、文字位置情報行列の第j行第k列の要素の値として、第j−1行第k列の要素の値を書き込む。すなわち、図5で説明したように、左隣の要素の値と、上隣の要素の値とのうち、LCS長が長いほう(ここでは、上隣の要素)の値と同一(両者のLCS長が同一の場合は、値が小さいほうの要素の値と同一。さらに両要素の値が同一の場合は、両要素の値と同一)とする(以上、ステップS125)。
その後、処理制御部121は、ステップS141に進む。
【0056】
一方、ステップS121において、第j−1行第k列の要素の値が、第j行第k−1列の要素の値未満であると判定した場合(ステップS121:NO)、処理制御部121は、第j−1行第k列の要素の値が、第j行第k−1列の要素の値未満であることを示す信号を、LCS長算出部123に出力する。
当該信号が処理制御部121から出力されると、LCS長算出部123は、LCS長行列の第j行第k列の要素の値として、第j行第k−1列の要素の値を書き込む。すなわち、図4で説明したように、左隣の値と、上隣の値とのうち大きいほう(ここでは、左隣の要素)の値と同一とする(以上、ステップS131)。
【0057】
また、ステップS121において、第j−1行第k列の要素の値が、第j行第k−1列の要素の値未満であると判定した場合(ステップS121:NO)、および、ステップS124において、第j−1行第k列の要素の値が、第j行第k−1列の要素の値より大きいと判定した場合(ステップS124:NO)、処理制御部121は、左隣の要素を書き込むよう指示する信号を、文字位置情報生成部124に出力する。
当該信号が処理制御部121から出力されると、文字位置情報生成部124は、文字位置情報行列の第j行第k列の要素の値として、第j行第k−1列の要素の値を書き込む。すなわち、図5で説明したように、左隣の要素の値と、上隣の要素の値とのうち、LCS長が長いほう(ここでは、左隣の要素)の値と同一(両者のLCS長が同一の場合は、値が小さいほうの要素の値と同一)とする(以上、ステップS132)。
その後、処理制御部121は、ステップS141に進む。
【0058】
以上により、LCS長行列および文字位置情報行列が完成する。そして、LCS長行列の最上行最右列の要素の値が、対応する用語のLCS長を示し、文字位置情報行列の最上行最右列の要素の値が、対応する用語中における、LCSに含まれる文字の出現位置、すなわち文字位置情報を示している。
【0059】
なお、図7のステップS105で用語の絞込みを行わない場合(例えば、閾値の値が「0」または「1」に設定されている場合)は、処理部120が、LCS長行列と文字位置情報行列とを常に新たに生成するのではなく、生成済みのLCS長行列および文字位置情報行列を更新するようにしてもよい。例えば、ユーザの操作入力により入力文字列の末尾に新たに1文字追加された場合、処理部120に入力される入力文字列のうち、末尾の文字を除いた部分文字列は、前回の入力文字列と同一である。そこで、LCS長算出部123が、各LCS長行列の末尾に行を追加し、文字位置情報生成部124が、各文字位置情報行列の末尾に行を追加するようにしてもよい。そして、処理部120は、新たに入力された入力文字列の末尾の文字に基づき、ループL12の処理手順に従って、LCS長行列および文字位置情報行列を完成させる。
【0060】
LCS長行列および文字位置情報行列が完成すると、処理制御部121は、用語記憶部131の記憶する各用語の順位を決定するように順位決定部125を制御する。
順位決定部125は、用語記憶部131の記憶する各用語の、LCS長と、文字位置情報と、用語の長さ(文字数)と、用語リストにおける順序(用語IDの値)とに基づいて、順位を決定し、決定した順位に基づいて並べられた用語のリストを生成する。
図9は、順位決定部125による用語の順位決定の例を示す図である。同図は、入力文字列が「大腸癌」である場合の例であり、図1に示す用語リストに含まれる用語のうちLCS長が3以上の用語と、各用語の順位と、順位を決定する基準となるLCS長と文字位置情報と用語の文字数と用語IDとを示している。
【0061】
順位決定部125は、まず、LCS長が閾値以上の用語のみを、端末装置200の表示部230に表示する用語として選択する。具体的には、順位決定部125は、LCS長行列記憶部133が記憶する各LCS長行列の最下行最右列の要素と閾値とを比較し、閾値以上の値を示すLCS長行列に対応する用語のみを選択する。ここで、LCS長行列記憶部133が記憶するLCS長行列の中には、図7のステップS105における判定の結果、LCS長算出処理が中止されているLCS長行列もある。このLCS長行列の最下行最右列の要素は、実際のLCS長よりも小さい値を示す場合がある。しかし、図7(ステップS105:NO)で説明したように、このLCS長行列に対応する用語は、LCS長が閾値未満となることが確定している用語であり、順位決定部125の選択には影響しない。
【0062】
次に順位決定部125は、選択した各用語に対して、LCS長が長いほど上位とし(上位の用語ほど高い優先順位である、すなわち表示部230の入力欄に近い位置に表示されやすくなる)、LCS長が同じ用語に対しては、文字位置情報の値が小さい用語を上位とする。さらに、LCS長および文字位置情報の値が同じ用語に対しては、用語の文字数が少ない用語を上位とし、用語の文字数も同じである用語に対しては、用語IDの小さい用語を上位とする。
上述したように、LCS長は入力文字列と用語との類似度を示す情報として用いることができる。従って、LCS長が長い用語ほど上位とすることで、入力文字列と類似度の高い用語を上位とすることができ、ユーザが入力したい文字列の候補を適切に提示できる。
また、ユーザは、通常、入力したい文字列の先頭から順に入力する。したがって、入力済みの文字列とのLCSが先頭付近に出現する用語のほうが、末尾付近に出現する用語よりも、ユーザが入力したい文字列の候補として適切である。文字位置情報の値が小さい用語を上位とすることで、入力済みの文字列とのLCSが先頭付近に出現する用語を上位とすることができ、ユーザが入力したい文字列の候補を適切に提示できる。
【0063】
順位決定部125は、例えば、順位を示す指標を用語毎に生成し、生成した指標に基づいて用語を並べ替える。
図10は、順位決定部125が生成する指標の例を示す図である。
同図に示す指標は、LCSの長さ(二進数表示)と、小数点と、文字位置情報(二進数表示)の2の補数と、用語の長さ(二進数表示)の2の補数と、用語ID(二進数表示)の2の補数とが、この順に結合されて生成される。その際、順位決定部125は、文字位置情報(二進数表示)の桁数を、当該用語文字数に揃える。また、用語の長さ(二進数表示)の桁数を、用語記憶部131が記憶する用語のうち最長のものを表現可能な桁数に揃える。また、用語ID(二進数表示)の桁数を、用語記憶部131が記憶する用語IDのうち最大のものを表現可能な桁数に揃える。
【0064】
また、同図の値は、入力文字列が「大腸癌」である場合に、用語「大腸粘膜内癌」に対して生成される指標の値を示している。
「大腸癌」の文字数は「3」であるため、同図に示す指標の整数部分は「11」となっており、また、小数部分は、文字位置情報「100011」の2の補数「011100」と、用語の長さ「6」の二進数表示「0・・・0110」の2の補数「1・・・1001」と、用語ID「5」の二進数表示「0・・・0101」の2の補数「1・・・1010」とを結合した値となっている。2の補数を取ることにより、元となる値が小さいほど大きい値の指標が生成される。
【0065】
順位決定部125が、この指標の大きい順に用語を並べ替えることにより、各用語は、LCSの長さが長い順に並べられ、LCSの長さが同一の場合は、文字位置情報の値が小さい順に並べられ、文字位置情報の値も同一の場合は、用語の長さが短い順に並べられ、用語の長さも同一の場合は、用語IDの値が小さい順に並べられる。
ここで、LCSに含まれる文字が用語に出現する位置のうち、最も後ろ(用語の末尾側)の位置が先頭に近い用語ほど、文字位置情報の値が小さくなる。また、LCSに含まれる文字が用語に出現する位置のうち、最も後ろの出現位置が同一の場合は、後ろから2番目の出現位置が先頭に近い用語ほど、文字位置情報の値が小さくなる。同様に、1〜i−1(iはLCS長以下の正整数)番目の各出現位置が同一の場合は、i番目の出現位置が先頭に近い用語ほど、文字位置情報の値が小さくなる。この点で、文字位置情報生成部124は、LCSに含まれる文字が用語中に出現する位置が先頭に近いほど小さい値を示す文字位置情報を生成する。
【0066】
順位決定部125は、並べ替えた用語を並べ替えた順に含むリストを生成し、通信部110を介して端末装置200に送信する。
端末装置200の通信部210は、順位決定部125からの用語のリストを受信すると、受信したリストを表示部230に出力する。表示部230は、通信部210から出力される用語のリストを、入力欄の下方近傍に表示する。
【0067】
図11は、表示部230が用語のリストを表示した例を示す図である。同図では、入力文字列が「大腸癌」である場合に、図2に示した用語リストの用語のうち、LCS長が3以上の用語を表示した例が示されている。順位決定部125は、設定されている閾値「3」に基づいて用語の絞込みを行い、さらに、図9で示した順位に従って用語を並べ替え、並べ替えた順に用語を含むリストを生成する。そして、表示部230がこのリストを表示する。
ユーザが、このリストに含まれる用語のいずれかを、マウスでクリックする等により選択すると、入力部220は、選択された用語を入力文字列として表示部230と通信部210に出力する。以下、各部は上述した処理を行う。
【0068】
以上のように、文字列入力支援装置100の文字インデックス記憶部132は、用語記憶部131の記憶する用語に含まれる文字の各々について、当該文字を含む用語を示す文字インデックスを予め記憶しておく。そして、処理部120は、ユーザが入力したい文字列の候補のリストを生成する際に、文字インデックスに基づいて処理対象となる用語の選択(絞込み)を行う。これにより、高速に、かつ、LCS長が所定の閾値以上の全ての用語を対象として適切に、ユーザの入力したい文字列の候補を得られる。
【0069】
また、処理部120は、入力文字列の部分文字列と用語とのLCS長を算出し、算出したLCS長に基づいて、当該用語に関する類似度を示す情報の生成を中止するか否かを決定する。具体的には、入力文字列のうち未処理の文字の数と、算出したLCS長との合計値が、予め定められた閾値未満の場合に、当該用語について、LCS長の算出および文字位置情報の生成を中止する。これにより、高速に、かつ、LCS長が閾値以上の全ての用語を対象として適切に、ユーザの入力したい文字列の候補を得られる。
【0070】
なお、LCS長算出部123が生成する類似度を示す情報は、上述したLCS長に限らず、ある文字が用語に含まれるか否かに基づいて再帰的に生成されるものであればよい。例えば、入力文字列と用語とに共通して出現する文字数(LCS長の算出において、文字の並びが同順であるとの条件を不要としたもの)を、上述したLCS長の算出と同様に、入力文字列の部分文字列について再帰的に算出するようにしてもよい。
【0071】
なお、処理制御部121が、用語リストに含まれる用語のうち、入力文字列に含まれる全ての用語を、ユーザの入力したい文字列の候補として選択するようにしてもよい。この場合、処理制御部121は、図7のループ12において、用語IDリストに基づいて得られる全ての用語を、ユーザの入力したい文字列の候補として選択する。
【0072】
なお、上述したように、文字列入力支援装置100は、コンピュータによって実現するようにしてもよい。すなわち、文字列入力支援装置100の全部または一部の機能を実現するためのプログラムをコンピュータ読み取り可能な記録媒体に記録して、この記録媒体に記録されたプログラムをコンピュータシステムに読み込ませ、実行することにより各部の処理を行ってもよい。なお、ここでいう「コンピュータシステム」とは、OSや周辺機器等のハードウェアを含むものとする。
また、「コンピュータシステム」は、WWWシステムを利用している場合であれば、ホームページ提供環境(あるいは表示環境)も含むものとする。
また、「コンピュータ読み取り可能な記録媒体」とは、フレキシブルディスク、光磁気ディスク、ROM、CD−ROM等の可搬媒体、コンピュータシステムに内蔵されるハードディスク等の記憶装置のことをいう。さらに「コンピュータ読み取り可能な記録媒体」とは、インターネット等のネットワークや電話回線等の通信回線を介してプログラムを送信する場合の通信線のように、短時間の間、動的にプログラムを保持するもの、その場合のサーバやクライアントとなるコンピュータシステム内部の揮発性メモリのように、一定時間プログラムを保持しているものも含むものとする。また上記プログラムは、前述した機能の一部を実現するためのものであっても良く、さらに前述した機能をコンピュータシステムにすでに記録されているプログラムとの組み合わせで実現できるものであっても良い。
【0073】
以上、この発明の実施形態を図面を参照して詳述してきたが、具体的な構成はこの実施形態に限られるものではなく、この発明の要旨を逸脱しない範囲の設計変更等も含まれる。
【符号の説明】
【0074】
1 文字列入力支援システム
100 文字列入力支援装置
110 通信部
120 処理部
121 処理制御部
122 文字インデックス生成部
123 LCS長算出部
124 文字位置情報生成部
125 順位決定部
130 記憶部
131 用語記憶部
132 文字インデックス記憶部
133 LCS長行列記憶部
134 文字位置情報行列記憶部
200 端末装置
210 通信部
220 入力部
230 表示部




【特許請求の範囲】
【請求項1】
第1の文字列を取得する取得部と、
1つ以上の第2の文字列の各々と、当該第2の文字列を識別する文字列識別情報とが対応付けられた識別情報付文字列群を記憶する文字列群記憶部と、
前記識別情報付文字列群中の前記第2の文字列に含まれる全ての文字について、異なる前記文字毎に、当該文字と、当該文字を含み前記識別情報付文字列群に含まれる前記第2の文字列の文字列識別情報と、が対応付けられた文字インデックスを記憶する文字インデックス記憶部と、
前記第1の文字列に含まれる文字に、前記文字インデックスにて対応付けられた前記文字列識別情報により識別される前記第2の文字列を選択する文字列選択部と、
を具備することを特徴とする文字列選択装置。
【請求項2】
前記文字列選択部は、前記選択した第2の文字列に含まれる文字と、前記第1の文字列に含まれる文字とに共通する文字の文字数を示す文字数情報を生成することを特徴とする請求項1に記載の文字列選択装置。
【請求項3】
前記文字列選択部は、前記第1の文字列の部分文字列に含まれる文字と、前記第2の文字列に含まれる文字とに共通する文字の文字数を示す文字数情報を生成し、当該文字数情報と、前記第1の文字列に含まれる文字数と前記部分文字列に含まれる文字数との差と、に基づいて定まる値が、予め定められた閾値未満の場合に、前記第1の文字列と当該第2の文字列との前記類似度を示す情報の生成を中止することを特徴とする請求項1または請求項2に記載の文字列選択装置。
【請求項4】
1つ以上の第2の文字列の各々と、当該第2の文字列を識別する文字列識別情報とが対応付けられた識別情報付文字列群を記憶する文字列群記憶部と、
前記識別情報付文字列群中の前記第2の文字列に含まれる全ての文字について、異なる前記文字毎に、当該文字と、当該文字を含み前記識別情報付文字列群に含まれる前記第2の文字列の文字列識別情報と、が対応付けられた文字インデックスを記憶する文字インデックス記憶部と、
を具備する文字列選択装置の文字列選択方法であって、
取得部が、第1の文字列を取得する取得ステップと、
文字列選択部が、前記第1の文字列に含まれる文字に、前記文字インデックスにて対応付けられた前記文字列識別情報により識別される前記第2の文字列を選択する文字列選択ステップと、
を具備することを特徴とする文字列選択方法。
【請求項5】
1つ以上の第2の文字列の各々と、当該第2の文字列を識別する文字列識別情報とが対応付けられた識別情報付文字列群を記憶する文字列群記憶部と、
前記識別情報付文字列群中の前記第2の文字列に含まれる全ての文字について、異なる前記文字毎に、当該文字と、当該文字を含み前記識別情報付文字列群に含まれる前記第2の文字列の文字列識別情報と、が対応付けられた文字インデックスを記憶する文字インデックス記憶部と、
を具備する文字列選択装置としてのコンピュータに、
第1の文字列を取得する取得ステップと、
前記第1の文字列に含まれる文字に、前記文字インデックスにて対応付けられた前記文字列識別情報により識別される前記第2の文字列を選択する文字列選択ステップと、
を実行させるためのプログラム。


【図1】
image rotate

【図2】
image rotate

【図3】
image rotate

【図4】
image rotate

【図5】
image rotate

【図6】
image rotate

【図7】
image rotate

【図8】
image rotate

【図9】
image rotate

【図10】
image rotate

【図11】
image rotate

【図12】
image rotate


【公開番号】特開2011−257921(P2011−257921A)
【公開日】平成23年12月22日(2011.12.22)
【国際特許分類】
【出願番号】特願2010−131071(P2010−131071)
【出願日】平成22年6月8日(2010.6.8)
【出願人】(000102728)株式会社エヌ・ティ・ティ・データ (438)
【Fターム(参考)】