(57)【要約】【課題】ユーザや入力状況に個別的に適応して文字列入力を容易にするのに好適な文字列入力装置等を提供する。【解決手段】符号入力部１０２は、ユーザからの符号入力を受け付け、候補辞書部１０３は、受け付けられた符号入力に対応付けてあらかじめ記憶された文字列を取得して、これを接頭辞として候補抽出部１０４に与え、候補抽出部１０４は、対象文書の入力を受け付け、接頭辞の入力を受け付け、当該対象文書に出現する部分文字列であって、当該接頭辞を接頭辞とするものを、候補文字列として出力し、候補選択部１０５は、候補辞書部１０３から取得された文字列と、候補抽出部１０４から出力された候補文字列と、を文字列入力の候補文字列として表示し、これらの候補文字列から、ユーザにいずれかを選択させ、入力結果出力部１０６は、選択された候補文字列を、入力結果として出力する。【選択図】  図１
2004164120.tif 000002
【特許請求の範囲】
【請求項１】
対象文書入力受付部と、接頭辞入力受付部と、抽出部と、を備える、接頭最長重複文字列を抽出する抽出装置であって、
「ある文書における、ある接頭辞に対する、接頭最長重複文字列」とは、「当該接頭辞を接頭辞とし、当該文書に２回以上出現する部分文字列（以下「接頭重複文字列」という。）であって、他の接頭重複文字列の接頭辞となっていないもの」をいい、
前記対象文書入力受付部は、対象文書の入力を受け付け、
前記接頭辞入力受付部は、接頭辞の入力を受け付け、
前記抽出部は、前記入力を受け付けられた対象文書における、前記入力を受け付けられた接頭辞に対する、接頭最長重複文字列を抽出する
ことを特徴とするもの。
【請求項２】
候補抽出部と、候補選択部と、入力結果出力部と、を備える文字列入力装置であって、
前記候補抽出部は、対象文書の入力を受け付け、接頭辞の入力を受け付け、当該対象文書に出現する部分文字列であって、当該接頭辞を接頭辞とするものを、候補文字列として出力し、
前記候補選択部は、前記出力された候補文字列を含む候補文字列から、いずれかを選択し、
前記入力結果出力部は、前記選択された候補文字列を、入力結果として出力する
ことを特徴とするもの。
【請求項３】
請求項２に記載の文字列入力装置であって、符号入力部と、候補辞書部と、をさらに備え、
前記符号入力部は、ユーザからの符号入力を受け付け、
前記候補辞書部は、前記受け付けられた符号入力に対応付けてあらかじめ記憶された文字列を取得して、これを接頭辞として前記候補抽出部に与え、
前記候補選択部は、前記取得された文字列を候補文字列にさらに含める
ことを特徴とするもの。
【請求項４】
請求項２または３に記載の文字列入力装置であって、
前記候補抽出部は、請求項１に記載の文字列抽出装置に、当該対象文書を入力として与え、当該接頭辞を入力として与え、当該抽出された接頭最長重複文字列を候補文字列として出力する
ことを特徴とするもの。
【請求項５】
請求項２または３に記載の文字列入力装置であって、部分文字列の抽出装置をさらに備え、
前記部分文字列の抽出装置は、文字列入力受付部と、開始位置受付部と、評価値計算部と、抽出部と、を備え、
前記文字列入力受付部は、長さＮ  （Ｎ≧１）の文字列
ｓ  ＝  Ｘ１，…，ＸＮ
の入力を受け付け、
前記開始位置受付部は、前記入力を受け付けられた文字列における開始位置ｋ  （１≦ｋ≦Ｎ）の入力を受け付け、
前記評価値計算部は、長さｉ  （１≦ｉ≦Ｎ−ｋ＋１）の部分文字列
ｓｉ  ＝  Ｘｋ，…，Ｘｋ＋ｉ−１
について、当該部分文字列ｓｉのｓにおける出現頻度Ｎｉと、ｓにおいて当該部分文字列ｓｉに続いて出現する文字の種類の数Ｃｉとから、評価値
ＳＣ（ｓｉ）  ＝  ｌｏｇ（ｉ＋１）×ｌｏｇ（Ｎｉ）×（１−１／Ｃｉ）
を計算し、
前記抽出部は、前記計算された評価値が
ＳＣ（ｓｉ＋１）  ＞  ＳＣ（ｓｉ）
を満たす場合、当該部分文字列ｓｉ＋１を抽出し、
前記候補抽出部は、前記部分文字列の抽出装置に、当該対象文書を文字列の入力として与え、当該接頭辞が当該対象文書において出現する場所のそれぞれについて、これに続く位置を開始位置の入力として与え、当該出現する位置から当該抽出された部分文字列の終了位置までの部分文字列を、候補文字列として出力する
ことを特徴とするもの。
【請求項６】
コンピュータを、請求項１に記載の抽出装置、または、請求項２から７のいずれか１項に記載の文字列入力装置として機能させることを特徴とするプログラム。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、対象文書から接頭最長重複文字列を抽出する抽出装置、文字列入力装置、ならびに、これらをコンピュータ上にて実現するプログラムに関する。
【０００２】
【従来の技術】
従来から、各種のキーボードや電話機の数字キーを用いた種々の文字列の入力手法が提案されている。近年では、特に文字の種類に比べてキーの種類が少ない状況下において、ユーザが入力しようとしている文字列を統計的に予測して候補を提示し、候補から所望の文字列をユーザが選択して確定することにより、文字列を入力する手法の研究が進んでいる。
【０００３】
【発明が解決しようとする課題】
このような予測入力の技術においては、ユーザや入力状況ごとに異なる入力の嗜好・傾向にできるだけ対応することにより、予測の精度を増し、できるだけ少ない操作で文字列の入力ができるようにしたい、との要望は大きい。
【０００４】
このほか、あらかじめ用意された辞書には登録されていない新語、方言、古文、業界用語などに容易に対応できるような文字列の入力技術が望まれている。
【０００５】
本発明は、以上のような問題を解決するためになされたもので、ユーザや入力状況に個別的に適応して文字列入力を容易にするのに好適な文字列入力装置、当該文字列入力装置にて利用可能な接頭最長重複文字列の抽出装置、ならびに、これらをコンピュータ上にて実現するプログラムを提供することを目的とする。
【０００６】
【課題を解決するための手段】
以上の目的を達成するため、本発明の原理にしたがって、下記の発明を開示する。
【０００７】
本発明の第１の観点に係る接頭最長重複文字列を抽出する抽出装置は、対象文書入力受付部と、接頭辞入力受付部と、抽出部と、を備え、以下のように構成する。
【０００８】
まず、「ある文書における、ある接頭辞に対する、接頭最長重複文字列」とは、「当該接頭辞を接頭辞とし、当該文書に２回以上出現する部分文字列（以下「接頭重複文字列」という。）であって、他の接頭重複文字列の接頭辞となっていないもの」をいう。
【０００９】
一方、対象文書入力受付部は、対象文書の入力を受け付ける。
【００１０】
さらに、接頭辞入力受付部は、接頭辞の入力を受け付ける。
【００１１】
そして、抽出部は、入力を受け付けられた対象文書における、入力を受け付けられた接頭辞に対する、接頭最長重複文字列を抽出する。
【００１２】
本発明の他の観点に係る文字列入力装置は、候補抽出部と、候補選択部と、入力結果出力部と、を備え、以下のように構成する。
【００１３】
すなわち、候補抽出部は、対象文書の入力を受け付け、接頭辞の入力を受け付け、当該対象文書に出現する部分文字列であって、当該接頭辞を接頭辞とするものを、候補文字列として出力する。
【００１４】
一方、候補選択部は、出力された候補文字列を含む候補文字列から、いずれかを選択する。
【００１５】
さらに、入力結果出力部は、選択された候補文字列を、入力結果として出力する。
【００１６】
また、本発明の文字列入力装置は、符号入力部と、候補辞書部と、をさらに備え、以下のように構成することができる。
【００１７】
すなわち、符号入力部は、ユーザからの符号入力を受け付ける。
【００１８】
一方、候補辞書部は、受け付けられた符号入力に対応付けてあらかじめ記憶された文字列を取得して、これを接頭辞として候補抽出部に与える。
【００１９】
さらに、候補選択部は、取得された文字列を候補文字列にさらに含める。
【００２０】
また、本発明の文字列入力装置において、候補抽出部は、上記の文字列抽出装置に、当該対象文書を入力として与え、当該接頭辞を入力として与え、当該抽出された接頭最長重複文字列を候補文字列として出力するように構成することができる。
【００２１】
また、本発明の文字列入力装置は、部分文字列の抽出装置をさらに備え、以下のように構成することができる。
【００２２】
すなわち、部分文字列の抽出装置は、文字列入力受付部と、開始位置受付部と、評価値計算部と、抽出部と、を備える。
【００２３】
ここで、文字列入力受付部は、長さＮ  （Ｎ≧１）の文字列
ｓ  ＝  Ｘ１，…，ＸＮ
の入力を受け付ける。
【００２４】
一方、開始位置受付部は、入力を受け付けられた文字列における開始位置ｋ  （１≦ｋ≦Ｎ）の入力を受け付ける。
【００２５】
さらに、評価値計算部は、長さｉ  （１≦ｉ≦Ｎ−ｋ＋１）の部分文字列
ｓｉ  ＝  Ｘｋ，…，Ｘｋ＋ｉ−１
について、当該部分文字列ｓｉのｓにおける出現頻度Ｎｉと、ｓにおいて当該部分文字列ｓｉに続いて出現する文字の種類の数Ｃｉとから、評価値
ＳＣ（ｓｉ）  ＝  ｌｏｇ（ｉ＋１）×ｌｏｇ（Ｎｉ）×（１−１／Ｃｉ）
を計算する。
【００２６】
そして、抽出部は、計算された評価値が
ＳＣ（ｓｉ＋１）  ＞  ＳＣ（ｓｉ）
を満たす場合、当該部分文字列ｓｉ＋１を抽出する。
【００２７】
一方、候補抽出部は、部分文字列の抽出装置に、当該対象文書を文字列の入力として与え、当該接頭辞が当該対象文書において出現する場所のそれぞれについて、これに続く位置を開始位置の入力として与え、当該出現する位置から当該抽出された部分文字列の終了位置までの部分文字列を、候補文字列として出力する。
【００２８】
本発明のその他の観点に係るプログラムは、コンピュータを、上記の抽出装置、または、上記の文字列入力装置として機能させるように構成する。
【００２９】
また、本発明のプログラムは、コンパクトディスク、フレキシブルディスク、ハードディスク、光磁気ディスク、ディジタルビデオディスク、磁気テープ、半導体メモリなどの情報記録媒体に記録することができる。
【００３０】
また、コンピュータとは独立して、本発明のプログラムを記録した情報記録媒体を配布、販売したり、コンピュータ通信網を介して当該プログラムを配布や販売等することができる。
【００３１】
【発明の実施の形態】
以下に本発明の一実施形態を説明する。なお、以下に説明する実施形態は説明のためのものであり、本願発明の範囲を制限するものではない。したがって、当業者であればこれらの各要素もしくは全要素をこれと均等なものに置換した実施形態を採用することが可能であるが、これらの実施形態も本願発明の範囲に含まれる。
【００３２】
（発明の実施の形態）
図１は、本発明の第１の実施形態に係る文字列入力装置の概要構成を示す模式図である。以下、本図を参照して説明する。
【００３３】
文字列入力装置１０１は、符号入力部１０２と、候補辞書部１０３と、候補抽出部１０４と、候補選択部１０５と、入力結果出力部１０６と、を備える。
【００３４】
すなわち、符号入力部１０２は、ユーザからの符号入力を受け付ける。ユーザからの符号入力は、一般には、コンピュータのキーボードや電話機の数字ボタンなどによって与えられる。
【００３５】
一方、候補辞書部１０３は、受け付けられた符号入力に対応付けてあらかじめ記憶された文字列を取得して、これを接頭辞として候補抽出部１０４に与える。
【００３６】
たとえば、日本語入力においてローマ字入力を用いる場合には、アルファベットの組合せに対応する符号入力（たとえば「ｍｏｎｏ」）が仮名列（たとえば「もの」「モノ」）、漢字列（たとえば「者」「物」）や漢字仮名まじり列といった文字列に対応付けて記憶されている。
【００３７】
一方、電話機のような少数キーでの入力においては、各キーにアルファベット複数文字を割り当て（たとえば「２」にＡ，Ｂ，Ｃ、「３」にＤ，Ｅ，Ｆ、…、「８」にＴ，Ｕ，Ｖ、…）、数字列を符号入力とし、これを、単語の綴りに対応付けて記憶する手法がある。この手法では、たとえば「２２８」には、「ＣＡＴ」や「ＡＣＴ」などが対応付けられ、「３２８」には、「ＥＡＴ」などが対応付けられる。
【００３８】
このほか、電話機のような少数キーでの入力においては、各キーに仮名文字を複数割り当て（たとえば「１」にあ行の仮名、「２」にか行の仮名、…、「７」にま行の仮名、「８」にな行の仮名、…）数字列を符号入力とし、これを、当該仮名によって表現されうる各種の日本語文字列に対応付けて記憶する手法もある。いわゆる子音入力と呼ばれるものである。たとえば「７８」には、「もの」「モノ」「者」「物」の他、「まね」「真似」「美濃」「蓑」「むね」「胸」等が対応付けて記憶される。
【００３９】
また、候補辞書部１０３は、上記のように、符号入力と同じ「長さ」の読みの単語だけでなく、これを接頭辞とするような単語を対応付けて記憶するような形態を採用することもできる。たとえば、符号入力「ｍｏｎｏ」に対しては、読みが「もの」で始まる文字列「者」「物」「ものがたり」「モノ」「物置」「モノレール」「物音」「ものすごい」「もの」等を取得できるような形態を採用してもよい。
【００４０】
そして、候補抽出部１０４は、対象文書の入力を受け付け、接頭辞の入力を受け付け、当該対象文書に出現する部分文字列であって、当該接頭辞を接頭辞とするものを、候補文字列として出力する。なお、この部分文字列の切り出しの詳細な実施形態については、後述する。
【００４１】
対象文書とは、文字列入力の見本とすることが可能な文書のことである。発明者らの研究によれば、文書の編集では、文字数がある程度（日本語の文章では約４０００文字〜８０００文字程度）以上に増えると、それ以降に使われる単語は、既出のものが７割、未出のものが３割程度となり、しかも、この性質は、さまざまな文書において成立することがわかっている。
【００４２】
たとえば、上記の候補辞書部１０３においてあらかじめ記憶されていないものはいわゆる未知語であるが、未知語であっても、一旦利用されれば既出語となる。したがって、あらかじめ用意された文字列入力用の辞書に登録されていない未知語であっても、適当な見本を採用すればその見本の中に出現する部分文字列を既出語として利用することにより、文字列の入力が容易になると予想される。
【００４３】
対象文書としては、これから文字列入力しようとする文書と同様の文書を選択することが望ましい。たとえば、電子メールの文字列入力をしようとする場合は、そのユーザが以前に編集した電子メールの文書を採用することができる。また、長い文章を編集しようとしているときには、当該文章の入力済みの部分を対象文書とすることができる。さらに、古文を入力するときには同じ時代の他の文書、法律関係書の文章を入力するときには判例集や法令集の文書などのようにすればよい。
【００４４】
たとえば、上記の最後の例において、対象文書として源氏物語の一節を採用したと考える。ローマ字で「ｍｏｎｏ」と入力したとすると、文字列として「者」「物」「ものがたり」「モノ」「物置」「モノレール」「物音」「ものすごい」「もの」等が得られるが、源氏物語の一節においては、これらのそれぞれを接頭辞とするような部分文字列としては、「物語」「物」「もの」「もののあはれ」「ものの」等が考えられ、これらが候補文字列として出力される。
【００４５】
そして、候補選択部１０５は、候補辞書部１０３から取得された文字列と、候補抽出部１０４から出力された候補文字列と、を文字列入力の候補文字列として表示し、これらの候補文字列から、ユーザにいずれかを選択させる。上記の例では、前者が「者」「物」「ものがたり」「モノ」「物置」「モノレール」「物音」「ものすごい」「もの」等、後者が「物語」「物」「もの」「もののあはれ」「ものの」等である。
【００４６】
図２は、文字列入力装置１０１の画面の構成例を示す説明図である。図２（ａ）は、「ｍｏｎｏ」を入力した際の表示例であり、図２（ｂ）は、さらに続けて「ｎｏ」を入力した際の表示例である。
【００４７】
画面２０１の中段２０２には、それまでに与えた符号入力が表示されている。図２（ａ）では「ｍｏｎｏ」であり、図２（ｂ）では「ｍｏｎｏｎｏ」である。
【００４８】
上段左２０４には、候補抽出部１０４から出力された候補文字列が表示されている。多くの場合、ユーザは、この中の候補文字列を選択することとなる。図２（ａ）では「物語」「物」「もの」「もののあはれ」「ものの」であり、図２（ｂ）では「もののあはれ」「ものの」である。
【００４９】
上段右２０３には、候補辞書部１０３から取得された文字列が候補文字列として表示されている。図２（ａ）では「ものがたり」「モノ」「物置」「モノレール」「物語っ」「物語る」「物音」「ものすごい」「物見」等、ローマ字の読み「ｍｏｎｏ」から始まる文字列が提示されている。図２（ｂ）では「物部」「もののあはれ」「物の数」等、ローマ字の読み「ｍｏｎｏｎｏ」から始まる文字列が提示されている。
【００５０】
ユーザは、これら提示された候補文字列から、たとえばカーソルキーやタブキー、決定（リターン）キー等を用いて、あるいはマウスを用いて、いずれかを選択する。ここで、後述するように候補文字列を整列して提示すれば、さらに、ユーザの符号入力の回数を減少させることができると期待される。
【００５１】
最後に、入力結果出力部１０６は、選択された候補文字列を、入力結果として出力する。図３は、文字列入力装置１０１の画面の構成例を示す説明図であり、上記の例において「もののあはれ」を選択した後に、さらに「ｗｏ」を符号入力した後のものである。図中、下段２０５に入力結果「もののあはれ」が表示されている。また、中段２０２には「ｗｏ」が、上段右２０３には「を」が、上段左２０４には「を」「を、」「をかし」「を思」「を見」等が、それぞれ表示されている。
【００５２】
なお、本実施例では、上段右２０３にひらがな「を」が表示されているが、これは符号入力をそのままひらがなにしたものである。また、図２（ｂ）では、上段右２０３と上段左２０４とに「もののあはれ」が重複して表示されている。このような重複した候補は、いずれか一方の候補の提示を省略するような態様を採用してもよい。
【００５３】
下段２０５に表示された入力結果は、さらに公知の文字列編集技術（たとえば、カーソルキー、バックスペースキー、削除キーを用いた、不要な文字の削除等）によって編集可能とすることにより、所望の文字列と少々異なる候補文字列が提示された場合であっても、これを手直しして文字列入力を行うことができる。
【００５４】
（候補抽出部の第１の実施の形態）
以下では、対象文書から部分文字列を切り出す手法について、詳細に述べる。ここでは、接頭最長重複文字列を抽出する文字列抽出装置を用いる。
【００５５】
ここで、「ある文書における、ある接頭辞に対する、接頭最長重複文字列」とは、「当該接頭辞を接頭辞とし、当該文書に２回以上出現する部分文字列（以下「接頭重複文字列」という。）であって、他の接頭重複文字列の接頭辞となっていないもの」をいう。
【００５６】
たとえば、文書として「ａｂｒａｃａｄａｂｒａ」を、接頭辞として「ａ」を考える。「ａ」を接頭辞とする接頭重複文字列は、以下の通りである。
「ａｂｒａ」…２回出現。
「ａｂｒ」…２回出現。
「ａｂ」…２回出現。
「ａ」…５回出現。
【００５７】
さてここで、２回出現した「ａｂｒ」はいずれも、他の接頭重複文字列「ａｂｒａ」の接頭辞となっている。また、２回出現した「ａｂ」はいずれも、他の接頭重複文字列「ａｂｒａ」の接頭辞となっている。さらに、５回出現した「ａ」のうち２回は、他の接頭重複文字列「ａｂｒａ」の接頭辞となっている。したがって、これらを除いたものが接頭最長重複文字列であり、以下の通りである。
「ａｂｒａ」…２回出現。
「ａ」…３回出現。
【００５８】
上記の例における「物語」「物」「もの」「もののあはれ」「ものの」等は、源氏物語の一節（約５０００文字）から抽出された接頭最長重複文字列である。一方、上記の例における候補辞書部１０３は、現代語の単語辞書を用いており、源氏物語で頻出する単語は登録されていない。
【００５９】
この結果を見ると、このような短い対象文書の場合を採用した場合であって、接頭最長重複文字列を単語や慣用句に相当する文字列であるとして考えれば、ユーザの指示入力を減らした文字列入力が可能であると考えられる。
【００６０】
図４は、このような接頭最長重複文字列を抽出する抽出装置の概要構成を示す模式図である。以下、本図を参照して説明する。
【００６１】
抽出装置４０１は、対象文書入力受付部４０２と、接頭辞入力受付部４０３と、抽出部４０４と、を備える。
【００６２】
ここで、対象文書入力受付部４０２は、対象文書の入力を受け付ける。
【００６３】
さらに、接頭辞入力受付部４０３は、接頭辞の入力を受け付ける。
【００６４】
そして、抽出部４０４は、入力を受け付けられた対象文書における、入力を受け付けられた接頭辞に対する、接頭最長重複文字列を抽出する。
【００６５】
接頭最長重複文字列の抽出には、サフィックスアレイ（ｓｕｆｆｉｘ  ａｒｒａｙ）を利用すると高速化を図ることができる。サフィックスアレイとは、対象文書の文字列を先頭から１文字ずつ削った文字列群をソートしたものである。たとえば「ａｂｒａｃａｄａｂｒａ」の先頭から１文字ずつ削った文字列群は、
ａｂｒａｃａｄａｂｒａ
ｂｒａｃａｄａｂｒａ
ｒａｃａｄａｂｒａ
ａｃａｄａｂｒａ
ｃａｄａｂｒａ
ａｄａｂｒａ
ｄａｂｒａ
ａｂｒａ
ｂｒａ
ｒａ
ａ
であるから、サフィックスアレイは、
ａ
ａｂｒａ
ａｂｒａｃａｄａｂｒａ
ａｃａｄａｂｒａ
ａｄａｂｒａ
ｂｒａ
ｂｒａｃａｄａｂｒａ
ｃａｄａｂｒａ
ｄａｂｒａ
ｒａ
ｒａｃａｄａｂｒａ
のようになる。
【００６６】
このサフィックスアレイから、「ａ」を接頭辞とする接頭最長重複文字列を求めるには、以下のようにすればよい。まず、２分探索により、「ａ」を接頭辞とする範囲（「ａ」〜「ａｄａｂｒａ」）の開始位置を求める。次に、その開始範囲を順に走査し、現在の文字列と次の文字列との接頭重複文字列を得て、それがまだ出力されていない場合には、それを接頭最長重複文字列として出力する。
【００６７】
たとえば、ａとａｂｒａとの対比ではａが出力され、ａｂｒａとａｂｒａｃａｄａｂｒａとの対比ではａｂｒａが出力される。ａｂｒａｃａｄａｂｒａとａｃａｄａｂｒａとの対比ではａが接頭重複文字列となるが、これは出力済みである。ａｃａｄａｂｒａとａｄａｂｒａとの対比ではａが接頭重複文字列となるが、これは出力済みである。
【００６８】
そして、ａｄａｂｒａとｂｒａを対比する時点で、ｂｒａが「ａ」を接頭辞としないことがわかるので、走査を終了する。なお、前のａｃａｄａｂｒａとａｄａｂｒａの比較時に走査時に接頭重複文字列ａを出力済みとして検出したので、ここでは何も出力しない。
【００６９】
このように接頭最長重複文字列を使うと、単語単位での切り出しではなく、文節や慣用句などの単位での切り出しとなることが期待される。したがって、１回の変換で複数単語の入力が可能となる。
【００７０】
（候補文字列の提示の実施の形態）
対象文書から抽出した部分文字列は、ユーザが所望の候補と予想されるものを選択しやすいように、適切に整列して提示することが望ましい。本実施形態では、そのための手法としてＰＰＭを用いる。
【００７１】
ＰＰＭでは、時系列ｘ０，…，ｘｉが与えられたとき、次の要素ｘｉ＋１が出現する確率を
Ｐ（ｘｉ＋１）  ＝  Σｋ＝−１ｋｍａｘ  ｕｋＰｋ（ｘｉ＋１）
により推定する。この確率の値の順に、候補を提示するのである。
【００７２】
ここで、ｋは、ｘｉ＋１の前ｋ個分の要素を表す。Ｐｋ（ｘｉ＋１）は、前ｋ個分の要素による文脈を考慮した確率であり、自然言語処理で用いられるｎ−ｇｒａｍで考えると、ｋ  ＝  ｎ−１との対応関係がある。すなわち、ｋ  ＝  １ではｂｉｇｒａｍを考えたことに、ｋ  ＝  ３ではｔｒｉｇｒａｍを考えたことになる。
【００７３】
Ｃｋをその文脈が現れた回数、ｃｋ（ｘｉ＋１）をその文脈に続いてｘｉ＋１が現れた回数とすれば、
Ｐｋ（ｘｉ＋１）  ＝  ｃｋ（ｘｉ＋１）／Ｃｋ
のように近似することができる。
【００７４】
ｋ  ＝  −１は、文脈から情報が全く得られない場合に対応する。この場合には、初期確率を適当に決める必要があるが、たとえば、任意のｘｉ＋１について等確率とする手法が採用できる。
【００７５】
また、ｕｋは重みで、各種の決め方が既に提案されている。たとえば、ＰＰＭＡと呼ばれる重みを採用することができる。ｋｍａｘはｋの上限であり、４程度で十分であることが実験により確かめられている。
【００７６】
なお、本実施形態では、見本となる対象文書については、何らの前処理を行わない。そこで、文脈としてとらえる際には、要素を文字単位で考え、候補としてとらえる際には、要素を候補文字列単位で考えることとした。上記のｘ０〜ｘｉは文字単位で考え、ｘｉ＋１は候補文字列単位で考えることになる。また、候補の頻度として、接頭最長重複文字列の出現回数を採用する。出現回数は、走査に並行して頻度を足し込んでいくことによって求めることができるし、一旦接頭最長重複文字列が求まってから、出現頻度を別途求めてもよい。
【００７７】
図２に示された候補文字列の表示順序は、上記のＰＰＭにより推定された順序になっている。
【００７８】
発明者らの実験によれば、およそ２５００単語の対象文書を用いることにより、１回の変換で１．２５単語の変換が可能となり、小さな文書を用意するだけで、効率の良い入力ができることが示された。また、平均すると、整列された候補のうち、平均して１番目〜２番目の候補が選ばれ、候補の提示順も適切であることがわかった。
【００７９】
（候補抽出部のその他の実施の形態）
本実施形態では、候補抽出部１０４において、以下のような部分文字列の抽出装置を利用する。
【００８０】
図５は、部分文字列の抽出装置の概要構成を示す模式図である。以下、本図を参照して説明する。
【００８１】
部分文字列の抽出装置５０１は、文字列入力受付部５０２と、開始位置入力受付部５０３と、評価値計算部５０４と、抽出部５０５と、を備える。
【００８２】
ここで、文字列入力受付部５０２は、長さＮ  （Ｎ≧１）の文字列
ｓ  ＝  Ｘ１，…，ＸＮ
の入力を受け付ける。
【００８３】
一方、開始位置入力受付部５０３は、入力を受け付けられた文字列における開始位置ｋ  （１≦ｋ≦Ｎ）の入力を受け付ける。
【００８４】
さらに、評価値計算部５０４は、長さｉ  （１≦ｉ≦Ｎ−ｋ＋１）の部分文字列
ｓｉ  ＝  Ｘｋ，…，Ｘｋ＋ｉ−１
について、当該部分文字列ｓｉのｓにおける出現頻度Ｎｉと、ｓにおいて当該部分文字列ｓｉに続いて出現する文字の種類の数Ｃｉとから、評価値
ＳＣ（ｓｉ）  ＝  ｌｏｇ（ｉ＋１）×ｌｏｇ（Ｎｉ）×（１−１／Ｃｉ）
を計算する。
【００８５】
そして、抽出部５０５は、計算された評価値が
ＳＣ（ｓｉ＋１）  ＞  ＳＣ（ｓｉ）
を満たす場合、当該部分文字列ｓｉ＋１を抽出する。
【００８６】
この評価値は、単語列からコロケーションを抽出するためのＣ−ｖａｌｕｅという評価関数から着想を得たものであり、文字列の文字単位で評価値をローカルに計算できるという特徴を有する。上記の積の第１項は、極端に短い候補の評価値を小さくする一方で、長過ぎる候補が優先されないようにしている。第２項は、出現頻度に対応するものである。第３項は、後続する文字の種類が多い場合に大きい値となる。これは、「極端に長くも短かくもなく、頻出し、後続する文字の種類が多い」ものが「単語候補」としてふさわしい、ということに対応する。
【００８７】
そして、候補抽出部１０４は、抽出装置５０１に、当該対象文書を文字列の入力として与え、当該接頭辞が当該対象文書において出現する場所のそれぞれについて、これに続く位置を開始位置の入力として与え、当該出現する位置から当該抽出された部分文字列の終了位置までの部分文字列を、候補文字列として出力する。
【００８８】
なお、上記の手法以外にも、候補の抽出の際には、所定の長さの部分文字列を単純に抽出する、という手法や、部分文字列を長く抽出しておき、その中の一部をユーザに選択させる、という手法などが考えられる。
【００８９】
【発明の効果】
以上説明したように、本発明によれば、ユーザや入力状況に個別的に適応して文字列入力を容易にするのに好適な文字列入力装置、当該文字列入力装置にて利用可能な接頭最長重複文字列の抽出装置、ならびに、これらをコンピュータ上にて実現するプログラムを提供することができる。
【図面の簡単な説明】
【図１】本発明の実施形態に係る文字列入力装置の概要構成を示す模式図である。
【図２】文字列入力装置の画面の表示例を示す説明図である。
【図３】文字列入力装置の画面の表示例を示す説明図である。
【図４】本発明の実施形態に係る接頭最長重複文字列の抽出装置の概要構成を示す模式図である。
【図５】本発明の実施形態に係る部分文字列の抽出装置の概要構成を示す模式図である。
【符号の説明】
１０１  文字列入力装置
１０２  符号入力部
１０３  候補辞書部
１０４  候補抽出部
１０５  候補選択部
１０６  入力結果出力部
２０１  画面
２０２  中段
２０３  上段右
２０４  上段左
２０５  下段
４０１  抽出装置
４０２  対象文書入力受付部
４０３  接頭辞入力受付部
４０４  抽出部
５０１  抽出装置
５０２  文字列入力受付部
５０３  開始位置受付部
５０４  評価値計算部
５０５  抽出部
【図１】
2004164120.tif 000003
【図２】
2004164120.tif 000004
【図３】
2004164120.tif 000005
【図４】
2004164120.tif 000006
【図５】
2004164120.tif 000007