(57)【特許請求の範囲】
【請求項１】
例文に共通な文字列で構成される第１の固定項目と前記例文に共通しない文字列を表す記号で構成される可変項目を含む第１の例文パターンにおける前記第１の固定項目を文字単位の第２の固定項目に変換する第１の変換手段と、
前記第２の固定項目及び前記可変項目を含む第２の例文パターンと入力文とが相違する程度を表す距離値を前記第２の例文パターンと前記入力文の文字毎に算出する場合に、前記距離値の算出対象となる第２の例文パターンの文字が前記第２の固定項目であるときには、前記算出対象の直前の文字と該直前の文字に対応する入力文の文字との距離値と前記算出対象を前記入力文の文字に置換させるために要する置換重みとの第１の和、前記算出対象の直前の文字と前記算出対象に対応する入力文の文字との距離値と前記算出対象を挿入するために要する挿入重みとの第２の和、及び前記算出対象と前記算出対象の直前の文字に対応する入力文の文字との距離値と前記算出対象に対応する入力文の文字を削除するために要する脱落重みとの第３の和の中で最小の和を前記距離値として算出し、前記距離値の算出対象となる第２の例文パターンの文字が前記可変項目であるときには、前記第１の和、前記第２の和、前記第３の和、及び前記算出対象の直前の文字と前記入力文の最初の文字から前記算出対象の２つ前の文字に対応する入力文の文字までの各距離値と前記各距離値に応じた前記置換重みのそれぞれの第４の和の中で最小の和を前記距離値として算出するとともに、前記第２の例文パターンと前記入力文との文字毎の類似度を求める所定の計算式と算出した前記距離値とに基づいて、前記第２の例文パターンと前記入力文との文字毎の類似度を算出する算出手段と、
前記算出手段で算出された距離値が最小となる第２の例文パターンの文字と入力文の文字との対応関係又は前記算出手段で算出された類似度が最大となる第２の例文パターンの文字と入力文の文字との対応関係を抽出する抽出手段と、
前記第１の例文パターンと前記第２の例文パターンとの対応関係に基づいて、前記抽出手段で抽出された対応関係を第１の例文パターンの文字列と入力文の文字列との対応関係に変換する第２の変換手段と、
を備えることを特徴とするパターンマッチング装置。
【請求項２】
例文に共通な文字列で構成される第１の固定項目及び前記例文に共通しない文字列を表す記号で構成される可変項目を含む第１の例文パターン、並びに前記第１の例文パターンが翻訳された対訳例文パターンを記憶する記憶手段と、
翻訳を行う対象として入力された入力文に対し、形態素解析を実行する解析手段と、
前記解析手段によって形態素解析が実行された前記入力文と前記第１の例文パターンとの類似度と前記第１の例文パターンが前記入力文をカバーしている割合を示すカバー率との大小関係に基づいて、前記記憶手段から前記入力文に応じた第１の例文パターンを検索する検索手段と、
前記検索手段で検索された第１の例文パターンにおける前記第１の固定項目を文字単位の第２の固定項目に変換する第１の変換手段と、
前記第２の固定項目及び前記可変項目を含む第２の例文パターンと入力文とが相違する程度を表す距離値を前記第２の例文パターンと前記入力文の文字毎に算出する場合に、前記距離値の算出対象となる第２の例文パターンの文字が前記第２の固定項目であるときには、前記算出対象の直前の文字と該直前の文字に対応する入力文の文字との距離値と前記算出対象を前記入力文の文字に置換させるために要する置換重みとの第１の和、前記算出対象の直前の文字と前記算出対象に対応する入力文の文字との距離値と前記算出対象を挿入するために要する挿入重みとの第２の和、及び前記算出対象と前記算出対象の直前の文字に対応する入力文の文字との距離値と前記算出対象に対応する入力文の文字を削除するために要する脱落重みとの第３の和の中で最小の和を前記距離値として算出し、前記距離値の算出対象となる第２の例文パターンの文字が前記可変項目であるときには、前記第１の和、前記第２の和、前記第３の和、及び前記算出対象の直前の文字と前記入力文の最初の文字から前記算出対象の２つ前の文字に対応する入力文の文字までの各距離値と前記各距離値に応じた前記置換重みのそれぞれの第４の和の中で最小の和を前記距離値として算出するとともに、前記第２の例文パターンと前記入力文との文字毎の類似度を求める所定の計算式と算出した前記距離値とに基づいて、前記第２の例文パターンと前記入力文との文字毎の類似度を算出する算出手段と、
前記算出手段で算出された距離値が最小となる第２の例文パターンの文字と入力文の文字との対応関係又は前記算出手段で算出された類似度が最大となる第２の例文パターンの文字と入力文の文字との対応関係を抽出する抽出手段と、
前記第１の例文パターンと前記第２の例文パターンとの対応関係に基づいて、前記抽出手段で抽出された対応関係を第１の例文パターンの文字列と入力文の文字列との対応関係に変換する第２の変換手段と、
前記第１の例文パターンの文字列と入力文の文字列との対応関係に基づいて、前記入力文を翻訳する翻訳手段と、
を備えることを特徴とする翻訳装置。
【請求項３】
例文に共通な文字列で構成される第１の固定項目及び前記例文に共通しない文字列を表す記号で構成される可変項目を含む第１の例文パターン、並びに前記第１の例文パターンが翻訳された対訳例文パターンを記憶する記憶手段と、
入力文を示す情報を入力する入力手段と、
翻訳を行う対象として前記入力手段により入力された入力文に対し、形態素解析を実行する解析手段と、
前記解析手段によって形態素解析が実行された前記入力文と前記第１の例文パターンとの類似度と前記第１の例文パターンが前記入力文をカバーしている割合を示すカバー率との大小関係に基づいて、前記記憶手段から前記入力文に応じた第１の例文パターンを検索する検索手段と、
前記検索手段で検索された第１の例文パターンにおける前記第１の固定項目を文字単位の第２の固定項目に変換する第１の変換手段と、
前記第２の固定項目及び前記可変項目を含む第２の例文パターンと入力文とが相違する程度を表す距離値を前記第２の例文パターンと前記入力文の文字毎に算出する場合に、前記距離値の算出対象となる第２の例文パターンの文字が前記第２の固定項目であるときには、前記算出対象の直前の文字と該直前の文字に対応する入力文の文字との距離値と前記算出対象を前記入力文の文字に置換させるために要する置換重みとの第１の和、前記算出対象の直前の文字と前記算出対象に対応する入力文の文字との距離値と前記算出対象を挿入するために要する挿入重みとの第２の和、及び前記算出対象と前記算出対象の直前の文字に対応する入力文の文字との距離値と前記算出対象に対応する入力文の文字を削除するために要する脱落重みとの第３の和の中で最小の和を前記距離値として算出し、前記距離値の算出対象となる第２の例文パターンの文字が前記可変項目であるときには、前記第１の和、前記第２の和、前記第３の和、及び前記算出対象の直前の文字と前記入力文の最初の文字から前記算出対象の２つ前の文字に対応する入力文の文字までの各距離値と前記各距離値に応じた前記置換重みのそれぞれの第４の和の中で最小の和を前記距離値として算出するとともに、前記第２の例文パターンと前記入力文との文字毎の類似度を求める所定の計算式と算出した前記距離値とに基づいて、前記第２の例文パターンと前記入力文との文字毎の類似度を算出する算出手段と、
前記算出手段で算出された距離値が最小となる第２の例文パターンの文字と入力文の文字との対応関係又は前記算出手段で算出された類似度が最大となる第２の例文パターンの文字と入力文の文字との対応関係を抽出する抽出手段と、
前記第１の例文パターンと前記第２の例文パターンとの対応関係に基づいて、前記抽出手段で抽出された対応関係を第１の例文パターンの文字列と入力文の文字列との対応関係に変換する第２の変換手段と、
前記第１の例文パターンの文字列と入力文の文字列との対応関係に基づいて、前記入力文を翻訳する翻訳手段と、
を備えることを特徴とする翻訳システム。
【請求項４】
例文に共通な文字列で構成される第１の固定項目及び前記例文に共通しない文字列を表す記号で構成される可変項目を含む第１の例文パターン、並びに前記第１の例文パターンが翻訳された対訳例文パターンを記憶する記憶手段と接続されたコンピュータを、
翻訳を行う対象として入力された入力文に対し、形態素解析を実行する解析手段と、
前記解析手段によって形態素解析が実行された前記入力文と前記第１の例文パターンとの類似度と前記第１の例文パターンが前記入力文をカバーしている割合を示すカバー率との大小関係に基づいて、前記記憶手段から前記入力文に応じた第１の例文パターンを検索する検索手段と、
前記検索手段によって検索された第１の例文パターンにおける前記第１の固定項目を文字単位の第２の固定項目に変換する第１の変換手段と、
前記第２の固定項目及び前記可変項目を含む第２の例文パターンと入力文とが相違する程度を表す距離値を前記第２の例文パターンと前記入力文の文字毎に算出する場合に、前記距離値の算出対象となる第２の例文パターンの文字が前記第２の固定項目であるときには、前記算出対象の直前の文字と該直前の文字に対応する入力文の文字との距離値と前記算出対象を前記入力文の文字に置換させるために要する置換重みとの第１の和、前記算出対象の直前の文字と前記算出対象に対応する入力文の文字との距離値と前記算出対象を挿入するために要する挿入重みとの第２の和、及び前記算出対象と前記算出対象の直前の文字に対応する入力文の文字との距離値と前記算出対象に対応する入力文の文字を削除するために要する脱落重みとの第３の和の中で最小の和を前記距離値として算出し、前記距離値の算出対象となる第２の例文パターンの文字が前記可変項目であるときには、前記第１の和、前記第２の和、前記第３の和、及び前記算出対象の直前の文字と前記入力文の最初の文字から前記算出対象の２つ前の文字に対応する入力文の文字までの各距離値と前記各距離値に応じた前記置換重みのそれぞれの第４の和の中で最小の和を前記距離値として算出するとともに、前記第２の例文パターンと前記入力文との文字毎の類似度を求める所定の計算式と算出した前記距離値とに基づいて、前記第２の例文パターンと前記入力文との文字毎の類似度を算出する算出手段と、
前記算出手段で算出された距離値が最小となる第２の例文パターンの文字と入力文の文字との対応関係又は前記算出手段で算出された類似度が最大となる第２の例文パターンの文字と入力文の文字との対応関係を抽出する抽出手段と、
前記第１の例文パターンと前記第２の例文パターンとの対応関係に基づいて、前記抽出手段で抽出された対応関係を第１の例文パターンの文字列と入力文の文字列との対応関係に変換する第２の変換手段と、
前記第１の例文パターンの文字列と入力文の文字列との対応関係に基づいて、前記入力文を翻訳する翻訳手段として機能させることを特徴とする翻訳プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、入力文などの文字列と、候補の例文パターンなどの文字列とをマッチングするパターンマッチング装置、これを用いた翻訳装置及び翻訳システム、並びに翻訳プログラムに関する。
【背景技術】
【０００２】
従来、この種の装置として、文字列間を1対1に対応させた編集距離を用いて、入力文に類似な例文を検索するものがある(特許文献１)。
【０００３】
従来のパターンベースの翻訳装置には、まず，入力文の形態素解析を行う。続いて、形態素解析の結果得られた入力文の単語列を用いて参照例文パターンとマッチングをし、マッチングした参照対訳例文パターンを用いて翻訳を行う。また、入力文としてのテキスト文と例文パターン間のマッチング法として、テキスト文からテキスト文のパターンを抽出し(パターン抽出技術)、抽出されたテキスト文のパターンを参照例文パターンにマッチングさせる方法は一般的な考え方である。
【０００４】
また、従来の翻訳装置として、参照例文パターンの文字列と、形態素解析された入力文の文字列とを直接マッチングするために、参照例文パターンに合わせて入力文を単語や節などに区切る変換をし、変換された入力文の文字列と参照例文パターンの文字列をマッチングさせるものが開示されている(特許文献２)。
【先行技術文献】
【特許文献】
【０００５】
【特許文献１】特開２００５−２３４８００号公報
【特許文献２】特開２００９−１２９０３２号公報
【発明の概要】
【発明が解決しようとする課題】
【０００６】
本発明は、パターンベースの翻訳装置では、例文パターンとテキスト文間でのマッチングパターンの可変項目がテキスト文の複数の単語に対応する場合に、例文パターンと文字列間の一対複数の対応が可能な編集距離を用いて、例文パターンとテキスト文の文字列間の相違値を算出することできず、パターンマッチング結果が形態素解析に依存するという課題を解決するパターンマッチング装置、これを用いた翻訳装置、及び翻訳システム、並びに翻訳プログラムを提供することにある。
【課題を解決するための手段】
【０００７】
本発明の請求項１に係るパターンマッチング装置は、例文に共通な文字列で構成される第１の固定項目と前記例文に共通しない文字列を表す記号で構成される可変項目を含む第１の例文パターンにおける前記第１の固定項目を文字単位の第２の固定項目に変換する第１の変換手段と、前記第２の固定項目及び前記可変項目を含む第２の例文パターンと入力文とが相違する程度を表す距離値を前記第２の例文パターンと前記入力文の文字毎に算出する場合に、前記距離値の算出対象となる第２の例文パターンの文字が前記第２の固定項目であるときには、前記算出対象の直前の文字と該直前の文字に対応する入力文の文字との距離値と前記算出対象を前記入力文の文字に置換させるために要する置換重みとの第１の和、前記算出対象の直前の文字と前記算出対象に対応する入力文の文字との距離値と前記算出対象を挿入するために要する挿入重みとの第２の和、及び前記算出対象と前記算出対象の直前の文字に対応する入力文の文字との距離値と前記算出対象に対応する入力文の文字を削除するために要する脱落重みとの第３の和の中で最小の和を前記距離値として算出し、前記距離値の算出対象となる第２の例文パターンの文字が前記可変項目であるときには、前記第１の和、前記第２の和、前記第３の和、及び前記算出対象の直前の文字と前記入力文の最初の文字から前記算出対象の２つ前の文字に対応する入力文の文字までの各距離値と前記各距離値に応じた前記置換重みのそれぞれの第４の和の中で最小の和を前記距離値として算出するとともに、前記第２の例文パターンと前記入力文との文字毎の類似度を求める所定の計算式と算出した前記距離値とに基づいて、前記第２の例文パターンと前記入力文との文字毎の類似度を算出する算出手段と、前記算出手段で算出された距離値が最小となる第２の例文パターンの文字と入力文の文字との対応関係又は前記算出手段で算出された類似度が最大となる第２の例文パターンの文字と入力文の文字との対応関係を抽出する抽出手段と、前記第１の例文パターンと前記第２の例文パターンとの対応関係に基づいて、前記抽出手段で抽出された対応関係を第１の例文パターンの文字列と入力文の文字列との対応関係に変換する第２の変換手段と、を備えることを特徴とするものである。
【０００８】
本発明の請求項２に係る翻訳装置は、例文に共通な文字列で構成される第１の固定項目及び前記例文に共通しない文字列を表す記号で構成される可変項目を含む第１の例文パターン、並びに前記第１の例文パターンが翻訳された対訳例文パターンを記憶する記憶手段と、翻訳を行う対象として入力された入力文に対し、形態素解析を実行する解析手段と、前記解析手段によって形態素解析が実行された前記入力文と前記第１の例文パターンとの類似度と前記第１の例文パターンが前記入力文をカバーしている割合を示すカバー率との大小関係に基づいて、前記記憶手段から前記入力文に応じた第１の例文パターンを検索する検索手段と、前記検索手段で検索された第１の例文パターンにおける前記第１の固定項目を文字単位の第２の固定項目に変換する第１の変換手段と、前記第２の固定項目及び前記可変項目を含む第２の例文パターンと入力文とが相違する程度を表す距離値を前記第２の例文パターンと前記入力文の文字毎に算出する場合に、前記距離値の算出対象となる第２の例文パターンの文字が前記第２の固定項目であるときには、前記算出対象の直前の文字と該直前の文字に対応する入力文の文字との距離値と前記算出対象を前記入力文の文字に置換させるために要する置換重みとの第１の和、前記算出対象の直前の文字と前記算出対象に対応する入力文の文字との距離値と前記算出対象を挿入するために要する挿入重みとの第２の和、及び前記算出対象と前記算出対象の直前の文字に対応する入力文の文字との距離値と前記算出対象に対応する入力文の文字を削除するために要する脱落重みとの第３の和の中で最小の和を前記距離値として算出し、前記距離値の算出対象となる第２の例文パターンの文字が前記可変項目であるときには、前記第１の和、前記第２の和、前記第３の和、及び前記算出対象の直前の文字と前記入力文の最初の文字から前記算出対象の２つ前の文字に対応する入力文の文字までの各距離値と前記各距離値に応じた前記置換重みのそれぞれの第４の和の中で最小の和を前記距離値として算出するとともに、前記第２の例文パターンと前記入力文との文字毎の類似度を求める所定の計算式と算出した前記距離値とに基づいて、前記第２の例文パターンと前記入力文との文字毎の類似度を算出する算出手段と、前記算出手段で算出された距離値が最小となる第２の例文パターンの文字と入力文の文字との対応関係又は前記算出手段で算出された類似度が最大となる第２の例文パターンの文字と入力文の文字との対応関係を抽出する抽出手段と、前記第１の例文パターンと前記第２の例文パターンとの対応関係に基づいて、前記抽出手段で抽出された対応関係を第１の例文パターンの文字列と入力文の文字列との対応関係に変換する第２の変換手段と、前記第１の例文パターンの文字列と入力文の文字列との対応関係に基づいて、前記入力文を翻訳する翻訳手段と、を備えることを特徴とするものである。
【００１２】
本発明の請求項３に係る翻訳システムは、例文に共通な文字列で構成される第１の固定項目及び前記例文に共通しない文字列を表す記号で構成される可変項目を含む第１の例文パターン、並びに前記第１の例文パターンが翻訳された対訳例文パターンを記憶する記憶手段と、入力文を示す情報を入力する入力手段と、翻訳を行う対象として前記入力手段により入力された入力文に対し、形態素解析を実行する解析手段と、前記解析手段によって形態素解析が実行された前記入力文と前記第１の例文パターンとの類似度と前記第１の例文パターンが前記入力文をカバーしている割合を示すカバー率との大小関係に基づいて、前記記憶手段から前記入力文に応じた第１の例文パターンを検索する検索手段と、前記検索手段で検索された第１の例文パターンにおける前記第１の固定項目を文字単位の第２の固定項目に変換する第１の変換手段と、前記第２の固定項目及び前記可変項目を含む第２の例文パターンと入力文とが相違する程度を表す距離値を前記第２の例文パターンと前記入力文の文字毎に算出する場合に、前記距離値の算出対象となる第２の例文パターンの文字が前記第２の固定項目であるときには、前記算出対象の直前の文字と該直前の文字に対応する入力文の文字との距離値と前記算出対象を前記入力文の文字に置換させるために要する置換重みとの第１の和、前記算出対象の直前の文字と前記算出対象に対応する入力文の文字との距離値と前記算出対象を挿入するために要する挿入重みとの第２の和、及び前記算出対象と前記算出対象の直前の文字に対応する入力文の文字との距離値と前記算出対象に対応する入力文の文字を削除するために要する脱落重みとの第３の和の中で最小の和を前記距離値として算出し、前記距離値の算出対象となる第２の例文パターンの文字が前記可変項目であるときには、前記第１の和、前記第２の和、前記第３の和、及び前記算出対象の直前の文字と前記入力文の最初の文字から前記算出対象の２つ前の文字に対応する入力文の文字までの各距離値と前記各距離値に応じた前記置換重みのそれぞれの第４の和の中で最小の和を前記距離値として算出するとともに、前記第２の例文パターンと前記入力文との文字毎の類似度を求める所定の計算式と算出した前記距離値とに基づいて、前記第２の例文パターンと前記入力文との文字毎の類似度を算出する算出手段と、前記算出手段で算出された距離値が最小となる第２の例文パターンの文字と入力文の文字との対応関係又は前記算出手段で算出された類似度が最大となる第２の例文パターンの文字と入力文の文字との対応関係を抽出する抽出手段と、前記第１の例文パターンと前記第２の例文パターンとの対応関係に基づいて、前記抽出手段で抽出された対応関係を第１の例文パターンの文字列と入力文の文字列との対応関係に変換する第２の変換手段と、前記第１の例文パターンの文字列と入力文の文字列との対応関係に基づいて、前記入力文を翻訳する翻訳手段と、を備えることを特徴とするものである。
【００１３】
本発明の請求項４に係る翻訳プログラムは、例文に共通な文字列で構成される第１の固定項目及び前記例文に共通しない文字列を表す記号で構成される可変項目を含む第１の例文パターン、並びに前記第１の例文パターンが翻訳された対訳例文パターンを記憶する記憶手段と接続されたコンピュータを、翻訳を行う対象として入力された入力文に対し、形態素解析を実行する解析手段と、前記解析手段によって形態素解析が実行された前記入力文と前記第１の例文パターンとの類似度と前記第１の例文パターンが前記入力文をカバーしている割合を示すカバー率との大小関係に基づいて、前記記憶手段から前記入力文に応じた第１の例文パターンを検索する検索手段と、前記検索手段によって検索された第１の例文パターンにおける前記第１の固定項目を文字単位の第２の固定項目に変換する第１の変換手段と、前記第２の固定項目及び前記可変項目を含む第２の例文パターンと入力文とが相違する程度を表す距離値を前記第２の例文パターンと前記入力文の文字毎に算出する場合に、前記距離値の算出対象となる第２の例文パターンの文字が前記第２の固定項目であるときには、前記算出対象の直前の文字と該直前の文字に対応する入力文の文字との距離値と前記算出対象を前記入力文の文字に置換させるために要する置換重みとの第１の和、前記算出対象の直前の文字と前記算出対象に対応する入力文の文字との距離値と前記算出対象を挿入するために要する挿入重みとの第２の和、及び前記算出対象と前記算出対象の直前の文字に対応する入力文の文字との距離値と前記算出対象に対応する入力文の文字を削除するために要する脱落重みとの第３の和の中で最小の和を前記距離値として算出し、前記距離値の算出対象となる第２の例文パターンの文字が前記可変項目であるときには、前記第１の和、前記第２の和、前記第３の和、及び前記算出対象の直前の文字と前記入力文の最初の文字から前記算出対象の２つ前の文字に対応する入力文の文字までの各距離値と前記各距離値に応じた前記置換重みのそれぞれの第４の和の中で最小の和を前記距離値として算出するとともに、前記第２の例文パターンと前記入力文との文字毎の類似度を求める所定の計算式と算出した前記距離値とに基づいて、前記第２の例文パターンと前記入力文との文字毎の類似度を算出する算出手段と、前記算出手段で算出された距離値が最小となる第２の例文パターンの文字と入力文の文字との対応関係又は前記算出手段で算出された類似度が最大となる第２の例文パターンの文字と入力文の文字との対応関係を抽出する抽出手段と、前記第１の例文パターンと前記第２の例文パターンとの対応関係に基づいて、前記抽出手段で抽出された対応関係を第１の例文パターンの文字列と入力文の文字列との対応関係に変換する第２の変換手段と、前記第１の例文パターンの文字列と入力文の文字列との対応関係に基づいて、前記入力文を翻訳する翻訳手段として機能させることを特徴とするものである。
【発明の効果】
【００１４】
請求項1の構成によれば、形態素解析に依存せず、パターンと文字列間の一対複数の対応が可能な編集距離を用いて、例文パターンとテキスト文の文字列間の相違値を直接に算出することができる。
【００１５】
請求項２の構成によれば、形態素解析に依存せず、翻訳に参照する例文パターンの候補を効率よく検索でき、例文パターンと文字列間の一対複数の対応が可能な編集距離を用いて、参照候補例文パターンと入力文の単語列間の相違値を少ない計算量で直接に算出することを可能となり、少ない計算量で精度よくマッチッグできると共に、その結果、少ない計算量で精度良く入力文を翻訳できる。
【００１９】
請求項３の構成によれば、形態素解析に依存せず、翻訳に参照する例文パターンの候補を効率よく検索でき、例文パターンと文字列間の一対複数の対応が可能な編集距離を用いて、参照候補例文パターンと入力文の単語列間の相違値を少ない計算量で直接に算出することを可能となり、少ない計算量で精度よくマッチッグできると共に、その結果、少ない計算量で精度良く入力文を翻訳できる。
【００２０】
請求項４の構成によれば、形態素解析に依存せず、例文パターンと文字列間の一対複数の対応が可能な編集距離を用いて、参照候補例文パターンと入力文の単語列間の相違値を少ない計算量で直接に算出することを可能となり、少ない計算量で精度よくマッチッグできると共に、その結果、少ない計算量で精度良く入力文を翻訳できる。
【図面の簡単な説明】
【００２１】
【図１】本発明の実施形態に係るパターンマッチング装置の機能的な構成例を示すブロック図である。
【図２】形態素解析による誤解析例を示す図である。
【図３】形態素解析結果と例文パターンの固定項目との不整合による誤マッチングを表す説明図である。
【図４】変換部の処理手順を示すフローチャートである。
【図５】文字列間の距離計算のパスを表す説明図である。
【図６】算出部の処理手順を示すフローチャートである。
【図７】抽出部の処理手順を示すフローチャートである。
【図８】写像変換部の処理手順を示すフローチャートである。
【図９】本発明の実施形態に係る翻訳システムの機能的な構成例を示すブロック図である。
【図１０】翻訳装置のハードウェアの一構成例を表すブロック図である。
【図１１】例文パターンを入力文との類似度とカバー率の関係で範囲を絞る例を示すグラフである。
【図１２】効率化された算出部の処理手順を示すフローチャートである。
【図１３】算出部の効率化された処理手順の説明図である。
【図１４】最適候補が除外される入力文と例文パターンの対応関係を示す図である。
【図１５】選択部における句の評価処理の手順を示すフローチャートである。
【図１６】翻訳装置の要部構成の処理手順前半を示すフローチャートである。
【図１７】翻訳装置の要部構成の処理手順後半を示すフローチャートである。
【図１８】文字列間の距離計算の具体例１を表す説明図である。
【図１９】文字列間の距離計算の具体例２を表す説明図である。
【図２０】変換部３の例文パターンの変換アルゴリズムを表す式である。
【図２１】算出部４の文字列間の相違計算アルゴリズムを表す式である。
【図２２】抽出部５の写像抽出アルゴリズムを表す式である。
【図２３】写像変換部６の写像変換アルゴリズムを表す式である。
【図２４】算出部４aの文字列間の相違計算アルゴリズムを表す式である。
【発明を実施するための形態】
【００２２】
以下、本発明の最良の実施形態について、添付図面を参照しつつ説明する。まず、翻訳システム(後述する)に使用できるパターンマッチング装置について説明する。
【００２３】
図１は、本発明の実施形態に係るパターンマッチング装置４０の機能的な構成例を示すブロック図である。同図に示すように、パターンマッチング装置４０は、変換部３、算出部４、抽出部５及び写像変換部６を含んで構成される。
【００２４】
変換部３は、比較対象の例文パターンの文字列A(要素ai)の固定項目を、単語単位等から文字単位に変換した文字列B(要素ｂi)を得る。同時に、変換前後の対応関係Tを求める。
【００２５】
算出部４は、変換部３で変換された例文パターンの文字列B(要素ｂi)と、入力文の文字列S(要素sj)の相違としての距離値及び類似度を算出する(i,jは自然数)。
【００２６】
抽出部５は、算出部４で算出された所定の距離値D及び類似度Simを定める例文パターンの文字列Bと入力文の文字列S間の全ての対応関係(写像)
Fset(S)を抽出し、所定の距離D及び類似度Simと写像(対応関係)の集合Fset(S)を出力する。類似度は距離値から算出される。所定の距離D及び類似度として、例えば、最小距離Dmin及び最大類似度SIMmaxが用いられる。
【００２７】
写像変換部６は、抽出部５で抽出された候補の例文パターンの文字列Bと入力文の文字列S間の全ての対応関係(写像)、候補の例文パターンの文字列Aと変換後の例文パターンの文字列Bの対応関係を用いて、例文パターンの文字列Bと入力文の文字列S間の対応関係(写像)を、例文パターンの文字列Aと入力文の文字列S間の対応関係(写像)に変換する。
【００２８】
次に各部を詳細に説明する。まず、変換部３について詳述する。上述のように、変換部３で、比較対象の例文パターンの文字列A(要素ai)の固定項目を、単語単位等から文字単位に変換した文字の列B(要素ｂi)を得る。これは、計算の効率化のためである。後で、図２及び図３を参照して詳述する。
【００２９】
図４のフローチャートを参照して変換部３の文字単位への変換処理を説明する。なお、図４は、説明を分かりやすくするために、手順を簡略化しているが、図２０に、比較的正確な変換部３のアルゴリズムを表す式を示す。パターンA= a1a2…anの固定項目を文字単位で以下のように文字列Bとして表現する。
B=b1b2…bz
ここで、AとBの対応関係T(h,1)=i,T(h,2)=j
、ahがbi…bjに対応していることを表す。
【００３０】
まず、候補の例文パターンA＝ a1a2…anを入力し、i,jを初期値１とし、aiが固定項目かどうか判断する(ステップＳ１〜Ｓ３)。aiが固定項目である場合には、固定項目の長さ(文字の数)としてｋを求め、aiのｋ個の文字を、開始を示すT(i,1)から終了を示すT(i,2)まで変換する(ステップＳ４ｆ)。aiが可変項目である場合には、1対１の変換をする。次に、iをインクリメント(+1)し、iがn以下かどうか判断する(ステップＳ５〜Ｓ６)。以下の場合には、ステップＳ３〜Ｓ５の処理を繰り返し、ｎを超えると、処理を終了する。なお、入力文Sの文字列Sjは、変換処理結果と共に、算出部４にそのまま転送されるものとする。
【００３１】
次に、1対多の対応関係(写像)を許す文字列間の距離について説明する。比較対象の例文パターンの文字列B＝
b1b2…bzとし、入力文の文字列S=s1s2…smとする。ここで、例文パターンの文字列Bの要素biには二種あり、f(bi)=ｆ（固定項目）と、f(bi)=v(可変項目)である。文字列Bから文字列Sへの写像={(i,j)}が次の写像条件を満たすときに，文字列Bから文字列Sへの条件保存写像と呼ぶ。
【００３２】
写像条件は、
・f(bi)= f (固定項目)の場合は、1対1写像で、交差写像が禁止、
・f(bi)= v (可変項目)の場合は、１対多写像で、交差写像が禁止、
である。文字列Bから文字列Sへの写像重みとは、文字列要素biが文字列要素sjに置換する操作，文字列要素biが挿入する操作，文字列要素sjが脱落操作を用いて，上記の条件保存写像の条件に従って，文字列Bを文字列Sに変換するときに必要な操作の重みである．ここで，biがsjに置換させる操作の重みは置換重み、biを挿入する操作の重みが挿入重み，siを削除する操作の重みが脱落重みと呼ぶ．なお、本明細書で、１対多写像を1対複数写像ともいう。
【００３３】
写像条件は下記の通りである。
写像条件：任意の(i1,j1)
∈ M， (i2,j2) ∈ M
ここで、i1,j1は、bi1,sj1の意味であるが、簡単のため番号部分のi1,ｊ1のみで示す。Mは写像(集合)を表す。
1、文字列Bの要素biが固定項目の場合は、従来の文字列間の編集距離の写像条件である。
case f(bi1)=f or
f(bi2)=f, 
1.1、１対1写像である。
i1 = i2
iff j1 = j2.
1.2、交差写像禁止(左右関係を保存する条件)。
i1 < i2,
iff j1 < j2. 
2、文字列Bの要素biが可変項目の場合は、一方向(正方向)で1対n写像。
case f(bi1)=v or
f(bi2)=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. 
【００３４】
距離の定義は下記の通りである。
距離の定義：  文字列B＝b1b2…bzと文字列S=s1s2…sm間のすべでの条件保存写像に対して、最小な条件保存写像の写像重みがBとS間の条件保存距離と呼び、D(B,S)と書く。
【００３５】
以上述べた条件保存写像の写像と距離の定義により、部分文字列間の条件保存距離を記憶するマットリスクd(i,j)、及び動的計画法を用いて、計算可能である。もし、文字列Bの要素biが固定項目を表すf(bi)=fなら、従来の文字列間の編集距離と同じなので、距離d(i,j)は、図５(ａ)に示すように、矢印で示すパスを従来の計算方法で計算する。距離d(i,j)の計算式は、後述する図６のステップＳ１５fに示す。もし、文字列Bの要素biが可変項目を表す
f(bi)=Vなら、biが連続している部分文字列に写像することができるので、距離d(i,j)は、図５(ｂ)に示すようなパス(矢印で示す)をすべて計算する必要がある。距離d(i,j)の計算式は、後述する図６のステップＳ１５vに示す。ここで、図５(ａ)、(ｂ)の縦方向は、文字列Bの要素f(bi)で、横方向は文字列Sの要素f(sj)である。i,ｊは自然数で、
i=1,2・・・ｚ、j=1,2・・・ｍ
である。
【００３６】
次に、図６乃至図８のフローチャートを参照してパターンマッチング装置４０の算出部４の処理以降についての動作を説明する。なお、図６乃至図８は、説明を分かりやすくするために、手順を簡略化しているが、それぞれ、図２１乃至図２３に、比較的正確な算出部４、抽出部５及び写像変換部６のアルゴリズムを表す式を示す。
【００３７】
まず、比較対象の例文パターンの文字列B＝ b1b2…bzと、入力文の文字列S=s1s2…smが、算出部４に入力される(ステップＳ１１)。次に、部分文字列間の距離を記憶するマトリックスd(i,j)，対応関係の情報を記憶するマトリックスPathFlag(i,j)を初期化する。例えば、d(0,0)
= 0や、 PathFlag(i,j) = (0,0,0)などの処理が行われる。その処理後にi、jに１が入力され、文字列Bの要素biが固定項目かどうか判断される(ステップＳ１２、Ｓ１３)。
【００３８】
文字列Bの要素biが固定項目の場合には、次式で距離値が求められる(ステップＳ１５ｆ)。
d(i,j) = min { d(i-1,j-1) +w(bi,sj)
, d(i-1,j)+q, d(i,j-1)+r }
また、文字列Bの要素biが文字列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)
とする。
【００３９】
文字列Bの要素biが可変項目の場合は、次式で距離が求められる(ステップＳ１５v)。
d(i,j) = min { d(i-1,j-1) +w(bi,sj)
, d(i-1,j-2) +w(bi,sj-1…sj), … ,
d(i-1,0) +w(bi,s1…sj),
d(i-1,j)+q, d(i,j-1)+r }
この際に、要素biがsjに置換する場合は、
PathFlag(i,j) = PathFlag or
(0,0,1)
とし、要素biが要素sj-1…sjに置換する場合は
PathFlag(i,j) = PathFlag or
(0,0,1)
…
要素biが要素sj…sjに置換する場合は、
PathFlag(i,j) = PathFlag or
(0,0,1)
とする。要素biが脱落する場合は、
PathFlag(i,j) = PathFlag or
(1,0,0)
とする。要素sjを挿入する場合は、
PathFlag(i,j) = PathFlag or
(0,1,0)
とする。
【００４０】
ステップＳ１５ｆ,Ｓ１５ｆで距離値D
(Distance)が求められる際に、以下の計算式で類似度Simも算出される。
Sim = (1 - Distance/
(|S|*q+|B|*r)) 
ここで、 |S| が入力文の文字列Sの長さ、|B|が例文パターンAから変換された例文パターンの文字列Bの長さである。
【００４１】
文字列Bの要素biが固定項目または可変項目の処理が終了すると、ｊが1だけインクリメントされ、ｊがｍ以下かどうか判断される(ステップＳ１６、Ｓ１７)。ｊがｍより以下の場合には、jがmと等しくなるまで、ステップＳ１４乃至Ｓ１６が繰り返される。jがmより大きくなると、ｊを１とし、iが１だけインクリメントされ、iがｚ以下かどうか判断される(ステップＳ１８、Ｓ１９)。iがｚより大きくなるまで、ステップＳ１４乃至Ｓ１８が繰り返される。iがｚより大きくなると、算出部４の処理を終了する。
【００４２】
このようにして、文字列Bと文字列S間の距離d(i,j)と写像情報PathFlag(i,j)が求められて出力される。ここでは、距離d(i,j)の距離値Dが所定の値かどうか判断する。例えば、最小かどうかを判断する。即ち、最小値Dminを定める例文パターンの文字列Bと入力文の文字列S間の写像F1(B,S)としての写像情報PathFlag(i,j)が、便宜上、抽出部５での抽出処理の前処理として保存されるものとする。同様に、類似度Simが所定の値か判断される。例えば、最大かどうか判断される。即ち、最大類似度SIMmaxを定める例文パターンの文字列Bと入力文の文字列S間の写像F1(B,S)としての写像情報PathFlag(i,j)が、抽出部５での抽出処理の前処理として保存されるものとする。この前処理を算出部４の算出処理の後処理としても良い。
【００４３】
算出部４の処理が終了すると、抽出部5の写像の抽出処理に移る。算出部４から抽出部５に例文パターンの文字列Bと入力文の文字列S間の写像情報PathFlagと、ｚとｍの値が渡される(ステップＳ２１)。その後に、ステップＳ２２で次の処理をする。以下距離算出処理のパスを、逆に辿る処理が行われる。まず、文パターンの文字列B
の要素bibi+1…bnと入力文の文字列Sの要素sjsj+1…sm間の写像F1(B,S)をMatching(i,j)に保存する。すべでのMatching(i,j)に初期値を付与し、(z,m)
から開始され(ステップＳ２２)、すべてのマッチングが求められるまで以下の処理が実行される。即ち、
PathFlagS=NULL、 Fset(S)=NULL、
Push (z,m) into PathFlagS
とする。次に、PathFlagSが空かどうか判断し、空でなければ、PathFlagSから1要素を取り出して
(i,j)に入れる(ステップＳ２３、Ｓ２４)。(i,j)の値が(0,0)に等しいか判断する(ステップＳ２５)。(i,j)の値が(0,0)であれば、一つのマッチングが求められたので、写像Matching(0,0)をF1set(S)に追加し、ステップ２３に戻る(ステップＳ２８)。(i,j)の値が(0,0)でなければ、次のステップＳ２６に進む。
【００４４】
文字列Bの要素biが文字列Sの要素sjに置換する場合は、
Matching(i-1,j-1)=Mathing(i,j)+(i,j);
Push (i-1,j-1) into PathFlagS;
とする。要素biが脱落する場合は、
Matching(i-1,j)
=Mathing(i,j)+(i,0); 
Push (i-1,j) into PathFlagS; 
とする。要素sjを挿入する場合は、
Matching(i,j-1)
=Mathing(i,j)+(0,j); 
Push (i,j-1) into PathFlagS; 
とする。その処理後に、ステップ２３に戻り、PathFlagSが空でなければ、ステップＳ２４以降の処理を行い、PathFlagSが空になると、抽出処理を終了する。
【００４５】
このようにして、抽出部５では、例文パターンの文字列Bと入力文の文字列S間の写像F(B,S)の集合F1set(S)が求められ、例文パターンの文字列AとBの対応関係T(h)、n, z, mと共に出力され、写像変換部６に送られる。
【００４６】
写像変換部６では、例文パターンの文字列Bと入力文の文字列S間の写像F1(B,S)の集合F1set(S)、例文パターンの文字列AとBの対応関係T(h)、n,
z, mを入力とし、集合F1set(S)が空かどうか判断する(ステップＳ３１、Ｓ３２)。F1set(S)が空でなければ、F1set(S)から一つの写像を取り出し、すべでF1(B,S)の写像している項目biについて、
Mo(i)=biの像sjの番号
とし、
F2(A,S)=null  i=1
とする(ステップＳ３３)。 
【００４７】
次に、文字列Aの要素aiが固定項目かどうか判断する(ステップＳ３４)。文字列Aの要素aiが固定項目の場合、要素aiがすべての文字が写像している場合には、
M(i)=(i, Mo(T(i,1)), Mo(T(i,2))
) 
とし、そうではない場合は
M(i) = (i, 0, 0)
とする（ステップ３５ｆ）。文字列Aの要素aiが可変項目の場合には、以下の処理をする(ステップ３５ｖ）。bT(i,1)が写像していない場合には、
M(i) = (i,0,0) 
とする。bT(i,1)が写像している場合は、bT(i,1)がskに写像しているので、
k=Mo(T(i,1)
とする。skの右に連続にh個の文字が挿入された場合は、
k=k+h
とし、さらに、
M(i) = (i, Mo(T(i,1)), k ) 
とする。この場合、部分文字列sMo(T(i,1))…skは、aiに写像させる。
【００４８】
次に、１だけインクリメントし、iがｎ以下かどうか判断する(ステップＳ３６、Ｓ３７)。iがnと等しくなるまでステップＳ３４乃至Ｓ３７の処理が繰り返され、iがnより大きくなると、F2(A,S)に挿入情報を追加し，写像F2(A,S)をF2set(S)に追加する(ステップＳ３８)。その後に、ステップＳ３２に戻り、集合F1set(S)が空かどうか判断し、空でなければ、ステップＳ３３以降の処理を繰り返し、空であれば、処理を終了する。
【００４９】
以上述べたパターンマッチング装置４０では、例文パターンの文字列と、入力文の文字列間のマッチングについて説明したが、記号間のマッチングについて適用することも可能である。
【００５０】
上述したパターンマッチング装置４０は、例文パターンAの固定項目を文字単位に変換することにより、固定部分が1対1写像でき、効率よく計算可能である(変換しないと、1対多写像であるので、計算に手間がかかる)。提案した1対多写像を許す文字列間の条件保存写像、その写像に基づく編集距離及び計算アルゴリズムを用いて、例文パターンと入力文の文字列(形態素解析後の単語列ではない)間のマッチングが実現可能になる。かつ、形態素解析の誤解析問題とパターンの自動抽出問題を回避することが可能である。
【００５１】
図２に形態素解析の誤解析の例を示す。中国語の入力文例であるが、例１は、地名「竹松」の前の文字を結合させて人名として誤解析した例である。例２は、〜からという意味の文字を、その前の文字と結合させて「以前」という意味に誤解析した例である。このため、いずれの場合も本来の文の構造が崩れたので、正しくマッチングできなかったものである。
【００５２】
図３の例は、形態素解析結果と、例文パターンの固定項目の不整合による誤マッチングとなる場合である。同図に示すように、入力文Sが、「分かる よう に 報告 書 を 書いてください」であり、例文パターンAは「分かる ように ＮＰ を   書いてください」である。形態素解析の結果“よう/に”は、例文パターンの固定項目“ように”にマッチングできない。
【００５３】
次に、以上述べたパターンマッチング装置４０を更に改良したパターンマッチング装置４０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以上）を検索(抽出)する。この際に、入力文と候補の例文パターンの類似度およびカバー率の関係から対象とする候補の範囲を絞って候補の例文パターンを検索する。詳細は後述する。
【００６４】
変換部３は、検索部２で検索(抽出)された第1言語例の文パターン候補Aの固定項目を文字単位に変換し例文パターンBとすると共に、変換前後の対応関係Ｔを求める。
【００６５】
算出部４aは検索部２で検索された第1言語の入力文の単語/節の文字列Ｓと第1言語の例文パターン候補B間の相違として距離及び類似度を求める。類似度は距離値を用いて計算する。
【００６６】
抽出部５は、最小な相違値としての最小距離及び最大類似度が定める第1言語の入力文Sと第1言語の例文パターン候補B間の対応関係(変換写像)を求める。ここで、最小な相違値を与える例文パターン候補が複数の場合があるし，最小な相違値を決める例文パターン候補と入力文間の変換写像が複数ある場合もある。
【００６７】
写像変換部６は、抽出部５で抽出された第1言語の入力文Sと抽出された第1言語の変換後の例文パターンBの間の対応関係、及び例文パターン候補Aと変換後のパターンBの対応関係Ｔを用いて、第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の図１２の手順との相違部分を図１３に示す。いずれもbiが可変項目のd(i,j)の計算処理で、図６のステップＳ１５vと、図１２のステップＳ１５vaのうち、破線で囲った部分が相違する。図６のステップＳ１５vに示すd(i,j)の式、
d(i,j) = min { d(i-1,j-1) +w(bi,sj)
, d(i-1,j-2) +w(bi,sj-1…sj),
… , d(i-1,0) +w(bi,s1…sj),
d(i-1,j)+q, d(i,j-1)+r }
に対して、biが可変項目のとき，biは任意の部分文字列sjに写像しても重みは等しく０とする。即ち、重みｗを
w(bi,s1)
= w(bi,s2) = … = w(bi,sm) = w(bi,
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の要素biが文字列Sの要素sjに置換する場合、
要素biが要素sj-1…sjに置換する場合、…要素biが要素sj…sjに置換する場合の処理が複数あったものが、図１２のステップＳ１５vaでは、要素biが要素sjに置換する場合だけになった。この結果、算出部４の時間計算量がO(n3)からO(n2)に効率化される。なお、図１２のフローチャートは、説明を分かりやすくするために、手順を簡略化しているが、図２４に、比較的正確な算出部４aのアルゴリズムを表す式を示す。
【００８０】
次に、最適写像を選択する選択部７の詳細について述べる。
【００８１】
例えば、対象となるすべての写像について、置換項目(例文パターンAの項目に対応関係を持っている入力文Ｓの項目)が一番多い写像を選択すると、本来、候補として選出すべき例文パターンであっても、置換項目の項目数(マッチング数とも言う)が小さいとき、最適な候補の例文パターンとならない場合がある。
【００８２】
この場合の入力文と候補の例文パターンとの対応関例を図１４に示す。入力文Ｓに対して、同じ距離値を持つ例文パターンが複数ある(同図の場合２個)。その中には、一般論として、マッチングした項目数が多ければ多いほど、例文パターンが入力文とのマッチング具合はよいと考えられる。しかし、図１４に示すような例外がある。
【００８３】
同図は、最初の入力文Ｓと候補の例文パターンA1(NP1
は NP2 を 食べている)は、その対応関係では、例文パターンA1の名詞句NP2 対して入力文Ｓの「子供が食べ残したリンゴ」に正しく対応させており、距離値が０で、置換項目数(マッチング数)は５である。これに対し、入力文Ｓと候補の例文パターンA3(「NP1が食べ残したNP2を食べている」)間の距離値がゼロであり，その対応関係では、例文パターンの名詞句NP1
に対して入力文Ｓの「私は子供」を誤って対応させているが、置換項目数(マッチング数)は6である。
【００８４】
図１４を参照して述べたように、入力文Sの「私は子供」を例文パターンのNP1
にマッチング(対応)させているので、得られた候補としての例文パターンは間違ったものとなる。もし、「私は子供」が名詞句ではないと判断が可能なら、「私は子供」がNP1
にマッチングできなくなる。しかし、まだ、句の判断技術は未熟なので、実用的ではない。従って、句の判断技術を使用しない判断手段が必要である。最適な翻訳用候補の例文パターンを選択する基本的な考え方として、
(１) 例文パターンの可変部分にマッチングしている入力文の部分文字列は意味のある句である。
(２) マッチングした項目数ができるだけ多い。
(３) 距離値が小さい。
(４) 上記(１)(２)(３)の評価結果を融合して、総合的に判定する。
【００８５】
このような基本的な考え方に従った具体的例について説明する。まず、(１)項の例文パターンの可変部分に対応する句の評価処理手順について、図１５のフローチャートを参照して説明する。なお、本実施例の翻訳システム１０ｂは、公知の図示しない翻訳メモリ(ＴＭ)やパターン対訳辞書を備えているものとする。ここでは、これらの要素は、句の評価のために参照するが、翻訳自体は行わないものとする。
【００８６】
まず、句Ｐが翻訳メモリ(ＴＭ)に存在するか判断し、存在する場合には、句の評価値を1.0とする(ステップＳ５１a、Ｓ５１ｂ)。存在しないならば、パターン対訳辞書に句Ｐと完全にマッチングするパターンがあるか判断し、ある場合には、句の評価値を0.8とする(ステップＳ５２ａ、Ｓ５２b)。この場合、少なくとも句の構造は保証できる。パターン対訳辞書に句Ｐと完全にマッチングするパターンがないならば次に句を構成する単語だけで判断する。ここでは、単語の数が少ないほど評価を良くし、名詞を含む句は、良い評価をし、動詞等を含む句の場合には、評価を下げている。すなわち、句Ｐには、動詞、助詞、助動詞、感動詞があるか判断し、ない場合には、名詞を含むと判断し、句の評価値を1.0/(単語数)1/2とする(ステップＳ５３ａ、Ｓ５３b)。これらの品詞を含むとき、動詞等を含む句と判断し、句の評価値を0.5/(単語数)1/2
とし(ステップＳ５４)、句の評価手順を終了する。
【００８７】
先に述べた基本的な考え方を採用した最適な翻訳用候補の写像を選択するための計算例について説明する。
・入力文と翻訳用候補の例文パターン間のマッチング集合F2set(S)にある各マッチングF2(A,S)について、Fun1(F2(A,S))を計算する。
【００８８】
次に、Fun1の計算方法について説明する。
Fun1は、次式で与えられる。
Fun1(F2(A, S)) = 
((Σ句の評価値)/句の数 * k1  +  
+   match-Num * match-Num /|A| *
k2 
+   (1 - Distance/
(|S1|+|B|))* (|S|+|A|)/2
*f1(パターンAのマッチングした固定項目の数) * f2（パターンAのマッチングした可変項目の数）
ここで、例えば，K1 =10, k2=3、
|S1| がSの長さ、|S|がF2(A,S)において、写像している項目の数と挿入した項目の数(連続挿入した部分が一つの挿入項目とする)の和、|A|がパターンの可変項目個数と固定項目個数の和、
match-Num が写像重みがゼロの写像の数（注意：F2(A,S)の写像個数である、F1(B,S)の写像個数ではない）、   |B|がＡから変換されたパターンBの長さである。
f1 = 0 ： マッチングした固定項目(写像重みがゼロの場合)の個数＜定数
; other 1
f2 = 0 ： マッチングしていない可変項目がある場合は 0
; other 1
上記f1、f2は、0か1の値をとり、f1の場合、例文パターンのマッチングした固定項目(写像重みがゼロの場合)の個数が定数より小さいとき０であり、それ以外は１である。f2の場合、例文パターンにマッチングしていなかった可変項目があるとき０であり、それ以外のとき１である。
【００８９】
F2set(S)にある任意の写像F2(A,S)に対して、以下の通りとする。
ここで、G3,G4は定数である。
1) もし(2 - Sim(A,S)/Cov(A,S))
< G3 and Fun1(F2(A,S))<G4 ，then   該写像候補を削除する。
2) すべての削除された写像候補に対して、最大なFun1(F2(A,S))が定める写像候補F2(A,S)が最適写像とする。
【００９０】
次に、以上述べた改良された構成要素を含む本実施形態における翻訳装置２０aの要部の動作を図１６及び図１７のフローチャートを参照して説明する。
【００９１】
入力文Ｓが検索部２に入力されと、検索部２は、入力文Ｓに対応する例文パターン候補Asetを検索する（ステップＳ４１、Ｓ４２）。この際、
(１) Sim(S,A)>=Con(S,A); 
(２) Sim(S,A)<2*Cov(S,A) ; 
(３) 例文パターンの個数を所定の最大値に限定 、
となる条件で、例文パターンの候補範囲を絞り込んで検索を行い、
F1set(S)=F1set(S,A)=NULL; Dmin
=Dmax; SIMmax=-1;
とする。
【００９２】
次に、例文パターン候補Asetから１つの例文パターン候補Aが取り出され、その固定項目(固定部分)を単語単位から文字単位に変換し、変換後の例文パターンの文字列をBとする(ステップＳ４４)。変換後の例文パターンBと入力文Sの間の距離D及び類似度Simが算出部４aにより求められる（ステップＳ４５）。さらに、距離Dが最小値Dmin以下かどうか判断される（ステップＳ４６d）。距離Dが最小値Dmin以下の場合には、抽出部５で、前処理として、距離Dminが定める入力文Sと例文パターンBの間の対応関係(写像)F1(A,S)が写像情報として求められ保存される（ステップＳ４７d）。一方、類似度Simが最大値SIMmax以上かどうか判断される（ステップＳ４６s）。最大値SIMmax以上の場合には、抽出部５で、前処理として、類似度SIMmaxが定める入力文Sと例文パターンBの間の対応関係(写像)F1(A,S)が写像情報として求められ保存される（ステップＳ４７s）。距離Dが最小値Dminより大きい場合、類似度Simが最大値SIMmaxより小さい場合及びステップＳ４７d、Ｓ４７sで写像情報の保存処理がされた場合には、例文パターン候補Asetの全ての例文パターンが処理済みかどうか判断される（ステップＳ４８）。全ての例文パターンが処理済でなければ、ステップＳ４３乃至Ｓ４７の処理が、全ての例文パターンの処理済判断となるまで繰り返される。
【００９３】
例文パターン候補Asetの全ての例文パターンが処理済みの判断となると、抽出部５で、距離Dminが定める例文パターンBと入力文Sの間での全ての写像(対応関係)F1set(S)が求められ、即ち、
F1set(S)= F1set(S)+ F1(B,S)
とされる（ステップＳ４９）。更に写像変換部６で、距離Dminが定める入力文Sと例文パターンBの間のすべての写像(対応関係)F1set(S)から対応しているSとAの間のすべての写像(対応関係)F2set(S)に変換される(ステップＳ５０)。
【００９４】
一方、類似度SIMmaxが定める入力文Sと例文パターンBの間のすべての写像(対応関係)F1(B,S)が抽出部５で求められ、即ち、
F1set(S)= F1set(S)+ F1(B,S)
とされる（ステップＳ５１）。更に写像変換部６で、類似度SIMmaxが定める入力文Sと例文パターンBの間のすべての写像(対応関係)F1set(S)から対応しているSとAの間のすべての写像(対応関係)F2set(S)に変換される(ステップＳ５２)。次に、選択部６で、求められたF2set(S)の中から最適な写像を求められ、最適な写像がFres(A,S)に入れられる（Ｓ５３）。
【００９５】
次に、図１８及び図１９を参照して具体的な例を説明する。
【００９６】
F1(A,S)⇒F2(A,S)
図１８に示す具体例１は、入力文Sが、
入力文S = 私は子供が食べ残したリンゴを食べている
であり、その文字列を文字単位で表の横方向に並べて配置している。また、例文パターンA が、
例文パターンA = NP1  は NP2 を  食べている[食べる
て いる]
であり、例文パターンAの固定項目を文字単位に変換した文字列を表の縦方向に並べて配置し、距離値は０で、１つのマッチング結果が得られた。即ち、
F1(B,S) = { (1,1), (2,2),
(3,3), (4,14), (5,15),(6.16),(7,17),(8,18),(9,19) }
である。右辺のカッコ内は、(例文パターンの要素番号,入力文の要素番号)を示す。
T(i)とF1(B,S)を用いてFset(A,S)を求める。即ち、
F2(A,S) = { (1,1,1), (2,2,2),
(3,3,13), (4,15,19)
である。右辺のカッコ内は、(例文パターンの要素番号,入力文の開始要素番号,
入力文の終了番号)を示す。
【００９７】
この具体例１から明らかなように、NP2の可変項目(可変部分)が、1対多写像で正確にマッチングできると共に、固定項目(固定部分)も、文字単位で正確にマッチングできるため、写像変換した例文パターンの文字列と入力文の文字列間の写像（対応関係）が、形態素解析に依存することなく、正確にマッチングできていることを示している。
【００９８】
図１９は、具体例２を示し、具体例１と同じ内容の中国語の例を示す。
【００９９】
以上述べたように、本実施形態に係る翻訳システムによれば、形態素解析やパターン抽出技術に依存せず、翻訳に参照する例文パターンの候補を効率よく検索でき、パターンと文字列間の一対多の対応が可能な編集距離を用いて、参照候補例文パターンと入力文の文字列間の相違値を少ない計算量で直接に算出することを可能となり、精度よく参照候補例文パターンと入力文の文字列間の対応関係を求めることができる。更に、求められた複数の翻訳用パターン候補から最適な翻訳参照パターンを抽出することができる。その結果、少ない計算量で精度良く入力文を翻訳できる。
【０１００】
以上本発明の好ましい実施例について詳述したが、本発明は係る特定の実施例に限定されるものではなく、特許請求の範囲に記載された本発明の要旨の範囲内において、種々の変形、変更が可能である。
【０１０１】
上記実施形態では、外部記憶装置はハードディスク（Hard Disk）で構成されるとして説明したが、これに限定されるわけではなく、例えば、フレキシブルディスク、ＣＤ−ＲＯＭ（Compact Disc Read Only Memory）、ＤＶＤ−ＲＯＭ（Digital Versatile Disk Read Only Memory）、ＤＶＤ−ＲＡＭ（Digital Versatile Disk
Random Access Memory）、ＭＯ（magneto-optic）、及び、フラッシュメモリ（flash memory）で構成される実施形式を採用できる。
【符号の説明】
【０１０２】
１…解析部                          ２…検索部(検索手段)          
３…変換部                          ４、４a…算出部（算出手段）         
５…抽出部(抽出手段)                ６…写像変換部                      
７…選択部(選択手段)                ８…翻訳部(翻訳手段)          
９…記憶部(記憶手段)
１０…入力装置                      ３０…出力装置                
２０a…翻訳装置                     ４０、４０a…パターンマッチング装置
１００…翻訳システム      
１００１…演算部                    １００２…ＲＯＭ                  
１００３…ＲＡＭ                    １００４…外部記憶部              
１００５…バス                      
【図１】
0005521670.tif 000002
【図２】
0005521670.tif 000003
【図３】
0005521670.tif 000004
【図４】
0005521670.tif 000005
【図５】
0005521670.tif 000006
【図６】
0005521670.tif 000007
【図７】
0005521670.tif 000008
【図８】
0005521670.tif 000009
【図９】
0005521670.tif 000010
【図１０】
0005521670.tif 000011
【図１１】
0005521670.tif 000012
【図１２】
0005521670.tif 000013
【図１３】
0005521670.tif 000014
【図１４】
0005521670.tif 000015
【図１５】
0005521670.tif 000016
【図１６】
0005521670.tif 000017
【図１７】
0005521670.tif 000018
【図１８】
0005521670.tif 000019
【図１９】
0005521670.tif 000020
【図２０】
0005521670.tif 000021
【図２１】
0005521670.tif 000022
【図２２】
0005521670.tif 000023
【図２３】
0005521670.tif 000024
【図２４】
0005521670.tif 000025