JPS6191739A - 順位指定デ−タ圧縮方式 - Google Patents

Abstract

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

Description

【発明の詳細な説明】 〔産業上の利用分野〕 本発明はデータ圧縮方式、特に複数のデータを順次処理
する際に優先順位を指定するデータの長さを短縮するた
めの順位指定データ圧縮方式に関する。

〔従来の技術〕

ファイル内の情報の検索などの情報処理を行う場合に、
一つの見出しに対応して処理対象のデータが複数個有る
と、この複数個のデータを処理する優先順位を指示する
几め順位指定データを設定して用いることが多い。例え
ば、日本語入力用のワードプロセッサのかな漢字変換処
理で、読みを示す見出しに対応して複数の漢字表記が有
る場合に、各表記データすなわち各漢字コードを順次に
送出して漢字表示するときの優先順位を指示するため、
順位指定データを設定して用いる。

第２図は従来の順位指定データを説明する几めのデータ
構成図である。順位指定データＰは、処理対象のデータ
Ｄ、ないしＤｍ−１にそれぞれ予め対応した番号０ない
しくｍ−１）を、処理優先順位に対応させて配列した番
号データｉｏないしｊｍ−１から成る。レコードＲは、
見出しデータにと、こｎに対応するデータＤＯないしＤ
ｍ−１とから成っており、このようなレコードＲを複数
個配列して検索用のファイルが構成される。順位指定デ
ータＰの最初の番号データｊ６は第０順位すなわち優先
順位が最高のデータＪ）ｉｏを指定する。番号データ１
１は次の第１順位のデータを指定し、以下順次に優先順
位が下ってゆき、番号データｊｍ−１は第（ｍ−１）順
位すなわち優先順位が最低のデータを指定する。

順位指定データＰのデータ長１ＢｒＩ、ビットとすると
、 Ｂヤ＝ｍｘｂ（ｍ）　　　　　　　　　　・・・・・・
・・・・・・（１）（但し５ｍはデータＤｏないしＤ　
ｒｎ−１の個数を示し、ｂ（ｍ）は整数（ｍ−１）を２
進表示するのに要するビット長を示す。） と表わ嘔れる。例えばｍ　＝　１０のときには、ｂ（ｍ
）＝４（ビット）であるから％ＢＩＯ＝４０（ビット）
である。

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

このような従来の順位指定データＰにおいては、番号デ
ータｉｏないしｉ。−１のうちのどこにでも番号（ｍ−
１）を書込めるように、各番号データ五〇ないしｉｍ−
□のデータ長をいずれもｂ　（ｍｌビットづつにしであ
る。このため、順位指定データＰのデータ長がかなり長
くなる。特に検索用ファイルが大量のレコードＲを含ん
でいる場合には、これに対応する順位指定データＰの個
数も大量になり、これを格納するためのメモリが大規模
化且つ高価格化するという欠点がある。

本発明の目的は、上述の欠点を除去すべ〈従来の順位指
定データの長さを短縮する順位指定データ圧縮方式を提
供することにある。

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

本発明の方式は、レジスタ内のそｊ、それ一つずつ番号
を付与さｆ′Ｌｆｃ複数の番号データのうち前記レジス
タ内に保持済みの保持番号データを除く未保持番号デー
タの一つ１−、前記未保持番号データの個数を表示する
のに挾する最短ビット長で表示して前記レジスタ内に保
持し、更に残りの前記未保持番号データにゼロから始ま
る連続番号を付与し直す変換手段を有し、 ゼロから始まる連続番号を付与した同一ビット長の複数
の番号データ全優先順位に対応して配列した第１の順位
従走データを、前記未保持番号１−タの個数が一つにな
るまでの回数だけ前記変換手段で変換することにエリ、
前記レジスタ内に前記保持番号データから成る圧縮され
た第２の順位発明の詳細な説明する。

本発明の一実施例のデータ構成図を示す第１図を参照し
て従来の順位指定データＰ（０）のデータ長を短縮して
順位指定データＱを得るまでの変換過程を説明する。順
位指定データＰ（０）は、第２図に示した従来の順位指
定データＰと同一構成を有し、各番号１−タ監０ないし
１　ｍ−１の長さはいずれもｂ　（ｍｌビットである。

この順位指定データル＋０１６レジスタに入れたあと％
　（ｍ−１）回の変換過程を経て圧縮された順位指定デ
ータＱ’に得る。

まず、順位指定データｐｔｏ１１順位指定データｐ　＋
１１、（０） に変換する第１回目の過程では、番号データ１゜はその
ままでこれを番号データｊｏとし、ほかの番号アーク１
１ないしＪｏｙ”’１はそれぞれ番号０ないしくｍ−２
）のうちの一つに対応させて、番号データ１ｉｌｌない
し１ｍ−１に変換する。すなわち、ｔｋ＞ｌｏ　が成立
つときには、　ｋｔｌｌ＝　、　ｋｆｏｅ□　とし、・
　（０）　　　　・　ｉｏ＋ １４°’＜ｉｏ　　が成立つときにはｌ　ｋ＝ｌ　ｋ　
とする。

途中の第（ｋ＋１）回目の過程すなわち順位指定データ
Ｐ（ｋ）を順位指定データｐ　（ｋ＋１）に変換する過
程では、番号データｉ、ＱＣ）は番号Ｏから（ｍ　−に
−１）までのうちの一つに等しく、従ってｂ（ｍ−ｋ　
）ビットの長さで表示できるから１番号１−夕１にヲｂ
（。−ｋ）ビットの長さにして番号データｊｋ　とする
。

番号データ１に＋１ないしＪｍ−１もそれぞれ番号０か
ら（ｍ−に−１）までの一つに対応しているが、番号デ
ータｌ　ｋ＋１ないし１ｍ−１の個数（すなわち、（ｍ
−に−１）個）は番号０ないしくｍ　−に−１）の個数
（すなわち、（ｍ−ｋ）個）よりも１個多い。そこで、
番号データｉｋ”＋ｔないしｉＪｌをそれぞれ番号０な
いしくｍ−に−２）のうちの一つに対応し直しで、番号
データｉ（ｋ　＋　１．）な、（ｋ＋１） いし’ｍ−１に変換する。すなわちｓ　　ｊ’７＞ｉ’
Ｆで、（ｋ＋１）−・（社） あれば１ｊ　−１７−１としｓ　　ｊ’２＜ｉ曾であれ
ば、（ｋ＋１）＝　１Ｇｒ）とする。但し、サフィック
スｌは、サフィックスに＋１ないしｍ−１のそれセルに
対応する。この変換により番号データｉ（Ｆ＋ｘ、）は
ｂ（ｍ−に−１）ビットの長さで表示できるようになる
。なお、この第（ｋ＋１）回目の過程では、レジスタ内
の番号データｊｏないしｊ　ｋ−ｘはいずれも変換を施
さずそのまま保持される。

このような変換を順次に施して第（ｍ−１）回目の過程
が終了したとき、レジスタ内の順位指定データｐ（＋″
−１）Ｋおける番号データｉ雫昌）は必らずゼロになる
。すなわち、元の順位指定データＰ（０）に含まれてい
た情報は、番号データｊｏないしＪｍ−２の中に変換さ
れ圧縮されている。番号データｊ。

ないしＪ　ｍ−ｚから成る順位指定データＱの長さをβ
。ビットとすると。

βｒｎ＝　ｂ　（ｍ）　＋　ｂ（ｍ−ｔ）　＋−１°°
＋ｂｔ２１＝Σｂ（ロ）　　　　　　　　　　　　　・
山・・（２）（但し、ｂ（ロ）は整数（μｍ１）ｉ２進
表示するのに要するビット長を示す。） と表わ場れる。

順位指定の対象データの個数ｍが２ないし１０の範囲で
、従来の順位指定データＰ（０）のデータ長Ｂｍと、本
実施例での圧縮された順位指定データＱのデータ長β。

との比較結果を第１表に示す。

データ長の圧縮率βｆｆｉ／Ｂ、は、検索用ファイル中
における対象データ個数ｍの分布に左右されるが、個数
ｍが２ないし１０の範囲では平均して６゜チ程度になり
、個数ｍの小さな方で頻度が高い分布の場合にはほぼ半
分まで圧縮できる。

第１表 このように圧縮された順位指定データＱをレジスタから
メモリへ送って格納するようにすれば、順位指定データ
を格納するのに要する記憶容量を従来の半分近＜まで低
減できる。更に実用上、順位指定データ群を揮発性メモ
リと不揮発性メモリとの間で転送することが多いが、そ
の転送時間も従来の半分近くまで低減でき、情報処理の
時間効率が向上される。

なお、順位指定データが示す優先順位でファイ　″層情
報処理を行ったり、優先順位の置換を行う場合には、圧
縮された順位指定データＱを元の順位指定データＰ（０
）に復元して用いることが多い。順位指定データＰ（０
）への復元は、第１図に示す過程の逆変換を施せば良い
。

すなわち、順位指定データｐ　（ｋ＋１）を順位指定デ
ーｊＩＰ（転）へ逆変換するには、ｂ（ｍ−ｋ）ビット
の番号データｊｋを指示番号はそのままでｂ　（ｒｎ）
　　ビットの長さにして番号１−夕１ｉとし、更に番号
１−夕凰に＋１ないしＩｎ−１については、ｉ（ン＋１
）≧ｊ　ｋテ；ｈｆｔｉＬ’　ｉ　ａ′１＝　ｉ（）＋
１）＋　１　（！：　Ｌ、、ｉ（５＋１）＜　ｊｋであ
れば１１１７　＝　１（ｋｈｌ）とする。この過程では
５番号データｊｏないしｊｋ−ｔには逆変換を流式ない
。

この逆変換を順次に施すことにより、順位指定データＰ
（０）をレジスタ内に復元できる。

本実施例では、順位指定データＱの番号データｊｏない
しＪｍ−１のレジスタへの変換・保持順序がまず番号ｊ
ｏから始まって次に番号データ】１に移り以下順次に移
行して番号データＪｍ−２に到達する場合を示したが、
この順序に限定するものではない。レジスタの物理的構
成と変換処理のやり易さとの関連を考慮し、これに応じ
予め定めた変換・保持順序に従うよう変換するのは容易
である。

〔効果〕

以上の説明から明らかなごとく、本発明の適用により従
来の順位指定データの長さを短縮してこ：ｒｔ′Ｊｋ格
納するためのメモリ・サイズを従来よりも低減し且つそ
のメモリに低価格化できるという効果がある。

【図面の簡単な説明】

第１図は本発明の実施例を示すデータ構成図、第２図は
従来の順位指定データを示すデータ構成図である。 Ｐ＊Ｐ”’ｔＱ・・・・・・順位指定データ、ｉｏない
し１ｍ−１ｓ　Ｉ　ＯないしＪｒｎ−１・・・・・・番
号データ。 、８７ηと゛・Ｉト Ｙｌ劇

Claims (1)

1. 【特許請求の範囲】 レジスタ内のそれぞれ一つずつ番号を付与された複数の
   番号データのうち前記レジスタ内に保持済みの保持番号
   データを除く未保持番号データの一つを、前記未保持番
   号データの個数を表示するのに要する最短ビット長で表
   示して前記レジスタ内に保持し、更に残りの前記未保持
   番号データにゼロから始まる連続番号を付与し直す変換
   手段を有し、 ゼロから始まる連続番号を付与した同一ビット長の複数
   の番号データを優先順位に対応して配列した第１の順位
   指定データを、前記未保持番号データの個数が一つにな
   るまでの回数だけ前記変換手段で変換することにより、
   前記レジスタ内に前記保持番号データから成る圧縮され
   た第２の順位指定データを形成することを特徴とする順
   位指定データ圧縮方式。