JP2009009583A - 構文パースを用いてセグメント化されていないテキストをセグメント化する方法 - Google Patents

Abstract

【課題】構文パースを使用して正字法バリエーションを有するテキストをセグメント化する方法の提供。
【解決手段】正字法および屈折言語のバリエーション３０８を構文パーサ３１６に送ることによりテキストをセグメント化する。可能なセグメントは文字列内で最初に識別される。識別されたセグメントのうち少なくとも２つは互いに重なる。セグメントのうち少なくとも１つについて、他の文字列が識別される。この他の文字列は、セグメントにより識別された単語の異なる語彙形式を識別する、屈折形態論３０６により形成される。他の文字列はセグメントで識別された単語の正字法バリエーション３０８を表す場合もある。その後、識別されたセグメントおよび他のセグメントが構文パーサ３１６に渡され、１つまたは複数の構文解析結果を出力する。解析結果にあるセグメントは、入力文字列のセグメント化を表す。
【選択図】図３

Description

本発明は、一般にテキストを識別するコンピュータベースの方法に関する。より詳細には、本発明は、構文パース（ｓｙｎｔａｃｔｉｃ ｐａｒｓｅ）を使用して正字法バリエーション（ｏｒｔｈｏｇｒａｐｈｉｃ ｖａｒｉａｔｉｏｎｓ）を有するテキストをセグメント化する方法に関する。

（発明の背景）
単語セグメント化（ｗｏｒｄ ｓｅｇｍｅｎｔａｔｉｏｎ）とは、テキストなど、言語表現を構成する個々の単語を識別するプロセスのことである。単語セグメント化は、スペルおよび文法のチェック、テキストの音声合成、自然言語理解の実行、および特定の単語や語句を文書集合の中で検索する作業に役立つ。

英語テキストでは、一般にスペースおよび句読点によりテキスト内の個々の単語が区切られるため、単語セグメント化はかなり簡単である。しかし、日本語や中国語などのセグメント化されないテキストでは、単語の境界は暗黙的であり明示的ではない。つまり、セグメント化されないテキストは通常、スペースや句読点を単語間に入れない。したがって、これらの言語では、英語のセグメント化と同じ方法でセグメント化を実行することはできない。

ほとんどの従来技術のシステムでは、単純な単語区切りを使用して、テキストをセグメント化する。これらの単語区切りでは、複数の文字を可能なセグメントグループにまとめ、用語集でセグメントを検索する。用語集内にセグメントが見つかると、テキストの可能なセグメント化の一部として保持される。

用語集の手法を使用して、互いに重なる多くのセグメントを識別することができ、したがって、これらのセグメントは同じセグメント化結果内に存在できない。これらの競合するセグメントのうちどれがテキストの実際のセグメントであるかを識別するために、いくつかの従来技術システムは単純な構文規則を使用する。ただし、これらの単純な規則は、元のテキスト文字列に現れる文字に対してのみ適用される。これらは、適切に識別されないと異なる構文になる元のテキスト内の正字法バリエーションには対応しない。日本語は、特に、同じ単語に対し多数の正字法バリエーションがあり、構文パーサ（ｓｙｎｔａｃｔｉｃ ｐａｒｓｅｒ）を使用して日本語テキストをセグメント化するのが難しい。これらのバリエーションの多くは、日本語では漢字、ひらがな、カタカナ、および英字の４種類のスクリプトを使用しており、異なるスクリプトまたはスクリプトの組み合わせを使用して同じ単語を綴ることができることが原因で生じる。

したがって、セグメント化システムは構文解析におけるセグメント化を活かしながら正字法バリエーションをきちんと説明するセグメント化システムを必要とする。本発明は、この問題および他の問題を解決するほかに、従来技術に勝る利点を持つ。

（発明の概要）
本発明の実施形態は、正字法および屈折言語のバリエーションを構文パーサに送ることによりテキストをセグメント化する方法および装置を実現している。本発明では、可能なセグメントは文字列内で最初に識別される。識別されたセグメントのうち少なくとも２つは互いに重なる。セグメントのうち少なくとも１つについて、他の文字列が識別される。場合によっては、この他の文字列は、セグメントにより識別された単語の異なる語彙形式を識別する、屈折形態論により形成される。他の文字列はセグメントで識別された単語の正字法バリエーションを表す場合もある。

その後、識別されたセグメントおよび他のセグメントが構文パーサに渡され、完全な構文パースを出力する。結果として得られたパースにあるセグメントは、入力文字列のセグメント化を表す。

（例示の実施形態の詳細な説明）
図１は、本発明を実施できる適当なコンピュータ・システム環境１００の例を示している。コンピューティングシステム環境１００は、適当なコンピューティング環境の一例にすぎず、本発明の使用または機能の範囲に関する限定を示唆するものではない。このコンピューティング環境１００は、例示のオペレーティング環境１００に示されているコンポーネントのいずれかまたは組み合わせに関して従属している、あるいは必要であるとは解釈すべきではない。

本発明は、他の多数の汎用または専用のコンピューティングシステム環境または構成でも動作する。本発明で使用するのに適していると思われるよく知られているコンピューティングシステム、環境、および／または構成の例として、パソコン、サーバ・コンピュータ、携帯またはラップトップデバイス、マルチプロセッサシステム、マイクロプロセッサベースのシステム、セットトップボックス、プログラム可能家電製品、ネットワークＰＣ、ミニコン、メインフレームコンピュータ、上記システムまたはデバイスを含む分散コンピューティング環境などがあるが、これに限定されない。

本発明は、コンピュータによって実行されるプログラムモジュールなどのコンピュータ実行可能命令の一般的コンテキストにおいて説明できる。一般に、プログラムモジュールには、特定のタスクを実行する、あるいは特定の抽象データ型を実装するルーチン、プログラム、オブジェクト、コンポーネント、データ構造などが含まれる。本発明は、さらに、通信ネットワークを介してリンクされているリモート処理デバイスによってタスクが実行される分散コンピューティング環境で実用することもできる。分散コンピューティング環境では、プログラムモジュールをメモリ記憶デバイスを含むローカルとリモートの両方のコンピュータ記
憶媒体に配置できる。

図１を参照すると、本発明を実施するシステム例に、コンピュータ１１０の形の汎用コンピューティングデバイスが含まれる。コンピュータ１１０のコンポーネントは、処理ユニット１２０、システムメモリ１３０、およびシステムメモリを備えるさまざまなシステムコンポーネントを処理ユニット１２０に結合するシステムバス１２１を備えるがこれに限られるわけではない。システムバス１２１には、さまざまなバスアーキテクチャを使用するメモリバスまたはメモリコントローラ、周辺機器バス、およびローカルバスを含む数種類のバス構造がある。例では、これに制限されるわけではないが、前記アーキテクチャに、Ｉｎｄｕｓｔｒｙ Ｓｔａｎｄａｒｄ Ａｒｃｈｉｔｅｃｔｕｒｅ（ＩＳＡ）バス、Ｍｉｃｒｏ Ｃｈａｎｎｅｌ Ａｒｃｈｉｔｅｃｔｕｒｅ（ＭＣＡ）バス、Ｅｎｈａｎｃｅｄ ＩＳＡ（ＥＩＳＡ）バス、Ｖｉｄｅｏ Ｅｌｅｃｔｒｏｎｉｃｓ Ｓｔａｎｄａｒｄｓ Ａｓｓｏｃｉａｔｉｏｎ（ＶＥＳＡ）ローカル・バス、およびＭｅｚｚａｎｉｎｅバスとも呼ばれるＰｅｒｉｐｈｅｒａｌ Ｃｏｍｐｏｎｅｎｔ Ｉｎｔｅｒｃｏｎｎｅｃｔ（ＰＣＩ）バスがある。

コンピュータ１１０は通常、多数のコンピュータ可読媒体を備える。コンピュータ可読媒体は、コンピュータ１１０によってアクセス可能な利用可能な媒体でよく、揮発性および不揮発性媒体、取り外し可能および取り外し不可能媒体がある。たとえば、コンピュータ可読媒体として、コンピュータストレージ媒体や通信媒体などがあるが、これらに限られるわけではない。コンピュータ記憶媒体には、揮発性と不揮発性の両方の取り外し可能および取り外し不可能媒体が備えられ、コンピュータ可読命令、データ構造、プログラムモジュール、またはその他のデータなどの情報の記憶用の方法または技術で実装されている。コンピュータ記憶媒体には、ＲＡＭ、ＲＯＭ、ＥＥＰＲＯＭ、フラッシュメモリまたはその他のメモリ技術、ＣＤ−ＲＯＭ、デジタル多用途ディスク（ＤＶＤ）、またはその他の光ディスク記憶装置、磁気カセット、磁気テープ、磁気ディスク記憶装置またはその他の磁気記憶デバイス、または目的の情報の格納に使用でき、コンピュータ１１０によってアクセスできる他の媒体がある。通信媒体は通常、コンピュータ可読命令、データ構造、プログラムモジュールまたはその他のデータをキャリア波やその他の搬送メカニズムなどのモジュール式データ信号で具現化し、情報配送媒体を含む。「変調データ信号」とは、情報を信号内にエンコードするなどの方法で１つまたは複数の特性を設定または変更する信号のことである。たとえば、これには限らないが、通信媒体は有線ネットワークまたは直接有線接続などの有線媒体および音響、ＲＦ、赤外線、およびその他の無線媒体などの無線媒体を含む。上記の組み合わせも、コンピュータ可読媒体の範囲に含まれるであろう。

システムメモリ１３０は、読み取り専用メモリ（ＲＯＭ）１３１およびランダムアクセスメモリ（ＲＡＭ）１３２などの揮発性または不揮発性メモリの形態のコンピュータ記憶媒体を含む。起動時などにコンピュータ１１０内の要素間の情報伝送を助ける基本ルーチンを含む基本入出力システム１３３（ＢＩＯＳ）は通常、ＲＯＭ １３１に格納される。ＲＡＭ １３２は、通常、処理ユニット１２０に即座にアクセス可能な、および／または現在操作されているデータおよび／またはプログラムモジュールを含む。例では、これに限らないが、図１はオペレーティングシステム１３４、アプリケーションプログラム１３５、その他のプログラムモジュール１３６、およびプログラムデータ１３７を示している。

コンピュータ１１０はさらに、その他の取り外し可能／取り外し不可能、揮発性／不揮発性コンピュータ記憶媒体も備えることができる。例としてのみであるが、図１は、取り外し不可能不揮発性磁気媒体への読み書きを行うハードディスクドライブ１４１、取り外し可能不揮発性磁気ディスク１５２への読み書きを行う磁気ディスクドライブ１５１、およびＣＤ−ＲＯＭまたはその他の光媒体などの取り外し可能不揮発性光ディスク１５６への読み書きを行う光ディスクドライブ１５５を示す。例のオペレーティング環境で使用できるその他の取り外し可能／取り外し不可能揮発性／不揮発性コンピュータ記憶媒体には、磁気テープカセット、フラッシュメモリカード、デジタル多用途ディスク、デジタルビデオテープ、半導体ＲＡＭ、半導体ＲＯＭなどがある。ハードディスクドライブ１４１は通常、インタフェース１４０などの取り外し不可能メモリインタフェースを通じてシステムバス１２１に接続され、磁気ディスクドライブ１５１、および光ディスクドライブ１５５は通常、インタフェース１５０などの取り外し可能メモリインタフェースによりシステムバス１２１に接続される。

上で述べた、図１に示されているドライブおよび関連コンピュータ記憶媒体は、コンピュータ１１０用のコンピュータ可読命令、データ構造、プログラムモジュール、およびその他のデータを格納する。図１では、たとえば、ハードディスクドライブ１４１はオペレーティングシステム１４４、アプリケーションプログラム１４５、その他のプログラムモジュール１４６、およびプログラムデータ１４７を格納するものとして示されている。これらのコンポーネントは、オペレーティングシステム１３４、アプリケーションプログラム１３５、その他のプログラムモジュール１３６、およびプログラムデータ１３７と同じであっても、異なっていてもよい。オペレーティングシステム１４４、アプリケーションプログラム１４５、その他のプログラムモジュール１４６、およびプログラムデータ１４７には、ここでは異なる番号が与えられており、最低でも、異なるコピーであることを示している。

ユーザは、キーボード１６２、マイク１６３、およびマウス、トラックボール、タッチパッドといったポインティングデバイス１６１などの入力デバイスを使用してコンピュータ１１０にコマンドおよび情報を入力できる。他の入力デバイス（図示せず）としては、ジョイスティック、ゲームパッド、衛星放送受信アンテナ、スキャナなどがある。これらの入力デバイスやその他の入力デバイスは、システムバスに結合されているユーザ入力インタフェース１６０を介して処理ユニット１２０に接続されることが多いが、パラレルポート、ゲームポート、またはユニバーサルシリアルバス（ＵＳＢ）などの他のインタフェースおよびバス構造により接続することもできる。モニタ１９１やその他のタイプの表示デバイスも、ビデオインタフェース１９０などのインタフェースを介してシステムバス１２１に接続される。モニタの他に、コンピュータには、出力周辺機器インタフェース１９０を介して接続可能な、スピーカ１９７やプリンタ１９６などの他の周辺出力デバイスもある。

コンピュータ１１０は、リモートコンピュータ１８０などの１つまたは複数のコンピュータへの論理接続を使用してネットワーク環境で動作することもできる。リモート・コンピュータ１８０は、パーソナルコンピュータ、ハンドヘルドデバイス、サーバ、ルータ、ネットワークＰＣ、ピアデバイスまたはその他の共通ネットワークノードでよく、通常は、コンピュータ１１０に関係する上述の要素の多くまたはすべてを含む。図１に示されている論理接続は、ローカルエリアネットワーク（ＬＡＮ）１７１とワイドエリアネットワーク（ＷＡＮ）１７３を含むが、他のネットワークを含んでいてもよい。このようなネットワーキング環境は、事務所、企業規模のコンピュータネットワーク、イントラネットおよびインターネットではよくある。

ＬＡＮネットワーキング環境で使用する場合は、コンピュータ１１０はネットワークインタフェースまたはネットワークアダプタ１７０を介してＬＡＮ １７１に接続される。ＷＡＮネットワーキング環境で使用する場合は、コンピュータ１１０は通常、モデム１７２またはインターネットなどのＷＡＮ １７３上で通信を確立するためのその他の手段を備える。モデム１７２は、内蔵でも外付けでもよいが、ユーザ入力インタフェース１６０またはその他の適切なメカニズムを介してシステム・バス１２１に接続できる。ネットワーク環境では、コンピュータ１１０またはその一部に関して述べたプログラムモジュールは、リモートメモリ記憶媒体に格納できる。例では、これに限らないが、図１はリモートコンピュータ１８０に常駐するようなリモートアプリケーションプログラム１８５を示している。図に示されているネットワーク接続は例であり、コンピュータ間に通信リンクを確立するのにその他手段を使用できることは理解されるであろう。

図２は、モバイルデバイス２００のブロック図であり、コンピューティング環境の実施例である。モバイルデバイス（ｍｏｂｉｌｅ ｄｅｖｉｃｅ）２００は、マイクロプロセッサ２０２、メモリ２０４、入出力（Ｉ／Ｏ）コンポーネント２０６、およびリモートコンピュータまたはその他のモバイルデバイスと通信するための通信インタフェース２０８を備える。一実施形態では、前述のコンポーネントは適当なバス２１０で互いに通信できるように結合されている。

メモリ２０４は、バッテリバックアップモジュール（図に示されていない）付きのランダムアクセスメモリ（ＲＡＭ）などの不揮発性電子メモリとして実装され、メモリ２０４に格納されている情報は、モバイルデバイス２００の一般電源がシャットダウンされても失われることがない。メモリ２０４の一部は、プログラム実行用にアドレス指定可能なメモリとして割り当てるのが好ましいが、メモリ２０４の他の部分はディスクドライブ上のストレージをシミュレートするなどストレージに使用するのが好ましい。

メモリ２０４は、オペレーティングシステム２１２、アプリケーションプログラム２１４、およびオブジェクトストア（ｏｂｊｅｃｔ ｓｔｏｒｅ）２１６を格納する。動作時に、オペレーティングシステム２１２は、メモリ２０４からプロセッサ２０２によって実行するのが好ましい。好ましい一実施形態では、オペレーティングシステム２１２は、Ｍｉｃｒｏｓｏｆｔ Ｃｏｒｐｏｒａｔｉｏｎから市販されているＷｉｎｄｏｗｓ（登録商標）ＣＥブランドのオペレーティングシステムである。オペレーティングシステム２１２は、モバイルデバイス用に設計されていることが好ましく、一組の公開されているアプリケーションプログラミングインタフェースおよびメソッドを通じてアプリケーション２１４で利用できるデータベース機能を実装している。オブジェクトストア２１６内のオブジェクトは、アプリケーション２１４およびオペレーティングシステム２１２により維持され、少なくとも一部は、公開されているアプリケーションプログラミングインタフェースおよびメソッドへの呼び出しに応答する。

通信インタフェース２０８は、モバイルデバイス２００で情報を送受信するための多数のデバイスおよび技術を表している。これらのデバイスの例としては、有線および無線モデム、衛星放送受信機、および放送チューナなどがある。モバイルデバイス２００は、データを交換するためコンピュータに直接接続することもできる。このような場合、通信インタフェース２０８は、赤外線トランシーバやシリアルまたはパラレル通信接続とすることができるが、ただしすべてストリーミング情報を送信することができるものとする。

入出力コンポーネント２０６には、タッチセンシティブスクリーン、ボタン、ローラ、およびマイク、さらにオーディオジェネレータ、振動デバイス、およびディスプレイなどさまざまな出力デバイスがある。上記のデバイスは、例であって、モバイルデバイス２００にすべて存在している必要はない。さらに、他の入出力デバイスが、本発明の範囲内で、モバイルデバイス２００に接続されていたり、それとともに存在する場合がある。

本発明の実施形態は、正字法および屈折言語のバリエーションを構文パーサに送ることによりテキストをセグメント化する方法および装置を実現している。図３は、本発明の一実施形態のさまざまなコンポーネントのブロック図である。図４は、図３のコンポーネントを使用する本発明の一実施形態による方法の流れ図である。

図４のステップ４００では、図３の単語ブレーカにより、小さな語彙レコードセット（ｌｅｘｉｃａｌ ｒｅｃｏｒｄ ｓｅｔ）３０４に現れる入力テキスト３００内の連続する文字の組み合わせを識別する。語彙レコードセット３０４は、単語ごとの文法情報の量が限られているという意味で小さい。語彙レコードセット３０４が含んでいる単語の数が必ずしも少ないわけではなく、実際、いくつかの実施形態では、小さい語彙レコードセット３０４には多数の単語が含まれる。

本発明の一実施形態では、単語ブレーカ３０２がトライ（ｔｒｉｅ）と呼ばれるデータ構造を使用して小さい語彙レコードセット３０４内の単語を検索する。トライでは、単語は順番に表示されないが、その代わりに、状態の連鎖により表される。各状態は個々の文字を表し、１つまたは複数の子状態を含み、それぞれの子状態は小さな語彙レコードセット３０４の少なくとも１つの単語の現在状態の文字の後に出現する文字を含む。各状態はさらに、現在の文字の前にある状態の連鎖により形成される単語内の最後の文字として現在の文字が出現するかどうかも示す。

トライデータ構造を使用し、ＡＢＣＤなどの文字列内の可能な単語を並行して決定できる。たとえば、システムは文字Ａと関連する状態から始まる。その状態が文字Ａが小さな語彙レコードセット３０４内に単語として単独で現れることを示す場合、「Ａ」はその文字列の可能なセグメントとして識別される。その後、システムは、文字Ａの状態から伸びる文字Ｂの子状態があるかどうかをチェックする。Ｂ子状態がある場合、Ｂ状態をチェックし、文字Ｂが単語の最終文字かどうかを確認する。最終文字であれば、文字列ＡＢは可能なセグメントとして識別される。その後、システムは、文字Ｂの状態から伸びる文字Ｃの子状態があるかどうかを調べる。現在の状態から伸びる文字Ｃの子状態がない場合、システムは現在の連鎖の追跡を停止し、文字Ｂから始まる新しい連鎖の追跡を開始する。入力文字列内の文字ごとに新しい連鎖を開始するプロセスを繰り返し、それぞれの文字を連鎖の可能な始まりとしてテストする。

小さな語彙レコードセット３０４に格納されている単語がステップ４００で識別されると、図４の方法がステップ４０２で続行され、単語ブレーカ３０２が屈折形態論（ｉｎｆｌｅｃｔｉｏｎａｌ ｍｏｒｐｈｏｌｏｇｙ）規則３０６を使用して、小さな語彙レコードセット３０４には格納できないが、その見出し語（ｌｅｍｍａｓ）は小さな語彙レコードセット３０４に格納できる単語を識別する。この見出し語は、辞書または語彙データベースに格納する際に使用する単語の標準形である。たとえば、部分文字列ＡＢＣがテキスト文字列内に見つかり、部分文字列ＢＣがいくつかの動詞の過去時制を示し、部分文字列ＢＣの前の文字列を取ってそれを新しい文字Ｑと組み合わせてそれらの動詞の見出し語を形成できると屈折形態論規則で規定している場合、屈折形態論では部分文字列ＡＢＣから見出し語ＡＱを識別できる。本発明のいくつかの実施形態では、ステップ４０８と関連して後述する派生形態論（ｄｅｒｉｖａｔｉｏｎａｌ ｍｏｒｐｈｏｌｏｇｙ）分析規則もステップ４０２で適用される。

見出し語を単語ラティス（ｗｏｒｄ ｌａｔｔｉｃｅ）に追加する前に、システムは小さな語彙レコードセット３０４を検索し、見出し語が言語内の１つの単語であることを確認する。見出し語が言語内の１つの単語であれば、見出し語が単語ラティスに追加され、見出し語の語彙情報がレコードセット３０４に格納され、単語に関する情報が屈折形態論により与えられる。たとえば、単語ラティス内に置かれているレコードは、入力テキスト文字列内に見つかった見出し語の時制を示す場合がある。見出し語に対し単語ラティス内に置かれているレコードはさらに、見出し語を見つけるために使用された入力文字列内の文字列の開始位置と終了位置も示す。たとえば、４文字を使用して、２文字のみ含む見出し語の過去時制を表した場合、見出し語のレコードは、見出し語がその見出し語の２文字だけで占有されるのではなく４文字で占有される領域を埋めることを示す。これにより、見出し語が見出し語を見つけるのに使用した文字列と異なる異なる数の文字の列であるとしても、文字シーケンス内の他のセグメントと見出し語を組み合わせることができる。

屈折形態論を実行している間、図４の方法はさらに、正字法正規化（ｏｒｔｈｏｇｒａｐｈｉｃ ｎｏｒｍａｌｉｚａｔｉｏｎ）を実行して単語の異なるスペルを正規化する。この正規化を実行することにより、小さな語彙レコードセット３０４にすべてのスペルを格納する必要があるわけではない。その代わりに、小さな語彙レコードセットに好ましいスペルを１つだけ格納する。

文字列の正字法を正規化するために、単語ブレーカ３０２はデータ構造３０８にアクセスし、それぞれの好ましい正字法形式の選択した単語をその単語の正字法バリエーションにリンクする。データ構造３０８を使用して、単語ブレーカ３０２は、入力テキストの可能なセグメント内に見つかる文字列を検索する。データ構造３０８内に文字列を見つけると、単語ブレーカ３０２は、データ構造３０８を使用してその単語の好ましい形式を識別する。その後、この好ましい形態を、単語の関連する語彙情報および正規化されたセグメントの開始位置と終了位置とともに単語ラティス内に挿入される。

正規化された形式の単語は基づく元のセグメントよりも文字が多い場合も少ない場合もあり、元のセグメントと文字が異なる場合があることに注意されたい。本発明では、元のセグメントの開始位置と終了位置を正規化された形式のレコードに格納することにより、正規化された形式を入力文字列内の他のセグメントと組み合わせて、入力文字列の完全なセグメント化を識別できる。

日本語の実施形態では、正字法正規化の一部は、日本語で一般に使用する４種類のスクリプト、漢字、ひらがな、カタカナ、および英字の好ましい組み合わせを選択する必要がある。漢字とは、中国語から借用した、かなり複雑に見える日本語文字の集合である。日本語にはこうした文字が数千個あり、それぞれの文字は複数の「読み」（つまり発音）がある場合がある。ひらがなは、発音に基づいて単語を書き出すために使用される日本語の音節文字である。カタカナは、主に外来語の表記や、センテンス内の単語の強調に使用されるもう１つの音節文字である。ひらがなおよびカタカナは、仮名と総称されることもある。

本発明の一実施形態では、正字法構造３０８は、正字法ラティスの集合の形を取り、各ラティスは単語を表す。各単語について、ラティスは、その単語の正字法形式のすべておよびその単語の好ましい正字法形式を示す。

このようなラティス５００の例が図５に示されている。ラティス５００は、括弧で示される３つの単語要素フィールド５０２、５０４、および５０６に分割され、単語の単一の要素を表すデータを保持する。それぞれの括弧内の単一要素を、単一の文字または複数の文字で表すことができる。３語からなる要素が図５に示されているが、当業者であれば、ラティス内に単語要素がいくつでもあり得ることは認識できるであろう。単語要素に代替がなかった場合、ラティス内にそれ自身として括弧なしで現れることにも注意されたい。

各単語要素データフィールドは、好ましいフィールド５０８および代替えフィールド５１０の２つのサブフィールドを含む。好ましいフィールド５０８は、対応する単語要素の主要な形式または好ましい形式を含む。ほとんどの日本語の実施形態では、好ましいフィールド５０８は漢字を含む。代替フィールド５１０は、対応する単語要素の代替形式を表すデータを含む。ほとんどの日本語の実施形態では、代替フィールド５１０は１つまたは複数の仮名文字を含む。好ましいフィールド５０８または代替フィールド５１０のいずれかに文字をいくつでも置くことができる。

たとえば、正字法ラティス［Ｗ：ａｂ］［Ｘ：ｃｄ］で、「ＷＸ」、「Ｗｃｄ」、「ａｂＸ」、または「ａｂｃｄ」として書くことができる単語を指定し、大文字は各要素の好ましい表現を示し、小文字は各要素の代替表現を示す。

漢字が通常仮名よりも好ましい日本語の実施形態では、本発明のラティスには、「送りがな」バリエーションも用意されている。送りがなは、オプションでいくつかのスペルバリエーションで漢字に付加できるが、漢字の仮名代替えに付加しなければならない１つまたは複数の仮名文字のことである。したがって、「Ｘ」が漢字、「ａ」がＸの代替え仮名文字、「ｂ」がオプション文字の場合、バリエーション「Ｘｂ」および「ａｂ」は有効であるが、「ｂ」のない「ａ」は有効でない。送りがなは、ラティス内でカンマで表される。したがって、ラティス［Ｗ：ａ，ｂ］［Ｘ：ｃ］では、正字法「ＷＸ」、「ＷｂＸ」、「Ｗｃ」、「Ｗｂｃ」、「ａｂＸ」、および「ａｂｃ」は許されるが、「ａＸ」または「ａｃ」は許されない。単一の単語要素の複数の送りがなは、カンマで送りがなのそれぞれを区切ることにより表される。たとえば、ラティス［Ｗ：ａ］［Ｘ：ｂ，ｃ，ｄ］では、許容可能なバリエーション「ＷＸ」、「ＷＸｄ」、「ＷＸｃ」、「Ｗｂｃｄ」、「ａＸ」、「ａＸｄ」、「ａＸｃ」、および「ａｂｃｄ」が使用できる。

一実施形態では、コンパイルされたラティス構造を直接使用して、可能な単語セグメントを好ましい正字法形式に変換する。この実施形態では、受け取った文字入力を各正字法ラティスの最初の単語要素と比較する。受け取った文字入力が特定のラティスの第１の単語要素の好ましい形式または代替形式と一致する場合、入力文字列内の後続文字を特定のラティス内の単語要素とさらに比較し、特定のラティスに対応する語彙入力の正字法形式が入力文字列内に存在するかどうかを確認する。入力文字列がラティス内の単語要素の組み合わせと一致する場合、正字法ラティスの各単語要素の好ましい形式を含む入力文字列の正規化された表現が生成される。その後、正規化された形式が、単語ブレーカ３０２によって生成されている単語ラティス内に挿入される。

いくつかの日本語実施形態では、追加構造を上のラティスと併用し、ラティスへのアクセスと関連する計算時間を短縮する。このデータ構造は、単語ごとに１エントリを含み、各エントリはすべて仮名のフィールドと好ましい形式のフィールドを持つ。すべて仮名のフィールドには、仮名文字のみで表される単語が格納される。好ましい形式のフィールドには、単語ラティスに入れるべき単語の好ましい正字法形式が格納される。この追加構造では、仮名文字のみを含む入力文字列を高速ルックアップできる。比較的複雑な正字法ラティス構造にアクセスする代わりに、単語ブレーカ３０２がその代わりに、仮名構造内で単純なルックアップを実行して、すべて仮名文字列の好ましい形式を見つける。いくつかの実施形態では、仮名構造は、上述のトライ構造に似たトライ構造として編成されている。

いくつかの実施形態では、ラティスおよびすべて仮名データ構造は、ルックバック（ｌｏｏｋ−ｂａｃｋ）データ構造で補強され、ラティスにアクセスする操作に関連する計算時間がさらに短縮される。ルックバックデータ構造では、好ましい文字にのみ基づいてラティスにインデックスを付けることができるため、一致するラティスの初期検索では、好ましい文字のみを比較し、代替文字は比較しない。この実施形態では、入力文字列が好ましい文字から始まる場合、好ましい文字で始まる単語が、単語の好ましい文字を使用して正字法ラティス内で直接検索される。ただし、入力文字列が好ましくない（代替）文字で始まる場合、入力文字列内に出現する第１の好ましい文字を使用してルックバックデータ構造が検索される。たとえば、入力文字列が「ａｂＸｃ」の場合、「ａ」、「ｂ」、「ｃ」が代替文字で、「Ｘ」が好ましい文字であれば、ルックバックデータ構造が「Ｘ」に対応するエントリについて検索される。

各ルックバックエントリは、特定の正字法形式の単語に対応する。これは、正字法形式内の第１の好ましい文字に基づいてインデックスが付けられる。各エントリはさらに、正字法形式内のこの第１の好ましい文字の前に代替文字の数およびこの形式内の第１の代替文字のＩＤも示す。たとえば、正字法形式「ａｂｃＹｄｅｆ」について、エントリは３つの代替文字が好ましい文字の前にあり、第１の代替文字が「ａ」であることを示す。このエントリはさらに、単語の好ましい正字法形式内でどの好ましい文字が先頭であるかも示す。たとえば、「ＶＸＹＺ」が単語「ａｂｃＹｄｅｆ」の好ましい正字法形式であった場合、エントリは「Ｖ」がその単語の好ましい形式の第１の好ましい文字であることを示す。

上述のように、ルックバックデータ構造は、入力文字列が好ましい文字で始まらないが、好ましい文字を含む場合にアクセスされる。入力文字列内の第１の好ましい文字を使用して、ルックバック構造を検索し、その文字のエントリを見つける。ルックバックインジケータによって示される差の分だけ検索文字の前にある入力文字列内の文字を評価する。評価された文字がルックバックエントリに格納されている代替文字と一致する場合、ルックバックエントリ内の第１の単語要素の好ましい形式を使用して、正字法ラティスを検索する。単語ブレーカ３０２では、この好ましい形式で始まる正字法ラティス内のエントリごとに、元の入力文字列とラティスエントリを比較し、エントリ内の正字法形式が入力文字列と一致するかどうかを調べる。一致している場合、単語の好ましい正字法形式は、単語ラティス内に挿入される。

いくつかの実施形態では、ルックバックエントリのいくつかの第１の好ましい文字は、好ましい文字のシーケンスを含む単語要素の一部である。このような実施形態では、ルックバック構造を検索するために使用される入力文字の後の入力文字列内の文字をそれぞれ、エントリ内の要素を構成する好ましい文字と比較する。これらの値が一致しない場合、ラティス検索は実行されない。

ステップ４０２で単語ブレーカ３０２が屈折形態論と正字法正規化を実行した後、単語ラティスは、入力テキスト内の文字と、入力テキスト内の単語のバリエーションをセグメント化することで直接形成できる単語で構成される。上述のように、これらのバリエーションの文字数は、バリエーションの元になった単語よりも多い場合も少ない場合もあり、また入力テキスト内に存在していない文字を含むこともある。したがって、単語ブレーカ３０２で生成される単語ラティスは、入力テキスト内に存在しているものと異なる文字を含むことができる。

単語ブレーカ３０２で生成される単語ラティスは、大きな語彙レコードセット３１２にアクセスできる語彙ルックアップ部３１０に送られる。大きな語彙レコードセット３１２は、小さな語彙レコードセット３０４よりも多い語彙情報を含む。実際、多くの実施形態では、小さな語彙レコードセット３０４が、大きな語彙レコードセット３１２を参照して構築され、定期的に更新される。

語彙ルックアップ部３１０は、大きな語彙レコードセット３１２を使用して、図４のステップ４０６でラティス内の各単語について単語ラティスに格納されている語彙情報の量を増やす。このような追加情報は、単語の語源などの項目、単語を適切な名詞の中で使用できるかどうか、および単語その他の語彙および文法上の詳細を含む。

単語ラティスは、拡張された語彙情報とともに、語彙ルックアップ３１０から派生形態論３１４に渡される。図４のステップ４０８で、派生形態論３１４は、単語ラティス内の文字の連続するセグメントを組み合わせてより大きな多セグメント単語を形成する。たとえば、派生形態論コンポーネント３１４は、接尾辞文字列、挿入辞文字列、および接頭辞文字列を、他のセグメントに対して、後ろに追加したり、挿入したり、前に追加したりすることができる。いくつかの実施形態では、形態論コンポーネント３１４によりステップ４０８ではなく、単語ブレーカ３０２によりステップ４０２でこれらの派生形態論規則の一部または全部が適用される。ただし、形態論コンポーネント３１４の適用には、派生形態規則に入力する大きな語彙レコードセットで豊富な情報を利用できるという利点がある。さらに、派生形態論コンポーネント３１４では、人、施設、および地理的場所の名称およびその他の固有名詞などの名前が付けられた実体、および日付や時刻などのその他の単位を識別し、抽出するためセグメントを組み合わせることができる。

派生形態論３１４によって構成される大きな単語は、その大きな単語の語彙情報とともに単語ラティスに追加される。ほとんどの実施形態では、派生形態論３１４で構成される大きな単語は、小さなセグメントを置き換えることはないが、その代わりに、小さなセグメントに加えてラティス内に置かれる。

派生形態論３１４によって生成される拡張された単語ラティスは、重なり合う１つまたは複数のセグメントを通常は含む。このような重なり合うセグメントは、１つまたは複数の文字を共通して持つ入力文字列から直接派生するセグメントを含む。重なり合うセグメントはさらに、１つまたは複数のその他のセグメントと重なる入力文字列内のセグメントから生成された屈折形態論または正字法正規化を通じて形成されたバリエーションを含む。

派生形態論３１４により生成された拡張された単語ラティスは、構文パーサ３１６に送られ、そこで、図４のステップ４１０で拡張された単語ラティスを使用して構文解析を実行する。一実施形態では、小さな単語および語句から大きな語句をインクリメンタルに構築することにより構文パースを出力するボトムアップチャートパース（ｂｏｔｔｏｍ−ｕｐ ｃｈａｒｔ ｐａｒｓｅ）を使用して構文解析を実行する。大きな語句を構築するために、構文パーサ３１６は、単語または語句の語彙指定を調べて大きな単語または語句を形成するためにどのように組み合わせるかを決定する文法規則を適用する。一実施形態では、２つの隣接する単語または語句を調べるバイナリ文法（ｂｉｎａｒｙ ｇｒａｍｍａｒ）を使用して、組み合わせ方を決定する。

構文パーサ３１６によって実行される構文解析では、拡張された単語ラティス内のすべてのセグメントを考慮する。構文パーサは、元の入力テキスト内の隣接する文字を表すセグメントのみを組み合わせ、最終的な解析で入力テキスト全体を対象とするように制約されている。したがって、構文パーサは、重なる２つのセグメントを伴う有効なパースを生成できないか、または入力文字列の全体を表さないセグメントのグループについて有効な構文解析結果を生成できない。

一実施形態では、構文パーサ３１６は、その出力で単一のパースを生成する。この単一のパースにより、単語ラティス内にある単語のグループ間の関係が識別される。屈折形態論および正字法正規化を実行して単語ラティスを構築しているため、この有効なパースに、元々入力テキスト内にはなかった形式の単語を含めることができる。その結果得られる有効なパースは、単語ラティス内で見つかった複数の可能なセグメント化から選択した入力テキストの有効なセグメント化を含む。構文パーサは、本質的に、重なり合うセグメントのグループから１つのセグメント化を選択するので、本発明では、構文パーサの前に適切なセグメント化を識別する別のセグメント化ユニットを必要としない。その代わりに、構文パーサ自体が、入力テキストの最も可能性の高いセグメント化を選択する。

本発明で生成されるセグメント化は、従来技術のセグメント化よりも高度であるが、それは構文パーサが入力テキスト自体の中に必ずしも存在していなかった文字に基づいて動作しているからである。したがって、構文パーサから得られるセグメント化の結果は、入力テキスト内に存在していなかった、従来技術のセグメント化システムでは考慮されていない単語形式に基づいている。

他の実施形態では、構文パーサ３１６は、複数の有効な構文パースを生成し、それぞれ、入力テキストの別々の有効なセグメント化を表す。一実施形態では、これらの有効なパースはそれぞれ、各パース内での意味論的関係を識別する論理形式ジェネレータ３１８に渡される。その後、意味論的関係を使用して、有効な構文パースのうちどれが入力文字列の正しいパースであるかを選択することができる。この意味論的識別は、図４でステップ４１２として示されている。

本発明は、特定の実施形態を参照しながら説明したが、当業者には本発明の精神と範囲を逸脱することなく形式と詳細に変更を加えられること明白であろう。

本発明を実装するのに適した汎用コンピュータシステム実施例のブロック図である。 本発明を実施できるハンドヘルドデバイスのブロック図である。 本発明の一実施形態の要素の詳細なブロック図である。 本発明の例示の実施形態による構文解析を使用してセグメント化する方法の流れ図である。 本発明の一実施形態において使用される正字法ラティスを示す図である。

Claims (2)

1. セグメント化されない言語の入力文字列をセグメント化する方法であって、
   前記文字列内の可能なセグメントを識別するステップであって、前記可能なセグメントのうちの少なくとも２つが互いに重なっているステップと、
   前記可能なセグメントのうちの少なくとも１つに対する代替文字列を識別するステップであって、前記代替文字列が代替セグメントを形成するステップと、
   前記可能なセグメントおよび前記代替セグメントを用いて複数の構文解析を実行するステップであって、該解析が、前記入力文字列のセグメント化に役立ち、
   前記入力文字列のセグメント化をもたらす完全な構文解析をもたらすステップと
   を備えることを特徴とする方法。
2. セグメント化されない言語の文字列内の構文を識別するシステムであって、
   前記入力文字列から単語の集合を生成するプロセッサの単語ブレーカであって、前記単語の集合が、前記文字列内の同じ文字から、その一部が得られる少なくとも２つの単語を含み、前記単語ブレーカが、
   前記単語の集合のための単語であって前記文字列から直接取り出される単語を得るために用いられる、システムメモリに格納された語彙レコードセットと、
   前記文字列内に見つかる単語の単語バリエーションを得るために前記プロセッサによって用いられる、システムメモリに格納されたバリエーションコンストラクタであって、各単語バリエーションは前記単語の集合に追加され、各単語バリエーションは、そのバリエーションの元である前記文字列内の単語に関する文字列とは異なる文字列を有し、各単語バリエーションは、前記文字列の単語とは異なる正字法形式または屈折形式を有するバリエーションコンストラクタとを用いる単語ブレーカと、
   前記単語ブレーカにより生成された単語の集合を用いて構文解析を実行し、前記文字列の構文を示す構文パースを生成する、前記プロセッサの構文パーサと
   を備えることを特徴とするシステム。

Images