(57)【要約】【課題】  ２バイト文字列の妥当性を確認して、「ノイズ」と称される無効な文字およびシーケンスを検出し除去する方法を提供すること。  【解決手段】  開示するのは、複数の状態を有するバイト・シーケンスの妥当性を検査する方法である。この方法は、複数の状態から１つ以上のノイズ状態を指定するステップと、バイト・シーケンスについて最も確率の高い状態シーケンスを生成するステップと、前記状態シーケンスを用いてバイト・シーケンスにおける全てのノイズを識別するステップと、前記ノイズ状態に前記ノイズを局所化するステップと、を有する。いったん局所化されると、ノイズは、バイト・シーケンスから消去することができる。【特許請求の範囲】
【請求項１】
バイト・シーケンスの妥当性を検査する方法であって、
前記バイト・シーケンスのための複数の状態を規定するステップと、
前記複数の状態から１つ以上のノイズ状態を指定するステップと、
前記バイト・シーケンスについて最も確率の高い状態シーケンスを生成するステップと、
前記状態シーケンスを用いて前記バイト・シーケンスにおける全てのノイズを識別するステップと、
前記ノイズ状態に前記ノイズを局所化するステップと、
を有する、方法。  
【請求項２】
前記バイト・シーケンスから前記ノイズを消去するステップを更に有する、請求項１に記載の方法。
【請求項３】
ノイズ状態としてＡＳＣＩＩ状態も指定する、請求項１に記載の方法。
【請求項４】
前記最も確率の高い状態シーケンスを生成するステップが、ある状態シーケンスが与えられた場合に前記バイト・シーケンスの条件付き確率を表すＰ（Ｘ0・・・Ｘｎ｜Ｓ0・・・Ｓｎ）を計算することを含む、請求項１に記載の方法。
【請求項５】
前記Ｐ（Ｘ0・・・Ｘｎ｜Ｓ0・・・Ｓｎ）の計算が、
【数１】
2006508606.tif 000032
の式を最大化するように前記バイト・シーケンスの各ｉthバイトＸiに状態ラベルＳiを割り当てることを含む請求項４に記載の方法であって、Ｐ0（Ｓ0）は状態の初期分布であり、
【数２】
2006508606.tif 000033
は「状態−状態」伝達マトリクスであり、
【数３】
2006508606.tif 000034
は、状態Ｓiが与えられた場合にバイト値Ｘiを生成する確率の「状態からバイト」マトリクスである方法。
【請求項６】
【数４】
2006508606.tif 000035
の式が成り立つ、請求項５に記載の方法であって、各ｐ（Ｓi-1→Ｓi）は、σ状態を有する有効バイト・シーケンスにおいて特定のＳi状態がＳi-1状態の直後に続く確率である方法。
【請求項７】
【数５】
2006508606.tif 000036
の式が成り立つ、請求項５に記載の方法であって、各ｐ（Ｓi-1→Ｓi）は、３つの状態を有する有効バイト・シーケンスにおいて特定のＳi状態がＳi-1状態の直後に続く確率である方法。
【請求項８】
【数６】
2006508606.tif 000037
の式が成り立ち、更に、前記有効バイト・シーケンスがＧＢ２３１２−８０文字セットにおける有効テキストである、請求項７に記載の方法。
【請求項９】
【数７】
2006508606.tif 000038
の式が成り立つ、請求項５に記載の方法であって、ｈS（Ｘi）はσ状態のヒストグラム関数であり、εj（Ｘi）は、バイト値Ｘiのｒ＋１範囲内でノイズをバイトに対する前記ノイズ状態に関連付ける確率である方法。
【請求項１０】
【数８】
2006508606.tif 000039
の式が成り立つ、請求項９に記載の方法であって、ｈS（Ｘi）は状態のヒストグラム関数であり、εj（Ｘi）は、３状態バイト・シーケンスについて複数のＸi範囲内でノイズをＡＳＣＩＩ状態に対する前記ノイズ状態に関連付ける確率である方法。
【請求項１１】
ＡＳＣＩＩ状態を有し、有効ＡＳＣＩＩおよび２バイト文字を含む有効３状態バイト・シーケンスを供給するステップと、
ＡＳＣＩＩヒストグラムｈA（Ｘi）を、以下のステップを含む方法によって計算するステップであって、その方法が、
各バイト値の発生の頻度を測定するように有効ＡＳＣＩＩテキストをサンプリングするステップと、
整数ＸiのＡＳＣＩＩ範囲について前記サンプリングの非正規化ＡＳＣＩＩヒストグラムを計算するステップと、
前記ＡＳＣＩＩヒストグラムを含む前記マトリクスの全列の和が１になるように、前記非正規化ＡＳＣＩＩヒストグラムを正規化するステップと、を含む、ステップと、
第１バイト・ヒストグラムｈ1（Ｘi）を計算するステップであって、有効２バイト・テキストをサンプリングし、奇数バイトについて非正規化第１バイト・ヒストグラムを計算し、前記第１バイト・ヒストグラムを含む前記マトリクスの全列の和が１になるように前記第１バイト・ヒストグラムを正規化する、ステップと、
第２バイト・ヒストグラムｈ2（Ｘi）を計算するステップであって、有効２バイト・テキストをサンプリングし、奇数バイトについて非正規化第２バイト・ヒストグラムを計算し、前記第２バイト・ヒストグラムを含む前記マトリクスの全列の和が１になるように前記第２バイト・ヒストグラムを正規化する、ステップと、
を更に有する、請求項１０に記載の方法。
【請求項１２】
機械によって読み取り可能なプログラム保存デバイスであって、前記機械によって実行されてバイト・シーケンスの妥当性を検査するための方法ステップを実行することができる命令のプログラムを実際に具現化し、前記方法が、
前記バイト・シーケンスのための複数の状態を規定するステップと、
前記複数の状態から１つ以上のノイズ状態を指定するステップと、
前記バイト・シーケンスについて最も確率の高い状態シーケンスを生成するステップと、
前記状態シーケンスを用いて前記バイト・シーケンスにおける全てのノイズを識別するステップと、
前記ノイズ状態に前記ノイズを局所化するステップと、
を有する、デバイス。
【請求項１３】
前記ノイズ状態に前記ノイズを局所化する前記ステップが、
ノイズ状態に対応しない前記バイト・シーケンス内の各バイトを調べるステップと、
前記バイトが有効であるか否かを判定するステップと、
前記バイトが有効でない場合、前記バイトの状態をノイズ状態に再指定するステップと、
を有する、請求項１２に記載のデバイス。
【請求項１４】
有効バイトの参照テーブルを更に有し、前記参照テーブルにアクセスすることによってバイトが有効であるか否かの前記判定が実行される、請求項１３に記載のデバイス。
【請求項１５】
バイト・シーケンスの妥当性を検査する方法であって、
前記バイト・シーケンスのための、少なくとも１つのＡＳＣＩＩ状態を含む複数の状態を規定するステップと、
前記少なくとも１つのＡＳＣＩＩ状態をノイズ状態として指定するステップと、
以下のステップを含む方法によって前記バイト・シーケンスについて最も確率の高い状態シーケンスを生成するステップであって、
その方法が、
ある状態シーケンスが与えられた場合に前記バイト・シーケンスの条件付き確率を表すＰ（Ｘ0・・・Ｘｎ｜Ｓ0・・・Ｓｎ）を計算するステップであって、
前記Ｐ（Ｘ0・・・Ｘｎ｜Ｓ0・・・Ｓｎ）の計算が、
【数９】
2006508606.tif 000040
の式を最大化するように前記バイト・シーケンスの各ｉthバイトＸiに状態ラベルＳiを割り当てることを含み、
Ｐ0（Ｓ0）は状態の初期分布であり、
【数１０】
2006508606.tif 000041
は「状態−状態」伝達マトリクスであり、
【数１１】
2006508606.tif 000042
は、状態Ｓiが与えられた場合にバイト値Ｘiを生成する確率の「状態からバイト」マトリクスである、前記計算するステップと、
前記状態シーケンスを用いて前記バイト・シーケンスにおける全てのノイズを識別するステップと、
前記ノイズ状態に前記ノイズを局所化するステップと、
前記ノイズを前記バイト・シーケンスから消去するステップと、
を有する方法により、状態シーケンスを生成する、前記生成するステップと、を有する、方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本出願は、ＤＡＲＰＡ政府契約すなわちＳＰＡＷＡＲ契約第Ｎ６６００１−９９−２−８９１６号のもとで擁護される。
【０００２】
本発明は、文字コード・シーケンスの妥当性確認に関する。
【背景技術】
【０００３】
２バイト文字の符号化は、多数の目的のため、とりわけ、ＧＢ２３１２−８０すなわち中国本土で用いられている簡体字中国語等の複雑な文字を符号化するため、広く用いられている。ＧＢ２３１２−８０は、１対のバイトとして表される７，４４５の漢字を含み、各バイトは１６１から２５４までの数である。これによって、漢字を、０から１２７までの範囲のバイト値で表される従来のＡＳＣＩＩテキストと混合することが可能となる。技術的には、ＧＢ２３１２−８０とＡＳＣＩＩを同時に表現することはＥＵＣ−ＣＮ符号化と呼ばれるが、我々は簡略化のため、この明細書を通してこれをＧＢ２３１２−８０と呼ぶ。これによって、必然的に、１６１から２５４の範囲のバイトが対でなければならず、かかる文字列は全て、いずれかの２つの１バイトＡＳＣＩＩ文字間に連続して偶数のかかるバイトを有しなければならないことを意味する。ＧＢ２３１２−８０では、１２８から１６０の範囲のバイト値は無効である。これらのルールにも関わらず、まとめて「ノイズ」と称される無効な文字およびシーケンスが、中国のウエブページおよびニュース送信テキストの５％から１０％において発生することがわかっている。このノイズの発生源は、はっきりしない。
【発明の開示】
【発明が解決しようとする課題】
【０００４】
２バイト符号化の処理に現在利用可能なアプリケーションは、ノイズを扱うには不適切である。例えば、ＧＢからユニコードへのコンバータは、最初の無効バイト・シーケンス上で単にクラッシュし、ノイズ後の全ての情報が失われる。
【０００５】
かかるノイズの修正は、あいまいさの問題を呈する。例えば、ＧＢ２３１２−８０文字の９バイト・シーケンスの場合を考える。その全てが１６１〜２５４の範囲である。どの「半文の文字」が破棄されるべきノイズなのか？  バイトのいずれか１つを破棄すると、４つの完全に有効な漢字が残るが、理解できないシーケンスになる。確率では、理解できる文字列を生成するように、バイトの１つのみを破棄すれば良い。
【０００６】
２バイト文字列の妥当性を確認して、かかるノイズを検出し除去する方法が求められている。
【課題を解決するための手段】
【０００７】
開示するのは、複数の状態を有するバイト・シーケンスの妥当性を検査する方法である。この方法は、複数の状態から１つ以上のノイズ状態を指定するステップと、バイト・シーケンスについて最も確率の高い状態シーケンスを生成するステップと、前記状態シーケンスを用いてバイト・シーケンスにおける全てのノイズを識別するステップと、前記ノイズ状態に前記ノイズを局所化するステップと、を有する。
【０００８】
本発明の別の態様では、次いで、ノイズをバイト・シーケンスから消去することができる。
【０００９】
本発明の別の態様では、ノイズ状態はＡＳＣＩＩ状態である。  
【００１０】
本発明の別の態様では、前記最も確率の高い状態シーケンスを生成するステップが、Ｐ（Ｘ0・・・Ｘｎ｜Ｓ0・・・Ｓｎ）を計算することを含み、これは、ある状態シーケンスが与えられた場合に前記バイト・シーケンスの条件付き確率を表す。
【００１１】
本発明の別の態様では、前記Ｐ（Ｘ0・・・Ｘｎ｜Ｓ0・・・Ｓｎ）の計算が、以下の式を最大化するように前記バイト・シーケンスの各ｉthバイトＸiに状態ラベルＳiを割り当てることを含む。
【数１２】
2006508606.tif 000002
ここで、Ｐ0（Ｓ0）は状態の初期分布であり、
【数１３】
2006508606.tif 000003
は「状態−状態」伝達マトリクスであり、
【数１４】
2006508606.tif 000004
は、状態Ｓiが与えられた場合にバイト値Ｘiを生成する確率の「状態からバイト」マトリクスである。
【００１２】
本発明の別の態様では、以下の式が成り立つ。
【数１５】
2006508606.tif 000005
ここで、各ｐ（Ｓi-1→Ｓi）は、σ状態を有する有効バイト・シーケンスにおいて特定のＳi状態がＳi-1状態の直後に続く確率である。
【００１３】
本発明の別の態様では、以下の式が成り立つ。
【数１６】
2006508606.tif 000006
ここで、各ｐ（Ｓi-1→Ｓi）は、３つの状態を有する有効バイト・シーケンスにおいて特定のＳi状態がＳi-1状態の直後に続く確率である。
【００１４】
本発明の別の態様では、以下の式が成り立つ。
【数１７】
2006508606.tif 000007
更に、前記有効バイト・シーケンスがＧＢ２３１２−８０文字セットにおける有効テキストである。
【００１５】
本発明の別の態様では、以下の式が成り立つ。
【数１８】
2006508606.tif 000008
ここで、ｈS（Ｘi）はσ状態のヒストグラム関数であり、εj（Ｘi）は、バイト値Ｘiのｒ＋１範囲内でノイズをバイトに対するノイズ状態に関連付ける確率である。
【００１６】
本発明の別の態様では、以下の式が成り立つ。
【数１９】
2006508606.tif 000009
ここで、ｈS（Ｘi）は状態のヒストグラム関数であり、εj（Ｘi）は、３状態バイト・シーケンスについて複数のＸi範囲内でノイズをＡＳＣＩＩ状態に対する前記ノイズ状態に関連付ける確率である。
【００１７】
本発明の別の態様では、更に、ＡＳＣＩＩ状態を有し、有効ＡＳＣＩＩおよび２バイト文字を含む有効３状態バイト・シーケンスを供給するステップと、ＡＳＣＩＩヒストグラムｈA（Ｘi）を、以下のステップを含む方法によって計算するステップであって、その方法が、各バイト値の発生の頻度を測定するように有効ＡＳＣＩＩテキストをサンプリングするステップと、ＸiのＡＳＣＩＩ範囲について前記サンプリングの非正規化ヒストグラムを計算するステップと、前記ＡＳＣＩＩヒストグラムを含むマトリクスの全列の和が１になるように、前記非正規化ＡＳＣＩＩヒストグラムを正規化するステップと、を含む、ステップと、第１バイト・ヒストグラムｈ1（Ｘi）を計算するステップであって、有効２バイト・テキストをサンプリングし、奇数バイトについて非正規化第１バイト・ヒストグラムを計算し、前記第１バイト・ヒストグラムを含むマトリクスの全列の和が１になるように前記第１バイト・ヒストグラムを正規化する、ステップと、第２バイト・ヒストグラムｈ2（Ｘi）を計算するステップであって、有効２バイト・テキストをサンプリングし、奇数バイトについて非正規化第２バイト・ヒストグラムを計算し、前記第２バイト・ヒストグラムを含むマトリクスの全列の和が１になるように前記第２バイト・ヒストグラムを正規化する、ステップと、を有する。
【００１８】
開示するのは、機械によって読み取り可能なプログラム保存デバイスであって、機械によって実行されて複数の状態を有するバイト・シーケンスの妥当性を検査するための方法ステップを実行することができる命令のプログラムを実際に具現化し、前記方法が、複数の状態から１つ以上のノイズ状態を指定するステップと、バイト・シーケンスについて最も確率の高い状態シーケンスを生成するステップと、前記状態シーケンスを用いてバイト・シーケンスにおける全てのノイズを識別するステップと、前記ノイズ状態に前記ノイズを局所化するステップと、を有する。
【００１９】
このデバイスの別の態様では、前記ノイズ状態に前記ノイズを局所化する前記ステップが、ノイズ状態に対応しない前記バイト・シーケンス内の各バイトを調べるステップと、バイトが有効であるか否かを判定するステップと、バイトが有効でない場合、前記バイトの状態をノイズ状態に再指定するステップと、を有する。
【００２０】
このデバイスの別の態様では、デバイスは、有効バイトの参照テーブルを更に有し、前記参照テーブルにアクセスすることによってバイトが有効であるか否かの前記判定が実行される。
【００２１】
開示するのは、ＡＳＣＩＩ状態を含む複数の状態を有するバイト・シーケンスの妥当性を検査する方法であって、この方法は、ＡＳＣＩＩ状態をノイズ状態として選択するステップと、以下のステップを含む方法によってバイト・シーケンスについて最も確率の高い状態シーケンスを生成するステップであって、その方法が、ある状態シーケンスが与えられた場合に前記バイト・シーケンスの条件付き確率を表すＰ（Ｘ0・・・Ｘｎ｜Ｓ0・・・Ｓｎ）を計算するステップを有し、前記Ｐ（Ｘ0・・・Ｘｎ｜Ｓ0・・・Ｓｎ）の計算が、以下の式を最大化するようにバイト・シーケンスの各ｉthバイトＸiに状態ラベルＳiを割り当てることを含む。
【数２０】
2006508606.tif 000010
ここで、Ｐ0（Ｓ0）は状態の初期分布であり、
【数２１】
2006508606.tif 000011
は「状態−状態」伝達マトリクスであり、
【数２２】
2006508606.tif 000012
は、状態Ｓiが与えられた場合にバイト値Ｘiを生成する確率の「状態からバイト」マトリクスである。更に、この方法は、前記状態シーケンスを用いてバイト・シーケンスにおける全てのノイズを識別するステップと、前記ノイズ状態に前記ノイズを局所化するステップと、前記ノイズを前記バイト・シーケンスから消去するステップと、を有する。
【発明を実施するための最良の形態】
【００２２】
図１を参照すると、本発明の基本フローが示されている。エラーの可能性があるバイト・シーケンスを状態シーケンス・ラベラ１００に送り、これはまずこのバイト・シーケンスに対する最も確率の高い状態シーケンスを生成し、次いでこの状態シーケンスを変更してエラーまたは「ノイズ」を全て単一の状態に局所化するようにする。次いで、バイト・シーケンスおよび関連する状態シーケンスを、修正モジュール１１０に送り、これは、シーケンスを調べて、バイト・シーケンスにエラーがあるか否かを判定し、ある場合はそれらを補正し、これによって有効バイト・シーケンスを出力する。
【００２３】
図２は、ＧＢタイプのバイト・シーケンス等、混合２バイトおよびＡＳＣＩＩシーケンスのための可能な状態シーケンスの典型的なマルコフ・モデル（Markov model）を示す。この例において、バイトの状態は３つのうち１つとすることができる。すなわち、ＡＳＣＩＩ文字（状態Ａ）、２バイト文字状態の第１バイト（状態ＧＢ１）、または２バイト文字状態の第２バイト（状態ＧＢ２）である。状態は、ユーザが検出したいと望むノイズに応じて、ユーザによって指定される。ノイズは、この例では無効文字コードである。図に見られるように、１バイトＡＳＣＩＩ文字（状態Ａ）の後に、別のＡＳＣＩＩ文字（状態Ａ）または２バイトＧＢタイプの文字の第１バイト（状態ＧＢ１）が続くことができるが、ＡＳＣＩＩ文字（状態Ａ）の後に２バイトＧＢタイプの文字の第２バイト（状態ＧＢ２）が続くことはできない。これは、ＡＳＣＩＩ状態Ａに向かう矢印およびこれから離れる矢印の方向によって示されている。同様に、第１ＧＢバイト（状態ＧＢ１）の後に第２バイト（状態ＧＢ２）が続くことができるが、ＡＳＣＩＩ文字（状態Ａ）が続くことはできない。第２バイト（状態ＧＢ２）の後にＡＳＣＩＩ文字（状態Ａ）が続くことはできるが、第１バイト（状態ＧＢ１）は続けない。これらのルールの違反は、図１の状態シーケンス・ラベラ１００が発生する状態ストリングにおいて許されず、これは、式４ｃの「状態−状態」伝達マトリクス
【数２３】
2006508606.tif 000013
においてゼロ・エントリによって数学的に保証される。これについては以下で更に詳しく説明する。
【００２４】
状態−状態マトリクスを用いてエラーのあるバイト・シーケンス上に適正な状態シーケンスを数学的に強制すると、結果として、無効な文字コードが生じる。すなわち、ＡＳＣＩＩ状態とラベルされたバイトは有効なＡＳＣＩＩ文字に相当せず、ＧＢ１およびＧＢ２バイトの対は有効な２バイト文字に相当しない。これらの無効文字は、修正モジュール１１０によって検出され修正される。以下で説明するように、修正モジュールは、無効な文字を、１つ以上の指定された「ノイズ状態」に「局所化」することによって、これを行う。
【００２５】
状態シーケンス・ラベラが特定のバイト・シーケンスのための状態シーケンスを生成するために利用する方法は、確率的モデルを利用する。いずれかのバイト・シーケンスについて、
Ｘ0、Ｘ1、Ｘ2、・・・Ｘn
（１）
我々は対応する状態シーケンスを生成したい。
Ｓ0、Ｓ1、Ｓ2、・・・Ｓn
（２）
ここで、各Ｘiは０から２５５までの整数であり（８ビットバイトについて）、各Ｓiは、１バイトのＡＳＣＩＩバイト、２バイトの第１のバイト、または２バイトの第２のバイトについて、それぞれＡ、１、または２のいずれかである。
【００２６】
次いで、我々は、式２の状態シーケンスが以下の通りである場合に、式１のバイト・シーケンスの条件付き確率をモデル化することができる。    
【数２４】
2006508606.tif 000014
ここで、Ｐ0（Ｓ0）は状態の初期分布である。すなわちＰ0（Ａ）＝Ｐ0（１）＝Ｐ0（２）＝１／３であり、
【数２５】
2006508606.tif 000015
は、状態−状態伝達マトリクスであり、用いているマルコフの特性を有する。
【数２６】
2006508606.tif 000016
は、所与の状態Ｓiが与えられた場合にバイト値Ｘiを生成する確率の「状態からのバイト」マトリクスである。
【００２７】
σの合計状態を有するいずれかのバイト・シーケンスについて、状態−状態マトリクスは、σｘσサイズのマトリクスである。
【数２７】
2006508606.tif 000017
【００２８】
状態−状態マトリクスは、図２に示す３状態マルコフ・モデルの場合、以下の形態を有する。
【数２８】
2006508606.tif 000018
ここで、ｐ（Ｓi-1→Ｓi）は、有効バイト・シーケンスにおいて、ｉthバイトについてのある特定のＳi状態が、直前のバイト（ｉ−１）についてのある特定のＳi-1状態の直後に来る確率または観察された頻度を示す。式４ｂは、３状態バイト・シーケンスについてのマトリクスであることは理解されよう。ＧＢ２３１２−８０文字セットに適用した場合、状態−状態マトリクスは、以下の通りであることがわかっている。
【数２９】
2006508606.tif 000019
【００２９】
また、４ｂのマトリクス・エントリの有意性は、以下のテーブルによって示すことができる。
【表１】
2006508606.tif 000020
【００３０】
表１から、我々は、例えば、ＡＳＣＩＩ文字（すなわち状態Ａ）の後に別のＡＳＣＩＩが来る確率は、ｐ（Ａ→Ａ）＝０．９９５１５７であり、一方、ＡＳＣＩＩの後に２バイト文字の第１バイトが来る確率はわずかｐ（Ａ→ＧＢ１）＝０．００４８４３であることがわかった。表１における数字は、有効テキストについて確率がどうあるべきかを表し、実際の有効テキストの統計データのコンパイルから得られる。
【００３１】
【数３０】
2006508606.tif 000021
マトリクスは、次のように記載される。
【数３１】
2006508606.tif 000022
ここで、ｈS（Ｘi）は状態のヒストグラム関数であり、ε（Ｘi）は、ｒ＋１  Ｘi範囲内でノイズをｓth状態に関連付ける確率である。これは、本発明に従って、ｓth状態が「ノイズ状態」として選択されたことを示す。これについて以下で更に詳しく記載する。
【００３２】
図２の３状態マルコフ・モデルでは、式５ａは以下の通りとなる。
【数３２】
2006508606.tif 000023
ここで、ｈA（Ｘi）を計算するには、有効ＡＳＣＩＩテキストをサンプリングし、そのバイトのヒストグラムを計算し、次いでマトリクスの全列（イプシロンを含む）の和が１になるようにそれらを正規化する。第１バイト・ヒストグラムｈ1（Ｘi）は、有効２バイト・テキストをサンプリングし、奇数バイトについてヒストグラムを計算することによって計算され、第２バイト・ヒストグラムｈ2（Ｘi）は、偶数バイトについて計算する。次いで、ヒストグラムｈ1（Ｘi）およびｈ2（Ｘi）を正規化して、それらの各列の和を１とする。上述のマトリクスは、ＡＳＣＩＩ状態が指定されたノイズ状態になることを意味することに留意すべきである。
【００３３】
ＧＢ２３１２−８０に関する
【数３３】
2006508606.tif 000024
マトリクス・エントリの有意性は、以下の表によって表される。
【表２】
2006508606.tif 000025
ここで、例えば、ＧＢ２３１２−８０の漢字（すなわち１６１≦Ｘi≦２５４）と関連したバイトは、状態ＧＢ１およびＧＢ２によって生成された確率が最も高いが、ＡＳＣＩＩ文字から生じるエラー確率ε2は低いことがわかる。
【００３４】
所与の文字列についての状態シーケンスを生成するため、式３を用いて、Ｐ（Ｘ0・・・Ｘｎ｜Ｓ0・・・Ｓｎ）の値を最大化する状態シーケンスを見出す。次いで、ＧＢ２が後に来るＧＢ１とラベルされた全てのバイト対を分析して、それらが有効ＧＢ文字であることを確認する（ＧＢ２３１２−８０文字セットは、有効バイト範囲内にいくつかの「ギャップ」を含むので、かかる「ギャップのある」文字セットのための好適な実施形態は、参照テーブル内の値を参照することによってこのチェックを行う）。それらが有効文字を形成しない場合、状態シーケンスにおいて、双方のバイトをノイズ状態と再度ラベル付けする。この例ではＡＳＣＩＩとして再度ラベル付けする。
【００３５】
上述の動作の結果として得られた状態シーケンスは、修正モジュール１１０に送られ、以下の特性を有する。
【表３】
2006508606.tif 000026
ここで、ノイズは全てこの時点で１つの状態すなわちＡＳＣＩＩ状態に局所化されていることがわかる。これは、例示のためのみに示す。なぜなら、ノイズの全てを他の状態の１つに局所化するように、シーケンス・ラベラ１００の手順を変更することも可能だからである。
【００３６】
修正モジュール１１０は、シーケンスにおける無効ＡＳＣＩＩ文字を単に識別してそれらを消去する。別の実施形態では、修正モジュール１１０は、列におけるあいまいさも検出して、実際の言語サンプルの統計データのデータベースにアクセスすることによって補正を行う。
【００３７】
ＧＢ２３１２−８０漢字セットに関連付けて、３つのみの状態を用いて本発明を説明し、全てのノイズをＡＳＣＩＩ状態に局所化するが、本発明は、σの状態を有する（ここでσ＞１である）いずれかの文字セットに一般化することができる。本発明は、１および２バイト文字を有する文字状態に限定されず、いずれかの数のバイトの文字のいずれかの組み合わせに一般化することができる。基本的な手順は、確率モデルを用いて全てのエラーを１つ以上の指定したノイズ状態に局所化することである。また、バイト値において禁止された遷移を表す状態を、いつでもモデルに加えることができ、また、指定したノイズ状態として用いることができる。従って、本発明は、あらゆるマルチバイト・テキストに容易に一般化することができ、文字コンバータおよびテキスト翻訳機、エディタ、サーチ・エジン等の全ての方法のためのフィルタとして有用であることがわかる。
【００３８】
更に、２つ以上の状態をノイズ状態として指定し、１組のルールに従って各々にエラーを割り当てることができることを指摘することができる。これは、異なるタイプのノイズを分離したい場合に有用である。ノイズ状態は実際の有効状態に対応しないが、それら自身の別個のそれぞれの状態として指定することができる。
【００３９】
本発明の方法は、コンピュータ等の機械によって読み取り可能な保存デバイス上に実際に具現化された命令のプログラムとして実行することができる。
【００４０】
本発明の作用の１例として、以下のＧＢ２３１２−８０バイト・シーケンスを考える。各２バイト・シーケンスをそれが表す漢字と共に示す。
【数３４】
2006508606.tif 000027
【００４１】
ここで、シーケンスが、逸脱したバイト値すなわち冒頭に挿入された十進数１８９によってエラーを生じた場合を考える。
【数３５】
2006508606.tif 000028
【００４２】
現在の技術は、上述のシーケンスが有効か否かを判定することができるが、中国語を母語とする人はエラーの生じたシーケンスを訳のわからないものとしてすぐに認識した。本発明に従って、エラーの生じたバイト列を、図１の状態シーケンス・ラベラ１００に送り、ここで、式１から５に従って対応する状態シーケンスを構築する。
【数３６】
2006508606.tif 000029
【００４３】
疑わしいバイト・シーケンスおよび対応する状態シーケンスを修正モジュール１１０に送り、ここで、ノイズをＡＳＣＩＩ状態に局所化することを選んだと仮定すると、非ＡＳＣＩＩ状態を調べて、それらが有効な数の範囲内にあるか否かを試験する。そうでないとわかったものは、ＡＳＣＩＩとして再ラベルする。次いで、ＡＳＣＩＩ状態を調べて、許容可能バイト値内にないＡＳＣＩＩ状態を無効と見なす。しかしながら、我々の例において全ての非ＡＳＣＩＩは有効であるので、これは修正モジュール１１０のためだけに残り、最後のステップに移って無効ＡＳＣＩＩ文字にフラグを付すかまたは消去する。
【数３７】
2006508606.tif 000030
これによって、正しいシーケンスを回復させる。
【００４４】
むろん、別個の状態シーケンス・ラベラ１００および修正モジュール１１０を図示したが、これは例示および明確さのためのみである。本発明の実施者の必要に応じて、モジュールの機能性は、統合するか、または逆に更に分割することも可能である。
【００４５】
バイト・シーケンスの「状態」はあいまいであり、従って、本発明のユーザの制御内にあることに留意すべきである。本発明の方法のために選択される状態は、排除したいノイズによって異なる。上述の例では、３状態マルコフ・モデルを用い、ノイズ状態としてＡＳＣＩＩ状態を指定した。これは、我々が関心を持っている唯一のノイズが無効バイトである場合に充分であるが、我々は、他のノイズを発見するようにマルコフ・モデルを拡張することも可能である。例えば、句読、子音、母音、大文字等のための追加の状態を加えて、他の形態のエラーを監視することができる。
【００４６】
１度に１つではなく、１度に２以上のバイトを分析するマルコフ・モデルを用いることも可能である。従って、状態からのバイト・マトリクス
【数３８】
2006508606.tif 000031
は、状態の定義をわずかに変更して、２５６2ｘ＃状態に拡張する。かかるモデルは、容認できないバイト対を選択するであろう（例えば、モデルの英語バージョンでは、文字ｑの後に「ｕ」以外のいずれかが来るものはノイズとして選択される可能性がある。または、子音の後に適正な母音が続かない）。
【００４７】
本明細書中で開示した全ての物理的な量は、特に明確に指示しない限り、開示した量に正確に等しいのではなく、開示した量にほぼ等しいものとして解釈すべきであることは理解されよう。更に、「約」等の修飾語がないだけで、かかる開示した物理的な量が、他のいずれかの本明細書中で開示した物理的な量に対して用いられるか否かにかかわらず、かかる量が正確な量であることを明示的に示すものと解釈すべきでない。
【００４８】
好適な実施形態を図示し説明してきたが、本発明の精神および範囲から逸脱することなく、様々な変形および置換を行うことができる。従って、本発明は、例示のためのみに記載し、本明細書中で開示したかかる例示および実施形態は、特許請求の範囲を限定するものとして解釈すべきでないことは理解されよう。
【図面の簡単な説明】
【００４９】
【図１】本発明の１実施形態の全プロセスの図である。
【図２】本発明の典型的なマルコフ・モデルの図である。
【符号の説明】
【００５０】
１００  状態シーケンス・ラベラ
１１０  修正モジュール
【図１】
2006508606.tif 000043
【図２】
2006508606.tif 000044
【国際調査報告】
2006508606.tif 000045