JPH058464B2

JPH058464B2 -

Info

Publication number: JPH058464B2
Application number: JP62023706A
Authority: JP
Inventors: Nobuyasu Ito; Hiroyasu Takahashi
Original assignee: International Business Machines Corp
Current assignee: International Business Machines Corp
Priority date: 1987-02-05
Filing date: 1987-02-05
Publication date: 1993-02-02
Also published as: EP0277356B1; JPS63198154A; EP0277356A2; US4903206A; EP0277356A3; DE3776783D1

Description

【発明の詳細な説明】

Ａ産業上の利用分野この発明はつづり誤りのある単語を自動的に訂
正したり、オペレータに正しい単語のつづりを助
言したりするのに用いるつづり訂正装置に関す
る。Ｂ従来技術コンピユータへの文書入力やデータ入力の負担
を軽減すべく、既存のテキストエデイタの改善に
加え、OCR、音声入力など様々な入力手法が提
供されてきている。しかしこれらのいずれにおい
ても入力誤りを完全に避けることは不可能であ
り、入力後のつづり誤りの検査と訂正とが不可欠
である。このためつづり誤りのある単語を見い出
し、さらにその入力文字列に対して正しいと思わ
れる単語の候補をオペレータに提示するプログラ
ムが開発されてきた。実用上からみるとこのようなプログラムの効率
を決定するのは入力文字列に対して候補となる単
語、すなわち比較的類似するつづりを有する単語
を選び出す過程である。候補単語はこののち入力
文字列と詳細にマツチングさせられ、それが正解
単語が判別される。もつとも簡単な方法は辞書内
の全単語を候補とし、その１つ１つと入力文字列
とをあらかじめ決められた距離式によりマツチン
グし、入力文字列との類似度を計算するものであ
る。しかし実用的な辞書の多くは１万語ないし２
万語以上のサイズであることからこの方法は計算
コスト上実用的ではない。そこで詳細なマツチン
グを行う前に候補単語を絞る方法としてたとえば
つぎのようなものが提案されてきた。 (1) 入力単語と先頭１文字が一致し、長さの差が
一定以上（通常１〜３文字）の単語のみを候補
とする。この手法は実用化されているプログラムに広
く採用されており、一例としてIBM社のWord
Proorを挙げることができる。 (2) 各文字に固定の数値を割り当て、入力単語の
つづりから一定の式に基づいてその入力単語の
値を計算し、その値をハツシングのキーとし、
値の差が一定以内の単語を取り出して候補とす
る。この手法についてはW.S.Rosenbaumおよび
J.J.Hilliardの論文“Multifont OCR
Postprocessing System”IBM Jounal of
research and development Vol.19、No.５、
pp.398−421、1975年５月に記載がある。詳細
についてはとくにpp403−404の説明を参照さ
れたい。 (3) 入力単語から得られる文字種集合と各単語の
文字種集合とを全要素間で比較し、差が一定以
内の単語を候補とする。なお、ここでは単語に
含まれるすべての文字種を要素とする集合を、
文字種集合と定義することにする。これについては特公昭59−29910号公報（米
国特許第435537号明細書）に詳細な説明があ
る。手法(1)は入力単語の先頭の文字が最も高い信頼
性を有するという仮定に基づくものである。この
仮定はキーボード入力においてはある程度妥当な
ものである。しかしOCRなどにおいてはこの仮
定は必ずしも満たされず、先頭１文字を誤つたた
めに正解が単語候補からもれてしまうことが起こ
り得る。また候補の減少率が低いため通常他の手
法、たとえば単語誤りの統計に基づいて可能性の
低いものは除くという手法を併用する必要があ
る。手法(2)は探索に要するコストは少ないが正解単
語の脱落という観点から見るとさらに検討を要す
る。各文字のどのような数値を割当てるべきかと
い検討も行われているが最悪の場合には１文字か
入れ替わつただけの入力文字列に対しても正解単
語が脱落し得る。手法(3)は一定の閾値に対してそれ以内の文字の
入れ替わりならば、正解単語の脱落は起こらない
ことが保証される。しかしこの方法では入力文字
列の文字種集合と全単語のそれとを比較する必要
がある。一回あたりの比較に要する計算コストは
比較的少ないとはいえ万単位の単語がある場合に
は計算コスト上問題が残る。Ｃ発明が解決しようとしている問題点この発明は以上の事情を考慮してなされたもの
であり、予め定められた閾値以内の文字の入れ替
わり、脱落、付加しか入力単語に存在しないので
あれば、その入力単語のつづりに基づいて決定さ
れた候補単語中に正解単語が含まれることを保証
することができ、しかも候補単語の決定の計算を
極めて少ないものに抑えることができるつづり誤
り訂正装置を提供することを目的としている。Ｄ問題点を解決するための手段この発明では以上の目的を達成するため単語の
文字種集合中の特定の文字種組み合わせに注目し
て候補単語を選択するようにしている。この特定の文字種組み合わせはつぎのように決
定される。入力単語に含まれる文字種を予め定められた
基準にしたがつて整列化する。整列化した文字種のうち上位のｎ個（ｎは整
数）を選ぶ。ｎ個の文字種のうちの任意のｍ個（ｍはｍ＜
ｎを満たす整数）からなる文字種組み合わせを
生成する。辞書中の単語はこのように抽出された文字種組
み合わせに基づいて分類され辞書中に記憶されて
いる。１個の単語に通常複数の文字種組み合わせ
が存在するので、１個の単語が複数のクラスに分
類されるのが普通である。入力単語に対する候補単語を選択するには、入
力単語から抽出された文字種組み合わせで特定さ
れる１または複数（通常は複数）のクラスに含ま
れる単語を辞書から取り出せばよい。この発明では上述の文字種組み合わせは単語の
属性と考えることができる。そしてこの属性は単
語の文字の置き換え、脱落、付加が一定の範囲の
ものであるかぎり、全面的には変更されることは
ない。すなわち少なくとも１つの文字種組み合わ
せはそのようなつづり誤りが加わつたとしても残
つているのである。したがつて上述のように特定
されたクラスの１つの中には正解単語が存在する
こととなる。この発明では文字の置き換え、脱落、付加が一
定の範囲のものであるかぎり、候補単語中に必ら
ず正解単語を含ませることができ、しかも入力単
語の属性から一意的に候補単語のクラスを判別で
き、特別に煩雑な計算を要しない。Ｅ実施例以下、この発明を印刷英数字OCRにより文書
入力システムに適用した一実施例について説明し
よう。なお、この発明を他の入力システムにも適
用できることはもちろんである。第１図はこの実施例の構成を全体として示すも
のであり、この図において、システムはパーソナ
ルコンピユータ１、ビツト・マツプ・デイプレイ
２、スキヤナ３および補助記憶装置４から構成さ
れている。破線内のブロツクすなわち認識部５、
後処理部６およびユーザーインターフエース部７
はソフトウエアとして実現されている。実用的に
は認識部５をハードウエアで実現するようにして
もよい。後処理部６はこの発明に直接関連する部
分であり、この後処理部６をソフトウエアで実現
しても計算量や処理速度上何ら支障がないことは
のちに理解される。第２図は第１図のシステムの手順を示すもので
ある。第１図および第２図において、オペレータ
が処理開始コマンドを発行するとユーザ・インタ
ーフエース部７はまずスキヤナ３にスキヤン要求
を供給する。文書８はスキヤナ３により検査さ
れ、イメージとして認識部５へ供給される
（S11）。認識部５ではイメージを１文字単位で切
り出したのち（S12）、切り出した１文字分のイ
メージがどの文字であるかを認識する（S13）。
識別の結果は唯一に決まると限らず、複数の候補
が出力されることもある。後述する第３図では第
１位の文字候補の列を枠で囲んで示してある。１
単語の認識が終了するとユーザーインターフエー
ス部７は後処理部６に対して認識結果のつづり誤
りの検査および訂正を要求する。後処理部６は認
識部５から供給された認識結果について補助記憶
装置４中の単語辞書を参照してつづりの確認を実
行し、辞書中に該当する単語が存在しない場合に
は、近似的に一致したつづりを有する単語を検索
する（S14）。この部分はこの発明と直接関連す
る部分であり、のち詳述する。ステツプ14の結果
はユーザーインタフエース部７を介してデイスプ
レイ２に表示され、オペレータが最終的に認識、
修正を行う（S15）。このようにしてコード化さ
れた正しい文書が得られることになる。つぎにこの発明に直接関連する後処理部６につ
いて説明する。なお、この後処理部６の機能とし
てはづぎの２つがある。 (1) 入力文字列が単語として正しいつづりである
か（単語辞書に存在するかどうか）を検査す
る。 (2) 入力文字列（あるいは認識結果そのもの）に
対して類似したつづりをもつ単語を探索する。機能(1)は機能(2)のサブセツトとして理解できる
のでここでは機能(2)についてのみ述べる。第３図は後処理部６の詳細を示しており、この
図において、後処理部６はクラス生成部９、検索
機構１０、マツチング部１１およびパーソナルコ
ンピユータ１の主記憶１２からなつている。クラ
ス生成部９は整列化部９ａ、上位４文字種選択部
９ｂおよび文字種組み合わせ生成部９ｃからなつ
ている。これら各部の構成は後述する第４図のス
テツプS22、S23およびS24にそれぞれ対応する。
この構成において、まず認識結果の第１位候補か
らなる文字列が入力文字列としてクラス生成部９
に供給される。クラス生成部はのちに詳述するク
ラスを生成する。検索機構１０は生成されたクラ
スをキーにして補助記憶装置４中の単語辞書を探
索し、候補単語を選択して主記憶１２に転送す
る。マツチング部１１に得られた候補単語と入力
文字列（あるいは認識結果）とのマツチングを実
行し、マツチング距離が閾値以内ならば確からし
い単語として出力する。以下、後処理部６の要部について順に詳述す
る。クラス生成部９第４図はクラス生成部９の処理手順を示してい
る。クラスとはｍ文字種（ｍは整数、たとえば
３）からなる文字種組み合わせに対応する属性名
として定義される。たとえば｛ａ、ｂ、ｃ｝、
｛ｄ、ｅ、ｆ｝はそれぞれ１つのクラスである。
そして所定の単語が特定のクラスに属すること
は、その単語から以下に述べる手順をへて得られ
る文字種組み合わせのなかに、そのクラスを特定
する文字種組み合わせが存在することを意味す
る。ではこのクラス生成部９の処理を第４図を参
照して説明する。ステツプS21 単語のつづりからその文字種集合を作成する。
従来技術の説明で述べたとおり、文字種集合とは
単語に含まれるすべての文字種を要素とする集合
である。［例］ example→｛ａ、ｅ、ｌ、ｍ、ｐ、ｘ｝ apple→｛ａ、ｅ、ｌ、ｐ｝ of→｛ｆ、ｏ｝ステツプS22 文字列集合を一定の基準により整列化する。こ
の例では単語の頻度を考慮しないときの各文字の
出現頻度の低さを用いている。この頻度順位を表
１に示す。［例］｛ａ、ｅ、ｌ、ｍ、ｐ、ｘ｝→［ｘ、ｐ、ｍ、
ｌ、ａ、ｅ］｛ａ、ｅ、ｌ、ｐ｝→［ｐ、ｌ、ａ、ｅ］｛ｆ、ｏ｝→［ｆ、ｏ］

【表】ステツプS23 整列化した要素の上位４文字種を取り出した部
分文字種集合を生成する。ただしもともと文字種
集合の要素が４個よりも少ない場合にはブランク
文字を加えて４文字種とする。ブランク文字は必
要に応じて重複して加えもよい。なお、以下でブ
ランク文字は“−”で表わす。［例］［ｘ、ｐ、ｌ、ｍ、ａ、ｅ］→｛ｘ、ｐ、ｍ、
ｌ｝［ｐ、ｌ、ａ、ｅ］→｛ｐ、ｌ、ａ、ｅ｝［ｆ、ｏ］→｛ｆ、ｏ、−、−｝ステツプS24 上述のように３文字種の組み合わせを１つのク
ラスと定義する。そして単語の部分文字集合の要
素を用いてつくることのできる３文字種組み合わ
せをすべて生成する。これは通常４個生成され
る。その単語は得られた３文字種組に対応するク
ラスに重複を許して、属しているものと定義す
る。英語の場合、文字種はブランク文字を含めて
27個あるので、合計2951個（＝₂₇C₃＋26）のクラ
スが存在し、各単語はこの中のいずれかに（通常
４クラスに重複して）属していることになる。［例］ appleの部分文字種集合は｛ｐ、ｌ、ａ、ｅ｝
であるから、appleは｛ａ、ｌ、ｐ｝、｛ｅ、ｌ、
ｐ｝、｛ａ、ｅ、ｐ｝および、｛ａ、ｅ、１｝の４
つのクラスに属する。単語辞書はこのようにして生成されたクラスに
基づいて検索できるようになつている。以下この
検索機構１０および辞書構成例について述べる。検索機構１０と辞書構成例第５図は辞書構成例を示す。第５図において、
辞書は第１インデツクス部１３、第２インデツク
ス部１４および辞書本体１５からなつている。第
１インデツクス部１３はクラスすなわち３文字種
組たとえば｛ａ、ｂ、ｃ｝と一意に対応するエン
トリを有し、各エントリごとにそのクラス第２イ
ンデツクスへの先頭ポインタと、属している単語
の数Ｎとを記憶している。第２インデツクス部１
４は各クラスと一対一に対応する複数の部分領域
１４ａを有している。そして第２インデツクス部
１４の部分領域１４ａ各エントリは単語と一意に
対応し、辞書本体１５へのポインタと単語の長さ
を有している。もちろん単語候補をより絞るため
の付加情報を有してもよい。各エントリは辞書本
体１５へのポインタおよび長さをキーとして整列
化されており、第１インデツクス１３から得た先
頭ポインタからＮ個順次読み出しを行えば、その
部分領域のエントリを全部アクセスできる。辞書
本体１５は単語のつづりやその他の情報を含んで
おり、第２インデツクス部１４の各エントリ中の
ポインタにより直接にアクセスされる。なおこの辞書構成においては、各クラスに属す
る単語を、そのクラスを特定する３文字種を上位
３文字種とする単語と、それ以外の単語とに別け
ておくことが好ましい。このようにすると単につ
づりが正しいかどうかを検査する場合に、余分な
検索を実行しなくてすむ。すなわち、つづりが正
しいかどうかの検査を行うには、上位３文字種が
入力単語に等しい単語のみを候補としてマツチン
グを実行すればよい。等しい単語が見い出せれば
つづりが正しいと判断し、見い出せなければつづ
りが誤つていると判断すればよいのである。そこ
で第５図の辞書を用いてつづりの誤りを検査する
場合には、入力文字列の上位３文字種組でクラス
を特定し、このクラスの中での上位３文字種組を
有する単語のみを取り出してマツチングを実行す
ればよい。以上のようにクラスを２分すれば不要
な検索を回避できる。なお、上位３文字種ではな
く、他の特定の列位置の３文字種を基準にしても
よい。つぎにこのように構成された辞書を検索機構１
０がどうのようにアクセスするかについて例を挙
げて説明しておく。部分文字種集合を｛ｘ、ｐ、
ｍ、ｌ｝とする場合について考える。まずクラス
生成部９から検索機構１０がクラス｛ｌ、ｍ、
ｐ｝を受け取ると、この検索機構１０は第１イン
デツクス部１３からクラス｛ｌ、ｍ、ｐ｝に属し
ている単語の数Niと、それらの単語の情報が格
納されている第２インデツクス部１４中の部分領
域１４ａ（Ciで示す）への先頭ポインタp_iとを得
る。ポインタp_iを用いて部分領域Ciにアクセスし
順に走査しながら入力文字列との長さが一定の閾
値以内のものを検索し、辞書本体１５の該当する
単語へのポインタpik（ｋ＝１、……、Ni）を得
る。そしてこれら辞書本体１５へのポインタをた
どり、たとえばsimple、exampleといつた単語の
つづりを読み出し、主記憶１２に転送する。同様にして他の３文字種組｛ｍ、ｐ、ｘ｝、
｛ｌ、ｐ、ｘ｝および｛ｌ、ｍ、ｘ｝についても
該当する単語を選択して転送する。この場合、ク
ラスの定義から明らかなように重複した単語がい
くつか存在する。たとえば単語exampleはクラス
｛ｌ、ｍ、ｐ｝、｛ｍ、ｐ、ｘ｝、｛ｌ、ｐ、ｘ｝お
よび｛ｌ、ｍ、ｘ｝のいずれにも属し、そのまま
で４度重複して転送される。検索装置１０はこの
重複した検索をチエツクして防止する機能も有す
る。以上のようにしてクラス生成部９および検索機
構１０により入力文字列に基づいて候補単語の選
択を実行できる。さまざまな入力文字列に対し、
このようにして得られる候補単語を表２に示す。
この表では、入力文字列との長さの差が１以内の
もののみ選択した。辞書のサイズは約11000語と
した。

【表】

【表】マツチング部１１マツチング部１１では選択された候補単語と入
力文字列（あるいは認識結果）とを照合してどの
程度類似しているかを測定する。この照合には
種々の手法を採用することができ、その詳細につ
いては当業者の自明であることから説明を行わな
いこととする。実施例の説明を終えるに際し、この実施例の特
徴をまとめておくことにする。 (1) 単語中の特定の位置にある文字が正解である
かどうかに依存しない。とくに先頭の文字が正
解であるかどうかに無関係であることは既存の
方法の中でも広く用いられている先行技術(1)に
比較して優位な点である。 (2) 処理が簡単である。部分文字集合をもとめる
操作は入力文字列中の文字種の確認と集合演算
のみであり要素の数も高々数個程度であるから
ハツシユ方式と比較しても同程度の探索コスト
ですむ。辞書のアクセスもまた候補単語選択の
過程では辞書本体にアクセスする必要はなく、
処理のほとんどはインデスク２へ順次アクセス
ですみ、辞書のアクセス（補助記憶装置４のア
クセス）は実用上問題にならない。 (3) 用いる部分文字集合の要素数(n)と文字組合せ
の要素数(m)とにより決定される閾値（ｎ−ｍ）
以内の文字の入れ替り、脱落、追加ならば正解
単語が候補からもれてしまうことはない。また
それ以上の入れ替りなどに対しても適切な整列
化の基準（本例で候補単語の減少率を高くする
ため頻度の低さを基準としているが、誤りの起
こり難さなども基準に取り入れることができ
る）のもとでは部分文字集合が大きく異なつて
しまうような単語の変形は極めてまれであり、
したがつて正解単語が脱落する確率は極めて低
い。 (4) 各クラス内の単語を上位ｍ文字種に着目して
２分することによりつづり検査時の検索を少な
くすることがでいる。 (5) 文字種組み合わせによる分類に加えて単語の
長さも考慮して候補単語を選択しているので、
効率よく候補の絞り込みを行える。なお、この発明の範囲は上述実施例のみに限定
されるものではなく、その趣旨を逸脱しない範囲
で変更を行うことができる。たとえば文字種は英
文字に限定されない。また。入力は音声認識やキ
ーボードを用いてもよい。また部分文字種集合の
要素数ｎや文字種組み合わせの要素数ｍを種々変
更できる。また整列化の基準として他の統計情報
等を用いてもよい。さらに辞書の構成としても
種々のものを採用してよい。Ｆ発明の効果以上説明したように、この発明によれば単語の
文字種集合の要素の特定の組み合わせをその単語
の属性とし、この属性に基づいて辞書中の単語を
分類している。他方入力単語から同様の属性を抽
出し、属性を同一とするクラスの単語を辞書から
取り出して入力単語の候補とするようにしてい
る。したがつて少ない計算量で候補単語を得るこ
とができる。しかも上述の組み合わせの生成規則
から所定の範囲の文字の入れ替え、脱落、挿入に
よるつづり誤りの訂正を保証することができる。

【図面の簡単な説明】

第１図はこの発明の一実施例全体として示すブ
ロツク図、第２図は第１図の実施例の手順を示す
フローチヤート、第３図は第１図の後処理部６の
詳細を示すブロツク図、第４図は第３図のクラス
生成部９を説明するためのフローチヤート、第５
図は検索機構１０がアクセスする単語辞書の構成
例を示す図である。１……パーソナルコンピユータ、２……デイス
プレイ、３……スキヤナ、４……補助記憶装置、
５……認識部、６……後処理部、９……クラス生
成部、１０……検索機構、１１……マツチング
部。

Claims

【特許請求の範囲】１つづり誤り訂正装置であつて、 (a) 正しくつづられている多数の単語を記憶する
記録手段を備え、前記単語の各々は前記単語に
割り当てられた文字種の組み合わせに基づいて
前記記憶手段から読みだすことができ、前記割
り当てられた文字種の組み合わせが、前記単語に含まれる文字種を所定の序列にし
たがつて整理し、文字列を得るステツプと、前記文字列から上位のｎ個のうちのｍ個から
なる文字種（ｎ、ｍは整数であり、ｎ＞ｍの関
係を有する）を選択するステツプと、によつて作られるような記憶手段と、 (b) 入力単語に含まれる文字種を前記序列に基づ
いて整列化する手段と、 (c) 整列化した文字種の上位ｎ個のうちのｍ個か
らなる文字種の組み合わせを求める手段と、 (d) 求められた文字種の組み合わせの各々に基づ
いて前記記憶手段から正しくつづられた単語を
読み出す手段と、 (e) 前記入力単語を前記読みだされた単語にマツ
チングさせる手段と、を含むつづ誤り訂正装置。２上記ｎ個の文字種には１以上のブランク文字
を含ませることができるようにした特許請求の範
囲の第１項記載のつづり誤り訂正装置。３上記序列は文字種の出現頻度の低さによるこ
ととした特許請求の範囲第１項または第２項記載
のつづり誤り訂正装置。４上記記憶手段は正しくつづられている単語を
記憶する記憶手段本体部と、上記文字種を組み合
わせに基づいて上記記憶手段本体部の記憶位置を
指定するインデツクス部とを有する特許請求の範
囲第１項、第２項または第３項記載のつづり誤り
訂正装置。５上記インデツクス部は、つづり誤りの検査時
に、上記入力単語の整列化された文字種のうちｍ
個の列位置の文字種に応じて、読み出すべき単語
の範囲を絞り込むようにされている特許請求の範
囲第４項記載のつづり誤り訂正装置。６上記ｍ個の列位置を上記のｍ位置とした特許
請求の範囲第５項記載のつづり誤り訂正装置。７上記インデツクス部は上記入力単語の長さに
応じて、読み出すべき単語の範囲を絞りこむよう
にされている特許請求の範囲第４項、第５項また
は第６項記載のつづり誤り訂正装置。