(57)【要約】【課題】言語処理のための二次元書き換え規則を提供する。【解決手段】順に並んだ言語トークン列の言語処理に用いるための言語書き換え規則３０は、順に並んだ言語トークン列を構文パタンと照合する、トークンパタン認識規則を含む。トークンパタン認識規則は、文字パタン認識規則を組み込むことで、順に並んだ言語トークン列の曖昧な部分に含まれる文字を、構文パタンの対応する部分を定義する文字パタンと照合する。【選択図】図１
2006178980.tif 000002
【特許請求の範囲】
【請求項１】
対応するデジタルプロセッサで実行された場合に、順に並んだ言語トークン列の言語処理に用いるための書き換え規則を実現する命令を記憶する記憶媒体であって、
前記書き換え規則は、（ｉ）文字パタン認識規則と、（ｉｉ）前記順に並んだ言語トークン列を構文パタンと照合するトークンパタン認識規則と、を含み、
前記トークンパタン認識規則は、前記文字パタン認識規則を組み込むことで、前記順に並んだ言語トークン列の曖昧な部分に含まれる文字を、前記構文パタンの対応部分を定義する文字パタンと照合する、記憶媒体。
【請求項２】
請求項１に記載の記憶媒体において、前記書き換え規則は、前記構文パタンと一致する前記順に並んだ言語トークン列を、名づけられた実体カテゴリに関連付ける、記憶媒体。
【請求項３】
請求項２に記載の記憶媒体において、前記構文パタンは、トークンを含み、前記トークンは、（ｉ）名詞として分類され、かつ、（ｉｉ）大文字で始まる、記憶媒体。
【請求項４】
順に並んだ言語トークン列を処理する言語処理方法であって、
前記順に並んだ言語トークン列と構文パタンとの照合を試みるステップであって、前記照合を試みるステップの少なくとも一部は、前記順に並んだ言語トークン列の曖昧な部分中に含まれる文字と文字パタンとの照合を試みることで実行されるステップと、
成功した照合に応じて、（ｉ）前記順に並んだ言語トークン列、（ｉｉ）前記順に並んだ言語トークン列中の順に並んだ下位トークン列、及び（ｉｉｉ）前記順に並んだ言語トークン列から選択されたトークン、のうち、少なくとも１つを分類するステップと、
を含むことを特徴とする言語処理方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、言語学の技術に関し、特に、電子翻訳機、ワードプロセッサの文法チェッカ、文書内容分析機、などの様々なアプリケーションに用いるための、自動自然言語処理に関連して応用できる。特に、そのようなアプリケーションを参照して本発明を説明する。しかしながら、以下は他の同様のアプリケーションにも応用できることが理解される。
【背景技術】
【０００２】
自然言語処理は、一般的に、語彙処理層、構文処理層、及び意味処理層、の３つの別個の処理層によって実行される。語彙の段階においては、言語の入力が、一般的に単語及び句読点を含む、基本の構成素に分解される。各々の単語、句読点、又は他の要素を、一般的に、トークンと呼ぶ。語彙層においては、各単語又はトークンを、辞書（lexicon）に含まれる語彙情報と関連付ける試みが行われる。辞書は、形態統語（morpho‐syntactic）情報、意味情報、及び関連する品詞を含む。このような、語彙段階におけるトークンの関連付けを、形態素解析と呼ぶ。語彙層は一般的に、個々のトークンに作用し、周囲の文脈、つまり、周囲のトークンを考慮することはない。従って、語彙処理の後では、しばしば、かなりの曖昧性が残る。例えば、英語の「ｆｌｙ」というトークンは、ある昆虫を示す名詞を表す可能性があり、又は、空中の動きを示す動詞を表す可能性がある。さらに、機械的な装置を示す「ｆｌｙ  ｗｈｅｅｌ」、又は、航空機が頭上を飛ぶという事象を示す「ｆｌｙ  ｂｙ」のような、連語の一部である可能性がある。
【０００３】
構文処理層において、トークンは、文脈情報を考慮して処理される。従って、例えば、対になっているトークン（例えば、“ｆｌｙ”及びこれに続く“ｗｈｅｅｌ”）を認識することで、連語を識別する。さらに、この追加の文脈情報は、形態統語解析、及び品詞の選択肢を狭めるために利用される。単語の定義を考慮する曖昧性解消レベルと、単語の意味を他に考慮することなく、構文カテゴリを考慮する（例えば、品詞又はより高レベルの構成素列を考慮する）文脈自由文法レベルと、に構文処理を分解することがある。このような文法を、拡張文脈自由文法と呼ぶことがある。一般的に、その文法は、書き換え規則によって記述される。各書き換え規則は、より高レベルの構成素を、より低レベルの、順に並んだ構成素列に関連付ける。
【０００４】
書き換え規則は、一般的に、「トップダウン（top‐down）」解析、若しくは、「ボトムアップ（bottom‐up）」解析、又は、それらのある組み合わせにおいて利用することができる。トップダウン法においては、言語入力を構成する、順に並んだトークン列の全体の形式を解析して、逐次、より低レベルの構成素に分解していく。例えば、文（Ｓ）から始まって、書き換え規則「Ｓ→ＮＰ  ＶＰ」を用いて、文の全体の形式に基づいて、名詞部（ＮＰ）及び動詞部（ＶＰ）を識別する。ＮＰ及びＶＰは、高レベル構成素であり、順番に、品詞などのより低レベルの構成素に分解される。
【０００５】
ボトムアップ法においては、個々のトークンをグループ化することで、逐次、より高レベルの構成素を識別する。例えば、冠詞（ＡＲＴ）としてタグ付けされるトークン「ｔｈｅ」と、その後に続く、名詞（Ｎ）としてタグ付けされるトークン「ｄｏｇ」とを、書き換え規則「ＮＰ→ＡＲＴ  Ｎ」を用いてグループ化し、「ｔｈｅ  ｄｏｇ」を名詞部（ＮＰ）構成素として識別する。その後、順番に、書き換え規則「Ｓ→ＮＰ  ＶＰ」に従って、名詞部は動詞部（ＶＰ）とグループ化され、文（Ｓ）構成素が識別される。関連技術として、以下に示す特許文献がある。
【０００６】
【特許文献１】米国特許第５６４２５２２号明細書
【発明の開示】
【発明が解決しようとする課題】
【０００７】
いくつかの構文処理装置は、再帰的解析を用いる。文、「Ｉ  ｈａｖｅ  ａｎｓｗｅｒｅｄ  ｔｈｅ  ｉｎｑｕｉｒｙ．」について考える。この文は、過去分詞「ａｎｓｗｅｒｅｄ」を含む。語彙解析では、トークン「ｈａｖｅ」、及びトークン「ａｎｓｗｅｒｅｄ」を識別する。語彙解析では文脈を考慮しないため、トークン「ｈａｖｅ」は曖昧であり、例えば、動詞、又は助動詞のいずれにもなり得る。トークン「ａｎｓｗｅｒｅｄ」も曖昧であり、形容詞、又は過去分詞のどちらでもあり得る。トークン「ａｎｓｗｅｒｅｄ」には、例えば「ＡＤＪＯＲＰＡＰ」のような、適切に曖昧なカテゴリが関連付けられる。１回目に構文処理レベルを通る時には、「ｈａｖｅ」及びこれに続くカテゴリ「ＡＤＪＯＲＰＡＰ」のトークンの順番の組み合わせは、過去分詞形として認識される。このため、「ｈａｖｅ」は助動詞のカテゴリに、「ａｎｓｗｅｒｅｄ」は過去分詞のカテゴリに入れられる。２回目に構文処理レベルを通る時には、文脈自由書き換え規則が、助動詞「ｈａｖｅ」及びこれに続く過去分詞の順番の組み合わせを、現在完了時制の動詞構成素として認識する。このような再帰的構文処理は、構文処理層の、計算効率及び速度を減少させる。
【０００８】
もう一つの問題は、固有名詞の利用において生じる。例えば、固有名詞「Ｂａｎｋｕｎｉｔｅｄ  Ｂａｎｃｏｒｐ」について考える。これを、銀行の名称を表す固有名詞として認識することが望ましい。しかしながら、その銀行が、大きな国内銀行、又は国際銀行でない限り、語彙処理レベルにおいて、トークン「Ｂａｎｋｕｎｉｔｅｄ」及び「Ｂａｎｃｏｒｐ」が、辞書に含まれる可能性は低い。辞書がこれらのトークンを含まない場合、語彙処理レベルでは、トークン「Ｂａｎｋｕｎｉｔｅｄ」及び「Ｂａｎｃｏｒｐ」に、形態統語情報、意味情報、又は品詞を関連付けることはできないだろう。続いて処理を行う構文処理レベルにおいても、周囲の文脈に基づいて、これらの品詞が名詞であると類推されない限り、これらのトークンに意味を関連付けることはできないだろう。他のより高レベルの構成素クラスについても、同様の問題が生じる。例えば、化学物質名、人名などの、その構成素クラスに属する単語を、容易には完全に辞書に列挙できない場合が問題となる。
【課題を解決するための手段】
【０００９】
１つの態様において、デジタルプロセッサにより実行された場合に、順に並んだ言語トークン列の言語処理に用いるための書き換え規則を実現する命令を記憶する記憶媒体が開示される。書き換え規則は、文字パタン認識規則と、順に並んだ言語トークン列を構文パタンと照合する、トークンパタン認識規則と、を含む。トークンパタン認識規則は、文字パタン認識規則を組み込み、順に並んだ言語トークン列中の曖昧な部分に含まれる文字を、構文パタンの対応部分を定義する文字パタンと照合する。
【００１０】
他の態様において、順に並んだ言語トークン列の言語処理に用いるための言語書き換え規則が開示される。書き換え規則は、文字パタン認識規則と、順に並んだ言語トークン列を構文パタンと照合する、トークンパタン認識規則と、を含む。トークンパタン認識規則は、文字パタン認識規則を組み込み、順に並んだ言語トークン列中の曖昧な部分に含まれる文字を、構文パタンの対応部分を定義する文字パタンと照合する。
【００１１】
他の態様において、順に並んだ言語トークン列を処理するための言語処理方法が実現される。順に並んだ言語トークン列と構文パタンとの照合が試みられる。照合する試みの少なくとも一部は、順に並んだ言語トークン列中の曖昧な部分に含まれる文字と、文字パタンとの照合を試みることによって実行される。（ｉ）順に並んだ言語トークン列、（ｉｉ）順に並んだ言語トークン列中の順に並んだ下位列、（ｉｉｉ）順に並んだ言語トークン列から選択したトークン、のうち少なくとも１つが、成功した照合に応じて分類される。
【００１２】
さらに他の態様において、言語入力を解析するためのパーザ（parser）が開示される。トークン化モジュールは、辞書と機能的に連絡する。トークン化モジュールは、言語入力を、順に並んだ言語トークン列に分割する。文字パタン認識コンポーネントが、順に並んだ文字列を文字パタンと照合する試みのために設けられる。トークンパタン認識コンポーネントが、順に並んだ言語トークン列を構文パタンと照合する試みのために設けられる。トークンパタン認識コンポーネントは、文字パタン認識コンポーネントを呼び出して、順に並んだ言語トークン列の曖昧な部分を、構文パタンの不確定な部分と照合しようと試みる。カテゴリ関連付け部（アソシエイタ（associator））が、構成素カテゴリを、（ｉ）順に並んだ言語トークン列、（ｉｉ）順に並んだ言語トークン列中の順に並んだ下位列、（ｉｉｉ）順に並んだ言語トークン列から選択したトークン、のうち少なくとも１つと関連付けるために設けられる。関連づけは、トークンパタン認識コンポーネントが実行する照合の成功に応じて行われる。
【発明を実施するための最良の形態】
【００１３】
図１を参照すると、自然言語処理システムは、パーザ１０を含み、このパーザ１０は、例えば、仏語、英語、又は他の自然言語で書かれた、段落、文、文の一部、又は複数の単語によるテキスト断片、などの自然言語テキスト１２を、受け取る。パーザ１０は、トークン化モジュール１４を含み、このトークン化モジュールは、自然言語テキスト１２を順に並んだトークン列に分解する。例えば、適切な手法においては、スペース及び／又は句読点によって区切られた各単語を、単一のトークンとして定義し、各句読点を単一のトークンとして定義する。トークン化モジュール１４は、語彙又は形態素処理も実行する。トークン化モジュール１４は、トークンの周囲の文脈を考慮することなく、すなわち、隣接するトークンを考慮することなく、形態統語情報、意味情報、及び品詞を、各トークンに関連付けるように試みる。これを行うために、トークン化モジュール１４は辞書１６を参照する。
【００１４】
辞書１６は、仏語、英語、又は処理にかける他の自然言語の単語のデータベースである。辞書１６は、形態統語情報、意味情報、及び品詞を、記憶された自然言語の単語と関連付ける。従って、例えば、トークン「ｇｏｒｉｌｌａ」は、「男性的」、「単数」、などのような形態統語情報、及び、「動物」のような意味情報によって辞書１６において識別され、名詞構成素としても分類される。いくつかの実施形態においては、トークン化モジュール１４は、入力テキスト１２をトークンに分割し、トークンを辞書１６の登録語と比較及び識別するために、オートマトンを用いる。
【００１５】
しかしながら、トークン化モジュール１４によって実行される語彙処理は文脈を考慮しないため、いくつかのトークンは曖昧である可能性がある。例えば、トークン「ｄｏｃｕｍｅｎｔ」は、英語の文中でどのように用いられるかによって、名詞又は動詞になり得る。これは、語彙処理において、トークン「ｄｏｃｕｍｅｎｔ」に、名詞及び動詞の両方を、２つの品詞候補として関連付けることで対処できる。加えて、いくつかのトークンは辞書１６に含まれていない可能性がある。例えば、辞書１６は、すべての人、場所、企業、又は他の名づけられた実体（entity）についての固有名詞について、包括的かつ網羅的なリストを含むことはできない。
【００１６】
トークン化モジュール１４によって実行される語彙処理の後、順に並んだトークン列は、構文処理部２０によって実行される構文解析を受ける。語彙解析では各トークンを単独で考慮する一方、構文解析では、順に並んだトークンの組み合わせを考慮する。このような構文解析は、語彙レベルにおいては曖昧、又は未確認であったいくつかのトークンの品詞を明確に決定し得る。加えて、構文解析では、２以上の単語又はトークンから構成される、より高レベルの構成素を識別することができる。従って、例えば、順に並んだトークン列「ｈａｖｅ  ａｎｓｗｅｒｅｄ」を、個々のトークン「ｈａｖｅ」及び「ａｎｓｗｅｒｅｄ」の品詞と、より高レベルの動詞構成素「ｈａｖｅ  ａｎｓｗｅｒｅｄ」と、の両方について明確に識別することができる。
【００１７】
いくつかの実施形態において、構文解析では文脈自由文法を用いる。文脈自由文法は、品詞などの文法的分類と、複数語からなる固有名詞及び名詞部などのより高レベルの分類と、は考慮するが、単語の定義によって与えられる単語の意味は考慮しない。しかしながら、純粋な文脈自由文法は、非標準的な用法でトークンを用いる複数語構造の連語を見逃す可能性がある。例えば、「ｆｌｙ  ｗｈｅｅｌ」という語句では、非標準的な用法で、構成素トークン「ｆｌｙ」を用いている。
【００１８】
従って、図示する実施形態においては、拡張文脈自由文法が用いられる。曖昧性解消モジュール２２は、辞書１６の情報に基づいて連語を処理する。従って、辞書が連語「ｆｌｙ  ｗｈｅｅｌ」を識別する場合、曖昧性解消モジュール２２は、トークン「ｗｈｅｅｌ」を名詞（Ｎ）に、トークン「ｆｌｙ」を形容詞（ＡＤＪ）に、適切に分類する。「ｆｌｙ」は、通常は形容詞ではないため、純粋な文脈自由文法では、「ｆｌｙ」を正常に分類することはできない。
【００１９】
拡張文脈自由文法の文脈自由コンポーネントは、適切な書き換え規則によって定義された文脈自由文法２６を適用する、チャンキング（chunking）モジュール２４によって実現される。文脈自由文法２６の各書き換え規則は、順に並んだ言語トークン列を構文パタンと照合するトークンパタン認識規則を定義し、従って、より高レベルの構成素を、順に並んだ、より低レベルの構成素列に関連付ける。この、より低レベルの構成素列は、順に並んだ言語トークン列によって定義される。例えば、書き換え規則「Ｓ→ＮＰ  ＶＰ」は、より高レベルの文（Ｓ）構成素を、より低レベルの、名詞部（ＮＰ）構成素、及び動詞部（ＶＰ）構成素に関連付ける。名詞部（ＮＰ）構成素、及び動詞部（ＶＰ）構成素は、それぞれ、順に並んだ１以上の言語トークン列から成る。書き換え規則「ＮＰ→ＡＤＪ  Ｎ」は、より高レベルの名詞部（ＮＰ）を、形容詞（ＡＤＪ）としてタグ付けされたトークンと、それに続く、名詞（Ｎ）としてタグ付けされたトークンと、に関連付ける。これらは例示でしかない。一般的な文脈自由文法は、集合的に多くの構文パタンを包含する、このような多くの書き換え規則を含む。曖昧性解消モジュール２２及び文脈自由文法２６の書き換え規則の両方が、トークン構成素レベルで、又はより高レベルで、作用する。
【００２０】
チャンキングモジュール２４は、拡張自由文法が効果的に処理することのできない、特定の構文構造を記述する、二次元書き換え規則３０も実現する。各二次元書き換え規則３０は、順に並んだ言語トークン列を構文パタンと照合する、トークンパタン認識規則を定義する。トークン構成素レベル、又はそれよりも高いレベルで作用する、文脈自由文法２６の書き換え規則とは異なり、各二次元書き換え規則は、少なくとも１個の文字パタン認識規則を組み込む。文字パタン認識規則は、順に並んだ言語トークン列中の曖昧な部分に含まれる文字を、構文パタンの対応部分を定義する文字パタンと照合する。従って、二次元書き換え規則３０は、文字レベルにおける語彙パタンと、トークン構成素レベル以上のレベルにおける構文パタンと、の両方に従って言語表現を記述する点において二次元である。
【００２１】
二次元書き換え規則３０は、特定の構文パタンを記述する。その特定の構文パタンは、構文を考慮する必要があるため、語彙レベルでは記述できないが、トークン構成素レベル以上のレベル単独では容易に記述できない。例えば、企業体は、しばしば、事業の種類を連想させる語根（word root）を含む固有名詞を有する。語根は、語彙レベルでトークンをタグ付けするには不十分であるが、構文情報を組み合わせると、明確に識別できる。同様の状況が、一般に化学的要素と関連する語根によって構成される複数語の用語である、化学物質の名称においても存在する。文字レベルで語根が識別できる場合もあるが、組み合わせの数が多すぎるため、辞書１６に記載することはできない。二次元書き換え規則３０が有利である他の状況は、本明細書に記載する例の中で説明する。
【００２２】
以上に説明した構文処理部２０は、実施形態の一例にすぎない。いくつかの実施形態においては、図１の後ろ向きの点線矢印３２に示すように、構文処理を再帰的に行うこともできる。いくつかの実施形態においては、構文処理部に純粋な文脈自由文法を実現するために、曖昧性解消モジュール２２が除外される。いくつかの実施形態においては、曖昧性解消モジュール２２及びチャンキング処理部２４は、単一の統一した構文処理部として統合される。この構文処理部は、辞書１６から得られる、形態統語情報及び意味情報を用いる、選択された文脈ベースの書き換え規則と、文脈自由書き換え規則と、の両方を実現する。
【００２３】
パーザ１０の出力は、自然言語処理システムの意図されたアプリケーションによって、様々な方法で利用することができる。例えば、ワードプロセッサと共に用いる文法チェッカにおいては、パーザ１０の出力を直接利用することができる。すべてのトークンについて、明確な品詞をタグ付けできる場合は、対応する自然言語テキスト１２は文法的に正しいとみなされる。一方、いくつかのトークンについて明確な品詞をタグ付けできない場合は、これらの曖昧性は、文法的に問題がある可能性として、例えば、ワードプロセッサで表示されるテキスト中の、これらの曖昧な単語に下線を引くことで、報告される。文書内容分析器、翻訳機、及び、テキストの意味が重要な他のアプリケーションにおいて、パーザ１０の出力に対して、更なる処理を実行することもできる。このような、更なる意味処理を、全般的に、意味処理モジュール３４として図１に示す。意味処理モジュール３４は、文書内容分析、言語翻訳などの処理を実行することができる。
【００２４】
ここまで、二次元書き換え規則３０を組み込んだパーザ１０の例を説明した。以下、更なる例を示すため、二次元書き換え規則のいくつかの例を記載する。
【００２５】
特定の実体型の関連付けは、適切に構成された二次元書き換え規則によって、適切に行われる。辞書１６に、企業又は他の団体の固有名詞の網羅的なリストを含むことは難しい。例えば、金融機関の名称として可能性のある名称を、短いリストとして挙げると、「ＢａｎｋＡｔｌａｎｔｉｃ  Ｂａｎｃｏｒｐ」、「Ｂａｎｋｕｎｉｔｅｄ  Ｆｉｎａｎｃｉａｌ」、「ＢａｎｋＥｎｇｉｎｅ  Ｔｅｃｈｎｏｌｏｇｉｅｓ」、「Ｂａｎｋｓｈａｒｅ  Ｂｅｎｃｈｍａｒｋ」がある。このリストは、明らかに、網羅的ではない。トークン「ＢａｎｋＡｔｌａｎｔｉｃ」、「Ｂａｎｋｕｎｉｔｅｄ」、「ＢａｎｋＥｎｇｉｎｅ」、及び「Ｂａｎｋｓｈａｒｅ」が辞書１６に含まれる可能性は低い。これらの各トークンは、大文字で始まる語根「Ｂａｎｋ」を含むことから、金融機関の固有名詞の一部であるという、強力な情報を有する。しかしながら、トークン化モジュール１４が個々のトークンを固有名詞の一部であることを識別するためには、この語根それ自身だけでは不十分である。この語根に続くトークンが大文字で始まることから得られる、周囲の構文情報と、この語根とを組み合わせることで、順に並んだトークン列：「ＢａｎｋＡｔｌａｎｔｉｃ  Ｂａｎｃｏｒｐ」；「Ｂａｎｋｕｎｉｔｅｄ  Ｆｉｎａｎｃｉａｌ」；「ＢａｎｋＥｎｇｉｎｅ  Ｔｅｃｈｎｏｌｏｇｉｅｓ」；「Ｂａｎｋｓｈａｒｅ  Ｂｅｎｃｈｍａｒｋ」が、金融機関の固有名詞であることを、比較的確信を持って、主張するのに十分な情報が得られる。しかしながら、文脈自由文法２６は、構成素レベル以上のレベルでトークンに作用するので、「Ｂａｎｋ」で始まる語根を文脈自由文法で考慮することはできない。しかしながら、二次元書き換え規則は、文字ベースの語根の様相「Ｂａｎｋ．．．」と、後に続くトークンが大文字で始まる名詞と共にこの語根を有するという構文的な様相と、の両方を考慮することができる。
【００２６】
これらのトークン列の全てを金融機関として識別する、適切な二次元書き換え規則を、適切に代数的に記述すると、以下の式（１）になる。
ｎｏｕｎ［ｏｒｇａｎｉｚａｔｉｏｎ：＋］→ｎｏｕｎ［ｌｅｍｍａ：Ｂａｎｋ？＋］，ｎｏｕｎ［ｌｅｍｍａ：［Ａ‐Ｚ］？*］  （１）
ここで、二次元書き換え規則（１）は、次のように解釈する。「団体（organization）という素性（feature）を有する、名詞に分類された要素は、名詞に分類された要素であって、その補題（lemma）が『Ｂａｎｋ』と一致する要素と、これに続く、大文字で始まる、すべての文字列及び名詞に分類された要素の列と、の連結に書き換えられる」。二次元書き換え規則（１）を用いると、辞書１６に属さない単語に対する、追加の語彙コーディングを必要とすることなく、前述の金融機関の固有名詞のすべてと、同様な名称の多くの金融機関の固有名詞と、に団体という素性が関連付けられる。
【００２７】
図２Ａ及び図２Ｂを参照すると、二次元書き換え規則（１）の、２つのパタン認識規則コンポーネントの各々が、補題を含む。各補題は、構文パタンの曖昧な部分に対処し、変換機（transducer）のようなオートマトンによって適切に実現される。図２Ａは、「ｌｅｍｍａ：Ｂａｎｋ？＋」を適切に実現するオートマトンを示す。図２Ｂは、「ｌｅｍｍａ：［Ａ‐Ｚ］？*」を適切に実現するオートマトンを示す。図２Ａのオートマトンは、順に並んだトークン列の第１のトークンの文字に対して、左から右へ作用し、一方、図２Ｂのオートマトンは、順に並んだトークン列の第２のトークンの文字に対して、同様に左から右へ作用する。
【００２８】
二次元書き換え規則の他の適用例は、特定分野のコーパス（ｃｏｒｐｏｒａ）における、多単語の専門用語の認識に対処する。例えば、化学及び医学のような分野において、化学物質要素の名称は、しばしば、類似の語彙構文パタンによって構成される。例えば、以下の、酸の名称の非網羅的なリストについて考える。「ａｌｐｈａ‐ｃｏｌｌａｔｏｌｉｃ  ａｃｉｄ」、「ａｌｅｃｔｏｒｏｎｉｃ  ａｃｉｄ」、「ｂａｒｂａｔｉｃ  ａｃｉｄ」、「ｃａｐｅｒａｔｉｃ  ａｃｉｄ」、「ｃｏｎｓｔｉｃｔｉｃ  ａｃｉｄ」、「ｃｏｎｓａｌａｚｉｎｉｃ  ａｃｉｄ」、「４‐ｏ‐ｄｅｍｅｔｈｙｌｂａｒｂａｔｉｃ  ａｃｉｄ」、「ｃｉｖａｒｉｃａｔｉｃ  ａｃｉｄ」、「ｅｃｈｉｎｏｃａｒｐｉｃ  ａｃｉｄ」、「ｅｖｅｒｎｉｃ  ａｃｉｄ」、「ｆｕｍａｒｐｒｏｔｏｃｅｔｒａｒｉｃ  ａｃｉｄ」、「ｇｌｏｍｅｌｌｉｆｅｒｉｃ  ａｃｉｄ」、「ｇｌｏｍｅｌｌｉｃ  ａｃｉｄ」、「ｇｙｒｏｐｈｏｒｉｃ  ａｃｉｄ」、「ｌｏｂａｒｉｃ  ａｃｉｄ」、「ｌｅｃａｎｏｒｉｃ  ａｃｉｄ」、「ｎｏｒｏｂｔｕｓａｔｉｃ  ａｃｉｄ」、「ｎｏｒｓｔｉｃｔｉｃ  ａｃｉｄ」、「ｎｒｏｔｏｃｅｔｒａｒｉｃ  ａｃｉｄ」、「ｎｅｒｌａｔｏｌｉｃ  ａｃｉｄ」、「ｓｅｃａｌｏｎｉｃ  ａｃｉｄ」、「ｓｔｅｎｏｓｐｏｒｉｃ  ａｃｉｄ」、「ｓｔｉｃｔｉｃ  ａｃｉｄ」、「ｓａｌａｚｉｎｉｃ  ａｃｉｄ」、及び「ｕｓｎｉｃ  ａｃｉｄ」。他に多くの同様な名称の酸が存在する。酸の名称は、「‐ｉｃ」で終わる単語と、それに続く「ａｃｉｄ」とを含む。このような酸についての包括的なリストを、辞書１６に符号化するのは難しいだろう。しかしながら、「‐ｉｃ」で終わる単語と、それに続く「ａｃｉｄ」とを含む、すべての酸の名称は、以下の二次元書き換え規則で適切に扱える。
Ｎｏｕｎ［ａｃｉｄＮａｍｅ＝＋］→？［ｌｅｍｍａ：［ａ‐ｚ＼‐］＋ｉｃ］，
ｎｏｕｎ［ｌｅｍｍａ：ａｃｉｄ］  （２）
二次元書き換え規則（２）は、辞書１６に何も符号化することなく、前述の酸の名称のすべてを、適切に分類する。
【００２９】
図３Ａ及び図３Ｂを参照すると、二次元書き換え規則（２）における文字パタン認識規則は、２つの補題を含む。各補題は、構文パタンの曖昧な部分に対処し、変換機のようなオートマトンによって適切に実現される。図３Ａは、「ｌｅｍｍａ：［ａ‐ｚ＼‐］＋ｉｃ」を適切に実現するオートマトンを示す。図３Ｂは、「ｌｅｍｍａ：ａｃｉｄ」を適切に実現するオートマトンを示す。図３Ａのオートマトンは、第１のトークンの文字に対して、右から左へ作用し、一方、図３Ｂのオートマトンは、第２のトークンの文字に対して、左から右へ作用する。第２の補題は固定長４文字の単語であるので、（図３Ｂの状態４から状態０へと）右から左へ作用する、同等のオートマトンもまた適切である。
【００３０】
二次元書き換え規則は、構文情報に基づいて、品詞を識別することにもまた有利であり得る。例えば、「‐ｅｄ」で終わる、曖昧な未知の単語の前に、動詞「ｈａｖｅ」のある形式がくる構文パタンについて考える。構文処理部２０は、以下の二次元書き換え規則を用いて、この構文パタンを処理し、文脈を利用して「‐ｅｄ」で終わる単語を過去分詞として識別することができ、同時に、助動詞「ｈａｖｅ」のある形式と、それに続く「‐ｅｄ」で終わる単語と、によって複合動詞形を構成することができる。
Ｖｅｒｂ＿Ｃｈａｉｎ［ｐｅｒｆｅｃｔ＝＋］→
Ｖｅｒｂ［ｌｅｍｍｅ：ｈａｖｅ］，？［ｇｕｅｓｓ：＋，ｌｅｍｍａ：？＋ｅｄ，ｃａｔ＝ｐａｓｔｐａｒｔｉｃｉｐｌｅ］  （３）
ここで、「ｌｅｍｍｅ：ｈａｖｅ」は、助動詞「ｈａｖｅ」の様々な形式を識別する。二次元書き換え規則（３）を用いることで、次の３つの言語処理タスクが同時に達成される。（ｉ）「‐ｅｄ」で終わる単語を過去分詞として識別する。（ｉｉ）「‐ｅｄ」で終わる単語を「ｐａｓｔｐａｒｔｉｃｉｐｌｅ（過去分詞）」として分類する。（ｉｉｉ）より低レベルの構成素を連結することで、より高レベルの構成素を構成する。
【００３１】
上述の背景技術に記載したように、二次元書き換え規則（３）の機能を、二次元書き換え規則を用いずに拡張文脈自由文法を用いる構文処理によって達成することもできる。しかしながら、二次元書き換え規則を用いずに、同等な処理を実行すると、構文レベルを再帰的に２回通る必要がある。それに対して、二次元書き換え規則（３）は、構文レベルを１回通るだけで、曖昧性解消と、より高レベルの構成素の生成との両方を、同時に達成する。
【００３２】
図４を参照すると、文字パタン認識規則「ｌｅｍｍｅ：ｈａｖｅ」は、オートマトンによって適切に実現される。図４に示すオートマトンは、第１のトークンの文字に対して左から右へ作用し、助動詞の「ｈａｖｅ」、「ｈａｄ」、及び「ｈａｓ」の形式すべてを識別する。「ｌｅｍｍａ：？＋ｅｄ」作用は、図３Ａのオートマトンにおいて、「ｃ」とラベル付けされた矢印を「ｄ」とラベル付けされた矢印に置き換え、「ｉ」とラベル付けされた矢印を「ｅ」とラベル付けされた矢印に置き換え、第２のトークンの文字に対して右から左に作用させることによって適切に実現される。
【００３３】
さらに他の例において、二次元書き換え規則は、より高レベルの句を構成する構成素の低レベル特性によって制御される構文構成を達成するために利用できる。例えば、自然言語処理部は、テキスト中の、その主語に補題「ｐｒｉｎｔｅｒ」（表層形式は、単数形であっても、複数形であってもよい）を含む全ての文を解析することに利用できる。以下の二次元規則は、文構造を構成し、同時に、能動的な形式（active form）の動詞部（ＶＰ）の前にくる名詞部（ＮＰ）に補題「ｐｒｉｎｔｅｒ」が現れることを検査する。
Ｓ→ＮＰ［ｌｅｍｍａ：？*ｐｒｉｎｔｅｒ？*］，ＶＰ［ａｃｔｉｖｅ＿ｆｏｒｍ：＋］  （４）
二次元書き換え規則（４）は、文字レベル及び句レベルの両方で作用し、正規表現を用いてＮＰを構成する文字列の特徴を調べる。「ｌｅｍｍａ：？*ｐｒｉｎｔｅｒ？*」の操作は、次のようにＮＰに適用される。ＮＰを構成する、順に並んだトークン列の文字が連結され、この連結された文字列に対して補題が適用され、連結されたＮＰ文字列中のいずれかの位置にある下位文字列「ｐｒｉｎｔｅｒ」を識別する。同様に、より高レベルの構成素の表層形式は、このより高レベルの構成素と関連付けられたノード（node）で処理されるテキスト中に発見された正確な文字列を照合することによって実現される。
【００３４】
前述の、二次元書き換え規則の例（１）から（４）は、例示である。以上の二次元書き換え規則の例は、実体型の関連付け、多単語用語の認識、文脈上の推測、同時のフィルタリング及び構文解析タスク、を実行する。一方で、二次元書き換え規則を利用することで、多くの他の言語処理タスクが、実行可能になる又はより効率的に実行されることが理解されるだろう。
【００３５】
ここに記載する、二次元書き換え規則を利用した解析は、実質的にすべての適切な自然言語処理プラットフォームを用いて、実現できる。一般的に、記憶媒体が、デジタルプロセッサで実行された場合に、言語処理に用いる１以上の二次元書き換え規則を実現する命令を記憶する。デジタルプロセッサは、例えば、デスクトップコンピュータ、ラップトップコンピュータ、ネットワークサーバ、インターネットを通じてアクセスされるリモートコンピュータ、携帯電話のマイクロプロセッサ、個人用携帯情報端末（personal data assistant、PDA）のマイクロプロセッサ、携帯用電子言語翻訳機のマイクロプロセッサ、又はメインフレームコンピュータのいずれであってもよい。記憶媒体は、例えば、磁気ディスクや光学ディスクであってもよい。いくつかの実施形態において、命令は、インターネット又は他のネットワークからダウンロードされる。この場合、記憶媒体は、揮発性のランダムアクセスメモリ（ＲＡＭ）、又は、命令を一時的に記憶する他の記憶媒体とみなすことができる。二次元書き換え規則は、トップダウン、若しくはボトムアップの解析パイプライン（pipeline）、又は、トップダウン、及びボトムアップ解析の何らかの組み合わせを利用するパーザにおいて、用いることができる。
【００３６】
いくつかの実施形態においては、適切な場合に、二次元書き換え規則を用いた解析を実行するために、ゼロックス・インクリメンタル・パーザ（Xerox Incremental Parser、ＸＩＰ）を適応させる。ＸＩＰプラットフォームは、順に続く、トークン化／形態素解析、曖昧性解消、及びチャンキング層を利用し、処理の始めから終わりまで、言語情報を表す単一のデータ構造を用いて、再帰的処理なしで、決定論的なボトムアップ解析パイプラインを実現する。ＸＩＰパーザに関連する、追加の背景は、サラ・アイト‐モクター（Salah Ait‐Mokhtar）、ジャン‐ピエール・シャノ（Jean‐Pierre Chanod）、「漸進的有限状態解析（Incremental finite‐state parsing）」、応用自然言語処理学会予稿集（Proceedings of Applied Natural Language Processing）、（米国）、１９９７年４月；及び、米国特許出願公開第２００３／００７４１８７号明細書；に記載され、これらの文献を参照によってここに援用する。
【００３７】
二次元書き換え規則の仕組みは、表層形式、又は補題のような、詳細な情報へのアクセスをパーザに提供するために実現される。入力文字列中の、表層形式、又は補題と一致する正規表現を、より高レベルの構成素の生成と同時に適用することができる。従って、正規表現は、構文規則の適用に制約を加える。その仕組みは、前終端記号カテゴリ（例えば、名詞、動詞など）、及び非終端記号カテゴリ（例えば、名詞部（ＮＰ）、動詞部（ＶＰ）など）に、正規表現を適用することを含む。表層形式、又は補題を非終端記号カテゴリに適用する一つの適切な方法においては、処理されて非終端記号カテゴリに関連付けられた文字列は、下位構成素と関連付けられたすべての下位文字列の結合である。また、例えば、非終端記号カテゴリに含まれる各トークンに補題を適用し、その結果を論理演算「ＯＲ」によって選言的に結合するような、他の方法を用いることもできる。
【００３８】
二次元書き換え規則を含むようにＸＩＰを適応させる一つの方法においては、パーザは、各二次元書き換え規則を指定されたオートマトンとしてコンパイルする。ここで、オートマトンの状態は、カテゴリの名称、及び複合素性構造の組み合わせである。表層形式及び補題上の正規表現もまた、文字ベースのオートマトンとしてコンパイルされ、二次元書き換え規則の文字パタン認識規則コンポーネントを実現する。ＸＩＰの素性妥当性チェックは、与えられた語彙又は構文ノードの、表層形式又は補題に対して、文字ベースのオートマトンを適用するように、適切に適応させられる。文字ベースのオートマトンの適用は、決定論的であり、最短の照合に従って実行される。この例においてＸＩＰを適応すると、任意の個数の素性を宣言することができる。入力から語彙ノードが生成される時、表層形式及び補題は、実行時において文字列を入力として受け取る。二次元書き換え規則がこれらの文字パタン認識素性のうちの１つを含む場合、パーザはコンパイル時においてそれを認識し、そのテストを文字ベースのオートマトン、例えば、図２Ａ、図２Ｂ、図３Ａ、図３Ｂ、及び図４に例示するオートマトンに翻訳する。これらのテストのそれぞれをオートマトンに翻訳することで、システムは複雑な正規表現を効率的に処理することができる。二次元書き換え規則の右辺は、構文カテゴリに関係するオートマトンとして実現でき、一方、二次元書き換え規則の文字パタン認識コンポーネントは、文字列に関係するオートマトンとして実現される。正規表現の実現は、これらの表現を実現する方法の一例である。しかしながら、他の実現方法を利用することもできる。さらに、ＸＩＰエンジンを利用する実施形態を、例として記載したが、実質的にどのような言語パーザでも、適切なオートマトン、又は他のコンピュータ上の実現を用いた、ここに記載するような二次元書き換え規則を容易に組み込むことができることを理解されたい。
【図面の簡単な説明】
【００３９】
【図１】自然言語処理システムの一例を示すブロック図である。
【図２Ａ】本発明による二次元書き換え規則の例に組み込まれた文字パタン認識規則を実現するのに適した、文字ベースのオートマトンの一例を示す図である。
【図２Ｂ】本発明による二次元書き換え規則の例に組み込まれた文字パタン認識規則を実現するのに適した、文字ベースのオートマトンの一例を示す図である。
【図３Ａ】本発明による二次元書き換え規則の例に組み込まれた文字パタン認識規則を実現するのに適した、文字ベースのオートマトンの一例を示す図である。
【図３Ｂ】本発明による二次元書き換え規則の例に組み込まれた文字パタン認識規則を実現するのに適した、文字ベースのオートマトンの一例を示す図である。
【図４】本発明による二次元書き換え規則の例に組み込まれた文字パタン認識規則を実現するのに適した、文字ベースのオートマトンの一例を示す図である。
【符号の説明】
【００４０】
１０  パーザ、１２  自然言語テキスト、１４  トークン化モジュール、１６  辞書、２０  構文処理部、２２  曖昧性解消モジュール、２４  チャンキングモジュール、２６  文脈自由文法、３０  二次元書き換え規則、３４  意味処理モジュール。
【図１】
2006178980.tif 000003
【図２Ａ】
2006178980.tif 000004
【図２Ｂ】
2006178980.tif 000005
【図３Ａ】
2006178980.tif 000006
【図３Ｂ】
2006178980.tif 000007
【図４】
2006178980.tif 000008