JPS6394366A - 英語文書圧縮装置 - Google Patents

Abstract

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

Description

【発明の詳細な説明】 抜４立夏 この発明は、和英辞書検索システムや英文データベース
・システム等に応用し得る自然言語データ、特に英語文
書データを圧縮する装置に関する。

盗】Ｕ１度 各種文書処理装置に入力され処理された英語文書を外部
記憶装置に記憶させる場合、その記憶８五以上に多量に
記憶させるためには、その英語文書のデータを圧縮する
必要がある。

このような英語文書の圧縮方式としては、英文アルファ
ベットの出願頻度に基づいた圧縮方式があるが、高い圧
縮率を達成できなかった。

また、各単語に対して可変長コードを割り当てる方式も
あるが、コードと単語の対応表が巨大なものになる。

さらに、単語単位のハフマン法では、ビット単位の処理
が必要になるため、処理に時間がかかるという間厘点が
あった。

目　　　的 この発明は、上記の点に鑑みてなされたものであり、英
語文書のデータを高い圧縮率で効率よく圧縮できるよう
にすることを目的とする。

構成 この発明は上記の目的を達成するため、次の（ａ）〜（
ｅ）の各手段からなる英語文書圧縮装置を提供するもの
である。

（、）圧縮対象とする英語文書中の全ての単語のうち、
出現頻度の多い方から所定数の単語について第１の出現
頻度リストを、それに続く出現頻度の多い方から所定数
の単語について第２の出現頻度リストをそれぞれ作成す
る出現頻度リスト作成手段、 （ｂ）出現頻度リスト作成手段によって作成された第１
．第２の出現頻度リスト中の単語に含まれる文字対のう
ち、出現頻度の多い方から所定数の文字対について出現
頻度リストを作成する文字対出現頻度リスト作成手段。

（ｃ）第１．第２の出現頻度リストの各単語中の文字射
出１［度リストに含まれる文字対を、それぞれ該文字対
出現頻度リスト中の順位に応じた１バイトのコードで直
換し、その各出現頻度リスト中の単語をそれぞれ語長順
に並べて第１の圧縮単語リストと第２の圧縮単語リスト
を作成する圧縮単語リスト作成手段、 （ｄ）第１．第２の圧縮単語リスト中の各単語の語順と
各リストの先頭からのバイト位置とを関連づける第１．
第２の検索リストを作成する検索リスト作成手段、 （ｅ）圧縮対象の英語文書の各単語のうち、第１の出Ｉ
Ｊ！頻度リストにある単語は第１の圧縮単語リスト中で
の語順に応じた１バイトの圧縮コードに変換し、第２の
出ｆ’ＡＭ度リストにある単語は第２の圧縮単語リスト
中での語順に応じた２バイトの圧縮コードに変換し、空
白を除去して圧縮データを作成する圧縮データ作成手段
、以下、この発明を実施例に基づいて具体的に説明する
。

第１図は、この発明による英語文書圧縮装置の構成を示
すブロック図である。

この装置は、出現頻度リスト作成手段１２文字対出現リ
スト作成手段２．圧縮単語リスト作成手段３．検索リス
ト作成手段４．及び圧縮データ作成手段５からなり、こ
れらは上述の（ａ）〜（ｅ）の各手段であり、実際には
ＣＰＵ、ＲＯＭ、ＲＡＭ等からなるマイクロコンピュー
タによって構成される。

なお、６は圧縮対象とする英語文書を一時記憶する英語
文書メモリである。

まず、この発明の第１実施例について各手段１〜５の機
能を説明する。

出現頻度リスト作成手段１は、英語文書メモリ６に記憶
されている圧縮対象とする英語文書中の全ての単語のう
ち、出現頻度の多い方から上位１２７語によって、第２
図（イ）に示すような１２７レコードの第１の出現頻度
リストを作成し、１２８位から３２８９５位までの単語
によって同図（ロ）に示すような３２７６８レコードの
第２の出現頻度リストを作成する。

文字対出現リスト作成手段２は、第１．第２の出現頻度
リスト中の単語に含まれる文字対（ｔ　ｈ。

ｒｅなど）のうち、各リスト中で出現頻度の多い方から
１２８位までの文字対について、それぞれ第３図に示す
ような１２８レコードの文字対出現頻度リストを作成す
る。

圧縮単語リスト作成手段３は、第１．第２の出現頻度リ
ストの各単語中のそれぞれ文字対出現頻度リストに含ま
れる文字対を、対応する文字対出現頻度リスト上の順位
を７ビツトで表わし、ＭＳＢをｌ”とした第４図に例示
するような１バイトのコードで置換して、第５図（イ）
（ロ）に示すような（ｔｉ換した文字対を０で囲んで示
す）第１゜第２の出現頻度リストを得る。

この各出現頻度リスト中の単語を、それぞれ語長（バイ
ト数）に順に並べて第１．第２の圧縮単語リストを作成
する。

第１の圧縮単語リストは、例えば第６図に示すように、
まず圧縮語長１の単語が並び（Ｉの部分）、次に圧縮語
長２の単語が並び（■の部分）、以下順次圧縮単語長３
，４．５・・・・・・の単語が並ぶ。

第２の圧縮単語リストも同様に、第５図（ロ）の８現頻
度リストの各単語を圧縮単語長の短かい語から順に並べ
たものとする。

検索リスト作成手段４は、このようにして作成された第
１．第２の圧縮単語リスト中の各単語の語順と各リスト
の先頭からのバイト位置を関連づけるために、各圧縮単
語リストそれぞれに対して、各語長の最初の単語に対す
る語順とバイト位置を記録した第１．第２の検索リスト
を作成する。

例えば、第６図に示した第１の圧縮単語リストに対して
は、第７図に示すような検索リストを作成する。

このリストから、例えば圧縮語長１の最初の単語は、第
１の圧縮単語リストの先頭から１′ｔｉ目で１バイト目
の位置にあるａ゛であることを示す。

同じく圧縮単語長２の最初の単語は、先頭から４語口で
４バイト目の位置にあるＯｅ”であることを示している
。

なお、各検索リストのレコード数は、各圧縮単語リスト
に記録されている圧縮単語の最大語長に等しい。

圧縮データ作成手段５は、英語文書メモリ６から圧縮対
象の英語文書を先頭から１語づつ読み出して、その各単
語のうち出現頻度リスト作成手段１によって作成された
第１の出現頻度リストにある出現頻度上位１２７語は、
圧縮単語リスト作成手段３によって作成された第１の圧
縮単語リスト中での語順を７ビツト（ｂｉｔ）で表わし
、ＭＳＢを０″とした第８図に示すような１バイトの圧
縮コードに変換し、第２の出現頻度リストにある出現頻
度１２８位から３２８９５位の３２７６８語は、第２の
圧縮は語リスト中での語順を１５ビツトで表わし、ＭＳ
Ｂを１”とした第Ｓ図に示すような２バイトの圧縮コー
ドに変換する。

さらに、出現頻度３２８９６位以下の単語は、先頭に各
ビットが全て０“の１バイト（ヌルバイト）の特殊コー
ドを付け、その後にその語の各文字のコードのＭＳＢを
最後の文字以外は０“とじ、最後の文字は１゛とじた第
１０図に示すような２バイト以上の可変長コードに変換
する。

そして、空白を削除して圧縮英文データを作成する。

なお、各文字射出ＴＩｔ頻度リスト、圧縮単語リスト及
び検索リストは、それぞれ圧縮英文データを復元する際
に使用するので保存する。

第１１図は、このような各手段の機能をマイクロコンピ
ュータによって実行する場合の処理手順を示すフローチ
ャートであり、ステップ１〜４が第１図の各手段１〜４
に相当し、ステップ６〜１２が圧縮データ作成手段Ｓに
相当する。

このようにすれば、英文データを１／３以下に圧縮する
ことができ、外部記憶装置に大量の英語文書を効率よく
記憶させることができる。

そして、その記憶された圧縮英文データは次のようにし
てバイト単位の操作で高速で復元することができる。

その復元処理のフローチャートを第１２図に示す。

これを簡単に説明すると、まず圧縮文書より最初の１バ
イトのデータを取り出し、そのＭＳＢが１“であれば出
現頻度１２８位から３２８９５位までの単語であるので
、次の１バイトのデータも取り出して、２バイトコード
用の第２の検索リスト及び第２の圧縮単語リストより対
応する文字列を取り出す。

最初の１バイトのデータのＭＳＢが０°ならば１次にそ
の１バイトのどれかのビットにｌ”があるか否かを判断
し、あれば出現頻度１２７位までの単語であるので、１
バイトコード用の第１の検索リスト及び第１の圧縮単語
リストより対応する文字列を取り出す。

そして、このいずれの場合にも、取り出した文字列中に
ＭＳＢが１”のバイトがあれば、対応する文字対出現リ
ストよりその圧縮コードを文字対に変換する。

また、最初の１バイトのＭＳＢが０″で、しかもどのビ
ットにも１゛がない場合にはヌルバイトの特殊コードで
あり、出現頻度３２８９６位以下の単語のデータが続く
ので、ＭＳＢが１″のバイト（第１０図の最後の文字の
バイト）が見つかるまで全てのバイトの文字データを取
り出し。

ＭＳＴｈを”０゛にする。

このようにして、３種類の復元処理のいずれかによって
取り出した文字列をファイルに書き出し、空白を付加し
た後、圧縮データがまだあれば次の１バイトのデータを
取り出して上述の処理を繰り返し、圧縮データがなくな
るまでこの復元処理を繰り返すことにより圧縮した英語
文書を全て復元することができる。

ここで、第６図に示した第１の圧縮単語リストと第７図
に示した第１の検索リストを使用して、１バイトの圧縮
コード　ｃｏｄｅ＝５　（２進数でｏｏｏｏｏｔｏｔ）
の単語を復元する場合の例を説明する。

まず、この１バイトのコードと第１の検索リスト（第７
図）の語順のレコード部分（前半部）を順に比較してい
き、このコード「５」を超えない最大の値をもつレコー
ドを選ぶ（ここでは２ｆｆｉ目のレコード）。

この第１の検索リストの各レコードは、第１の圧縮単語
リストの各語長の最初の語に関する情報を持っており、
対応する語長の短かい順にソートされているので、２番
目のレコードは語長２の圧縮単語に対応している。

したがって、このコードに対応する圧縮単語の語長２（
これを■とする）であることがわかる。

また、この第１の検索リストの２′ａ目のレコードの前
半部（語順）と後半部（バイト位置）から語長２の圧縮
単語は、第１の圧縮単語リストの先頭から４語目（これ
を■とする）で４バイト目（これを■とする）から記録
されていることがわかる。

そして、このコードの値「５」は、このコードに対応す
る語が第１の圧縮単語リストの先頭からＳＭｉ目（これ
を■とする）にあることを示している。

そこで、 （■の値）＋（（■の値）−（■の値））×（■の値）
の式によって、このコード「５」に対応する圧縮単語の
バイト位置を計算すると、 ４＋（５−４）Ｘ２＝６ となり、６バイト目から記録されていることがわかる。

すなわち、第１の圧縮単語リスト（第６図）の先頭から
６バイト目から２バイト（語長が２であるから）を取り
出した文字列゛Ｏ○″がコード「５ノを復元した圧縮単
語となる。

さらに、第３図及び第４図に示した文字対出現リストか
ら、そのリストが文字対のコード順にソートされている
ことを利用してＯ”＠“に対応する文字対を調べて置換
すれば、コード「５」はｍｕｓｔ−に復元される。

次に、この発明の第２実施例について、上述の第１実施
例と異なる点のみを説明する。

この第２実施例は、圧縮対象となる英語文書の異なる単
語の種類が３２８９６種類以下の場合に適するものであ
り、第１図と同様な構成であるが、出現頻度リスト形成
手段１と圧縮データ作成手段５の機能が前述の第１実施
例とは異なる。

この第２実施例の出現頻度リスト作成手段１は、圧縮対
象となる英語文書に含まれる全ての単語の出現頻度の多
い方から上位１２８語（この場合、３２８９６位以下の
語を識別するための全ピッド０゛のヌルバイトを残して
おく必要がないので、第１実施例の場合より１語多い）
によって第１３図（イ）に示すような１２８レコードの
第１の出現頻度リストを作成し、１２９位以下の単語に
よって同図（ロ）に示すような３２７６８レコード以下
の第２の出現頻度リストを作成する。

圧縮データ作成手段５は、英語文書メモリ６から圧縮対
象の英語文書を先頭から１語づつ読み出して、その各単
語のうち上述の出現頻度リスト作成手段１によって作成
された第１の出現頻度リス１〜にある出現頻度上位１２
８語は、第１の圧縮単語リスト中での語順を７ビツト（
ｂｉｔ）で表わし、ＭＳＢを０”とした第８図に示した
ような１バイトの圧縮コードに変換し、第２の出現頻度
リストにある出現頻度１２９位以下の単語は、第２の圧
縮単語リスト中での語順を１５ビツトで表わし、ＭＳＢ
を１”とした第９図に示したような２バイトの圧縮コー
ドに変換し、空白を削除して圧縮英文データを作成する
。

第１４図は、この第２実施例による圧縮英文データ作成
の処理手順を示すフローチャートであり、第１１図と対
応するステップには、同一のステップ番号を付しである
。

ステップ１′は、上述のように第１１図のステップ１と
は若干相違するが第１．第２の出現頻度リストを作成す
る点では同じである。

圧縮データ作成手段５に相当するステップ５〜１２が、
第１１図の第１実施例より簡略になり、そのステップ８
と１０が不要になる。そして、ステップ６′は出願頻度
順位が１２８位までか否かを判断する点が第１１図のス
テップ６（１２７位までか否かの判断）と異なる。

次に、この発明の第３実施例について、前述の第１実施
例と異なる点についてのみを説明する。

この第３実施例も第１図のように構成されており、検索
リスト作成手段４の機能のみが第１実施例と異なる。

この第３実施例の検索リスト作成手段４は、圧縮単語リ
スト作成手段３によって作成された第１の圧縮単語リス
ト（第６図）に対しては、各単語がリストの先頭から何
バイト目から記録されているか（リスト先頭からのバイ
ト数）を記録した、第１６図に示すような第１の検索リ
ストを作成する。

第２の圧縮単語リストに対しては、第１実施例と同様に
各語長の最初の単語に対する語順とバイト位置（リスト
の先頭からのバイト数）を記録した第２の検索リストを
作成する。

この第３実施例による圧縮英文データ作成処理の手順を
フローチャートで示すと、第１１図と同様になるが、ス
テップ４の検索リスト作成処理が若干具なり、上述のよ
うになる。

また、この場合の圧縮英文データの復元処理の手順をフ
ローチャートで示すと、第１２図と同様になるが、１バ
イ１−の圧縮コードを復元する処理が異なる。

そこで、第８図に示した第１の圧縮単語リストと第１６
図に示した第１の検索リストを使って。

１バイトの圧縮コード　ｃ　ｏ　ｄ　ｅ　”　５　　を
復元する場合の例を説明する。

第１６図の検索リストはコード順にソートされているの
で、５番目のレコードを見ると「６」という値が得られ
る。

したがって、第１の圧縮単語リストの先頭から６バイト
目からこのコードに対応する圧縮単語が記録されている
ことがわかる。

次に、この検索リストの（ｃａｒｄ　＋　、１　）番目
すなわち６番目のレコードを見ると、「８」という値が
得られる。これから、第１の圧縮単語リストにおいて、
このコード「５」に対応する圧縮単語の次の単語は、８
バイト目から記録されていることがわかる。

そこで、第１の圧縮単語リストの６バイト目から（８−
１＝７）バイト目までのデータを取り出せば、コード「
５」に対応する圧縮単語゛Ｏ○゛が得られる。

さらに、第１の文字対出現頻度リストからＯ“○”に対
応する文字対を検索して置換するば、”ｍｕｓｔ”を復
元することができる。

この実施例によれば、第１．第２の実施例の場合に比べ
て圧縮データの復元処理に要する時間を短縮することが
できる。

なお、第２の圧縮単語リストに対する第２の検索リスト
も、その各単語が第２の圧縮単語リストの先頭から何バ
イト目から記録されているかを記録した検索リストを作
成するようにすれば、圧縮データの復元処理に要する時
間をさらに短縮することが可能であるが、第２の検索リ
ストのレコード数が極めて多くなるため、それを保存す
るメモリ容量が増大することになる。

豊−釆 以上、各実施例について説明してきたように、この発明
による英語文書圧縮装置は、英文データを１／３以下に
圧縮できるので、各槌英語文書処理システムにおいて、
外部記憶装置に大量の英文データを効率よく記憶させる
ことができる。しかもその圧縮データをバイト単位の操
作で高速で復元することができる。

なお、この発明は、英語文書に限らず、フランス語、ド
イツ語、イタリア語等のアルファベットを用いた自然言
語文書のデータ圧縮にも応用することができる。

【図面の簡単な説明】

第１図はこの発明の実施例の構成を示すブロック図、 第２図（イ）（ロ）は第１実施例の出現頻度リスト作成
手段１によって作成される第１．第２の出現頻度リスト
の例を示す図、 第３図は同じく文字対出現リスト作成手段２によって作
成される第１の文字対出現リストの例を示す図、 第４図は同じくその各文字対と圧縮コードの関係を示す
図。 第５図（イ）（ロ）は文字対置換後の第１．第２の出現
頻度リストの例を示す図、 第６図は圧縮単語リスト作成手段乙によって作成される
第１の圧縮単語リストの例を示す図。 第７図は第１実施例の検索リスト作成手段４によって作
成される第１の検索リストの例を示す図、 第８図、第Ｓ図、及び第１０図は第１実施例の圧縮デー
タ作成手段によって圧縮される１バイトの圧縮コード、
２バイトの圧縮コード。 及び可変長圧縮コードの例をそれぞれ示す図。 第１１図は第１実施例による英文データ圧縮処理のフロ
ー図、 第１２図は同じくその圧縮データ復元処理のフロー図、 第１３図（イ）（ロ）は第２実施例の出現頻度リスト作
成手段１によって作成される第１．第２の出現頻度リス
トの例を示す図、 第１４図は同じくその英文データ圧縮処理のフロー図、 第１５図は同じくその圧縮データ復元処理のフロー図、 第１６図は第３実施例の検索リスト作成手段４によって
作成される第１の検索リストの例を示す図である。 １・・・出現頻度リスト作成手段 ２・・・文字対出現リスト作成手段 ３・・・圧縮単語リスト作成手段 ４・・・検索リスト作成手段 ５・・・圧縮データ作成手段 ６・・・英語文書メモリ 第１図 第２図 （イ）　　　　　　　　　　　　　　　　（ロ）第８図
　　　　　第９図 １パイ）　　　　　　　　　　　　　　　　　２パイＦ
Ｗ１３図 （イ）　　　　　　　　　　　　　　　（ロ）第１６図 ２バイト ローロ　　− ロ０ロー 凶 α） 第１１図 第１４図 第１５図

Claims (1)

1. 【特許請求の範囲】 １　圧縮対象とする英語文書中の全ての単語のうち、出
   現頻度の多い方から所定数の単語について第１の出現頻
   度リストを、それに続く出現頻度の多い方から所定数の
   単語について第２の出現頻度リストをそれぞれ作成する
   出現頻度リスト作成手段と、 該手段によつて作成された第１、第２の出現頻度リスト
   中の単語に含まれる文字対のうち、出現頻度の多い方か
   ら所定数の文字対について出現頻度リストを作成する文
   字対出現頻度リスト作成手段と、 上記第１、第２の出現頻度リストの各単語中の上記文字
   対出現頻度リストに含まれる文字対を、それぞれ該文字
   対出現頻度リスト中の順位に応じた１バイトのコードで
   置換し、その各出現頻度リスト中の単語をそれぞれ語長
   順に並べて第１の圧縮単語リストと第２の圧縮単語リス
   トを作成する圧縮単語リスト作成手段と、 上記第１、第２の圧縮単語リスト中の各単語の語順と各
   リストの先頭からのバイト位置とを関連づける第１、第
   ２の検索リストを作成する検索リスト作成手段と、 圧縮対象の英語文書の各単語のうち、上記第１の出現頻
   度リストにある単語は上記第１の圧縮単語リスト中での
   語順に応じた１バイトの圧縮コードに変換し、上記第２
   の出現頻度リストにある単語は上記第２の圧縮単語リス
   ト中での語順に応じた２バイトの圧縮コードに変換し、
   空白を除去して圧縮データを作成する圧縮データ作成手
   段とを有することを特徴とする英語文書圧縮装置。 ２　検索リスト作成手段が、第１、第２の圧縮単語リス
   トの各語長の最初の語に対してその語の語順と各リスト
   の先頭からのバイト数を記録した第１、第２の検索リス
   トを作成する手段である特許請求の範囲第１項記載の英
   語文書圧縮装置。 ３　検索リスト作成手段が、少なくとも第１の圧縮単語
   リストの各単語に対してそのリストの先頭からのバイト
   数を記録した検索リストを作成する手段を有する特許請
   求の範囲第１項記載の英語文書圧縮装置。 ４　出現頻度リスト作成手段が、出現頻度の多い方から
   上位１２７語によつて第１の出現頻度リストリストを作
   成し、１２８位から３２８９５位までの単語によつて第
   ２の出現頻度リストを作成する手段である特許請求の範
   囲第１項乃至第３項のいずれかに記載の英語文書圧縮装
   置。 ５　圧縮データ作成手段が、圧縮対象の英語文書中に上
   記第１、第２の出現頻度リストのいずれにも含まれない
   単語がある場合には、その単語を１バイトの特殊コード
   を付けた２バイト以上の可変長コードに変換する手段を
   備えている特許請求の範囲第１項乃至第３項のいずれか
   に記載の英語文書圧縮装置。 ６　出現頻度リスト作成手段が、圧縮対象とする英語文
   書中の異なる単語が３２８９６種類以下の場合に、出現
   頻度の多い方から上位１２８語によつて第１の出現頻度
   リストを作成し、１２９位以下の単語によつて第２の出
   現頻度リストを作成する手段である特許請求の範囲第１
   項乃至第３項のいずれかに記載の英語文書圧縮装置。 ７　文字対出現頻度リスト作成手段が、第１、第２の出
   現頻度リスト中の単語に含まれる文字対のうち、各リス
   ト中で出現頻度の多い方から１２８位までの文字対につ
   いてそれぞれ文字対出現頻度リストを作成する手段であ
   る特許請求の範囲第１項乃至第６項のいずれかに記載の
   英語文書圧縮装置。