(57)【特許請求の範囲】
【請求項１】
トークン分割トランスデューサを用いてテキスト（文章）をトークンに分割する方法を実行する、少なくともコンフィギュレーションを記憶するコンフィギュレーション記憶ユニットと、コンフィギュレーションの数をカウントするカウント手段と、該コンフィギュレーション記憶ユニット及び該カウント手段を制御する該制御手段を含む、テキストトークン分割システムであって、
該方法は、
（ａ）前記トークン分割トランスデューサの拡張状態と出力ノードとを有する少なくともひとつの現在のコンフィギュレーションをすべて、当該テキストトークン分割システムのコンフィギュレーション記憶ユニットに記憶するステップと、
（ｂ）前記コンフィギュレーション記憶ユニットに記憶した少なくともひとつの現在のコンフィギュレーションから、未処理のコンフィギュレーションをひとつ選択するステップと、
（ｃ）選択した前記コンフィギュレーションに、次のコンフィギュレーションの生成を含み、前記トランスデューサの遷移を含む処理を実行するステップと、
（ｄ）すべての現在のコンフィギュレーションの処理が完了するまで、前記ステップ（ｂ）および（ｃ）を繰り返すステップと、
（ｅ）前記すべての現在のコンフィギュレーションを前記コンフィギュレーション記憶ユニットから消去するステップと、
（ｆ）すべての次のコンフィギュレーションを現在のコンフィギュレーションとし、次のテキスト位置を前記トランスデューサの遷移の処理を適用する現在のテキスト位置として再定義するステップと、
（ｇ）新規に現在のコンフィギュレーションとなった前記次のコンフィギュレーションの数を、当該テキストトークン分割システムのカウント手段によりカウントするステップと、
（ｈ）前記カウント手段によりカウントされたコンフィギュレーションの数がひとつだけの場合、出力を生成するステップと、
を含む、
テキストトークン分割システム。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、テキスト（文章）をトークンに分割する方法および装置に関し、特に、任意の自然語の文字ストリームを、意味を持つサブユニット（すなわちトークン）に分割する方法および装置に関する。
【０００２】
【従来の技術および発明が解決しようとする課題】
文書上で任意のテキスト処理を行う前に、テキストを識別可能な意味を持つ単位（ユニット）に分割する必要がある。このようなテキストの「トークン分割」処理は、句読点によって文章が完全に区切られる言語に対しては、比較的行いやすい。意味を持つ各単位（トークン）は、特定のキャラクタまたはシンボルによって、その他の単位（トークン）から区分される。英語の書き言葉は、きわめて効果的に句読点で区切られた言語ではあるが、それでもある種の不明確さを含む。この結果、ひとつの意味を持つユニットを隣接のユニットから分割する場合に、トークン分割に複数のオプションが生じることがある。
【０００３】
英語の書き言葉でのこのような不明確さ（両義性）は、以下に延べる２通りの場合に生じる。第１の例は、ひとつの意味を成すユニットが、スペースで区切られた２つの単語から成る場合である。一般に英語の書き言葉では、単語は前後のスペースによって隔てられることによって、ひとつの意味を持つユニットを構成する。しかし、いくつかの固有名詞には、この一般規則があてはまらない。例えば、「ジェネラルモーターズ（General Motors）」や「キーウエスト（Key West）」といった名称がそうである。また、固有名詞以外の単語ストリングでも、上記一般規則があてはまらないものがある。例えば、"jack rabbit" （ジャックウサギ）、"to and fro"（〜から）、"a priori"（演繹的に）といった語句は、２つ以上の単語の集合が、それぞれ個々の単語成分とは異なるひとつの意味を持つ。実際、これらの単語成分の中には、単独では独立した単語として存在しないものもある（priori、fro など）。
【０００４】
第２の例は、英語の書き言葉において、ピリオドが検出された場合に生じる。ピリオドに遭遇した場合、それが文末、省略、あるいはその双方（文末の省略語）を表わす可能性がある。例えば、"Jan."は、文章の最後に位置する人名である場合と、文の途中に位置する"January" （一月）という単語の省略である場合があり、さらにまた、文の終わりに位置する"January" の省略である可能性もある。同様に、"chap." は、文の最後に位置する"chap"（男）という単語かもしれないし、文中の任意の位置での"chapter" （章）の省略形かもしれない。
【０００５】
このような不明確さ（両義性）は、トークン分割したテキストをある種のテキスト処理に適用する場合に問題を引き起こす。例えば、マウスを使ったコンピュータに適用する場合、ユーザーはテキストブロックを選択するのに、マウスを何度か続けてクリックする。マウスを一度クリックすると単語が選択され、２度クリックするとセンテンス（文）が選択され、３度クリックすると、パラグラフ（段落）が選択されるなど。この例でいくと、ユーザーが「ａ  ｐｒｉｏｒｉ」といった複合語を一単語として選択したくても、マウスを一度だけクリックすると、単語「ａ」しか選択されず、二度クリックすると、センテンス全体が選択されてしまう。また、一文を選択したくても、その文が、文の途中に位置する省略語（例えば"Jan."など）を含む場合、その省略語の位置で区切られて選択される。
【０００６】
トークン分割がきわめて大きな問題となるテキスト処理の別の例として、サーチ、検索オペレーションがある。ユーザーがある単語をサーチしたいとする。その単語が文末に位置してピリオドをともなう場合、それを正確なストリングのマッチングで見つけることはできない。また、その単語が複合語の一部に含まれている場合、検索の対象外であってもその単語が検索されてしまう。このようなことはユーザーにとって好ましくないとしても、システムではすべてを検索してしまう。
【０００７】
この種の問題は、英文テキストの処理でそれほど頻繁に生じる問題ではないので、無視されがちであるが、英語以外の言語では問題がより大きく、無視するわけにはいかない。例えば中国語テキストでは、文中の文字が句読法やスペースによって区切られていないので、トークンの境界を見分けるのがさらに困難である。
【０００８】
もちろん、中国語テキストにおいても、各文字は等間隔のホワイト空間で隔てらているので、２つ以上の個別の文字がひとつの単語を形成する場合が多いとはいえ、句点で終了する一文を意味を成すユニットに分割するトークン分割方法がいくつか可能である。
【０００９】
一般に従来の方法では、文字列は単にスペースと句読点を識別することによってトークンに分割されてきた。英文テキストの処理と関連して述べたように、このような従来の方法では不正確なトークン分割が行われることがある。さらに、これを中国語テキストに適用した場合、完全なセンテンスごとにしかトークンの境界が検出されず、文中にはトークンの境界が存在しないことになる。これではトークン分割の意味がない。
【００１０】
従来、中国語のテキストには、可能なすべてのトークン分割の各々の確率を考慮した統計的な方法が適用されてきた。このような方法は、辞書などの語彙情報を組み込むことができる。
【００１１】
また別の方法として、「深さ優先（depth-first ）」方法がある。これはトークン分割の規則をテキストの文節ごとに適用する方法である。この方法では一般に、最初のテキストキャラクタから順に、文節を通して可能なトークン分割のパスをひとつ選択する。このパスが不適当な場合は、再度最初のテキストキャラクタでの処理から始める。この方法は、後になって出力を取り消したり、長文テキスト全体を処理して、最終的にはっきりと正確なパスを決定するまで出力を遅延することが多く、煩雑である。この方法では、選択したパス次第で、余分な記憶スペースが必要になってくる。パスを拡張するときは、後戻り記憶装置を配置して、最初に選択したパスが後になって不適正であると判明した場合にプロセスを回復できるようにしなければならない。選択したパスが正しく、オペレーションをテキスト末まで継続できた場合は、後戻り記憶装置を使う必要はない。しかしこの方法は、パスが後になって不適当とされる可能性があるので、増分出力ができない。したがってクライアントは、テキスト全体が処理されるまで、テキストの任意の部分を操作することができない。
【００１２】
本発明で使用する関係式は、１９９５年３月２７日にアイルランド、ダブリンで開催されたＡＣＬ  ＳＩＧＤＡＴワークショップの議事録、『テキストからタグへ：多種言語の言語解析に関する討論』に掲載された「多種言語テキスト解析におけるトークン分割と書記素から音素への変換のための有限状態アーキテクチュア」（"A Finite-State Architecture for Tokenization and Grapheme-to-Phoneme Conversion in Multilingual Text Analysis" From Text to tags:Issues in Multilingual Language Analysis, proceedings of the ACL SIGDATWorkshop. March 27, 1995, Dublin, ireland ）で、スプロウト（Sprout）が提唱した式と事実上同一である。しかし、スプラウトは式の計算プロセスを記載しておらず、計算は通常の（従来の）有限状態演算方法を実行することによって達成されると前提している。また、本発明と異なり、スプラウトはこの式を完全な長文テキストにではなく、個々の独立したセンテンスに適用することにのみ着目しているので、処理効率の問題には触れていない。スプラウトは、重み付けしたトランスデューサについて論じており、プロセス全体を通して最良のパスを選択してゆく。本発明も、すべてのピンチポイントにおいてそれぞれの最良のパスを決定して、それらを連結するので、本発明を増分的な方法での最良パスの選択にまで拡張することができる。
【００１３】
【課題を解決するための手段】
本発明によるテキストのトークン分割方法は、従来の深さ優先方法とは異なり、キャラクタベース（あるいは幅優先（breadth-first ）ベース）で進み、特定のキャラクタ位置までテキストのあらゆる可能なトークン分割をまず検出し、トークン分割のすべてがそのキャラクタ位置より後のテキストと矛盾しない場合に、すべての適正なトークン分割を出力する。
【００１４】
ある言語のためのトークン分割の規則は、有限状態トランスデューサ内に符号化され、本発明はこのようなトランスデューサをテキストに適用する有効な方法を提供する。
【００１５】
本発明の方法では、（ａ）拡張状態と出力ノードとを有する少なくともひとつの現在のコンフィギュレーションをすべて、コンフィギュレーション記憶ユニットに記憶し、（ｂ）記憶した少なくともひとつの現在のコンフィギュレーションから、未処理のコンフィギュレーションをひとつ選択し、（ｃ）選択した現在のコンフィギュレーションを、次のコンフィギュレーションの生成を含めて処理し、（ｄ）すべての現在のコンフィギュレーションの処理が完了するまで、前記（ｂ）および（ｃ）を繰り返し、（ｅ）前記すべての現在のコンフィギュレーションを消去し、（ｆ）すべての次のコンフィギュレーションを現在のコンフィギュレーションとし、次のテキスト位置を現在のテキスト位置として再定義し、（ｇ）新規に現在のコンフィギュレーションとなったコンフィギュレーションの数をカウントし、（ｈ）次のコンフィギュレーションの数がひとつだけの場合、出力を生成する。
【００１６】
本発明は、テキストの特定の特性を利用することによって、正確な増分出力を生成し、従来のトークン分割方法に見られた問題点を回避する。
【００１７】
本発明で使用する場合のテキストの重要な特性は、非循環性である。この非循環性によって、テキストキャラクタを横断する際に、大量の記憶を必要とせずにすむ。より具体的には、現在のテキスト位置からのすべてのトランスデューサ遷移を処理し、新規の現在のテキスト位置を検出したならば、古いテキスト位置に戻る必要性がないので、古いテキスト位置に関する情報を記憶装置に保持する必要がない。
【００１８】
また、テキストの非循環性によって、テキストを幅優先の処理方法で横断することが可能になる。すなわち、次のキャラクタ位置に進む前に、現在のキャラクタまでのすべてのトークン分割パスを検出する。これは、すべてのキャラクタ位置を通る単一のパスを横断し、その後、以前のキャラクタ位置へ戻って別のパスを解析するという、従来の深さ優先方法とは対照的である。
【００１９】
幅優先方法において、処理は少なくともピンチポイントに到達するまでは継続して進む。ピンチポイントは、そのポイントまでのすべてのトークン分割パスが、まったく同一の経路に拡張されるキャラクタ位置として定義される。このようなキャラクタ位置では、それ以前のすべてのトークン分割のオプションが、この位置の後に続くすべてのトークン分割と矛盾しないように決定される。ピンチポイントに到達した後は、先のキャラクタ位置に関連する記憶が不必要となり、この時点で、前のピンチポイントから現在のピンチポイントまでのトークン分割が出力として生成され得る。
【００２０】
ピンチポイントは、意味をなすユニット（すなわちトークン）間の境界と一致してもよいし、一致しなくてもよい。したがって、ひとつのトークン内のピンチポイントでも出力を生成できるが、その場合、クライアントはさらに処理を進める前に、次のトークン境界にたどり着くまで出力をバッファに一時格納しなければならない。または、ピンチポイントとトークン境界とが一致する地点に到達するまで、トークン分割の出力を遅延させる。後者の方法（トークン分割出力の遅延）のほうが、クライアントが出力を受け取ったなら、バッファリングを必要とせずに即座に出力を処理できるので、より効率的である。上述のような本発明の方法では、正確な増分トークン分割出力が生成できる。トークン分割出力は、ピンチポイント間のキャラクタストリングのすべての可能な適正トークン分割を含む。トークン分割出力は、通常は有限状態マシンとして構成されるが、もちろん、トークン分割したストリングの完全な集合を出力することも可能である。
【００２１】
テキスト全体として、適正な構成形式でない（例えば許容できない句読パターンを含むなど）と後で判明することがあるにしても、本発明ではトークン分割の出力ごとに、それまで調べたキャラクタストリングが適正かつ完全であることが確証される。
【００２２】
【発明の実施の形態】
以下で、図面を参照して本発明の好適な実施形態を詳細に説明する。
【００２３】
本発明の方法は、次式（１）の演算方法を含む。
Ｄｏｍ（Ｔ  ｏ  Ｉｄ（ｔｅｘｔ））      ．．．  （１）
ここで、「ｔｅｘｔ」はトークン分割を行うテキスト、「Ｉｄ（ｔｅｘｔ）」は、テキストをそれ自体と一対にする一致関係である。Ｔはトークン分割関係を表わし、トークンに分割されたストリングと、それを表わす対応のテキストストリングから成る対（ペア）の有限集合である。Ｔは、例えば後述する規則集合であってもよい。「ｏ」 は比較計算の周知の合成演算子を表わす。関係式（Ｔｏ  Ｉｄ（ｔｅｘｔ））の定義域（ドメイン）「Ｄｏｍ」は、まさにＴが所定のテキストとして表現するはずのトークン分割されたストリングの集合である。この関係式の値域（レンジ）は、表面テキストそのもので構成される。これらの演算子、およびその他の関連の演算子については、１９９４年９月発行の『コンピュータ言語学』第３号、第２０巻に掲載の、カプラン（Kaplan）およびカイ（Kay ）共著「音韻システムの正則モデル」（"regular Model of PhonologicalSystem", Computational Linguistics, Vol. 20, #3, Sept. 1994 ）に詳細に記載されている。
【００２４】
言語とは、キャラクタストリングの集合である。言語は、合併集合演算子、連結演算子、およびクリーネ（Kleene）の閉鎖演算子を使用して、ストリング（文字列）の有限集合から構築され得る場合には、正則言語である。周知のように、正則言語は有限状態マシンによって表わされる。ストリング関係は、ストリング（文字列）の順序対の集合である。ストリング関係が、合併集合演算子、連結演算子、およびクリーネ（Kleene）の閉鎖演算子を使用してストリング対から構築され得る場合には、そのストリング関係は正則である。正則ストリング関係は、有限状態トランスデューサで表わされる（上記Kaplan and Kayの参照）。トークン分割関係は正則関係であるとみなされ、テキストは単一ストリングの正則言語であると解釈される。したがって、Ｉｄ（ｔｅｘｔ）は、単一対の正則関係式であるとみなされる。周知のように、有限状態マシンとトランスデューサは、ともにグラフで表わされる。このようなグラフでは、ノードは「状態」と呼ばれ、エッジは「遷移」と呼ばれる。識別されたスタート状態から、最終状態のひとつに至るパスが存在し、そのパスでの遷移のラベルが、ストリングまたはストリング対のキャラクタとマッチすれば、そのストリング対は許容される。有限状態マシンと有限状態トランスデューサとの相異点は、有限状態マシンの遷移ラベルはキャラクタ単体であるのに対し、有限状態トランスデューサの遷移ラベルはシンボル対であることである。これらの詳細については、上記カプラン＆カイの論文、およびその引用文献を参照されたい。式（１）の合成演算子は一般に、関係式Ｔを有する有限状態トランスデューサと、Ｉｄ（ｔｅｘｔ）を有する有限状態トランスデューサ上で演算することによって求められる。この合成演算方法は、通常は２つのオペランドトランスデューサ（この場合は「Ｔ」および「Ｉｄ（ｔｅｘｔ）」）の状態の数の積によって設定される二次演算である。
【００２５】
合成演算によって、「Ｔ」トランスデューサと、「Ｉｄ（ｔｅｘｔ）」トランスデューサとの状態対に対応する状態を有する出力トランスデューサが生成される。この出力トランスデューサはまた、状態対の間の移動を符号化した遷移を有する。この演算を実行する間、索引付け構造を維持して、「Ｔ」と「Ｉｄ（ｔｅｘｔ）」を通る別のパスで到達した場合にもこの状態対を表わすデータ構造が獲得されるようにしなければならない。この場合、すべてのパスにおいて、それ以降での同一の遷移が有効となる。これは、これらのパスの単一の状態対へのマージ（融合）によって表わされる。マージされない場合は、演算は循環入力トランスデューサ上で終了できない。したがって、この演算はテキストの長さに比例する容量の索引付け記憶装置を必要とするので本来は実用的ではないが、本発明の方法では、テキストの非循環性に基づいて、記憶スペースを効果的に使用することができる。
【００２６】
本発明の方法では、言語のトークン分割パターンを、正則関係「Ｔ」で定義する。「Ｔ」は、明確に区切られた境界を有するトークン分割テキストを、このトークンストリングの適正な表現である、キャラクタと句読記号とから成る具体的なストリングにマッピングする。
【００２７】
一実施形態では、Ｔを正則関係を表わす規則集合で定義する。以下に示す必須のリライト（書換え）規則集合は、英語の句読法の慣例をほぼ正確に示す正則関係を定義するものである。
【００２８】
（ａ）  ．−＞エプシロン（ε）/＿｜.
（ｂ）  ｜−＞エプシロン（ε）/＿句読点
（ｃ）  スペース−＞ホワイトスペース＋
（ｄ）  ｜−＞ホワイトスペース＋
文脈を考慮したこれらのリライト（書換え）規則の一般形態は、入力−＞出力／左＿右であり、ここで、入力、出力、左、右は、任意の正則言語を表わすことができる。
【００２９】
２つ以上の規則から成る順序立った規則ファミリーが与えられた場合、第１の規則をある文字列に適用し、第１の規則の出力に第２の規則を適用し、第２の規則の出力に第３の規則を順次適用してゆく。上述のKaplan and Kayの文献は、このような規則のファミリーをどのように等価の有限状態トランスデューサに変換するかを示している。
【００３０】
このような規則を、あるストリング（文字列）に適用した場合、入力言語に属するそのストリングの任意のサブストリングが、左に属するサブストリングと右に属するサブストリングの間に現われたならば、そのサブストリングを出力言語のストリングとして書き換える。マッチング要求がないことを示して、左と右の少なくとも一方の文脈を省略する。上記の書換え規則において、「｜」は意味を成すユニットを他から区分するトークン境界を示し、エプシロン（ε）は空ストリングを表わす。εにマップされたキャラクタは消去される。「スペース」は複合語内部のスペースであり、「ホワイトスペース＋」は、ひとつ以上のホワイトスペースキャラクタのシーケンス（例えば、スペース、リターン、タブなど）である。これらのことから明らかなように、規則（ａ）は、文末のピリオドより前に省略ピリオドがきた場合に、その省略ピリオドを消去するものである。規則（ｂ）は、句読点の前にあるトークン境界を消去する規則である。規則（ｃ）は、複合語の内部のスペースをホワイトスペースキャラクタの任意のシーケンスに変換する規則である。規則（ｄ）は、残りのすべてのトークン境界をホワイトス
ペースに変える規則である。
【００３１】
上述の規則はあくまでも例であり、必要であれば、行末のハイフォネーション、文頭の大文字、語頭での句読点（語尾の句読点に加えて、あるいはその代わりに）などを扱う規則を追加することができる。また、これらの規則に高位の情報を組み合わせることができる。例えば英語では、トークンナイザＴに、内部にスペースを有するすべての複合語のリストと許可される省略形のリスト、および他のトークン中に現われるスペースとピリオドに対する禁止を組み込むことができる。
【００３２】
トークンナイザ（またはトークン分割トランスデューサ）Ｔの作用は以下の通りである。トークン分割されたテキストストリング（Ａ）があるとする。
【００３３】
Happily ｜, ｜he｜saw ｜the ｜jack rabbit ｜in｜Jan.｜.     （Ａ）トークンナイザは、上記のようにトークン分割したテキストを、下記のストリング（Ｂ）に示す実際のテキストにマップする。
【００３４】
Happily, he saw the jack rabbit in Jan.               （Ｂ）
しかし、上記（Ａ）のトークン分割されたストリングが、実際のテキストストリング（Ｂ）にマップする唯一のトークン分割ストリングというわけではなく、少なくとも下記（Ｃ）および（Ｄ）があるが、これらも上記のトークン分割ストリング（Ａ）と同じマッピング結果になる。
【００３５】
Happily ｜, ｜he｜saw ｜the ｜jack｜rabbit｜in｜Jan ｜. （Ｃ）
Happily ｜, ｜he｜saw ｜the ｜jack rabbit ｜in｜Jan ｜. （Ｄ）
したがって、本発明の方法は、実際に上記正則関係「Ｔ」の逆数を使って、具体的なテキストをその多様なトークン分割した形態にマップする。例えば、ストリング（Ｂ）の表現は、上記（Ａ）、（Ｃ）、（Ｄ）３つすべてのトークン分割ストリングをトークン分割出力として生成する。トークン分割出力は有限状態マシンの形態で生成され得る。
【００３６】
もちろん、明確なデータ構造として構築するのは非効率的であり、Ｉｄ（ｔｅｘｔ）を（１）式のように表わす有限状態トランスデューサが必要となるだろう。しかし、テキストのキャラクタストリングを、明確なデータ構造であるかのように解釈することができる。各キャラクタ位置を状態として解釈し、各キャラクタを、その一致対として解釈できる。すなわち、キャラクタストリング“ＡＢ”を、図５の有限状態トランスデューサとして解釈できる。コロン（：）の左側のラベルはドメイン（定義域）キャラクタであり、コロンの右側はレンジ（値域）キャラクタと呼ばれる。
【００３７】
一般に、テキストは非循環性で分岐しないので、合成オペレーションの効率的な幅優先処理が実行できる。出力記憶ユニット４５は、現在のキャラクタ位置に到達するトランスデューサＴのすべてのパスから生成された出力を記憶し、各パスは、そのパスがどのように拡張され得るかを示すトランスデューサＴの状態と対にされる。これらの出力は、ノードとエッジを有する有向グラフとして記憶される。例えば図６は、「Ｊａｎ」というストリングをトークン分割した際の出力グラフを示している。図６の出力グラフと、図７に示す識別されたトークンシーケンスを示す従来の有限状態マシンとの間に単純な相異があることに留意されたい。従来の有限状態マシンの各状態は、出力グラフのノードに対応し、有限状態マシンの遷移は出力グラフのエッジに対応するが、出力グラフのエッジがノードｘを出てノードｙに入るのに対し、有限状態マシンの対応の遷移はｙ状態を出てｘ状態へと延びる。有限状態マシンのスタート状態は、出力グラフの最初のノード（図６の左端）に対応する状態であり、有限状態マシンの最終状態は、トークン分割プロセスが出力グラフに追加する最後のノード（図６の右端）に対応する。図６の出力グラフに対応する有限状態マシンを図７に示す。
【００３８】
図８は、コンフィギュレーションの格納状態を示すブロック図である。コンフィギュレーションは、「処理済み」か「未処理」かを指定するブロック１、「現在（のコンフィギュレーション）」か「次（のコンフィギュレーション）」かを指定するブロック２、出力ノード３、拡張状態４で構成される。ここではコンフィギュレーションをフィールド（指定域）として示しているが、周知のリスト処理方法で記憶してもよい。本発明の幅優先方法によるパスの合成は、単に現在のテキスト位置に関連するコンフィギュレーションの集合と、次のテキスト位置に関連するコンフィギュレーションの別の集合を維持することによって実行される。
【００３９】
図１は、図２、３、４に示す本発明の好適な方法にしたがって作動するテキストトークン分割システム１００の概略図である。
【００４０】
トークン分割されるテキストの生成方法は様々である。図１の例では、スキャナ２００でテキストの一部を走査する。スキャナ２００は、ＣＣＤ（電化結合素子）などの周知の方法および装置を用いてテキスト画像を走査画像に変換する。引き続いてテキストを符号化し、光学文字認識（ＯＣＲ）システム３００で文字認識する。ＯＣＲシステム３００は、図１では個別のシステムとして描かれているが、汎用コンピュータ９０に組み込んでもよい。
【００４１】
ＯＣＲ３００で認識したテキストを汎用コンピュータ９０に送ってトークン分割する。汎用コンピュータへのテキストの入力は、メモリ、コンピュータ５００、ＬＡＮ４００などを介して行うことができる。汎用コンピュータ９０は、入出力（Ｉ／Ｏ）装置８０、テキスト記憶ユニット１０、トークン分割手段２０（より高位の制約条件を組み込むことができる）、パス決定手段３０、コンフィギュレーション記憶ユニット４０および出力記憶ユニット４５、比較手段５０、カウント手段６０、制御手段７０を含む。
【００４２】
テキストトークン分割システム１００は、ＣＰＵ、マイクロコントローラ、マイクロプロセッサ、ＡＳＩＣ、その他の集積回路によって実行されるか、または離散素子ハードウェア回路、その他従来の周知の制御構造上で実行される。図１では、テキスト記憶ユニット１０とコンフィギュレーション記憶ユニット４０を個別の装置として示しているが、ＲＡＭ、不揮発性メモリ（ハードディスク、光学ディスク、フロッピーディスクなど）、あるいはフラッシュメモリといった単一の記憶装置内の異なる場所に設けることが可能なことはいうまでもない。テキストをＩ／Ｏ装置８０を介して汎用コンピュータに入力する。この入力時にテキストを処理してもよいし、テキスト記憶ユニット１０に記憶してから、後に処理を行ってもよい。
【００４３】
トークン分割されるテキストは、まずトークン分割手段２０に入力される。ここで、空ノード（出力エッジがまったくないノード）を含む初期コンフィギュレーションを、出力ノードとして、およびトランスデューサ２２のスタート状態の拡張状態として生成する。次いで、トークン分割手段２０は、この初期コンフィギュレーションを処理して、次のキャラクタ位置での次のコンフィギュレーションを生成する。コンフィギュレーションＰの処理では、トークン分割手段２０は検出手段を用い、そのコンフィギュレーションの拡張状態において、レンジキャラクタが現在のキャラクタ位置でのテキストキャラクタにマッチするあらゆる可能な遷移を検出する。マッチした遷移の各々において、比較手段５０によって別のコンフィギュレーションを獲得する。獲得された別のコンフィギュレーションの出力ノードからは、ひとつ前のコンフィギュレーションＰの出力ノードに向かうエッジが延び、このエッジに遷移のドメインキャラクタがラベルされる。このコンフィギュレーションの拡張状態は、その遷移が到達するトランスデューサ２２の状態である。より高位の制約条件２１を含む場合は、トークン分割手段はこれらの高位の制約条件２１を適用して、低位の制約条件下では許容されるような遷移を切り捨てることができる。高位の制約条件は、辞書、問題のある単語のリスト等を含む。英語では、そのような単語リストは、単に複合語と省略語だけを含み、これらの単語のストリングにおいてのみ、トークン内でのスペースやピリオドが許容される。
【００４４】
現在の位置でのすべてのコンフィギュレーションを処理したならば、コンフィギュレーションの記憶ユニット４０のメモリスペースを一掃するために、それらをすべて消去し、次の新たなコンフィギュレーションに使用できる状態にする。その後、次のテキスト位置に移り、これを現在のテキスト位置として、これに関連するすべてのコンフィギュレーションをマークする。
【００４５】
カウント手段６０は、コンフィギュレーション記憶ユニット４０に残っている記憶されたコンフィギュレーションの数をカウントする。コンフィギュレーション記憶ユニット４０に残っているコンフィギュレーションの数がひとつだけになった時点で、テキストトークン分割システム１００は、ピンチポイントに到達したと判断する。この時点で、トークン分割出力が、Ｉ／Ｏ装置８０を介してＬＡＮ４００あるいはその他のコンピュータ５００に出力される。トークンナイザが別のプログラムのサブルーチンとして呼び出されている場合は、トークン分割出力はプログラムに返送される。または、そのピンチポイントがトークン境界に対応しない場合には、それを無視して、トークン分割処理を続行する。この場合、トークン分割出力は、テキストトークン分割システム１００が、ピンチポイントとトークン境界の双方に同時に到達したと判定するまで、出力記憶ユニット４５に記憶される。いずれにしても、現在のコンフィギュレーションが引き続き処理され、未処理のコンフィギュレーションがなくなるまで処理を続ける。
【００４６】
トークン分割出力が検出された場合は必ず、そのトークン分割出力の最終的なユーザーの必要に応じて、ＬＡＮ４００あるいはコンピュータ５００の少なくとも一方に出力が送信される。
【００４７】
テキストを、テキストトークン分割システム１００によって増分的に処理することができる。トークン分割出力は、ピンチポイントに到達するたびに、またはピンチポイントとトークン境界に同時に到達するたびに、継続的に送られる。このプロセスは、全テキストを横断し終えるまで続く。最後になって、テキストが全体的に不適切な構成であると判明することもあるが、出力のたびに各トークン分割出力セグメントは適正であると一応確証される。この状況は、カウント手段６０が、残りのコンフィギュレーションがもう残っていないと判断した時点で確認される。
【００４８】
次に、図２を参照して、本発明のトークン分割方法の作用を説明する。図２は、本発明の方法のアウトラインを示すフローチャートである。ステップＳ１００でプロセスを開始した後、Ｓ２００でテキストを入力する。Ｓ３００で、いくつかの変数を初期化する。すなわち、演算結果フラグを初期値ＦＡＩＬに設定し、次の拡張状態をＴのスタート状態に設定し、現在のテキスト位置をテキストの初頭に設定する。Ｓ４００で、テキストのトークン分割を行う。このトークン分割プロセスの詳細は、図３を参照して以下で詳細に説明する。トークン分割を終えたら、Ｓ５００でプロセスを終了する。
【００４９】
図３は、図２のステップＳ４００（テキストのトークン分割処理）を詳細に示すフローチャートである。Ｓ４０５において、コンフィギュレーション記憶ユニットで新規の未処理の現在のコンフィギュレーションを生成する。このコンフィギュレーションは、図８と関連して延べたように、拡張状態４、出力ノード３、現在のコンフィギュレーションか次のコンフィギュレーションかの指定領域２、処理済みか未処理かの指定領域１を含む。Ｓ４０５で生成するコンフィギュレーションが、現在の未処理のコンフィギュレーションとなる。その拡張状態は、次の拡張状態変数（初期状態としてトランスデューサのスタート状態になる）の値となり、その出力ノードは空ノードとなる。Ｓ４１０で、コンフィギュレーション記憶ユニットから、未処理の現在のコンフィギュレーションを選択する。未処理のコンフィギュレーションを選択したならば、Ｓ４１５で、そのコンフィギュレーションを処理する。コンフィギュレーションの処理については、図４を参照して詳細に延べる。
【００５０】
コンフィギュレーションを処理したならば、Ｓ４２０でコンフィギュレーション記憶ユニットをチェックして、未処理の現在のコンフィギュレーションがまだ残っているかどうかを調べる。未処理の現在のコンフィギュレーションがなくなるまで、ステップＳ４１０〜Ｓ４２０を繰り返す。
【００５１】
Ｓ４２０で、未処理の現在のコンフィギュレーションがもう存在しないと判定されたらば、Ｓ４２５ですべての現在のコンフィギュレーションを解除する。この結果、次の処理のための記憶スペースができることになる。
【００５２】
Ｓ４３０で、コンフィギュレーション記憶ユニットで次のコンフィギュレーションを調べる。次のコンフィギュレーションがあれば、Ｓ４３５でそれらが現在のコンフィギュレーションとなり、次のテキスト位置が現在のテキスト位置となる。次のテキストコンフィギュレーションがまったく存在しない場合は、それ以上処理は行われず、結果フラグが戻される。
【００５３】
次のコンフィギュレーションがある場合は、前述のようにＳ４３５でそれらすべてを現在のコンフィギュレーションとし、Ｓ４４０でカウント手段によってその数をカウントする。
【００５４】
現在のコンフィギュレーションの数が１より大きい場合は、ステップＳ４１０〜４２０を繰り返して、新規に現在のコンフィギュレーションとなった集合を処理する。コンフィギュレーションの数が１に等しい場合は、Ｓ４４５に進み、出力が適切であるかどうかを判定する。コンフィギュレーションが出力可能としてマークされたならばステップＳ４５０で増分出力を生成する。すると、そのコンフィギュレーションの拡張状態がステップＳ４５５で次の拡張状態になり、Ｓ４６０ですべての記憶されているコンフィギュレーションと出力を消去する。
【００５５】
Ｓ４４５で出力が望ましくないと判定された場合は、出力が適切である状態に到達するまで、ステップＳ４１０〜４４０を繰り返す。出力を遅延させる機能は、クライアントがトークン境界に到達するまで出力を受け取らないことを選択した場合に特に有用である。出力は、すべての出力エッジが出力許可を示した場合に許可される。トークン境界シンボルだけが出力を許可している場合は、出力はトークン境界にのみ現われる。このような出力の遅延が望まれない場合は、すべてのラベルが許可出力として受け取られ、Ｓ４４５での判定は、常に「ＹＥＳ」（肯定判定）となる。
【００５６】
ここで、図４を参照して、ステップＳ４１５のコンフィギュレーション処理を詳細に説明する。
【００５７】
図３と関連して延べたように、コンフィギュレーション記憶ユニットから未処理の現在のコンフィギュレーションＰを選択した後、まず、選択したコンフィギュレーションに未処理の遷移があるかどうかを、Ｓ０５で判定する。未処理の遷移があれば、Ｓ１０でその中のひとつを選択する。
【００５８】
未処理の遷移を選択した後、Ｓ１５以降でその遷移を現在のテキスト位置で適用する。
【００５９】
Ｓ１５でその遷移のレンジシンボルがエプシロン（ε）であるかどうかを判定する。肯定判定された場合は、ステップＳ２０へ進んでマッチをチェックする必要はない。この時点で、拡張状態コンフィギュレーションを、遷移先と同一の拡張状態を有する現在のコンフィギュレーションと等しく設定する。遷移の結果、ある単語とそれに続く句読点との間のトークン境界が消去される場合は、レンジキャラクタはエプシロンである。しかし、この判定は、用いるトークンナイザによって異なる。コンフィギュレーション記憶ユニットの中に、要求される拡張状態を有するコンフィギュレーションがもう存在しない場合は、新たな現在のコンフィギュレーションが生成される。そうでない場合は、存在するコンフィギュ
レーションを獲得する。
【００６０】
Ｓ１５で、選択した遷移のレンジキャラクタがエプシロンでないと判定された場合は、Ｓ２０に進み、そのレンジキャラクタが現在のテキストキャラクタとマッチするかどうかを判定する。レンジキャラクタが、現在のテキストキャラクタとマッチすれば、Ｓ３０で拡張状態コンフィギュレーションを、遷移先と同一の拡張状態を有する次のコンフィギュレーションに設定する。所望の拡張状態を有する次のコンフィギュレーションが、コンフィギュレーション記憶ユニットに存在しない場合は、新たなコンフィギュレーションを生成する。
【００６１】
Ｓ２５またはＳ３０で、拡張状態コンフィギュレーションを獲得したならば、Ｓ３５でその拡張状態コンフィギュレーションの出力ノードに出力エッジを追加する。このエッジに、遷移のドメインシンボルでラベルする。この出力エッジは、Ｐの出力ノードを指し示す。このステップは、トークン化トランスデューサによって定義される出力ストリングがノード−エッジ出力グラフに記録されることを確実にする。
【００６２】
しかし、Ｓ２０でレンジキャラクタが現在のテキストキャラクタにマッチしない場合は、拡張状態コンフィギュレーションも出力情報も獲得されず、残っている未処理の遷移に対して、Ｓ０５〜Ｓ３０を繰り返す。
【００６３】
上述の処理ステップを、未処理の遷移がなくなるまで繰り返す。すべての遷移を処理し終えたら、テキスト末に到達する。テキスト末に到達し、Ｐの遷移状態がＳ４０で最後になったならば、ステップＳ４５でリターンフラグをＳＵＣＣＥＥＤに設定する。
【００６４】
処理を終えるためには、ステップＳ５０で、拡張状態コンフィギュレーションを、ダミーの「エンド」状態を拡張状態として有する次のコンフィギュレーションに設定する。次いでＳ５５で、エプシロンとラベルされた拡張状態コンフィ
ギュレーションの出力ノードに出力エッジを追加する。Ｓ５５で、このエッジにエプシロンとラベル付けし、出力用にマークする。Ｓ６５で、図３のＳ４２０に戻る。この構成は、ピンチポイントがＳ４４０で検出されることを確実にし、テキストの最後のセグメントで出力が生成されるようにする。
【００６５】
Ｓ４０で、テキストの終点に到達しない場合、または状態が最終状態でない場合は、Ｓ６０で、図３のＳ４２０のコンフィギュレーション処理に戻す。Ｓ４２０にＳ６０から戻ろうとＳ６５から戻ろうと、いずれにしても未処理のコンフィギュレーションをさらに処理する。
【００６６】
次に、図２〜図４で説明した処理オペレーションを、いくつかの例に基づいて、さらにわかりやすく説明する。
【００６７】
図１０は、単純なトークン分割トランスデューサＴの一部であり、以下のほとんどの例で使用される遷移を含むものである。この図で、状態Ｓは、スタート状態であり、内部のＦは、それが同時に最終状態であることを示す。このトークンナイザはいくつかの高位の制約を含む。例えば、「a priori」は、複合語であるが、「ａ」を直前に伴わない「ｐｒｉｏｒｉ」は単独では許可されないなど。特定の状態で遷移に「その他（ＯＴＨＥＲ）」とラベル付けされる場合は、その状態で明確に示される同一キャラクタの対を除くすべての同一キャラクタ対を示す（例えばｂ：ｂ、ｃ：ｃなど。ただし、スペース：スペースや、同一の句読点対は除く）。すなわち、スタート状態での「その他」は、「ｇ：ｇ」、「ｏ：ｏ」、「ｆ：ｆ」など、その状態からその状態へループを作る遷移があることを示す。また、これらの例は、ドメインシンボルがトークン境界「｜」である遷移のみが、出力としてマークされることを前提としている。
【００６８】
このプロセスを、「ｇｏ  ｆｏｒ」という語句を用いた簡単な例で説明すると、より理解が容易になる。この例を図９に示す。
【００６９】
Ｓ１００でプロセスを開始し、Ｓ２００でテキスト「ｇｏ  ｆｏｒ」を入力する。Ｓ３００で、次の拡張状態をＴのスタート状態に設定し、その状態に図１０の「Ｓ」とラベルする。結果フラグをＦＡＩＬに設定し、現在のテキスト位置をテキストの開始位置に設定する。
【００７０】
現在のテキスト位置、すなわちこの例では文字「ｇ」に対応する位置から、テキストをＳ４００にしたがってトークン分割する。
【００７１】
Ｓ４１０にしたがって、未処理のコンフィギュレーションを追加し、コンフィギュレーション記憶ユニットから未処理のコンフィギュレーションを選択する。選択したコンフィギュレーションをＳ４１５で処理する。「ｇ」に対応するキャラクタ位置において、Ｓ２０で現在のテキストキャラクタとマッチするレンジシンボルを有する遷移が存在する。この「ｇ：ｇ」遷移は、図１０の状態Ｓで「その他」とラベルされた遷移によって示される。Ｓ３０で、拡張状態コンフィギュレーションが決定され、それを次のコンフィギュレーションに設定する。Ｓ３５で、ドメインシンボル「ｇ」とラベルされた出力エッジを、出力ノードの方向を指して追加する。現在のキャラクタ位置では、状態Ｓには「ｇ」とマッチする遷移は他に存在しない。
【００７２】
Ｓ０５で、所定の現在のコンフィギュレーションにおける未処理の遷移がもう存在せず、かつＳ４０でテキストが残っていない場合は、プロセスはＳ４２０に戻って未処理の現在のコンフィギュレーションが残っているかどうかをチェックする。この例では、そのようなコンフィギュレーションはもう残っていないので、Ｓ４３５で単一の次のコンフィギュレーションを現在のコンフィギュレーションにする。Ｓ４４０で、現在のコンフィギュレーションがひとつだけあると判定されるが、「ｇ」はトークン境界ではないので、Ｓ４４５では出力としてマークされず、オペレーションはＳ４１０へ進む。
【００７３】
Ｓ０５で、再度「その他」とラベルされた未処理の遷移が選択され、文字「ｏ」に対して上述と同様の処理を行う。すなわち、別の出力エッジが追加され、このエッジに、図９に示すようにドメインシンボル「ｏ」がラベル付けされる。
【００７４】
スペースキャラクタに到達した場合は、処理が異なる。その場合、Ｓ１５でのレンジシンボルはスペースである。この時点で、スペースキャラクタは上述の「ｇ」とまったく同一の方法で処理されるが、スペースはトークン境界を示すと判定される。トークン境界に到達したので、Ｓ４４５でこのコンフィギュレーションは出力としてマークされる。
【００７５】
Ｓ４４５で単一のコンフィギュレーションが出力としてマークされたので、Ｓ４５０で増分出力を生成する。すなわち、“ｇｏ｜”を含む出力グラフを生成し（可能ならば、図６、７と関連して延べた従来の有限状態マシンに変換して）、Ｓ４５５で、この単一のコンフィギュレーションの状態を次のコンフィギュレーション状態として保存し、Ｓ４６０ですべての出力とコンフィギュレーションの記憶を消去する。次いでＳ４０５で、保存した次のコンフィギュレーション状態を拡張状態として有する、新たな現在のコンフィギュレーションを生成する。これはまだ状態Ｓである。
【００７６】
上述の処理を単語「ｆｏｒ」に対しても行い、この単語の末尾に到達したときに出力が可能になる。
【００７７】
語句「ｇｏ  ｆｏｒ」に関しては、処理も出力グラフもともに単純であるが、図１０に示す「ａ  ｐｒｉｏｒｉ」といった複合語に対しては、トークン分割はより複雑になる。
【００７８】
この例では、トークン分割トランスデューサＴは、許容される複合語のリスト（集合）を含むので、当然、単語「ａ  ｐｒｉｏｒｉ」も含まれる。Ｓ４０５で、初期設定のコンフィギュレーションを生成し、このコンフィギュレーションを選択する。このコンフィギュレーションを図４のプロセスにしたがって処理する。Ｓ１０で、最初の未処理の遷移を選択する。
【００７９】
Ｓ１５でこの遷移の処理を開始する。唯一のマッチングは、レンジシンボルが「ａ」である遷移なので、「ａ」を出力し、その拡張状態が遷移先、すなわち状態Ｚ（図１０参照）である新規の次のコンフィギュレーションを生成する。
【００８０】
このコンフィギュレーションの処理に続いて、現在のキャラクタとしてスペースがくる。このスペースは前述の例での「ｇｏ」の後のスペースとは異なり、レンジシンボルがスペースである２つの遷移が存在する。ひとつは、例えば「ａｍａｎ」などのようなストリングが後に続く場合に適切となるトークン境界を出力する。もうひとつは、ａは複合語「ａ  ｐｒｉｏｒｉ」の最初の部分であるという仮定に基づいて（この場合、この仮定は真である）、そのドメインシンボルとしてスペースを有する遷移である。これらの各遷移をＳ２０でマッチングさせる。この結果、２つの次のコンフィギュレーションが生成される。図１１は、これらの遷移の処理結果である出力エッジを示す。Ｓ４３５でこれらの次のコンフィギュレーションが現在のコンフィギュレーションとなり、Ｓ４４０で現在のコンフィギュレーションの数は２であると判定される。したがって、これらのコンフィギュレーションのひとつ（出力グラフでトークン境界を有する方）が出力としてマークされたとしても、出力処理はまったく考慮されない。２つのコンフィギュレーションが存在するということは、これはピンチポイントではないことを意味するからである。
【００８１】
同様の処理を次のキャラクタ「ｐ」に対しても繰り返し、「ｉ」の後のスペースが検出されるまで「ｒ」、「ｉ」、「ｏ」、「ｒ」、「ｉ」と順次処理を繰り返す。
【００８２】
各キャラクタ位置で２つのコンフィギュレーションが処理され、この結果出力グラフ中で２つの個別のパスＡとＢが生じる。スペースに到達したら、図１０の状態Ｔが現在のコンフィギュレーションの一方の拡張状態であり、状態Ｕがもう一方の拡張状態である。スペースは状態Ｔで単一の遷移でのレンジキャラクタとマッチし、この結果、次のコンフィギュレーションと、トークン境界がラベルされた新規の出力エッジが生成され、複合トークン「ａ  ｐｒｉｏｒｉ」が識別されたことを示す。一方、状態Ｕでは、スペースが唯一の「その他」の遷移とマッチせず、そのパスで次のコンフィギュレーションが生成されない。これは、図１０のトークン分割トランスデューサは、「ｐｒｉｏｒｉ」を単独のトークンとして許可しないという、より高位の制約を含むからである。この事実を反映して、図１１に示すように、上方のパスが「ブロック」される。スペースキャラクタでの双方のコンフィギュレーションを処理したら、Ｓ４３５でひとつだけ生成された新規の次のコンフィギュレーションが現在のコンフィギュレーションになる。現在のコンフィギュレーションがひとつしかないので、それを出力としてマークし（この出力ノードから出る唯一のエッジがトークン境界なので）、ピンチポイントに到達して出力「ａ  ｐｒｉｏｒｉ」が生成され、記憶データをＳ４５０とＳ４５５で消去する。処理はＳ４０５に続く。
【００８３】
前述の例のバリエーションとして、「ａ  ｐｒｉｏｒ」のトークン分割を図１３に示す。この例では、最後の「ｒ」で現在のコンフィギュレーションが処理されるまで、同じ２つのパスが生成される。一方のコンフィギュレーションは、（そのストリングが複合語「ａ  ｐｒｉｏｒｉ」であるという仮定に基づいて）その拡張状態に図１０の状態Ｙを有する。他方のコンフィギュレーションは、（そのストリングが、トークン「ａ」と、その後に文字「ｐｒｉｏｒ」で始まるが、最後のｒの後にｉをひとつだけともなう単語（ｐｒｉｏｒｉ）は除く別のトークンを含むという仮定に基づいて）状態Ｘを有する。この例では、「ｒ」の後のスペースが唯一の遷移である「ｉ：ｉ」遷移とマッチしないので、状態Ｙでのコンフィギュレーションはこの時点でブロックされる。しかし、状態Ｘでスペースは「｜：スペース」遷移とマッチするので、さらに別のコンフィギュレーションのために、次のコンフィギュレーションが生成される。ピンチポイントに到達し、ここで始めてトークンシーケンス「ａ｜ｐｒｉｏｒ」が生成される。すなわち、トークン「ａ」は、そのキャラクタの最初のマッチングの時点では不明確さが残るのでまだ出力が生成されず、さらにテキストキャラクタの処理を進めて、不明確が解決された時点で出力が生成される。
【００８４】
これらの例では、両義性が解決されるピンチポイントもまた、（トークン境界出力エッジを有するので）出力がマークされるコンフィギュレーションとなる。このように、すべての不明確さが解消されるやいなや、出力が生成される。しかし、これが当てはまらない例もある。これを図１２に示す「ａ  ｐｅｒｓｏｎ」のトークン分割の例で説明する。図１２の例では、複合語が見つからないことが明確になるまで、パスＢは維持される。Ｃは現在のコンフィギュレーションを示し、Ｎは次のコンフィギュレーションを示す。パスＡが適正なパスであると判明する。出力がトークン境界でのみ許可されると仮定すると、「ｐｅｒｓｏｎ」の後ろのスペースに到達するまで、出力は生成されず、到達した時点で始めてトークンシーケンス「ａ｜ｐｅｒｓｏｎ」が生成されことになる。しかし、「ｅ」に到達した時点で複合語が存在しないことが明確になり、この時点で“ａ｜”がまちがいなくひとつのトークンであると明確になる。したがって、クライアントは残りのキャラクタ「ｒｓｏｎ」の処理が完了するのを待たなくても、“ａ｜”出力を受け取ってその操作を始めることができるはずである。
【００８５】
この利点を可能にするために、図１１は、不明確さが解消されると直ちに、次の出力マークされたコンフィギュレーションへの到達を待たずとも、出力“ａ｜”を生成する方法を示している。文字「ｅ」で複合語「ａ  ｐｒｉｏｒｉ」を表わすパスがブロックされ、別のパスからのコンフィギュレーションが現在のコンフィギュレーションになると、Ｓ４４０で現在のコンフィギュレーションの数は１であると判定される。Ｓ４４５の判定（出力をマークするか否か）で出力は許可されないが、ここでさらに演算を行って、両義性を含まないそれ以前のトークン境界の位置を特定することができる。
【００８６】
出力エッジのパスは、コンフィギュレーションの出力ノードでスタートして、トークン境界としてラベルされたエッジに到達するか、または２つ以上の出力
エッジを有するノードに遭遇するまで、ノードからノードへと後ろ向きにたどることができる。トークン境界に到達する前に複数エッジの出力ノードに遭遇したなら、どのトークン境界もまだ、これら複数の出力エッジによって表わされる不明確さの中にあり、安全を期して出力は生成されない。ここからさらに個々のエッジのパスをたどってトークン境界に到達したならば、その境界に関して不明確さはなくなるので、その境界からもとの方向への出力グラフを首尾よく出力として生成できる。これを図１２に示す。Ｎコンフィギュレーションから逆にたどるパスは、ｅとｐのエッジを通り、トークン境界「｜」に到達する。トークン“ａ｜”が出力として生成され、出力グラフのその部分のノードとエッジが再利用のために回収される。通過したｐとｅのエッジは、コンフィギュレーションからアクセス可能な出力グラフ中に保持され、Ｓ４１０で処理される。
【００８７】
このようにして、パスが任意の地点で遷移を有するかどうかは、トークンナイザＴと高位の情報源次第であることがわかる。どのようなトークンナイザＴを選択するかは、特定の言語とトークン分割するテキストをどのように使用するかによって決まる。
【００８８】
トークン分割処理工程をさらに理解しやすくするために、さらに「ｗａｌｋ，」のテキスト処理例を以下で説明する。このストリングのトークン分割された出力は「ｗａｌｋ｜，｜」であり、トークン境界はコンマの前に挿入されるとともに、最後のスペースもトークン境界に変換されている。これは、トークン分割トランスデューサＴのエプシロンでラベルされた遷移によって達成される。
【００８９】
図１５は、上記の例と関連するＴのサブセクションを示す。Ｓとラベルされた状態はスタート状態である。単語の多様な最初の文字に対する遷移（ｗ：Ｗ遷移など）があり、これらの遷移は、２番目以降の文字をカバーする遷移を有する状態Ｌにつながる。さらに、ＬからＭ、Ｎを経て、「コンマ−スペース」シーケンスを許可するパスが延びる。コンマパスが状態Ｓからではなく状態Ｌから延びるという事実は、コンマは単語の後に続く句読点として、単語内の少なくともひとつの文字の後に来なければならないという制約を具象化したものである。
【００９０】
状態Ｓでの「Ｗ：Ｗ」遷移は、最初のコンフィギュレーションの処理工程で、Ｓ２０でマッチングされ、図１６に示す状態へとつながる。拡張状態としてのＬと、出力グラフで符号化された「Ｗ」とを有する単一のコンフィギュレーションが存在する。このコンフィギュレーションを処理する際に、「ａ」が現在のキャラクタとなる。Ｓ１０で「ａ：ａ」遷移が選択され、この遷移はＳ２０でマッチして、同じく拡張状態Ｌ次のコンフィギュレーションにつながる。次のコンフィギュレーションの出力グラフは、ストリング「ｗａ」を符号化したものである。しかし、「｜：エプシロン」という遷移が選択された場合、それはＳ１５の判定テストを満たし、この結果、拡張状態がＭである新たな現在のコンフィギュレーションが生成される。その出力グラフはストリング「ｗ｜」を符号化したものであり、これは、テキストが単一文字のトークンを含み、その後ろにコンマがともなうという仮定（まだ未知ではあるが）に基づいている。図１６のコンフィギュレーションを処理した後の状態が図１７である。状態Ｌでのすべての遷移を「ｗ」で処理したら、Ｓ６０からＳ４２０のテストに戻る。このテストは、未処理の現在のコンフィギュレーション、すなわち、状態Ｌでエプシロンレンジの遷移から生成されたコンフィギュレーションがまだあるかどうかを調べるものである。未処理のものがまだあれば、Ｓ４１０で選択し、Ｓ４１５で処理する。
【００９１】
このコンフィギュレーションの拡張状態、すなわち状態Ｍは、「，：，」遷移をひとつだけ有し、これは現在のキャラクタ「ａ」とマッチしない。したがって状態Ｍの処理は、新規のコンフィギュレーションへは移行しない。Ｓ４２０に戻って、未処理の現在のコンフィギュレーションは存在しないので、現在のテキスト位置は「ｌ（エル）」に進み、単一の次のコンフィギュレーションが現在のコンフィギュレーションになる。「ｌ（エル）」での処理は「ａ」での処理とまったく同一の工程を通る。すなわち、新規の次のコンフィギュレーションと、新規の現在のコンフィギュレーションが生成されるが、現在のコンフィギュレーションはそれ以上進むことができない。「ｋ」でも同様の処理を行い、図１８の状態に進む。ここでも、拡張状態Ｌを有するコンフィギュレーションはひとつだけであり、現在のテキストキャラクタは「，（コンマ）」である。状態Ｌで、そのレンジシンボルにコンマを有する遷移はないので、生成され得る新規のコンフィギュレーションは、図１９に示すように、拡張状態Ｍを有する現在のコンフィギュレーションである。このコンフィギュレーションからの出力グラフは、ストリング「Ｗａｌｋ｜」を符号化したものである。
【００９２】
このコンフィギュレーションを選択して処理すると、状態Ｍでの単一の遷移が現在のテキスト位置でコンマとマッチし、図２０に示すように、次のコンフィギュレーションにつながる。拡張状態はＮであり、符号化された出力ストリングは「Ｗａｌｋ｜，」である。新規の次のコンフィギュレーションが現在のコンフィギュレーションとなり、状態Ｎでの単一の遷移が現在のテキストキャラクタ（すなわちスペース）とマッチし、出力「Ｗａｌｋ｜，｜」が生成される。これで図３および４に示した処理工程が完了したことになる。
【００９３】
上述のように、本発明によれば限られた記憶スペースだけで処理が可能になる。現在のコンフィギュレーションは、各テキスト位置での処理が完了した後にＳ４２５で解除され、ピンチポイントで出力が生成された場合はかならず、Ｓ４６０において、出力格納と残っている単一のコンフィギュレーションをクリアにして、再利用する。もちろん、上述したように、出力記憶装置中のノードとエッジを必要以上に長く保持する場合もある。この状況は、両義性が検出された場合に生じ、その場合、コンフィギュレーションの２つ以上のパスに沿って処理を進める。それらのパスのひとつにおいて、そのパスに独自の出力エッジとノードがクリアされリサイクルされたならば、このパスはブロックし、以降の処理に対する要求はまったくない。この状況は図１３の「ａ  ｐｒｉｏｒ」の例で示されている。下方のパスのコンフィギュレーションがブロックすると、「（スペース）ｐｒｉｏｒ」を符号化するすべてのノードとエッジはもはや必要ではなくなる。いずれにしてもそれらは次の出力ピンチポイントで再利用されるが、本発明は、単純な基準カウントによる不要部分の整理（garbage-collection）によって、この記憶出力の簡単な検出と早期の再利用を可能にする。
【００９４】
出力エッジがグラフに追加されるたびに、エッジが指し示すノードと関連するカウントがひとつインクリメントされる。これらの基準カウントは、出力ノードが生成されるたびに初期化される。したがって、ノードでのカウントは常に、それにつながるエッジの数を示す。ある所定のコンフィギュレーションを処理した結果、新規のコンフィギュレーションが生成されたとすると、新規のコンフィギュレーションの出力ノードから、その所定のコンフィギュレーションの出力を指し示すエッジが生成され、所定のコンフィギュレーションの出力ノードの基準カウントは、もはやゼロではなくなる。一方、新規のコンフィギュレーションが生成されない場合は、パスがブロックしたことを示し、基準カウントはまだゼロ（０）のままである。この場合は、コンフィギュレーション記憶が不要部分として回収整理されるだけではなく、その出力ノードと、そのノードから出るすべてのエッジも回収される。エッジが回収されると、それが指し示すノードの基準カウントがひとつ減少する。この結果そのノードのカウントがゼロ（０）になったならば、プロセスを繰り返してそのノードとそこから出るエッジも回収される。この繰り返しが完了したら、不必要なノードとエッジの集合を戻して記憶を解除し、記憶装置を再使用可能にする。図１２の例では、スペースおよびトークン境界が指し示すノードは、基準カウント「２」を有するが、それ以外のノードはすべて基準カウント「１」である。下方のコンフィギュレーションがブロックすると、そのノードと「ｐ」エッジがリサイクルされ、「スペース」エッジを有する下方のノードがゼロになり、このノードも「スペース」エッジとともにリサイクルされる。この繰り返しは、「ａ」エッジを有するノードに到達した時点で基準カウントが「２」から「１」になるので、そこで終了する。
【００９５】
Ｔそれ自体が直線的に境界付けられる場合は、基準カウントガベッジコレクタは、できる限り早く記憶を回収できることになる。Ｔはほとんどの場合直線的に境界づけられる。すなわち、ドメインストリングの長さが、それに対応するレンジストリングの長さのｋ倍を越えないような係数ｋが存在する。直線境界付けは、トランスデューサが有することのできる周知の特性である（例えば、コムスキー（Chomsky ）の「文法の形式特性（Formal Property of Grammar）」に延べられている直線境界トランスデューサを参照）。所定の状態からその同一の状態に戻る遷移または一連の遷移があり、それらすべてがレンジシンボルとしてエプシロンを有する場合は、Ｔは直線的に境界付けされない。このような場合は、出力グラフはループになる。ループを成す遷移は、ループが全体として必要でなくなっても、基準カウントがゼロになることを防げる。この場合、単純な基準カウント方法では、論理的に可能になると直ちにすべての出力記憶を収集整理するという保証はされない。しかし、Ｔが直線的に境界付けされなくても、ガーベッジ（不要部分）は、次のピンチポイントで回収される。
【００９６】
本発明はまた、各ピンチポイントで出力されるすべての出力をつなぎ合わせると、式Ｄｏｍ（Ｔ  ｏ  Ｉｄ（ｔｅｘｔ））の演算結果であるストリング集合（または均等の有限状態マシン）になるという意味で、各ピンチポイントでの出力がそれぞれ適正であるが確証される。テキストが全体として適正に構成されている場合、すなわちＤｏｍ（Ｔ  ｏ  Ｉｄ（ｔｅｘｔ））で示される言語が少なくともひとつのストリングを含む場合は、各ピンチポイントでの出力は有効であり、クライアアントによって行われる以降の処理を取り消す必要はなくなる。テキストが全体として不適正な構成で、テキスト全体に有効なトークン分割がない場合は、いずれかのポイントでＳ４６５の結果フラグとして値「ＦＡＩＬ」が返される。この場合、クライアントは、以前のピンチポイントからの出力に対して行った処理を撤回しなければならない。もちろん、Ｔのレンジがシグマ＊、すなわちアルファベットのΣに関するすべてのストリング集合である場合、Ｔは、このアルファベットにおいてのみ、キャラクタを有するすべてのテキストにトークン分割を施す。Ｔがこの特性を有するかどうかを判定するのは容易である。
【００９７】
本発明のテキストトークン分割システムにおいて、トークン分割されたストリングの集合を出力するのは可能であるが、上述したように、トークン分割出力は一般に有限状態マシンの形で出力される。図６は、図７の後方へ進む有限状態マシンに対応する出力グラフである。テキスト「Ｊａｎ．」を横断した結果得られるトークン分割出力において、入力「Ｊａｎ．」は有限状態マシンの弧（エッジ）の上にラベル付けされている。状態は有限状態マシンの弧と弧の間のノードで示される。図から明らかなように、ここには３つのパスが存在する。すなわち、「Ｊａｎ．｜」、「Ｊａｎ｜．」、「Ｊａｎ．｜．」であるが、これら３つのパスはピリオドの後でひとつになる。
【００９８】
また、トークン分割したストリングの形で出力を生成することも可能である。トークン分割出力はまた、グラフデータ構造、例えばより高位の構文解析のための品詞解析の初期チャートなどにコピーすることが可能である。
【００９９】
トークンナイザＴそれ自体の機能に加え、より高位の制約に基づいてテキストを評価することによって、可能なトークン分割の多くを制限することができる。高位の制約によって、処理の初期段階で不適切なトークン分割が消去される。さらに追加の制約が正則関係として表現され得る場合は、それらをオリジナルの公式に組み込んで、制約に幅を持たせたトークン分割マッピングを行うことができる。
【０１００】
Ｌが正則の語彙関係であり（米国特許出願第０８／２５５、５０４号（FiniteState Transdaption Of Related Word Forms For Text Indexing And Retriev-al）参照）、語幹−タグのストリングのシーケンスを、トークン境界で分割された対応の単語の変化後の形態にマップすると、マッピングの結果は次式で表わされる。
【０１０１】
Ｄｏｍ（Ｌ  ｏ  Ｔ  ｏ  Ｉｄ（ｔｅｘｔ））      ．．．  （２）
式（２）は、トークン分割したテキストの語形論的解析を定義するものである。合成は連想演算なので、（２）式をさらに次のように書き直すことができる。
【０１０２】
Ｄｏｍ（（Ｌ  ｏ  Ｔ）  ｏ  Ｉｄ（ｔｅｘｔ））  ．．．  （３）
語彙関係ＬとトークンナイザＴは、テキストとは独立のものなので、成分”Ｌｏ  Ｔ”を翻訳時（コンパイル時）に評価して、トークン分割語幹を表面テキストにマップする新規のトランスデューサ「ＬＴ」を生成することもできる。本発明のテキストトークン分割システムを、トランスデューサＬＴに適用することによって、テキストのトークン分割の語形論的分析が可能になる。
【０１０３】
しかしながら、翻訳時にＬおよびＴのトランスデューサを合成してトークン分割処理がまちがいなくスピードアップできるとしても、この翻訳工程を行うのが不都合な場合もある。例えば、合成を行うアルゴリズムが使用できない、結果としての単一のトランスデューサが大きすぎて限られたメモリで処理できないなどである。そのような場合は、本発明を容易に拡張して、トークン分割を実行する過程で２つのトランスデューサの合成をシミュレート（模擬）することが可能である。すなわち、単一の有限状態トランスデューサの状態を、コンフィギュレーションの拡張状態として機能させる代わりに、拡張状態は、Ｌトランスデューサからの状態と、Ｔトランスデューサからの状態との状態対になる。遷移をマッチングする処理工程は、Ｔ遷移のレンジキャラクタがテキストにマッチし、かつ対応のドメインキャラクタが、Ｔ状態と対をなすＬ状態での遷移のレンジキャラクタにマッチするときに新規のコンフィギュレーションが生成されるように、一般化される。出力エッジには、Ｌ遷移のドメインキャラクタがラベル付けされる。この結果としての出力グラフは、テキストをＴでトークン分割し、語彙関係Ｌを通過して出力されたストリングだけを表わす。
【０１０４】
上記の結果としての出力は、高位の制約条件Ｌのレベル次第で決定される。Ｌは、テキストの完全な語形論的解析を行う膨大な辞書でもよいが、完全な解析が望ましくない場合は、トークンナイザに追加する情報量を抑さえて、トークン分割関係を増やすことができる。
【０１０５】
少量の追加情報だけでも、すべてのスペースをトークン境界または複合語の内部スペースとして解釈し、すべてのピリオドを文末境界または省略語として解釈した結果生じる、極端な不明確さを制御することができる。
【０１０６】
次式（４）では、Ｍは既知の複合語のリストであり、Ａは許容される省略語のリストである。Ｘはスペースもピリオドも含まないすべてのストリング集合である。正則言語「ＸＡＭ」は、ＸとＡとＭの結合である。この言語でのストリングは、スペースやピリオドがＭまたはＡにない限り、スペースもピリオドも含まない。
【０１０７】
Ｉｄ（［ＸＡＭ｜）＊ＸＡＭ］）ｏＴ    ．．．（４）
上記の（４）式の関係は、ＭまたはＡに含まれるストリングに対してのみ、スペース／ピリオドに関連する両義牲を生成するトークン分割関係として使用され得る。
【０１０８】
より高位の制約が出力を制限するのに有効であってもなくても、上述のスプロウト（Ｓｐｒｏａｔ）が提案した重み付けトランスデューサの使用を、本発明に適用することができる。スプロウト（ｓｐｒｏａｔ）は、トークン分割トランスデューサの遷移に重み付けを与えており、、ここで重みは、ある任意の遷移が取られる可能性のロガリズムの負数として解釈される。Ｓｐｒｏｕｔは、ベストパス関数を適用して、トークン分割の結果が式で与えられることを提案している（Ｓｐｒｏａｔは、Ｔのドメインとレンジの位置を反対にしているが）。
【０１０９】
ＢｅｓｔＰａｔｈ（Ｄｏｍ（Ｔ  ｏ  ＩＤ（ｔｅｘｔ））    ．．．（５）
ＢｅｓｔＰａｔｈは、一連の遷移の重みが加算されたときに最大数となる遷移のシーケンスによって生成されるストリングを出力として選択する。本発明のピンチポイント演算は、どのピンチポイントでのストリング出力も、その他すべてのピンチポイント出力での任意のストリングと調和することを保証する。すなわち、テキスト全体を通過するベストパスは必ず、各ピンチポイント出力でベストパスとして選択されたストリングを連結したものでなければならない。本発明を、Ｓｐｒｏａｔのベストパストークン分割を増分的な方法で演算する方法に拡張できることは明らかである。Ｔの遷移が生成される出力エッジ上で遷移の重みを単純に記録して、その重みを使用して各ピンチポイントでのベストパス演算が実行できるようにすればよい。
【０１１０】
本発明を上述の特定の実施形態に基づいて延べてきたが、当業者にとって多様な代用、変形が可能であることはいうまでもない。上記実施形態は本発明の一例にすぎず、本発明の原理と範囲内で多様な変化が可能である。
【０１１１】
【発明の効果】
本発明のテキストトークン分割方法によれば、ピンチポイントを使用し、ピンチポイントごとに出力を生成する。各ピンチポイントでの出力は、幅優先方式の処理によって、それが適正な出力であると保証されるので、出力生成語は、それまでの処理の記憶を消去できる。したがって、限られた記憶スペースで効果的にテキストを分割できる。
【図面の簡単な説明】
【図１】  本発明によるテキストのトークン分割方法に用いる装置の好適な実施形態を示すブロック図である。
【図２】  本発明の方法の基本的な処理工程を示すフローチャートである。
【図３】  図２のフローチャートのうち、テキストのトークン分割ステップの詳細を示すフローチャートである。
【図４】  コンフィギュレーションを処理する処理オペレーションを示すフローチャートである。
【図５】  文字列「ＡＢ」の有限状態トランスデューサを示す図である。
【図６】  トークン分割グラフの形態でのサンプル出力を示す図である。
【図７】  図６のサンプル出力に対応する有限状態マシンの図である。
【図８】  コンフィギュレーションを示すブロック図である。
【図９】  文字列「ｇｏ  ｆｏｒ」の処理を示す図である。
【図１０】  文字列「ｇｏ  ｆｏｒ」、「ａ  ｐｒｉｏｒｉ」、「ｐｒｉｏｒ」、「ａ  ｐｅｒｓｏｎ」に関するトークン分割トランスデューサのサブセクションを示すグラフである。
【図１１】  「ａ  ｐｒｉｏｒｉ」の出力グラフの図である。
【図１２】  「ａ  ｐｅｒｓｏｎ」のトークン分割を示す図である。
【図１３】  「ａ  ｐｒｉｏｒ」のトークン分割を示す図である。
【図１４】  「ａ  ｐｒｉｅｓｔ」のトークン分割を示す図である。
【図１５】  単語「ｗａｌｋ」のトークン分割トランスデューサのサブセクションを示す図である。
【図１６】  単語「ｗａｌｋ」のトークン分割出力を示す図である。
【図１７】  単語「ｗａｌｋ」のトークン分割出力を示す図である。
【図１８】  単語「ｗａｌｋ」のトークン分割出力を示す図である。
【図１９】  単語「ｗａｌｋ」のトークン分割出力を示す図である。
【図２０】  単語「ｗａｌｋ」のトークン分割出力を示す図である。
【符号の説明】
１０  テキスト記憶ユニット
２０  トークン分割手段
３０  判定手段
４０  記憶ユニット
４５  出力記憶ユニット
５０  比較手段
６０  カウント手段
７０  制御手段
１００  テキストトークン分割システム。
【図１】
0004213228.tif 000002
【図２】
0004213228.tif 000003
【図３】
0004213228.tif 000004
【図４】
0004213228.tif 000005
【図５】
0004213228.tif 000006
【図６】
0004213228.tif 000007
【図７】
0004213228.tif 000008
【図８】
0004213228.tif 000009
【図９】
0004213228.tif 000010
【図１０】
0004213228.tif 000011
【図１１】
0004213228.tif 000012
【図１２】
0004213228.tif 000013
【図１３】
0004213228.tif 000014
【図１４】
0004213228.tif 000015
【図１５】
0004213228.tif 000016
【図１６】
0004213228.tif 000017
【図１７】
0004213228.tif 000018
【図１８】
0004213228.tif 000019
【図１９】
0004213228.tif 000020
【図２０】
0004213228.tif 000021