JPH02193279A - ソーティング装置 - Google Patents

Abstract

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

Description

【発明の詳細な説明】 〔産業上の利用分野〕 本発明は、データをそのキーによって一定の順番に並べ
替えるソーティング装置に係り、例えば文字認識装置に
おいて辞書との距離をキーとして候補の文字コードの高
速ソーティングの用途に好適なソーティング装置に関す
る。

〔従来の技術と発明が解決しようとする課題〕漢字ＯＣ
Ｒでは、認識対象文字イメージの特徴を抽出し、それと
標準特徴辞書とのマツチングを行うことによって認識結
果（候補）を決定するが、各テンプレート（辞書の１文
字毎の特徴パターン）とのマツチングを行う毎に距離を
キーとしたソーティングが必要である。第８図はこのソ
ーティングの例である。この例は、（ａ）に示した状態
で、文字コードにのテンプレートとのマツチングで距離
が８０となった場合（簡略的に（Ｋ、８０）と表す）、
文字コードＣと文字コードＤの間に文字コードＫが挿入
されて（ｂ）の状態に更新されたことを示している。

また、漢字ＯＣＲでは、マルチフォントへの対応など、
認識率向上のために同一文字コードに対して複数のテン
プレートを用意する場合がある。

この場合、候補中に同一文字コードが重複しないように
する必要がある。第９図はこの例であり、（ａ）の状態
において、文字コードＧが重複して候補となった＼め、
（Ｇ、８０）を挿入後、同じ文字コードＧで距離が大き
い（Ｇ、１２０）のデータを削除することにより（ｂ）
の状態になったことを示している。

なお、漢字ＯＣＲでは認識結果として１０候補程度を出
力し後処理の対象とするのが一般的であるので、こ＼で
も１０候補としている。また、文字コードとして通常、
シフトＪＩＳなどの漢字コードが用いられるが、こ＼で
は便宜上アルファベットで示している。

このようなソーティングは、汎用のＣＰＵとメモリを用
いソフトウェア処理によって行うことも可能である。し
かし、一つ一つの文字について登録済みデータとの距離
を比較していき、挿入位置を決めた後に、その位置より
後方（距離が大きい側）の登録済みデータ（文字コード
と距離）の移動（読出し書込みの繰返し）を行わなけれ
ばならず、高速処理が難しい。文字コードの重複を排除
する場合には、そのための同様の処理も必要である。

これに対し、距離の値をメモリアドレスのインデックス
として文字コードを書込むことによるソーティングする
方式も提案されているが、かなりのメモリ容量を必要と
する（容量は候補として有効とする距離の最大値に依存
する）といった欠点があり、特に１チツプ化を図る場合
に問題がある。

また、同一文字コードの重複排除は、別処理として行わ
なければならない。

さらに、データベース・システム等への適用を主目的と
して、ソーティング処理を専用のハードウェアを実行さ
せるパイプライン・マージソータ、バイトニックソータ
等も提案されているが、文字認識装置における候補デー
タのソーティング処理用としては回路構成が複雑すぎる
という問題がある。

本発明の目的は、１チツプ化が容易な比較的簡単な構成
で、漢字ＯＣＲの候補データの高速ソーティングなどの
用途に好適なソーティング装置を提供することにある。

本発明の他の目的は、ソートされた結果を外部に効率よ
く読み出すことのできるソーティング装置を提供するこ
とにある。

〔課題を解決するための手段〕

上記目的を達成するために、請求項（１）では、外部よ
り入力されるデータおよびそのキーを保持する手段と、
ロードおよびシフトが可能なエレメントの組合せからな
る多段構成のデータ・シフトアレイおよびキー・シフト
アレイと、該データ・＝４− シフトアレイの各段に保持された各データと該データ保
持手段に保持されたデータとを一斉に比較する手段と、
該キー・シフトアレイの各段に保持された各キーと該キ
ー保持手段に保持されたキーとを一斉に比較する手段と
、該各比較手段の比較績Ｉｋに従って該各シフトアレイ
の各段について一斉に、該保持手段に保持されたデータ
およびキーのロードおよび該各シフトアレイの保持して
いるデータおよびキーのシフトを順次制御することによ
り、該各シフトアレイ上にデータおよびキーをキーの順
番に従って配列させる制御手段とを有することを特徴と
するものである。

また、請求項（２）では、制御手段は、ソーティング結
果を読み出す際、各シフトアレイをアップダウン制御し
、キーの小さい順または大きい順にデータおよび／また
はキーを任意に読み出すことを特徴とするものである。

〔作　用〕

例えば文字認識装置の候補のソーティングに適用した場
合、データは文字コード、キーは距離となる。新規の文
字コードと距離が保持手段に保持されると、各比較手段
によって、この文字コードおよび距離と各シフトアレイ
の各段に保持されている文字コードおよび距離が比較さ
れる。この比較の結果に従って制御手段により、各シフ
トアレイの各段のシフトおよびロードが順次制御され、
新規の文字コードおよび距離を挿入すべき段にスペース
が確保され、その段に新規の文字コードおよび距離がロ
ードされることにより、距離をキーとしたソーティング
がなされる。重複文字コードがある場合、距離の大きい
側の削除も、この時に同時になされる。

新規の距離および文字コードの比較は各シフトアレイの
全段について一斉に比較され、またその比較結果に基づ
く各シフトアレ・ｒのロードおよびシフトも全段につい
て一斉に行われるため、高速のソーティングが可能であ
る。

また、ソーティング結果を外部へ読み出す際は、各シフ
トアレイをアップダウン制御して、キーの小さい順また
は大きい順に読み出すことができるため、これを必要に
応じて任意に変更することにより、効率のよい読出しが
可能である。

装置構成に関しては、各シフトアレイはエレメントを多
段に組合せた規則的構成となり、また各比較手段も通常
の多ビツト比較器と同様の規則的な構成（同一エレメン
トの繰返し）となるため、全体として比較的簡単な回路
構成となり、１チツプ化に向いている。

〔実施例〕

以下、図面を用いて本発明の一実施例について説明する
。

第１図は本発明の一実施例を示すブロック図である。こ
の実施例は、文字認識装置の候補のソーティングに適用
されるもので、認識結果としての文字コード（データ）
と距離（キー）はそれぞれ文字コード・シフトアレイ１
と距離データ・シフトアレイ２上に距離の小さい順にソ
ーティングされるものとする。

新たな文字コードと距離を各シフトアレイ１゜２の該当
する位置に挿入する場合、内部バス３を介し、文字コー
ドは文字コードレジスタ４に、距離データは距離データ
レジスタ５にそれぞれセットされ、コントロール線６に
よりシフトコントロール部７に起動がかけられる。また
、距離データ比較器８により、距離データレジスタ５に
セットされた距離データと、距離データ・シフトアレイ
２に登録済みの距離データ（こ＼では最大１０個）が−
斉に比較され、比較結果がシフトコントロール部７へ与
えられる。同時に、文字コード比較器９により１文字コ
ードレジスタ４にセットされた文字コードと、文字コー
ド・シフトアレイ１に登録済みの文字コードが一斉に比
較され、比較結果がシフトコントロール部７に与えられ
る。

起動されたシフトコントロール部７では、各比較器８，
９の比較結果をもとに簡単な論理演算（後述）を行い、
その結果により各シフトアレイ１．２を動作させて各レ
ジスタ４，５上の文字コードおよび距離データの挿入ス
ペースを確保した後、その挿入スペースに当該文字コー
ドおよび距離データを書込む。最終的な認識結果として
の候補の文字コードおよび距離データは、距離の小さい
順（第１段目から）あるいは大きい順（第１０段目から
）に、文字コードレジスタ４および距離データレジスタ
５を経由して内部バス３に逐次読出すことができる。

第２図（ａ）はシフトアレイ（文字コード・シフトアレ
イ１または距離データ・シフトアレイ２、いずれも同一
構成）のブロック図である。１１は１ビツトのデータの
保持・シフトのためのシフトエレメントである。横一列
に並んだシフトエレメント１１が一つの文字コードまた
は距離データを保持するもので、これが１０段配列され
ている。

データは上の段から下の段へあるいは下の段から上の段
へ向ってシフトされる。同一の段のシフトエレメント１
１は、シフトコントロール部７によって一斉に制御され
る。

第２図（ｂ）に一つのシフトエレメントの入出力信号線
の関係を示す。ここで、ロードデータ入力線ａは文字コ
ード・レジスタ４あるいは距離データレジスタ５に各段
共通に接続される。また、シフトデータ入出力線す、ｃ
は、シフト方向が上から下の場合、ｂが入力線、Ｃが出
力線となり、下から上の場合はこの関係が逆になり、第
１段目のシフトデータ入出力線す及び第１０段目のシフ
トデータ入出力線Ｃはそれぞれレジスタ４または５に接
続される。ｄ−ｈはコントロール／クロック信号線であ
る。なお、シフト／ロード指定線ｆおよびクロック入力
線ｇは（ａ）図では省略しである。データの上段から下
段あるいは下段から上段のシフト方向はシフトアップダ
ウン信号線りの値で決まる。

各シフトエレメント１１は第３図に示すように。

アンド回路２１〜２５、オア回路２６，２７、インバー
タ回路２８〜３０、トランスファゲート回路３１〜３３
、フリップフロップ回路３４より構成されている。信号
名は第２図と一致している。

ロード動作時、レジスタ４または５からのデータ（文字
コードまたは距離）はロードデータ入力線ａに入力し、
フリップフロップ３４に保持される。

シフト動作時、シフトアップダウン信号線りがロウの場
合は、前段からのフリップフロップシフト出力されたデ
ータはシフトデータ入出力線すに入力して、当該段のフ
リップフロップ３４に移り、それまでフリップフロップ
３４に保持されていたデータはシフトデータ入出力線Ｃ
に出力する。シフトアップダウン信号線りがハイの時は
、この関係が逆になる。これらの動作で必要とするシフ
トコントロール部７からのコントロール信号線としては
、シフトを行うかどうかを制御するためのシフトマスク
信号が入力するシフトマスク線ｄ、外部からのデータ入
力を制御するためのロードマスク信号が入力するロード
マスクｓｅ、シフトまたはロードを選択するためのロー
ド／シフト信号が入力するロード／シフト線ｆ、クロッ
クが入力するクロック線ｇ、及び、上記シフトデータ入
出力線す、ｃの入出力関係（すなわち、シフト方向）を
切替えるシフトアップダウン信号が入力するシフトアッ
プダウン信号線りがある。

第４図は距離データ比較器８のブロック図であり、４１
は１ビツトの比較を行う距離データ比較器エレメントを
示している。距離データ比較器８には、一つの距離デー
タのビット数に等しい個数の距離データ比較器エレメン
ト４１を図示のように接続したブロックが、距離データ
・シフトアレイ２の各段に対応して合計１０段分あり、
−斉に作動する。第４図（ｂ）に一つの距離データ比較
器エレメント４１の入出力信号の関係を示す。

各距離データ比較器エレメント４１は第５図に示すよう
に、アンド回路４２〜４５、オア回路４６．４７、イン
バータ回路４８〜５０より構成される。信号名は第４図
と一致している。ａは距離データ・レジスタ８の対応ビ
ットの出力と接続される比較距離入力線、ｆは距離デー
タ・シフトアレイ２の対応段の対応ビットのシフトデー
タ入出力線と接続される登録距離入力線である。ｄは登
録距離〉比較距離のときに有効となる出力線、ｅは登録
距離＝比較距離のときに有効となる出力線である。ｂと
Ｃはそれぞれ上位ビットの距離データ比較器エレメント
の出力線ｄ、ｅが接続される入力線である。

第６図（ａ）は文字コード比較器９のブロック図であり
、５１は文字コードの１ビツトの比較を行うための文字
コード比較器エレメントを示している。文字コード比較
器９には１文字コードのビット数に等しい個数の文字コ
ード比較器エレメント５１を図示のように接続したブロ
ックが、文字コード・シフトアレイ１の各段に対応して
合計１０段分あり、−斉に作動する。第６図（ｂ）に一
つの文字コード比較器エレメント５１の入出力信号関係
を示す。

各文字コード比較器エレメント５１は第７図に示すよう
に、アンド回路５２〜５４、オア回路５５、インバータ
回路５６．５７より構成される。

信号名は第６図と一致している。ａは文字コード・レジ
スタ４の対応ビットの出力と接続される比較文字コード
入力線、Ｃは文字コード・シフトアレイ１の対応段の対
応ビットのシフトデータ出力線と接続される登録文字コ
ード入力線である。ｄは登録文字コード＝比較文字コー
ドのときに有効となる出力線、ｂは上位ビットの文字コ
ード比較器エレメントの出力線ｄが接続される入力線で
ある。

シフトコントロール部７の働きは次の通りである。距離
データレジスタ５にセットされた対象距離データをＤ、
文字コードレジスタ４にセットされた対象文字コードを
Ｃ１登録済みの距離データおよび文字コードをそれぞれ
Ｄ　ｉ＋　ｃｉ　（ｉ＝　ｉ〜１０で１位から１０位ま
での登録済みデータ、すなわちシフトアレイ１，２の各
段の値に対応）とし、距離データ比較器８の結果をＲＤ
□、文字コード比較器９の結果をＲＣ，とする。

ＲＤ□はＤ□〉Ｄのときに有効となり、ＲＣ□はＣ工＝
Ｃのときに有効となる。

ＲＸ、＝ＲＣ工ΦＲＸ□＋１ ＲＸ１１＝ＲＣ，＋ＲＣ２＋・＋ＲＣ１゜とすると、 シフトマスクＭＳよ＝ＲＸ、・ＲＤエ ロードマスクＭＬ□＝　（ＲＤ工０ＲＤ＝−、）・ＭＳ
。

たゾしＲＤ、＝０ となる。こ＼で＋は論理和、・は論理積、■は排他的論
理和、−は否定を表す。

シフトコントロール部７は、ソーティング動作時、上記
演算によって決定したシフトマスクＭＳ□およびロード
マスクＭＬ、の信号をシフトアレイ１．２の対応入力線
に印加した状態で、シフト／ロード指定信号をシフト指
定状態（ハイ状態）にしてクロックを供給し、次にロー
ド指定状態（ロウ状態）にしてクロックを与える。シフ
トアップダウン信号をロウとしておく。最初（シフト指
定時）のクロックで、シフトアレイ１，２上のある段が
挿入すべきスペースとして確保され、次のクロック（ロ
ード指定時）でそのスペース段に対象距離データおよび
対象文字コードが書込まれる。

なお、文字コードが重複している場合、距離が大きいほ
うのデータは上記操作でシフトアレイ１゜２より削除（
シフトアウト）される。

また、ソーティング動作を始める前に、文字コードシフ
トアレイ１は０クリアしく文字コードとしてＯはないも
のとしている）、距離データ・シフトアレイ２はリジェ
クト距離閾値で初期化しておくことは当然である。第１
０図にソーティング動作時のシフトコントロール部７の
処理フローチャートを示す。

ソーティング動作が終了し、各シフトアレイ１゜２より
結果を読み出す場合は、シフト／ロード指定信号をシフ
ト指定状態（ハイ状態）に設定すると共に、シフトアッ
プタウン信号はハイあるいはロウに設定して、クロック
を与える。これにより、各シフトアレイ１，２のソート
済み文字コードおよび距離データが距離の小さい順また
は大きい順に各レジスタ４，５に読み出される。即ち、
シフトアップダウン信号をハイにすると、第２図におい
て、シフト方向は下から上になり、距離の小さい順に読
み出され、シフトアップダウン信号をロウにすると、逆
にシフト方向は上から下になり、距離の大きい順に読み
出される。この読出しは、シフトアレイ１，２の一方に
ついてのみ行ってもよい。

〔発明の効果〕

以上の説明から明らかなように、本発明によれば、比較
的簡単かつ１チツプ化に向いた規則的回路構成で、漢字
ＯＣＲの認識結果などの高速ソーティングおよびソーテ
ィング結果の効率のよい読出しが可能なソーティング装
置を実現することができる。

【図面の簡単な説明】

第１図は本発明の一実施例のブロック図、第２図はシフ
トアレイのブロック図、第３図はシフトエレメントの回
路図、第４図は距離データ比較器の１段分の構成を示す
ブロック図、第５図は距離データ比較器エレメントの回
路図、第６図は文字コード比較器の１段分の構成を示す
ブロック図、第７図は文字コード比較器エレメントの回
路図、第８図は認識結果のソーティングの説明図、第９
図は文字コードが重複した場合の認識結果のソーティン
グの説明図、第１０図はソーティング動作時のシフトコ
ントロール部の処理フロー図である。 １・・・文字コード・シフトアレイ、 ２・・・距離データ・シフトアレイ、 ３・・・内部バス、　４・・・文字コードレジスタ、５
・・・距離データレジスタ、 ７・・・シフトコントロール部、 ８・・・距離データ比較器、 ９・・・文字コード比較器、 １１・・・シフトエレメント、 ３１・・・距離データ比較器エレメント、４１・・・文
字コード比較器エレメント。 ト 一８１７− −よ。−這、勉騨 → 喝ψ ｎ、ｙｈ−）阜ミぐ ｄ υ　譜−−

Claims (2)

【特許請求の範囲】
1. （１）外部より入力されるデータおよびそのキーを保持
   する手段と、ロードおよびシフトが可能なエレメントの
   組合せからなる多段構成のデータ・シフトアレイおよび
   キー・シフトアレイと、該データ・シフトアレイの各段
   に保持された各データと該データ保持手段に保持された
   データとを一斉に比較する手段と、該キー・シフトアレ
   イの各段に保持された各キーと該キー保持手段に保持さ
   れたキーとを一斉に比較する手段と、該各比較手段の比
   較結果に従って該各シフトアレイの各段について一斉に
   、該保持手段に保持されたデータおよびキーのロードお
   よび該各シフトアレイの保持しているデータおよびキー
   のシフトを順次制御することにより、該各シフトアレイ
   上にデータおよびキーをキーの順番に従って配列させる
   制御手段とを有することを特徴とするソーティング装置
   。
2. （２）前記制御手段は、ソーティング結果を外部へ読み
   出す際、各シフトアレイをアップダウン制御し、キーの
   小さい順または大きい順にデータおよび／またはキーを
   読み出すことを特徴とする請求項（１）記載のソーティ
   ング装置。