(57)【特許請求の範囲】
【請求項１】
機械翻訳用の複数の翻訳規則を生成するトレーニング段階であって、
メモリに記憶されたストリングベースのトレーニング情報のコーパスを受領手段によって受け取るサブステップであって、前記コーパスはソース言語でのストリング、ターゲット言語での対応するストリングについての構文解析ツリーであるターゲット・ツリーおよびソース言語でのストリングであるソース・ストリングのシンボルとターゲット言語でのストリングであるターゲット・ストリングの対応するシンボルの間のアラインメントを含む、サブステップと、
アラインメント・グラフ形成手段によって、ターゲット・ツリーに基づき、さらに該ターゲット・ツリーに対応するソース・ストリングの要素を表すノードおよびソース・シンボルとターゲット・シンボルの間のアラインメントを表すエッジを含むアラインメント・グラフを形成するサブステップと、
前記アラインメント・グラフから翻訳規則を推定するサブステップであって、該推定は：
前記アラインメント・グラフの各ノードについて、そのノードのスパンとそのノードの補スパンの和集合を計算して前記アラインメント・グラフのフロンティア集合を決定し；
前記フロンティア集合の各ノードを拡張し、前記拡張内にシンク・ノードがあるかどうかを判定し、ノードの拡張またはシンク・ノードの拡張から生じる各シンク・ノードを拡張して、フロンティア集合の各ノードに根をもつ極小フロンティア・グラフ・フラグメントを計算し；
前記極小フロンティア・グラフ・フラグメントの二つ以上から合成されることのできるグラフ・フラグメントの集合を計算することによって実行され、
推定される翻訳規則の入力は前記グラフ・フラグメントのシンクに対応し、前記翻訳規則の出力は、前記フラグメントのツリー部分のシンクを変数で置き換えたものに対応する、サブステップと、
生成された翻訳規則をメモリに記憶するサブステップとを含み、
前記翻訳規則は該翻訳規則の諸部分としてツリーの諸部分を含むようなトレーニング段階と；
翻訳手段によって、前記メモリに記憶された前記翻訳規則を使用して、ソース言語でのストリングからターゲット言語でのターゲット・ツリーへの翻訳を実行する翻訳段階、
とを有する方法。
【請求項２】
前記翻訳規則が該翻訳規則の確率に関連付けられている、請求項１記載の方法。
【請求項３】
翻訳されるべきストリングを受領手段によって受け取る段階をさらに含み、
前記翻訳段階が；
適用手段によって、前記複数の翻訳規則を翻訳されるべき前記ストリングに適用して、該ストリングの可能な翻訳を表す複数の異なるターゲット・ツリーを得る段階と、
判別手段によって、それらのターゲット・ツリーのどれが最も確からしい翻訳を表しているかを、前記翻訳規則に関連付けられた確率に従って判別する段階とをさらに含む、請求項２記載の方法。
【請求項４】
前記トレーニング段階がパラメータ推定技法を使用する、請求項２記載の方法。
【請求項５】
前記トレーニング段階が期待値最大化技法を使用する、請求項４記載の方法。
【請求項６】
一つまたは複数のソース語と一つまたは複数のターゲット語の間の交差を解決するために、ソース・ストリングの句内の語の並べ替えを可能にするためにツリーの一つまたは複数の部分ツリーを平坦化手段によって平坦化することをさらに有する、請求項２記載の方法。
【請求項７】
請求項１ないし６のうちいずれか一項記載の方法であって、前記トレーニング段階が、所与のソース・ストリングから、所与のターゲット・ツリーをアラインメントに基づいて導出する導出ステップの集合を集成することを含み、前記導出ステップの集合は、前記ソース・ストリングにおける語が置き換えられる少なくとも一つの導出ステップおよびターゲット語が生成される少なくとも一つの導出ステップを含む、方法。
【請求項８】
前記トレーニング段階が、前記導出の集合の少なくとも一つの導出から誘導されたアラインメントを決定することを含み、前記少なくとも一つの誘導されたアラインメントは、ターゲット語が、前記ソース・ストリングにおける語が置き換えられるのと同じ導出ステップにおいて生成されたのであれば、前記ソース・ストリングにおける単語と関連付けられる該ターゲット語を含む、請求項７記載の方法。
【請求項９】
前記ツリー内の要素の少なくともいくつかが、他のツリーによって内容が定義される変数である、請求項７または８記載の方法。
【請求項１０】
前記フラグメントが前記アラインメント・グラフの非自明な部分グラフを含む、請求項１ないし９のうちいずれか一項記載の方法。
【請求項１１】
前記部分グラフは、あるノードnが前記部分グラフ内にあれば、該ノードnが前記部分グラフのシンク・ノードであるか、該ノードnの子が全部前記部分グラフ内にありかつ該ノードの全部に接続されているようなものである、請求項１０記載の方法。
【請求項１２】
前記集合の各導出から誘導されたアラインメントと前記コーパスに含まれるアラインメントとの関係に基づいて、前記集合に含まれる導出のうち認められる導出が決定される、請求項８記載の方法。
【請求項１３】
翻訳規則を推定する前記サブステップが、ソース言語の部分ストリングをターゲット・ツリーの部分ツリーに変換する翻訳規則を、該部分ストリングから該部分ツリーを導出するために必要とされる置き換えに基づいて形成することを含む、請求項１ないし１２のうちいずれか一項記載の方法。
【請求項１４】
前記規則の出力が記号ツリーであり、その葉の少なくとも一部はターゲットアルファベットからの記号ではなく変数でラベル付けされている、請求項１３記載の方法。
【請求項１５】
規則の集合を形成できる最小の情報の集合を決定手段によって決定する段階をさらに含み、前記最小の情報の集合がフロンティア情報を含む、請求項１ないし１２のうちいずれか一項記載の方法。
【請求項１６】
前記アラインメント・グラフの極小フロンティア・グラフ・フラグメントを決定手段によって決定する段階をさらに含み、
前記アラインメント・グラフのフラグメントを規則に変換する段階が、前記極小フロンティア・グラフ・フラグメントを規則に変換することを含む、請求項１ないし１２のうちいずれか一項記載の方法。
【請求項１７】
前記複数の翻訳規則を適用する処理が、個々の語を見出し、まず前記個々の語に適用される規則を見出し、次いで前記個々の語の組み合わせを見出し、前記個々の語の組み合わせに適用される規則を見出すことを含む、請求項３記載の方法。
【請求項１８】
前記複数の翻訳規則を適用する処理が、nグラム言語モデルおよび統語ベースの言語モデルの両方を使うことを含む、請求項３記載の方法。
【請求項１９】
前記規則の入力をなす前記フラグメントのシンクが、前記コーパスに含まれるソース言語でのストリングにおける順序に並べられる、請求項１ないし１８のうちいずれか一項記載の方法。
【請求項２０】
前記トレーニング段階が、対応する要素の対から翻訳規則を生成することを含み、
前記対応する要素の対が、ターゲット言語におけるツリーおよびソース言語におけるストリングを含む対として与えられる、
請求項１記載の方法。
【請求項２１】
第一の言語でのストリングおよび第二の言語での対応するストリングを含むストリングベースのトレーニング情報のコーパスに基づいて機械翻訳用の複数の翻訳規則を生成するトレーニング方法であって：
アラインメント手段によって、メモリに記憶されている前記第一の言語および第二の言語の情報の項目をアラインメントさせてアラインメントされた情報を形成し、該アラインメントされた情報をメモリに記憶する段階であって、少なくとも前記第一の言語の前記情報はツリーの形であるような段階と；
アラインメント・グラフ形成手段によって、ツリーの形である前記第一の言語の前記情報に基づき、さらに前記第二の言語の情報の項目を表すノードおよび前記アラインメントされた情報に基づく前記第一および第二の言語の情報の項目の間のアラインメントを表すエッジを含むアラインメント・グラフを形成する段階と；
抽出手段によって、前記アラインメント・グラフのフラグメントを、該フラグメントのシンクを入力とし、該フラグメントのツリー部分のシンクを変数で置き換えたものを出力とする規則に変換することによって、規則を抽出する段階と、
前記規則をメモリに記憶する段階
とを有しており、
前記アラインメント・グラフのフラグメントは：
前記アラインメント・グラフの各ノードについて、そのノードのスパンとそのノードの補スパンの和集合を計算して前記アラインメント・グラフのフロンティア集合を決定し；
前記フロンティア集合の各ノードを拡張し、前記拡張内にシンク・ノードがあるかどうかを判定し、ノードの拡張またはシンク・ノードの拡張から生じる各シンク・ノードを拡張して、フロンティア集合の各ノードに根をもつ極小フロンティア・グラフ・フラグメントを計算し；
前記極小フロンティア・グラフ・フラグメントの二つ以上から合成されることのできるグラフ・フラグメントの集合を計算することによって得られる、
方法。
【請求項２２】
前記第一の言語および前記第二の言語の両方の前記情報が前記ツリーの形である、請求項２１記載の方法。
【請求項２３】
前記整列グラフから規則を抽出する前記段階が、前記整列グラフのフラグメントを規則に変換することを含む、請求項２１記載の方法。
【請求項２４】
前記規則を抽出する前記段階に先立ち、縮小集合形成手段によって、前記アラインメント・グラフのフラグメントの縮小された集合を形成する段階をさらに有し、
前記アラインメント・グラフから規則を抽出する前記段階が、前記アラインメント・グラフのフラグメントの前記縮小された集合から規則を抽出することを含む、
請求項２３記載の方法。
【請求項２５】
ターゲット言語に翻訳されるべきソース言語のストリングを取得手段によって取得する段階と；
生成手段によって、アラインメント・グラフを、
ソース言語でのストリング、
所与のソース・ストリングに対応するターゲット言語でのストリングについての構文解析ツリーであるターゲット・ツリーおよび
ソース言語でのストリングとターゲット・ツリーとの一つまたは複数のアラインメントから生成する段階であって、少なくとも前記ターゲット言語についての前記ストリングは少なくとも部分ツリーの諸部分を含み、部分ツリーはターゲット言語での情報項目の統語ツリーの一部である、段階と；
推定手段によって、前記アラインメント・グラフから翻訳規則を推定する段階であって、該推定は：
前記アラインメント・グラフの各ノードについて、そのノードのスパンとそのノードの補スパンの和集合を計算して前記アラインメント・グラフのフロンティア集合を決定し；
前記フロンティア集合の各ノードを拡張し、前記拡張内にシンク・ノードがあるかどうかを判定し、ノードの拡張またはシンク・ノードの拡張から生じる各シンク・ノードを拡張して、フロンティア集合の各ノードに根をもつ極小フロンティア・グラフ・フラグメントを計算し；
前記極小フロンティア・グラフ・フラグメントの二つ以上から合成されることのできるグラフ・フラグメントの集合を計算することによって実行され、
推定される翻訳規則の入力は前記グラフ・フラグメントのシンクに対応し、前記翻訳規則の出力は、前記フラグメントのツリー部分のシンクを変数で置き換えたものに対応する、段階と；
翻訳手段によって、
前記翻訳規則を含む少なくとも一つの規則集合、
確率、
少なくともnグラム言語モデルおよび
統語ベースの言語モデル
を使って、前記ストリングを前記ターゲット言語に翻訳する段階、
とを有する方法。
【請求項２６】
前記翻訳する段階が、まず個々の語に規則を適用し、次いで語の組み合わせに規則を適用することを含む、請求項２５記載の方法。
【請求項２７】
出力手段によって、ターゲット言語についての統語ツリーを翻訳として出力する段階をさらに有する、請求項２５記載の方法。
【請求項２８】
前記翻訳手段は複数の異なるツリーを可能な翻訳として生成し、最高確率に従って最良のツリーを選択する、請求項２７記載の方法。
【請求項２９】
メモリと；
複数の翻訳規則を生成するトレーニング部であって、
ストリングベースのトレーニング情報のコーパスを入力インターフェースを介して受け取る段階であって、前記コーパスはソース言語でのストリング、ターゲット言語での対応するストリングについての構文解析ツリーであるターゲット・ツリーおよびソース言語でのストリングであるソース・ストリングのシンボルとターゲット言語でのストリングであるターゲット・ストリングの対応するシンボルの間のアラインメントを含む、段階と、
ターゲット・ツリーに基づき、さらに該ターゲット・ツリーに対応するソース・ストリングの要素を表すノードおよびソース・シンボルとターゲット・シンボルの間のアラインメントを表すエッジを含むアラインメント・グラフを形成する段階と、
前記アラインメント・グラフから翻訳規則を推定する段階であって、該推定は：
前記アラインメント・グラフの各ノードについて、そのノードのスパンとそのノードの補スパンの和集合を計算して前記アラインメント・グラフのフロンティア集合を決定し；
前記フロンティア集合の各ノードを拡張し、前記拡張内にシンク・ノードがあるかどうかを判定し、ノードの拡張またはシンク・ノードの拡張から生じる各シンク・ノードを拡張して、フロンティア集合の各ノードに根をもつ極小フロンティア・グラフ・フラグメントを計算し；
前記極小フロンティア・グラフ・フラグメントの二つ以上から合成されることのできるグラフ・フラグメントの集合を計算することによって実行され、
推定される翻訳規則の入力は前記グラフ・フラグメントのシンクに対応し、前記翻訳規則の出力は、前記フラグメントのツリー部分のシンクを変数で置き換えたものに対応する、段階と、
生成された翻訳規則をメモリに記憶する段階とを行うよう構成されており、
前記翻訳規則は該翻訳規則の構成要素としてツリーの諸部分を含むようなトレーニング部と、
前記メモリに記憶された前記翻訳規則を使用して、ソース言語でのストリングからターゲット言語でのターゲット・ツリーへの翻訳を実行するよう構成された規則適用部、
とを有するシステム。
【請求項３０】
前記メモリがさらに前記規則の確率を保存する、請求項２９記載のシステム。
【請求項３１】
前記規則適用部が、
入力インターフェースを介して、翻訳されるべきストリングを受け取り、
前記複数の翻訳規則を翻訳されるべき前記ストリングに適用して、該ストリングの可能な翻訳を表す複数の異なるツリーを得、
それらの異なるツリーのどれが最も確からしい翻訳を表しているかを、前記規則の確立に従って判別するよう動作する、請求項３０記載のシステム。
【請求項３２】
前記アラインメント・グラフから翻訳規則を推定する処理が、前記アラインメント・グラフのフラグメントを規則に変換することを含む、請求項２９記載のシステム。
【請求項３３】
翻訳規則を推定する処理が、ソース言語の部分ストリングをターゲット・ツリーの部分ツリーに変換する翻訳規則を、該部分ストリングから該部分ツリーを導出するために必要とされる置き換えに基づいて形成することを含む、請求項２９ないし３２のうちいずれか一項記載のシステム。
【請求項３４】
前記アラインメント・グラフの極小フロンティア・グラフ・フラグメントを決定するために前記アラインメント・グラフが解析され、
前記アラインメント・グラフのフラグメントを翻訳規則に変換する前記処理が、前記極小フロンティア・グラフ・フラグメントを規則に変換することを含む、
請求項３２記載のシステム。
【請求項３５】
前記規則適用部が、nグラム言語モデルおよび統語ベースの言語モデルの両方を使用する、請求項３１記載のシステム。
【請求項３６】
第一の言語でのストリングおよび第二の言語での対応するストリングを含むストリングベースのトレーニング情報のコーパスに基づいて機械翻訳用の複数の翻訳規則を生成するトレーニング・システムであって、トレーニング部を有しており、前記トレーニング部は：
前記第一の言語および第二の言語の情報の項目をアラインメントさせてアラインメントされた情報を形成し、少なくとも前記第一の言語の前記情報はツリーの形であり、
アラインメント・グラフ形成手段によって、ツリーの形である前記第一の言語の前記情報に基づき、さらに前記第二の言語の情報の項目を表すノードおよび前記アラインメントされた情報に基づく前記第一および第二の言語の情報の項目の間のアラインメントを表すエッジを含むアラインメント・グラフを形成し、
前記アラインメント・グラフのフラグメントを、該フラグメントのシンクを入力とし、該フラグメントのツリー部分のシンクを変数で置き換えたものを出力とする規則に変換することによって、規則を抽出するよう構成されており、
前記アラインメント・グラフのフラグメントは：
前記アラインメント・グラフの各ノードについて、そのノードのスパンとそのノードの補スパンの和集合を計算して前記アラインメント・グラフのフロンティア集合を決定し；
前記フロンティア集合の各ノードを拡張し、前記拡張内にシンク・ノードがあるかどうかを判定し、ノードの拡張またはシンク・ノードの拡張から生じる各シンク・ノードを拡張して、フロンティア集合の各ノードに根をもつ極小フロンティア・グラフ・フラグメントを計算し；
前記極小フロンティア・グラフ・フラグメントの二つ以上から合成されることのできるグラフ・フラグメントの集合を計算することによって得られる、
システム。
【請求項３７】
前記第一の言語および前記第二の言語の両方の前記情報が前記ツリーの形である、請求項３６記載のシステム。
【請求項３８】
前記規則を抽出する前記段階に先立ち、前記アラインメント・グラフのフラグメントの縮小された集合を形成する段階をさらに有し、
前記アラインメント・グラフから規則を抽出する前記段階が、前記アラインメント・グラフのフラグメントの前記縮小された集合から規則を抽出する、
請求項３６記載のシステム。
【請求項３９】
少なくとも一つの規則集合を保存するメモリを有するシステムであって、前記メモリは、前記少なくとも一つの規則集合は、アラインメント・グラフから推定された翻訳規則を含み、また確率を含み、
当該システムはさらに、
前記アラインメント・グラフを、
ソース・ストリング、
所与のソース・ストリングに対応するターゲット言語でのストリングについての構文解析ツリーであるターゲット・ツリーおよび
ソース言語でのストリングのターゲット・ツリーとの一つまたは複数のアラインメントから生成する手段であって、少なくとも前記ターゲット言語についての前記ストリングは少なくとも部分ツリーの諸部分を含み、部分ツリーはターゲット言語での情報項目の統語ツリーの一部である、手段と、
前記アラインメント・グラフから翻訳規則を推定する推定手段であって、該推定は：
前記アラインメント・グラフの各ノードについて、そのノードのスパンとそのノードの補スパンの和集合を計算して前記アラインメント・グラフのフロンティア集合を決定し；
前記フロンティア集合の各ノードを拡張し、前記拡張内にシンク・ノードがあるかどうかを判定し、ノードの拡張またはシンク・ノードの拡張から生じる各シンク・ノードを拡張して、フロンティア集合の各ノードに根をもつ極小フロンティア・グラフ・フラグメントを計算し；
前記極小フロンティア・グラフ・フラグメントの二つ以上から合成されることのできるグラフ・フラグメントの集合を計算することによって実行され、
推定される翻訳規則の入力は前記グラフ・フラグメントのシンクに対応し、前記翻訳規則の出力は、前記フラグメントのツリー部分のシンクを変数で置き換えたものに対応する、手段と；
ターゲット言語に翻訳されるべきソース言語のストリングを取得し、前記メモリから前記少なくとも一つの規則集合を受け取って、
該少なくとも一つの規則集合、
確率、
少なくともnグラム言語モデルおよび
統語ベースの言語モデル
を使って前記ストリングを前記ターゲット言語に翻訳する復号部、
とを有する、
システム。
【請求項４０】
前記復号部がまず個々の語に規則を適用し、次いで語の組み合わせに規則を適用する、請求項３９記載のシステム。
【請求項４１】
前記復号部が翻訳としてターゲット言語についての統語ツリーを出力する、請求項３９記載のシステム。
【請求項４２】
前記復号部が可能な翻訳として複数の異なるツリーを生成し、最高確率に基づいて最良のツリーを選択する、請求項４１記載のシステム。
【発明の詳細な説明】
【技術分野】
【０００１】
〈優先権の主張〉
本出願は米国特許法第１１９条（ｅ）のもとに、2004年10月12日に出願された米国特許出願第60/618,244号および60/618,366号の優先権を主張するものであり、前記文献の内容全体はここに参照によって組み込まれる。
【背景技術】
【０００２】
モダンな機械翻訳システムは語から語および句から句への確率的なチャネルモデルを、nグラム（n-gram）言語モデルとともに使用する。
【０００３】
機械翻訳を使って翻訳する従来式の方法が図１に示されている。図１は、原語対として中国語と英語の概念を示しているが、代替的に他のいかなる原語対を用いてもよいことは理解されるはずである。
【０００４】
トレーニングは１５０として示されている。ここではトレーニングコーパス１５３が使用される。コーパスは英語ストリング１５１および中国語ストリング１５２を含んでいる。単語レベルでトレーニングコーパスにおいて単語を整列させるのには既存の技術が使用されうる。復号モジュール１６７が使用されるが、これは、eおよびfをトレーニングコーパスにおける語または句として、コーパス内のある言語が与えられたときに、引数argmax/e  P(e)×P(f|e)を最大化し、eの確率を最大化するものである。復号モジュール１６７は単にトレーニングモジュールと同じユニット内のモジュールであってもよい。よって復号器は、１６０のような新たな中国語ストリングが与えられて、言語モデル１６１とともに確率１６０を使用する。言語モデルはnグラム言語モデルであってもよい。復号器は、前記の確率および言語モデルに基づいて最も高いスコアに対応する英語ストリングを出力する。
【０００５】
句に基づくシステムは時に最も精確な翻訳を生じるが、そうしたシステムはしばしば、ソース言語〔起点言語〕の文をターゲット言語〔目標言語〕に翻訳するときに、長距離の構成素並べ替えを奨励するには弱すぎるので、グローバルに文法的な出力のための制御はしない。
【０００６】
他のシステムはこれらの問題をシンタックスを使って解決しようと試みることがある。たとえば、ある種の言語対におけるある種の並べ替えが実行されうる。ある研究によれば、たとえ英語／フランス語のような類似の言語対についてであっても、普通に見られる多くの翻訳パターンがYamada  &  Knightの子並べ替えモデル（Child  reordering  model）の範囲外になることが示されている。これは異なる可能な代替に導いた。ある提案は、当該データに対してはシンタックスはよく当てはまらなかったという理由でシンタックスを放棄することであった。別の可能性は、代替的な翻訳モデルを調査する間は有効な英語のシンタックスを維持することである。
【発明の開示】
【課題を解決するための手段】
【０００７】
本出願は、ストリングから生成されたツリーを使って統計的解析を実行することを記載する。トレーニングにおいては、ツリーが生成されて、確率に加えて規則を形成するために使用される。適用においては、ツリーは出力として使用され、ツリーまたはツリーから導出された情報のいずれかが出力される。システムがソース記号のストリングを入力してターゲットのツリーを出力するのでもよい。
【０００８】
ある実施形態では、ツリー構造のより大きなフラグメントに対する条件を与える変換規則が生成される。これらの規則は、そのような規則の大きなセットを形成するために、手動で生成されることも、あるいはコーパス解析を通じて自動的に生成されることもできる。アルゴリズムが所与のデータのよりよい説明およびよりよい規則を生成する動機を与えるために、交差（crossing）および発散（divergence）の特定の場合を使ってもよい。
【０００９】
本記述は、ストリングからツリーへの翻訳を記述する。ストリングとシンタックス・ツリーとの間の直接翻訳を可能にする諸側面が記載される。
【００１０】
これらのことを含む諸側面について、これから付属の図面を参照しつつ詳細に述べる。
【発明を実施するための最良の形態】
【００１１】
より一般的な目標を達成する種々の方法を実施するために使うことのできる一般的な構造および技術ならびにより特定的な実施形態がここでは記載される。
【００１２】
図２は、ある実施形態の全体的なブロック図を示している。ある実施形態では、テキストからテキストへの適用のための規則を学習するために、規則学習が使われる。規則学習およびテキストからテキストへの適用はそれぞれ図１０に示されるようなコンピュータ１０００上で実行されうる。図１０には、翻訳規則、確率および／またはモデルを保存する付属メモリ１００１も含まれている。ここで記載されるコンピュータは、ワークステーションなどいかなる種類のコンピュータであってもよく、汎用でも、何らかの個別目的用コンピュータでもよい。コンピュータはペンティアム（登録商標）クラスのコンピュータでウィンドウズ（登録商標）XPまたはリナックスを走らせているものであってもよく、あるいはマッキントッシュ（登録商標）コンピュータであってもよい。プログラムはC、Java（登録商標）または他のいかなるプログラミング言語で書かれてもよい。プログラムは、記憶媒体、たとえば磁気的または光学式、たとえばコンピュータ・ハード・ドライブ、リムーバブル・ディスクまたはその他のリムーバブル媒体に存在していてもよい。
【００１３】
この実施形態では、英語ストリング１５１および中国語ストリング１５２がまず整列装置２５１によって単語整列される。英語ストリングは、ここで記載されるように構文解析器２５０によって英語ストリングの内容を表す英語ツリー２５５に構文解析される。この英語ツリーが中国語ストリング１５２とともに、ストリングベースのトレーニングモジュール２６０によって使用される。翻訳モジュール２６０は２６５で示される確率を生成し、またトレーニングを示す２７０で示される部分ツリー（subtree）／部分ストリング（substring）規則を生成しもする。こうして、トレーニング装置は、確率をもった諸規則を生成し、それらの規則の少なくとも一部はツリーの形である。
【００１４】
規則および確率は、その後新たな中国語ストリング１６０を復号するために復号モジュール２６７によって使用される。復号モジュール２６７は複数の言語モデル、ここではnグラム言語モデル１６１およびまたシンタックスベースの言語モデル２６２も使う。復号器２６７の出力２８０は、前記諸規則に従って前記中国語ストリングの翻訳であるあらゆる可能な英語ツリーに対応する。スコアが最高の英語ツリーがユーザーに表示される。あるいはまた、それらのツリーに基づく情報が表示されてもよい。たとえば、それらのツリーに対応するストリング情報である。
【００１５】
本実施形態のいくつかの利点には、次のようなものが含まれる。規則内のツリーからの情報の使用により、種々の部分が何を表すかをモデルが学習することが許容されうる。たとえば、図１の機械翻訳システムは名詞が何であるかは全く知らないが、本実施形態はそれを翻訳の一環として学習することができる。さらに、図１のシステムによって生成されるのが句置換規則であるのに対して、本実施形態はツリー／ストリング規則を提供する。ツリーの使用により、言語モデル２６２に基づいたシンタックスの使用が可能になる。これは従来技術においては通常（conventional）ではない。
【００１６】
別の実施形態によれば、両方の言語でのトレーニング情報がトレーニングに先立って構文解析されてツリーにされてもよい。
【００１７】
ツリー出力は、よく形成された、たとえば動詞を正しい位置にもち、他の部分も正しい位置にもつ出力を生成する。さらに、ツリー／ストリング規則は、並べ替えがいつ有用でありうるかについての情報も捕捉する。ツリー／ストリング規則は、機能語をいつ使用し、いつ使用すべきでないかを制御する。しかし、ツリーストリング規則の多くは単純な語から句への置換であってもよい。
【００１８】
ここで、トレーニングについて図３〜図９を参照しつつ述べる。
【００１９】
図３ａは、フランス語の文（il  ne  va  pas）およびその英訳の構文解析ツリー３００を示している。構文解析ツリーは従来式の構文解析要素を含む。文S、名詞句（NP）、動詞句（VP）およびその他の従来式の文要素である。
【００２０】
ある実施形態が定義するのは、根付きターゲットツリーにマッピングされているソースアルファベットからのストリングを使って規則を決定することである。その根付きターゲットツリーのノードはターゲットアルファベットを用いてラベル付けされる。この命名法を維持するため、ソースアルファベットからの記号〔シンボル〕（symbol）は「ソース記号」と称され、ターゲットアルファベットからの記号は「ターゲット記号」と称される。記号ツリーは、アルファベットΔ上で根付き有向ツリーとして定義される。このアルファベットの諸ノードはそれぞれΔの記号でラベル付けされる。ある実施形態では、ソース信号のストリングからターゲット言語上で記号ツリーが導出されるプロセスが捕らえられる。導出されるべき記号ツリーは、ターゲット言語なので、ターゲットツリーと呼ばれる。このツリーの任意の部分ツリーはターゲット部分ツリーと呼ばれる。
【００２１】
導出系列Sは、諸要素の順序付きシーケンスとして導出される。ここで、各要素はソース記号またはターゲット部分ツリーである。
【００２２】
導出プロセスの形式的な定義は次のとおりである。導出系列Sが与えられると、導出ステップは、Sの部分ストリングS′を次の属性をもつターゲット部分ツリーTで置き換える：
１．S′内のいかなるターゲット部分ツリーもTの部分ツリーである。
２．S′内でないS内のいかなるターゲット部分ツリーもTとノードを共有しない。
３．ソース記号のストリングSからターゲットツリーTへの導出は、SからTを生成する導出ステップからなるシーケンスである。
【００２３】
図３ａの特定の例の整列を考えよう。図３Ｂは、フランス語のソースストリングからターゲットツリー３００の３つの異なる導出を示している。この３つの導出は２０１、２０２、２０３とラベル付けされている。これらの導出のそれぞれは、上記の定義の１ないし３と一貫している。
【００２４】
しかしながら、これらの導出を分析すれば、これらの導出のうち少なくとも一つは他よりもより「誤っている」ことが示される。たとえば第二の導出２０２において、語pasが英単語heで置き換えられているが、これは正しくない。
【００２５】
整列により、トレーニングシステムは、良い導出と悪い導出を区別することが許容される。SとTとの間の整列は、可能な導出を改良するために実行されうる。Sがソース記号のストリングであり、Tがターゲットツリーである場合、上記の定義は、Sの各要素が導出におけるちょうど一つのステップにおいて置き換えられ（replaced）、Tの各ノードは導出におけるちょうど一つのステップにおいて生成される（created）という結論に導く。こうして、s1の各要素sについて、導出Dのうちsが置き換えられるステップにおいて、replaced(s,D)と呼ばれるセットが生成される。このセットは、導出において、種々の部分がどこで置き換えられるかを追跡する。
【００２６】
２０１では、単語vaは導出の第２ステップで置き換えられている．
種々の導出のそれぞれは、いくつかの「ステップ」を含み、したがって各ステップはある種のことを行う。たとえば導出２０１は、ステップ２１０、２１１、２１２、２１３を含む。たとえば２０１では、フランス語の単語vaは導出の第２ステップ２１１で置き換えられる。こうして、記号法（notation）の形で、語が置き換えられたステップを示すファイルが生成されることができる。たとえば、ここで、
replaced(s,D)＝2
である。
【００２７】
同様にして、Tの各ノードtには、created(T,D)と呼ばれるファイルが定義されていることができ、これは導出Dのうちtが生成されるステップである。２０１では、導出の第３ステップ２１２の間にAUX（補助語）およびVP（動詞句）によってラベル付けされるノードが生成されている。よって、created(AUX,D)＝3であり、created(VP,D)＝3である。
【００２８】
ソース記号のストリングSとターゲット・ツリーTが与えられたとき、SおよびTに関する整列〔アラインメント〕（alignment）Aは、Tの葉とSの要素との間の関係を形成する。SとTとの間の導出Dが選択された場合、Dによって誘導される整列（the  alignment  induced  by  D）とはSの要素sをTの葉ノードtとを整列させることによって生成されるものであるが、要素sとtが整列されるのはreplaced(s,D)がcreated(T,D)に等しい場合でありかつその場合に限られる。換言すれば、ソース語がターゲット語に「整列される」のは、そのターゲット語がそのソース語が置き換えられたのと同じステップの間に生成されている場合である。
【００２９】
図３Ｃは整列を図示している。図１のツリー３０１は図３Ｂの導出２０１に対応する。同様にして、３０２は２０２に、３０３は２０３に対応する。導出を分析する規則が記述される。整列Aに従う「良好な」導出の集合というのは、AがA′の部分整列（subalignment）となるような整列A′を誘導する導出の集合にほかならない。ここでの用法では、部分整列という用語はA⊆A′ということを要求する。整列は単なる数学的関係なので、これは比較的簡単に決定できる。Aが２つの要素を整列させるのがA′もそれらの２つの要素を整列させる場合のみであるならば、語AがA′の部分整列である。これは図３Ｂおよび３Ｃから直感的に理解可能である。一見して正しいように思える二つの導出には導出２０１および２０３がある。これらは図３Ａで与えられた整列の上位整列（superalignment）になっている。明らかに誤っている導出２０２はそのような上位整列になっていない。
【００３０】
記号法の点から（Notationally）いえば、導出が整列Aによって認められるのは、その導出がAの上位整列を誘導する場合である。ソースストリングSとターゲットストリングTとの間の、整列Aによって認められる導出の集合は、δA(S,T)と表すことができる。
【００３１】
本質的には、各導出ステップは一つの規則と考え直すことができる。これは、δA(S,T)の任意の導出において使われる導出ステップの集合を集成することによって、システムは(S,T,A)から引き出せるあらゆる有意な規則を決定できる。各導出ステップは、この実施形態に従って使用可能な規則に変換される。その規則は、自動化されたトレーニング情報の形成のために使用されることができる。
【００３２】
導出２０１における導出ステップ２１２は、ソース記号neで始まる。そのあとにVBに根を持つターゲット部分ツリーが続き、そのあとに別のソース記号pasが続く。該導出のこれら３つの要素は、該導出によって、VPに根をもつターゲット部分ツリーで置き換えられる。それにより、ソース記号が破棄されてVBに根をもつ開始されるターゲット部分ツリーが含められる。
【００３３】
図４は、この置き換えプロセスがどのようにして規則によって捕えられるかを示している。左側の４０１は導出ステップを示している。ここでは要素が他の要素で置き換えられる。４０２は形成される誘導規則を示している。規則４０２への入力は、置き換えられようとしている導出系列中の要素の根を含む。ここで、記号についての根とは、その記号自身であると定義される。規則の出力は記号ツリーである。ツリーの葉のいくつかは、ターゲットアルファベットからの記号ではなく変数でラベル付けされていてもよい。記号ツリーにおける変数は、当該規則への入力の要素に対応する。たとえば、誘導されるツリーのｘ２とラベル付けされた葉は、この規則が適用されるとき、ｘ２は、入力の第二の要素であるVBに根をもつターゲット部分ツリーによって置き換えられるということを意味している。二つの誘導された規則４０３および４０４がそれぞれの導出から得られる。このように、この規則フォーマットはCFG規則の一般化でありうる。各導出ステップは、このようにして規則にマッピングするためにこのシステムを使うことができる。
【００３４】
よって、ソースストリングS、ターゲットストリングTおよび整列Aが与えられると、セットδA(S,T)が任意の導出D∈δA(S,T)内の規則の集合として定義できる。この規則の集合は、三つ組(S,T,A)から推定できる規則の集合である。
【００３５】
ある実施形態では、規則の集合δA(S,T)は、図５に示した型の特別な整列グラフを使って三つ組み(S,T,A)から学習できる。整列グラフ（alignment  graph）とは、三つ組(S,T,A)を根付きの有向の非環状グラフとして描くグラフである。図５は上から下に向かう向きで示されているが、これは代替的に非常に容易に上下さかさまにできることは理解されるはずである。ある実施形態では、整列グラフのある種のフラグメントがδA(S,T)の規則に変換される。有向の非環状グラフGのフラグメント（fragment）とは、ここでは、ノードAがG′内にある場合の非自明な部分グラフG′として定義される。ここで、非自明とは、そのグラフが単なる一つのノードよりも多くを有しているということを意味する。前記の部分グラフG′は、ノードnがG′内にあれば、nがG′のシンク・ノード（sink  node）（子のないノード）であるか、nの子が全部G′内にありかつそのノードの全部に接続されているようなものである。図６は、図５の整列グラフから形成されたグラフ・フラグメントを示している。
【００３６】
整列グラフのノードNのスパン（span）とは、Sのノードのうちnから到達可能なノードの部分集合をなす。スパンは、Sのある連続的な部分ストリング内のすべての要素を含んでいれば連続であると定義される。スパン（n）の閉包（closure）とは、スパン（n）の上位集合である最短の連続なスパンである。たとえば、(s2,s3,s5,s7)の閉包は(s2,s3,s4,s5,s6,s7)である。図５の整列グラフは、各ノードのスパンで注釈付けされている。各ノード、たとえば５００は、そのノードのスパンを表す注釈５０２をもっている。
【００３７】
一つの側面は、これらのグラフから、規則の集合を形成できる最小の情報の集合を決定することである。この側面によれば、まず、規則のより小さな諸部分が見出され、次いで諸規則が一緒にされてより大きな諸部分を形成する。かたまり（chunk）は種々の方法で定義できる――ある実施形態では、整列グラフ内のある種のフラグメントがフロンティア・グラフ・フラグメントと呼ばれる特別なフラグメントとして定義される。整列グラフのフロンティア集合とは、ノードnの集合であって、nに接続されているがnの祖先でも子孫でもない整列グラフの各ノードn′について、span(n′)∩closure(span(n))=0となるような集合を含む。図５のフロンティア集合はボールドイタリック体で示される。
【００３８】
整列グラフのフロンティア・グラフ・フラグメントは、根およびすべてのシンクがフロンティア集合内にあるグラフ・フラグメントである。フロンティア・グラフ・フラグメントは、そのフラグメントの諸シンクのスパンがそれぞれ連続であるという性質をもつ。これらのスパンは、やはり連続である根のスパンの分割をなす。スパンと根との間の変換プロセスは、次のようにして実行できる：
１）まず、シンクが分割によって定義される順に位置される。そのスパンが根のスパンの最初の部分であるようなシンクが最初にくる。これに続いて、そのスパンが根のスパンの第二の部分であるようなSeがくる。これが規則の入力をなす。
２）次に、フラグメントのシンクノードが、入力におけるそれらの位置に対応する変数で置き換えられる。次いで、フラグメントのツリー部分を取る。これはたとえばフラグメントをT上に投影することによる。これが規則の出力をなす。
【００３９】
図６は、ある種のグラフ・フラグメントおよび規則：それらのグラフ・フラグメントから生成される入力および出力の両方を示している。整列グラフと規則との間の変換に基づいて構築される規則は、ρA(S,T)と呼ばれる部分集合内にある。
【００４０】
ここでは、いくつかの規則抽出技術も記載される。
【００４１】
ある第一の実施形態では、ρA(S,T)の規則は、グラフ・フラグメントの空間を探索してフロンティア・グラフ・フラグメントを探すことによって、整列グラフから抽出される。しかし、この技術についての一つの考えられる問題は、グラフの全フラグメントからなる探索空間はグラフの大きさに対して指数関数的になるということである。よって、この手順は実行に比較的長い時間がかかることがある。この技法は、以下の単純さを用いることによって改良できる。
【００４２】
整列グラフのフロンティア集合は、グラフの大きさに対して線形な時間で識別できる。第二の単純さは、フロンティア集合の各ノードNについて、nに根をもつ一意的な極小フロンティア・グラフ・フラグメントがあるということである。フロンティア集合の定義により、フロンティア集合内でない任意のノードn′はn′に根をもつフロンティア・グラフ・フラグメントは持ち得ない。極小フラグメントの定義は、そのフロンティア・グラフ・フラグメントが、Se根をもつ他のすべてのフロンティア・グラフ・フラグメントの部分グラフであるということを要求する。
【００４３】
k個のノードをもつ整列グラフについては、極小フロンティア・グラフ・フラグメントは高々k個ある。
【００４４】
図７は、図５の整列グラフからの７つの極小フロンティア・グラフ・フラグメントを示している。他のフロンティア・グラフ・フラグメントのすべては二つ以上の極小グラフ・フラグメントを合成することによって生成できる。図８は、この方法でどのように他のフロンティア・グラフ・フラグメントが生成できるかを示している。
【００４５】
よって、フロンティア・グラフ・フラグメントの集合全体、そしてそれらのフラグメントから導出可能な全規則が、図９のフローチャートに従って系統的に計算できる。図９のフローチャートは、たとえば図１０のコンピュータシステム上で実行できる。９００において、各トレーニング対について極小フロンティア・グラフ・フラグメントの集合が計算される。より一般には、この演算において、いかなる情報の極小集合でもトレーニング集合として利用できる。
【００４６】
９１０では、極小グラフ・フラグメントを合成することから得られるグラフ・フラグメントの集合が計算される。これにより、主要な諸極小フロンティア・グラフ・フラグメントから導出される諸規則を、該諸フロンティア・グラフ・フラグメントから導出可能な規則のすべての基礎とみなすことが許容される。
【００４７】
９２０では実際に規則が導出される。これらの規則はすでに極小フラグメントから導出されている。これらの規則は、ツリーまたはそれらのツリーから導出される情報を含む。
【００４８】
９３０では、極小フラグメントからの規則が組み合わされて「合成された」規則を形成する。
【００４９】
こうして、規則の抽出は、任意の所与の整列グラフについて極小フロンティア・グラフ・フラグメントの集合を見出すタスクになる。
【００５０】
これは、その整列グラフのフロンティア集合を計算することによって実行される。フロンティア集合の各ノードについて、そのノードに根をもつ極小フロンティア・グラフ・フラグメントが決定される。フロンティア集合の計算は、その整列グラフを通じて１パスで計算される。各ノードとそのスパンとの、およびまたその補スパンとの和集合として計算される。補スパン（complement  span）は、その親の補スパンとそのすべてのきょうだいのスパンとの和集合である。ここで、きょうだいとは同じ親を共有するノードである。
【００５１】
ノードnがフロンティア集合内にあるのは、complement  span(n)∩closure(span(n))が0に等しい場合であり、その場合に限る。よって、補スパンは、nの祖先でも子孫でもないすべてのノードのスパンをほとんど要約している。このステップはグラフを通す処理は１回しか必要とせず、よって線形時間で走る。
【００５２】
前記ノードに根をもつ極小フロンティア・グラフ・フラグメントを計算する第二のステップも比較的ストレートである。フロンティア集合の各ノードnについて、nが拡張される（expanded）。結果として得られるグラフ・フラグメントに、フロンティア集合内でない何らかのシンクノードn′がある限り、n′も拡張する必要がある。こうして、フロンティア集合のノードに根をもつ極小グラフ・フラグメントを計算したのちには、整列グラフの全ノードは高々一度拡張されている。よって、この演算も線形時間で実行できる。
【００５３】
上記はある種の側面を単純化していた。たとえば、整列されない要素は無視されている。しかしながら、これらの整列されない要素を取り入れるプロセスは決定できる。このシステムは、整列されない単語を説明するためのあらゆる方法に対応するあらゆる導出を計算する。さらに、これらの技法は部分ストリングが単一のツリーではなくツリーの集合によって置き換えられる導出を含むこともできる。
【００５４】
これは、出力が単一の根をもつツリーであることを要求しない規則を許容することに対応する。この一般化は、補助語（auxiliary  word）doesの生成を導出のあとのほうまで遅らせるのではなく、vaをdoes  goにじかに翻訳するような言語現象を説明することを許容しうる。
【００５５】
上記はいくつかの観察をもって試験された。整列の品質はこの導出において重要な役割を果たす。さらに、線形時間での実行に単純化される技法は、抽出（abstracts）の規則の大きさによっては余り影響されず、良好な効果を生じる。
【実施例】
【００５６】
図１１は、英語とフランス語との間の交差の一つの原因を同定している。これは他の言語対にも拡張できる。フランス語では副詞はしばしば動詞のあとに現れるが、これは英語ではそれほど一般的ではない。機械構文解析器は副詞が存在するときにはネストされた動詞句を生成する。このため、子並べ替えは、動詞および副詞が浸透されるべきことを許容することを妨げられる。図１１に示されるような多階層の並べ替えはこれらの種類の交差を防止または減らすことができる。
【００５７】
最初Foxによって提案された一つの解決策は、動詞句を平坦化することでありうる。これは、この文の対については解決策をなす。副詞‐動詞並べ替えについても説明しうる。ツリー構造の平坦化は、非常に限られた数のシンタックス範疇にしか適用できないので、必ずしも一般的な解決策ではない。しかし、時にはツリー構造の平坦化はノード並べ替えモールにおける交差を解決しない。これらのモデルでは、いかにVPが平坦化されようと、MDとAUXとの間の交差は残る。
【００５８】
前記変換規則モデルは図１２で１２００として示されている語彙規則を生成する。この語彙規則は、交差を解決する唯一の方法として、will  beの-sera-への変換を許容する。
【００５９】
これらの技法は、ここで述べるように、復号のために使うこともできる。この実施例は、ソースの自然言語文からターゲットの自然言語文への自動翻訳を記載する。その際には、語から語の、句から句の、統語（シンタックス）的な、および意味論（セマンティクス）的な規則翻訳の、複雑な確率的モデルを使う。これはまた、確率的な単語的、統語的および意味論的な言語モデルを記載する。
【００６０】
この第二の実施例は、ストリングベースの情報から直接的にツリーを形成する。ここで、入力される情報は翻訳されるべき情報である。翻訳は、入力として与えられるソース言語文からいくつかのターゲット言語構文解析ツリーを自動的に導出することによって構築される。各ツリーは、確率的モデルどうしの間の重み付き組み合わせおよび言語特徴の追加的な集合によってスコアを与えられる。最大確率のツリーがターゲット言語への翻訳を提供することになる。
【００６１】
この実施例は、任意の種類の確率的チャネルまたはターゲット言語モデル：すなわち単語ベース、句ベース、統語ベースまたは意味ベースのものを使う統計的翻訳システムを開発することを可能にする言語横断的（cross-lingual）構文解析枠組みを定義する。
【００６２】
チャネルおよびターゲット言語モデルは、パラレルコーパスから、期待値最大化アルゴリズム（expectation  maximization  algorithm）のような伝統的なパラメータ推定技法を使って直接的にトレーニングできる。代替的に、モデルはシンタックスの知識を全く持たないモデルを使って整列された語整列または句整列されたコーパスから推定されることもできる。さらに、これは翻訳の可能性のより大きな集合を探査することを可能にする。
【００６３】
この実施例では、ターゲット言語構文解析ツリーは、ソース言語ストリングから直接的に生成される。あらゆるチャネル演算（operations）は、種々の種類の翻訳規則の一つとして具現される。これらの演算の一部は、語から語または句から句への翻訳規則のような語彙的なものであり、他の規則は統語的なものである。
【００６４】
表１は、データから自動的に学習された規則を示す。
【００６５】
【表１】
0005452868.tif 000002
表１
これらの翻訳規則はいくつかの異なる範疇にはいる。
【００６６】
語彙的単純規則は１〜７番のような規則である。これらは、ターゲット言語部分を支配する、１階層の統語的構成素をもつ。これらの規則は単語の種別、単語そのものおよび翻訳を含む。
【００６７】
語彙的複雑規則は８番のような規則である。ここでは、ターゲット言語部分を支配する、多階層の統語的構成素がある。
【００６８】
規則１０、１１、１６、１７は語彙的アンカー付き複雑規則である。これらの規則は、混合された入力の上にいかにしてターゲットの統語構造が構築されるべきかを説明する。混合された入力は、語彙的ソース言語項目および統語的構成素ターゲット言語構成素でありうる。たとえば、規則１６は中国語の小辞「的」が二つの統語的構成素x1  x0の間に生じる場合には、結果として得られるターゲット構文解析ツリーはNP:x0およびX1:VPをもつNPであることを言っている。換言すれば、この規則は言語間の統語的構成素のための順序情報を保存しているのである。
【００６９】
統語的単純規則は規則１３のような規則で、ターゲット統語構造の導出を可能にする。最後に、統語的複雑規則は多階層のターゲット統語構造の導出を可能にする。この技法は、ソース言語語彙項目およびターゲット言語統語成分もしくは構成素を参照する１１および１６のような言語横断的翻訳規則を使用できる。これらの規則の多くに含まれる特徴は、ストリングの形で書かれているが実際にはツリーベースの情報であることを注意しておく。たとえば、NP(DT(“the”),x0:...)はツリーベースの情報を表す。
【００７０】
図１３は、入力文についての統語的なツリーの形の導出を示している。この導出を上から下に通すことで、ターゲット文の生成が可能になる。導出における各ノードは明示的に、ターゲット言語において子らが通過を必要とする順序をエンコードしているからである。
【００７１】
復号は種々の階層に従って復号のクラスターを使って実行される。第一のステップでは、まず規則のそれぞれが句１３００内の個々の語に適用される。既存のソフトウェアによってすでに中国語の句１６０がその個々の語に分割されていることを注意しておく。１３０２のような各語は、何らかの規則がその語だけに当てはまるかどうかを判別するために設定された諸規則に対して評価される。たとえば、語１３０２は、その単一の語に適用される明示的な規則１３０４（規則１）がある。これが規則階層１、１３１０として示される規則の第一階層をなす。
【００７２】
階層２では、語の各対が解析される。たとえば、対１３０２、１３１２は規則１３１４によって解析される。同様に、対１３１２、１３１６が解析されて、何らかの規則がその対に適用されるかどうかが判別される。たとえば、規則１３１４は、語１３１２が次に続くいかなる語に対しても適用される。したがって、規則１３１４は語の対１３０２、１３１２に適用される。これらの二個複合語規則（dual  compound  rules）が階層２、１３２０をなす。同様に、階層３では三個組（triplets）が解析され、これに四個組などが続き、階層ｘとして示される最上階層規則が実行されるまで続けられる。
【００７３】
これらの規則のそれぞれは、その規則内のストリング部分のためにストリングを含んでいる。たとえば、規則１３はテキスト形式で書かれた特定のツリーの情報を示している。ツリー部分はツリー内変数を含んでいてもよい。
【００７４】
これがすべて完了すると、見出されたツリーすべてのうちでスコアが最高のツリーに基づいて、英語ツリーが翻訳として出力される。
【００７５】
上記ではほんのわずかの実施形態について詳細に開示されただけだが、他の実施形態が可能であり、本発明人らはそれらも本明細書内に包含されることを意図している。本明細書は他の方法で達成されてもよいより一般的な目標を達成するために個別的な例を記載している。この開示は例示的なものと意図されており、請求項は通常の当業者に予測可能でありうるいかなる修正または代替をもカバーすることが意図されている。たとえば、異なる規則および導出技法が使われることもできる。
【００７６】
また、本発明人らは、米国特許法第１１２条第６項ものとで解釈されるのは「手段」の語を使用する請求項だけであることを意図している。さらに、明細書からのいかなる限定も、そのような限定が請求項に明示的に含められているのでない限り、いかなる請求項に読み込まれてもならない。
【図面の簡単な説明】
【００７７】
【図１】翻訳システムのブロック図である。
【図２】規則の諸部分としてツリー部分を使った実施形態を示す図である。
【図３Ａ】諸ステップのツリーの形成および整列を示す図の一つである。
【図３Ｂ】諸ステップのツリーの形成および整列を示す図の一つである。
【図３Ｃ】諸ステップのツリーの形成および整列を示す図の一つである。
【図４】導出ステップおよびそれから誘導される規則を示す図である。
【図５】整列グラフを示す図である。
【図６】図５の整列グラフから導出された極小フラグメントを示す図である。
【図７】図５の整列グラフから導出された極小フラグメントを示す図である。
【図８】いかにして極小フラグメントを組み合わせるかを示す図である。
【図９】図１０のコンピュータ上で実行されるフローチャートである。
【図１０】コンピュータを含むシステムを示す図である。
【図１１】交差および並べ替えを示す図である。
【図１２】交差および並べ替えを示す図である。
【図１３】復号規則を示す図である。
【図１】
0005452868.tif 000003
【図２】
0005452868.tif 000004
【図３Ａ】
0005452868.tif 000005
【図３Ｂ】
0005452868.tif 000006
【図３Ｃ】
0005452868.tif 000007
【図４】
0005452868.tif 000008
【図５】
0005452868.tif 000009
【図６】
0005452868.tif 000010
【図７】
0005452868.tif 000011
【図８】
0005452868.tif 000012
【図９】
0005452868.tif 000013
【図１０】
0005452868.tif 000014
【図１１】
0005452868.tif 000015
【図１２】
0005452868.tif 000016
【図１３】
0005452868.tif 000017