(57)【特許請求の範囲】
【請求項１】
例文に共通な文字列で構成される固定項目と前記例文に共通しない文字列を表す記号で構成される可変項目を含む例文パターンと入力文とが相違する程度を表す距離値を前記例文パターンと前記入力文の構成要素毎に算出する場合に、前記距離値の算出対象となる例文パターンの構成要素が前記固定項目であるときには、前記算出対象の直前の構成要素と該直前の構成要素に対応する入力文の構成要素との距離値と前記算出対象を前記入力文の構成要素に置換させるために要する置換重みとの第１の和、前記算出対象の直前の構成要素と前記算出対象に対応する入力文の構成要素との距離値と前記算出対象を挿入するために要する挿入重みとの第２の和、及び前記算出対象と前記算出対象の直前の構成要素に対応する入力文の構成要素との距離値と前記算出対象に対応する入力文の構成要素を削除するために要する脱落重みとの第３の和の中で最小の和を前記距離値として算出し、前記距離値の算出対象となる例文パターンの構成要素が前記可変項目であるときには、前記第１の和、前記第２の和、前記第３の和、及び前記算出対象の直前の構成要素と前記入力文の最初の構成要素から前記算出対象の２つ前の構成要素に対応する入力文の構成要素までの各距離値と前記各距離値に応じた前記置換重みのそれぞれの第４の和の中で最小の和を前記距離値として算出する算出手段と、
前記算出手段で算出された距離値が最小となる例文パターンの構成要素と入力文の構成要素との対応関係を抽出する抽出手段と、
を備えることを特徴とするパターンマッチング装置。
【請求項２】
例文に共通な文字列で構成される固定項目及び前記例文に共通しない文字列を表す記号で構成される可変項目を含む例文パターン、並びに前記例文パターンが翻訳された対訳例文パターンを記憶する記憶手段と、
翻訳を行う対象として入力された入力文に対し、形態素解析を実行する解析手段と、
前記解析手段によって形態素解析が実行された前記入力文と前記例文パターンとの類似度と前記例文パターンが前記入力文をカバーしている割合を示すカバー率との大小関係に基づいて、前記記憶手段から前記入力文に応じた例文パターンを検索する検索手段と、
前記検索手段によって検索された例文パターンと前記入力文とが相違する程度を表す距離値を前記例文パターンと前記入力文の構成要素毎に算出する場合に、前記距離値の算出対象となる例文パターンの構成要素が前記固定項目であるときには、前記算出対象の直前の構成要素と該直前の構成要素に対応する入力文の構成要素との距離値と前記算出対象を前記入力文の構成要素に置換させるために要する置換重みとの第１の和、前記算出対象の直前の構成要素と前記算出対象に対応する入力文の構成要素との距離値と前記算出対象を挿入するために要する挿入重みとの第２の和、及び前記算出対象と前記算出対象の直前の構成要素に対応する入力文の構成要素との距離値と前記算出対象に対応する入力文の構成要素を削除するために要する脱落重みとの第３の和の中で最小の和を前記距離値として算出し、前記距離値の算出対象となる例文パターンの構成要素が前記可変項目であるときには、前記第１の和、前記第２の和、前記第３の和、及び前記算出対象の直前の構成要素と前記入力文の最初の構成要素から前記算出対象の２つ前の構成要素に対応する入力文の構成要素までの各距離値と前記各距離値に応じた前記置換重みのそれぞれの第４の和の中で最小の和を前記距離値として算出する算出手段と、
前記算出手段で算出された距離値が最小となる例文パターンの構成要素と入力文の構成要素との対応関係を抽出する抽出手段と、
前記抽出手段で抽出された対応関係に基づいて、前記入力文を翻訳する翻訳手段と、
を備えることを特徴とする翻訳装置。
【請求項３】
例文に共通な文字列で構成される固定項目及び前記例文に共通しない文字列を表す記号で構成される可変項目を含む例文パターン、並びに前記例文パターンが翻訳された対訳例文パターンを記憶する記憶手段と、
入力文を示す情報を入力する入力手段と、
翻訳を行う対象として前記入力手段により入力された入力文に対し、形態素解析を実行する解析手段と、
前記解析手段によって形態素解析が実行された前記入力文と前記例文パターンとの類似度と前記例文パターンが前記入力文をカバーしている割合を示すカバー率との大小関係に基づいて、前記記憶手段から前記入力文に応じた例文パターンを検索する検索手段と、
前記検索手段によって検索された例文パターンと前記入力文とが相違する程度を表す距離値を前記例文パターンと前記入力文の構成要素毎に算出する場合に、前記距離値の算出対象となる例文パターンの構成要素が前記固定項目であるときには、前記算出対象の直前の構成要素と該直前の構成要素に対応する入力文の構成要素との距離値と前記算出対象を前記入力文の構成要素に置換させるために要する置換重みとの第１の和、前記算出対象の直前の構成要素と前記算出対象に対応する入力文の構成要素との距離値と前記算出対象を挿入するために要する挿入重みとの第２の和、及び前記算出対象と前記算出対象の直前の構成要素に対応する入力文の構成要素との距離値と前記算出対象に対応する入力文の構成要素を削除するために要する脱落重みとの第３の和の中で最小の和を前記距離値として算出し、前記距離値の算出対象となる例文パターンの構成要素が前記可変項目であるときには、前記第１の和、前記第２の和、前記第３の和、及び前記算出対象の直前の構成要素と前記入力文の最初の構成要素から前記算出対象の２つ前の構成要素に対応する入力文の構成要素までの各距離値と前記各距離値に応じた前記置換重みのそれぞれの第４の和の中で最小の和を前記距離値として算出する算出手段と、
前記算出手段で算出された距離値が最小となる例文パターンの構成要素と入力文の構成要素との対応関係を抽出する抽出手段と、
前記抽出手段で抽出された対応関係に基づいて、前記入力文を翻訳する翻訳手段と、
を備えることを特徴とする翻訳システム。
【請求項４】
例文に共通な文字列で構成される固定項目及び前記例文に共通しない文字列を表す記号で構成される可変項目を含む例文パターン、並びに前記例文パターンが翻訳された対訳例文パターンを記憶する記憶手段と接続されたコンピュータを、
翻訳を行う対象として入力された入力文に対し、形態素解析を実行する解析手段と、
前記解析手段によって形態素解析が実行された前記入力文と前記例文パターンとの類似度と前記例文パターンが前記入力文をカバーしている割合を示すカバー率との大小関係に基づいて、前記記憶手段から前記入力文に応じた例文パターンを検索する検索手段と、
前記検索手段によって検索された例文パターンと前記入力文とが相違する程度を表す距離値を前記例文パターンと前記入力文の構成要素毎に算出する場合に、前記距離値の算出対象となる例文パターンの構成要素が前記固定項目であるときには、前記算出対象の直前の構成要素と該直前の構成要素に対応する入力文の構成要素との距離値と前記算出対象を前記入力文の構成要素に置換させるために要する置換重みとの第１の和、前記算出対象の直前の構成要素と前記算出対象に対応する入力文の構成要素との距離値と前記算出対象を挿入するために要する挿入重みとの第２の和、及び前記算出対象と前記算出対象の直前の構成要素に対応する入力文の構成要素との距離値と前記算出対象に対応する入力文の構成要素を削除するために要する脱落重みとの第３の和の中で最小の和を前記距離値として算出し、前記距離値の算出対象となる例文パターンの構成要素が前記可変項目であるときには、前記第１の和、前記第２の和、前記第３の和、及び前記算出対象の直前の構成要素と前記入力文の最初の構成要素から前記算出対象の２つ前の構成要素に対応する入力文の構成要素までの各距離値と前記各距離値に応じた前記置換重みのそれぞれの第４の和の中で最小の和を前記距離値として算出する算出手段と、
前記算出手段で算出された距離値が最小となる例文パターンの構成要素と入力文の構成要素との対応関係を抽出する抽出手段と、
前記抽出手段で抽出された対応関係に基づいて、前記入力文を翻訳する翻訳手段として機能させることを特徴とする翻訳プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、入力文などの単語列と、例文パターンなどの文字列とをマッチングするパターンマッチング装置、これを用いた翻訳装置及び翻訳システム、並びに翻訳プログラムに関する。
【背景技術】
【０００２】
従来、この種の装置として、文字列間を1対1に対応させた編集距離を用いて、入力文に類似な例文を検索するものがある(特許文献１)。
【０００３】
また、従来の翻訳装置として、パターンベース翻訳装置がある。パターンベース翻訳装置は、入力文の形態素解析結果である入力文の各単語列を参照例文パターンとマッチングをし、マッチングした参照対訳例文パターンを用いて翻訳を行うものである。また、入力文としてのテキスト文と例文パターン間とのマッチングは、テキスト文を直接例文パターンとマッチングさせるのではなく，テキスト文からテキスト文のパターンを抽出し、抽出されたテキスト文のパターンを参照例文パターンにマッチングさせる。
【０００４】
このようなパターンベースの翻訳装置において、参照例文パターンと、形態素解析された入力文の単語列とを直接マッチングするために、参照例文パターンに合わせて入力文を単語や節などに区切る変換をし、変換された入力文の単語列と参照例文パターンをマッチングさせるものがある(特許文献２)。
【先行技術文献】
【特許文献】
【０００５】
【特許文献１】特開２００５−２３４８００号公報
【特許文献２】特開２００９−１２９０３２号公報
【発明の概要】
【発明が解決しようとする課題】
【０００６】
本発明は、パターンベースの翻訳装置において、例文パターンとテキスト文間とのマッチングパターンの可変項目がテキスト文の複数の単語に対応する場合に、パターンと文字列間の一対多の対応が可能な編集距離を用いて、例文パターンとテキスト文の文字列間の相違値を算出することできなかったという課題を解決するパターンマッチング装置、これを用いた翻訳装置、及び翻訳システム、並びに翻訳プログラムを提供することにある。
【課題を解決するための手段】
【０００７】
本発明の請求項１に係るパターンマッチング装置は、例文に共通な文字列で構成される固定項目と前記例文に共通しない文字列を表す記号で構成される可変項目を含む例文パターンと入力文とが相違する程度を表す距離値を前記例文パターンと前記入力文の構成要素毎に算出する場合に、前記距離値の算出対象となる例文パターンの構成要素が前記固定項目であるときには、前記算出対象の直前の構成要素と該直前の構成要素に対応する入力文の構成要素との距離値と前記算出対象を前記入力文の構成要素に置換させるために要する置換重みとの第１の和、前記算出対象の直前の構成要素と前記算出対象に対応する入力文の構成要素との距離値と前記算出対象を挿入するために要する挿入重みとの第２の和、及び前記算出対象と前記算出対象の直前の構成要素に対応する入力文の構成要素との距離値と前記算出対象に対応する入力文の構成要素を削除するために要する脱落重みとの第３の和の中で最小の和を前記距離値として算出し、前記距離値の算出対象となる例文パターンの構成要素が前記可変項目であるときには、前記第１の和、前記第２の和、前記第３の和、及び前記算出対象の直前の構成要素と前記入力文の最初の構成要素から前記算出対象の２つ前の構成要素に対応する入力文の構成要素までの各距離値と前記各距離値に応じた前記置換重みのそれぞれの第４の和の中で最小の和を前記距離値として算出する算出手段と、前記算出手段で算出された距離値が最小となる例文パターンの構成要素と入力文の構成要素との対応関係を抽出する抽出手段と、を備えることを特徴とするものである。
【０００８】
本発明の請求項２に係る翻訳装置は、例文に共通な文字列で構成される固定項目及び前記例文に共通しない文字列を表す記号で構成される可変項目を含む例文パターン、並びに前記例文パターンが翻訳された対訳例文パターンを記憶する記憶手段と、翻訳を行う対象として入力された入力文に対し、形態素解析を実行する解析手段と、前記解析手段によって形態素解析が実行された前記入力文と前記例文パターンとの類似度と前記例文パターンが前記入力文をカバーしている割合を示すカバー率との大小関係に基づいて、前記記憶手段から前記入力文に応じた例文パターンを検索する検索手段と、前記検索手段によって検索された例文パターンと前記入力文とが相違する程度を表す距離値を前記例文パターンと前記入力文の構成要素毎に算出する場合に、前記距離値の算出対象となる例文パターンの構成要素が前記固定項目であるときには、前記算出対象の直前の構成要素と該直前の構成要素に対応する入力文の構成要素との距離値と前記算出対象を前記入力文の構成要素に置換させるために要する置換重みとの第１の和、前記算出対象の直前の構成要素と前記算出対象に対応する入力文の構成要素との距離値と前記算出対象を挿入するために要する挿入重みとの第２の和、及び前記算出対象と前記算出対象の直前の構成要素に対応する入力文の構成要素との距離値と前記算出対象に対応する入力文の構成要素を削除するために要する脱落重みとの第３の和の中で最小の和を前記距離値として算出し、前記距離値の算出対象となる例文パターンの構成要素が前記可変項目であるときには、前記第１の和、前記第２の和、前記第３の和、及び前記算出対象の直前の構成要素と前記入力文の最初の構成要素から前記算出対象の２つ前の構成要素に対応する入力文の構成要素までの各距離値と前記各距離値に応じた前記置換重みのそれぞれの第４の和の中で最小の和を前記距離値として算出する算出手段と、前記算出手段で算出された距離値が最小となる例文パターンの構成要素と入力文の構成要素との対応関係を抽出する抽出手段と、前記抽出手段で抽出された対応関係に基づいて、前記入力文を翻訳する翻訳手段と、を備えることを特徴とするものである。
【００１３】
本発明の請求項３に係る翻訳システムは、例文に共通な文字列で構成される固定項目及び前記例文に共通しない文字列を表す記号で構成される可変項目を含む例文パターン、並びに前記例文パターンが翻訳された対訳例文パターンを記憶する記憶手段と、入力文を示す情報を入力する入力手段と、翻訳を行う対象として前記入力手段により入力された入力文に対し、形態素解析を実行する解析手段と、前記解析手段によって形態素解析が実行された前記入力文と前記例文パターンとの類似度と前記例文パターンが前記入力文をカバーしている割合を示すカバー率との大小関係に基づいて、前記記憶手段から前記入力文に応じた例文パターンを検索する検索手段と、前記検索手段によって検索された例文パターンと前記入力文とが相違する程度を表す距離値を前記例文パターンと前記入力文の構成要素毎に算出する場合に、前記距離値の算出対象となる例文パターンの構成要素が前記固定項目であるときには、前記算出対象の直前の構成要素と該直前の構成要素に対応する入力文の構成要素との距離値と前記算出対象を前記入力文の構成要素に置換させるために要する置換重みとの第１の和、前記算出対象の直前の構成要素と前記算出対象に対応する入力文の構成要素との距離値と前記算出対象を挿入するために要する挿入重みとの第２の和、及び前記算出対象と前記算出対象の直前の構成要素に対応する入力文の構成要素との距離値と前記算出対象に対応する入力文の構成要素を削除するために要する脱落重みとの第３の和の中で最小の和を前記距離値として算出し、前記距離値の算出対象となる例文パターンの構成要素が前記可変項目であるときには、前記第１の和、前記第２の和、前記第３の和、及び前記算出対象の直前の構成要素と前記入力文の最初の構成要素から前記算出対象の２つ前の構成要素に対応する入力文の構成要素までの各距離値と前記各距離値に応じた前記置換重みのそれぞれの第４の和の中で最小の和を前記距離値として算出する算出手段と、前記算出手段で算出された距離値が最小となる例文パターンの構成要素と入力文の構成要素との対応関係を抽出する抽出手段と、前記抽出手段で抽出された対応関係に基づいて、前記入力文を翻訳する翻訳手段と、を備えることを特徴とするものである。
【００１４】
本発明の請求項４に係る翻訳プログラムは、例文に共通な文字列で構成される固定項目及び前記例文に共通しない文字列を表す記号で構成される可変項目を含む例文パターン、並びに前記例文パターンが翻訳された対訳例文パターンを記憶する記憶手段と接続されたコンピュータを、翻訳を行う対象として入力された入力文に対し、形態素解析を実行する解析手段と、前記解析手段によって形態素解析が実行された前記入力文と前記例文パターンとの類似度と前記例文パターンが前記入力文をカバーしている割合を示すカバー率との大小関係に基づいて、前記記憶手段から前記入力文に応じた例文パターンを検索する検索手段と、前記検索手段によって検索された例文パターンと前記入力文とが相違する程度を表す距離値を前記例文パターンと前記入力文の構成要素毎に算出する場合に、前記距離値の算出対象となる例文パターンの構成要素が前記固定項目であるときには、前記算出対象の直前の構成要素と該直前の構成要素に対応する入力文の構成要素との距離値と前記算出対象を前記入力文の構成要素に置換させるために要する置換重みとの第１の和、前記算出対象の直前の構成要素と前記算出対象に対応する入力文の構成要素との距離値と前記算出対象を挿入するために要する挿入重みとの第２の和、及び前記算出対象と前記算出対象の直前の構成要素に対応する入力文の構成要素との距離値と前記算出対象に対応する入力文の構成要素を削除するために要する脱落重みとの第３の和の中で最小の和を前記距離値として算出し、前記距離値の算出対象となる例文パターンの構成要素が前記可変項目であるときには、前記第１の和、前記第２の和、前記第３の和、及び前記算出対象の直前の構成要素と前記入力文の最初の構成要素から前記算出対象の２つ前の構成要素に対応する入力文の構成要素までの各距離値と前記各距離値に応じた前記置換重みのそれぞれの第４の和の中で最小の和を前記距離値として算出する算出手段と、前記算出手段で算出された距離値が最小となる例文パターンの構成要素と入力文の構成要素との対応関係を抽出する抽出手段と、前記抽出手段で抽出された対応関係に基づいて、前記入力文を翻訳する翻訳手段として機能させることを特徴とするものである。
【発明の効果】
【００１５】
請求項1の構成によれば、例文パターンと入力文の文字列との間の一対複数の対応が可能な編集距離を用いて、例文パターンと入力文の文字列間の相違値を算出することできる。
【００１６】
請求項２の構成によれば、翻訳に参照する例文パターンの候補を効率よく検索でき、例文パターンと文字列間の一対複数の対応が可能な編集距離を用いて、参照候補例文パターンと入力文の単語列間の相違値を少ない計算量で直接に算出することを可能となり、少ない計算量で精度よくマッチッグできると共に、その結果、少ない計算量で精度良く入力文を翻訳できる。
【００２１】
請求項３の構成によれば、翻訳に参照する例文パターンの候補を効率よく検索でき、例文パターンと文字列間の一対多の対応が可能な編集距離を用いて、参照候補例文パターンと入力文の単語列間の相違値を少ない計算量で直接に算出することを可能となり、少ない計算量で精度よくマッチッグできると共に、その結果、少ない計算量で精度良く入力文を翻訳できる。
【００２２】
請求項４の構成によれば、例文パターンと文字列間の一対多の対応が可能な編集距離を用いて、参照候補例文パターンと入力文の単語列間の相違値を少ない計算量で直接に算出することを可能となり、少ない計算量で精度よくマッチッグできると共に、その結果、少ない計算量で精度良く入力文を翻訳できる。
【図面の簡単な説明】
【００２３】
【図１】本発明の実施形態に係るパターンマッチング装置の機能的な構成例を示すブロック図である。
【図２】文字列間の距離計算のパスを表す説明図である。
【図３】算出部の処理手順を示すフローチャートである。
【図４】抽出部の処理手順を示すフローチャートである。
【図５】本発明の実施形態に係る翻訳システムの機能的な構成例を示すブロック図である。
【図６】翻訳装置のハードウェアの一構成例を表すブロック図である。
【図７】例文パターンを入力文との類似度とカバー率の関係で範囲を絞る例を示すグラフである。
【図８】効率化された算出部の処理手順を示すフローチャートである。
【図９】算出部の効率化された処理手順の説明図である。
【図１０】最適候補が除外される入力文と例文パターンの対応関係を示す図である。
【図１１】選択部における句の評価処理の手順を示すフローチャートである。
【図１２】翻訳装置の要部構成の処理手順を示すフローチャートである。
【図１３】形態素解析結果と例文パターンの固定項目との不整合による誤マッチングを表す説明図である。
【図１４】本発明の実施形態の変形例に係る翻訳システムの構成例を示すブロック図である。
【図１５】算出部の固定項目が拡張された距離計算処理を表すフローチャートである。
【図１６】文字列間の距離計算の具体例１を表す説明図である。
【図１７】文字列間の距離計算の具体例２を表す説明図である。
【図１８】文字列間の距離計算の具体例３を表す説明図である。
【図１９】算出部４の文字列間の距離計算アルゴリズムを表す式である。
【図２０】抽出部５の抽出アルゴリズムを表す式である。
【図２１】算出部４aの文字列間の距離計算アルゴリズムを表す式である。
【図２２】算出部４bの文字列間の距離計算アルゴリズムを表す式である。
【発明を実施するための形態】
【００２４】
以下、本発明の最良の実施形態について、添付図面を参照しつつ説明する。まず、翻訳システム(後述する)に使用できるパターンマッチング装置について説明する。
【００２５】
図１は、本発明の実施形態に係るパターンマッチング装置４０の機能的な構成例を示すブロック図である。同図に示すように、パターンマッチング装置４０は、算出部４及び抽出部５を含んで構成される。
【００２６】
算出部４は、比較対象の例文パターンA(要素ai)と、入力文の単語列S(要素sj)の相違としての距離値を算出する(i,jは自然数)。抽出部５は、算出部４で算出された距離値Dを定める例文パターンAと単語列S間の全ての対応関係(写像)
Fset(S)を抽出し、距離Dと写像の集合Fset(S)を出力する。
【００２７】
次に、1対多の対応関係(写像)を許す文字列間の距離について説明する。比較対象の例文パターンA＝
a1a2…anとし、入力文の単語列S=s1s2…smとする。ここで、例文パターンAの要素aiには二種あり、f(ai)=ｆ（固定項目），とf(ai)=v(可変項目)。例文パターンAから入力文の単語列Sへの写像={(i,j)}が次の写像条件を満たすときに，例文パターンAから入力文の単語列Sへの条件保存写像と呼ぶ。
【００２８】
写像条件は、
・f(ai)= f (固定項目)の場合は、1対1写像で、交差写像が禁止、
・f(ai)= v (可変項目)の場合は、１対多写像で、交差写像が禁止、
である。例文パターンAから入力文Sへの写像重みとは、例文パターンAの要素aiが文字列要素sjに置換する操作、要素aiが挿入する操作、要素sjが脱落操作を用いて、上記の条件保存写像の条件に従って、文字列Aを文字列Sに変換するときに必要な操作の重みである。ここで、aiがsjに置換させる操作の重みは置換重み、aiを挿入する操作の重みが挿入重み、siを削除する操作の重みが脱落重みと呼ぶ．なお、本明細書で、１対多写像を1対複数写像ともいう。
【００２９】
写像条件は下記の通りである。
写像条件：任意の(i1,j1)
∈ M， (i2,j2) ∈ M
ここで、i1,j1は、ai1,sj1の意味であるが、簡単のため番号部分のi1,ｊ1のみで示す。Mは写像(集合)を表す。
1、文字列Aの要素aiが固定項目の場合は、従来の文字列間の編集距離の写像条件である。
case f(ai1)=f or
f(ai2)=f, 
1.1、１対1写像である。
i1 = i2
iff j1 = j2.
1.2、交差写像禁止(左右関係を保存する条件)。
i1 < i2,
iff j1 < j2. 
2、文字列Aの要素aiが可変項目の場合は、一方向(正方向)で1対n写像。
case f(ai1)=v or
f(ai2)=v,  
2.1、逆方向は1対1写像である。
if j1 = j2
then i1 = i2 ,
2.2、正方向が1対n写像の時、nは連続している部分文字列である。
if i1 = i2,
and j1 < j2 
then for any (i3,j3)
∈ M and j1<j3< j2 , i1 = i3
2.3、正方向が交差写像禁止である。
if i1 < i2,
then j1 < j2.
2.4、逆方向も交差写像禁止である。
if j1 < j2
then i1 < i2, or i1 = i2. 
【００３０】
距離の定義は下記の通りである。
距離の定義：  文字列A＝a1a2…anと文字列S=s1s2…sm間のすべでの条件保存写像に対して、最小な条件保存写像の写像重みがAとS間の条件保存距離と呼び、D(A,S)と書く。
【００３１】
以上述べた条件保存写像の写像と距離の定義により、部分文字列間の条件保存距離を記憶するマットリスクd(i,j)、及び動的計画法を用いて、計算可能である。もし、例文パターンAの要素aiが固定項目を表すf(ai)=fなら、要素aiがSの一つの要素Sjに写像可能である。従って、従来の文字列間の編集距離と同じなので、距離d(i,j)は、図２(ａ)に示すように、矢印で示すパスを従来の計算方法で計算する。距離d(i,j)の計算式は、後述する図３のステップＳ１５fに示す。もし、例文パターンAの要素aiが可変項目を表す
f(ai)=Vなら、要素aiがSの連続している部分単語列に写像することができるので、距離d(i,j)は、図２(ｂ)に示すようなパス(矢印で示す)をすべて計算する必要がある。距離d(i,j)の計算式は、後述する図３のステップＳ１５vに示す。ここで、図２(ａ)、(ｂ)の縦方向は、例文パターンAの要素f(ai)で、横方向はSの要素f(sj)である。i,ｊは自然数で、
i=1,2・・・ｎ、j=1,2・・・ｍ
である。
【００３２】
次に、図３及び図４のフローチャートを参照してパターンマッチング装置４０の処理動作を説明する。なお、図３及び図４は、説明を分かりやすくするために、手順を簡略化しているが、それぞれ、図１９および図２０に、比較的正確な算出部４および抽出部５のアルゴリズムを表す式を示す。
【００３３】
まず、比較対象の例文パターンA＝ a1a2…anと、入力文の単語列S=s1s2…smが、算出部４に入力される(ステップＳ１１)。次に、部分文字列間の距離を記憶するマトリックスd(i,j)，対応関係の情報を記憶するマトリックスPathFlag(i,j)を初期化する。例えば、d(0,0)
= 0や、 PathFlag(i,j) = (0,0,0)などの処理が行われる。その処理後にi、jに１が入力され、例文パターンAの要素aiが固定項目かどうか判断される(ステップＳ１２、Ｓ１３)。
【００３４】
例文パターンAの要素aiが固定項目の場合には、次式で距離値が求められる(ステップＳ１５ｆ)。
d(i,j) = min { d(i-1,j-1) +w(ai,sj)
, d(i-1,j)+q, d(i,j-1)+r }
また、例文パターンAの要素aiが文字列Sの要素sjに置換する場合は、
PathFlag(i,j) = PathFlag or
(0,0,1)
とする。即ち、現在の写像情報PathFlag の内容と(0,0,1)のOR演算を行う。同様に、要素aiが脱落する場合は、
PathFlag(i,j) =
PathFlag or (1,0,0)
とする。要素Sjを挿入する場合は、
PathFlag(i,j) = PathFlag or
(0,1,0)
とする。
【００３５】
例文パターンAの要素aiが可変項目の場合は、次式で距離が求められる(ステップＳ１５v)。
d(i,j) = min { d(i-1,j-1) +w(ai,sj)
, d(i-1,j-2) +w(ai,sj-1…sj), … ,
d(i-1,0) +w(ai,s1…sj),
d(i-1,j)+q, d(i,j-1)+r }
この際に、要素aiがsjに置換する場合は、
PathFlag(i,j) = PathFlag or
(0,0,1)
とし、要素aiが要素sj-1…sjに置換する場合は
PathFlag(i,j) = PathFlag or
(0,0,1)
…
要素aiが要素sj…sjに置換する場合は、
PathFlag(i,j) = PathFlag or
(0,0,1)
とする。要素aiが脱落する場合は、
PathFlag(i,j) = PathFlag or
(1,0,0)
とする。要素sjを挿入する場合は、
PathFlag(i,j) = PathFlag or
(0,1,0)
とする。
【００３６】
例文パターンAの要素aiが固定項目または可変項目の処理が終了すると、ｊが1だけインクリメントされ、ｊがｍ以下かどうか判断される(ステップＳ１６、Ｓ１７)。ｊがｍより小さい場合には、jがmと等しくなるまで、ステップＳ１４乃至Ｓ１６が繰り返される。jがmより大きくなると、ｊを１とし、iが１だけインクリメントされ、iがｎ以下かどうか判断される(ステップＳ１８、Ｓ１９)。iがｎと等しくなるまで、ステップＳ１４乃至Ｓ１８が繰り返される。iがｎより大きくなると、算出部４の処理を終了する。
【００３７】
このようにして、例文パターンAと入力文の単語列S間の距離d(i,j)と写像情報PathFlag(i,j)が求められて出力される。ここでは、距離d(i,j)の距離値Dが所定の値かどうか判断する。例えば、最小かどうかを判断する。即ち、最小値Dminを定める例文パターンAと入力文の単語列S間の写像F(A,S)としての写像情報PathFlag(i,j)が、便宜上、抽出部５での抽出処理の前処理として保存されるものとする。この前処理を算出部４の算出処理の後処理としても良い。
【００３８】
算出部４の処理が終了すると、抽出部5の写像の抽出処理に移る。算出部４から抽出部５に例文パターンAと入力文の単語列S間の写像情報PathFlagと、ｎとｍの値が渡される(ステップＳ２１)。その後に、ステップＳ２２で次の処理をする。以下距離算出処理のパスを、逆に辿る処理が行われる。まず、例文パターンA
の要素aiai+1…anと入力文の単語列Sの要素sjsj+1…sm間の写像F(A,S)をMatching(i,j)に保存する。すべでのMatching(i,j)に初期値を付与する。即ち、
PathFlagS=NULL、 Fset(S)=NULL、
Push (n,m) into PathFlagS
とする。次に、PathFlagSが空かどうか判断し、空でなければ、PathFlagSから1要素を取り出して
(i,j)に入れる(ステップＳ２２、Ｓ２３)。(i,j)の値が(0,0)に等しいか判断する(ステップＳ２４)。(i,j)の値が(0,0)であれば、写像Matching(0,0)をFset(S)に追加すし、ステップ２３に戻る(ステップＳ２８)。(i,j)の値が(0,0)でなければ、要素aiが固定項目かどうか判断する(ステップＳ２６)。
【００３９】
例文パターンAの要素aiが固定項目であれば、次の処理を行う(ステップＳ２７f)。例文パターンAの要素aiが単語列Sの要素sjに置換する場合は、
Matching(i-1,j-1)=Mathing(i,j)+(i,j,j);
Push (i-1,j-1) into PathFlagS;
とする。要素aiが脱落する場合は、
Matching(i-1,j)
=Mathing(i,j)+(i,0,0); 
Push (i-1,j) into PathFlagS; 
とする。要素sjを挿入する場合は、
Matching(i,j-1)
=Mathing(i,j)+(0,j,j); 
Push (i,j-1) into PathFlagS
とする。
【００４０】
例文パターンAの要素aiが可変項目であれば、次の処理を行う(ステップＳ２７v)。例文パターンAの要素aiが単語列Sの要素sj1…sj2に置換する場合は、
Matching(i-1,j-1)=Mathing(i,j)+(i,j1,j2);
Push (i-1,j-1) into PathFlagS;
とする。要素aiが脱落する場合は、
Matching(i-1,j)
=Mathing(i,j)+(i,0,0); 
Push (i-1,j) into PathFlagS; 
とする。要素sjを挿入する場合は、 
Push (i,j-1) into PathFlagS
とする。その処理後に、ステップ２３に戻り、PathFlagSが空でなければ、ステップＳ２４以降の処理を行い、PathFlagSが空になると、抽出処理を終了する。
【００４１】
このようにして、抽出部５では、例文パターンAと入力文の単語列S間の写像F(A,S)の集合Fset(S)が求められて出力される。
【００４２】
次に、以上述べたパターンマッチング装置４０を更に改良したパターンマッチング装置４０aを用いた翻訳システム１００について説明する。後述するように、パターンマッチング装置４０aは、パターンマッチング装置４０の算出部４における文字列間の距離計算の時間計算量がO(n3)であるのに対し、その時間計算量がO(n2)と効率のよいマッチングアルゴリズムに改良した算出部４aを含む。
図５は、本実施形態に係る翻訳システム１００の構成を示すブロック図である。同図に示すように、翻訳システム１００は、及び入力装置１０、翻訳装置２０a、および出力装置３０を含んで構成される。
【００４３】
入力装置１０は、例えば、キーボード、ポインティング・ディバイス（いわゆるマウス）や、タッチパネル等で構成され、翻訳装置２０aに接続されている。この入力装置１０は、翻訳装置２０aの使用者に操作されて、第１の言語で表された入力文を入力する。
【００４４】
翻訳装置２０aは、入力装置１０及び表示装置などの出力装置３０に接続されている。この翻訳装置２０aは、入力装置１０から第１の言語で表された文を取得し、取得した文を第２の言語で表された文へ翻訳し、翻訳した文を出力装置３０としての表示装置に表示させる。
【００４５】
出力装置３０としての表示装置は、例えば、可視表示装置で、ＣＲＴ（Cathode Ray Tube）、液晶ディスプレイ、またはプラズマディスプレイなどの表示デバイスを含んで構成される。この表示装置は、翻訳装置２０aに制御されて第１の言語で表された入力文、翻訳の処理経過、および翻訳処理結果の翻訳文などの情報を表示画面上に表示する。
【００４６】
翻訳装置２０aは、、解析部１、検索部２、パターンマッチング装置４０a、選択部６、翻訳部７及び記憶部８を含んで構成される。パターンマッチング装置４０aは、算出部４aおよび抽出部５を含んで構成される。これらの各部の機能は、翻訳装置２０aが実行するソフトウェア制御により実現される。
【００４７】
図６は、このソフトウェア制御を実現する翻訳装置２０aのハードウェアの一構成例を表す図である。
【００４８】
翻訳装置２０aは、例えば、ＣＰＵ（Central
Processing Unit）等の演算部１００１、ＥＰＲＯＭ（Erasable Programmable Read-Only Memory）またはＥＥＰＲＯＭ（Electrically Erasable Programmable Read-Only Memory）等の読み出し専用メモリであるＲＯＭ１００２（Read-Only Memory ）、ＤＲＡＭ（Dynamic  RAM）またはＳＲＡＭ（Static  RAM）等の揮発性メモリ及びＮＶＲＡＭ（Non Volatile RAM）等の不揮発性メモリで構成されるＲＡＭ１００３（Random Access Memory）、並びにハードディスク装置等の外部記憶装置で構成される外部記憶部１００４で構成され、演算部１００１、ＲＯＭ１００２、ＲＡＭ１００３、および外部記憶部１００４は互いにバス１００５によって接続されている。
【００４９】
ソフトウェア制御は、ＲＯＭ１００２または外部記憶部１００４に格納したプログラムであるアプリケーションを演算部１００１が読込み、読込んだアプリケーションに従って演算部１００１が演算を行うことにより上記各部の機能を実現する。なお、ＲＡＭ１００３には、演算結果のデータが書き込まれ、特にＮＶＲＡＭには、電源オフ時にバックアップが必要なデータが保存される。
【００５０】
次に、翻訳装置２０aの各部を説明する。
【００５１】
まず、解析部１は、入力装置１０から入力された第1言語の文書情報(テキスト文)を形態素解析し、入力文を構成する単語を切り分け、単語の品詞を付与するなどの処理をする。
【００５２】
検索部２は、入力されたテキスト文の文字列および記憶部８の記憶内容(例文パターン対訳辞書)を参照して、入力文と類似な第1言語の例文パターン候補Aset（1以上）を検索(抽出)する。この際に、入力文と候補の例文パターンの検索用の類似度およびカバー率の関係から対象とする候補の範囲を絞って候補の例文パターンを検索する。詳細は後述する。
【００５３】
算出部４aは解析部１で形態素解析された結果の第1言語入力文の単語列Ｓと、検索部２で検索された第1言語例文パターン候補A間の相違としての距離を求める。
【００５４】
抽出部５は、最小距離が定める第1言語入力文Sと抽出された第1言語の例文パターン候補A間の対応関係(変換写像)を求める。ここで、最小な相違値としての距離値を与える例文パターン候補が複数の場合があるし，最小な相違値を決める例文パターン候補と入力文間の変換写像が複数ある場合もある。
【００５５】
選択部６は、抽出部５で求められたすべての例文パターンの候補と第1言語入力文の単語列間の対応関係集合から、最適な対訳関係(写像)を選択する。選択条件には、優先順位を付けずに総合的に判断する。詳細は後述する。この選択により求められた例文パターン対訳ペア(後述する)の番号と、第1言語入力文の単語列と抽出された第1言語の例文パターン間の対応関係を出力する。
【００５６】
翻訳部７は、選択部６で選択された第1言語入力文の単語列と第1言語例文パターン間の対応関係、第1言語例文パターンとそのパターンに対応している訳語言語の例文パターン間の対応関係を用いて、第1言語入力文の単語列と訳語言語の例文パターン間の対応関係を求め、可変部分を翻訳して、訳文を生成する。
【００５７】
記憶部８は、その記憶内容として、例文対訳辞書および例文パターン対訳辞書を含む。例文パターン対訳辞書は、例えば、例文パターン、訳文パターン、および例文パターンと訳文パターン間の対応関係を一組として記憶している。これを例文パターン対訳ペアと呼ぶ。
【００５８】
次に、翻訳システム１００の特徴的構成要素について詳細に説明する。それ以外の構成要素については、例えば、本出願人が出願し、公開された先願(特開２００９−１２９３２号公報)他に詳細に開示されている。
【００５９】
まず、検索部２を詳細に説明する。
【００６０】
検索部２では、例文パターンの候補範囲を絞ることにより、以降の処理の効率化による高速化が期待できる。例文パターンを入力文との類似度とカバー率で範囲を絞る場合の例を図７に示す。同図(ａ)(ｂ)は、横軸を類似度Sim(S,A)、縦軸をカバー率Cov(S,A)としたグラフである。例えば、同図(ａ)に示すように、入力文との類似度とカバー率がそれぞれある閾値(Ｇ２、Ｇ１)を超えると、例文パターンを候補とする。右の矩形領域に属している例文パターンが候補となる。ここで、検索部２で検索するとき、入力文Sと例文パターンAの間の検索用の類似度とカバー率が次のように定義されている。
Sim(S,A)=(2 *|S∩A|)/(|S|+ |A|); Cov(S,A)= |S∩A|/|S| 
|S|:Sのバイグラム(Bi-gram：２グラムとも云う)の数であり、|A|:AのBi-gramの数でS∩A|: SとAの共通Bi-gramの数である。
【００６１】
さらに、効率よく範囲を絞る例について述べる。レンマ１(Lemma1)およびレンマ２(Lemma1)を導入する。レンマ１、レンマ２は、以下のように定義される。
Lemma1: Sim(S,A)≧Cov(S,A)
Lemma2:
Sim(S,A)<2*Cov(S,A) 
【００６２】
レンマ１は、次のように証明される。
証明： Sim(S,A)/Cov(S,A) =
2* |S|/(|S|+ |A|); |A|> |S|
の場合には、例文パターンのBi-gram数が入力文のBi-gram数より多い。もし、この例文パターンを用いて入力文Ｓを翻訳するときに、例文パターンAには、入力文と対応できない項目がある。従って、例文パターンAから対応できない項目を削除する必要がある。しかし、例文パターンの項目を削除すると、例文パターンが崩れるため、翻訳が困難になる。従って、|A|<=
|S|の場合だけ考えれば十分である。従って、
Sim(S,A)/Cov(S,A) = 2*
|S|/(|S|+ |A|)≧1;
となる。
【００６３】
レンマ２は、次のように証明される。
証明：  Sim(S,A)/Cov(S,A) =
2* |S|/(|S|+ |A|); |S| >> |A|
の場合は、入力文Ｓが例文パターンAより大きければ大きいほど、
Sim(S,A)/Cov(S,A)は2に接近する。つまり、 Sim(S,A)/Cov(S,A)の最大値が2より小さい。従って、
Sim(S,A)/Cov(S,A)<2. 
となる。
【００６４】
図７(ｂ)は、図７(ａ)の矩形領域で示す範囲に対してレンマ１の境界線(４５度の傾きの線)以下で、かつレンマ２の境界線(類似度に対してカバー率が２分の１となる線)以上の領域で示す範囲となる。この結果、無駄なマッチングを減らすことができ、効率よくマッチング処理をおこなうことができる。従って、その処理を高速化できる。
【００６５】
次に、パターンマッチング装置４０の算出部４を改良したパターンマッチング装置４０aの算出部４aについて図３および図８のフローチャートを参照して相違部分を説明する。
【００６６】
算出部４の図３の手順と、算出部４aの図８の手順との相違部分を図９に示す。いずれもaiが可変項目のd(i,j)の計算処理で、図３のステップＳ１５vと、図８のステップＳ１５vaのうち、破線で囲った部分が相違する。図３のステップＳ１５vに示すd(i,j)の式、
d(i,j) = min { d(i-1,j-1) +w(ai,sj)
, d(i-1,j-2) +w(ai,sj-1…sj),
… , d(i-1,0) +w(ai,s1…sj),
d(i-1,j)+q, d(i,j-1)+r }
に対して、aiが可変項目のとき，aiは任意の部分文字列sjに写像しても重みは等しく０とする。即ち、重みｗを
w(ai,s1)
= w(ai,s2) = … = w(ai,sm) = w(ai,
sh…sk) 
とする。ここで，  1<=h,k<=m．である。この結果、ステップＳ１５vaのd(i,j)
が、
d(i,j) = min { d(i-1,j-1) +w(ai,sj)
, d(i-1,j)+q, d(i,j-1) }
となる。また、図３のステップＳ１５vでは、文字列Aの要素aiが文字列Sの要素sjに置換する場合、
要素aiが要素sj-1…sjに置換する場合、…要素aiが要素sj…sjに置換する場合の処理が複数あったものが、図８のステップＳ１５vaでは、要素 aiが要素sjに置換する場合だけになった。この結果、算出部４の時間計算量がO(n3)からO(n2)に効率化される。なお、図８のフローチャートは、説明を分かりやすくするために、手順を簡略化しているが、図２１に、比較的正確な算出部４aのアルゴリズムを表す式を示す。
【００６７】
次に、最適写像を選択する選択部６の詳細について述べる。
【００６８】
例えば、対象となるすべての写像について、置換項目(例文パターンAの項目に対応関係を持っている入力文Ｓの項目)が一番多い写像を選択すると、本来、候補として選出すべき例文パターンであっても、置換項目の項目数(マッチング数とも言う)が小さいとき、最適な候補の例文パターンとならない場合がある。
【００６９】
この場合の入力文と候補の例文パターンとの対応関例を図１０に示す。入力文Ｓに対して、同じ距離値を持つ例文パターンが複数ある(同図の場合２個)。その中には、一般論として、マッチングした項目数が多ければ多いほど、例文パターンが入力文とのマッチング具合はよいと考えられる。しかし、図１０に示すような例外がある。
【００７０】
同図は、最初の入力文Ｓと候補の例文パターンA1は、その対応関係では、例文パターンA1の名詞句NP2
対して入力文Ｓの「子供/2が/61 食べ[食べる/47]/47 残した[残す/47 た/74]/47 リンゴ/2 」に正しく対応させており、距離値が０で、置換項目数(マッチング数)は５である。これに対し、入力文Ｓと候補の例文パターンA3（「NP1 が食べ[食べる/47]/47 残した[残す/47 た/74]/47
NP2 を食べている[食べる て いる]」)間の距離値が同じである。その対応関係では、例文パターンの名詞句NP1 に対して入力文Ｓの「私/14は/65子供/2」を誤って対応させているが、置換項目数(マッチング数)は７である
【００７１】
図１０を参照して述べたように、入力文Sの「私は子供」を例文パターンのNP1
にマッチング(対応)させているので、得られた候補としての例文パターンは間違ったものとなる。もし、「私は子供」が名詞句ではないとする判断が可能なら、「私は子供」がNP1
にマッチングできなくなる。しかし、まだ、句の判断技術は未熟なので、実用的ではない。従って、句の判断技術を使用しない判断手段が必要である。最適な翻訳用候補の例文パターンを選択する基本的な考え方として、
(１) 例文パターンの可変部分にマッチングしている入力文の部分文字列は意味のある句である。
(２) マッチングした項目数ができるだけ多い。
(３) 距離値が小さい。
(４) 上記(１)(２)(３)の評価結果を融合して、総合的に判定する。
【００７２】
このような基本的な考え方に従った具体的例について説明する。まず、(１)項の例文パターンの可変部分に対応する句の評価処理手順について、図１１のフローチャートを参照して説明する。なお、本実施例の翻訳システム１０ｂは、公知の図示しない翻訳メモリ(ＴＭ)やパターン対訳辞書を備えているものとする。ここでは、これらの要素は、句の評価のために参照するが、翻訳自体は行わないものとする。
【００７３】
まず、句Ｐが翻訳メモリ(ＴＭ)に存在するか判断し、存在する場合には、句の評価値を1.0とする(ステップＳ５１a、Ｓ５１ｂ)。存在しないならば、パターン対訳辞書に句Ｐと完全にマッチングするパターンがあるか判断し、ある場合には、句の評価値を0.8とする(ステップＳ５２ａ、Ｓ５２b)。この場合、少なくとも句の構造は保証できる。パターン対訳辞書に句Ｐと完全にマッチングするパターンがないならば次に句を構成する単語だけで判断する。ここでは、単語の数が少ないほど評価を良くし、名詞を含む句は、良い評価をし、動詞等を含む句の場合には、評価を下げている。すなわち、句Ｐには、動詞、助詞、助動詞、感動詞があるか判断し、ない場合には、名詞を含むと判断し、句の評価値を1.0/(単語数)1/2とする(ステップＳ５３ａ、Ｓ５３b)。これらの品詞を含むとき、動詞等を含む句と判断し、句の評価値を0.5/(単語数)1/2
とし(ステップＳ５４)、句の評価手順を終了する。
【００７４】
先に述べた基本的な考え方を採用した最適な翻訳用候補の写像を選択するための計算例について説明する。
・入力文と翻訳用候補の例文パターン間のマッチング集合F1set(S)にある各マッチングF1(A,S)について、Fun1(F1(A, S))と Fun2(F1(A,S))を計算する。
・Fun2(F1(A,S)) < G4(このG4は閾値で0.1〜0.3の値をとる)
の場合は、F1set(S)集合から当該マッチングF1(A,S)を削除する。F1set(S)集合に残ったすべてのマッチングに対して，最大のFun1(F1(A,S))を決めるマッチングを求める。Fun1とFun2の計算方法について、以下にその例を二つ述べる。
【００７５】
次に、Fun1とFun2の計算方法１について説明する。
Fun1とFun2の計算方法１：
Fun1は、次式で与えられる。
Fun1(F1(A,S)) = 
( (Σ句の評価値)/句の数 * k1  +   マッチングした項目の総数
* k2 - 距離値*K3 )
* f1(例文パターンAのマッチングした固定項目数)
* f2（例文パターンAのマッチングした可変項目数）
Fun2は、次式で与えられる。
Fun2(F1(A, S)) = (Σ句の評価値) / 句の数
ここで，例えば，K1 =10, k2=１,
K3=1である。
【００７６】
次に、Fun1とFun2の計算方法２について説明する。
Fun1とFun2の計算方法２：
Fun1は、次式で与えられる。
Fun1(F1(A,S)) = 
((Σ句の評価値)/句の数 * k1  +  
+  マッチングした項目の総数 *マッチングした項目の総数
/|A| * k2 
+   (|S|*q+|A|*r -距離値)/2)
* f1(パターンAのマッチングした固定項目数) *f2（パターンAのマッチングした可変項目数）
ここで、例えば，K1 =10, k2=3,   |S|がF1(A,S)において、写像している項目の数と挿入した項目の数(連続挿入した部分が一つの挿入項目とする)の和、|A|がパターンの可変項目個数と固定項目個数の和、  qとrはそれぞれ、マッチングするときの挿入重みと脱落重みである。
f1 = 0 ：例文パターンのマッチングした固定項目数がG5(閾値)より小さい;
other 1
f2 = 0 ： 例文パターンにマッチングしていなかった可変項目数がある
;   other 1
上記f1、f2は、0か1の値をとり、f1の場合、例文パターンのマッチングした固定項目数がG5(閾値)より小さいとき０であり、それ以外は１である。f2の場合、例文パターンにマッチングしていなかった可変項目数があるとき０であり、それ以外のとき１である。
【００７７】
以上二つの計算例について説明したが、先に述べた基本的な考え方を採用するならば、他の計算方法でも良い。
【００７８】
次に、以上述べた改良された構成要素を含む本実施形態における翻訳装置２０aの要部の動作を図１２のフローチャートを参照して説明する。
【００７９】
形態素解析済みの入力文Ｓが解析部１から検索部２に入力されと、検索部２は、入力文Ｓに対応する例文パターン候補Asetを検索する（ステップＳ３１、Ｓ３２）。この際、
(１) Sim(S,A)>=Con(S,A); 
(２) Sim(S,A)<2*Cov(S,A) ; 
(３) 例文パターンの個数を所定の最大値に限定 、
となる条件で、例文パターンの候補範囲を絞り込んで検索を行い、
F1set(S)=F1set(S,A)=NULL; Dmin
=Dmax;
とする。
【００８０】
次に、例文パターン候補Asetから１つの例文パターン候補Aが取り出され、この例文パターンAと入力文Sの間の距離Dが算出部４aにより求められる（ステップＳ３３、Ｓ３４）。さらに、距離Dが最小値Dminより小さいか判断される（ステップＳ３５）。距離Dが最小値Dminより小さい場合(等しい場合含む)には、抽出部５で、前処理として、距離Dが定める入力文Sと例文パターンAの間の対応関係(写像)F(A,S)が求められ保存される（ステップＳ３６）。距離Dが最小値Dminより小さくない場合およびステップ３６で写像の保存処理がされた場合には、例文パターン候補Asetの全ての例文パターンが処理済みかどうか判断される（ステップＳ３７）。全ての例文パターンが処理済でなければ、ステップＳ３３乃至Ｓ３６の処理が、全ての例文パターンの処理済判断となるまで繰り返される。例文パターン候補Asetの全ての例文パターンが処理済みの判断となると、距離Dが定める例文パターンAと入力文Sの間での全ての写像(対応関係)Fset(S)が求められ、即ち、
Fset(S)= Fset(S)+ F(A,S)
とされる（ステップＳ３８）。次に、選択部６で、求められたFset(S)の中から最適な写像を求め、求められた写像をFres(A,S)に入れる（ステップＳ３９）。
【００８１】
次に、形態素解析結果と、例文パターンの固定項目の不整合による誤マッチングの課題を改善した本実施形態の変形例の翻訳システム１００ｂについて説明する。
【００８２】
そのような場合の一例を図１３に示す。同図に示すように、入力文Ｓが、「分かる よう に
報告 書 を 書いてください」であり、例文パターンＡは「分かる ように ＮＰ を   書いてください」である。形態素解析の結果“よう/に”は、例文パターンの固定項目“ように”にマッチングできない。
【００８３】
図１４は本実施形態の変形例に係る翻訳システム１００ｂの構成例を示すブロック図である。図５で説明した翻訳システム１００との相違部分について説明する。同図に示すように、その相違点は、図５で示す翻訳システム１００のパターンマッチング装置４０aが算出部４aを持つのに対し、翻訳システム１００ｂでは、パターンマッチング装置４０bがそれとは異なる算出部４bを持つことである。
【００８４】
算出部４bは、図１３で説明した形態素解析結果と、例文パターンの固定項目の不整合による誤マッチングの課題を改善した処理手順を持つ。図１５に算出部４bの処理手順を表すフローチャートを示す。その相違部分は、aiが固定項目の算出部４aのステップＳ１５f(図８参照)に対し、算出部４bのステップＳ１５fbには、次の点が追加されている。
【００８５】
例文パターンAの固定項目と入力文間が１対２の写像の場合、即ちaiがsj-1sjに置換する場合には
d(i,j)=d(i-1,j-2) ;  PathFlag(i,j)=(0,0,2)
とする。また、例文パターンAの固定項目と入力文間が１対３の写像の場合、aiがsj-2sj-1sjに置換する場合には
d(i,j)=d(i-1,j-3) ;
PathFlag(i,j)=(0,0,3) 
とする。この手順追加により、図１３で述べた「よう/に」のような不整合の課題も解決できる。なお、図１５のフローチャートは、説明を分かりやすくするために、手順を簡略化しているが、図２２bに、比較的正確な算出部４bのアルゴリズムを表す式を示す。
【００８６】
次に、図１６乃至図１８を参照して具体的な例を説明する。
【００８７】
図１６に示す具体例１は、例文パターンA が、
例文パターンA = NP1  は NP2 を  食べている[食べる
て いる]
であり、表の縦方向に並べて配置し、入力文Sは、
入力文S = 私は子供が食べ残したリンゴを食べている
であり、形態素解析した結果を表の横方向に並べて配置している。p=r=q=1.0をとした場合の距離を計算している。距離値は０で、１つのマッチング結果が得られた。即ち、
F1(A,S) = { (1,1,1), (2,2,2),
(3,3,7), (4,8,8), (5,9,9) }
である。右辺のカッコ内は、(例文パターンの要素番号,入力文の開始要素番号,
入力文の終了番号)を示す。即ち、矢印上の対応関係を示し、(1,1,1)は、例文パターンAの１番目の要素(可変項目)「NP1」と、入力文Sの１番目の要素「私」との対応関係、同様に(2,2,2)は、例文パターンAの２番目の要素「は」と、入力文Sの２番目の要素「は」との対応関係、(3,3,7)は、例文パターンAの3番目の要素(可変項目)「NP2」と、入力文Sの3番目の要素「子供」、同4番目の要素「が」、同5番目の要素「食べ」、同6番目の要素「残した」、および同7番目の要素「リンゴ」との１対5の対応関係、(4,8,8)は、例文パターンAの4番目の要素「を」と、入力文Sの8番目の要素「を」との対応関係、(5,9,9)は、例文パターンAの９番目の要素「食べている」と、入力文Sの8番目の要素「食べている」との対応関係をそれぞれ示し、いずれも距離値０である。
【００８８】
図１７は、具体例２を示し、具体例１と同じ内容の中国語の例を示す。
【００８９】
図１８は、具体例３を示し、表の縦方向には、例文パターンAが、
例文パターンA = NP1 は  NP2 と 一緒  に
NP3 を  見る
を示し、表の横方向には、入力文Sが、
入力文S =アイスを食べている山崎さんはリンゴとミカンを食べている田中さんと一緒に映画を見る
を、形態素解析した結果の文字列を示す。同様に、p=r=q=1.0をとした場合の距離を計算している。距離値は０で、１つのマッチング結果が得られた。即ち、
F1(A,S) = { (1,1,5),
(2,6,6),(3,7,13),(4,14,14),
(5,15,15),
(6,16,16),(7,17,17),(8,18,18),(9,19,19) }
である。
【００９０】
以上述べたように、本実施形態に係る翻訳システムによれば、パターン抽出技術に依存せず、翻訳に参照する例文パターンの候補を効率よく検索でき，パターンと文字列間の一対多の対応が可能な編集距離を用いて，参照候補例文パターンと入力文の単語列間の相違値を少ない計算量で直接に算出することを可能となり、精度よく参照候補例文パターンと入力文の単語列間の対応関係(写像)を求めることができる。更に、求められた複数の翻訳用パターン候補から最適な翻訳参照パターンを抽出することができる。その結果、少ない計算量で精度良く入力文を翻訳できる。
【００９１】
以上本発明の好ましい実施例について詳述したが、本発明は係る特定の実施例に限定されるものではなく、特許請求の範囲に記載された本発明の要旨の範囲内において、種々の変形、変更が可能である。
【００９２】
上記実施形態では、外部記憶装置はハードディスク（Hard Disk）で構成されるとして説明したが、これに限定されるわけではなく、例えば、フレキシブルディスク、ＣＤ−ＲＯＭ（Compact Disc Read Only Memory）、ＤＶＤ−ＲＯＭ（Digital Versatile Disk Read Only Memory）、ＤＶＤ−ＲＡＭ（Digital Versatile Disk
Random Access Memory）、ＭＯ（magneto-optic）、及び、フラッシュメモリ（flash memory）で構成される実施形式を採用できる。
【符号の説明】
【００９３】
１…解析部                          ２…検索部(検索手段)          
４、４a、４b…算出部（算出手段）    ５…抽出部(抽出手段)          
６…選択部(選択手段)                ７…翻訳部(翻訳手段)          
８…記憶部(記憶手段)
１０…入力装置                      ２０…出力装置                
２０、２０ｂ…翻訳装置              ４０、４０a、４０ｂ…パターンマッチング装置
１００、１００ｂ…翻訳システム      
１００１…演算部                  １００２…ＲＯＭ                  
１００３…ＲＡＭ                  １００４…外部記憶部              
１００５…バス                    
【図１】
0005521669.tif 000002
【図２】
0005521669.tif 000003
【図３】
0005521669.tif 000004
【図４】
0005521669.tif 000005
【図５】
0005521669.tif 000006
【図６】
0005521669.tif 000007
【図７】
0005521669.tif 000008
【図８】
0005521669.tif 000009
【図９】
0005521669.tif 000010
【図１０】
0005521669.tif 000011
【図１１】
0005521669.tif 000012
【図１２】
0005521669.tif 000013
【図１３】
0005521669.tif 000014
【図１４】
0005521669.tif 000015
【図１５】
0005521669.tif 000016
【図１６】
0005521669.tif 000017
【図１７】
0005521669.tif 000018
【図１８】
0005521669.tif 000019
【図１９】
0005521669.tif 000020
【図２０】
0005521669.tif 000021
【図２１】
0005521669.tif 000022
【図２２】
0005521669.tif 000023