JPH04335488A

JPH04335488A - 単語照合方法

Info

Publication number: JPH04335488A
Application number: JP3133269A
Authority: JP
Inventors: Masanobu Nakamura; 匡伸中村; Akiko Konno; 紺野　章子; Yasuo Hongo; 本郷　保夫
Original assignee: Fuji Electric Co Ltd; Fuji Facom Corp
Current assignee: Fuji Electric Co Ltd; Fuji Facom Corp
Priority date: 1991-05-10
Filing date: 1991-05-10
Publication date: 1992-11-24

Abstract

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

Description

【発明の詳細な説明】

【０００１】

【産業上の利用分野】この発明は、光学的文字認識装置
（ＯＣＲ）による認識結果に対し、誤読の修正をする場
合に用いて好適な単語照合方法に関する。

【０００２】

【従来の技術】従来、この種の照合方法としては、通常
の文字並びをした単語辞書を用いた照合を文頭から逐次
的に行なうものが一般的である。

【０００３】

【発明が解決しようとする課題】しかしながら、このよ
うな方法では、候補順位の低いところに正解である単語
の先頭文字がある場合、その単語を照合するにはその先
頭文字の上位にある文字まで辞書照合を行なう必要があ
る。また、正解文字が１位であるのに、下位順位にある
文字を前方からの照合によって検定し、誤った文字に修
正してしまうおそれがある。さらには、語頭の文字が候
補もれを起こしている場合は、従来は全く辞書引きが行
なえない、という問題もある。従って、この発明の課題
は不要な単語抽出と誤った修正（誤修正）を防止すると
ともに、候補もれにも対処し得るようにすることにある
。

【０００４】

【課題を解決するための手段】このような課題を解決す
るため、この発明では、文字認識装置が認識した認識結
果に対応する候補文字群を、その確からしさの程度に応
じて複数個の集合に分け、より確からしい候補文字集合
を起点として未照合文字列の照合を行ない、照合されず
に残った文字列に対して、次に確からしい候補文字列を
起点とする照合を順次繰り返すことにより、単語照合を
行なうことを特徴としている。また、前記照合に当たっ
ては、各文字の有向グラフの点、２つの文字間の連接を
有向グラフの枝、語を有向グラフの道として表現し、任
意の文字位置から文末方向へ所定の辞書を参照してその
文字から連接して行く枝を順に辿る照合と、文頭方向へ
所定の辞書を参照してその文字から連接して行く枝を順
に辿る照合とを行なうことを特徴としている。

【０００５】

【作用】未知入力文字列に対して確からしい文字から波
及的に単語を照合することにより、不要な単語抽出と誤
修正を防止するとともに、候補もれがあっても照合でき
るようにする。

【０００６】

【実施例】従来の言語モデルでは、言語を記号の１次元
的な配列として捉えていたが（言語を単語レベルで捉え
た従来のモデルとして、例えばアルファベット集合Ｓ＝
｛ａ１　ａ２　…ａｎ　｝の閉包（Ｃｌｏｓｕｒｅ）が
ある。これはアルファベットがｋ個並んだ集合Ｓｋ　＝｛ａ１
　ａ２　…ａｎ　｝の和集合Ｓ＊　＝Ｓ０　＋Ｓ１　…
＋Ｓｎ　のことであり、これを処理対象としている）、
この発明では言語シンボル、つまり文字を図２の如く有
向グラフの点（Ｖｅｒｔｅｘ）１、文字同士の連接を有
向グラフの枝（Ａｒｃ）２、単語を有向グラフの道（Ｐ
ａｔｈ）としてそれぞれ表現することにより、従来では
できなかった任意の文字位置からの単語照合を可能とす
るものである。なお、このような言語モデルは一般に有
向グラフ言語モデル（ＤＬＭ：Ｄｉｇｒａｐｈ　　Ｌａ
ｎｇｕａｇｅ　　Ｍｏｄｅｌ）と呼ばれる。このＤＬＭ
の定義は次のとおりである。

【０００７】Ｄ＝Ｄ（Ｓ，Ａ）Ｄは有向グラフＳは言語シンボルｓｉ　を要素とする点集合Ｓ＝｛ｓｉ
　｜１≦ｉ≦ｕ｝Ａは２つの文字ｓｉ　，ｓｊ　が隣接して語ｗを構成し
、ｓｉ　が語ｗのｋ番目の文字であることを示す枝集合
Ａ＝｛ａｉ，ｊ　ｗ，ｋ　｜１≦ｉ≦ｕ，１≦ｊ≦ｕ，
１≦ｗ≦ｖ，１≦ｋ≦（ｌｍａｘ　−１）｝Ｐは語をなす点と枝の交互列で表わされた道の集合Ｐ＝
｛ｐｗ　｜ｐｗ　＝（ｓｈ　，ａｈ，ｉ　ｗ，ｌ　，ｓ
ｉ　，…，ａｓ，ｔ　ｗ，ｌ−１　，ｓｔ　）、ｓｈ　
，ｓｉ　，…ｓｔ　∈Ｓ、ａｈ，ｉ　ｗ，ｌ　，…ａｓ
，ｔ　ｗ，ｌ　∈Ａ、１≦ｗ≦ｖ，１≦ｌ≦ｌｍａｘ　
｝

【０００８】すなわち、語長ｌの語ｗを、有向グラフの
道ｐｗ　＝（ｓｈ　，ａｈ，ｉ　ｗ，ｌ　，ｓｉ　，…
，ａｓ，ｔ　ｗ，ｌ−１　，ｓｔ　）で表わす。ｓｈ　
とｓｔ　は道の始点と終点であり、それぞれ語ｐｗ　に
関する語頭シンボル，語尾シンボルと呼び、両者を合わ
せて語端シンボルともいう。ｌ＝１の場合はｐｗ　＝（
ｓｈ　）となり、道が「退化」している状態で１文字単
語を表わす。言語シンボル（文字）の総数は｜Ｓ｜＝ｕ
であり、語彙総数は｜Ｐ｜＝ｖである。つまり、ＤＬＭ
は各シンボルがどのように関連し合っているかを、有向
グラフを用いて体系的に記述したものであり、こうする
ことで任意の文字位置からの辞書引きを可能とするもの
である。いま、或る単語をｓ１　ｓ２　…ｓｉ　…ｓｎ
　（ｓｉ　は言語シンボル）とすると、従来は単語の先
頭の文字から順番にｓ１　ｓ２　…と辞書引きを行なっ
ていたのに対し、ＤＬＭを利用すれば単語の途中の文字
ｓｉ　を起点としてｓｉ　から出て行く枝（後接シンボ
ルへの枝）を辿ることによって語尾方向に、またｓｉ　
に入って来る枝（前接シンボルからの枝）を辿ることに
よって語頭方向に、それぞれ単語の辞書引きを行なうこ
とができる。

【０００９】有向グラフの一般的なデータ構造としては
、隣接テーブルと接続テーブルとがある。これらは点同
士の隣接関係あるいは点と枝の接続関係をマトリックス
で示したものであり、この行列値を変えることで単語を
表現することができるが、語彙数が数十万程度になると
アドレス空間だけで数十ＭＢ〜１ＧＢとなり、メモリ容
量の点から実用的とは言い難い。また、有向グラフの一
般的なリスト表現として頂点と枝を表わす２つの配列を
用い、或る頂点ｓｉ　から出る枝、またはｓｉ　へ入る
枝を順次ポインタで連結したものがあるが、これは単語
Ｐａｔｈの表現と検索には適していない。そこで、この
発明では単語をＤＬＭの「道」として捉え、この「道」
の検索，照合に適したデータ構造として「前後接リスト
」を利用することとする。

【００１０】図３に前後接リストと前後接枝ポインタの
例を示す。同図（イ）が「日本語」の場合の前後接リス
トであり、同図（ロ）が前後接枝ポインタである。これ
は、語のＰａｔｈが次々とシンボルへ入り、出て行く様
子を示したものであり、前接枝または後接枝を順次辿る
ことにより語頭方向と語尾方向に単語の検索を行なうこ
とができる。すなわち、前後接リスト１０は辞書項目を
１つのシンボル群毎にまとめ、その先頭アドレスである
ＢａｓｅＡｄｒへは基本アドレステーブル２０により、
そのシンボルをキーとしてアクセスする。辞書項目は１
つの単語の中でそのシンボルが、どのシンボルから連接
してきたかを示す前接枝ポインタ１２、そしてどのシン
ボルへ連接して行くかを示す後接枝ポインタ１１、その
シンボルを含む語のＰａｔｈＮｏ．１３、およびそのシ
ンボルが単語内で何番目にあるかを示す文字順位１４か
ら成っている。例えば、後接枝ポインタ１１は図３（ロ
）の如く後接シンボルそれ自身と、単語内の後接シンボ
ルが後接して行くシンボル群の先頭アドレスから、どの
位置に記載されているかを示すＯｆｆｓｅｔアドレス（
ＯｆｆｓｅｔＡｄｒ）から成っている。これは、前接枝
ポインタ１２についても同様である。なお、語尾シンボ
ルの後接と語頭シンボルの前接には、それ以上何もない
のでφ（ＮＵＬＬ）を記載しておく。

【００１１】いま、１つの或るシンボルｓｉ　にｓｊ　
が後接している場合、ｓｉ　のその単語における辞書項
目から、次のｓｊの辞書項目へは以下のようにしてアク
セスする。（ａ）シンボルｓｊ　に関する辞書項目が記載されてい
る先頭アドレス（ＢａｓｅＡｄｒ）を、基本アドレステ
ーブル２０で参照する。（ｂ）得られたベースアドレス（ＢａｓｅＡｄｒ）とそ
の語が連接して行く辞書項目が、ｓｊ　群の先頭からど
の位置にあるかを示すオフセットアドレス（Ｏｆｆｓｅ
ｔＡｄｒ）から、後接シンボルが記載してある事項のア
ドレスへのポインタ（Ｐｏｉｎｔｅｒ）を次式により求
める。Ｐｏｉｎｔｅｒ＝ＢａｓｅＡｄｒ＋ＯｆｆｓｅｔＡｄｒ
このポインタにより、着目シンボルに後接するシンボル
の辞書項目へアクセスすることができる。これを繰り返
すことにより、語尾方向への照合を行なうことができる
。なお、語頭方向へは、前接シンボルについて上記と同
様の操作をすることにより、辞書引きをすることができ
る。辞書の後接シンボルまたは前接シンボルがφの場合
は、そのシンボルが語尾または語頭シンボルであること
を示す。

【００１２】図１はこの発明の実施例を示すフローチャ
ートである。ＤＬＭは並列処理に適しているが、不要な
単語照合の抽出を抑制し、照合時間の短縮と誤修正の防
止を図る上からも、確からしい文字から単語照合を行な
う方が良いので、ここでもこの手法を採用することとす
る。なお、「確からしさ」の求め方には種々あるが、こ
こでは誤読確率から求めており、その確率は例えばサン
プルシートの誤読リストから作成している。今、入力文
を｛ｓｉ　｜１≦ｉ≦ｎ｝、候補文字をＣ＝｛ｃｉ　ｊ
　｜ｃｉ　ｊ　をｓｉ　の第ｊ位の候補文字とする。１
≦ｉ≦ｎ，１≦ｊ≦ｍ｝とする。入力文と候補文字群と
の関係を図４に示す。符号３１が入力文、３２が候補文
字群である。始めに、ステップＳ１において、第１位の候補文字Ｃ１
　＝｛ｃｉ　１　｝を候補文字間の類似度や統計的デー
タ等から、その候補文字が正解である確率の高い順にΓ
１　，Γ２　…ΓＺ　に分割する（Γ１　∪Γ２　…∪
ΓＺ　＝Ｃ１　、Γ１　∩Γ２　…∩ΓＺ　＝φ（空集
合））。

【００１３】次に、ステップＳ２において、Γ１　に属
する候補文字を起点として、文末方向へａ照合、文頭方
向へｂ照合を行なう（ａはａｆｔｅｒ，ｂはｂｅｆｏｒ
ｅの意味）。（１）ａ照合ステップＳ３では、ｃｉ　１　の辞書後接｛（ｃｉ　１
　）ａ　｝と後方入力文字ｓｉ＋１　の候補文字｛ｃｉ
＋１　ｊ　｜１≦ｊ≦ｍ｝とのマッチングを行ない、照
合するもの（ｊ＝ｊｂ　で一致するとする）があれば、
ｃｉ＋１　ｊｂのポインタによる辞書引きを行なって次
の照合へと進む。（２）ｂ照合ステップＳ４では、ｃｉ　１　の辞書前接｛（ｃｉ　１
　）ｂ　｝と後方入力文字ｓｉ−１　の候補文字｛ｃｉ
−１　ｊ　｜１≦ｊ≦ｍ｝とのマッチングを行ない、照
合するもの（ｊ＝ｊａ　で一致するとする）があれば、
ｃｉ−１　ｊａのポインタによる辞書引きを行なって次
の照合へと進む。

【００１４】１回のａ照合およびｂ照合の照合結果は、
次の３つの状態となる。イ）照合継続状態対象シンボルが検索方向へ連接する場合（ステップＳ５
，Ｓ６参照）ロ）照合完了状態対象シンボルが語端シンボルの場合（ステップＳ７，Ｓ
８参照）ハ）照合停止状態対象シンボルが非語端シンボルで検索方向に連接しない
場合（ステップＳ９，Ｓ１０参照）そして、照合継続状態である限り照合を続け、同一Ｐａ
ｔｈのａ方向，ｂ方向の照合結果がともに照合完了状態
のとき、その単語が照合されたことになる（ステップＳ
１１参照）。或るＰａｔｈのａ方向，ｂ方向のいずれか
で照合停止状態のときは、単語照合は失敗したことを意
味する。

【００１５】Γ１　照合が終了すると、入力文字列の中
で最も確からしい文字集合に属する文字を、単語内に少
なくとも１つ含んだ単語の照合が行なわれたことになる
。或るコラムでΓ照合が成功した場合の処理は次のように
行なう。今、ｃｉ　１　∈Γｋ’とし、Γｋ　照合がｃ
ｉ　ｊ　（１≦ｊ≦ｍ）で成功したとする。（１）ｋ＜ｋ’ならば、新たにｃｉ　１　を起点とした
照合は行なわない。（２）ｋ＝ｋ’ならば、（２−１）ｃｉ　１　が照合された場合ｃｉ　１　を起
点とした照合は行なわない。（２−２）ｃｉ　ｊ　（２≦ｊ≦ｍ）が照合された場合
ｃｉ　ｊ　を起点とした照合を行なう。また、Γ１　からΓＺ　の全Γ照合が終了しても未照合
の入力文字列がある場合、さらに２位以下の文字を起点
とした照合を行なう。

【００１６】実験結果につき、説明する。（１）正解入力文字が「年金」でＯＣＲ読取結果が次の
ような場合「候補文字」１：任（Γ２　）金（Γ１　）２：年　　
　　　　　　命従来の手法では語頭より照合を行ない、「任命」と検定
していた。つまり、「任」を修正せず、逆に正しい「金
」まで「命」に誤修正していた。これに対し、ＤＬＭを
利用するこの発明によれば、より確からしい文字集合で
あるΓ１　に属する「金」から照合を開始し、ｂ照合に
より文頭方向への照合を行なうことで、正しく「年金」
と照合することができる。

【００１７】（２）正解入力文字が「観点」でＯＣＲ読
取結果が「歓点」となっている場合「候補文字」１：歓（Γ２　）点（Γ１　）２：観（Γ
３　）黒（Γ３　）従来の手法では「歓」と「点」をそれぞれ１文字単語と
して照合していたが、この発明によれば「点」から照合
を行なうことにより、正しく「観点」と照合できる。

【００１８】（３）正解が「政治資金規正法改正案」で
ＯＣＲ読取結果が「政治衡金晩正法改正案」の場合従来
は「晩」も「正」も１文字単語として扱っていたが、こ
の発明によれば「資」が候補もれしているため、「衡金
」は「資金」と修正はできないが、「正」がΓ１　集合
に属するため、「晩正」は「規正」と修正できる。

【００１９】（４）正解が「首脳」で「首」が候補もれ
を起こしている場合、従来の辞書では全く照合できなか
ったが、この発明によれば「首脳」は勿論「頭脳」など
十数語の単語を照合することができる。

【００２０】

【発明の効果】この発明によれば、未知入力文字列に対
し確からしい文字から波及的に単語を照合するようにし
たので、次のような利点が得られる。（１）不要な単語抽出が抑制され、文節列の効果的な検
定と誤修正の防止を図ることができる。（２）単語の語頭の文字が候補もれしていると、従来で
は全く辞書引きができなかったが、この発明によれば候
補単語の検索が可能である。（３）候補もれによる照合失敗の悪影響が周囲に拡散す
るのを防ぐことができる。

【図面の簡単な説明】

【図１】この発明の実施例を示すフローチャートである
。

【図２】有向グラフの例を説明するための説明図である
。

【図３】前後接リストと前後接ポインタとを説明するた
めの説明図である。

【図４】入力文と候補文字との関係を説明するための説
明図である。

【符号の説明】

１　　点（Ｖｅｒｔｅｘ）２　　枝（Ａｒｃ）１０　　前後接リスト１１　　後接枝ポインタ１２　　前接枝ポインタ１３　　語ＰａｔｈＮｏ．１４　　文字順位２０　　基本アドレステーブル３１　　入力文３２　　候補文字

Claims

【特許請求の範囲】

【請求項１】　　文字認識装置が認識した認識結果に対
応する候補文字群を、その確からしさの程度に応じて複
数個の集合に分け、より確からしい候補文字集合を起点
として未照合文字列の照合を行ない、照合されずに残っ
た文字列に対して、次に確からしい候補文字列を起点と
する照合を順次繰り返すことにより、単語照合を行なう
ことを特徴とする単語照合方法。
【請求項２】　　前記照合に当たっては、各文字の有向
グラフの点、２つの文字間の連接を有向グラフの枝、語
を有向グラフの道として表現し、任意の文字位置から文
末方向へ所定の辞書を参照してその文字から連接して行
く枝を順に辿る照合と、文頭方向へ所定の辞書を参照し
てその文字から連接して行く枝を順に辿る照合とを行な
うことを特徴とする請求項１に記載の単語照合方法。