(57)【要約】【課題】  単語解析のためのシステムおよび方法を提供する。【解決手段】  入力テキスト解析のコンピュータで実施される方法は、入力テキスト内の遷移を規則エンジン内の遷移と比較するステップを含む。この方法は、規則エンジンの形態素に見つかったキャラクタ、および規則に応じた語尾変化したバリエーションと規則に応じた語境界とに関連付けられた入力テキストの少なくとも１つとに基づいて入力テキストの遷移が規則エンジンで見つかるか否かを判定するステップも含む。【選択図】  図１
2004303240.tif 000002
【特許請求の範囲】
【請求項１】
複数の遷移を含む入力テキストを解析するためのコンピュータで実施される方法において、
前記入力テキストの前記複数の遷移のそれぞれに対して、
前記入力テキストの遷移を規則エンジンの遷移と比較するステップと、
前記規則エンジンの形態素に見つかったキャラクタ、および規則に応じた語尾変化したバリエーションと前記規則に応じた語境界とに関連付けられた前記入力テキストの少なくとも１つとに基づいて前記入力テキストの遷移が前記規則エンジンで見つかるか否かを判定するステップと
を備えることを特徴とする方法。
【請求項２】
前記入力テキストの前記遷移が前記規則エンジンの遷移で見つからないと判定された場合、前記規則エンジンの実現可能な遷移を提案するステップと、前記実現可能な遷移にコストを適用するステップとをさらに備えることを特徴とする請求項１に記載のコンピュータで実施される方法。
【請求項３】
前記規則エンジンで見つからなかった前記入力テキストのすべての遷移のための合計コストを計算するステップをさらに備えることを特徴とする請求項２に記載のコンピュータで実施される方法。
【請求項４】
前記実現可能な遷移の前記コストが高すぎると判定された場合、前記実現可能な遷移を破棄するステップをさらに備えることを特徴とする請求項３に記載のコンピュータで実施される方法。
【請求項５】
前記入力テキストの前記遷移が語境界であるという指示を提供するステップをさらに備えることを特徴とする請求項１から４のいずれかに記載のコンピュータで実施される方法。
【請求項６】
語境界に基づいて前記規則エンジンの遷移で前記入力テキストの前記遷移が見つかったと判定された場合、前記入力テキストの形態素解析を提供するステップをさらに備えることを特徴とする請求項１から５のいずれかに記載のコンピュータで実施される方法。
【請求項７】
前記入力テキストの前記遷移が形態素の境界であるという指示を提供するステップをさらに備えることを特徴とする請求項１から６のいずれかに記載のコンピュータで実施される方法。
【請求項８】
前記判定するステップに応じて前記入力テキストのスペルチェック解析の指示を提供するステップをさらに備えることを特徴とする請求項１から７のいずれかに記載のコンピュータで実施される方法。
【請求項９】
複数の遷移を含む入力テキストを解析するためのコンピュータ可読媒体において、コンピュータによって実行された場合に請求項１から８のいずれかによる方法を実行する命令を含むことを特徴とするコンピュータ可読媒体。
【請求項１０】
入力テキストの単語解析用に単語を処理するためのシステムにおいて、
複数の自由形態素および拘束形態素を記憶するための辞典と、
語尾変化したバリエーションへの自由形態素の変形を規定する正字法規則モジュールと、
前記自由形態素および前記拘束形態素、ならびに前記語尾変化したバリエーションおよび前記拘束形態素の許容し得る結合を規定する形態素結合モジュールと
を備えることを特徴とするシステム。
【請求項１１】
前記辞典は、前記自由形態素に対する語境界と、自由形態素および拘束形態素、ならびに語尾変化したバリエーションおよび拘束形態素の前記許容できる結合との指示を含むことを特徴とする請求項１０に記載のシステム。
【請求項１２】
前記辞典は、前記自由形態素のそれぞれに対する意味論的情報と、自由形態素および拘束形態素、ならびに語尾変化したバリエーションおよび拘束形態素の前記許容できる結合との指示を含むことを特徴とする請求項１０または１１に記載のシステム。
【請求項１３】
前記辞典は、前記自由形態素のそれぞれに対する構文情報と、自由形態素および拘束形態素、ならびに語尾変化したバリエーションおよび拘束形態素の前記許容できる結合との指示を含むことを特徴とする請求項１０から１２のいずれかに記載のシステム。
【請求項１４】
前記辞典はトライ構造形式で記憶されており、前記正字法規則モジュールおよび前記形態素結合モジュールが前記トライ構造内の実現可能な遷移を規定することを特徴とする請求項１０から１３のいずれかに記載のシステム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、言語またはテキスト処理に関する。より詳細には、本発明は、入力テキストを解析するための改善された方法および装置に関する。
【背景技術】
【０００２】
言語またはテキスト処理は、多種類のシステムを含んでいる。例えば、パーサ、スペルチェッカ、文法チェッカ、ワードブレーカ、形態素解析器、自然言語プロセッサ、および理解システム（understanding  system）は、この広範なカテゴリに含まれるシステムの種類の数例にすぎない。
【０００３】
これらシステムの多くは入力テキストを解析する際に有用である。例えば、スペルチェッカは、入力テキストが辞書の単語に相当するか、または一致するかを判定するために入力テキスト内の単語を辞書または辞典（lexicon）と比較する。入力テキストが辞書で見つからず、したがってスペリングミスである可能性があるという指示がユーザに提供される場合がある。スペリングミスした単語を訂正する提案も提供される場合がある。スペルチェッカは、入力テキストが辞書の単語の正規な語尾変化に相当するか否かを判定し、スペリングミスした単語に対して辞書の単語の正規な語尾変化の提案を提供する必要がある場合もある。
【０００４】
単語の分割または単語のセグメント化は、文書テキストのような言語表現を構成する１つ１つの単語を識別するプロセスを意味している。単語のセグメント化は、スペルおよび文法のチェック、テキストからの音声の合成、音声認識、情報の取り出し、および自然言語の構文解析および理解の実行に有用である。一般にスペースおよび句読点がテキスト内の個々の単語を区切るので、英文テキストの単語のセグメント化はむしろ直線的であってよい。しかし中国語のような他の言語では、語境界は明示的というよりも暗黙的である。したがって、語境界に対する提案の提示は言語処理において有用である。
【０００５】
形態素解析器は、非原形（non-root  form）から用語の原形（root  from）を識別することに関係している。例えば、単語「ｒｕｎｎｉｎｇ」の形態素解析は原形として「ｒｕｎ」を識別する。形態素解析器は、原形を探し出すために非常に語尾変化した言語に関して大量のデータを記憶することを必要とする。一度原形が探し出されると、構文解析または情報の検索など、さらなる処理のためにその原形を使用することができる。
【０００６】
【特許文献１】米国特許第６，１３１，１０２号明細書
【発明の開示】
【発明が解決しようとする課題】
【０００７】
一般に、上記のシステムは、英語、フランス語、ドイツ語、スペイン語、中国語、および日本語を含む様々な異なる言語用にカスタマイズされている。さらに、言語解析が複雑な性質を有することから、独立して実行されるべき処理は制限されているが、これは非常に厄介なことである。したがって、入力テキストの様々な解析を提供することができる汎用言語処理システムが求められている。
【課題を解決するための手段】
【０００８】
本発明の一態様は、複数の遷移を含む入力テキストを解析するためのコンピュータで実施される方法である。入力テキストの複数の遷移のそれぞれに対して、この方法は、入力テキストの遷移を規則エンジンの遷移と比較する。次いで、規則エンジンの形態素に見つかったキャラクタ、および規則に応じた語尾変化したバリエーションまたは規則に応じた語境界に関連付けられた入力テキストの少なくとも１つとに基づいて入力の遷移が規則エンジンで見つかるか否かに関して判定がなされる。入力テキストの遷移が規則エンジンの遷移で見つからないと判定された場合、この方法は、規則エンジンの実現可能な遷移をさらに提案し、その実現可能な遷移にコストを適用することができる。
【０００９】
コンピュータによって実施される方法は、スペルの提案、形態素解析、および語境界候補を提供する統合された有効な方法を提供する。規則エンジンでの遷移は、入力テキストの単語解析を提供するために様々な言語学的規則によって規定される。
【００１０】
本発明の別の態様は、入力テキストの単語解析を提供するシステムである。このシステムは、辞典、正字法規則モジュール、および形態素結合モジュールを含む。辞典は、複数の自由形態素と拘束形態素とを含む。正字法規則モジュールは、語尾変化したバリエーションへの自由形態素の変形を規定する。また、形態素結合モジュールは、自由形態素および拘束形態素、ならびに語尾変化したバリエーションおよび拘束形態素の許容し得る結合を規定する。したがって、語尾変化したバリエーションからの変形は正字法規則モジュールで規定されているので、辞典は自由形態素と拘束形態素とを記憶するだけでよい。辞典は、自由形態素のそれぞれに対する語境界、意味論的情報、および構文情報の指示と、自由形態素および拘束形態素、ならびに語尾変化したバリエーションおよび拘束形態素の許容できる結合とをさらに含むことができる。
【発明を実施するための最良の形態】
【００１１】
図１は、一般にテキストストリング形式である言語入力１２を受け取り、これもまた同様に一般にテキストストリング形式である言語出力１４を提供するために言語入力１２を処理する言語またはテキスト処理システム１０を全体的に表している。例えば、言語処理システム１０は、ワードプロセッシング、言語構文解析、および／または情報の取り出しで使用することができる。これらの応用例に提供される出力１４は、スペルチェック解析、単語分割解析（word  breaking  analysis）、形態素解析、および／またはこれらの組合せの指示であってよい。当業者には理解されようが、言語処理システム１０は、スタンドアロンのアプリケーションであっても、別のシステムによってアクセス可能な、または別のシステムに含まれる１つのモジュールまたはコンポーネントであってよい。
【００１２】
一般に、言語処理システムは、テキストアナライザ２０と規則エンジン２２とを含む。テキストアナライザ２０は、入力１２を受け取り、規則エンジン２２にアクセスしてそこから情報取得し、出力１４を提供するために単語情報を処理するコンポーネントまたはモジュールを概略的に示している。本発明の一態様は、形態素、スペリングエラー、および単語分割を識別するために入力テキストを解析するための改善された規則エンジン２２を取り扱っている。規則エンジン２２が、多くの言語処理システムで多くの形式のテキストアナライザにより使用することができる別個のコンポーネントであることに鑑みて、テキストアナライザ２０の規則エンジン２２との一般的な相互作用を説明するが、本発明を理解するためには必要ないのでテキストアナライザの様々な形式に関する具体的な説明は省く。
【００１３】
本発明をさらに詳細に検討する前に、動作環境を概観しておくことは有益であろう。図２は、本発明を実施することのできる適切なコンピューティングシステム環境５０の一例を示している。このコンピューティングシステム環境５０は、適切なコンピューティング環境の一例であるに過ぎず、本発明の適用範囲または機能に関する限定を示唆することを目的としたものではない。また、コンピューティング環境５０は、動作環境例５０に示したコンポーネントのどの１つ、またはどのような組合せに対するいかなる依存または要件を有するものとも理解されるべきではない。
【００１４】
本発明は、多数の他の汎用または専用コンピューティングシステム環境または構成で動作可能である。本発明と共に使用するのに適したよく知られたコンピューティングシステム、環境、および／または構成の例は、限定はしないが、パーソナルコンピュータ、サーバコンピュータ、ハンドヘルドまたはラップトップデバイス、マルチプロセッサシステム、マイクロプロセッサベースのシステム、セットトップボックス、プログラム可能な家庭用電化製品、ネットワークＰＣ、ミニコンピュータ、メインフレームコンピュータ、上記システムまたはデバイスのどれかを含む分散型コンピューティング環境などを含む。
【００１５】
本発明は、コンピュータによって実行される、プログラムモジュールのようなコンピュータ実行可能命令の一般的な状況で説明することができる。一般に、プログラムモジュールは、特定のタスクを実行し、または特定の抽象データタイプを実施するルーチン、プログラム、オブジェクト、コンポーネント、データ構造などを含む。本発明は、通信ネットワークを介してリンクされるリモート処理デバイスによってタスクが実行される分散型コンピューティング環境でも実施することができる。分散型コンピューティング環境では、プログラムモジュールは、記憶装置を含むローカルおよびリモートコンピュータ記憶媒体の両方に配置することができる。プログラムおよびモジュールによって実行されるタスクを、以下で図面を参照しながら説明する。当業者には、コンピュータ可読媒体のいかなる形式でも書き込むことのできるプロセッサ実行可能命令として以下の説明および図面を実施することができよう。
【００１６】
図２を参照すると、本発明を実施するための例示的システムはコンピュータ６０の形式の汎用コンピューティングデバイスを含む。コンピュータ６０のコンポーネントは、限定はしないが、処理装置７０、システムメモリ８０、およびシステムメモリを含む様々なシステムコンポーネントを処理装置７０に結合するシステムバス７１を含む。システムバス７１は、メモリバスまたはメモリコントローラ、周辺バス、および様々なバスアーキテクチャのどれかを使用するローカルバスを含めて数種類あるバス構造のどれであってもよい。限定ではなく、一例として、このようなアーキテクチャは、業界標準アーキテクチャ（ＩＳＡ）バス、マイクロチャネルアーキテクチャ（ＭＣＡ）バス、拡張ＩＳＡ（ＥＩＳＡ）バス、ビデオ電子規格化協会（ＶＥＳＡ）ローカルバス、およびＭｅｚｚａｎｉｎｅバスとしても知られる周辺装置相互接続（ＰＣＩ）バスを含む。
【００１７】
コンピュータ６０は、通常、様々なコンピュータ可読媒体を含む。コンピュータ可読媒体は、コンピュータ６０によってアクセス可能ないかなる使用可能な媒体であってもよく、揮発性／不揮発性媒体および取り外し可能／固定媒体の両方を含む。限定ではなく、一例として、コンピュータ可読媒体は、コンピュータストレージ媒体および通信媒体を含むことができる。コンピュータ記憶媒体は、コンピュータ可読命令、データ構造、プログラムモジュール、または他のデータのような情報の記憶のためのいかなる方法または技術でも実施される揮発性／不揮発性および取り外し可能／固定媒体の両方を含む。コンピュータ記憶媒体は、限定はしないが、ＲＡＭ、ＲＯＭ、ＥＥＰＲＯＭ、フラッシュメモリ、または他のメモリ技術と、ＣＤ−ＲＯＭ、デジタル多用途ディスク（ＤＶＤ）、または他の光ディスク記憶と、磁気カセット、磁気テープ、磁気ディスク記憶、または他の磁気記憶装置と、または所望の情報を記憶するために使用することができ、コンピュータ６０によってアクセス可能な他の媒体を含む。
【００１８】
通信媒体は、通常、コンピュータ可読命令、データ構造、プログラムモジュール、または搬送波または他の伝送機構のような変調されたデータ信号形式の他のデータを具現し、いかなる情報伝達媒体をも含む。「変調されたデータ信号」という用語は、信号の情報を符号化するような方法で設定または変更したその特徴のうちの１つまたは複数を有する信号を意味する。限定ではなく、一例として、通信媒体は、有線ネットワークまたは直接有線接続のような有線媒体、アコースティック、ＦＲ、赤外線、および他の無線媒体のような無線媒体を含む。上記のどの組合せも、コンピュータ可読媒体の範囲に含まれるべきである。
【００１９】
システムメモリ８０は、読み取り専用メモリ（ＲＯＭ）８１およびランダムアクセスメモリ（ＲＡＭ）８２のような揮発性および／または不揮発性メモリの形式のコンピュータ記憶媒体を含む。起動時などにコンピュータ６０内の素子間での情報の転送に役立つ基本ルーチンを含んでいる基本入出力システム８３（ＢＩＯＳ）は、通常、ＲＯＭ  ８１に記憶されている。ＲＡＭ  ８２は、通常、処理装置７０によって直接アクセス可能、かつ／または処理装置７０で現在操作中のデータおよび／またはプログラムモジュールを含んでいる。限定ではなく、一例として、図３は、オペレーティングシステム８４、アプリケーションプログラム８５、他のプログラムモジュール８６、およびプログラムデータ８７を示している。
【００２０】
コンピュータ６０は、他の取り外し可能／固定揮発性／不揮発性コンピュータ記憶媒体を含むこともできる。単なる一例として、図２は、固定な不揮発性磁気媒体から読み取りまたは書き込むハードディスクドライブ９１、取り外し可能不揮発性磁気ディスク１０２から読み取りまたは書き込む磁気ディスクドライブ１０１、およびＣＤ  ＲＯＭまたは他の光媒体のような取り外し可能不揮発性光ディスク１０６から読み取りまたは書き込む光ディスクドライブ１０５を示している。動作環境例で使用することができる他の取り外し可能／固定揮発性／不揮発性コンピュータ記憶媒体は、限定はしないが、磁気テープカセット、フラッシュメモリカード、デジタル多用途ディスク、デジタルビデオテープ、固体ＲＡＭ、固体ＲＯＭなどを含む。ハードディスクドライブ９１は、通常、インターフェース９０のような固定メモリインターフェースを介してシステムバス７１に接続されており、磁気ディスクドライブ１０１および光ディスクドライブ１０５は、通常、インターフェース１００のような取り外し可能メモリインターフェースによってシステムバス７１に接続されている。
【００２１】
上記で検討し、図２に示した複数のドライブおよびそれらに関連するコンピュータ記憶媒体は、コンピュータ可読命令、データ構造、プログラムモジュール、および他のデータのストレージをコンピュータ６０に提供する。図２で、例えば、ハードディスクドライブ９１は、オペレーティングシステム９４、アプリケーションプログラム９５、他のプログラムモジュール９６、およびプログラムデータ９７を記憶しているものとして示されている。これらのコンポーネントは、オペレーティングシステム８４、アプリケーションプログラム８５、他のプログラムモジュール８６、およびプログラムデータ８７と同じであっても異なってもよいということに留意されたい。オペレーティングシステム８４、アプリケーションプログラム８５、他のプログラムモジュール８６、およびプログラムデータ８７には、少なくともそれらが異なるものであることを示すために本明細書では別々の番号を付番している。
【００２２】
ユーザは、キーボード１１２、マイクロフォン１１３、ハンドライティングタブレット１１４、およびマウス、トラックボール、またはタッチパッドのようなポインティングデバイス１１１のような入力装置によってコマンドおよび情報をコンピュータ６０に入力することができる。他の入力装置（図示せず）は、ジョイスティック、ゲームパッド、衛星放送受信アンテナ、スキャナなどを含むことができる。これらまたは他の入力装置は、システムバスに結合されているが、パラレルポート、ゲームポート、またはユニバーサルシリアルバス（ＵＳＢ）のような他のインターフェースおよびバス構造によっても接続することのできるユーザ入力インターフェース１１０を介して処理装置７０に接続されることがしばしばある。モニタ１４１または他の種類の表示装置は、ビデオインターフェース１４０のようなインターフェースを介してシステムバス７１にも接続される。モニタに加え、コンピュータは、出力周辺インターフェース１４５を介して接続することのできるスピーカ１４７およびプリンタ１４６のような他の周辺出力装置を含むこともできる。
【００２３】
コンピュータ６０は、リモートコンピュータ１３０のような１つまたは複数のリモートコンピュータへの論理接続を使用するネットワーク接続された環境で動作することができる。リモートコンピュータ１３０は、パーソナルコンピュータ、ハンドヘルドデバイス、サーバ、ルータ、ネットワークＰＣ、ピアデバイス、または他の共通ネットワークノードであってよく、また、通常、コンピュータ６０に関して上述した要素の多くまたはすべてを含む。図２に示した論理接続は、ローカルエリアネットワーク（ＬＡＮ）１２１、ワイドエリアネットワーク（ＷＡＮ）１２３を含むが、他のネットワークも含む。このようなネットワーク接続された環境は職場、企業規模コンピュータネットワーク、イントラネット、およびインターネットには一般に見られる。
【００２４】
ＬＡＮネットワーク接続環境で使用される場合、コンピュータ６０はネットワークインターフェースまたはアダプタ１２０を介してＬＡＮ１２１に接続される。ＷＡＮネットワーク接続環境で使用される場合、コンピュータ６０は、通常、インターネットのようなＷＡＮ  １２３を介して通信を確立するためのモデム１２２または他の手段を含む。内蔵であっても外付けであってもよいモデム１２２は、ユーザ入力インターフェース１１０または他の適切な機構を介してシステムバス７１に接続することができる。ネットワーク接続された環境では、コンピュータ６０に関して示したプログラムモジュールまたはその一部をリモート記憶装置に記憶することができる。限定ではなく、一例として、図２は、リモートアプリケーションプログラム１３５をリモートコンピュータ１３０に常駐しているものとして示している。図示したネットワーク接続は一例であって、コンピュータ間に通信リンクを確立する他の手段も使用することができるということを理解されたい。
【００２５】
テキストアナライザ２０は、コンピュータ６０に常駐してもよく、あるいはリモートコンピュータ１３０のようなコンピュータ６０と通信する他のいかなるコンピュータに常駐してもよいということを理解されたい。同様に、規則エンジン２２は、上記の記憶装置のいずれかの形式でコンピュータ６０に常駐してもよく、あるいは適切な通信リンクを介してアクセス可能としてもよい。
【００２６】
一実施形態では、本発明に関する辞書情報はトライ（trie）で記憶されている（デジタルツリーとしても知られている）。トライを表すには、一連のノードとしてトライを表すような複数の方法がある。図３は、辞書の様々な単語を示す、トライ２００のノードを含んでいるトライデータ構造の図面である。各ノード、例えばノード２０５は１つの文字を表しており、１つまたは複数のフラグを含むこともできる。フラグの１つは、図３のノード２１２のような陰影ノードで表された単語終了フラグであってよい。各ノードは、他のノードへのダウンポインタ２１０とライトポインタも含むことができる。隣接ノードはライトポインタによって接続されているが、これは図３では相互に隣接するノードによって暗黙的に示されている。例えば、ある状態も構成している２１１のノード「ａ」、「ｉ」、「ｋ」、および「ｕ」である。本明細書で示されているように、ある状態（例えば、２１１または２１５）とは、ライトポインタによって接続されている一連のノードのことである。
【００２７】
完全な辞書では、トライ２００のトップ状態２１５は、通常、その辞書の単語のすべての許可された最初のキャラクタ（ＡＳＣＩＩまたはＵｎｉｃｏｄｅ）である。すなわち、英語の場合は文字「Ａ」から「Ｚ」である。図３では、「．．．」は他の許可されたノードを表している。各ノードからのダウンポインタ２１０は、通常は文字を含んでいるが句読点または「？」のような記号も含むことのできる許可されたそれ以降のノードの次の状態の最初のノードを指し示している。例えば、ノード２２０で最初の許可された（しかもこの例では唯一の）文字は「ｒ」である。
【００２８】
実現可能な遷移または経路に従って、リスト２２５の単語を再生することができる。ダウンポインタ２１０を辿っていくと、ダウンポインタ２１０が指し示しているノードに辿り着くか、そのノードの右にあるノードのどれかに辿り着くことができる。すべてのノードはダウンポインタを有しても、単語終了ノード（例えば、ノード２３０）であってもよいということにも留意されたい。事実、多くのノードはダウンポインタを有しており、単語終了ノード（例えば、ノード２１２）でもある。
【００２９】
図３は、終了圧縮のようなトライによって使用される圧縮技術も示している。例えば、ノード２３０は、多くの異なるノードから指し示されている。したがって、ノード２３０に記憶されている「ｓ」を表すために単一の記憶値または位置を使用することができる。トライおよび様々な圧縮技術は複数の辞書を表し、記憶するための確立された方法であり、詳細な説明は必須ではない。語尾変化のそれぞれがこの従来技術の実施形態に含まれており、これが辞書のサイズを大きくすることに繋がることに注目されたい。一部の非常に語尾変化の多い言語では、その語尾変化のすべてを辞書またはトライに含めることは実用的でない。
【００３０】
トライのすべてのノードを訪問し、したがって１つのトライに含まれる単語のすべてを抽出するために、キャラクタの配列を設定し、その配列の各位置を次々に充填する方法は従来技術では周知である。例えば、配列の最初の位置は第１の見込みのあるキャラクタに設定され、次の位置はそれに続く次に見込みのあるキャラクタに設定され．．．という具合である。エンドノードのすべてのインスタンスは、トライ内の単語または辞書の単語が見つかったということを意味している。
【００３１】
ある単語が辞書にあることを検証するため、またはある単語をスペルチェックするため、そのノードの現在の文字がユーザ入力の文字に一致した場合にのみあるノードのダウンポインタに辿り着く必要があるということを理解されたい。入力テキストにはそのトライと「並列に」辿り着く。第１のポインタがその入力テキストを１文字ずつ辿り、第２のポインタはそのトライをノード毎に辿る。入力が辞書の単語と一致した場合、その入力テキストは正しいと判定される。
【００３２】
規則エンジン２２は、単語解析を実行するためにトライを含む。本発明の一実施形態では、トライは、様々な言語学的規則に従いトライをトラバースするための規則を規定する有限状態変換器として実施される。この規則はトライとは別に記憶される。様々な規則を使用して、規則エンジン２２は、形態素解析を実行し、スペルをチェックし、有限状態変換器の各遷移で候補の単語分割を識別し、それを示す出力を提供する。したがって規則エンジン２２は、単語解析の高速かつ効率的な方法を提供する。
【００３３】
図４に示すように、規則エンジン２２は複数のコンポーネントを含んでいる。第１のコンポーネントは、「自由形態素」（すなわち、「ｈａｐｐｙ」「ｒｕｎ」「ｃａｔ」などのような単語）と「拘束形態素」（すなわち、「ｕｎ」「ｎｅｓｓ」「ｉｎｇ」などのような接辞）の両方を含んでいるトライベースの辞典２５０である。自由および拘束単語形態素は、図３に示すトライ形式で構成することができる。辞典２５０は、形態素に関する情報を含んでいるデータ構造である。例えば、辞典２５０は、構文情報および意味情報の指示を記憶することができる。指示は、形態素が名詞、動詞、または形容詞のどれであるかを含むことができる。形態素の組合せに関する指示を提供することもできる。例えば、辞典２５０は、形態素「ｈａｐｐｙ」は形容詞であり、「ｎｅｓｓ」は形容詞を名詞に変形させる接辞であるという指示を含むことができる。したがって、単語「ｈａｐｐｉｎｅｓｓ」は、別項目を有する必要はないが１つの名詞であると判定することができる。
【００３４】
さらに、別のタイプの言語学的情報を辞典に記憶することができる。この言語学的情報は、実行中の単語解析の種類によって異なる場合がある。構文解析に役立つ単語に関する記憶情報は、この種の情報の一例である。単語が固有名詞か地名かに関する指示も有益である場合がある。
【００３５】
規則エンジン２２の別のコンポーネントは正字法規則モジュール２５２である。正字法規則モジュール２５２は辞典２５０と相互作用し、入力テキストから形態素を識別することを可能にするために様々な規則を規定する。したがって辞典２５０は、語尾変化したバリエーションのすべてではなく形態素を記憶するだけでよい。正字法規則モジュール２５２は、「２レベル」形態学として知られる解析に基づいて動作する。２レベル形態学解析は、表面レベル（すなわち、ユーザからの入力）から辞典レベル（すなわち、単語および様々な特徴の部分）までのデータの変形を含む。例えば、２レベルの形態素解析は、ユーザ入力「ｈａｐｐｉｎｅｓｓ」を形容詞「ｈａｐｐｙ」と様々な特徴を示す接辞「ｎｅｓｓ」とに変形させる。
【００３６】
言語学者または同様の技術を有する人物によって開発された正字法規則は、２レベル形態素システムの変形を規定する。例えば、「ｈａｐｐｉｎｅｓｓ」から「ｈａｐｐｙ＋ｎｅｓｓ」への変形は、以下の例に示すような規則に基づいている。各規則は「正規表現」で表現することができる。正規表現は、コアと演算子と左および右コンテキストとを含む。コアは特定の規則に対するキャラクタのマッピングである。演算子は、コアが左および右のコンテキストとどのように相互作用するかを指示する。左および右コンテキストは、規則を適用するためにコア周辺のキャラクタを規定する。
【００３７】
図５は表現３００の一例を示している。以下に提供する表記法は単なる例示にすぎないことに留意されたい。表現３００は、コア３０２、演算子３０４、左コンテキスト３０６、および右コンテキスト３０８を含む。コア３０２は、それに対して規則またはマッピングが動作する主要な１つ以上のキャラクタである。コア３０２は「ａ」から「ｂ」をマッピングするが、これは「ａ：ｂ」と表現される。フォーマット「ａ：ｂ」は「表面キャラクタ（surface  character）「ａ」は辞典キャラクタ（lexical  character）「ｂ」としてマッピングできる」ことを意味するものと解釈することができるということに注目されたい。表現３００は、どこでマッピングが発生するかを示す「−−−」を含む。演算子３０４は表１に含まれる４つのオプションのうちの１つとすることができる。
【００３８】
【表１】
2004303240.tif 000003
【００３９】
ここで、演算子３０４は「＜−＞」であるが、これは、左コンテキスト３０６（ｃ：ｃ）と右コンテキスト３０８（ｄ：ｄ）が与えられた場合に、コア３０２の変形（ａ：ｂ）が発生しなければならないことを意味している。ユーザが「ｃａｄ」を入力すると仮定すると、その正字法表現３００は「ｃａｄ」は正式には「ｃｂｄ」と表現することもできるということを立証（establish）する。
【００４０】
左コンテキスト３０６と右コンテキスト３０８は、表面および辞典キャラクタ、複数組のキャラクタ（すなわち、すべての子音に対するＣＯＮＳ、すべての母音に対するＶＯＷＬなど）、または特殊なメタキャラクタを含むことができる。表２は、使用される様々なメタキャラクタを含む。
【００４１】
【表２】
2004303240.tif 000004
【００４２】
正字法規則モジュール２５２は、辞典の単語を検索する際に使用可能なオプションを提供する。例えば、入力「ｈａｐｐｉｎｅｓｓ」が与えられた場合、正字法規則モジュール２５２は「ｉ」を「ｙ」にマッピングして、その辞典で形態素「ｈａｐｐｙ」と「ｎｅｓｓ」を見つける。この表現の一般的な表示を次に示す。
i:y  <->  CONS:CONS  ---  *:+
【００４３】
この表現は、そのマッピングの前に辞典にマッピングされた子音があり、形態素の境界を表す任意のキャラクタが後に続く場合にのみ、表面の「ｉ」が「ｙ」としてマッピングされるということを示している。したがって、「ｈａｐｐｉｎｅｓｓ」という入力が辞典でトラバースされた場合、「ｈａｐ」は「ｈａｐ」に、「ｐ」は「ｐ」に（これは左のコンテキストＣＯＮＳ：ＣＯＮＳを満たす）マッピングされ、「ｙ」のマッピングの後に形態素の境界、すなわち形態素「ｈａｐｐｙ」の境界が続く。
【００４４】
表現は、結合表現を示すために結合することもできる。ある結合演算子は論理積／和集合（｜｜）であり、別の結合演算子は論理和／共通集合（＆＆）である。例えば、上記の規則表現にキャラクタ「ｑｕ」を含めるために、上記の規則表現を結合することができる。この結果得られた結合規則を次に示す。
i:y  <->  CONS:CONS  ---  *:+  ||  qu:qu  ---  *:+
【００４５】
さらに、左および右コンテキスト内で異なる演算子を使用することができる。表３に演算子の例を示す。
【００４６】
【表３】
2004303240.tif 000005
【００４７】
規則表現の他の例を以下に示す。規則の表現で、ＣＯＮＳは任意の子音と定義され、ＶＯＷＬは任意の母音と定義され、ＳＩＢは任意の歯擦子音｛ｓ  ｘ  ｚ｝と定義され、ＶＯＷ１は｛ｅ  ｉ  ｏ  ｕ  ｙ｝と定義される。
【００４８】
例えば、「ｆｉｓｈｅｓ」を「ｆｉｓｈ＋ｓ」にマッピングし、または「ｂｏｘｅｓ」を「ｂｏｘ＋ｓ」にマッピングするには、歯擦子音「ｓｈ」、「ｃｈ」が前に来た場合、または「ｙ」が「ｉ」として表面化し、「ｓ」が後に続く場合にのみ、形態素の境界は「ｅ」として表面化しなければならない。次の表現を使用することができる。
e:+  <->  sh:sh  |  SIB:SIB  |  i:y  --- s:s  ||  ch:ch  ---  s:s
【００４９】
「ｂａｇｇｅｄ−＞ｂａｇ＋ｅｄ」または「ｂｉｇｇｅｒ−＞ｂｉｇ＋ｅｒ」をマッピングするには、表面の「ｇ」は、子音、母音、および任意のキャラクタとして辞典に出現する表面の「ｇ」が前にあり、母音または「ｙ」として表面化する任意のキャラクタが後にある場合には辞典で１つの形態素境界として出現する。次の表現を使用することができる。
g:+  ->  (CONS:CONS)  VOWL:VOWL  g:*  ---  VOW1:*|a:*
【００５０】
「ｃｏｎｔｉｎｕｉｎｇ−＞ｃｏｎｔｉｎｕｅ＋ｉｎｇ」「ｔｙｉｎｇ−＞ｔｉｅ＋ｉｎｇ」または「ｒｅｐｔｉｌｉａｎ−＞ｒｅｐｔｉｌｅ＋ａｎ」をマッピングするには、子音または「ｕ」として表面化する任意のキャラクタがその前にあり、ヌルキャラクタと「ａ」または「ｉ」として表面化する形態素の境界とが後に続く場合、または「ｙ」として表面化する「ｉ」が前にあり、ヌルキャラクタとして表面化する形態素の境界が後に続く場合、または任意のキャラクタが前にあり、「ｉ」として表面化する形態素の境界が後に続く場合、「ｅ」がヌルキャラクタとして表面化しなければならない。次の表現を使用することができる。
-:e  <->  CONS:CONS  u:*  ---  -:+  a:a|i:i  ||  y:i  ---  -:+  ||  *:*  ---  i:+
【００５１】
「ｐａｎｉｃｋｅｄ−＞ｐａｎｉｃ＋ｅｄ」および「ｐａｎｉｃｋｉｎｇ−＞ｐａｎｉｃ＋ｉｎｇ」をマッピングするには、母音および「ｃ」がその前にあり「ｅ」または「ｙ」がその後にある場合、または母音および「ｃ」がその前にあり「ｉ」と「ｎ」、「ｏ」または「ｆ」とが後にある場合にのみ、形態素の境界は「ｋ」として表面化しなければならない。次の表現を使用することができる。
k:+  <->  VOWL:VOWL  c:c  ---  e:e|y:y  ||  VOWL:VOWL  c:c  ---  i:i  n:n|o:o|f:f
【００５２】
規則エンジン２２は、許容できる形態素結合を規定するために辞典２５０と相互作用する形態素結合モジュール２５４も含む。このような情報を記憶するためには任意の適切なデータ構造を使用することもできる。例えば、相互作用は形態素のそれぞれと共に記憶されている辞典ビット（lexical  bits）であってよい。辞典ビットは、基語の様々な許容できる語尾変化を定義することができる。例えば、形態素「ｈａｐｐｙ」を記憶してもよく、あるいはそれを「ｎｅｓｓ」、「ｅｒ」、「ｅｓｔ」、および「ｌｙ」のような様々な接辞と結合することを可能にする様々な指示に関連付けてもよい。さらにこの指示は、「ｈａｐｐｙ」と「ｕｎ」のような接頭辞との結合を識別することができる。
【００５３】
規則エンジン２２を使用すると、単語分割、スペルチェック、および形態的解析を同時に実行する高速で効率よい方法が達成される。単語分割を実行するには、単語の境界を指示するためにフラグを形態素と共に辞典２５０に記憶することができる。ユーザ入力および辞典２５０の両方とも単語の終わりに一致する場合、候補の単語の終わりが識別される。次いでユーザ入力ポインタは次のユーザ入力単語に移動することができる。さらに、次の単語を検索するために辞典２５０へのポインタが再初期化される。
【００５４】
語句の構成部分の一部またはすべてが辞書にあるわけではない場合、語句の認識を可能にするために複数の語句を辞典２５０に入れることもできる。このような語句の一例として「Ｓｒｉ  Ｌａｎｋａ」がある。「Ｓｒｉ」も「Ｌａｎｋａ」も辞書にはない。「Ｓｒｉ  Ｌａｎｋａ」の後に語境界を入れることによって、規則エンジン２２は、一部にすぎない「Ｓｒｉ」または「Ｌａｎｋａ」ではなく語句全体を認識することができる。
【００５５】
ユーザ入力が（多くのアジアの言語がそうであるように）単語分割を含まない場合、様々な規則に従って候補の単語分割が識別される。候補の単語の終わりが見つかった後で辞典２５０へのポインタが再初期化される。適宜、候補の単語の終わりのそれぞれと共に確率データを記憶することができる。すべての候補の単語分割が識別された後で、ユーザ入力テキストの単語分割をさらに特定するためにさらなる解析を実行することができる。
【００５６】
形態素解析を実行するために、形態素の境界フラグが辞典２５０の形態素に追加される。辞典２５０の形態素が識別されると、その形態素を形態素解析に追加することができる。形態素がどのように結合されているかを基に解析を行うことができるように、形態素結合モジュール２５４は形態素の実現可能な結合を識別する。
【００５７】
スペリング訂正を実行するために、コスト計算用の方法およびシステムを使用することができる。ユーザ入力と辞典２５０との情報の間の違いに対してコストが計算される。ユーザ入力と辞典２５０の項目が一致した場合、コストは０である。そうでない場合、使用可能な遷移に対するスペリングの提案を生成するためにコストが計算される。遷移のコストが閾値で定義されているように高くなりすぎた場合、それ以上遷移は探索されない。本発明の実施形態によるスペルチェックのためのシステムおよび方法の一例が、２０００年１０月１０日発行の「Method  and  System  for  Cost  Computation  of  Spelling  Suggestions  and  Automatic  Replacement」という名称の特許文献１に説明されている。
【００５８】
図６は、規則エンジン２２を使用した単語解析の方法を示している。規則エンジン２２は、辞典２５０、正字法規則モジュール２５２、および形態素結合モジュール２５４に基づく様々な遷移を含む状態マシンである。方法３５０はステップ３５２から開始する。ステップ３５４で、入力テキストの遷移が規則エンジン２２の遷移と比較される。例えば、この遷移は入力テキストでは「ｈ」として、辞典２５０の形態素「ｈａｐｐｙ」の第１のキャラクタマッピングとしては「ｈ：ｈ」として比較することができる。遷移が適用された後、経路に関して規則エンジン２２でスペリング規則、形態素規則、単語分割規則のどれに従ってその遷移が見つかったかに関してステップ３５６で判定がなされる。遷移が一致した場合、この方法はステップ３５８に進み、そこで規則エンジン２２およびユーザ入力のポインタが増分される。遷移が一致しない場合、ステップ３６０で実現可能な遷移が提案され、その実現可能な遷移にペナルティ（コスト）が適用される。ステップ３６２で、提案された経路（遷移）を辿るための合計コストが高すぎるか否かが判定される。提案された経路に追加のペナルティが既に適用済みである場合、複数のコストを追加する必要がある。コストが高すぎる場合、ステップ３６４で特定の経路が破棄される。したがって、この経路はこれ以上探索されない。コストが許容できる範囲内である場合、この方法はステップ３５８に戻り、入力および規則エンジン２２のポインタが増分される。
【００５９】
ポインタが増分された後、その経路の終わりに既に達しているか否かが判定される。この判定はステップ３６６で行われる。追加の遷移がユーザ入力に含まれている場合、この方法はステップ３５４に戻る。経路の終わりに到達している場合、ステップ３６８で追加の使用可能な経路があるか否かの判定が行われる。経路のすべてが探索された後、この方法はステップ３７０で終了する。追加の経路が探索される必要がある場合、ステップ３７２で規則エンジン２２は次の経路を探索し、ステップ３５４で遷移を適用する。ステップ３７２で次の経路を見つけるステップは、規則エンジン２２を介して後方に移動し、代替遷移を適用するか、または次の入力単語を解析するために規則エンジン２２を再初期化することを伴う場合がある。
【００６０】
図７は、単語分割、スペルチェック、および形態素解析を図６の方法３５０に従って同時に提供するために規則エンジン２２をトラバースする一例を示している。規則エンジン２２のポインタは初期状態から開始する。
【００６１】
入力が「ｄｉｓｈｅｓ」である場合、辞典２５０は形態素「ｄｉｓｈ」の最初の文字「ｄ」までトラバースされる。次に、遷移が辞典２５０の「ｉ」に続く。「ｓ：ｓ」遷移は、規則に支配される遷移、すなわち「ｓｈ」に続く複数の名詞は「ｅｓ」としてマッピングすることができる遷移を開始する。遷移「ｓ：ｓ」および「ｈ：ｈ」は状態「Ｓ２」に到達するために規則エンジン２２に従う。状態「Ｓ２」で、文字「ｈ」について形態素の境界「＋」と語境界「＃」に到達するので、このキャラクタは形態素および語境界候補として機能する。正字法規則モジュール２５２は、「＋：ｅ」と示される、形態素の境界から「ｅ」への辞典２５０の遷移を可能にする。また、形態素結合モジュール２５４は、遷移「ｓ：ｓ」と示されていれば、形態素「ｄｉｓｈ」が「ｓ」と結合されることを可能にする。ユーザ入力は「Ｓ３」および「Ｓ４」の残りの遷移と一致する。「Ｓ４」は、ユーザの入力の一致する単語の境界を示す語境界フラグを含んでいる。したがって、状態「Ｓ４」に到達した後、スペルチェックがまったくエラーを見つけなかった場合、「ｄｉｓｈｅｓ」の後で単語分割が発生したか否かを単語分割が判定し、形態素解析は形態素「ｄｉｓｈ」と「ｓ」とを識別している。次いでこれらの解析を示す出力を提供することができる。
【００６２】
ユーザ入力と辞典２５０が一致しない場合、辞典２５０を介してトラバースするために適切なペナルティが適用される。例えば、ユーザが「ｄｅｓｈｅｓ」を入力した場合、「ｄ」から「ｉ」への提案された遷移に対してペナルティ「Ｐ１」が適用される。したがって、正確な単語「ｄｉｓｈｅｓ」の提案を行うことができる。ユーザが誤って「ｄｉｓｈｉｓ」と入力した場合、状態「Ｓ２」から「Ｓ３」への遷移、すなわち「＋：ｅ」に対してペナルティ「Ｐ２」が適用されるであろう。同様に、「ｄｉｓｈｅｓ」の提案を行い出力として提供することができる。上述のように、ペナルティが高すぎる場合、遷移はトラバースされない。この結果、辞典２５０を通した遷移は正字法モジュール２５２および形態素結合モジュール２５４によって確立された規則によって支配される。規則エンジン２２を介したトラバースは効率的な単語解析を提供する。
【００６３】
以上、本発明を特定の実施形態を参照して説明したが、当業者ならば、本発明の趣旨および範囲を逸脱せずに形式および細部に対する変更を行うことができることを理解するだろう。
【図面の簡単な説明】
【００６４】
【図１】言語またはテキスト処理システムのブロック図である。
【図２】本発明を実施するための例示的環境のブロック図である。
【図３】トライの図形表現である。
【図４】本発明による規則エンジンのブロック図である。
【図５】変形を規定する規則の一表現を示す図である。
【図６】本発明の一実施形態による単語解析を提供する方法を示す図である。
【図７】規則エンジンのトラバースの図形表現を示す図である。
【符号の説明】
【００６５】
１２  入力
１４  出力
２０  テキストアナライザ
２２  規則エンジン
２５０  辞典
２５２  正字法規則モジュール
２５４  形態素結合モジュール
【図１】
2004303240.tif 000006
【図２】
2004303240.tif 000007
【図３】
2004303240.tif 000008
【図４】
2004303240.tif 000009
【図５】
2004303240.tif 000010
【図６】
2004303240.tif 000011
【図７】
2004303240.tif 000012
【外国語明細書】
2004303240000001.pdf