JPS63198154A

JPS63198154A - つづり誤り訂正装置

Info

Publication number: JPS63198154A
Application number: JP62023706A
Authority: JP
Inventors: 伸泰伊東; 高橋　弘晏
Original assignee: International Business Machines Corp
Current assignee: International Business Machines Corp
Priority date: 1987-02-05
Filing date: 1987-02-05
Publication date: 1988-08-16
Also published as: DE3776783D1; EP0277356A3; JPH058464B2; US4903206A; EP0277356A2; EP0277356B1

Abstract

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

Description

【発明の詳細な説明】Ａ、産業上の利用分野この発明はつづり誤りのある単語を自動的に訂正したり
、オペレータに正しい単語のつづりを助緬したりするの
に用いるつづり誤り訂正装置に関する。

Ｂ、従来技術］ンピュータへの文書入力やデータ入力の負担を軽減す
べく、既存のテキストエディタの改善に加え、０ＣＲ１
音声入方など様々な入力手法が提供されてきている。し
かしこれらのいずれにおいても入力誤りを完全に避ける
ことは不可能であり、入力後のつづり誤りの検査と訂正
とが不可欠である。このためつづり誤りのある単語を見
い出し、さらにその入力文字列に対して正しいと思われ
る単語の候補をオペレータに提示するプログラムが開発
されてきた。

実用上からみるとこのようなプログラムの効率を決定す
るのは入力文字列に対して候補となる単語、すなわち比
較的類似するつづりを有する単語を選び出す過程である
。候補単語はこののち入力文字列と詳細にマツチングさ
せられ、それが正解単語かどうか判別される。もっとも
簡単な方法は辞書内の全単語を候補とし、その１つ１つ
と入力文字列とをあらかじめ決められた距離式によりマ
ツチングし、入力文字列との類似度を計算するものであ
る。しかし実用的な辞書の多くは１万語ないし２万語以
上のサイズであることがらこの方法は計算コスト上実用
的ではない。そこで詳細なマツチングを行う前に候補単
語を絞る方法としてたとえばっぎのようなものが提案さ
れてきた。

（１）入力単語と先頭１文字が一致し、長さの差が一定
以上（通常１〜３文字）の単語のみを候補とする。

この手法は実用化されているプログラムに広く採用され
ており、−例としてＩＢＭ社のＷｏｒｄＰｒｏｏｆを挙
げることができる。

（２）各文字に固定の数値を割り当て、入力単語のつづ
りから一定の式に基づいてその入力単語の値を計算し、
その値をハツシングのキーとし、値の差が一定以内の単
語を取り出して候補とする。

この手法にライてはＷ、　Ｓ、　Ｒｏｓｅｎｂａｕｍお
よびＪ、　Ｊ、　Ｈｉｌｌｉａｒｄの論文“Ｍｕｌｔｉ
ｆｏｎｔ　ＯＣＲＰｏｓｔｐｒｏｃｓｓｓｉｎｇ　Ｓｙ
ｓｔｅｍ”ＩＢＭ　Ｊｏｕｎａｌ　ｏｆｒｅｓｅａｒｃ
ｈ　ａｎｄ　ｄｅｖｅｌｏｐｍｅｎｔ　Ｖｏｌ、　１９
．　Ｎｏ、　５．　ｐｐ。

３９８−４２１．１９７５年７月に記載がある。詳細に
ついてはとくにｐｐ４０３−４０４の説明を参照された
い。

（３）入力単語から得られる文字種集合と各単語の文字
種集合とを全要素間で比較し、差が一定以内の単語を候
補とする。なお、ここでは単語に含まれるすべての文字
種を要素とする集合を、文字種集合と定義することにす
る。

これについては特公昭５９−２９９１０号公報（米国特
許第４３５５３７１号明細書）に詳細な説明がある。

手法（１）は入力単語の先頭の文字が最も高い信頼性を
有するという仮定に基づくものである。

この仮定はキーボード入力においてはある程度妥当なも
のである。しかしＯＣＲなどにおいてはこの仮定は必ず
しも満たされず、先頭１文字を誤ったために正解が単語
候補からもれてしまうことが起こり得る。また候補の減
少率が低いため通常他の手法、たとえば単語誤りの統計
に基づいて可能性の低いものは除くという手法を併用す
る必要がある。

手法（２）は探索に要するコストは少ないが正解単語の
脱落という観点から見るとさらに検討を要する。各文字
にどのような数値を割当てるべきかという検討も行われ
ているが最悪の場合には１文字が入れ替わっただけの入
力文字列に対しても正解単語が脱落し得る。

手法（３）は一定の閾値に対してそれ以内の文字の入れ
替わりならば、正解単語の脱落は起こらないことが保証
される。しかしこの方法では入力文字列の文字種集合と
全単語のそれとを比較する必要がある。−回あたりの比
較に要する計算コストは比較的少ないとはいえ万単位の
単語がある場合には計算コスト上問題が残る。

Ｃ０発明が解決しようとしている問題点この発明は以上
の事情を考慮してなされたものであり、予め定められた
閾値以内の文字の入れ替わり、脱落、付加しか入力単語
に存在しないのであれば、その入力単語のつづりに基づ
いて決定された候補単語中に正解単語が含まれることを
保証することができ、しかも候補単語の決定の計算を極
めて少ないものに抑えることができるつづり誤り訂正装
置を提供することを目的としている。

Ｄ０問題点を解決するための手段この発明では以上の目的を達成するため単語の文字種集
合中の特定の文字種組み合わせに注目して候補単語を選
択するようにしている。

この特定の文字種組み合わせはつぎのように決定される
。

■入力単語に含まれる文字種を予め定められたノ、（準
にしたがって整列化する。

■整列化した文字種のうち上位のｎ個（ｎは整数）を選
ぶ。

０８個の文字種のうちの任意のｍ個（ｍはｍ　＜　ｎを
満たす整数）からなる文字種組み合わせを生成する。

辞書中の単語はこのように抽出された文字種組み合わせ
に基づいて分類されて辞書中に記憶されている６１個の
単語に通常複数の文字種組み合わせが存在するので、１
個の単語が複数のクラスに分類されるのが普通である。

入力単語に対する候補単語を選択するには、入力単語か
ら抽出された文字種組み合わせで特定される１または複
数（通常は複数）のクラスに含まれる単語を辞書から取
り出せばよい。

この発明では上述の文字種組み合わせは単語の属性と考
えることができる。そしてこの属性は単語の文字の置き
換え、脱落、付加が一定の範囲のものであるかぎり、全
面的には変更されることばない。すなわち少なくとも１
つの文字種組み合わせはそのようなつづり誤りが加わっ
たとしても残っているのである。したがって上述のよう
に特定されたクラスの１つの中には正解単語が存在する
こととなる。

この発明では文字の置き換え、脱落、付加が一定の範囲
のものであるかぎり、候補単語中に必らず正解単語を含
ませることができ、しかも入力単語の属性から一意的に
候補単語のクラスを判別でき、特別に煩雑な計算を要し
ない。

Ｅ、実施例以下、この発明を印刷英数字ＯＣＲによる文書入力シス
テムに適用した一実施例について説明しよう。なお、こ
の発明を他の入力システムにも適用できることはもちろ
んである。

第１図はこの実施例の構成を全体として示すものであり
、この図において、システムはパーソナルコンピュータ
１、ビット・マツプ・ディプレイ２、スキャナ３および
補助記憶装置４から構成されている。破線内のブロック
すなわち認識部５、後処理部６およびユーザーインター
フェース部７はソフトウェアとして実現されている。実
用的には認識部５をハードウェアで実現するようにして
もよい。後処理部６はこの発明に直接関連する部分であ
り、この後処理部６をソフトウェアで実現しても計算量
や処理速度上何ら支障がないことはのちに理解される。

第２図は第１図のシステムの手順を示すものである。第
１図および第２図において、オペレータが処理開始コマ
ンドを発行するとユーザ・インターフェース部７はまず
スキャナ３にスキャン要求を供給する。文′ＩＩ８はス
キャナ３により走査され、イメージとして認識部５へ供
給される（Ｓ１１）。

認識部５ではイメージを１文字単位で切り出したのち（
Ｓｎ２）、切り出した１文字分のイメージがどの文字で
あるかを識別する（Ｓｉ２）。識別の結果は唯一に決ま
るとは限らず、複数の候補が出力されることもある。後
述する第３図では第１位の文字候補の列を枠で囲んで示
しである。１単語分の認識が終了するとユーザーインタ
ーフェース部７は後処理部６に対して認識結果のつづり
誤りの検査および訂正を要求する。後処理部６は認識部
５から供給された認識結果について補助記憶装置４中の
単語辞書を参照してつづりの確認を実行し、辞書中に該
当する嘔語が存在しない場合には、近似的に一致したつ
づりを有する単語を検索する（Ｓ１４）。この部分はこ
の発明と直接関連する部分であり、のちに詳述する。ス
テップ１４の結果はユーザーインターフェース部７を介
してディスプレイ２に表示され、オペレータが最終的に
認識、修正を行う（Ｓ１５）。このようにしてコード化
された正しい文書が得られることになる。

つぎにこの発明に直接関連する後処理部６について説明
する。なお、この後処理部６の機能としてはづぎの２つ
がある。

（１）入力文字列が単Ｉｎとして正しいつづりであるか
（単語辞書に存在するかどうか）を検査する。

（２）入力文字列（あるいは認識結果そのもの）に対し
て類似したつづりをもつ単語を探索する。

機能（１）は機能（２）のサブセットとして理解できる
のでここでは機能（２）についてのみ述べる。

第３図は後処理部６の詳細を示しており、この図におい
て、後処理部６はクラス生成部９、検索機構１０、マツ
チング部１１およびパーソナルコンピュータ１の主記憶
１２からなっている。この碍成において、まず認識結果
の第１位候補からなる文字列が入力文字列としてクラス
生成部９に供給される。クラス生成部はのちに詳述する
クラスを生成する。検索機構１０は生成されたクラスを
キーにして補助記憶装置４中の単語辞書を探索し、候補
単語を選択して主記憶１２に転送する。マツチング部１
１に得られた候補単語と入力文字列（あるいは認識結果
）とのマツチングを実行し、マツチング距離が閾値以内
ならば確からしい単語として出力する。

以下、後処理部６の要部について順に詳述する。

欠乏ジ（生−成＃□」第４図はクラス生成部９の処理手順を示している。クラ
スとはｍ文字種（ｍは整数、たとえば３）からなる文字
種組み合わせに対応する属性名として定義される。たと
えば（ａ、ｂ、ｃ）　、（ｄ。

ｅ、ｆ）はそれぞれ１つのクラスである。そして所定の
単語が特定のクラスに属するとは、その単語から以下に
述べる手順をへて得られる文字種組み合わせのなかに、
そのクラスを特定する文字種組み合わせが存在すること
を意味する。ではこのクラス生成部９の処理を第４図を
参照して説明する。

ステップ５−２１卿語のつづりからその文字種集合を作成する。

従来技術の説明で述べたとおり、文字種集合とは’ｌ’
−ｇ７ｋに含まれるすべての文字種を要素とする集合で
ある。

［例コｅｘａｍｐｌｅ　　→　（ａ、ｅ、　　ｌ、　ｍ＋　ｐ
＋　ｘ）ａｐｐｌｅ　　　　→　（ａ、ｅ、　　１、ｐ
）Ｏｆ　　　　　→　（ｆ、０）ステップＳ２２文字種集合を一定の基へ１口こより整列化する。この例
では単語の頻度を考慮しないときの各文字の出現頻度の
低さを用いている。この頻度順位を表１に示す。

［例］（ａ、　ｅ、　ｌ、ｍ、　ｐ、　ｘ）→［ｘ＋ｐ＋ｍＳ
１．　ａ＋ｅ］（ａ、　ｅ、１、Ｐ）　　　→［ｐ、　
１．　ａ、　ｅ］（ｆ、　ｏ）　　　　　　　→［ｆ、
０］表１、文字種の頻度組進−ＩＵゆ鎚紗」ＬＬ−ｊｑ
ｘｚｗｋｖｆｂｙ　　ｇ　ｈｐｍ　　ｄ　　ｕ　　ｃ　　ｓ　　ｌ　　ｔ　　ｏ　　ｎ
　　ｒ　　ｉ　　ａ　　ｅステップＳ２３整列化した要素の上位４文字種を取り出した部分文字種
集合を生成する。ただしもともと文字種集合の要素が４
個よりも少ない場合にはブランク文字を加えて４文字種
とする。ブランク文字は必要に応じて重複して加えてよ
い。なお、以下でブランク文字は１１　　Ｉ＋で表わす
。

［例］［ｘ、　ｐ、　１、ｍ、　ａ、　ｅｌ→（ｘ、　ｐ、　
ｍ＋１）［ｐ、　１．　　ａ、　　ｅコ　　　　　　　
→　（Ｐ、　１、　ａ、　　ｅ）［ｆ、　０コ　　　　
　　　　　　　　　→　（ｆ、　　ｏ、　−５−）ステ
ーツブ−８２４− 上述のように３文字種の組み合わせを１つのクラスと定
義する。そして単語の部分文字集合の要素を用いてつく
ることのできる３文字種組み合わせをすべて生成する。

これは通常４個生成される。

その単語は得られた３文字種組に対応するクラスに、重
複を許して、属しているものと定義する。

英語の場合、文字種はブランク文字を含めて２７個ある
ので、合計２９５１個（＝２□Ｃ，＋２６）のクラスが
存在し、各単語はこの中のいずれかに（通常４クラスに
重複して）属していることになる。

［例コａｐｐｌｅの部分文字種集合は（Ｐ、１、ａ、　ｅ）で
あるから、ａｐｐｌｅは（ａ、１、Ｐ）、（ｅ、１、Ｐ
）、（ａ、　ｅ。

ｐ）および、（ａ、　ｅ、　ｌ）の４つのクラスに属す
る。

単語辞書はこのようにして生成されたクラスに基づいて
検索できるようになっている。以下この検索機構１０お
よび辞書構成例について述べる。

軟索−機−構−咀−９−と晩−書遭成−例第５図は辞書
構成例を示す。第５図において、辞書は第１インデック
ス部１３、第２インデックス部１４および辞書本体１５
がらなっている。第１インデックス部１３はクラスすな
わち３文字種組たとえば（ａ、ｂ、ｃ）と−意に対応す
るエントリを有し、各エントリごとにそのクラスの第２
インデツクスへの先頭ポインタと、属している単語の数
Ｎとを記憶している。第２インデックス部１４は各クラ
スと一対一に対応する複数の部分領域１４ａを有してい
る。そして第２インデックス部１４の部分領域１４ａの
各エントリは単ｄｔｔと一意に対応し、辞書本体１５へ
のポインタと単ｄｔ）の長さを有している。もちろん単
語候補をより絞るための付加情報を有してもよい。各エ
ントリは辞書本体１５へのポインタおよび長さをキーと
して整列化されており、第１インデツクス１３から得た
先頭ポインタからＮ個順次読み出しを行えば、その部分
領域のエントリを全部アクセスできる。

辞書本体１５は単語のつづりやその他の情報を含んでお
り、第２インデックス部１４の各エントリ中のポインタ
により直接にアクセスされる。

なおこの辞書構成においては、各クラスに属する単語を
、そのクラスを特定する３文字種を上位３文字種とする
単語と、それ以外の単語とに別けておくことが好ましい
。このようにすると単につづりが正しいかどうかを検査
する場合に、余分な検索を実行しなくてすむ。すなわち
、つづりが正しいかどうかの検査を行うには、上位３文
字種が入力単語に等しい単語のみを候補としてマツチン
グを実行すればよい。等しい単語が見い出せればつづり
が正しいと判断し、見い出せなければつづりが誤ってい
ると判断すればよいのである。そこで第５図の辞書を用
いてつづりの誤りを検査する場合には、入力文字列の上
位３文字種組でクラスを特定し、このクラスの中でその
上位３文字種組を有する単語のみを取り出してマツチン
グを実行すればよい。以上のようにクラスを２分すれば
不要な検索を回避できる。なお、上位３文字種ではなく
、他の特定の列位置の３文字種を基ベロにしてもよい。

つぎにこのように構成された辞書を検索機構１０がどの
ようにアクセスするかについて例を挙げて説明しておく
。部分文字種集合を（ｘ、ｐ、ｍ、１）とする場合につ
いて考える。まずクラス生成部９から検索機構１０がク
ラス（１、ｍ、ｐ）を受は取ると、この検索機構１０は
第１インデックス部１３からクラス（１，ｍ、ｐ）に属
している単語の数Ｎｉと、それらの単語の情報が格納さ
れている第２インデックス部１４中の部分領域１４ａ（
Ｃｉで示す）への先頭ポインタｐ□とを得る。

ポインタＰｔを用いて部分領域Ｃ１にアクセスし順に走
査しながら入力文字列との長さが一定の閾値以内のもの
を検索し、辞書本体１５中の該当する乍語へのポインタ
Ｐ１ｋ（ｋ：１、・・・・、Ｎｉ）を得る。そしてこれ
ら辞書本体１５へのポインタをたどり、たとえばｓｉｍ
ｐｌｅ、　ｅｘａｍｐｌｅといった単ｄｔ１のつづりを
読み出し、主記憶１２に転送する。

同様にして他の３文字種組（ｍ、　ｐ、　ｘ）、（１、
Ｐ、Ｘ）および（１、ｍ、ｘ）についても該当する単語
を選択して転送する。この場合、クラスの定義から明ら
かなように重複した単語がいつくか存在する。

たとえば単＃）　ｅｘａｍｐｌｅはクラス（１，ｍ、　
ｐ）、（ｍ、ｐ、　ｘ）、（１、ｐ、　ｘ）および（１
、ｍ、！）のいずれにも屈し、そのままでは４度重複し
て転送される。

検索機構１０はこの重複した検索をチェックして防止す
る機能も有する。

以上のようにしてクラス生成部９および検索機構１０に
より入力文字列に」みづいて候補単語の選択を実行でき
る。さまざまな入力文字列に対し、このようにして得ら
れる候補単語を表２に示す。

この表では、入力文字列との長さの差が１以内のものの
み選択した。辞書のサイズは約１１０００語とした。

マツチング紙上上マツチング部１１では選択された候補単語と入力文字列
（あるいは認識結果）とを照合しどの程度類似している
かを８１１定する。この照合には種々の手法を採用する
ことができ、その詳細については当業者に自明であるこ
とから説明を行わないこととする。

実施例の説明を終えるに際し、この実施例の特徴をまと
めておくことにする。

（１）単語中の特定の位置にある文字が正解であるかど
うかに依存しない。とくに先頭の文字が正解であるかど
うかに無関係であることは既存の方法の中でも広く用い
られている先行技術（１）に比較して優位な点である。

（２）処理が簡単である。部分文字集合をもとめる操作
は入力文字列中の文字種の確認と集合演算のみであり要
素の数も高々数個程度であるからハツシュ方式と比較し
ても同程度の探索コストですむ。辞書のアクセスもまた
候補単語選択の過程で゛は辞書本体にアクセスする必要
はなく、処理のほとんどはインデックス２への順次アク
セスですみ、辞書のアクセス（補助記憶装置４のアクセ
ス）は実用上問題にならない。

（３）用いる部分文字集合の要素数（ｎ）と文字組合せ
の要素数（ｍ）とにより決定される閾値（ｎ−ｍ）以内
の文字の入れ替り、脱落、追加ならば正解単語が候補か
らもれてしまうことはない。

またそれ以上の入れ替りなどに対しても適切な整列化の
基準（本例では候補単語の減少率を高くするため頻度の
低さを基準としているが、誤りの起こり難さなども基準
に取り入れることができる）のもとでは部分文字集合が
大きく異なってしまうような単語の変形は極めてまれで
あり、したがって正解単語が脱落する確率は極めて低い
。

（４）各クラス内の単語を上位ｍ文字種に着目して２分
することによりつづり検査時の検索を少なくすることが
できる。

（５）文字種組み合わせによる分類に加えて単語の長さ
も考慮して候補単語を選択しているので、効率よく候補
の絞り込みを行える。

なおこの発明の範囲は上述実施例のみに限定されるもの
ではなく、その趣旨を逸脱しない範囲で変更を行うこと
ができる。たとえば文字種は英文字に限定されない。ま
た入力は音声認識やキーボードを用いてもよい。また部
分文字種集合の要素数ｎや文字種組み合わせの要素数ｍ
を種々変更できる。また整列化の基準として他の統計情
報等を用いてもよい。さらに辞書の構成としても種々の
ものを採用してよい。

Ｆ９発明の詳細な説明したように、この発明によれば単語の文字種集合
の要素の特定の組み合わせをその単語の属性とし、この
属性に基づいて辞書中の単語を分類している。他方入力
単語から同様の属性を抽出し、属性を同一とするクラス
の単語を辞書から取り出して入力単語の候補とするよう
にしている。

したがって少ない計算量で候補単語を得ることができる
。しかも上述の組み合わせの生成規則から所定の範囲の
文字の入れ替え、脱落、挿入によるつづり誤りの訂正を
保証することができる。

【図面の簡単な説明】

第１図はこの発明の一実施例全体としてを示すブロック
図、第２図は第１図の実施例の手順を示すフローチャー
ト、第３図は第１図の後処理部６の詳細を示すブロック
図、第４図は第３図のクラス生成部９を説明するための
フローチャート、第５図は検索機構１０がアクセスする
単語辞書の構成例を示す図である。１・・・・パーソナルコンピュータ、２・パ・ディスプ
レイ、３・・・・スキャナ、４・・・・補助記憶装置、
５・・・・認識部、６・・・・後処理部、９・・・・ク
ラス生成部、１０・・・・検索機構、１１・・・・マツ
チング部。出願人　　インターナショナル・ビジネス・マシーンズ
・コーポレーション復代理人　　弁理士　　澤　　１）　俊　　夫実施例の
システム算Ｘに・実施例の処理の流九第２図欲７趙理邦のａ代第、３居辞書のｔ戊第５呂

Claims

【特許請求の範囲】

（１）正しくつづられている多数の単語を記憶する記憶
手段であつて、上記単語の各々を、文字種に関して予め
定められている基準で整列化された、当該単語に含まれ
る文字種の、上位ｎ個（ｎは定数）のうちの任意のｍ個
（ｍはｍ＜ｎを満たす定数）からなる文字種組み合わせ
により、読み出せるようにしたものと、入力単語に含まれる文字種を上記整列化の基準で整列化
する手段と、整列化した文字種の上位ｎ個のうちのｍ個からなるすべ
ての文字種組み合わせを求める手段と、求められた文字
種組み合わせの各々に基づいて上記記憶手段から正しく
つづられている単語を読み出す手段と、上記入力単語を上記読み出された単語にマッチングさせ
る手段とを有することを特徴とするつづり誤り訂正装置
。
（２）上記ｎ個の文字種には１以上のブランク文字を含
ませることができるようにした特許請求の範囲第（１）
項記載のつづり誤り訂正装置。
（３）上記整列化の基準は文字種の出現頻度の低さによ
ることとした特許請求の範囲第（１）項または第（２）
項記載のつづり誤りの訂正装置。
（４）上記記憶手段は正しくつづられている単語を記憶
する記憶手段本体部と、上記文字種組み合わせに基づい
て上記記憶手段本体部の記憶位置を指定するインデック
ス部とを有する特許請求の範囲第（１）項、第（２）項
または第（３）項記載のつづり誤り訂正装置。
（５）上記インデックス部は、つづり誤りの検査時に、
上記入力単語の整列化された文字種のうちの予め定めら
れたｍ個の列位置の文字種に応じて、読み出すべき単語
の範囲を絞り込むようにされている特許請求の範囲第（
４）項記載のつづり誤り訂正装置。
（６）上記予め定められたｍ個の列位置を上位ｍ位置と
した特許請求の範囲第（５）項記載のつづり誤り訂正装
置。
（７）上記インデックス部は上記入力単語の長さに応じ
て、読み出すべき単語の範囲を絞り込むようにされてい
る特許請求の範囲第（４）項、第（５）項または第（６
）項記載のつづり誤り訂正装置。