JPH01211191A - 辞書ソーティング処理装置 - Google Patents

Abstract

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

Description

【発明の詳細な説明】 〔概　　要〕 辞書メモリからの特徴量データとイメージメモリからの
認識対象文字の特徴量データとから距離演算を行い、そ
の演算結果に応じてソーティング回路がソーティングメ
モリのソーティングを行う辞書ソーティング処理装置に
関し、 辞書検索にも辞書作成にも使用することができ、指定に
よって目的に応したソーティングが可能となることを目
的とし、 該ソーティング回路が、該ソーティングメモリから読み
出したＸ段目のデータをラッチする第１のラッチ回路と
、該Ｘ段目のデータの前段の距離データをラッチする第
２のラッチ回路と、該距離演算結果とＥｌ　Ｘ段目のデ
ータとを比較して両者の大小関係を該ソーティングメモ
リに対応した昇べき／降べき指定により選択し、同一の
ときは先着／後着優先指定により選択した出力を発生す
る比較優先回路と、該比較優先回路の前回の比較結果を
ラッチする第３のラッチ回路と、該比較優先回路及び第
３のラッチ回路の両比較結果に基づき、該距離演算結果
と該Ｘ段目のデータと該ｘ−１段目の距離データとのう
ちから１つを選択して該ソーティングメモリのＸ段目に
記憶するセレクタと、で構成する。

〔産業上の利用分野〕 本発明は、辞書ソーティング処理装置に関し、特に辞書
メモリからの特徴量データとイメージメモリからの認識
対象文字の特＠量データとから距離演算を行い、その演
算結果に応じてソーティング回路がソーティングメモリ
のソーティングを行う辞書ソーティング処理装置に関す
るものである。

一般に、辞書ソーティング処理装置は、第４図に示すよ
うに、文字認識の辞書検索部ｌと辞書メモリ（ＤＭ）２
とイメージメモリ（ＩＭ）４と候補文字レジスタとして
のソーティングメモリ（ＳＭ）９とで構成されている。

辞書検索部１は更に辞書メモリ２に格納されている４Ｉ
準特微量のデータ３と認識対象文字の特＠量データ５と
から距離演算を行う距離演算部６と、距離演算結果７に
基づいてソーティングメモリ９から読み出した候補文字
データと比較して並べ替えソーティング結果として再び
ソーティングメモリ９に書き込むソーティング回路８と
、を含んでいる。

この内、ソーティングメモリ９は第５図に示すように、
１〜Ｎ＋１位までの候補文字を備え、それぞれソーティ
ングメモリアドレスＸａ　　（初期値）＋０〜χ。十Ｎ
を有し、それぞれのアドレスにはり、−ＤＨの距離デー
タが格納されている。この場合、χはソーティング段ｌ
＆ｏ−Ｎを示し、ＤｗはＸ段目の距離データを示してい
る。また、この例では、最下位Ｎ＋１の候補文字の距離
データが最も大きい、昇べき順に並べである。従って、
この逆の最下位Ｎ＋１の候補文字の距離データが最も小
さい、降べき順に並べたものもある。

このような辞書ソーティング処理装置では、情報通信処
理の高度化、統合化に伴い、文字認識技術によるイメー
ジ情報からコード情報へのメディア変換に対する要求が
高いが、中でも重要な役割を担っているのが活字メディ
アであり、日本語文書を対象にした文字認識処理の高速
化・多様化が要望されている。

〔従来の技術〕

第６図は、従来の辞書ソーティング処理装置におけるソ
ーティング回路を示しており、距離演算部６からの距離
演算結果ＡＤは、セレクタ１７に送られるとともに、比
較器２ｏにも送られている。

また、ソーティングメモリ９から読み出したＸ段目の距
離データＤＸは、読み出しデータラッチ回路（フリップ
フロップ）１２に送られて、距離演算部６からソーティ
ングクロック発生部１９により発生されるクロック１４
゛にょリランチされてセレクタ１７に送られるとともに
比較器２ｏ及びラッチ回路１３に送られる。ラッチ回路
１３では、ラッチクロック１４によりラッチした前回の
データをセレクタ１７に送っている。

従って、このセレクタ１７には、距離データＡＤ、ｘ段
目の距離データＤｏ＋及びＸ段目より１段前の距離デー
タＤＸ−１が入力されることになり、これら３者のうち
の一つが選択されるが、その選択基準は比較器２０の出
力２１（演算結果ＡＤと距離データＤイの比較結果）と
、この出力２１をラッチクロック１４によってラッチす
るラッチ回路２２の出力２３（演算結果ＡＤと前段の距
離データＤＸ−１の比較結果）とを用いて行い、その結
果選択されたＸ段目のソーティングデータＤ、ｌＸがソ
ーティングメモリ９のＸ段目に格納される。尚、図示し
ていないが、ソーティングメモリ９の各段の距離データ
にはそれぞれ対応した文字を指定する符号が一緒に格納
されている。

第７図は第６図の回路をより詳しく示したもので、セレ
クタ１７は、３つのアンドゲート１７ａ〜１７ｃと、ノ
アゲート１７ｄと、インバータ１７ｅとで構成されてい
る。また、比較器２０は、１出力型のコンパレータ２０
ａと、このコンパレータ２０ａの出力とともにソーティ
ング指示信号２７を入力信号とするアンドゲート２０ｂ
及びナントゲート２０ｃとで構成されている。アンドゲ
ート２０ｂの出力２８及びナントゲート２０ｃの出力２
９（第６図の信号２１に相当）がそれぞれアンドゲート
１７ａ及び１７ｂに人力されている。

ナントゲート２０ｃの出力２９はアンドゲート２０ｂの
出力を反転させたものであり、ランチ回路２２に入力さ
れている。

従って、第７図に破線で示したインバータＩＮ■１．２
を用い、その代わりにアンドゲート２０ｂ、及び口出力
３１を割愛すれば、第６図のようにセレクタ１７への制
御入力は信号２１及び２３で済む。

次に上記の従来例の動作を第８図に示すタイムチャート
を参照して説明する。

今、演算した距離データＡＤを第８図に示すように、ｘ
ｗｌ、Ｄ、＜ＡＤ＜ＤＩ　と仮定すると、まず、ランチ
回路１２にラッチされた最初の距離データＤ０は比較器
２０のコンパレータ２０ａで比較され、その比較の結果
、コンパレータ２０ａの出力２１は１Ｌ°゛レベルとな
り、アンドゲート２０ｂの出力２８も“Ｌ゛レベルなっ
てナントゲート２０ｃの出力２９が“Ｈ”レベルとなる
ので、データＤ０はそのままアンドゲート１７ｂ５ノア
ゲート１７ｄ、インバータ１７ｅを経てソーティングデ
ータＤｌｌＸとして出力され、ソーティングメモリ９の
１段目に格納される。

この時、アンドゲート１７ａはラッチ回路２２のＱ出力
３０が“Ｌ″°°レベルっていることによりアンドゲー
ト１７ａはディスエーブルになっており演算データＡＤ
はソーティングされない。

また、アンドゲート１７ｃもラッチ回路２２のζ出力３
１が最初は“Ｌ”になっているので、ディスエーブル状
態にある。

読み出しデータラッチクロック１４により、次の距離デ
ータＤ、がソーティングメモリ９から読み出されると、
今度はＤＸ−、＝Ｄ、　、Ｄ、＝Ｄ。

となり、コンパレータ２０ａの出力は、“Ｈ”レベルに
なり、ソーティング指示信号２７とのアンドをとると信
号２日としてアンドゲート１７ａに入力される。このと
き、前回の比較により信号２９が“Ｈｏ“レベルになっ
ていたため、ラッチ回路２２のＱ出力３０もＨ”レベル
になっている。

従って、演算結果ＡＤはアンドゲート１７ａを経てソー
ティングデータＤＸＸとしてソーティングメモリ９の２
段目にソーティングされる。

この時、今回の信号２９が“Ｌ”レベルにあり、ラッチ
回路２２のζ出力３１が“Ｌ”レベルにあるため、デー
タＤ０、Ｄｌは出力されないことになる。

次の読み出しクロック１４では、Ｄ　ｘ−、＝　Ｄ　＋
、Ｄｘ＝Ｄｚ　となるため、Ｄ、がソーティングデータ
としてソーティングメモリ９の３段目にソーティングさ
れる。

この後は、距離データＤｚ−ｔ）ｓが順次距離データの
大きい方にシフトされて１つの未知文字に対するソーテ
ィングメモリ９のソーティングが終了することになる。

尚、第８図では、セレクタ１７からの出力１８がソーテ
ィングメモリ９に順次格納されて行く順にＤｏｌＳＤｌ
ｌ、Ｄ２′、、、→Ｄ６Ｉ１１Ｄ１−１Ｄ２會り・・・
のように示している。

このようにして、外部メモリである候補文字レジスタと
してのソーティングメモリに入っている候補文字の距離
データと、１文字の距離演算が終了する度にソーティン
グ回路に入力される距離データとを比較して候補に入ら
なければ、そのデータは捨てられ、最終的には、認識対
象文字に最も近い候補文字が残ることになる。

〔発明が解決しようとする課題〕

このような従来の辞書ソーティング処理装置では、ソー
ティングメモリは昇べき、即ち距離データの小さい方か
ら大きい方にソーティングされており、最下位候補の持
つ距離データよりも大きいデータは捨てられることにな
る。

また、最下位候補と同じ距離データの場合には、先着デ
ータの方が優先する。というのは、比較器２０は例えば
′Ｈ”出力の場合はＡＤ＜ＤＸ、’Ｌ”出力の場合はＡ
Ｄ≧Ｄ８となるからである。

このため、辞書の検討を行う時など、幅広いデータが集
められず、ソーティングメモリが外部メモリで、いくら
でも候補文字が増やせるという、辞書検討時に有利な条
件が充分に活かせないという問題点があった。

従って、本発明は、辞書メモリからの特徴量データとイ
メージメモリからの認識対象文字の特徴量データとから
距離演算を行い、その演算結果に応じてソーティング回
路がソーティングメモリのソーティングを行う辞書ソー
ティング処理装置において、辞書検索にも辞書作成・変
更にも使用することができ、指定によって目的に応じた
ソーティングが可能となることを目的とする。

〔課題を解決するための手段〕 上記の目的を達成するため、本発明に係る辞書ソーティ
ング処理装置では、第１図に概念的に示すように、ソー
ティング回路８が、ソーティングメモリ９から読み出し
たＸ段目のデータＤＸをラッチする第１のラッチ回路１
２と、該Ｘ段目のデータＤ、の前段の距離データＤｘ−
，をラッチする第２のラッチ回路１３と、該距離演算結
果ＡＤと該Ｘ段目のデータＤ、とを比較して両者の大小
関係を該ソーティングメモリ９に対応した昇べき／降べ
き指定により選択し、同一のときは先着／後着優先指定
により選択した出力を発生する比較優先回路３２と、該
比較優先回路３２の前回の比較結果をラッチする第３の
ラッチ回路２２と、該比較優先回路３２及び第３のラッ
チ回路２２の両比較結果に基づき、該距離演算結果ＡＤ
と該Ｘ段目のデータＤ、と該ｘ−１段目の距離データＤ
や−１とのうちから１つのデータを選択して該ソーティ
ングメモリ９のＸ段目に記憶するセレクタ１７と、を備
えている。

〔作　　　用〕

本発明では、まず、ソーティングメモリ９を目的に応じ
て昇べきか又は降べきとなるように距離データのソーテ
ィングをしておく、そして、比較優先回路３２では、演
算結果ＡＤとソーティングメモリ９のＸ段目のデータＤ
Ｘとを比較する。

この場合の比較結果としては、■ＡＤ＜ＤＸ、■ＡＤ＞
ＤＸ、■ＡＤ−Ｄ、の３つが存在し、昇べき指定のとき
は■が選択され、陣べき指定のときは■が選択され、そ
して、■の関係にあるときには、先着優先指定であれば
元から記憶されているＤｘが優先され、後着優先指定で
あれば演算結果ＡＤが優先的に選択されるように比較優
先回路３２から出力が発生される。

従って、比較優先回路３２からの出力が発生されたとき
には、従来と同様に、距離演算結果ＡＤとＸ段目のデー
タＤ、と該χ−１段目の距離データＤＸ−１とのうちか
らセレクタ１７が１つのデータＤＸｌ＋を選択し該ソー
ティングメモリ９のＸ段目に記憶する。

このようにして順次、ソーティングメモリの並べ替えを
昇べきか又は降べきかに応じて、更に先着Ｉｌｌか後着
順かに応じて行うことができる。

〔実　施　例〕

以下、上記の本発明の辞書ソーティング処理装置を実施
例に沿って説明する。

第２図は、本発明の辞書ソーティング処理装置に用いる
ソーティング回路の一実施例を示したもので、第７図の
構成とは比較優先回８３２の構成が異なっている。

この実施例での比較優先回路３２は、演算結果ＡＤとソ
ーティングメモリ９のＸ段目の距離データＤ、とを入力
し、■ＡＤ＜ＤＸ　、■ＡＤ＞Ｄ。

、■ＡＤ＝Ｄ、の時にそれぞれ５Ｈ゛レベルとなる３つ
の出力端子Ｔ１〜Ｔ３を有するコンパレータ３２ａと、
コンパレータ３２ａの出力端子ＴＩ、Ｔ２の出力信号を
昇べき／降べき指定信号（これは図示しないシーケンサ
によって生成される信号）に基づいて選択するセレクタ
３２ｂと、コンパレータ３２ａの出力端子Ｔ３と先着／
後着優先指定信号（この信号も図示しないシーケンサに
よって選択される）とのアンドゲート３２Ｃと、セレク
タ３２ｂの出力とアンドゲート３２ｃの出力とのオアゲ
ート３２ｄと、上述したゲート２０ｂ１２０ｃとで構成
されている。

尚、この実施例においても、第７図と同様に、インバー
タＩＮＶＩ、ＩＮＶ２を用いることにより、信号２８及
び３１をセレクタ１７の内部で生成することができる。

次に、この実施例の動作を以下に説明する。

第３図は、第２図のオアゲート３２ｄの出力信号の論理
状態を示しており、この第３図において今、降べき指定
で後者優先指定であると仮定すると、ソーティングメモ
リ９もこれに対応して降べき順にソーティングされてい
る。また、ｘ＝１であり、上記の従来例と同様に距離デ
ータの関係が、Ｄｏ　＜ＡＤ＜ＤＩ　とする。

かかる場合、コンパレータ３２ａの比較結果は、出力端
子ＴＩが“Ｈ″゛゛レベルり、出力端子Ｔ２及びＴ３が
“Ｌ”レベルとなるが、降べき指定によりセレクタ３２
ｂは出力端子Ｔ２の出力を選択するので、オアゲート３
２ｄの入力は“Ｌ”レベルとなる。また、後着優先指定
を′Ｈ゛レヘレベすると、アンドゲート３２ｃの出力は
′Ｌ゛レヘレベなる。従って、オアゲート３２ｄの出力
は′″Ｌ″°となる。

もし、ＡＤ＞Ｄ、であれば、出力端子Ｔ２のレベルは“
Ｈ”′となるため、これをセレクタ３２ｂを介して受け
るオアゲート３２ｄの出力は第３図に示すように“Ｈ”
　レベルとなる。

同様にして、昇べき・後着優先、降べき・先着優先の場
合も第３図に示すようになる。

尚、本発明において昇べき・先着優先指定を行う場合に
は、第８図に示すタイムチャートと同じタイムチャート
が得られることになる。

〔発明の効果〕

このように、本発明の辞書ソーティング処理装置によれ
ば、昇べき／降べき及び先着／後着優先指定により、ソ
ーティングメモリに入る距離データＤＬＸは、ソーティ
ング前のＸ段目の距離データＤｋと、ｘ−１段目の距離
データＤ　Ｉ＋−１と、距離演算結果ＡＤの３つのうち
のいずれかが入るように構成したので、昇べき・後着優
先に加えて、昇べき・後着優先、降べき・先着優先、降
べき・後着優先ソーティングが可能となり、辞書検索だ
けでなく、辞書の内容の検討にも種々利用することがで
きる。

【図面の簡単な説明】

第１図は本発明に係る辞書ソーティング処理装置におけ
るソーティング回路を概念的に示すブロック図、 第２図は本発明の辞書ソーティング処理装置に用いられ
るソーティング回路の一実施例を示すブロック図、 第３図は本発明の辞書ソーティング処理装置に用いられ
る比較優先回路の論理状態を、昇べき／降べき及び先着
／後着優先指定と対応して示す図、第４図は本発明の辞
書ソーティング処理装置全体構成を示すブロック図、 第５図はソーティングメモリを示す図、第６図は従来の
辞書ソーティング処理装置におけるソーティング回路を
示すブロック図、第７図は従来の辞書ソーティング処理
装置におけるソーティング回路の一実施例を示す図、第
８図は昇べき・先着優先の場合のソーティング処理を示
すタイムチャート図、である。 第１図及び第４図において、 ２・・・辞書メモリ、 ４・・・イメージメモリ、 ６・・・距離演算部、 ８・・・ソーティング回路、 ９・・・ソーティングメモリ、 １２．１３．２２・・・ラッチ回路、 １７・・・セレクタ、 ３２・・・比較優先回路。 尚、図中、同一符号は同−又は相当部分を示す。 ソーティング回路の鬼り意図 第１図 ２と 従来のソーティング回路 第６図 省を床のソーアイレグ回路の具イホ佼１第７図

Claims (1)

1. 【特許請求の範囲】 辞書メモリ（２）からの特徴量データとイメージメモリ
   （４）からの認識対象文字の特徴量データとから距離演
   算を行い、その演算結果（ＡＤ）に応じてソーティング
   回路（８）がソーティングメモリ（９）のソーティング
   を行う辞書ソーティング処理装置において、該ソーティ
   ング回路（８）が、 該ソーティングメモリ（９）から読み出したｘ段目のデ
   ータ（Ｄ＿ｘ）をラッチする第１のラッチ回路（１２）
   と、 該ｘ段目のデータ（Ｄ＿ｘ）の前段の距離データ（Ｄ＿
   ｘ＿−＿１）をラッチする第２のラッチ回路（１３）と
   、該距離演算結果（ＡＤ）と該ｘ段目のデータ（Ｄ＿ｘ
   ）とを比較して両者の大小関係を該ソーティングメモリ
   （９）に対応した昇べき／降べき指定により選択し、同
   一のときは先着／後着優先指定により選択した出力を発
   生する比較優先回路（３２）と、該比較優先回路（３２
   ）の前回の比較結果をラッチする第３のラッチ回路（２
   ２）と、 該比較優先回路（３２）及び第３のラッチ回路（２２）
   の両比較結果に基づき、該距離演算結果（ＡＤ）と該ｘ
   段目のデータ（Ｄ＿ｘ）と該ｘ−１段目の距離データ（
   Ｄ＿ｘ＿−＿１）とのうちから１つのデータを選択して
   該ソーティングメモリ（９）のｘ段目に記憶するセレク
   タ（１７）と、 を備えたことを特徴とする辞書ソーティング処理装置。