(57)【要約】【課題】この発明の実施の形態は、アラインされていないエントリをアラインされたエントリに変換することによって発音辞書を構築するための方法およびシステムを開示する。【解決手段】アラインされていないエントリおよびアラインされたエントリは、単語のセットと、単語のセットに対応する発音のセットとを含む。上記方法は、単語ごとに、単語と発音予測との間に１対１の対応が存在するように、発音予測を求め、各発音予測を発音のサブセットにマッピングして、各発音予測が発音のサブセットにアラインされた予測−発音マップを作成し、単語と発音予測との１対１の対応を使用して、予測−発音マップに基づいてアラインされたエントリを求めることによって、アラインされたエントリ内の各単語を、発音のサブセットとアラインする。【選択図】図２
2011209704.tif 000002
【特許請求の範囲】
【請求項１】
アラインされていないエントリをアラインされたエントリに変換することによって発音辞書を構築するための方法であって、前記アラインされていないエントリおよび前記アラインされたエントリは、単語のセットと、前記単語のセットに対応する発音のセットとを含み、前記アラインされたエントリ内の各単語は、前記発音のセットからの発音のサブセットとアラインされ、前記方法は、
前記単語のセット内の前記単語ごとに、前記単語と発音予測との間に１対１の対応が存在するように、前記発音予測を求めるステップと、
前記各発音予測を前記発音のサブセットにマッピングするステップであって、前記各発音予測が前記発音のサブセットとアラインされた予測−発音マップを作成する、マッピングするステップと、
前記単語と前記発音予測との間の前記１対１の対応を使用して、前記予測−発音マップに基づいて前記アラインされたエントリを求めるステップと、
を含み、前記方法の前記ステップはプロセッサによって実行される、方法。
【請求項２】
前記発音および前記予測は、音節の連結として表され、前記方法は、
Ａ文字列を形成する前記発音のセット内の前記発音の前記音節を連結するステップであって、前記発音の前記音節は、Ａチャンクを形成する、連結するステップと、
Ｂ文字列を形成する前記発音予測の音節を連結するステップであって、前記発音予測の前記音節は、Ｂチャンクを形成する、連結するステップと、
前記Ａ文字列内の文字と前記Ｂ文字列内の文字との間のアラインメント経路を求めるステップと、
前記アラインメント経路に基づいてＡチャンク対Ｂチャンクマップを求めるステップと、
前記Ａチャンク対Ｂチャンクマップに基づいて前記予測−発音マップを求めるステップと、
をさらに含む、請求項１に記載の方法。
【請求項３】
前記Ａチャンク対Ｂチャンクマップは、１対１のチャンクマップである、請求項２に記載の方法。
【請求項４】
前記Ａチャンク対Ｂチャンクマップは、１対多のチャンクマップであり、前記方法は、
前記Ａチャンク対Ｂチャンクマップを１対１のチャンクマップに分解するステップをさらに含む、請求項２に記載の方法。
【請求項５】
前記分解するステップは、
前記１対多のチャンクマップが許容するＡチャンク対Ｂチャンクマッピングの１対１のチャンクマップのデカルト積を求めるステップと、
前記各１対１のチャンクマップの累積編集距離を計算するステップと、
最も小さい累積編集距離を有する前記１対１のチャンクマップを選択するステップと、
をさらに含む、請求項４に記載の方法。
【請求項６】
前記各１対１チャンクマップ内の前記マッピングごとに編集距離を求めるステップであって、前記各１対１チャンクマップの編集距離を生成する、編集距離を求めるステップと、
前記各１対１チャンクマップの前記編集距離を合算することによって前記累積編集距離を求めるステップと、
をさらに含む、請求項５に記載の方法。
【請求項７】
内部辞書から前記発音予測を選択するステップをさらに含む、請求項１に記載の方法。
【請求項８】
書記素対音素変換器を使用して前記発音予測を求めるステップをさらに含む、請求項１に記載の方法。
【請求項９】
前記単語の正書法形態を、前記単語の前記発音予測として選択するステップをさらに含む、請求項１に記載の方法。
【請求項１０】
前記Ａ文字列内の前記文字と、前記Ｂ文字列内の前記文字との間の、挿入コスト、削除コスト、および置換コストを表すコスト行列を求めるステップと、
前記コストを最小にする要素のインデックスを表すインデックス行列を求めるステップと、
前記インデックス行列に基づいて前記アラインメント経路を求めるステップと、
をさらに含む、請求項２に記載の方法。
【請求項１１】
前記アラインメント経路は、前記インデックス行列内の右下端の要素から開始し、前記コストを最小にする前記要素の前記インデックスを辿ることによって後方にリトレースされる経路である、請求項１０に記載の方法。
【請求項１２】
前記インデックス行列内の前記要素は、前記削除コストを表し、前記方法は、
前記アラインメント経路上に、２つのアスタリスクを水平に並べて配置するステップをさらに含む、請求項１１に記載の方法。
【請求項１３】
前記インデックス行列内の前記要素は、前記挿入コストを表し、前記方法は、
前記アラインメント経路上に、２つのアスタリスクを垂直に並べて配置するステップをさらに含む、請求項１１に記載の方法。
【請求項１４】
前記インデックス行列内の前記要素は、前記置換コストを表し、前記方法は、
前記アラインメント経路上に、２つのアスタリスクを対角線状に並べて配置するステップをさらに含む、請求項１１に記載の方法。
【請求項１５】
前記アラインされたエントリは、単語−発音マッピングのセットを含み、前記方法は、
閾値未満の確率を有する単語−発音マッピングを除去するステップをさらに含む、請求項１に記載の方法。
【請求項１６】
前記単語のセット内の前記単語ごとに、頻度カウントｃ（ｗ，ｐ）を求めるステップであって、前記頻度カウントは、単語ｗと発音ｐとの間のマッピング数を示す、頻度カウントを求めるステップと、
【数１】
2011209704.tif 000004
にしたがって、前記頻度カウントｃ（ｗ，ｐ）および発音ｑを有する前記単語の頻度カウントに基づいて、前記単語ｗと前記発音ｐとの間の前記単語−発音マッピングの確率Ｐ（ｗ，ｐ）を求めるステップと、
をさらに含む、請求項１５に記載の方法。
【請求項１７】
アラインされていないエントリのセットから発音辞書を構築するための方法であって、アラインされていないエントリは、単語のセットと、前記単語のセットに対応する発音のセットとを含み、前記方法は、
前記各アラインされていないエントリをアラインされたエントリに反復的に変換するステップであって、前記アラインされたエントリ内の各単語は、前記発音のセットからの発音のサブセットとアラインされる、変換するステップと、
前記各アラインされたエントリを内部辞書に格納するステップと、
前記内部辞書を前記発音辞書として出力するステップと、
を含み、前記方法の前記ステップはプロセッサによって実行される、方法。
【請求項１８】
前記変換するステップは、
前記単語のセット内の前記単語ごとに、前記単語と発音予測との間に１対１の対応が存在するように、前記発音予測を求めるステップと、
前記各発音予測を前記発音のサブセットにマッピングするステップであって、前記各発音予測が前記発音のサブセットとアラインされた予測−発音マップを作成する、マッピングするステップと、
前記単語と前記発音予測との間の前記１対１の対応を使用して、前記予測−発音マップに基づいて前記アラインされたエントリを求めるステップと、
をさらに含む、請求項１７に記載の方法。
【請求項１９】
前記アラインされたエントリは、単語−発音マッピングのセットを含み、前記方法は、
閾値未満の確率を有する単語−発音マッピングを除去するステップをさらに含む、請求項１７に記載の方法。
【請求項２０】
アラインされていないエントリをアラインされたエントリに変換することによって発音辞書を構築するためのシステムであって、前記アラインされていないエントリおよび前記アラインされたエントリは、単語のセットと、前記単語のセットに対応する発音のセットとを含み、前記アラインされたエントリ内の各単語は、前記発音のセットからの発音のサブセットとアラインされ、前記システムは、
前記単語のセット内の前記単語ごとに、前記単語と発音予測との間に１対１の対応が存在するように、前記発音予測を求めるための発音予測サブモジュールと、
前記各発音予測を前記発音のサブセットにマッピングして、前記各発音予測が前記発音のサブセットにアラインされた予測−発音マップを作成するための動的プログラミングサブモジュールと、
前記単語と前記発音予測との間の前記１対１の対応を使用して、前記予測−発音マップに基づいて前記アラインされたエントリを求めるように構成されるプロセッサと、
を備える、システム。
【発明の詳細な説明】
【技術分野】
【０００１】
この発明は、包括的には自動音声認識（ＡＳＲ）に関し、詳細にはＡＳＲのための発音辞書を構築することに関する。
【背景技術】
【０００２】
情報検索（ＩＲ）システムは、通常、地理的関心地点（ｐｏｉｎｔｓ  ｏｆ  ｉｎｔｅｒｅｓｔ）（ＰＯＩ）、または音楽アルバムの題名のような、アイテムの大規模なリストを含む。ユーザから提供されるクエリに応答して、ＩＲシステムは、クエリに最も一致した結果リストを検索する。この結果、リストは、様々な要因にしたがって順序付けすることができる。アイテムの入力リスト、クエリ、および結果リストは、通常、単語の形態でテキストによって表される。
【０００３】
発話クエリは、ユーザが、たとえば機械を運転または操作している間、キーボードをユーザインタフェースの一部として使用することができないか、またはユーザが物理的に障害を有する環境において使用される。この場合、ユーザインタフェースは、マイクロフォンを含み、自動音声認識器（ＡＳＲ）が使用されて発話が単語に変換される。
【０００４】
ＡＳＲは、２つの基本データ構造、すなわち単語の発音辞書および単語の言語モデルを使用する。一般に、ＩＲシステムは、単語を音素として音声的に表す。たとえば、ＲＥＳＴＡＵＲＡＮＴは、「Ｒ  ＥＨ  Ｓ  Ｔ  Ｒ  ＡＡ  Ｎ  Ｔ」として表される。音素は、特定の言語における音の基本単位を指す。音素は、強勢符号、音節境界、および単語がどのように発音されるかを示す他の表記を含むことができる。
【０００５】
発音辞書は、ＡＳＲシステムの語彙における単語ごとに、単語に関する１つ、または場合によってはいくつかの発音を規定する。ＩＲシステムによって検索されるアイテムのそれぞれは、対応する発音を有する。多くの場合、これらのアイテムの発音は、単語のデータベースを使用して提供される。しかしながら、ほとんどの場合、発音辞書は、図１に示すものに類似したアラインされていない入力ファイルの形態である。
【０００６】
入力ファイルは、エントリのセット１１０を含み、ここで各エントリは、対応する発音１２０を有する単語のセット１１５を含む。しかしながら、単語は、対応する発音にアラインされていない。
【０００７】
従来の方法は、各単語を登場順で各発音にマッピングすることによってアラインを実行する。図１に示す例の場合、その方法は、単語「ＨＥＲＩＴＡＧＥ」を発音「ｈＥ｜ｒＩ｜ｔＩｄＺ」にマッピングし、単語「ＥＬＥＭＥＮＴＡＲＹ」を発音「Ｅ｜ｌ＠｜ｍＥｎ｜ｔ＠｜ｒｉ」にマッピングし、単語「ＳＣＨＯＯＬ」を発音「ｓｋｕｌ」にマッピングする。しかしながら、この方法は、以下のようないくつかの重要な状況において機能しない。
【０００８】
単語より発音が多い：図１の第２行において、発音「ｂｉ」および「ｄＺｉｚ」は、第１の単語「ＢＧ’Ｓ」にマッピングされなくてはならない。
【０００９】
発音より単語が多い：第３行において、単語「ＣＡＲＲＥＲ」は、対応する発音を有していないので、マッピングされない状態にしておくべきである。
【００１０】
エントリに誤りがある：第４行において、発音「ｂＡｒ｜ｂ＠｜ｋｊｕ」における音節は、単語「ＢＡＲ  Ｂ  ＱＵＥ」にマッピングする３つの別個の発音としておかれる代わりに、誤って１つの単語にマージされている。
【発明の概要】
【発明が解決しようとする課題】
【００１１】
したがって、単語を発音とアラインするための方法を提供するとともに、音声認識器に入力するのに適した発音辞書を作成することが必要とされている。
【００１２】
主題発明の目的は、単語を発音にアラインして発音辞書を作成するための方法を提供することである。
この発明のさらなる目的は、単語を自動的にアラインする方法を提供することである。
この発明のさらなる目的は、自動音声認識器への入力に適した最終発音辞書を作成することである。
【課題を解決するための手段】
【００１３】
この発明の実施の形態は、単語の正書法表現が、対応する発音の形態と大幅に異なり、これがマッピングエラーにつながるという認識に基づく。したがって、この発明の実施の形態は、単語を発音に直接マッピングする代わりに、単語ごとに、単語と発音予測との間に１対１の対応が存在するように、発音予測を求め、次に、発音予測を発音にマッピングする。この発明の実施の形態は、２つの表音形態間のマッピングは、正書法と表音形態との間のマッピングよりも正確であるという別の認識を利用する。
【００１４】
この発明の実施の形態の１つは、アラインされていないエントリをアラインされたエントリに変換することによって発音辞書を構築するための方法であって、アラインされていないエントリおよびアラインされたエントリは、単語のセットと、単語のセットに対応する発音のセットとを含み、アラインされたエントリ内の各単語は、発音のセットからの発音のサブセットとアラインされ、上記方法は、
単語のセット内の単語ごとに、単語と発音予測との間に１対１の対応が存在するように、発音予測を求めるステップと、
各発音予測を発音のサブセットにマッピングするステップであって、各発音予測が発音のサブセットとアラインされた予測−発音マップを作成する、マッピングするステップと、
単語と発音予測との間の１対１の対応を使用して、予測−発音マップに基づいてアラインされたエントリを求めるステップと、
を含む、方法を開示する。
【００１５】
この発明の実施の形態の別の形態は、アラインされていないエントリのセットから発音辞書を構築するための方法であって、アラインされていないエントリは、単語のセットと、単語のセットに対応する発音のセットとを含み、上記方法は、
各アラインされていないエントリをアラインされたエントリに反復的に変換するステップであって、アラインされたエントリ内の各単語は、発音のセットからの発音のサブセットとアラインされる、変換するステップと、
各アラインされたエントリを内部辞書に格納するステップと、
内部辞書を発音辞書として出力するステップと、
を含み、方法のステップはプロセッサによって実行される、方法を開示する。
【００１６】
この発明の実施の形態のさらに別の形態は、アラインされていないエントリをアラインされたエントリに変換することによって発音辞書を構築するためのシステムであって、アラインされていないエントリおよびアラインされたエントリは、単語のセットと、単語のセットに対応する発音のセットとを含み、アラインされたエントリ内の各単語は、発音のセットからの発音のサブセットとアラインされ、上記システムは、
単語のセット内の単語ごとに、単語と発音予測との間に１対１の対応が存在するように、発音予測を求めるための発音予測サブモジュールと、
各発音予測を発音のサブセットにマッピングして、各発音予測が発音のサブセットとアラインされた予測−発音マップを作成するための動的プログラミングサブモジュールと、
単語と発音予測との間の１対１の対応を使用して、予測−発音マップに基づいてアラインされたエントリを求めるように構成されるプロセッサと、
を備える、システムを開示する。
【発明の効果】
【００１７】
この発明によれば、単語を発音にアラインして発音辞書を作成するための方法を得ることができる。
【図面の簡単な説明】
【００１８】
【図１】アラインされていないエントリを含む従来の入力ファイルのブロック図である。
【図２】この発明の実施の形態１による、アラインされていないエントリをアラインされたエントリに変換するための方法のフローチャートである。
【図３】図１に示すアラインされていないエントリに対応するアラインされたエントリのテーブルである。
【図４】この発明の実施の形態１による、発音辞書を確定するための方法のフローチャートである。
【図５】この発明の実施の形態１による変換モジュールのフローチャートである。
【図６Ａ】アラインされていないエントリのテーブルである。
【図６Ｂ】アラインされていないエントリのテーブルである。
【図７Ａ】単語の発音予測のテーブルである。
【図７Ｂ】単語の発音予測のテーブルである。
【図８Ａ】発音および音節のテーブルである。
【図８Ｂ】発音および音節のテーブルである。
【図９Ａ】チャンクおよび文字列編成の例のブロック図である。
【図９Ｂ】チャンクおよび文字列編成の例のブロック図である。
【図１０】この発明の実施の形態１による動的プログラミング例の結果としてのアラインメント経路のグラフである。
【図１１】この発明の実施の形態１によるＡ文字対Ｂチャンクマッピングのテーブルである。
【図１２】この発明の実施の形態１によるＡ文字対Ｂチャンクマップを分解するフローチャートである。
【図１３Ａ】単語およびアラインされた音節のテーブルである。
【図１３Ｂ】単語およびアラインされた音節のテーブルである。
【図１４Ａ】プルーニングされていない辞書の例である。
【図１４Ｂ】プルーニングされた辞書の例である。
【図１５】この発明の実施の形態１による、アラインメント経路を求めるための擬似コードである。
【発明を実施するための形態】
【００１９】
実施の形態１．
システム概観
この発明の実施の形態は、単語の正書法表現が発音の対応する形態と大幅に異なり、これが単語を発音にマッピングする際のエラーにつながるという認識に基づく。したがって、この発明の実施の形態では、単語を発音に直接マッピングする代わりに、単語と発音予測との間に１対１の対応が存在するように単語ごとに発音予測が求められ、発音予測が発音にマッピングされる。この発明の実施の形態は、２つの表音形態間のマッピングが、正書法形態と表音形態との間のマッピングよりも正確であるという別の認識を利用する。
【００２０】
図２は、この発明の実施の形態１による、アラインされていないエントリ２１０をアラインされたエントリ２２０に変換するための方法を示している。この方法は、この技術分野において既知のプロセッサ２０１を使用して、変換モジュール２００によって実行される。アラインされていないエントリは、単語のセット２１２および単語のセットに対応する（２１６）発音のセット２１４を含む。しかしながら、アラインされていないエントリ内の単語および発音は、アラインされていない。本明細書において定義されるように、単語のセットは、単語のセット内の各単語が、発音のセットからの発音のサブセットにマッピングされている場合、その発音のセットにアラインされている。様々な実施形態において、発音のサブセットは、０個以上の発音を含む。
【００２１】
図３は、図１に示すアラインされていないエントリの例に対応するアラインされたエントリ２２０の例を示している。左側の列３０１の単語は、右側の列３０２からの発音にアラインされている。この発明の様々な実施形態では、アラインされていないエントリは、等しい数または異なる数の単語および発音を含む。
【００２２】
上述した目的によれば、発音予測２３５は、単語と発音予測との間に１対１の対応が存在するように、単語のセットからの単語ごとに求められる（２３０）。各発音予測は、発音のサブセットにマッピングされ（２４０）、各発音予測が発音のサブセットに位置合わされた、予測−発音マップ２４５が作成される。アラインされたエントリ内の単語が発音にアラインされる（２２５）ように、１対１の対応２５５に基づいて、発音予測−発音マップから、アラインされたエントリが求められる（２５０）。アラインされたエントリ内の単語は、アラインされていないエントリ内の単語と同一である。しかしながら、アラインされたエントリ内の発音は、アラインされていないエントリ内の発音と異なる可能性がある。様々な実施形態において、下記でより詳細に説明するように、発音は、より小さな成分、たとえば音節に分割され、それにしたがって再配列される。
【００２３】
発音辞書の確定
図４は、この発明の実施の形態１の１つによる、発音辞書４７０を構築するための方法４００を示している。この方法は、メモリ（図示せず）内に格納されているアラインされていないエントリのセット４１０にわたって反復する。各アラインされていないエントリ２１０は、変換モジュール２００によってアラインされたエントリ２２０に変換される。アラインされたエントリは、反復４６０中、本方法によって維持される内部辞書４３５に追加される（４３０）。４４０において全てのアラインされていないエントリが変換された（４４５）とき、内部辞書は、発音辞書４７０として出力される。１つの実施形態では、出力の前に、プルーニングモジュール４５０が、低精度の単語−発音マッピングが除去されるように内部辞書をプルーニングする。
【００２４】
図５は、変換モジュールの例を示している。１つの実施形態では、変換モジュールは、発音予測サブモジュール５１０と、音節分解サブモジュール５２０と、動的プログラミング（ＤＰ）サブモジュール５３０と、編集距離（ＥＤ）サブモジュール５４０とを含む。変換モジュールの動作は、以下の例を用いて説明される。
【００２５】
図６Ｂは、アラインされていないエントリの例を示している。アラインされていないエントリ内の単語は、「Ｎｅｗ  Ｙｏｒｋ  ＮＹ  Ｅｘｓｐｒｅｓｓｏ」であり、対応する発音は、「ｎｕ  ｊＯｒｋ  ｎｕ  ｊＯｒｋ  Ｅｋ｜ｓｐｒＥ｜ｓｏ」である。この例では、発音の数は単語の数よりも多い。
【００２６】
図６Ａは、図６Ｂと同じ例がシンボルで書かれたものを示している。ここで、発音ｐｉは、音節の連結ＳｊＳｋとして表される。変数ｉは、発音のセットにおける発音のインデックスであり、変数ｊおよびｋは、発音の音節のインデックスである。
【００２７】
発音予測サブモジュール
発音予測サブモジュールは、アラインされていないエントリ内の単語ごとに発音予測を作成する。様々な実施形態において、発音予測は、いくつかのソースのうちの少なくとも１つから導出される。第１のソースは、内部辞書４３５である。発音予測サブモジュールは、内部辞書内にその単語のための単語−発音マップが存在するか否かを判断し、その単語の頻度の最も高い発音をその単語の発音予測として選択する。その目的のために、１つの実施形態は、これまでに単語−発音マップが発生した回数を示す頻度カウントｃ（ｗ，ｐ）を含む。発音が発音予測として選択される場合、単語−発音マップの頻度カウントは、たとえば１だけ増加される。
【００２８】
付加的にまたは代替的に、１つの実施形態は、書記素対音素（Ｇ２Ｐ）エンジン５５０を使用して単語の発音予測を求める。この実施形態は、単語がまれに、かつ／または変換２００の開始時に発生する場合に有利である。たとえば、１つの実施形態は、論理的推論（ｓｅｑｕｉｔｕｒ）Ｇ２Ｐエンジン５５０を使用する。これは、アーヘン工科大学コンピューターサイエンス学部において開発されたデータ駆動型書記素対音素変換器である。参照により本明細書に援用される、Ｍ．ビザーニ（Ｍ．Ｂｉｓａｎｉ）およびＨ．ナイ（Ｈ．Ｎｅｙ）「書記素対音素変換のための結合シーケンスモデル（Ｊｏｉｎｔ−Ｓｅｑｕｅｎｃｅ  Ｍｏｄｅｌｓ  ｆｏｒ  Ｇｒａｐｈｅｍｅ−ｔｏ−Ｐｈｏｎｅｍｅ  Ｃｏｎｖｅｒｓｉｏｎ）」（Ｓｐｅｅｃｈ  Ｃｏｍｍｕｎｉｃａｔｉｏｎ，  Ｖｏｌｕｍｅ  ５０，  Ｉｓｓｕｅ  ５，  Ｍａｙ  ２００８，  Ｐａｇｅｓ  ４３４−４５１）を参照されたい。
【００２９】
付加的にまたは代替的に、１つの実施形態は、単語の正書法形態を単語の発音予測として使用する。図７Ａおよび図７Ｂは、発音予測の例を示している。
【００３０】
音節分解サブモジュール
音節分解サブモジュール５２０は、アラインされていないエントリ内の発音を、個々の音節に編成する。音節分解は、誤りのあるエントリの問題、すなわち、発音の音節が１つの単語に誤ってマージされる問題に対処する。発音を音節に編成することによって、この問題を訂正する発音の再アラインメントが可能になる。
【００３１】
１つの実施形態では、発音は、連結シンボル、たとえば「｜」によって隔てられた連結音節であり、音声分解サブモジュールは、連結シンボルを空白類で置き換える。付加的にまたは代替的に、別個の音声分解製品が音声分解に使用される。たとえば、１つの実施形態は、アメリカ国立標準技術研究所（ＮＩＳＴ）によって開発された分節ツールを使用する。図８Ａおよび図８Ｂは、音節分解の例を示している。
【００３２】
動的プログラミングサブモジュール
用語のみの問題として、各発音の音節は、Ａチャンクと呼ばれる。同様に、発音予測は、Ｂチャンクと呼ばれる。Ａチャンクの連結は、Ａ文字によって形成されるＡ文字列と呼ばれ、Ｂチャンクの連結は、Ｂ文字によって形成されるＢ文字列と呼ばれる。図９Ａは、Ａチャンク９１０およびＢチャンク９２０の例を示している。図９Ｂは、Ａ文字列９３０およびＢ文字列９４０の例を示している。
【００３３】
動的プログラミングサブモジュールは、Ａ文字列内の文字と、Ｂ文字列内の文字との間の、最小編集距離を有するアラインメント経路を求める。２つの文字列間の、レーベンシュタイン距離とも呼ばれる編集距離は、第１の文字列を第２の文字列に変換するのに必要とされる編集動作の最小数として規定される。ここで、許容可能な編集動作は、一度に単一のシンボルの挿入、削除、または置換である。
【００３４】
編集距離は、動的プログラミングサブモジュールによって用いられる動的プログラミングを介して求められる。シンボルシーケンスの長さがそれぞれｎおよびｍである場合、動的プログラミングは、サイズｎ×ｍの行列のエントリを求めることをともなう。動的プログラミングサブモジュールは、挿入コスト、削除コスト、および置換コストの最小値に基づいて、行列内の全ての要素を再帰的に求める。行列内の全ての要素が求められると、行列内の右下端の要素が２つの文字列間の編集距離となる。様々な実施形態において、挿入コスト、削除コスト、および置換コストは、同一であるかまたは異なる。
【００３５】
図１０は、Ａ文字列９３０とＢ文字列９４０との間の最小編集距離を有するアラインメント経路を示している。アラインメント経路は、アスタリスク１０１０によってマークされている。アラインメント経路を求めるために、動的プログラミングサブモジュールは、要素、すなわち挿入コスト、削除コスト、または置換コストを表す要素を追跡し、行列の各点においてアラインメントのコストを最小にする。たとえば、１つの実施形態は、２つの行列、すなわちコストを表すコスト行列およびコストを最小にする要素のインデックスを表すインデックス行列を求める。
【００３６】
行列の全ての要素が求められた後、インデックス行列内の右下端の要素から開始する経路は、要素のインデックスを辿ることによって後方にリトレースされ、文字列間のアラインメント経路が特定される。アスタリスク１０１０は、アラインメント経路に沿った点である。
【００３７】
インデックス行列内の要素が削除を表す場合、アラインメント経路上に、２つのアスタリスク１０１５が水平に並んで配置される。図１０を参照すると、これらの２つのアスタリスクは、文字列９３０からの要素ｊおよびｊ＋１が、ともに文字列９４０からの要素ｉにマッピングされており、すなわち、要素ｊが文字列間のマッピングから削除されることを示している。
【００３８】
インデックス行列内の要素が挿入を表す場合、アラインメント経路上に、２つのアスタリスク１０２５が垂直に並んで配置される。これらの２つのアスタリスクは、文字列９３０からの要素ｊが、文字列９４０からの要素ｉおよびｉ＋１にマッピングされており、すなわち、要素ｊが文字列間のマッピングにおいて２回挿入されることを示している。
【００３９】
インデックス行列内の要素が置換を表す場合、アラインメント経路上に、２つのアスタリスク１０３５が対角線状に並んで配置される。これらの２つのアスタリスクは、文字列９３０からの要素ｊが文字列９４０からの要素ｉにマッピングされており、要素ｊ＋１が要素ｉ＋１にマッピングされていることを示している。図１５は、この発明の実施の形態１による、アラインメント経路を求めるための擬似コードを示している。
【００４０】
編集距離サブモジュール
編集距離サブモジュールは、ＢチャンクとＡチャンクとの間に１対１のマッピングを作成する。マッピングは、動的プログラミングサブモジュールによって提供されるアラインメント経路に基づいて作成される。最初に、Ａ文字対Ｂチャンクマップが生成され、マップが、Ａ文字列またはＢ文字列の文字ごとに、その文字が属する対応するＡチャンクまたは、Ｂチャンクを特定する。たとえば、図１０に示すように、Ａ文字／Ｎ／は、Ｂチャンク１にマッピングし、Ａ文字／ｕ／は、Ｂチャンク１にマッピングし、Ａ文字／ｊ／は、Ｂチャンク２にマッピングし、以下同様である。しかしながら、いくつかの場合、動的プログラミングは、１つのＡ文字を複数のＢチャンクにマッピングする。たとえば、Ａ文字／ｋ／は、Ｂチャンク２およびＢチャンク３にマッピングされる。
【００４１】
図１１に示すように、Ａ文字対Ｂチャンクマップに基づいて、Ａチャンク対Ｂチャンクマップが求められる。Ａチャンク対Ｂチャンクマップは、以下のように求められる。単一のＡチャンクからの全ての文字が単一のＢチャンクにマッピングされる場合、Ａチャンクは、対応するＢチャンクにマッピングされる。たとえば、Ａチャンク１は、Ｂチャンク１にマッピングされる。Ａチャンク内の文字が複数のＢチャンクにマッピングする場合、そのＡチャンクは、複数のＢチャンクにマッピングする。たとえば、Ａチャンク２は、Ｂチャンク２およびＢチャンク３にマッピングされる。
【００４２】
Ａ文字対Ｂチャンクマップが１対１のチャンクマップである場合、すなわち各Ａチャンクが１つのみのＢチャンクにマッピングされる場合、予測発音マップ２４５が形成され、このマップに基づいて、アラインされたエントリが求められる。しかしながら、少なくとも１つのＡチャンクが複数のＢチャンクにマッピングされる場合、すなわち図１１に示すような１対多のチャンクマップの場合、Ａ文字対Ｂチャンクマップは、１対１のチャンクマップに分解される必要がある。
【００４３】
１つの実施形態は、１対多のチャンクマップが許容するＡチャンク対Ｂチャンクマッピングの１対１のチャンクマップのデカルト積を求め、各１対１のチャンクマップの累積編集距離を計算し、最も小さい累積編集距離を有する１対１のチャンクマップを選択することによって、Ａ文字対Ｂチャンクマップを分解する。
【００４４】
図１２は、Ａ文字対Ｂチャンクマップを分解するための方法を示している。ここで、Ａ文字対Ｂチャンクマップは、１対多のチャンクマップである。各１対１のチャンクマップ１２１０〜１２４０について、マッピングされたＡチャンクとＢチャンクとの間の編集距離が求められ、合算されて、累積編集距離１２１５〜１２４５が生成される。最小の（１２５０）値１２６０を有する累積編集スコアによって、分解されたＡチャンク−Ｂチャンクマッピングが決まる。この例では、マッピング１２１０が最も小さい累積編集距離、すなわち７を有するので、マッピング１２１０が、分解されたマッピングとして選択される。
【００４５】
図１３Ａおよび図１３Ｂは、変換モジュールによって出力されたアラインされたエントリの例を示している。変換モジュールは、単語「Ｎｅｗ」を発音「ｎｕ」とアラインし、単語「Ｙｏｒｋ」を発音「ｊＯｒｋ」とアラインし、単語「ＮＹ」を発音「ｎｕ｜ｊＯｒｋ」とアラインし、単語「Ｅｘｓｐｒｅｓｓｏ」を発音「Ｅｋ｜ｓｐｒＥ｜ｓｏ」とアラインする。
【００４６】
プルーニングモジュール
プルーニングモジュール４５０は、低い精度の単語−発音マッピングが除去されるように、内部辞書をプルーニングする。１つの実施形態は、上述した頻度カウントｃ（ｗ，ｐ）に基づいて単語−発音マッピングをプルーニングする。各頻度カウントｃ（ｗ，ｐ）は、
【００４７】
【数１】
2011209704.tif 000003
【００４８】
にしたがって、単語ｗについて全ての他の発音ｑに関して求められた全ての頻度カウントの和で除算することによって、単語ｗが発音ｐにマッピングされる確率Ｐ（ｗ，ｐ）に変換される。確率Ｐが特定の閾値未満の単語−発音マッピングは、内部辞書から除去され、したがって発音辞書から除去される。図１４Ａおよび図１４Ｂは、プルーニングの例を示している。
【００４９】
この発明を好ましい実施形態の例として説明してきたが、この発明の精神および範囲内で様々な他の適応および変更を行うことができることは理解されたい。したがって、添付の特許請求の範囲の目的は、この発明の真の精神および範囲内に入るすべての変形および変更を包含することである。
【図１】
2011209704.tif 000005
【図２】
2011209704.tif 000006
【図３】
2011209704.tif 000007
【図４】
2011209704.tif 000008
【図５】
2011209704.tif 000009
【図６Ａ】
2011209704.tif 000010
【図６Ｂ】
2011209704.tif 000011
【図７Ａ】
2011209704.tif 000012
【図７Ｂ】
2011209704.tif 000013
【図８Ａ】
2011209704.tif 000014
【図８Ｂ】
2011209704.tif 000015
【図９Ａ】
2011209704.tif 000016
【図９Ｂ】
2011209704.tif 000017
【図１０】
2011209704.tif 000018
【図１１】
2011209704.tif 000019
【図１２】
2011209704.tif 000020
【図１３Ａ】
2011209704.tif 000021
【図１３Ｂ】
2011209704.tif 000022
【図１４Ａ】
2011209704.tif 000023
【図１４Ｂ】
2011209704.tif 000024
【図１５】
2011209704.tif 000025
【外国語明細書】
2011209704.tif 000026
2011209704.tif 000027
2011209704.tif 000028
2011209704.tif 000029
2011209704.tif 000030
2011209704.tif 000031
2011209704.tif 000032
2011209704.tif 000033
2011209704.tif 000034
2011209704.tif 000035
2011209704.tif 000036
2011209704.tif 000037
2011209704.tif 000038
2011209704.tif 000039
2011209704.tif 000040
2011209704.tif 000041
2011209704.tif 000042
2011209704.tif 000043
2011209704.tif 000044
2011209704.tif 000045
2011209704.tif 000046
2011209704.tif 000047
2011209704.tif 000048
2011209704.tif 000049
2011209704.tif 000050
2011209704.tif 000051
2011209704.tif 000052
2011209704.tif 000053
2011209704.tif 000054
2011209704.tif 000055
2011209704.tif 000056
2011209704.tif 000057
2011209704.tif 000058
2011209704.tif 000059
2011209704.tif 000060
2011209704.tif 000061
2011209704.tif 000062
2011209704.tif 000063