JPH07506207A - 文字認識におけるストリングのカテゴライズ - Google Patents

Abstract

(57)【要約】本公報は電子出願前の出願データであるため要約のデータは記録されません。

Description

【発明の詳細な説明】 発明の名称 文字認識におけるストリングのカテゴライズ発明の背景 本発明は、文字または他のエレメントのストリングのような、ストリングをカテ ゴライズする文字認識方法に関する。

従来のいくつかの文字認識方法は、テキスト中で生じ得る文字ストリングの異な るカテゴリーを考慮することにより認識精度を改善している。例えば、文字認識 を行う製造物（製品）であるゼロンクスイメージングシステムは、いくつかの特 別なアルゴリズムを使用しており、各アルゴリズムは文字ストリングの各カテゴ リーに対応する。あるアルゴリズムは単語を辞書で調べることが可能であり、そ の他のアルゴリズムは句読記号を伴うアラビア数字の適正なストリングを認識可 能である、等となっている。文字候補のストリングが、２つ以上の文字カテゴリ ーに対する実質的可能性を有する候補を含む場合、可能性のある各文字カテゴリ ーに帰着することが予想される存在可能なストリングに対して各認識アルゴリズ ムを適用することにより曖昧さが解消されることが可能である。存在可能なスト リングの内の１つがアルゴリズムの内の１つにより認識される場合、認識結果は 曖昧さを解消するために使用されることが可能である。２つまたはそれ以上の存 在可能なストリングが異なるアルゴリズムにより認識される場合、曖昧さを解消 するためにストリングのカテゴリーのシーケンスが考慮されることが可能である 。

Ｔａｋａｈａｓｈｉ　らによる米国特許第４．００３．０２２号ではストリング パターン認識方法か記述されている。図１から４、および７に関して記述および 示されているように、文字は順序論理に与えられるシンボルとしてのストリング パターンに分解される。コラム３の５２から５５行では、シンボルストリングパ ターンを全ての順序論理と比較してとの論理か該パターンを許容したかをチェッ クすることにより各シンボルストリングパターンのクラスが決定されることが記 述されている。

５ｉｎｈａ、　Ｒ，Ａ１．　Ｋ、およびＰｒａｓａｄａ、　Ｂ、らによるｒＶｉ ｓｕａｌ　Ｔｅｘｔ　Ｒｅｃｏｇｎｉｔｉｏｎ　ｔｈｒｏｕ■■ Ｃ０ｎｔｅＸｔｕａｌ　Ｐｒｏｃｅｓｓｉｎｇ　Ｊ　（Ｐａｔｔｅｒｎ　Ｒｅｃ ｏｇｎｉｔｉｏｎ、Ｖｏｌ、２１．Ｎｏ、５．１９８８．　垂吹A４６３−４７ ９ ）では視覚的テキスト認識方法か記述されている。４６３ページの最終、＜ラグ ラフの冒頭では辞書に関する方法か記述されている。４６５ページのセクション ２５　ｌては部分辞書が記述されている。４６７ページのセクション２．６では 、曖昧でない句読記号に基づく単語境界識別が記述されている。４６７から４６ ８ページのセクション２．７では、単語境界を識別し、辞書と照合し、修正され たヴイタビネノトを通して検討するための発見的方法の使用が記述されている。

４６８ページのセクション３、図３および４では辞書の編成および検索が記述さ れており、これらは特にツリー構造ベースの辞書に関する。図３はノード構造を 示し、該ノート構造は、ＮＥＸＴフィールド、ＡＬＴフィールド、文字、単語末 尾記号、およびフラグを含む。４７３ページの右コラムでは、い（つかの原因に より誤りか発生することが記述されており、該原因は単語中の曖昧な句読記号、 および辞書単語への数値のマツピングを含む。

５ｒｉｈａｒｉ、　Ｓ、　Ｎ、、１（ｕｌｌ、Ｊ、Ｊ、　、およびＣｈｏｕｄｈ ａｒｉ、　Ｒ，らによるｒ［ｎｔｅｇｒａｔｉｎｇ　Ｄｉｖ■ ｒｓｅ　Ｋｎｏｗｌｅｄｇｅ　５ｏｕｒｃｅ　ｉｎ　Ｔｅｘｔ　Ｒｅｃｏｇｎ山 ｏｎ」（ＡＣＭ　Ｔｒａｎｓａｃｔｉｏｎｓ　ｏｎ　０ｆｆ奄モ■@Ｉｎ ｆｏｒｍａｔ　ｉｏｎ　Ｓｙｓｔｅｍｓ、　Ｖｏｌ、　１．Ｎｏ、　１．　Ｊａ ｎｕａｒｙ　１９８３．　ｐｐ、　６８−８７）ではテキスg認識方法 か記述されている。７２から７４ページのセクション３および図２では辞書の編 成か記述されており、これらは特にレターツリーに関する。図２（ａ）はノード のフィールドを示し、該ノードフィールドは、トークンを表すＣＨＡＲ、ビット から成る単語長インジケータアレイを表すＷＬ、単語末尾タグピットを表すＥ、 およびＮＥＸＴとＡＬＴＥＲＮＡＴＥとラベル付けされた２つのポインタを含む 発明の要旨 本発明の１懸様は、文字ストリングカテゴリーを考慮した従来の文字認識方法に おける基本的問題を処理する。前述のように、従来のいくつかの方法は個別のア ルゴリズムを用いて各文字ストリングカテゴリーを処理する。文字候補の各スト リングに対して各カテゴリーのアルゴリズムが実行されなければならないため、 この方法は時間的に非効率的となる。また、各カテゴリーのアルゴリズムを実行 するために必要となる、命令を含むデータが別々に保存されなければならないた め、この方法は空間的にも非効率的となる。

この慾様はさらに、これらの基本的問題を解決する方法の発見に基づいている。

該方法はストリングの全てのカテゴリーに対するアルゴリズムを統合し、その結 果、文字候補の各ストリングに対して単一のアルゴリズムのみが実行される。

該方法はまたストリングの各カテゴリーに対するデータを統合し、その結果、統 合化アルゴリズムにより使用されるデータがコンパクトなものとなる。

この発見は、有向グラフの方法、特に有限状態マシンを表す有向グラフが広範な ストリング認識アルゴリズムを統合することを可能にするという所見に基づいて いる。ストリングの許容可能なカテゴリーは非常に多様であるが、各カテゴリー はそれに対応する有限状態マソン（ＦＳＭ）として表されることが可能である。

アラヒア数字のような、限りなく多数の存在可能なストリングを含むカテゴリー でさえも、循環ＦＳＭとして表されることが可能である。従って、同一のルック アップ（検索）アルゴリズムが各カテゴリーのＦＳＭを表す有向グラフと共に使 用されることが可能である。空間的効率化を実現するために、全てのカテゴリー のＦＳＭが合成ＦＳＭに編成されることが可能であり、その結果、合成ＦＳＭを 表すために単一の有向グラフのみか必要となる。時間的効率化を実現するために 、文字候補のストリングの認識においてルックアップアルゴリズムが１回だけ実 行される。２つ以上のカテゴリーとして許容可能なストリングを分析するために 、有向グラフは許容可能な各ストリングに対する１つまたはそれ以上のカテゴリ ーを示すデータを含む。

従って、本発明に従うストリングデータはデータユニットのシーケンスを含み、 該データユニットはストリングの文字を示すデータを使用してアクセスされるこ とか可能である。ストリングが許容可能である場合、該文字ストリーシグが許容 可能であることを示す情報と、該ストリングに対するカテゴリー集合を示す情報 とを含むサブシーケンス（部分シーケンス）と共にデータユニットのシーケンス は終了する。従って、文字認識システムのプロセッサはエンディングサブシーン スを使用して、ストリングが許容可能であることと該ストリングのカテゴリー集 合とを示すエンディングデータを得ることか可能である。

冗長性を除去するためにストリングのプリフィクスおよびサフィックスの両者が 無効にされることが可能なように構成されたデータに対して、前述の方法は特に 有利である。カテゴリーインジケータは数が比較的少ないため、許容可能ストリ ングの各々に対してカテゴリーインジケータが存在する場合、各カテゴリーイン ジケータの多くの発生をデータか含むことが予想される。しかし、各ストリング のカテゴリーインジケータかストリングのサフィックスの末尾に保存される場合 、サフィックスを無効にすることはデータ中のカテゴリーインジケータの数を大 きく低減する。有向グラフまたはＦＳＭを表す他のデータに適用することが可能 な公知の最小化アルゴリズムを用いてサフィックスが無効にされることが可能で ある。

前述のようなカテゴリーインジケータを含むストリングデータは、フロッピーデ ィスクのようなデータ保存媒体により保存されることが可能である。データ保存 媒体は命令のような制御データを含むこともまた可能であり、プロセッサはその ようなデータをストリングデータへのアクセス時に使用することが可能である。

従って、文字認識を実行するシステムのプロセッサは制御データおよびストリン グデータを使用して、文字のストリングが許容可能なストリングかどうか、およ び許容可能な場合には該ストリングに対するカテゴリー集合を示すデータを得る ことか可能である。

以下の記述、図面、および請求項は、本発明に関する前述および他の態様、対象 、特徴、および利点をさらに明らかにするものである。

図面の簡単な説明。

図１は、プロセッサがストリングデータを使用してストリングに対するカテゴリ ー集合データを得ることが可能なシステムの要素を示す概略ブロック図である図 ２は、ストリングデータを使用して図１のプロセッサが文字をマツチする（文字 データと突き合わせて文字を確定する）ことを可能にする一般的ステップを示す フローチャートである。

図３は、ストリングデータを使用して図１のプロセッサがエンディングデータを 得ることを可能にする一般的ステップを示すフローチャートである。

図４は文字サブシーケンスの概略図であり、文字サブシーケンス自体の含む情報 および他のサブシーケンスへのリンクを示す。

図５は、文字をマツチする場合に図４のようなサブシーケンスへアクセスするス テップを示すフローチャートである。

図６は、ストリングか許容可能かとうかとそのカテゴリー集合を示すエンディン グデータを得る場合に図４のようなサブシーケンスへアクセスするステップを示 すフローチャートである。

図７はデータユニットの文字サブシーケンスを示す概略図である。

図８は、図５の方法を実行するためのより詳細なステップを示すフローチャート てあ−る。　− 図９は、図６の方法を実行するためのより詳細なステップを示すフローチャート である。

図１０は、カテゴリー集合データをリターンするためのＮビットベクトルの概略 図である。

図ＩＩは、認識のためにストリングデータを使用するシステムの要素を示す概略 ブロック図である。

図１２は、ストリングデータを含むソフトウェア製造物の概略図である。

詳細な説明 Ａ、　一般的特徴 図１および２は本発明の一般的特徴を示す。図１はストリングデータの一般的特 徴を示し、該データはアクセプタンスデータおよびカテゴリー集合データを得る ためにアクセスされることが可能である。図２は、図１に示されるようなストリ ングデータを使用する場合の一般的ステップを示す。

図１はシステムＩＯを示しており、そこではストリングデータ１２が使用される 。例えば、ストリングデータ１２はプロセッサ１４によりアクセス可能なデータ 保存媒体により保存されることか可能であり、例えば、ストリングデータ１２は 、フロッピーディスク、ＣＤ−ＲＯＭ、またはこれらに類するもののようなソフ トウェア製造物に保存されることか可能である。プロセッサ１４は、ストリング の文字を示す文字データ１６を受信することもまた可能である。プロセッサ１４ はアクセプタンスデータを与えることが可能であり、該データは文字のストリン グか許容可能であることおよびストリングに対するカテゴリー集合を示す。

図１は、ストリングデータ１２内のデータユニット３ｏのシーケンスを示す。

文字データ１６が文字ｒｍｉＸＪを示す場合、例えば、シーケンス３ｏは文字「 ｍＪを示すサブシーケンス３２と、文字「ｉ」を示すサブシーケンス３４と、文 字ｒＸＪを示すサブシーケンス３６とを含むことが可能である。各サブシーケン スは１つまたはそれ以上のデータユニットを含むことが可能である。

サブシーケンスは文字を示す情報に加えて他の情報を含むことが可能である。

例えばサブシーケンス３６は、文字ｒＸＪを示す情報に加え、ストリング「ｍｉ Ｘ」か許容可能であることと、単語とローマ数字を含むそのカテゴリーとを示す 情報を含むこともまた可能である。プロセッサＩ４がストリングｒｍｉＸＪの末 尾に到達し、サブシーケンス３６にアクセス中である場合、この情報がプロセッ サ１４により使用されることが可能である。プロセッサ１４はこの情報を使用し てアクセプタンスデータを得ること力呵能であり、該データはｒｍｉＸＪが許容 可能ストリングであることと、１ｍ１ＸＪについての単語とローマ数字を含むカ テゴリー集合とを示す。

図２は、ストリングデータ１２を使用して文字をマツチする（文字データと突き 合わせて文字を確定する）場合にプロセッサ１４が従うことが可能なステップを 示す。ボックス５０のステップは、文字をマツチすることのリクエストとエント リロケーションとを受信することにより開始する。このエントリロケーションは ＦＳＭのスタート状態を表すロケーションであることが可能であるか、またはス トリングデータ１２内のその他のロケーションであることが可能であり、後者の ロケーションからは、そのロケーションに続くこと力呵能な代替可能な文字の集 合を示すデータユニットがアクセスされることが可能である。例えばそれは、デ ータユニットの文字のサブシーケンスのロケーションであることが可能である。

エントリロケーションからアクセスされることが可能なデータユニットは、該ロ ケーションに続く代替可能な文字の各々に対応するデータユニットのサブシーケ ンスを含むことが可能である。

ボックス５２のステップはストリングデータ１２内のエントリロケーションにア クセスする。次にボックス６０のステップは該ロケーションに続く代替可能な文 字を示すデータユニットにアクセスし、エントリロケーションに続くことが可能 な文字の内の１つと文字がマツチするかどうかを最終的に決定する。文字がマツ チする場合、ボックス６２のステップはマツチする文字のサブシーケンスのロケ ーションをリターンする。一方エントリロケーションに続くことが可能ないづれ の文字にも文字がマツチしない場合、ボックス６４のステップはマツチされるス トリングが許容可能でないことを示すデータをリターンする。

図３は、ストリングデータ１２を使用してストリングに対するエンディングデー タを得る場合にプロセッサ１４が従うことが可能なステップを示す。ボックス７ ０のステップは、エンディングデータのリクエストとエンディングロケーション とを受信することにより開始する。ボックス７２のステップはストリングデータ １２内のエンディングロケーションにアクセスする。ボックス８ｏのステップは 、エンディングロケーションで終了するストリングが許容可能なストリングであ るかとうかを決定する。許容可能である場合、ボックス８２のステップはエンデ ィングデータをリターンし、該データはストリングが許容可能であることを示す と共にストリングに対するカテゴリー集合を示す。ストリングが許容可能でない 場合、ボックス８４のステップは許容可能でないことを示すデータをリターンす る。ボックス８０．８２、および８４のステップは、図１のエンディングサブシ ーケンス３６のようなエンディングサブシーケンスがらのアクセプタンス情報お よびカテゴリー集合情報を使用して実行されることが可能である。

図２および３のステップは文字認識において一体となって使用されること力呵能 である。例えば、候補ストリングの各文字に対してプロセッサ１４が図２のステ ップを実行することが可能である。先行する文字がマツチしているようなロケー ションからスタートする任意の文字がマツチしない場合、プロセッサ１４はスト リングが許容可能でないことを示すデータを得ることが可能である。ストリング の最終文字をマツチする際、ストリングが許容可能がどうかを決定すること、お よび許容可能な場合にそのカテゴリー集合を示すデータを得ることのために最終 文字かマツチされたロケーションにおいてプロセッサ１４は図３のステップを実 行することが可能である。

前述の一般的特徴は多くの方法を用いて様々なマシン上で実施されることが可能 である。本発明は、Ｓｕｎ　５ｐａｒｃＳｔａｔｉｏｎ上ての実行を目的とした Ｖｅｎｕｅ　Ｃｏｒｐｏｒａｔｉｏｎの１ｓｐプログラム言ｉｇＭｅｄｌｅｙバ ージョンで、またＳｕｎ　ＳｐａｒｃＳｔａｔｉｏｎＳＭａｃｉｎｔｏｓｈパー ソナルコンピュータ、および他のマシン上での実行を目的としたＣプログラム言 語で実施された。

１　文字サブシーケンス 図４から６は、本発明を実施する場合に使用することが可能なストリングデータ の高レベルな特徴を示す。図４は文字サブシーケンスおよび該サブシーケンスと 他のサブシーケンスとの関係を示す。図５は、文字をマツチすることのリクエス トに応答して文字サブシーケンスにアクセスする場合のステップを示す。図６は 、エンディングデータに対するリクエストに応答して文字サブシーケンスにアク セスする場合のステップを示す。

図４の文字サブシーケンス１００はいくつかのタイプの情報を含む。ラベル情報 １０２は文字タイプを示す。Ｎｅｘｔサブシーケンス情報１０４は、サブシーケ ンス１００が次のサブシーケンスを有するかどうかと、次のサブシーケンスを有 している場合は代替可能なサブシーケンスのロケーションとを示す。Ａｌｔサブ シーケンス情ｌＦｉ　１０６は、サブシーケンス１００が代替可能なサブシーケ ンスを有するかとうかと、代替可能なサブシーケンスを有している場合はそのサ ブシーケンスのロケーションとを示す。エンディング情報１０８は、ラベル情報 １０２にマツチする文字て終了しているストリングか許容可能なストリングであ るかとうかと、許容可能な場合にはストリングのカテゴリー集合とを示す。

図４に示されるような相互リンクされた文字サブシーケンス集合は、ＦＳＭを表 すために一体となってリンクされることか可能である。図に示されるように、文 字サブシーケンス！００は、１つまたはそれ以上のサブシーケンスに対する次の 、または代替可能なサブシーケンスであることが可能である。

図５は一般に図２のステップに従う。ボックス１２０のステップは、関数［Ａｄ ＶａｎＣｅＪの呼び出しの受信から開始し、該関数はロケーションと文字タイプ と共に呼び出される。ボックス１２２のステップはロケーションを使用して文字 サブシーケンスにアクセスする。ボックス１２２のステップはまたサブシーケン スのＮｅｘｔ情報を使用し、該サブシーケンスの次のサブシーケンスのロケーシ ョンを示すデータを得る。ボックス１２４のステップは次のサブシーケンスのロ ケーションを示すデータを使用してそれにアクセスする。

ボックス１２６のステップは繰り返しループを開始し、次のサブシーケンスまた は代替可能なサブシーケンスがある場合にはマツチを見出すために該ループはそ れらにアクセスする。ボックス１２６のステップは現行サブシーケンスのラベル 情Ｉｆｆを使用し、文字タイプを示すデータを得る。ボックス１３０のステップ は、この文字タイプがボックス１２０で受信した文字タイプと同一かどうかに基 づいて分岐する。同一の場合、ボックス１３２のステップは現行サブシーケンス のロケーションを示すデータをリターンする。一方同一でない場合、ボックス１ ３４のステップは現行サブシーケンスのＡｌｔ情報を使用し、該サブシーケンス が代替可能なサブシーケンスを有するかどうかと、有する場合には代替可能なサ ブシーケンスのロケーションとを示すデータを得る。

現行サブシーケンスが代替可能なサブシーケンスを存していない場合、ボックス ＋４０の分岐はボックス＋４２のステップへ続き、ボックス１２０で受信した文 字はマツチされることか不可能であることを示すデータを該ステップはリターン する。一方サブシーケンスが代替可能なサブシーケンスを有している場合、ボッ クス＋４４のステップは代替可能なサブシーケンスのロケーションを示すデータ を使用し、ホックス１２６のステップへ戻る前に前記代替可能なサブシーケンス にアクセスする。

図６は一般に図３のステップに従う。ボックス１７０のステップは、関数［Ｅｎ ｄ　５ｔａｔｕｓＪの呼び出しの受信から開始し、該関数はロケーションと共に 呼び出される。ボックス１７２のステップはロケーションを使用して文字サブシ ーケンスにアクセスする。ボックス＋７２のステップはまたサブシーケンスのエ ンディング情報を使用し、該サブシーケンスが許容可能なストリングのエンディ ングサブシーケンスであるかどうかと、エンディングサブシーケンスである場合 には該ストリングに対するカテゴリー集合とを示すデータを得る。

サブノーケンスか許容可能なストリングのエンディングサブシーケンスでない場 合、ホックス１８０の分岐はホックス１８２のステップへ続き、該ステップはス トリングか許容可能でないことを示すデータをリターンする。一方サブシーケン スか許容可能なストリングのエンディングサブシーケンスである場合、ボックス １８４のステップはストリングに対するカテゴリー集合を示すデータをリターン し、該データはまたストリングか許容可能であることを暗に示す。

２　エンコーディングおよびデコーディング本発明の実施において文字サブシー ケンスは多くの方法でエンコード（符号化）およびデコード（復号化）されるこ とが可能である。表１はバイト値空間が配置されることか可能となる１方法を示 し、該配置によりいくつかのバイト値が文字バイトおよびカテゴリーバイトの両 者として使用されることが可能となる。図７は文字サブシーケンスを示し、該サ ブシーケンス内の各データユニットは表１の配置から得られるバイト値となって いる。図８は表１の配置に対して図５のステップがとのように実施されるかを示 す。図９はカテゴリー集合データを得るためのステップを示す。図１０はカテゴ リー集合データをリターンするためのビットベクトルを示す。

表１ 表１のバイト値はＯから２５５の範囲にあり、従って８ビツト長である。Ｎは個 別の６ビツトラベルの数であり、後により詳細な説明を行う。Ｐｌはロングポイ ンタバイトコードの数であり、Ｐ２は中間サイズポインタバイトコードの数であ る。表１に見られるように、ショートポインタバイトコードの数は２５５−（４ Ｎ＋Ｐｌ　十Ｐ２　）である。

ハイド値のブロックは６つの異なるタイプの文字に割り当てられることが可能で あり、各タイプは最終タイプ、代替可能タイプ、およびＥＯＢ　（分岐終了）タ イプのいくつかから成る組み合わせとなる。しかし表１では特別なＥＯＢバイト か値Ｏを割り当てられ、分岐終了を表す任意のバイトに続くことが可能である。

現行の実施において、このバイトがショートポインタバイトとして扱われる場合 、自身に回帰するサブシーケンスから始まる最終でないデータユニットを該バイ トは指示する。このことはＥＯＢバイトの後に最終データユニットに到達するこ とが不可能であることを保証する。

ＥＯＢバイトの結果として、各文字は４つの異なるタイプ、即ち本文中で許容可 能とも呼ばれている最終タイプと、本文中でＡｌｔとも呼ばれている代替可能タ イプとから成る、文字の４つの存在可能な組み合わせのみを有することとなる。

文字について４つのタイプのみを有することは、各文字のタイプが２ビツトで表 されることか可能となることから有利である。該ビットは比較のためにマスクさ れることが可能であり、テーブルルックアップを行うことおよびバイト値につい ての他の複雑なデコーディングを行うことの必要性が回避される。従って表１は 、Ｎ−２ｇＩの各文字に対して４つの連続したバイト値を割り当てる。

表１はまたタグマークに対しても４つの連続したバイト値を割り当て、タグマー クは文字としては翻訳されず、先行する文字が許容可能ストリングの末尾である ことを示す。従ってタグマークに続くバイトは文字以外のものとして翻訳され、 表１はタグマークバイト値および文字バイト値がカテゴリーバイト値として翻訳 されることも可能であることを示す。タグマークへのアクセスの後にデータユニ ットのシーケンス内でバイト値かアクセスされる場合、この翻訳はタグマークお よび文字／カテゴリー範囲内のバイト値に適用される。

表１はまたテーブルラベルに対しても４つの連続したバイト値を割り当て、テー ブルラベルは文字としてもまたカテゴリーとしても翻訳されず、次のバイトがテ ーブルのポインタであることを示す。テーブルラベルは随意に選択される方法で あり、ＦＳｔｖｉ内の状態が多数の出力遷移を有する場合、ＦＳＭを表すストリ ングデータの検索に必要となる時間を低減するために使用されることが可能であ る。ＦＳＭ変換器が一般的規則を要約する場合、ＦＳＭが許容可能ストリングの 合成を可能とする場合、または許容可能ストリングと句読記号のような他のエレ メントとの合成であることが可能なストリングをクラス分けするためにＦＳＭが 使用される場合、テーブルラベルは有利であることが見出されている。そのよう な状況における状態はＦＳＭのスタート状態に似ており、該状態は多数の出力遷 移を有する。

各テーブルはＮ−１ｇのエントリと共に実施されることが可能であり、この結果 、タグマークバイトから文字／カテゴリーバイトを通じて各ラベル値に対するエ ントりは１つとなる。これはテーブルラベルが最高のラベル値であり、テーブル はテーブルラベル自体に対してエントリを存する必要がないためである。エント リは同一長であり、この結果、６ビツトラベル値にエントリ長を掛は合わせるこ とにより、与えられたラベル値に対するエントリがアクセスされてテーブル内へ のオフセットが得られることが可能となる。

各エントリはラベルバイトと共に始まる。テーブルラベルに先行するロケーショ ンからラベル値がマツチされることが可能である場合、ラベル値のエントリは同 一のラベル値を伴うラベルバイトを存する。一方テーブルラベルに先行するロケ ーションからラベル値かマツチされることが可能でない場合、ラベル値のエント リは異なるラベル値を伴うラベルバイトを有する。例えば、マツチされることか 可能てない各エントリに対するラベルバイトとしてテーブルラベルバイトか使用 されることが可能であり、これはそのラベル値がいづれのエントリのラベル値と も異なるためである。

各エントリはまたラベルバイトに続くポインタフィールドを含み、該ポインタフ ィールドは最長ポインタを保持するのに充分な大きさとなっている。現行の実施 において、各最長ポインタは３ハイドてあり、このためエントリ長は４バイトで ある。テーブルラベルに先行するロケーションからラベル値がマツチされること か可能である場合、ラベル値のテーブルエントリのポインタフィールドは、ラヘ ルに対する次のサブシーケンスのポインタ、または次のサブシーケンスがない場 合には特別なＥＯＢハイドを有する。

前述のようなテーブルは、テーブルのエントリのいくつかが不適正となる状態に より共存されることが可能である。このことは、テーブルラベルが常に最終遷移 となるよう各状態の出力遷移か順序付けられている場合に実行されることが可能 である。テーブルエントリか不適正となる遷移についての情報を与えるために出 力に先立つ遷移が使用されることが可能である。

一般に、テーブルラベルかどの状態に続くへきであるかに関する選択は、特定さ れるデータおよびタスクに強く依存する時間的空間的な複合したトレードオフを 伴う。より多くのテーブルの使用は検索速度を改善するが、テーブルを含むスト リングデータを保存するために必要となる空間を増加させる可能性がある。代替 可能な終端句読記号を状態が表すような特定の状況においては、テーブルは劇的 な速度の改善を可能とすると共に全体空間を低減する。これは与えられたテーブ ルを非常に多数の状態が共有することが可能なためである。

文字／カテゴリーバイト値と同様に、タグマークバイト値の下位２ビツトが使用 されて該ハイド値が代替可能なデータユニットを有するかどうかが示されること か可能である。タグマークが許容可能なストリングの末尾であるかどうかを示す ヒツトは考慮する必要がない。これはタグマーク自体は許容可能なストリングの 末尾とは決してならず、許容可能なストリングの末尾の文字に常に続くためであ る。タグマークの最初のバイト値は本文中でｒｃｈａｒＢａｓｅＪと呼ばれ、４ の倍数となる２５６−４Ｎである。従って、各文字バイトの下位２ビツトは、文 字を識別する上位６ビツトを得るためにマスクされることが可能である。

テーブルラベルの下位２ビツトも同様に、有用な情報を与えるために必要に応じ て使用されることか可能である。例えば、それらはテーブルのポインタ長を示す ために使用されることが可能である。

文字／カテゴリーハイドはエスケープコードを含むことが可能である。エスケー プフードと、ストリングデータ内てこれに続くこの他のバイトとを合わせたもの は、文字の総数かＮ−２より大きい場合に文字をエンコードするために使用され ることが可能であり、各サイズのポインタ数を最適化するためにＮが選択される 場合にこのようになる傾向にある。終端句読記号のような、許容可能なストリン グの末尾に現れる全ての文字に対してエスケープコードが使用される場合、終端 句読記号は全て無効にされて単−状態にされることが可能であり、この状態はま たハイフン、もしくは合成単語の部分となることが可能な他の文字に対するスタ ート状態へ戻る単一遷移を有する。しかしエスケープコードは前記以外の文字に 対して使用することか望ましく、従っていつエスケープコードを使用するかの選 択もまた複合したトレードオフとなる。

特定されるデータまたは特定されるタスクに対して有利であれば、代替可能な多 様なエンコーディングか使用される二とが可能である。例えば、全ての分岐がカ テゴリーバイトと共に終了する場合、および全てのカテゴリーバイトが分岐の終 了である場合、特別なＥＯＢバイトは無視されることが可能である。最終タイプ の文字ハイドに常にタグマークハイドか続く場合、およびカテゴリーバイトが常 に最終タイプである場合、文字バイトまたはカテゴリーバイトが代替可能エレメ ントを有するかとうかを示す単一ヒツトを使用することもまた可能である。これ らの方法は、例えば、ノヨートポインタの数を増加させるために使用されること か可能である。値を示す側々のブロックか文字およびカテゴリーに対して割り当 てられる場合、タグマークバイトか除去されることもまた可能であることか予想 、される。これは最終文字ハイドに続くカテゴリーバイトは最初の出力遷移とし て設定されることか可能であるためである。即ち、文字バイトに続くカテゴリー ハイドの出現は、文字バイトか許容可能ストリングの末尾にあることと、カテゴ リーハイドかストリングに対するカテゴリー集合の始まりにあることとを示すた めである。

タグマークハイド、または池のエンコーディングにおけるこれと同等のものは、 ＦＳＭ内の任意の最終状態に続く特別な遷移として考えられることが可能である 。タグマーク遷移に続くものは、最終状態で終了した全てのストリングに適用可 能なストリングカテゴリーとしてデコートされるバイト集合である。カテゴリー の例は、メイン辞書、ユーザー辞書、ローマ数字、アラビア数字、でんわ番号、 データ等を含む。

図７はデータユニットのシーケンス２００内にある多（のデータユニットを示す 。データユニット２０２．２０４．２０６．２０８．２１０、および２１２は一 体となって文字サブシーケンスを形成し、該サブシーケンスは図１のサブシーケ ンス３６と同一の情報を含む。データユニット２２０はサブシーケンスの次の文 字サブシーケンスの始まりにあり、データユニット２２２はサブシーケンスの代 替可能な文字サブシーケンスの始まりにある。タグマークバイトであるデータユ ニット２０４がデータユニット２０２の次バイトとして例示されており、この場 合は文字サブシーケンスのデータユニットが隣接する。しかしデータユニット２ ２０か代わりに次バイトとなることが可能であり、またデータユニット２０４か 代替可能タイプとなることが可能である。図に示されるようにこの場合は文字の データユニットが隣接しないことか予想される。

ノーケンス２００内のデータユニットは、ポインタを除く表１のバイト値の全て を示している。データユニット２０２．２２０、および２２２は文字バイトであ る。データユニット２０４はタグマークバイトである。データユニット２０６お よび２１０はカテゴリーハイドである。そしてデータユニット２０８および２１ ２はＥＯＢバイトである。

文字ハイドの各々は図に示される２つの下位ビットを含む。第１のビットは該ハ イドか許容可能ストリングの末尾であるかとうかを示し、第２のビットは該バイ トが代替可能ハイドを有しているかどうかを示す。タグマークバイトでは、第１ の下位ヒツトは該ハイドか許容可能ストリングの末尾でないことを示し、第２の ヒツトは該バイトが代替可能バイトを有しているかどうかを示す。カテゴリーハ イドの各々ては、第１のヒントは該バイトが許容可能ストリングの末尾であるこ とを示し、第２のビットは該バイトか代替可能バイトを存しているかどうかを示 す。

図８のステップは、図５のボックス＋２０に続くステップを置き換えることが可 能である。ホックス２４０のステップは、図５のボックス１２０で受信されたロ ケーションをインクリメントし、インクリメントされたロケーションでのパイ＋ １直を？号る。ホックス２４２のステップは、得られたバイト値がＣｈａｒＢａ ｓｅより小さい、即ち該ハイド値がポインタハイド値であるかどうかに基づき分 岐する。ポインタバイト値である場合、ボックス２４４のステップはポインタｌ こより示されるロケーションに進み、該ロケーションてのバイト値を得る。

ポインタでないハイドか得られた場合、ホックス２５０のステップは該バイト値 からＣｈａｒＢａｓｅを差し引く。ボックス１２０で受信された文字が、４倍し てＣｈａｒＢａｓｅを加えることにより文字ハイドの範囲内へ以前にマツプされ ている場合、ＣｈａｒＢａｓｅを差し引く必要はない。ボックス２５０のステッ プはまた、ｒｌｌｌｌｌｌｏＯＪのバイ）・と論理積をとるような方法で下位２ ヒツトをマスクし、ハイドのラベルを生成する。

ホックス２５２のステップは、ホックス２５０からのラベルとボックス１２０て 受信された文字とを比較する。ボックス２５４のステップは比較結果に基つき分 岐する。ラベルと文字かマツチする場合、図５のステップ１３２が実行されて現 行ロケーションがリターンされる。

ラベルと文字かマツチしない場合、ボックス２６０のステップはラベルかテーブ ルラベルであるかどうかを決定する。テーブルラベルでない場合、考慮されなけ 第１はならない代替可能ハイドかさらに存在する可能性がある。ボックス２６２ のステップは現行ロケーションのＡｌｔヒツトを得、該ビットはボックス２５０ のステップで保存されることか可能である。次にボックス２６０のステップは現 行ロケーションか代替可能バイトを有しているかとうかに基づき分岐する。有し ていない場合、図５のボックス１４２のステップが実行され、ボックス１２０て 受信された文字かマツチされることか不可能であることを示すデータかりターン される。

現行ロケーションか代替可能ハイドを有している場合、ボックス２６６のステッ プは代替可能タイプのロケーションヘ進み、該ロケーションでのバイトラ得ル。

代替可能ハイドは、Ａｌｔヒツトおよび図７に見られるようなＥＯＢバイトをカ ウントすることにより見出されることか可能である。次にボックス２７０のステ ップは、ホックス２４２のようにハイドかポインタであるかどうかに基づき分岐 する。ポインタでない場合、代替可能ノ１イトに到達したこととなり、この結果 ホックス２５０のステップが再び実行されることが可能である。バイトがポイン タである場合、ボックス２５０のステップの実行に先立つボックス２４４のよう に該ポインタの示すロケーションでのバイトが得られる。

ホックス２６０てテーブルラベルが見出される場合、ボックス２８０のステ・ノ ブはボックス１２０て受信された文字を使用して適正なテーブルエントリにアク セスする。前述のように、二のことは文字バイトを４倍してそれをテーブルラベ ルに続くポインタに加える二とにより実行されることが可能である。次にボック ス２８２のテストは、文字がテーブルエントリのラベルバイトとマツチするかど うかに基づき分岐する。文字がラベルバイトとマツチしない場合、図５のボック ス＋４２のステップか実行され、ボックス１２０で受信された文字がマツチされ ることか不可能であることを示すデータかりターンされる。一方文字がマツチす る場合、ホックス２８２てテーブルエントリのロケーションがリターンされ、こ のことは図５のホックス＋３２における現行サブシーケンスのロケーションのリ ターンと同一の効果を有する。

図８のステップは、図７のデータユニット２０２のロケーションを始まりとして 実行されることか可能である。文字ｒＸＪの次の文字が例えばｒｔＪである場合 、ホックス２５４のステップの最初の繰り返しにより、データユニツト２０４の タグマークラベルとのミスマツチが見出される。ボックス２６６のステップは、 データユニット２２０へ到達するためにＡｌｔビットおよびＥＯＢバイトをカウ ントし、ボックス２５４のステップの第２の繰り返しによりｒｔＪラベルとのマ ツチか見出され、その結果図５のボックス１３２のステップにおいてデータユニ ット２２０のロケーションかりターンされる。

図９はカテゴリー集合データを得る場合のステップを示す。バイト値が表１のよ うに配置されている場合、図９のステップは図６のボックス１７２．１８０、お よび１８４を置き換えることか可能である。

ボックス３００のステップは、図６のホックス１７０で得られたロケーションで のバイト値を得る。次にボックス３０２のステップは、バイト値が許容可能スト リングの末尾であるかどうかに基づき分岐し、このことは該バイト値の最終ビッ トにより示される。末尾でない場合、現行の文字サブシーケンスは許容可能スト リングのエンディングサブシーケンスではなく、従ってマツチ不可能であること かボックス１８２でリターンされる。バイト値が許容可能ストリングの末尾であ る場合、ボックス３０４のステップはＡｄｖａｎｃｅ　（ロケーション５　タグ マーク）を呼び出すことによりタグマークバイトのロケーションを得る。図５お よび８のステップが実行されてタグマークのロケーションがリターンされる。

ボックス３１０のステップはＡｄｖａｎｃｅによりリターンされるロケーション の次バイトへ進み、該バイトを得る。このステップは図８のボックス２４０．２ ４２、および２４４のステップと同一である。次にボックス３１２のステップは 得られたハイドの上位６ヒソトを示すデータを保存する。これは、これらビット か許容可能ストリングに対するカテゴリーの内の１つを示すためである。次に、 ホックス３２０のステップは得られたハイドのＡｌｔビットに基づき分岐する。

Ａｌｔビットかオンの場合、図８のボックス２６６．２７０、および２７２に関 連して先に記述されたように、ホックス３２２のステップは該バイトの代替バイ トへ進み、代替バイトを得る。次にホックス３１２のステップが再び実行される 。Ａｌｔヒントがオフの場合、ボックス３２４のステップはボックス３１２で保 存さオ］たデータに基つきカテゴリー集合データをリターンする。

図９のステップは、文字ｒＸＪをマツチした後、図７のデータユニット２０２の ロケーションを始まりとして実行されることが可能である。ボックス３２４てリ ターンされたカテゴリー集合データは、Ｌ！およびローマ数字のカテゴリーを示 す。

図１０はＮヒノトベクトル３５０を示し、該ベクトルはボックス３１２でバイト 値を保存するため、およびボックス３２４てカテゴリー集合データをリターンす るために使用されることが可能である。ボックス３１２のステップはバイト値か ら最終およびＡｌｔビットを除去することが可能であり、またバイト値を保存す るのにベクトル３５０内のとのビットがオンされるべきかを示すためにより高位 のビットを使用することか可能である。ボックス３１２において全てのカテゴリ ーバイトが処理された場合、ベクトル３５０はボックス３２４においてカテゴリ ー集合データとしてリターンされることが可能である。全てが０のベクトル３５ ０は、ボックス１８２においてストリングが許容可能でないことを示すデータを リターンするために使用されることもまた可能であり、これは、ストリングが許 容可能な場合には少なくとも１つのヒツトがオンされなければならないためであ る。

Ｆ　Ｓ　Ｍにイプシロン遷移を系統的に導入することにより、場合によってはよ りコンパクトなデータ構造か得られることが可能であり、これにより出力遷移集 合の共通部分の共有が促進される。即ち、ＦＳＭの任意の状態は２値状態の連鎖 に拡張されることが可能であり、最終状態を除くこれら状態の全ては、連鎖にお いて次の２値状態へのイプシロン遷移を有する。このイプシロンシェアリングの 方法はまた拡張されたＦＳＭを最小化することを含み、最小化の後に余分なイプ シロン遷移か除去される。

イプシロンシェアリングの方法か使用される場合、タグマークバイトに続いてカ テゴリーバイトが配置される順序は、（特定なバイト等を無効にする）無効操作 を適切に改善するよう選択されることか可能である。例えば、最も頻繁に発生す るカテゴリーはカテゴリーハイドの各集合において最後に配置されることが可能 であり、最も発生しないものは最初に配置されることが可能である、等となる。

表１の配置において、付加的な無効操作を目的として最も頻繁に発生するカテゴ リーに対して最も頻繁に発生する文字と同一のバイト値を割り当てることが有利 である可能性かある。一般に、目的とすべきことは頻度の偏りを有効に利用して より良いデータ圧縮を得ることである。

３、　製造物 前述のエンコードされたストリングデータは、図１１に示される認識システムで 使用されることか可能である。図１２はそのようなシステムで使用されることか 可能なソフトウェア製造物を示す。

図１１において、プロセッサ３７０は画像を定義するデータをイメージソース３ ７２から受信するために接続され、イメージソースは例えばスキャナであること か可１１ヒである。プロセッサ３７０はまた認識結果を示すデータを認識出力３ ７４へ与えるために接続され、ＬＦ！ｉ出力は例えばディスプレイであることが 可能である。プロセッサ３７０はまたソフトウェア入力デバイス３７６からソフ トウェアをロートするために接続され、ソフトウェア入力デバイスは、フロッピ ーディスク１へライブ、ＣＤ−ＲＯＭプレイヤー、モデム、ネットワーク回線、 または、データ保存媒体上のソフトウェアにアクセスすることが可能であるかも しくは通信チャネルを通して伝送されるソフトウェアを受信することが可能であ るような他の周辺装置であることか可能である。

認識を実行する場合、プロセッサ３７０は命令メモリ３８０にアクセスし、認識 命令３８２を実行する。認識命令はストリングデータアクセス命令３８４の呼び 出しを含む。データメモリ３９０はプロセッサ３７０によりアクセスされるデー タを保存する。プロセッサ３７０は、ストリングデータアクセス命令３８４を実 行する場合はストリングデータ３９２にアクセスし、認識命令３８２を実行する 場合には画像データ３９４にアクセスする。

図１２のソフトウェア製造物４００はデータ保存媒体４０２を含み、データ保存 媒体は、フロッピーディスク、ＣＤ−ＲＯＭ、磁気テープ、またはデータを保存 することか可能なその他の媒体を含む。媒体４０２はストリングデータ４０４と 、ス）・リングデータ４０４に関連して実行されることが可能な命令とを含む。

Ｕ！Ｊ１２に示される実施において命令は、ロート命令４１０１スタートロケー シヨン命令・１１２、アドバンス命令４１４、エンドステータス命令４１６、お よびフリー命令４１８を含む。

ロート命令４１０は、ストリングデータ４０４をデータメモリ３９０ヘロードす るためにプロセッサ３７０か実行するルーチンを含むことが可能である。このル ーチンはヘッダのメモリロケーションをリターンし、ヘッダはストリングデータ ４０４内のスタート状態にアクセスするための１つまたはそれ以上のオフセット を含む。プロセッサ３７０はまた媒体４０２上の命令を、実行前に命令メモリ３ ８０ヘロートすることか可能である。

スタートロケーション命令４１２は、データメモリ３９０内のストリングデータ ４０４にアクセスするためのスタートロケーションを示すデータを得るためにプ ロセッサ３７０か実行するルーチンを含むことが可能である。このルーチンは、 ロート命令４１０によりリターンされるヘッダのメモリロケーションと、スター ト決悪識別子と共に呼び出されることが可能である。ルーチンは次にヘッダにア クセスし、識別されたスタート状態に対するオフセットを得、オフセットを使用 してメモリ内にあるスタート状態のアクセスロケーションを得、そしてアクセス ロケーションをリターンする。他の命令と整合をとるため、スタート状態に対す るアクセスロケーションは、ストリングの最初の文字に応答して次のサブシーケ ゛／スかマツチされるようなロケーションとなっている。

アドバンス命令４１４は、ストリングデータ４０４内で処理を進めるためにプロ セッサ３７０か実行するルーチン、与えられたロケーション、および文字を含む ことか可能である。即ち、該ルーチンは図２のようなステップを実行することか 可能である。

エンドステータス命令４１６は、与えられたロケーションが許容可能ストリング の末尾であるかどうかを示すデータと、末尾である場合には該ストリングのカテ ゴリー集合とを得るためにプロセッサ３７０か実行するルーチンを含むことが可 能である。即ち、該ルーチンは図３のようなステップを実行することが可能であ る。

フリー命令４１８は、データメモリ３９０からストリングデータ４０４を読みだ すためにプロセッサ３７０か実行するルーチンを含むことが可能である。

図ＩＩの認識命令３８２は、データ保存媒体４０２からロードされる命令を呼び 出すルーチンを含むことか可能である。媒体４０２上に示される命令により実行 される機能は簡潔なものであるため、他のソフトウェアへのインターフェイスは 比較的簡潔となり、ソフトウェア製造物４００は様々な認識方法で使用される二 とか可能である。

現行の実施において、ＦＳＭ生成ルーチンに対して特別なユーザーインターフエ イスを与えることにより、ストリングデータ４０４のバリエーションの設定が促 進される。ストリングのリストを含むファイルを用いて、または特別な文法形態 の定義を用いても、ユーザーは文字ストリングのカテゴリーを定義することが可 能である。例えば次のような場合に文法が使用されることが可能である。アラビ ア数字、数学的表現、または通貨量のような限りな（多い許容可能ストリングを 有するカテゴリーを定義する場合、ローマ数字、電話番号、またはソーシャルセ キュリティ一番号のように許容可能ストリングがアルゴリズムの規則に従う場合 、句読記号もしくはハイフンを含むか、ストリングを結合して合成ストリングを 形成するか、またはリスト内のストリングて発生するものに類似した妥当性のあ る文字パターンを含むようなバリエーションを付加することによりストリングリ ストのようなカテゴリーを拡張する場合である。

現行の実施において、ユーザーは許容可能ストリングを様々な方法で記述する規 則的表現を与えることが可能である。例えば、ストリングが順に、始まりとなる 句読記号のサブストリング（部分ストリング）、随意に選択されるアラビア数字 、分離符号のサブストリング、辞書からの許容可能ストリング、分離符号のその 他のサブストリング、辞書からのその他の許容可能ストリング、等を含み、そし て終了句読記号のサブストリングと共にストリングが終了する場合にはストリン グが許容可能であるということを何らかの表現により示すことが可能であり、も しくはストリングか順に、■から９の内の１つの数字、０から始まりＯから９の 内の２つの数字までの数字のサブストリング、そして次に終了するかさもなくば ０から９の内の３つの数字が続くコンマを含む任意の数のサブストリングが続く 場合にはストリングが許容可能であるということを何らかの表現により示すこと が可能である。

各カテゴリーの定義はそれらに対応するＦＳＭを生成するために使用されること か可能である。カテゴリーデータが各ＦＳＭに含まれ、このことはＦＳＭの許容 可能ストリングの各々がタグマークおよびカテゴリー識別子と共に終了すること を示す。前述のような複合ストリングに対するカテゴリーは、最終ストリングの ような複合ストリングの構成部分の内の１つのカテゴリーであることが可能であ る。

現実的である場合、公知のＦＳＭ合成アルゴリズムを用いて全てのカテゴリーに 対するＦＳＭが結合されて単一なＦＳＭとなることが可能である。合成ＦＳＭは 、ストリングの許容可能集合を全く変えること無く確定され、最小化される。

結果として得られるＦＳＭは１つのスタート状態を有する。ＦＳＭの状態シーケ ンスはサイクルを含むことが可能てあり、サイクルは自身に回帰する状態からの 、または状態シーケンスの初期に発生したその他の状態へのポインタを含む。

全てのカテゴリーに対するＦ　Ｓ　Ｍを結合し、単一で確定され最小化されたＦ ＳＭにすることがコンピューター上実際的でない場合、１つまたはそれ以上の付 加的ＦＳＭが含まれることが可能であり、これら各々は対応するスタート状態お よびカテゴリーデータを存しており、従ってこれら各々が許容するストリングの 各々は特別なカテゴリー識別子と共に終了する。

結果として得られる１つまたはそれ以上のＦＳＭの組み合わせは、次にエンコー ドされてデータ構造を生成することか可能となる。該データ構造はソフトウェア 製造物４００を生成する場合にデータ保存媒体４０２上に保存されることが可本 発明は多くの方法で認識問題に適用することが可能であり、それら方法はインク リメンタルルックアップの方法を含み、この方法ではシーケンス内の各文字を与 える二とによりメイン認識ルーチンかストリングをチェックする。その結果、許 容不可能な候補ストリングの集合が許容不可能なプリフィクスを共存する場合、 単一のルックアップ動作でこれら全てが除去されることが可能となる。メイン認 識ルーチンはまた、過去に与えられた文字のロケーションを示すデータ構造を維 持することが可能であり、その結果、過去の選択点への引き返しがより効率的と なる二とが可能となる。

本発明の方法は文字のストリングの認識に限られず、ストリングが離散的カテゴ リーに振り分けられるような他のタイプのエレメントのストリングの認識に対し ても適用可能であることが予想される。例えば、ハントライティングの認識では ストロークのストリングか単語のカテゴリーに振り分けられる。同様に、音声認 識では音素のストリングが単語のカテゴリーに振り分けられる。

本発明の方法はスペル訂正問題に対しても適用可能であることが予想される。

例えば、本発明の方法はキーホードのような入力デバイスからの文字シーケンス 対して適用可能であることか予想され、タイプミスを訂正する手助けとなる。

Ｄ、　付記 本発明は、データ保存媒体上でソフトウェア製造物が得られるような実施に関連 して記述されてきた。本発明はまた、電話回線またはネットワークにおけるよう な伝送を通して得られるソフＩ・ウェア製造物と共に実施可能であることか予想 される。

本発明はソフトウェアの実施に関連して記述されてきたが、本発明は特別なハー ドウェアと共に実施可能であることか予想される。

本発明は、修正、バリエーション、および拡張を伴う様々な実施に関連して記述 されてきたか、他の修正、バリエーション、および拡張も本発明の範囲内にある 。従って、本発明は本文中に含まれる記述および図面によっては限定されず、請 求の範囲のみによって限定されるものである。

図１ 図６ 図７ ボックス＋２０から ボックス＋７０から 図９ ビットＮ−１ビット２　ビット１　ビット０図１１ 区■２ フロントページの続き （７２）発明者　ムリンス、アティー　ティー。

アメリカ合衆国　０２１１５　マサチューセッツ州　ボストン　ナンバー　２　 マーボラフ　ストリート３９６

Claims (19)

【特許請求の範囲】
1. １．プロセッサを含む文字認識システムで使用するための製造物であって、デー タ保存媒体と、 データ保存媒体に保存されるストリングデータであって、各々が文字認識システ ムのプロセッサによりアクセスされることが可能な複数のデータユニットをスト リングデータが含み、文字についての複数の許容可能ストリングの各々に対して 、ストリングの文字の文字タイプを示す文字データを使用してプロセッサがアク セスすることが可能なデータユニットの対応するシーケンスをデータユニットが 含む、ストリングデータと、 複数のカテゴリーから成る第１の集合内にある第１のストリングを含む複数の許 容可能ストリングであって、第１のストリングのシーケンスの末尾でプロセッサ がアクセスすることが可能であり、かつ、第１のストリングが許容可能ストリン グの内の１つであることと第１のカテゴリー集合とを示す、第１のストリングの エンディングデータを得るためにプロセッサが使用することが可能であるデータ ユニットの対応するエンディングサブシーケンスを第１のストリングのデータユ ニットのシーケンスが含む、複数の許容可能ストリングと、それに対応するシー ケンスの末尾でプロセッサがエンディングサブシーケンスにアクセスすることが 可能なストリングが複数の許容可能ストリングの内の１つであることを示すアク セプタンス情報と、第１のカテゴリー集合を示すカテゴリー集合情報であって、 第１のカテゴリー集合が複数のカテゴリーの内の少なくとも１つを含む、カテゴ リー集合情報と、を含む製造物。
2. ２．各データユニットがバイトである請求項１に記載の製造物。
3. ３．言語の単語であることが可能な複数のストリングを複数の許容可能ストリン グが含む請求項１に記載の製造物。
4. ４．複数のカテゴリーから成る第２の集合内にある第２のストリングを複数の許 容可能ストリングが含み、第２のストリングのシーケンスの末尾でプロセッサが アクセスすることが可能であり、かつ、第２のストリングのエンディングデータ を得るためにプロセッサが使用することが可能であるデータユニットの対応する エンディングサブシーケンスを第２のストリングのデータユニットのシーケンス が含み、第２のストリングが許容可能ストリングの内の１つであることと第２の カテゴリー集合とを第２のストリングのエンディングデータが示す請求項１に記 載の製造物。
5. ５．複数のカテゴリーの内の共有される１つを第１および第２のカテゴリー集合 の両者が含み、共有されるカテゴリーを示す共有されるデータユニットをデータ ユニットが含み、第１のストリングのエンディングサブシーケンスおよび第２の ストリングのエンディングサブシーケンスの両者が共有されるデータユニットを 含む請求項４に記載の製造物。
6. ６．対応する文字タイプを有するエンディング文字を第１のストリングが含み、 エンディング文字の文字タイプを示す文字ラベル情報を含む文字ラベルデータユ ニットを第１のストリングのデータユニットのエンディングサブシーケンスが含 み、それに対応するシーケンスの末尾でプロセッサがエンディングサブシーケン スにアクセスすることが可能なストリングが許容可能ストリングの内の１つであ る二とを示す文字ラベルデータユニット内のビットをアクセプタンス情報が含む 請求項１に記載の製造物。
7. ７．第１のストリングのエンディングサブシーケンス内のアクセプタンスデータ ユニットをアクセプタンス情報が含み、それに対応するシーケンスの末尾でプロ セッサがエンディングサブシーケンスにアクセスすることが可能なストリングが 許容可能ストリングの内の１つであることを示す値をアクセプタンスデータユニ ットが有する請求項１に記載の製造物。
8. ８．アクセプタンスデータユニットヘのアクセスの後にプロセッサがアクセスす ることが可能な第１のストリングのエンディングサブシーケンス内のカテゴリー データユニットの集合をカテゴリー集合情報が含む請求項７に記載の製造物。
9. ９．第１のカテゴリー集合内の各カテゴリーに対して、第１のストリングのエン ディングサブシーケンス内の対応するカテゴリーデータユニットをカテゴリー集 合情報が含み、各カテゴリーのカテゴリーデータユニットがカテゴリーを示す値 を有する請求項１に記載の製造物。
10. １０．第１のカテゴリー集合が複数のカテゴリーを含み、第１のストリングのエ ンディングサブシーケンス内の複数のカテゴリーデータユニットをカテゴリー集 合情報が含む請求項９に記載の製造物。
11. １１．データ保存媒体に保存される制御データをさらに含み、ストリングの対応 するデータユニットのシーケンスにアクセスするためにストリングの文字を使用 する場合にプロセッサが実行することが可能である命令を制御データが含む請求 項１に記載の製造物。
12. １２．シーケンス内の第１のストリングのエンディングサブシーケンスの直前の データユニットの中間サブシーケンスを第１のストリングのシーケンスがさらに 含み，中間サブシーケンスがストリングデータ内の第１の位置を有し、エンディ ングサブシーケンスがストリングデータ内の第２の位置を有し、第２の位置を示 す第２のポジションデータを得るためにプロセッサが実行することが可能な第１ の命令集合であって、第１の命令集合を実行する場合に、第１の位置を示す第１ のポジションデータをプロセッサが使用して中間サブシーケンスにアクセスする 、第１の命令集合と、第１のストリングのエンディングデータを得るためにプロ セッサが実行することが可能な第２の命令集合であって、第２の命令集合を実行 する場合に、第２のポジションデータをプロセッサが使用してエンディングサブ シーケンスにアクセスする、第２の命令集合と、 を命令が含む請求項１１に記載の製造物。
13. １３．第１のストリングがエンディング文字を対応する文字タイプと共に有し、 エンディング文字の文字タイプを示す文字タイプ情報をエンディングサブシーケ ンスがさらに含み、第１の命令集合を実行する場合にプロセッサが第１のストリ ングのエンディングサブシーケンスにアクセスして文字タイプを示す文字タイプ データとエンディングサブシーケンスとを使用してマッチデータを得、文字タイ プデータにより示される文字タイプと文字タイプ情報により示される文字タイプ とがマッチするかどうかをマッチデータが示す請求項１２に記載の製造物。
14. １４．シーケンス内の第１のストリングのエンディングサブシーケンスに先立つ データユニットの中間サブシーケンスを第１のストリングのシーケンスがさらに 含み、第１のストリングのデータユニットのシーケンス内で中間サブシーケンス が１回発生し、第１のカテゴリー集合内にある第２のストリングを複数の許容可 能ストリングが含み、第２のストリングのデータユニットのシーケンスが第１の ストリングのエンディングサブシーケンスを含み、その結果、第２のストリング のシーケンスの末尾でプロセッサが第１のストリングのエンディングサブシーケ ンスにアクセス可能となり、かつ、プロセッサがそれを使用して、第２のストリ ングが許容可能ストリングの内の１つであることと第１のカテゴリー集合とを示 す、第２のストリングのエンディングデータを得ることが可能となり、第２のス トリングのデータユニットのシーケンス内で中間サブシーケンスが２回発生する 請求項１に記載の製造物。
15. １５．プロセッサと、 アクセスするためにプロセッサが接続されるメモリと、メモリに保存されるスト リングデータであって、各々がプロセッサによりアクセスされることが可能な複 数のデータユニットをストリングデータが含み、文字についての複数の許容可能 ストリング′の各々に対して、ストリングの文字を示す文字データを使用してプ ロセッサがアクセスすることが可能なデータユニットの対応するシーケンスをデ ータユニットが含む、ストリングデータと、複数のカテゴリーから成る第１の集 合内にある第１のストリングを含む複数の許容可能ストリングであって、第１の ストリングのシーケンスの末尾でプロセッサがアクセスすることが可能であり、 かつ、第１のストリングが許容可能ストリングの内の１つであることと第１のカ テゴリー集合とを示す、第１のストリングのエンディング′データを得るために プロセッサが使用することが可能であるデータユニットの対応するエンディング サブシーケンスを第１のストリングのデータユニットのシーケンスが含む、複数 の許容可能ストリングと、それに対応するシーケンスの末尾でプロセッサがエン ディングサブシーケンスにアクセスすることが可能なストリングが複数の許容可 能ストリングの内の１つであることを示すアクセプタンス情報と、第１のカテゴ リー集合を示すカテゴリー集合情報であって、第１のカテゴリー集合か複数のカ テゴリーの内の少なくとも１つを含む、カテゴリー集合情報と、を含むシステム 。
16. １６．ストリングの文字を使用してストリングのデータユニットのシーケンスに アクセスする場合にプロセッサが実行することが可能なメモリに保存された命令 をさらに含む請求項１５に記載のシステム。
17. １７．シーケンス内の第１のストリングのエンディングサブシーケンスの直前の データユニットの中間サブシーケンスを第１のストリングのシーケンスがさらに 含み、中間サブシーケンスがストリングデータ内の第１の位置を有し、エンディ ングサブシーケンスがストリングデータ内の第２の位置を有し、第２の位置を示 す第２のポジションデータを得るためにプロセッサが実行することが可能な第１ の命令集合であって、第１の命令集合を実行する場合に、第１の位置を示す第１ のポジションデータをプロセッサが用して中間サブシーケンスにアクセスする、 第１の命令集合と、第１のストリングのエンディングデータを得るためにプロセ ッサが実行することが可能な第２の命令集合であって、第２の命令集合を実行す る場合に、第２のポジションデータをプロセッサが使用してエンディングサブシ ーケンスにアクセスする、第２の命令集合と、 を命令が含む請求項１６に記載のシステム。
18. １８．システムを動作させる方法であって、プロセッサと、 アクセスするためにプロセッサが接続されるメモリと、メモリに保存されるスト リングデータであって、各々がプロセッサによりアクセスされることが可能な複 数のデータユニットをストリングデータが含み、文字についての複数の許容可能 ストリングの各々に対して、ストリングの文字を示す文字データを使用してプロ セッサがアクセスすることが可能なデータユニットの対応するシーケンスをデー タユニットが含む、ストリングデータと、複数のカテゴリーから成る第１の集合 内にある第１のストリングを含む複数の許容可能ストリングであって、第１のス トリングのシーケンスの末尾でプロセッサがアクセスすることが可能であるデー タユニットの対応するエンディングサブシーケンスを第１のストリングのデータ ユニットのシーケンスが含み、第１のストリングのエンディングサブシーケンス が、それに対応するシーケンスの末尾でプロセッサがエンディングサブシーケン スにアクセスすることが可能なストリングが複数の許容可能ストリングの内の１ つであることを示すアクセプタンス情報と、第１のカテゴリー集合を示すカテゴ リー集合情報であって、第１のカテゴリー集合が複数のカテゴリーの内の少なく とも１つを含む、カテゴリー集合情報と、を含む、複数の許容可能ストリングと 、をシステムが含み、 第１のストリングの文字を示す第１のストリングの文字データを使用して第１の ストリングのシーケンスにアクセスするためにプロセッサを動作させるステップ であって、第１のストリングのシーケンスにアクセスするためにプロセッサを動 作させるステップが、第１のストリングのエンディングサブシーケンスにアクセ スするサブステップを含む、プロセッサ動作ステップと、第１のストリングのエ ンディングサブシーケンスを使用して、第１のストリングが許容可能ストリング の内の１つであることと第１のカテゴリー集合とを示す、第１のストリングのエ ンディングデータを得るためにプロセッサを動作させるステップと、 を含むシステム動作方法。
19. １９．複数のカテゴリーがＮ個のカテゴリーを含み、第１のストリングのエンデ ィングデータが、Ｎビットを含むデータの項目であり、それらビットの各々が第 １のストリングがカテゴリーの内の対応する１つにあるかどうかを示す請求項１ ８に記載のシステム動作方法。