【事件の表示】
　特許第２６１００８４号「データ伸長方法および装置ならびにデータ圧縮伸長方法および装置」の特許に対する特許異議の申立てについて、次のとおり決定する。
【結論】
　訂正を認める。
　特許第２６１００８４号の特許請求の範囲第１項、第８項、第１５項、第１８項に記載された発明についての特許を維持する。
【理由】
１．手続の経緯
　特許第２６１００８４号の請求項１（実施態様項２ないし７）、請求項８（実施態様項９ないし１４）、請求項１５（実施態様項１６ないし１７）及び請求項１８（実施態様項１９ないし２０）に係る発明は、特願昭５９−１２５４７３号の一部を分割して、平成４年１２月１６日に新たな特許出願とした特願平４−３３４８０４号（優先権主張１９８３年６月２０日、米国）に係る発明であり、平成９年２月１３日にその特許の設定登録がなされ、その後、黒岩　景より特許異議の申立てがなされ、取消理由通知がなされ、その指定期間内である平成１０年８月２４日に訂正請求がなされたものである。
２．訂正の適否についての判断
（１）訂正明細書の特許請求の範囲第１、８、１５、２０項に記載された発明
　訂正明細書の特許請求の範囲第１、８、１５、２０項に記載された発明は、その特許請求の範囲の請求項１、８、１５、２０に記載された次のとおりのものである。
特許請求の範囲第１項
『データ文字ストリームにおける、データ文字ストリングに対応する圧縮された符号信号ストリームから、当該データ文字ストリームを復元するデータ伸長方法において、
　前記圧縮された符号信号ストリームを受信するステップと、
　前記圧縮されたストリーム中の受信した符号信号から対応するデータ文字ストリングを取り出すステップであって、前記圧縮されたストリーム中の受信した符号信号を用いて、前記圧縮されたストリーム中の前記受信した符号信号に対応するデータ文字ストリングをストアするメモリから、対応するデータ文字ストリングを検索するステップを含むステップと、
　取り出されたデータ文字ストリングを用いて前記データ文字ストリームを復元するステップと、
　前記取り出すステップに応答して、拡張されたストリングを前記メモリにストアすることによって、前記圧縮されたストリーム中の前記受信した符号信号に応答してデータ文字ストリングを前記メモリに供給するステップとを具え、前記圧縮されたストリーム中の対応する受信した符号信号から取り出されたデータ文字ストリングを、前記圧縮されたストリーム中の次に続く受信した符号信号から取り出されたデータ文字ストリングの第１文字と連結させて、拡張されたストリングを形成し、および拡張されたストリングの各々を、前記圧縮されたストリーム中の対応する符号信号を用いて、前記メモリから検索可能な形態で、前記メモリにストアし、それにより前記圧縮された符号信号ストリームにより、前記メモリから対応するデータ文字ストリングを取り出し、および前記圧縮されたストリーム中のこれらの符号信号によって、その取り出しに応答して、前記拡張されたストリングを前記メモリに生成し、およびストアすることにより、前記圧縮されたストリーム中の後続の対応する符号信号に対するデータ文字ストリングを取り出すのに用いることを特徴とするデータ伸長方法。』
特許請求の範囲第８項
『データ文字ストリームにおける、データ文字ストリングに対応する圧縮された符号信号ストリームから、当該データ文字ストリームを復元するデータ伸長装置において、
　前記圧縮された符号信号ストリームを受信する手段と、
　前記圧縮されたストリーム中の受信した符号信号に応答して、対応するデータ文字ストリングを取り出す手段であって、前記圧縮されたストリーム中の受信した符号信号に応答して、前記圧縮されたストリーム中の前記受信した符号信号に対応するデータ文字ストリングをストアするメモリから、対応するデータ文字ストリングを検索する手段を含む手段と、
　取り出されたデータ文字ストリングを用いて前記データ文字ストリームを復元する手段と、
　取り出されたデータ文字ストリングに応答して、拡張されたストリングを、前記メモリにストアすることによって、前記圧縮されたストリーム中の前記受信した符号信号に応答してデータ文字ストリングを前記メモリに供給する手段とを具え、前記圧縮されたストリーム中の対応する受信した符号信号から取り出されたデータ文字ストリングを、前記圧縮されたストリーム中の次に続く受信した符号信号から取り出されたデータ文字ストリングの第１文字と連結させて、拡張されたストリングを形成し、拡張されたストリングを、それぞれ、前記圧縮されたストリーム中の対応する符号信号を用いて、前記メモリから検索可能な形態で前記メモリにストアし、それにより前記圧縮された符号信号ストリームにより、前記メモリから対応するデータ文字ストリングを取り出し、および前記圧縮されたストリーム中のこれらの符号信号によって、その取り出しに応答して、前記拡張されたストリングを前記メモリに生成し、およびストアすることにより、前記圧縮されたストリーム中の後続の対応する符号信号に対するデータ文字ストリングを取り出すのに用いることを特徴とするデータ伸長装置。』
特許請求の範囲第１５項
『入力されたデータ文字ストリームを圧縮して圧縮された符号信号ストリームにし、および前記符号信号を用いて、前記圧縮されたストリームを伸長して前記データ文字ストリームを復元する方法において、
　前記データ文字ストリームにおけるデータ文字を探索し、データ文字ストリングに関連する符号信号を有する第１メモリにストアされたデータ文字ストリングとの最長一致を決定するステップと、
　最長一致が決定されたデータ文字ストリングに対応する符号信号を用いて、前記圧縮されたストリームを生成するステップと、
　拡張されたストリングを前記第１メモリにストアし、およびそれに関連した符号信号を割り当てて、最長一致を決定するために用いるデータ文字ストリングを給するステップであって、最長一致を構成するデータ文字を、前記データ文字トリーム中の次の文字と連結して、拡張されたストリングを形成するステップと
を具えて前記入力されたデータ文字ストリームを圧縮し、および
　前記圧縮されたストリーム中の符号信号から対応するデータ文字ストリングを取り出すステップであって、前記圧縮されたストリーム中の前記符号信号に対応するデータ文字ストリングをストアする第２メモリから、前記圧縮されたストリーム中の符号信号を用いて、データ文字ストリングを検索するステップを含むステップと、
　取り出されたデータ文字ストリングを用いて前記データ文字ストリームを復元するステップと、
　前記取り出すステップに応答して、拡張されたストリングを第２メモリにストアすることによって、前記圧縮されたストリーム中の前記符号信号に対応して、データ文字ストリングを前記第２メモリに供給するステップとを具え、前記圧縮されたストリーム中の対応する符号信号から取り出されたデータ文字ストリングを、前記圧縮されたストリーム中の次に続く符号信号から取り出されたデータ文字ストリングの第１文字と連結させて、拡張されたストリングを形成し、および拡張されたストリングを前記圧縮されたストリーム中の当該拡張されたストリングに対応する符号信号を用いて、前記第２メモリから検索可能な形態で、前記第２メモリにストアし、それにより前記圧縮された符号信号ストリームにより、前記第２メモリから対応するデータ文字ストリングを取り出し、および前記圧縮されたストリーム中のこれらの符号信号によって、その取り出しに応答して、前記拡張されたストリングを前記第２メモリに生成し、およびストアすることにより、前記圧縮されたストリーム中の後続の対応する符号信号に対するデータ文字ストリングを取り出すのに用いることにより、前記符号信号を用いて、前記圧縮されたストリームを伸長して前記データ文字ストリームを復元することを特徴とするデータ圧縮伸長方法。』
特許請求の範囲第１８項
『データ文字ストリームを圧縮して圧縮された符号信号ストリームにし、および前記符号信号を用いて、前記圧縮されたストリームを伸長して前記データ文字ストリームを復元する装置において、
　前記入力されたデータ文字ストリームを圧縮する装置と、
　前記圧縮されたストリームを伸長する装置とを具備し、
　前記圧縮する装置は、
　前記データ文字ストリームにおけるデータ文字を探索し、データ文字ストリングに関連する符号信号を有するデータ文字ストリングとの最長一致を決定する手段と、
　前記データ文字ストリングをストアする第１メモリと、
　最長一致が決定されたデータ文字ストリングに対応する符号信号を用いて、前記圧縮されたストリームを生成する手段と、
　拡張されたストリングを前記第１メモリにストアし、およびそれに関連した符号信号を割り当てて、最長一致を決定するために用いるデータ文字ストリングを供給する手段であって、最長一致を構成するデータ文字を、前記データ文字ストリーム中の次の文字と連結して、拡張されたストリングを形成する手段とを具え、
　前記伸長する装置は、
　前記圧縮されたストリーム中の前記符号信号に対応するデータ文字ストリングをストアする第２メモリと、
　前記圧縮されたストリーム中の符号信号から対応するデータ文字ストリングを取り出す手段であって、前記第２メモリから、前記圧縮されたストリーム中の符号信号を用いて、データ文字ストリングを検索する手段と、
　取り出されたデータ文字ストリングを用いて前記データ文字ストリームを復元する手段と、
　取り出されたデータ文字ストリングに応答して、拡張されたストリングを前記第２メモリにストアすることによって、前記圧縮されたストリーム中の前記符号信号に対応して、データ文字ストリングを前記第２メモリに供給する手段とを具え、前記圧縮されたストリーム中の対応する符号信号から取り出されたデータ文字ストリングを、前記圧縮されたストリーム中の次に続く符号信号から取り出されたデータ文字ストリングの第１文字と連結させて、拡張されたストリングを形成し、および拡張されたストリングを前記圧縮されたストリーム中の当該拡張されたストリングに対応する符号信号を用いて、前記第２メモリから検索可能な形態で、前記第２メモリにストアし、それにより前記圧縮された符号信号ストリームにより、前記第２メモリから対応するデータ文字ストリングを取り出し、および前記圧縮されたストリーム中のこれらの符号信号によって、その取り出しに応答して、前記拡張されたストリングを前記第２メモリに生成し、およびストアすることにより、前記圧縮されたストリーム中の後続の対応する符号信号に対するデータ文字ストリングを取り出すのに用いることを特徴とする圧縮伸長装置。』
（２）訂正の目的の適否、新規事項の有無及び拡張・変更の存否
　前記訂正は、特許請求の範囲の減縮に該当し、新規事項の追加に該当せず、実質的に特許請求の範囲を拡張又は変更するものではない。
（３）独立特許要件の判断
　訂正明細書の特許請求の範囲第１、８、１５、１８項に記載された発明に対し、当審が通知した取消理由で引用した刊行物１（米国特許第４，３６６，５５１号明細書）第８欄４３行〜第９欄８行及び図４及び図９には、「ＲＯＳＥ」及び「ＲＯＢＯＴ」を圧縮して得られた「Ａｄｄｒｅｓｓ　Ｎｕｍｂｅｒ」から「ＲＯＢＯＴ」を伸長する際の処理について記載され、入力された「Ａｄｄｒｅｓｓ　Ｎｕｍｂｅｒ」で示される「Ｎｅｔｗｏｒｋ　Ｍｅｍｏｒｙ１２」の「Ａｄｄｒｅｓｓ」を検索し、その「Ａｄｄｒｅｓｓ」に記憶されている「ＧＡＴＥ」及び「ＰＯＩＮＴＥＲ」の連結を取り出し、この取り出した「ＧＡＴＥ」を伸長した文字として出力すると共に、この取り出した「ＰＯＩＮＴＥＲ」で示される次の「Ｎｅｔｗｏｒｋ　Ｍｅｍｏｒｙ１２」中の「Ａｄｄｒｅｓｓ」を検索し、そこに記憶されている「ＧＡＴＥ」及び「ＰＯＩＮＴＥＲ」の連結を取り出す、このような取り出された「ＰＯＩＮＴＥＲ」に基ずき、順次、次の「ＧＡＴＥ」及び「ＰＯＩＮＴＥＲ」の連結を取り出すという処理を「ＰＯＩＮＴＥＲ」の内容０が検索されるまで繰り返すことにより「ＲＯＢＯＴ」を伸長することを例にして説明されている。
　同第６欄第２０行〜第７欄６７行及び図７には、「ＲＯＢＯＴ」を圧縮する際に、これより前に圧縮が行われた「ＲＯＳＥ」との最長一致をＮｏ　Ｍａｔｃｈに基づいて決定し、その結果生成された最長一致した文字に対応する「ＧＡＴＥ」と次に続く文字とを連結させて「Ｎｅｔｗｏｒｋ　Ｍｅｍｏｒｙ１２」に記憶する旨記載されている。
　同刊行物２（米国特許第４，０２１，７８２号明細書）には、入力される文字列を行単位「ｄａｔａ　ｂｌｏｃｋ」に区切り、この区切られた行単位の文字列のうち圧縮対象行の文字列について、当該圧縮対象行の前の行の文字列との比較を行い、一致する部分を特定のデータに置き換えると共に、圧縮対象行の同一行に存在する文字列の中で圧縮対象とする文字列の前に当該圧縮対象とする文字列と一致する文字列が存在する場合、その一致する部分を特定データに置き換えることにより圧縮するという方法及び圧縮されたデータを伸長する方法について記載されている。
（対比・判断）
　訂正明細書の特許請求の範囲第１、８、１５、１８項に記載された発明と刊行物１、２に記載された発明とを対比すると、刊行物１、２には、訂正明細書の発明の、圧縮されたストリーム中の符号信号により、メモリから対応する元のデータ文字ストリングを取り出すのみならず、その取り出しに応答して、拡張されたストリングをメモリに生成することにより、圧縮されたストリーム中の後続の対応する符号信号に対するデータ文字ストリングを取り出すことに用いるようにしたことについての事項、すなわち、訂正明細書の特許請求の範囲第１項の『前記圧縮されたストリーム中の次に続く受信した符号信号から取り出されたデータ文字ストリングの第１文字と連結させて、拡張されたストリングを形成し、および拡張されたストリングの各々を、前記圧縮されたストリーム中の対応する符号信号を用いて、前記メモリから検索可能な形態で、前記メモリにストアし、それにより前記圧縮された符号信号ストリームにより、前記メモリから対応するデータ文字ストリングを取り出し、および前記圧縮されたストリーム中のこれらの符号信号によって、その取り出しに応答して、前記拡張されたストリングを前記メモリに生成し、およびストアすることにより、前記圧縮されたストリーム中の後続の対応する符号信号に対するデータ文字ストリングを取り出すのに用いること』、訂正明細書の特許請求の範囲第８項の『前記圧縮されたストリーム中の対応する受信した符号信号から取り出されたデータ文字ストリングを、前記圧縮されたストリーム中の次に続く受信した符号信号から取り出されたデータ文字ストリングの第１文字と連結させて、拡張されたストリングを形成し、拡張されたストリングを、それぞれ、前記圧縮されたストリーム中の対応する符号信号を用いて、前記メモリから検索可能な形態で前記メモリにストアし、それにより前記圧縮された符号信号ストリームにより、前記メモリから対応するデータ文字ストリングを取り出し、および前記圧縮されたストリーム中のこれらの符号信号によって、その取り出しに応答して、前記拡張されたストリングを前記メモリに生成し、およびストアすることにより、前記圧縮されたストリーム中の後続の対応する符号信号に対するデータ文字ストリングを取り出すのに用いること』、訂正明細書の特許請求の範囲第１５項の『前記圧縮されたストリーム中の対応する符号信号から取り出されたデータ文字ストリングを、前記圧縮されたストリーム中の次に続く符号信号から取り出されたデータ文字ストリングの第１文字と連結させて、拡張されたストリングを形成し、および拡張されたストリングを前記圧縮されたストリーム中の当該拡張されたストリングに対応する符号信号を用いて、前記第２メモリから検索可能な形態で、前記第２メモリにストアし、それにより前記圧縮された符号信号ストリームにより、前記第２メモリから対応するデータ文字ストリングを取り出し、および前記圧縮されたストリーム中のこれらの符号信号によって、その取り出しに応答して、前記拡張されたストリングを前記第２メモリに生成し、およびストアすることにより、前記圧縮されたストリーム中の後続の対応する符号信号に対するデータ文字ストリングを取り出すのに用いることにより、前記符号信号を用いて、前記圧縮されたストリームを伸長して前記データ文字ストリームを復元すること』、訂正明細書の特許請求の範囲第１８項の『前記圧縮されたストリーム中の対応する符号信号から取り出されたデータ文字ストリングを、前記圧縮されたストリーム中の次に続く符号信号から取り出されたデータ文字ストリングの第１文字と連結させて、拡張されたストリングを形成し、および拡張されたストリングを前記圧縮されたストリーム中の当該拡張されたストリングに対応する符号信号を用いて、前記第２メモリから検索可能な形態で、前記第２メモリにストアし、それにより前記圧縮された符号信号ストリームにより、前記第２メモリから対応するデータ文字ストリングを取り出し、および前記圧縮されたストリーム中のこれらの符号信号によって、その取り出しに応答して、前記拡張されたストリングを前記第２メモリに生成し、およびストアすることにより、前記圧縮されたストリーム中の後続の対応する符号信号に対するデータ文字ストリングを取り出すのに用いること』については記載されておらず、示唆もなく、しかも、訂正明細書の特許請求の範囲第１、８、１５、１８項に記載された発明は、当該事項を備えることにより、それぞれ訂正明細書の［発明の効果］の項に記載された顕著な効果を奏するものであるから、刊行物１、２に記載のものから容易に発明をすることができたものとはいえない。
　したがって、訂正明細書の特許請求の範囲第１、８、１５、１８項に記載された発明は、特許出願の際独立して特許を受けることができるものである。
（４）むすび
　以上のとおりであるから、前記訂正は、特許法第１２０条の４第２項及び同条第３項で準用する第１２６条第２項ないし４項の規定に適合するので、当該訂正を認める。
３．特許異議の申立てについての判断
（１）申立の理由の概要
　異議申立人黒岩　景は、請求項１ないし２０に係る各特許発明は甲第１号証（米国特許第４，３６６，５５１号明細書）、甲第２号証（米国特許第４，０２１，７８２号明細書）に記載された発明に基づいて、容易に発明をすることができたものであるから、特許法第２９条第２項の規定により、特許を受けることができず、特許を取り消すべきと主張している。
（１）判断
　訂正明細書の特許請求の範囲第１、８、１５、１８項に記載された発明は前記２．（３）独立特許要件の判断の項で示したように、取消理由通知で示した刊行物１（甲第１号証）、刊行物２（甲第２号証）に記載された発明から容易に発明をすることができたものであるとすることはできない。
　また、他に訂正明細書の特許請求の範囲第１、８、１５、１８項に記載された発明を取り消すべき理由を発見しない。
　よって、結論のとおり決定する。
【異議決定日】
平成１１年５月２０日（１９９９．５．２０）
【訂正の要旨】
（３）訂正の要旨
▲１▼　訂正の要旨ａ
　本件特許明細書（特許第２６１００８４号公報）第１頁第２欄第７行〜第８行（請求項１）、および同第２頁第３欄第４７行〜第４８行（請求項８）に記載の「前記メモリにストアする」を、明りようでない記載の釈明を目的として、「前記メモリにストアし、それにより前記圧縮された符号信号ストリームにより、前記メモリから対応するデータ文字ストリングを取り出し、および前記圧縮されたストリーム中のこれらの符号信号によって、その取り出しに応答して、前記拡張されたストリングを前記メモリに生成し、およびストアすることにより、前記圧縮されたストリーム中の後続の対応する符号信号に対するデータ文字ストリングを取り出すのに用いる」と訂正する。
　本件特許明細書第３頁第５欄第１６行〜第１７行（請求項１５）、および同第３頁第６欄第１４行〜第１５行（請求項１８）に記載の「前記第２メモリにストアする」を、明りようでない記載の釈明を目的として、「前記第２メモリにストアし、それにより前記圧縮された符号信号ストリームにより、前記第２メモリから対応するデータ文字ストリングを取り出し、および前記圧縮されたストリーム中のこれらの符号信号によって、その取り出しに応答して、前記拡張されたストリングを前記第２メモリに生成し、およびストアすることにより、前記圧縮されたストリーム中の後続の対応する符号信号に対するデータ文字ストリングを取り出すのに用いる」と訂正する。
　本件特許明細書第６頁第１１欄第１６行、および同第６頁第１２欄第１６行に記載の「前記メモリにストアする」を、明りようでない記載の釈明を目的として、「前記メモリにストアし、それにより前記圧縮された符号信号ストリームにより、前記メモリから対応するデータ文字ストリングを取り出し、および前記圧縮されたストリーム中のこれらの符号信号によって、その取り出しに応答して、前記拡張されたストリングを前記メモリに生成し、およびストアすることにより、前記圧縮されたストリーム中の後続の対応する符号信号に対するデータ文字ストリングを取り出すのに用いる」と訂正する。
　本件特許明細書第７頁第１３欄第２８行、および同第７頁第１４欄第２１行に記載の「前記第２メモリにストアする」を、明りようでない記載の釈明を目的として、「前記第２メモリにストアし、それにより前記圧縮された符号信号ストリームにより、前記第２メモリから対応するデータ文字ストリングを取り出し、および前記圧縮されたストリーム中のこれらの符号信号によって、その取り出しに応答して、前記拡張されたストリングを前記第２メモリに生成し、およびストアすることにより、前記圧縮されたストリーム中の後続の対応する符号信号に対するデータ文字ストリングを取り出すのに用いる」と訂正する。
▲２▼　訂正の要旨ｂ
　本件特許明細書第１頁第１欄第８行（請求項１）、および同第２頁第３欄第３３行（請求項８）に記載の「その受信した符号信号」を、明りようでない記載の釈明を目的として、「前記圧縮されたストリーム中の受信した符号信号」と訂正する。
　本件特許明細書第１頁第１欄第９行（請求項１）、同第２頁第３欄第５行（請求項３）、同第２頁第３欄第１９行（請求項６）、同第２頁第３欄第３４行（請求項８）、同第２頁第４欄第１１行（請求項１０）、および同第２頁第４欄第２４行（請求項１３）に記載の「受信した符号信号」を、明りようでない記載の釈明を目的として、「前記圧縮されたストリーム中の受信した符号信号」と訂正する。
　本件特許明細書第１頁第１欄第１０行（請求項１）、同第１頁第２欄第１行〜第２行（請求項１）、同第２頁第３欄第３５行（請求項８）、および同第２頁第３欄第４２行（請求項８）に記載の「前記符号信号」を、明りょうでない記載の釈明を目的として、「前記圧縮されたストリーム中の前記受信した符号信号」と訂正する。
　本件特許明細書第１頁第２欄第６行（請求項１）、同第２頁第３欄第４６行〜第４７行（請求項８）に記載の「対応する符号信号」を、明りようでない記載の釈明を目的として、「前記圧縮されたストリーム中の対応する符号信号」と訂正する。
　本件特許明細書第２頁第３欄第２３行（請求項７）、同第２頁第３欄第２５行（請求項７）、同第２頁第４欄第２７行（請求項１４）、同第２頁第４欄第２９行（請求項１４）、同第３頁第５欄第４行（請求項１５）、および同第３頁第６欄第２行（請求項１８）に記載の「符号信号」を、明りょうでない記載の釈明を目的として、「前記圧縮されたストリーム中の符号信号」と訂正する。
　本件特許明細書第３貫第５欄第２行〜第３行（請求項１５）、同第３頁第５欄第９行〜第１０行（請求項１５）、同第３頁第５欄第４８行（請求項１８）、および同第３頁第６欄第７行〜第８行（請求項１８）に記載の「前記符号信号」を、明りようでない記載の釈明を目的として、「前記圧縮されたストリーム中の前記符号信号」と訂正する。
　本件特許明細書第６頁第１１欄第１行〜第２行、および同第６頁第１２欄第１行〜第２行に記載の「その受信した符号信号」を、明りょうでない記載の釈明を目的として、「前記圧縮されたストリーム中の受信した符号信号」と訂正する。
　本件特許明細書第６頁第１１欄第３行、同第６頁第１１欄第２７行、同第６頁第１１欄第３９行、同第６頁第１２欄第３行、同第６頁第１２欄第２７行、および同第６頁第１２欄第３８行に記載の「受信した符号信号」を、明りょうでない記載の釈明を目的として、「前記圧縮されたストリーム中の受信した符号信号」と訂正する。
　本件特許明細書第６頁第１１欄第３行〜第４行、同第６頁第１１欄第１０行、同第６頁第１２欄第４行、および同第６頁第１２欄第１０行に記載の「前記符号信号」を、明りようでない記載の釈明を目的として、「前記圧縮されたストリーム中の前記受信した符号信号」と訂正する。
　本件特許明細書第６頁第１１欄第１４行〜第１５行、同第６頁第１２欄第１５行に記載の「対応する符号信号」を、明りようでない記載の釈明を目的として、「前記圧縮されたストリーム中の対応する符号信号」と訂正する。
　本件特許明細書第６頁第１１欄第４２行、同第６頁第１１欄第４４行〜第４５行、同第６頁第１２欄第４１行、同第６頁第１２棚第４３行〜第４４行、同第７頁第１３欄第１６行、および同第７頁第１４欄第９行に記載の「符号信号」を、明りょうでない記載の釈明を目的として、「前記圧縮されたストリーム中の符号信号」と訂正する。
　本件特許明細書第７頁第１３櫛第１５行、同第７頁第１３欄第２１行、同第７頁第１４欄第６行、および同第７頁第１４欄第１４行に記載の「前記符号信号」を、明りょうでない記載の釈明を目的として、「前記圧縮されたストリーム中の前記符号信号」と訂正する。
▲３▼　訂正の要旨ｃ
　本件特許明細書第３頁第５欄第１４行〜第１５行（請求項１５）、および同第３頁第６欄第１２行〜第１３行（請求項１８）に記載の「当該拡張されたストリングに対応する受信された符号信号」を、明りようでない記載の釈明および誤記の訂正を目的として、「前記圧縮されたストリーム中の当該拡張されたストリングに対応する符号信号」と訂正する。
　本件特許明細書第７頁第１３欄第２６行〜第２７行、および同第７頁第１４欄第１９行〜第２０行に記載の「当該拡張されたストリングに対応する受信された符号信号」を、明りようでない記載の釈明および誤記の訂正を目的として、「前記圧縮されたストリーム中の当該拡張されたストリングに対応する符号信号」と訂正する。
▲４▼　訂正の要旨ｄ
　本件特許明細書第１頁第２欄第３行〜第５行（請求項１）、同第２頁第３欄第４３行〜第４５行（請求項８）に記載の「取り出されたデータ文字ストリングを、次に取り出されたデータ文字ストリングの第１文字と連結させて」を、明りようでない記載の釈明を目的として、「前記圧縮されたストリーム中の対応する受信した符号信号から取り出されたデータ文字ストリングを、前記圧縮されたストリーム中の次に続く受信した符号信号から取り出されたデータ文字ストリングの第１文字と連結させて」と訂正する。
　本件特許明細書第３頁第５欄第１１行〜第１３行（請求項１５）、同第３頁第６欄第９行〜第１１行（請求項１８）に記載の「取り出されたデータ文字ストリングを、次に取り出されたデータ文字ストリングの第１文字と連結させて」を、明りょうでない記載の釈明を目的として、「前記圧縮されたストリーム中の対応する符号信号から取り出されたデータ文字ストリングを、前記圧縮されたストリーム中の次に続く符号信号から取り出されたデータ文字ストリングの第１文字と連結させて」と訂正する。
　本件特許明細書第６頁第１１欄第１１行〜第１３行、同第６頁第１２欄第１１行〜第１３行に記載の「取り出されたデータ文字ストリングを、次に取り出されたデータ文字ストリングの第１文字と連結させて」を、明りようでない記載の釈明を目的として、「前記圧縮されたストリーム中の対応する受信した符号信号から取り出されたデータ文字ストリングを、前記圧縮されたストリーム中の次に続く受信した符号信号から取り出されたデータ文字ストリングの第１文字と連結させて」と訂正する。
　本件特許明細書第７頁第１３欄第２３行〜第２５行、同第７頁第１４欄第１６行〜第１７行に記載の「取り出されたデータ文字ストリングを、次に取り出されたデータ文字ストリングの第１文字と連結させて」を、明りょうでない記載の釈明を目的として、「前記圧縮されたストリーム中の対応する符号信号から取り出されたデータ文字ストリングを、前記圧縮されたストリーム中の次に続く符号信号から取り出されたデータ文字ストリングの第１文字と連結させて」と訂正する。
▲５▼　訂正の要旨ｅ
本件特許明細書第２頁第３欄第２０行〜第２１行（請求項６）、および同第２頁第４欄第２５行（請求項１３）に記載の「検索すること」を、明りょうでない記載の釈明を目的として、「検索し、前記拡張されたストリングの前記データ文字ストリング部分を、そのデータ文字ストリングに対応する前記圧縮されたストリーム中の符号信号を用いて供給すること」と訂正する。
　本件特許明細書第６頁第１１欄第４１行、および同第６頁第１２欄第３９行に記載の「検索すること」を、明りようでない記載の釈明を目的として、「検索し、前記拡張されたストリングの前記データ文字ストリング部分を、そのデータ文字ストリングに対応する前記圧縮されたストリーム中の符号信号を用いて供給すること」と訂正する。
▲６▼　訂正の要旨ｆ
　本件特許明細書第２頁第４欄第４９行（請求項１５）に記載の「により前記入力された」を、明りょうでない記載の釈明を目的として、「を具えて前記入力された」と訂正する。
　本件特許明細書第３頁第５欄第１７行（請求項１５）に記載の「ことを特徴とする」を、明りようでない記載の釈明を目的として、「ことにより、前記符号信号を用いて、前記圧縮されたストリームを伸長して前記データ文字ストリームを復元することを特徴とする」と訂正する。
　本件特許明細書第７頁第１３欄第１２行に記載の「により前記入力された」を、明りようでない記載の釈明を目的として、「を具えて前記入力された」と訂正する。
　本件特許明細書第７頁第１３欄第２８行〜第２９行に記載の「ことを特徴とする」を、明りようでない記載の釈明を目的として、「ことにより、前記符号信号を用いて、前記圧縮されたストリームを伸長して前記データ文字ストリームを復元することを特徴とする」と訂正する。
▲７▼　訂正の要旨ｇ
　本件特許明細書第２頁第４欄第２５行（請求項１３）に記載の「データ文字」を、誤記の訂正を目的として、「データ文字ストリング」と訂正する。
　本件特許明細書第６頁第１２欄第３９行に記載の「データ文字」を、誤記の訂正を目的として、「データ文字ストリング」と訂正する。
▲８▼　訂正の要旨ｈ
　本件特許明細書第３頁第６欄第８行（請求項１８）に記載の「デタ文字ストリング」を、誤記の訂正を目的として、「データ文字ストリング」と訂正する。
　本件特許明細書第７頁第１４欄第１４行〜第１５行に記載の「デタ文字ストリング」を、誤記の訂正を目的として、「データ文字ストリング」と訂正する。
▲９▼　訂正の要旨ｉ
　本件特許明細書第１１頁第２２欄第３２行に記載の「ハッシュ関数２３」を、誤記の訂正を目的として、「ハッシュ関数回路２３」と訂正する。
▲１０▼　訂正の要旨ｉ
　本件特許明細書第３頁第６欄第６行（請求項１８）に記載の「取り出されたストリング」を、明りようでない記載の釈明を目的として、「取り出されたデータ文字ストリング」と訂正する。
　本件特許明細書第７頁第１４欄第１２行に記載の「取り出されたストリング」を、明りようでない記載の釈明を目的として、「取り出されたデータ文字ストリング」と訂正する。
（５４）【発明の名称】
データ伸長方法および装置ならびにデータ圧縮伸長方法および装置
（５７）【特許請求の範囲】
　【請求項１】　データ文字ストリームにおける、データ文字ストリングに対応する圧縮された符号信号ストリームから、当該データ文字ストリームを復元するデータ伸長方法において、
　前記圧縮された符号信号ストリームを受信するステップと、
　前記圧縮されたストリーム中の受信した符号信号から対応するデータ文字ストリングを取り出すステップであって、前記圧縮されたストリーム中の受信した符号信号を用いて、前記圧縮されたストリーム中の前記受信した符号信号に対応するデータ文字ストリングをストアするメモリから、対応するデータ文字ストリングを検索するステップを含むステップと、
　取り出されたデータ文字ストリングを用いて前記データ文字ストリームを復元するステップと、
　前記取り出すステップに応答して、拡張されたストリングを前記メモリにストアすることによって、前記圧縮されたストリーム中の前記受信した符号信号に応答してデータ文字ストリングを前記メモリに供給するステップとを具え、前記圧縮されたストリーム中の対応する受信した符号信号から取り出されたデータ文字ストリングを、前記圧縮されたストリーム中の次に続く受信した符号信号から取り出されたデータ文字ストリングの第１文字と連結させて、拡張されたストリングを形成し、および拡張されたストリングの各々を、前記圧縮されたストリーム中の対応する符号信号を用いて、前記メモリから検索可能な形態で、前記メモリにストアし、それにより前記圧縮された符号信号ストリームにより、前記メモリから対応するデータ文字ストリングを取り出し、および前記圧縮されたストリーム中のこれらの符号信号によって、その取り出しに応答して、前記拡張されたストリングを前記メモリに生成し、およびストアすることにより、前記圧縮されたストリーム中の後続の対応する符号信号に対するデータ文字ストリングを取り出すのに用いることを特徴とするデータ伸長方法。
　【請求項２】　前記圧縮された符号信号ストリームは、前記データ文字ストリーム中のデータ文字を探索して、割り当てられた符号信号を持つデータ文字ストリングとの最長一致を決定して生成されたものに対応し、
　決定された最長一致に対応する符号信号を用いて前記圧縮されたストリームを生成し、および
　各決定された最長一致を、データ文字ストリームにおいて次に続く文字と連結させて、最長一致を決定するために用いるデータ文字ストリングを供給することを特徴とする特許請求の範囲第１項に記載の方法。
　【請求項３】　前記対応するデータ文字ストリングを取り出すステップは、前記圧縮されたストリーム中の受信した符号信号が最初にストアされた文字に対応するか否かを決定し、対応する場合は、当該文字を、取り出したデータ文字ストリングとして用いるステップを含むことを特徴とする特許請求の範囲第１項に記載の方法。
　【請求項４】　複数の予め定めたストリングを最初にストアし、および前記圧縮されたストリームを伸長する前に、対応する符号信号を前記複数の予め定めたストリングに割り当てるステップを含むことを特徴とする特許請求の範囲第１項に記載の方法。
　【請求項５】　最初にストアされた予め定めたストリングは、前記データ文字ストリーム中の個別の文字に対応するストリングを含むことを特徴とする特許請求の範囲第４項に記載の方法。
　【請求項６】　前記圧縮されたストリーム中の受信した符号信号を用いて前記メモリをアドレス指定して対応するデータ文字ストリングを検索し、前記拡張されたストリングの前記データ文字ストリング部分を、そのデータ文字ストリングに対応する前記圧縮されたストリーム中の符号信号を用いて供給することを特徴とする特許請求の範囲第１項に記載の方法。
　【請求項７】　前記圧縮されたストリーム中の符号信号に応答して前記メモリから逆の順序でデータ文字ストリングを検索し、および検索されたデータ文字を反転させて、検索に用いた前記圧縮されたストリーム中の符号信号に対応するデータ文字ストリングを生成するステップを含むことを特徴とする特許請求の範囲第６項に記載の方法。
　【請求項８】　データ文字ストリームにおける、データ文字ストリングに対応する圧縮された符号信号ストリームから、当該データ文字ストリームを復元するデータ伸長装置において、
　前記圧縮された符号信号ストリームを受信する手段と、
　前記圧縮されたストリーム中の受信した符号信号に応答して、対応するデータ文字ストリングを取り出す手段であって、前記圧縮されたストリーム中の受信した符号信号に応答して、前記圧縮されたストリーム中の前記受信した符号信号に対応するデータ文字ストリングをストアするメモリから、対応するデータ文字ストリングを検索する手段を含む手段と、
　取り出されたデータ文字ストリングを用いて前記データ文字ストリームを復元する手段と、
　取り出されたデータ文字ストリングに応答して、拡張されたストリングを、前記メモリにストアすることによって、前記圧縮されたストリーム中の前記受信した符号信号に応答してデータ文字ストリングを前記メモリに供給する手段とを具え、前記圧縮されたストリーム中の対応する受信した符号信号から取り出されたデータ文字ストリングを、前記圧縮されたストリーム中の次に続く受信した符号信号から取り出されたデータ文字ストリングの第１文字と連結させて、拡張されたストリングを形成し、拡張されたストリングを、それぞれ、前記圧縮されたストリーム中の対応する符号信号を用いて、前記メモリから検索可能な形態で前記メモリにストアし、それにより前記圧縮された符号信号ストリームにより、前記メモリから対応するデータ文字ストリングを取り出し、および前記圧縮されたストリーム中のこれらの符号信号によって、その取り出しに応答して、前記拡張されたストリングを前記メモリに生成し、およびストアすることにより、前記圧縮されたストリーム中の後続の対応する符号信号に対するデータ文字ストリングを取り出すのに用いることを特徴とするデータ伸長装置。
　【請求項９】　前記圧縮された符号信号ストリームは、前記データ文字ストリーム中の連続データ文字を探索して、割り当てられた符号信号を持つデータ文字ストリングとの最長一致を決定して生成されたものに対応し、
　決定された最長一致に対応する符号信号を用いて前記圧縮されたストリームを生成し、および
　各決定された最長一致を、データ文字ストリームにおいて次に続く文字と連結させて、最長一致を決定するために用いるデータ文字ストリングを供給することを特徴とする特許請求の範囲第８項に記載の装置。
　【請求項１０】　前記対応するデータ文字ストリングを取り出す手段は、前記圧縮されたストリーム中の受信した符号信号が最初にストアされた文字に対応するかを決定し、対応する場合は、当該文字を、取り出したデータ文字ストリングとして用いることを特徴とする特許請求の範囲第８項に記載の装置。
　【請求項１１】　複数の予め定めたストリングを最初にストアし、および前記圧縮されたストリームを伸長する前に、対応する符号信号を前記複数の予め定めたストリングに割り当てる手段を含むことを特徴とする特許請求の範囲第８項に記載の装置。
　【請求項１２】　最初にストアされた予め定めたストリングは、前記データ文字ストリームの個別の文字に対応するストリングを含むことを特徴とする特許請求の範囲第１１項に記載の装置。
　【請求項１３】　前記メモリは、前記圧縮されたストリーム中の受信した符号信号に応答して対応するデータ文字ストリングを検索し、前記拡張されたストリングの前記データ文字ストリング部分を、そのデータ文字ストリングに対応する前記圧縮されたストリーム中の符号信号を用いて供給することを特徴とする特許請求の範囲第８項に記載の装置。
　【請求項１４】　前記圧縮されたストリーム中の符号信号に応答して前記メモリから逆の順序でデータ文字ストリングを検索し、および検索されたデータ文字を反転させて、検索に用いた前記圧縮されたストリーム中の符号信号に対応するデータ文字ストリングを生成する手段を含むことを特徴とする特許請求の範囲第１３項に記載の装置。
　【請求項１５】　入力されたデータ文字ストリームを圧縮して圧縮された符号信号ストリームにし、および前記符号信号を用いて、前記圧縮されたストリームを伸長して前記データ文字ストリームを復元する方法において、
　前記データ文字ストリームにおけるデータ文字を探索し、データ文字ストリングに関連する符号信号を有する第１メモリにストアされたデータ文字ストリングとの最長一致を決定するステップと、
　最長一致が決定されたデータ文字ストリングに対応する符号信号を用いて、前記圧縮されたストリームを生成するステップと、
　拡張されたストリングを前記第１メモリにストアし、およびそれに関連した符号信号を割り当てて、最長一致を決定するために用いるデータ文字ストリングを供給するステップであって、最長一致を構成するデータ文字を、前記データ文字ストリーム中の次の文字と連結して、拡張されたストリングを形成するステップと、
を具えて前記入力されたデータ文字ストリームを圧縮し、および
　前記圧縮されたストリーム中の符号信号から対応するデータ文字ストリングを取り出すステップであって、前記圧縮されたストリーム中の前記符号信号に対応するデータ文字ストリングをストアする第２メモリから、前記圧縮されたストリーム中の符号信号を用いて、データ文字ストリングを検索するステップを含むステップと、
　取り出されたデータ文字ストリングを用いて前記データ文字ストリームを復元するステップと、
　前記取り出すステップに応答して、拡張されたストリングを第２メモリにストアすることによって、前記圧縮されたストリーム中の前記符号信号に対応して、データ文字ストリングを前記第２メモリに供給するステップとを具え、前記圧縮されたストリーム中の対応する符号信号から取り出されたデータ文字ストリングを、前記圧縮されたストリーム中の次に続く符号信号から取り出されたデータ文字ストリングの第１文字と連結させて、拡張されたストリングを形成し、および拡張されたストリングを前記圧縮されたストリーム中の当該拡張されたストリングに対応する符号信号を用いて、前記第２メモリから検索可能な形態で、前記第２メモリにストアし、それにより前記圧縮された符号信号ストリームにより、前記第２メモリから対応するデータ文字ストリングを取り出し、および前記圧縮されたストリーム中のこれらの符号信号によって、その取り出しに応答して、前記拡張されたストリングを前記第２メモリに生成し、およびストアすることにより、前記圧縮されたストリーム中の後続の対応する符号信号に対するデータ文字ストリングを取り出すのに用いることにより、前記符号信号を用いて、前記圧縮されたストリームを伸長して前記データ文字ストリームを復元することを特徴とするデータ圧縮伸長方法。
　【請求項１６】　最初に、複数の同様の予め定めたストリングを前記第１および第２メモリの各々にストアし、符号信号を割り当てるステップを含むことを特徴とする特許請求の範囲第１５項に記載の方法。
　【請求項１７】　最初にストアされた予め定めたストリングは、前記データ文字ストリーム中の個別の文字に対応するストリングを含むことを特徴とする特許請求の範囲第１６項に記載の方法。
　【請求項１８】　データ文字ストリームを圧縮して圧縮された符号信号ストリームにし、および前記符号信号を用いて、前記圧縮されたストリームを伸長して前記データ文字ストリームを復元する装置において、
　前記入力されたデータ文字ストリームを圧縮する装置と、
　前記圧縮されたストリームを伸長する装置とを具備し、
　前記圧縮する装置は、
　前記データ文字ストリームにおけるデータ文字を探索し、データ文字ストリングに関連する符号信号を有するデータ文字ストリングとの最長一致を決定する手段と、
　前記データ文字ストリングをストアする第１メモリと、
　最長一致が決定されたデータ文字ストリングに対応する符号信号を用いて、前記圧縮されたストリームを生成する手段と、
　拡張されたストリングを前記第１メモリにストアし、およびそれに関連した符号信号を割り当てて、最長一致を決定するために用いるデータ文字ストリングを供給する手段であって、最長一致を構成するデータ文字を、前記データ文字ストリーム中の次の文字と連結して、拡張されたストリングを形成する手段とを具え、
　前記伸長する装置は、
　前記圧縮されたストリーム中の前記符号信号に対応するデータ文字ストリングをストアする第２メモリと、
　前記圧縮されたストリーム中の符号信号から対応するデータ文字ストリングを取り出す手段であって、前記第２メモリから、前記圧縮されたストリーム中の符号信号を用いて、データ文字ストリングを検索する手段と、
　取り出されたデータ文字ストリングを用いて前記データ文字ストリームを復元する手段と、
　取り出されたデータ文字ストリングに応答して、拡張されたストリングを前記第２メモリにストアすることによって、前記圧縮されたストリーム中の前記符号信号に対応して、データ文字ストリングを前記第２メモリに供給する手段とを具え、前記圧縮されたストリーム中の対応する符号信号から取り出されたデータ文字ストリングを、前記圧縮されたストリーム中の次に続く符号信号から取り出されたデータ文字ストリングの第１文字と連結させて、拡張されたストリングを形成し、および拡張されたストリングを前記圧縮されたストリーム中の当該拡張されたストリングに対応する符号信号を用いて、前記第２メモリから検索可能な形態で、前記第２メモリにストアし、それにより前記圧縮された符号信号ストリームにより、前記第２メモリから対応するデータ文字ストリングを取り出し、および前記圧縮されたストリーム中のこれらの符号信号によって、その取り出しに応答して、前記拡張されたストリングを前記第２メモリに生成し、およびストアすることにより、前記圧縮されたストリーム中の後続の対応する符号信号に対するデータ文字ストリングを取り出すのに用いることを特徴とする圧縮伸長装置。
　【請求項１９】　最初に、複数の同様の予め定めたストリングを前記第１および第２メモリの各々にストアし、符号信号を割り当てる手段を含むことを特徴とする特許請求の範囲第１８項に記載の装置。
　【請求項２０】　最初にストアされた予め定めたストリングは、前記データ文字ストリーム中の個別の文字に対応するストリングを含むことを特徴とする特許請求の範囲第１９項に記載の装置。
【発明の詳細な説明】
　【産業上の利用分野】
　本発明は一般的にいえば、データ圧縮および圧縮データの伸長（ｄｅｃｏｍｐｒｅｓｓｉｏｎ）の分野に関するものである。さらに具体的にいえば、ディジタル入力信号の流れにおいて新しく遭遇した文字ストリングごとに接頭部ストリングと一つの拡張文字からなる文字ストリングとして割り当てた符号信号を用いて圧縮した符号信号の流れからディジタル入力信号の流れを回復するデータ伸長方法とその方法を実現するためのデータ伸長装置ならびにデータ圧縮伸長方法および装置に関する。
　【従来の技術】
　ディジタル・データ信号のストリームを圧縮されたディジタル・データ信号に符号化して、圧縮されたディジタル・データ信号を元のデータ信号に復元するデータ圧縮装置が従来知られている。データ圧縮とは、与えられたフォーマットのデータを元のものより少ないビットをもつもう一つのフォーマットに変換するすべての処理をいう。データ圧縮装置の目的はディジタル情報の与えられた主要部を保持するに必要な記憶装置の量またはその主要部を伝送するに必要な時間の量を節約することである。圧縮比は、符号化されたデータの長さの元の入力データの長さに対する比として定義される。圧縮比が小さければ小さいほど、記憶域または時間の節約が大きくなる。データ記憶に必要な記憶装置またはデータ伝送に必要な時間を減らすことによって、圧縮は金銭上の節約をもたらす。磁気ディスクまたは磁気テープのような物理的装置がデータファイルの格納に用いられれば、圧縮されたデータを格納する装置に必要なスペースが小さくなって利用するディスクまたはテープが少なくなる。電話線またはサテライト・リンクをディジタル情報の伝送に用いる場合、伝送の前にデータを圧縮するとコストが下がる。データ圧縮装置は、元のデータが高い頻度で現れる記号または記号のストリングを持つような冗長性を含む場合に特に有効である。データ圧縮装置がデータの入力ブロックをより簡潔な形に変換し、そのあとでその簡潔な形を逆にそれの元のフォーマットの元のデータに翻訳または伸長する。
　例えば、日刊新聞の内容をサテライト・リンクを経て遠隔の地に伝送して、そこで印刷することが望まれることがある。適当なセンサが新聞の内容を直列に発生する文字のデータ・ストリームに変換して、通信リンクを介して伝送することができる。新聞の内容を含む何百万の記号が伝送前に圧縮されて受信者のところで再構成されるとすればかなりの量の伝送時間が節約されるであろう。
　別の例として、定期航空路予約データベースまたはバンキング・システム・データベースなどの広範囲なデータベースが記録保管の目的で格納されるとき、データベースを構成する文字の全体が記憶に先立って圧縮されて、あとで使用するには格納された圧縮ファイルから再び広げられるとすれば、かなりの量の記憶スペースが節約されるであろう。
　【発明が解決しようとする課題】
　実際にそして一般に役立つようにするためには、ディジタル・データ圧縮装置がある基準を満足する必要がある。この装置はデータ圧縮装置およびデータ伸長装置が仲介している機器によって授受されるデータ速度に関して高い性能を与える必要がある。データ圧縮できる速度は、圧縮装置に入る入力データ処理速度によって決まり、普通数百万バイト毎秒（メガバイト／秒）である。普通１メガバイト／秒を超える速度を持つ今日のディスク、テープおよび通信装置において達成されたデータ速度を保つには高性能が必要である。従って、データ圧縮装置およびデータ伸長装置は、最近の装置で達成される帯域幅に一致するデータ帯域幅をもっていなければならない。従来のデータ圧縮装置およびデータ伸長装置の性能は、普通、統計的データを記憶して圧縮処理および伸長処理を管理するのに用いられるランダムアクセス記憶装置（ＲＡＭ）などの速度によって制限される。圧縮装置に対する高性能は、圧縮装置に入る入力文字ごとに必要なｒａｍサイクル（読み書き動作）の数によって特徴づけられる。記憶サイクルの数が少なければ少ないほど性能は高い。高性能設計を電話通信等の低速度の適用業務に対して経済的な低速ＲＡＭを用いて利用でき、または磁気ディスク転送に対して超高速ＲＡＭを用いて利用できる。
　データ圧縮装置およびデータ伸長装置の設計におけるもう一つの重要な基準は、圧縮有効度である。圧縮有効度は装置の圧縮比によって特徴づけられる。圧縮比は、圧縮された形のデータ記憶の大きさを圧縮されていない形のデータ記憶の大きさで割った比である。データが圧縮可能であるためには、そのデータは、冗長度を含んでいなければならない。圧縮有効性は、圧縮手順が入力データにおける冗長性のいろいろな形態にいかに有効に調和するかによって決められる。代表的なコンピュータに記憶されたデータ、例えば整数の配列、テキストまたはプログラムなどにおいて、冗長は個々の記号表記法、例えば数字、バイトの不統一な使用と共通語などの記号列、空白記録欄などの頻繁な繰返しの両方において起こる。有効なデータ圧縮装置は、両方の形式の冗長性に応じる必要がある。
　データ圧縮装置およびデータ伸長装置の設計における別の重要な基準は、適応性の基準である。多くの従来のデータ圧縮手段は、圧縮されようとするデータの以前の知識または統計を必要とする。従来の手順のあるものは、データが受けられるときのデータの統計に適用する。従来の処理における適応性は、法外な複雑度を必要とした。普通には、汎用コンピュータ施設における必要条件である広範囲の情報形式にわたって適応圧縮および伸長装置を用いることができる。圧縮装置は、データ統計の以前の知識がなくても良好な圧縮比を達成することが望ましい。現在利用できるデータ圧縮手順およびデータ伸長手段は、一般には適応できないので、それを汎用用途には利用できない。
　データ圧縮装置およびデータ伸長装置の設計におけるもう一つの重要な基準は、可逆性の基準である。データ圧縮装置が可逆性の性質をもつためには、その装置は、圧縮されたデータを情報の変質または損失なしにその元の形に再拡張または伸長することができなければならない。伸長されたデータと元のデータとは同一であって互いに区別できないものでなければならない。
　適応性のあるようにされているか、または適応性のあるようにされる可能性のある汎用データ圧縮手段が従来技術において知られており、二つの該当する手順は、ハフマン（Ｈｕｆｆｍａｎ）法およびタンスタル（Ｔｕｎｓｔａｌｌ）法である。ハフマン法は広く知られて用いられており、それに関してはハフマンの「最小冗長性コードの構成のための方法」という論文［プロシーディングスＩＲＥ、第４０巻、第１０号、１０９８〜１１００頁（１９５２年９月）］に出ている。さらハフマンの方法については、Ｒ．ガラハ（Ｇａｌｌａｇｈｅｒ）の「ハフマンによる論文についての変形」という論文［ＩＥＥＥ情報理論トランザクションズ，ＩＴ−２４，Ｎｏ．６（１９７８年１１月）］に見ることができる。適応ハフマン・コーディングは、固定長の記号列を可変長さ２進語に写像する。適応ハフマン・コーディングは、その方法が解釈できる固定列長より長い入力記号列内に冗長があるとき、それが有効でないという限界をもっているという欠点がある。ハフマン法を実際に装置として具体化するときは、入力列長は、ＲＡＭの価格のために１２ビットを超えることは殆どないので、この方法は、一般は良好な圧縮比を達成しない。なお、適応ハフマン法は複雑で、各入力記号に対して法外に多数の記憶サイクルを必要とすることが多い。従って、適応ハフマン法は、望ましくないほどわずらわしく、高価でかつ遅い傾向があるために、この方法を実際的な現在の設備のほとんどに適さなくしている。
　タンスタルの方法については、Ｂ．Ｔ．タンスタルの「雑音のない圧縮コードの合成」という題名の博士論文、［ジョージア・インスティチュート・オブ・テクノロジ（１９６７年９月）］に見ることができる。タンスタルの方法は、可変長の入力記号列を固定長の２進出力語に写像する。タンスタル法の適応形は、従来技術に記載されていないが、一つの適応形を誘導できる可能性はあるものの、それは複雑で高性能の装置にするには不適切であろう。ハフマン法もタンスタル法も原始記号の組合せの長さが段々長くなると符号化することができなくなる。
　従来技術の欠点の多くを克服するさらに別の適応データ圧縮および伸長装置は、Ｍ．コーイン（Ｃｏｈｅｎ）、Ｗ．イーストマン（Ｅａｓｔｍａｎ）、Ａ．レンペル（Ｌｅｍｐｅｌ）およびＪ．ジブ（Ｚｉｖ）の米国特許第４，４６４，６５０号（データの圧縮と圧縮されたデータの伸長の装置と方法」（１９８１年８月１０日出願）に開示されたものである。前記米国特許第４，４６４，６５０号の方法は入力データの記号のストリームを記号の適応増大する列に分解する。前記特許第４，４６４，６５０号の方法は、入力文字ごとに多数のＲＡＭサイクルを必要として、圧縮および伸長を行うために乗算および除算のような時間のかかる複雑な数学的手順を用いるという欠点をもっている。これらの欠点は、前記特許第４，４６４，６５０号の方法を多くの経済的で高性能の装置として実現するのに不適当にする傾向がある。前述のことから従来技術も前記米国特許第４，４６４，６５０号の方法も高性能のアプリケーションに適する適応性があり、かつ効率的な圧縮装置および伸長装置を提供しないことがわかる。既知の従来の設計アプローチは、そのような装置には直接には適当ではない。
　したがって、本発明の目的は、前述の新規なデータ圧縮方式によって圧縮された圧縮符号を確実にかつ経済的に元のデータに伸長する方法および装置を提供することにある。
　本発明の他の目的は、前述の新規なデータ圧縮方式によってデータを圧縮し、かつその圧縮された圧縮符号を確実にかつ経済的に元のデータに伸長するデータ圧縮伸長方法および装置を提供することにある。
　本発明は、上述の装置の欠点を、良好な圧縮比を達成する経済的で高性能で適応性があり、可逆的なデータ圧縮装置によって圧縮されたデータを伸長する装置と方法を提供することによって克服する。本発明の伸長装置に入力される圧縮データは圧縮装置によって入力データ・ストリームからパース（構文解析して分解すること）されたデータ文字信号のストリングを格納（ストア）し、そのストリームとの最長一致を決めるために、そのストリームを格納されたストリングと比較してデータ文字信号のストリームを探索（サーチ）することによって、データ文字信号のストリームを符号信号の圧縮されたストリームに圧縮する。この圧縮装置はまた、データ文字信号のストリームからの最長一致を含み最長一致に続く次の一つのデータ文字信号によって拡張された拡張ストリングを格納する。最長一致を拡張して格納するとき、格納された拡張ストリングに対応する符号信号がそれに割当てられる。符号信号の圧縮されたストリームは、格納された最長一致に対応する符号信号で作られる。データ文字の格納されたストリングが接頭部ストリングと拡張文字で構成される。ストリングがその接頭部ストリングに対応する符号信号によって格納される。
　本発明によれば、符号信号の圧縮されたストリームは、接頭符号信号および拡張文字信号を含む文字ストリングを構成して格納することによって伸張される。さらに詳しくいえば、本発明においては、符号信号を逐次に受け、受けた符号信号が単一文字に対応するかどうかを決定し、受けた符号信号が単一文字に対応する場合は、該単一文字を出力し、受けた符号信号が単一文字に対応しない場合は、ストリングテーブルの中に該符号信号を少なくともデータ文字信号の接頭部ストリングと一つの拡張文字信号として記憶し、次に、前記ストリングテーブルを探索して、受けた符号信号の最終文字信号を抽出し、前記受けた符号信号の接頭部ストリングについて前記ストリングテーブルを探索して該接頭部ストリングに対応するデータ文字ストリングの最終文字信号を抽出し、この操作を次々の接頭部ストリングが単一文字を表す符号信号になるまで繰返し、前記受けた符号信号について抽出された文字ストリングの順序を逆にし、抽出された順序を逆にされた文字ストリングを出力することによって圧縮されたディジタルデータ信号を伸張する。
　データ文字信号のストリングは、各探索繰返しに対する限られた数のハッシュアドレスを与える限定探索ハッシング技術によって記憶装置に入れられる。
　本発明の第１の形態は、データ文字ストリームにおける、データ文字ストリングに対応する圧縮された符号信号ストリームから、当該データ文字ストリームを復元するデータ伸長方法において、前記圧縮された符号信号ストリームを受信するステップと、前記圧縮されたストリーム中の受信した符号信号から対応するデータ文字ストリングを取り出すステップであって、前記圧縮されたストリーム中の受信した符号信号を用いて、前記圧縮されたストリーム中の前記受信した符号信号に対応するデータ文字ストリングをストアするメモリから、対応するデータ文字ストリングを検索するステップを含むステップと、取り出されたデータ文字ストリングを用いて前記データ文字ストリームを復元するステップと、前記取り出すステップに応答して、拡張されたストリングを前記メモリにストアすることによって、前記圧縮されたストリーム中の前記受信した符号信号に応答してデータ文字ストリングを前記メモリに供給するステップとを具え、前記圧縮されたストリーム中の対応する受信した符号信号から取り出されたデータ文字ストリングを、前記圧縮されたストリーム中の次に続く受信した符号信号から取り出されたデータ文字ストリングの第１文字と連結させて、拡張されたストリングを形成し、および拡張されたストリングの各々を、前記圧縮されたストリーム中の対応する符号信号を用いて、前記メモリから検索可能な形態で、前記メモリにストアし、それにより前記圧縮された符号信号ストリームにより、前記メモリから対応するデータ文字ストリングを取り出し、および前記圧縮されたストリーム中のこれらの符号信号によって、その取り出しに応答して、前記拡張されたストリングを前記メモリに生成し、およびストアすることにより、前記圧縮されたストリーム中の後続の対応する符号信号に対するデータ文字ストリングを取り出すのに用いることを特徴とする。
　ここで、前記圧縮された符号信号ストリームは、前記データ文字ストリーム中のデータ文字を探索して、割り当てられた符号信号を持つデータ文字ストリングとの最長一致を決定して生成されたものに対応し、決定された最長一致に対応する符号信号を用いて前記圧縮されたストリームを生成し、および各決定された最長一致を、データ文字ストリームにおいて次に続く文字と連結させて、最長一致を決定するために用いるデータ文字ストリングを供給することを特徴とする。
　ここで、前記対応するデータ文字ストリングを取り出すステップは、前記圧縮されたストリーム中の受信した符号信号が最初にストアされた文字に対応するか否かを決定し、対応する場合は、当該文字を、取り出したデータ文字ストリングとして用いるステップを含むことを特徴とする。
　ここで、複数の予め定めたストリングを最初にストアし、および前記圧縮されたストリームを伸長する前に、対応する符号信号を前記複数の予め定めたストリングに割り当てるステップを含むことを特徴とする。
　ここで、最初にストアされた予め定めたストリングは、前記データ文字ストリーム中の個別の文字に対応するストリングを含むことを特徴とする。
　ここで、前記圧縮されたストリーム中の受信した符号信号を用いて前記メモリをアドレス指定して対応するデータ文字ストリングを検索し、前記拡張されたストリングの前記データ文字ストリング部分を、そのデータ文字ストリングに対応する前記圧縮されたストリーム中の符号信号を用いて供給することを特徴とする。
　ここで、前記圧縮されたストリーム中の符号信号に応答して前記メモリから逆の順序でデータ文字ストリングを検索し、および検索されたデータ文字を反転させて、検索に用いた前記圧縮されたストリーム中の符号信号に対応するデータ文字ストリングを生成するステップを含むことを特徴とする。
　また本発明の第２の形態は、データ文字ストリームにおける、データ文字ストリングに対応する圧縮された符号信号ストリームから、当該データ文字ストリームを復元するデータ伸長装置において、前記圧縮された符号信号ストリームを受信する手段と、前記圧縮されたストリーム中の受信した符号信号に応答して、対応するデータ文字ストリングを取り出す手段であって、前記圧縮されたストリーム中の受信した符号信号に応答して、前記圧縮されたストリーム中の前記受信した符号信号に対応するデータ文字ストリングをストアするメモリから、対応するデータ文字ストリングを検索する手段を含む手段と、取り出されたデータ文字ストリングを用いて前記データ文字ストリームを復元する手段と、取り出されたデータ文字ストリングに応答して、拡張されたストリングを、前記メモリにストアすることによって、前記圧縮されたストリーム中の前記受信した符号信号に応答してデータ文字ストリングを前記メモリに供給する手段とを具え、前記圧縮されたストリーム中の対応する受信した符号信号から取り出されたデータ文字ストリングを、前記圧縮されたストリーム中の次に続く受信した符号信号から取り出されたデータ文字ストリングの第１文字と連結させて、拡張されたストリングを形成し、拡張されたストリングを、それぞれ、前記圧縮されたストリーム中の対応する符号信号を用いて、前記メモリから検索可能な形態で前記メモリにストアし、それにより前記圧縮された符号信号ストリームにより、前記メモリから対応するデータ文字ストリングを取り出し、および前記圧縮されたストリーム中のこれらの符号信号によって、その取り出しに応答して、前記拡張されたストリングを前記メモリに生成し、およびストアすることにより、前記圧縮されたストリーム中の後続の対応する符号信号に対するデータ文字ストリングを取り出すのに用いることを特徴とする。
　ここで、前記圧縮された符号信号ストリームは、前記データ文字ストリーム中の連続データ文字を探索して、割り当てられた符号信号を持つデータ文字ストリングとの最長一致を決定して生成されたものに対応し、決定された最長一致に対応する符号信号を用いて前記圧縮されたストリームを生成し、および各決定された最長一致を、データ文字ストリームにおいて次に続く文字と連結させて、最長一致を決定するために用いるデータ文字ストリングを供給することを特徴とする。
　ここで、前記対応するデータ文字ストリングを取り出す手段は、前記圧縮されたストリーム中の受信した符号信号が最初にストアされた文字に対応するかを決定し、対応する場合は、当該文字を、取り出したデータ文字ストリングとして用いることを特徴とする。
　ここで、複数の予め定めたストリングを最初にストアし、および前記圧縮されたストリームを伸長する前に、対応する符号信号を前記複数の予め定めたストリングに割り当てる手段を含むことを特徴とする。
　ここで、最初にストアされた予め定めたストリングは、前記データ文字ストリームの個別の文字に対応するストリングを含むことを特徴とする。
　ここで、前記メモリは、前記圧縮されたストリーム中の受信した符号信号に応答して対応するデータ文字ストリングを検索し、前記拡張されたストリングの前記データ文字ストリング部分を、そのデータ文字ストリングに対応する前記圧縮されたストリーム中の符号信号を用いて供給することを特徴とする。
　ここで、前記圧縮されたストリーム中の符号信号に応答して前記メモリから逆の順序でデータ文字ストリングを検索し、および検索されたデータ文字を反転させて、検索に用いた前記圧縮されたストリーム中の符号信号に対応するデータ文字ストリングを生成する手段を含むことを特徴とする。
　また本発明の第３の形態は、入力されたデータ文字ストリームを圧縮して圧縮された符号信号ストリームにし、および前記符号信号を用いて、前記圧縮されたストリームを伸長して前記データ文字ストリームを復元する方法において、前記データ文字ストリームにおけるデータ文字を探索し、データ文字ストリングに関連する符号信号を有する第１メモリにストアされたデータ文字ストリングとの最長一致を決定するステップと、最長一致が決定されたデータ文字ストリングに対応する符号信号を用いて、前記圧縮されたストリームを生成するステップと、拡張されたストリングを前記第１メモリにストアし、およびそれに関連した符号信号を割り当てて、最長一致を決定するために用いるデータ文字ストリングを供給するステップであって、最長一致を構成するデータ文字を、前記データ文字ストリーム中の次の文字と連結して、拡張されたストリングを形成するステップとを具えて前記入力されたデータ文字ストリームを圧縮し、および前記圧縮されたストリーム中の符号信号から対応するデータ文字ストリングを取り出すステップであって、前記圧縮されたストリーム中の前記符号信号に対応するデータ文字ストリングをストアする第２メモリから、前記圧縮されたストリーム中の符号信号を用いて、データ文字ストリングを検索するステップを含むステップと、取り出されたデータ文字ストリングを用いて前記データ文字ストリームを復元するステップと、前記取り出すステップに応答して、拡張されたストリングを第２メモリにストアすることによって、前記圧縮されたストリーム中の前記符号信号に対応して、データ文字ストリングを前記第２メモリに供給するステップとを具え、前記圧縮されたストリーム中の対応する符号信号から取り出されたデータ文字ストリングを、前記圧縮されたストリーム中の次に続く符号信号から取り出されたデータ文字ストリングの第１文字と連結させて、拡張されたストリングを形成し、および拡張されたストリングを前記圧縮されたストリーム中の当該拡張されたストリングに対応する符号信号を用いて、前記第２メモリから検索可能な形態で、前記第２メモリにストアし、それにより前記圧縮された符号信号ストリームにより、前記第２メモリから対応するデータ文字ストリングを取り出し、および前記圧縮されたストリーム中のこれらの符号信号によって、その取り出しに応答して、前記拡張されたストリングを前記第２メモリに生成し、およびストアすることにより、前記圧縮されたストリーム中の後続の対応する符号信号に対するデータ文字ストリングを取り出すのに用いることにより、前記符号信号を用いて、前記圧縮されたストリームを伸長して前記データ文字ストリームを復元することを特徴とする。
　ここで、最初に、複数の同様の予め定めたストリングを前記第１および第２メモリの各々にストアし、符号信号を割り当てるステップを含むことを特徴とする。
　ここで、最初にストアされた予め定めたストリングは、前記データ文字ストリーム中の個別の文字に対応するストリングを含むことを特徴とする。
　また本発明の第４の形態は、データ文字ストリームを圧縮して圧縮された符号信号ストリームにし、および前記符号信号を用いて、前記圧縮されたストリームを伸長して前記データ文字ストリームを復元する装置において、前記入力されたデータ文字ストリームを圧縮する装置と、前記圧縮されたストリームを伸長する装置とを具備し、前記圧縮する装置は、前記データ文字ストリームにおけるデータ文字を探索し、データ文字ストリングに関連する符号信号を有するデータ文字ストリングとの最長一致を決定する手段と、前記データ文字ストリングをストアする第１メモリと、最長一致が決定されたデータ文字ストリングに対応する符号信号を用いて、前記圧縮されたストリームを生成する手段と、拡張されたストリングを前記第１メモリにストアし、およびそれに関連した符号信号を割り当てて、最長一致を決定するために用いるデータ文字ストリングを供給する手段であって、最長一致を構成するデータ文字を、前記データ文字ストリーム中の次の文字と連結して、拡張されたストリングを形成する手段とを具え、前記伸長する装置は、前記圧縮されたストリーム中の前記符号信号に対応するデータ文字ストリングをストアする第２メモリと、前記圧縮されたストリーム中の符号信号から対応するデータ文字ストリングを取り出す手段であって、前記第２メモリから、前記圧縮されたストリーム中の符号信号を用いて、データ文字ストリングを検索する手段と、取り出されたデータ文字ストリングを用いて前記データ文字ストリームを復元する手段と、取り出されたデータ文字ストリングに応答して、拡張されたストリングを前記第２メモリにストアすることによって、前記圧縮されたストリーム中の前記符号信号に対応して、データ文字ストリングを前記第２メモリに供給する手段とを具え、前記圧縮されたストリーム中の対応する符号信号から取り出されたデータ文字ストリングを、前記圧縮されたストリーム中の次に続く符号信号から取り出されたデータ文字ストリングの第１文字と連結させて、拡張されたストリングを形成し、および拡張されたストリングを前記圧縮されたストリーム中の当該拡張されたストリングに対応する符号信号を用いて、前記第２メモリから検索可能な形態で、前記第２メモリにストアし、それにより前記圧縮された符号信号ストリームにより、前記第２メモリから対応するデータ文字ストリングを取り出し、および前記圧縮されたストリーム中のこれらの符号信号によって、その取り出しに応答して、前記拡張されたストリングを前記第２メモリに生成し、およびストアすることにより、前記圧縮されたストリーム中の後続の対応する符号信号に対するデータ文字ストリングを取り出すのに用いることを特徴とする。
　ここで、最初に、複数の同様の予め定めたストリングを前記第１および第２メモリの各々にストアし、符号信号を割り当てる手段を含むことを特徴とする。
　ここで、最初にストアされた予め定めたストリングは、前記データ文字ストリーム中の個別の文字に対応するストリングを含むことを特徴とする。
　【実施例】
　本発明はデジタルデータ文字信号のストリームまたは列を圧縮して、圧縮されたディジタル符号信号の対応するストリームを与えるデータ圧縮装置を備えている。例えば、圧縮される予定のデータは、英語の原文資料、格納されたコンピュータ記録などを含んでいてもよい。今日のデータ処理装置および通信装置においては、圧縮を行われるはずのアフファベットの文字は、処理されてＡＳＣＩＩフォーマットのような都合のよいコードで２進数字のバイトとして伝達されることがわかっている。例えば、入力文字を８ビット・バイトの形式で２５６文字の文字体系全体を受けることができる。圧縮装置からの圧縮符号信号は、例えば、記録保管の目的のために電子記憶ファイルに格納されるか、または伸長を行う遠隔の場所に伝送されてもよい。このほかに、ディスク記憶装置のような電子記憶ファイルが入力電子回路に圧縮装置を備え、出力電子回路に伸長器を備えることができ、それによってファイルに入るすべてのデータを記憶するために圧縮して、ファイルから検索されたすべてのデータを利用機器に伝送する前に伸長する。前述の従来の圧縮装置および伸長装置は、圧縮および伸長のそのような用途に適合させる性能または適応性を与えない。本発明に従って実施された高性能適応装置をそのように用いることができる。
　多数の設計オプションが被圧縮データおよび装置の所望の特性に従う種々の組合せで本発明の実施例に用いることができる。発明の三つの実施例を以下に説明する。一つの実施例は、最高性能を与えるオプションを組合せており、第２の実施例は、最高圧縮を与えるオプションを組合せており、第３の実施例は、最高性能実施例のプログラムされたコンピュータの例を提供する。
　本発明の伸長装置に入力される圧縮データ信号を生成する圧縮装置は、データ文字の入力ストリームをストリングまたはセグメントにパースして、各ストリングを識別する符号信号を伝送する。圧縮装置が初めて遭遇したデータ文字以外は、各パースされたストリングは、前に認識されたストリングに対する最長一致を含んでいる。圧縮装置は、認識されたストリングに対応する符号信号を伝送する。１ストリングの文字が入力ストリームからパースされると、パースされたストリングは、入力ストリームにおいて次に発生する文字によって拡張され、あとで符号化に利用されるために圧縮装置において符号化され、そこに記憶される拡張ストリングを形成する。従って認識されている文字シーケンスは、１ブロックのデータを圧縮する過程で統計的情報を集めるとき、平均長さがたえず大きくなっている。拡張文字は、次のパーシング繰返しにおける最初の文字として用いられる。パーシングは、データを１回通すだけで達成され、初めの文字から出発して、１回の１文字を分離する。従って、単一文字のストリング以外は、各ストリングは、前に記憶されたストリングと一致する接頭部ストリングと拡張文字として記憶される。そのストリングは、そのような各ストリングを接頭部の符号信号表現と拡張文字の実際の表現または暗示表現を一緒にして記録するのが都合よい。パーシングは、データ・ストリームの各文字間に仮想コンマを挿入し、それによってパースされたストリングまたはセグメントを区切るものとして概念化できる。従って、本発明においては、一致を得るための未処理のデータストリームの探索は、先に観察されたストリングとの最長一致を見出すために一つのコンマから次に続くコンマを一文字越えたところまでを探索することを含む。
　図１を参照すると、データ文字のストリームの一部分の略図が示されており、そこではＸがアルファベットの任意の文字を表している。コンマは、パーシングを表すためにのみデータストリーム中に示されている。このデータストリームのストリング１が仮想コンマ２および３によってパースされている。ストリング１は前のストリング１´に一致し、ストリング１′はコンマ２に続く入力データストリームに一致するコンマ２に先行した最長拡張ストリングである。ストリング１′は、前に符号化されたものであるから、その符号は、ストリング１に遭遇したとき圧縮装置によって伝送される。次いで圧縮装置は、接頭部ストリング１と拡張文字５を含む拡張ストリング４を符号化して記憶する。拡張文字は、それがどんな文字であるかに関係なく、接頭部１に続くデータストリームの中の次の文字である。すなわち、拡張文字５は、前に、データストリームの中で現れた文字であってもよいし、またはそれは初めて遭遇するアルファベットの１文字であってもよい。
　圧縮装置は、もう一度最長一致が達成されるまで拡張文字５で始まる次のパーシングの繰返しを仮想コンマ３のところで開始する。このようにして、前に拡張されたストリング６′にマッチするストリング６がパースされる。前の繰返しにおけると同じようにまた、ストリング６′に対する符号信号は、伝送され、ストリング６は後続の文字によって拡張され、拡張されたストリングは、符号化されて記憶される。続くパーシング繰返しにおいては、符号化されて記憶されたストリング４にマッチするストリング７がパースされる。このパーシング繰返しで伝送された符号信号は、拡張ストリング４に割当てられたものである。
　上述のように、圧縮装置によって与えられた符号信号を受けた伸長装置は、符号化接頭部ストリングと拡張文字の形でデータを記憶する。従って、伸長装置は、一つの受信符号信号と一つの拡張文字を含むエントリーを記憶装置内に構成する。例えば、続けて図１を参照すると、伸長装置がストリング１に関連した符号信号を受けると、その伸長装置が前にストリング１′を構成して記憶しているので、そのストリングを構成する文字が、以下に詳細に説明する方法で、再構成される。次に続く繰返しにおいて、伸長装置がストリング６に関連した符号信号を受けると、そのストリングを構成する文字が検索される。この時点で、伸長装置は、ストリング１からの符号信号を受け取って拡張文字５を検索しているので、以下に詳細に説明する方法でストリング４を構成して記憶できる。
　本発明において、入力バイトの各シーケンスが実施例次第で固定長または可変長のものであってもよい符号信号に圧縮される。上述のように、各入力バイト列は、各符号識別子を割当てられ、一つの列が入力データ・ストリームの中で再び出てくるときはいつも、同じ識別子が再び伝送される。各１バイト列が各符号を割当てられ、一つの列が再び出てくるときはいつも、１バイトだけ拡張され、新しい符号が拡張されたシーケンスに割当てられる。概念的には、圧縮装置は、各データブロックを格納されたセット内のゼロストリングのみから開始する。圧縮装置は、新しい文字が出てくるたびにそのセットに１文字のストリングを入れ、次にこれらの記憶された１文字ストリングをさらに長いストリングを形成するのに用いる。各ストリングがそのセットに加えられると、それは、一つの符号信号を割当てられる。入力からの一つの文字ストリングがセット内で見出される度に、次の入力文字がそのストリングに追加され、拡張されたストリングがそのセットの中にあるかどうかを決めるためにそのセットが探索される。拡張されたストリングが既に存在しなければ、そのストリングがセットに入れられる。随意選択的に、そのストリングセットをすべての単一文字ストリングを含むように初期設定できる。これは、より高い性能の装置として実現できるようににすることもあるが、ある程度の圧縮効率を失うことがある。圧縮装置からの出力符号信号は、同一文字列が以前に起こったことを示しているものとして考えることができる。
　前記米国特許第４，４６４，６５０号のデータ圧縮および伸長装置において、拡張文字が各認識された列に追加されて拡張された列が符号化された。拡張列の符号化表現は、それの圧縮符号として圧縮装置によって伝送された。その代りに、本発明の圧縮装置は、拡張列を記憶して、認識された列に対する符号を伝送する。認識された列は、拡張列の接頭部である。記憶された拡張列は、次にあとで符号化するために用いられる。前記米国特許第４，４６４，６５０号の方法をこのように変更すると、前記米国特許第４，４６４，６５０号において用いた時間のかかる、やっかいな数学的操作および乗算・除算装置のような付随のハードウェアをなくすことによってデータ圧縮および伸長装置を著しく簡単にすることができる。この変更は、装置の性能を著しく高めると同様にまた、普通に遭遇するデータの場合の圧縮効率を増加させる。これは、前記米国特許第４，４６４，６５０号の装置では、圧縮された符号信号の一部分として伝送される拡張文字が等しく起こりそうな文字体系のすべての記号に見合った多数のビットを含むからである。本発明では、拡張文字は、次の圧縮ストリング符号の一部分として伝送されるので、文字の各ストリングについて行われた圧縮に一致して必要とするビットの数が少なくなる。
　本発明は、限定探索長の計算されたアドレス・ハッシング装置を用いて各ストリングをストリング・テーブルに入れ、そのストリング・テーブル内で各ストリングを探索する。ハッシング関数は、前の符号信号と拡張文字とからなるハッシュ・キーを用いてＮ個のハッシュ・テーブル・アドレスの組を与える（ここでＮは普通１ないし４である）Ｎ個のＲＡＭ記憶場所は、逐次に探索され、その項目がＮ個の記憶場所になければ、それはそのテーブル内にないと考えられる。圧縮のときに、テーブルに挿入されるべき新しいキーをＮ個の割当て場所に受入れできなければ、それはテーブルから除外される。この限定探索ハッシング法は、圧縮効率をわずかに下げるが、装置として実現するのを非常に簡単にする。Ｎ個のハッシュ・アドレスが反復したＲＡＭの中で並列に探索される別の実施例を用いてもよい。
　本発明は、固定長または可変長の圧縮された符号信号を用いて装置として具体化することができる。固定長符号信号の実施例は、圧縮効率においてわずかの損失を伴いながら装置として実現する場合の簡単化をもたらす。固定長符号実施例は、ＲＡＭのスペース必要度と可変符号長による装置としての実現に必要な符号シフティング機構の複雑さを小さくする傾向がある。しかし固定長符号による装置の実現は非常に高い性能の装置の実現を行うときに望ましい。
　一般には、本発明は、入力文字信号の可変ストリングを出力符号記号信号に写像することによって圧縮を行う。圧縮装置は、ストリング・テーブル（ＲＡＭ）の中に圧縮装置が認識するストリングのリストを記憶し、各ストリングに対しては対応する出力符号信号を記憶する。そのように記憶されたストリングの組は、どんな一連の入力文字も記憶されるストリングにパースでき、従って、出力符号に写像できるように構成される。パーシングは、どの繰返しにおいてもストリング・テーブルの中に最長ストリングに一致するすべての連続する入力文字を使いきり、対応する出力符号を伝送することによって達成される。最長一致は、次の入力文字によって拡張され、ストリング・テーブルに記憶され、そして対応する符号を割当てられる。
　従って、ストリング・テーブル内のストリングの組を合成することは、現在のデータブロックの統計に適応し、かつその統計の一つの表現法である。明確にいえば、そのストリングの組に追加される各ストリングは、その組に既にある一つのストリングを１文字で拡張したものである。一つのストリングがそのセットに加えられるのは、それが実際に入力データにおいて観測されたのちにおいてである。従って、一つの長いストリングがそのセット内に現れる可能性のあるのは、それが何度も出てきたので頻繁に再び現れると期待できる場合だけである。このストリングセットは、できればランダムアクセス記憶装置（ＲＡＭ）にテーブルとして記憶されるのがよい。各ストリングは、連結トリー構造と考えてもよいものに記憶される。各ストリングは、少なくとも暗黙的にすなわち間接的に、その符号記号、そのストリングの最後の文字および最後の文字以外のすべてのストリング文字を含むストリング接頭部の符号記号で記憶される。各文字が個別に得られ、かつ各接頭部符号が逐次に呼び出されるので、伸長装置は、一つのストリングを複合するときに多重ＲＡＭアクセスを用いる。
　各データ信号は、入力文字列に対する最長一致を探すのを容易にするようなやり方でストリング・テーブル内に記憶される。各入力文字が読まれると、それが既に認識された一つのストリング（新しい列の始めにゼロストリングで始まったもの）に付け加えられて、その新しいストリングは、それがそのテーブルの中にあるかどうかを決めるために検査される。新しいストリングがそのテーブルの中にあれば、その符号が検索されて、その処理が新しい文字と新しい符号とで繰返される。それらのストリングをそのように呼び出すために、それらのストリングは、“接頭部符号、拡張文字”の組（タブル）によって識別されるのが都合よい。限定探索ハッシング装置がストリング・テーブルをくまなく探索するのに用いられる。
　本発明を実施する際に用いることのできるハッシング装置は、一つの符号、文字組合わせに対して一連の記憶アドレスを発生する関数
　　　　　ハッシュ（符号、文字）→アドレス１，アドレス２・・・
を含む。テーブルに一つのストリングを挿入すると、発生したＲＡＭアドレスが空サイトを発見するまで逐次に呼出され、項目がその点に挿入される。一つの項目を検索するとき、同じアドレス列がその項目が発見されるかまたは空サイトが発見されるまで呼出され、空サイトが発見された場合にその項目はテーブルの中に存在しないと定義される。各占有されたサイトにおいては、そのストリングのための識別用符号、文字の組は、そのサイトを占有するものが所望の項目であるかどうかを決めるために比較されてもよい。あとで説明する理由によって、識別用符号を比較することは、実際には、この実施例で必要なだけである。
　本発明で用いられたハッシュ関数においては、取り出されて用いられたアドレスの数は、小さな一定値Ｎ（Ｎは普通１ないし４である）に限定される。一つの項目をＮ回の呼出しでストリング・テーブルに挿入できなければ、その項目は用いられない。テーブルから検索される予定の一つの項目がＮ回の呼出しの中で所在をつきとめられなければ、それはテーブル内にないと定義される。この限定探索の特徴は、圧縮効率の小さな損失をもたらすが、性能を著しく増加させる。本発明はＢビット・バイトの文字体系について圧縮を行うとして説明する。本発明を実施する際に用いられるハッシュ関数は、任意の一つの符号に関連したアドレスの組すなわち２Ｂ拡張文字すべてに対するＮ個のアドレスすべてがどのアドレスをも２回は含まない。従って、一つのアドレスが特定の符号、文字の組に対してアクセスされると、その符号の比較はその記憶場所の占有物の識別を行うのに十分である。その文字の値をＲＡＭに記憶する必要はない。従って、ＲＡＭのスペースは、ハッシュ関数のこの特徴のために保存される。なお、ハッシュ関数は、符号または文字の連続する値を異常なほど激しく使ってもどの特定のアドレスの組をも使い過ぎることにはならないように設計される。これは同じ最初のアドレス値をもつ任意の二つの符号、文字の組が同じ第２のアドレス値をもたないことを確実にすることが可能であれば、それによって達成される。ハッシュ関数によって作られた幾つかのアドレスを、二つの全く同じＲＡＭを同時に探索して装置の性能をさらに高めることができるように並列に与えてもよいことが分かるであろう。上記の基準を満足する多くのハッシュ関数が本発明を実施するのに満足に機能することになる。特定の適当なハッシュ関数を以下に説明する。上記の基準を満足する他のハッシュ関数を通常のやり方で導出できることがわかる。
　以下に説明する本発明の実施例において、圧縮装置からの出力符号信号は、Ｃビットの公称語長（２Ｃはストリング・テーブルの大きさ以下である）をもつことになる。しかし、ストリング・テーブルが最初に構成されようとしているとき、各ストリングを１回の繰返しの間に利用できるものから選択するためには、Ｃより少ないビットを必要とする。最高の圧縮は、漸新的に大きくなる出力符号をＣビットの限界まで伝送する場合に達成される。このアプローチは、可変符号を固定バイト配向に整列させるのに追加の出力ハードウェアを用いる。出力語長はまた新しい入力文字の認識に従って変わることがある。以下に説明する実施例の一つにおいて、一つの入力文字がまず出てくると常に、その文字そのもののビットパターンがあとに続くゼロ・ストリング符号が与えられる。従って、これらの出力は正規のストリング符号よりいくらか長い。あとで説明するようにして、出力長のこの変動は、入力データを処理する前にすべての単一文字ストリングを含むようにストリング・テーブルを初期設定することによって避けられる。このアプローチは、それがそうでない場合に必要な任意のビット・シフト・ハードウェアをなくすが、圧縮を小さくすることがある点で装置としての具体化の複雑性を簡単にする。圧縮の低減は、未使用の単一文字に割当てられた符号が有益に用いられ得ないが、すべての割当てられた符号を区別するのに必要なビットの数を大きくするので起こる。この圧縮の低減は、可変長符号を利用する初期ストリングの圧縮の間に起こるだけである。
　以下に説明する発明の諸実施例において、伸長プロセスで用いるストリングテーブルは、圧縮プロセスの場合と論理的に同じであるが、いくらか異なって記憶される。各符号信号を伸長装置によって受けるとき、それが接頭部ストリング符号と拡張文字とに翻訳されるストリング・テーブル内で直接に探される。次に接頭部符号が探されて翻訳され、その処理が空ストリングに出合うまで繰返される。しかしこの処理は、その文字ストリングを圧縮装置によって受けた順次配列と逆の配列になっているデータ文字を発生する。ストリング内文字列を逆にする二つの技術を以下に説明する。ＬＩＦＯスタック（後入れ先出し）が各文字を一時保持するのに用いられ、各文字が伸長装置によって発生されると、それはスタックの上に押し上げられる。反復の終りには、各文字が正しい順序でスタックから読出される。別のやり方として、一つのストリング長さカウントがストリングテーブル内の各符号に対して維持されて一つの文字を読み出すとき、それをランダム・アクセス出力バッファ内の適当な位置に直接置くことができるようにしている。
　図２および図３は本発明の最高性能の実施例を実現する圧縮装置および伸長装置をそれぞれ示している。この実施例は、経済的で高速な圧縮処理を与える。Ｂビットの文字の大きさおよびＣビットの圧縮符号の大きさが用いられる。ストリング・テーブルは、２Ｃの記憶場所を含む。普通には、Ｂは、８ビットであり、Ｃは、１２ビットで、他の文字および符号の大きさをこの発明を実施するのに利用できるようにしている。この実施例は、ハッシュされたストリング・テーブル内のストリング記述項のアドレスとして用いられるＣビットの固定長符号記号信号を用いる。最初の２Ｂ記憶場所は、各単一文字ストリングを含むように初期設定される。この圧縮装置は、各記述項にＣビットの接頭部ストリング符号だけを含むストリング・テーブルを用いる。伸長テーブルは、この同じ符号とそのほかに現在のストリングを合成するのに接頭ストリングに追加されるＢビットの拡張文字を含む。
　圧縮装置からの出力符号記号信号として用いられるストリング・テーブルに入るアドレスは、図２および図３の実施例の説明の次に詳細に説明するハッシュ関数を用いて得られる。ハッシュ関数は、Ｎ個のＣビット・アドレスを順次に発生する。図２および図３の実施例は、図４および図５の実施例とともに以下に説明する多数の機能を制御する制御装置を用いる。例えば、ハッシュ関数装置は、Ｎ番目のアドレスが発生したときに制御装置に知らせる。本発明のハードウェア実施例は、順次状態機械（シーケンシャル・ステート・マシーン）として実現され説明される。圧縮装置の制御装置は、それらの種々のブロックから信号を受けて、機械の現存の状態に従って圧縮装置の構成要素を制御するためにそれらへ信号を与える。説明した各シーケンスを制御するのにどんな標準制御論理装置をも利用できる。例えば、１状態ごとに１フリップ・フロップを付勢して、各状態の間実行されるべき演算上の接続および機能を区別し、その状態を制御するフリップ・フロップをその状態の間付勢してもよい。
　次に図２を参照すると本発明の伸長装置への圧縮入力符号信号を発生する最高性能の実施例の圧縮装置が示されている。この圧縮装置は、バス１０に入力文字信号を受けてバス１１に圧縮出力符号信号を与える。入力文字は外部装置からバス１０に与えられる。外部装置は、また入力文字信号がその外部装置から利用でき、バス１０に加えられるときにつねに、データ利用可能信号をライン１２に与える。ライン１２上のデータ利用可能信号は、圧縮装置制御装置１３に加えられる。圧縮装置制御装置１３は、図２の圧縮装置のブロックのすべてにリード１４を経て制御信号を与える。圧縮装置制御装置１３は、図２の圧縮装置を制御状態を介して以下に詳細に説明するような方法で順序付けする。制御装置１３はまた、追加の入力文字を要求するためライン１５を通して外部装置に文字ストローブ信号を与える。出力符号信号がバス１１の上で利用できるとき、制御装置１３は、符号ストローブ信号をリード１６を通して外部装置に与える。
　バス１０の上の入力文字は、Ｂビット文字レジスタ１７に入れられる。単一文字ストリング符号を作るために、文字レジスタ１７からのＢビット文字バイトは、バス１８を経てＣビット符号番号レジスタ１９のＢ個の下位ビットに挿入される。符号番号レジスタ１９の高位桁のＣ−Ｂビットをリード２０の上の制御信号を用いてゼロにセットできる。
　レジスタ１９からの符号記号信号およびレジスタ１７からの文字信号は、それぞれバス２１および２２を経てハッシュ関数回路２３に加えられる。ハッシュ関数回路２３は、バス２１の上のＣビット符号信号をバス２２の上のＢビット文字と結合してバス２４の上にＮ個のＣビット・アドレスを逐次に与える。ハッシュ関数回路２３は、バス２４を通して与えられたハッシュアドレスがそのシーケンスのＮ番目のアドレスであるかどうかをリード２５を経て制御装置１３に知らせる。
　ハッシュ関数回路２３はまた、制御装置１３から「新ハッシュ」指令および「次のハッシュ」指令を受ける。制御装置１３は、ハッシュ関数回路２３に指令して「新ハッシュ」指令に応答するＮ個のハッシュ・アドレスの最初のものおよび「次のハッシュ」指令が相次いで発生するのに応答して相次ぐハッシュ・アドレスを与える。既に説明したように、ハッシュ関数回路２３がＮ番目のハッシュ・アドレスを与えたとき、一つの信号がリード２５を介して制御装置１３に戻される。
　バス２４の上のハッシュ・アドレスは、２Ｂに等しい一定値信号をも受ける比較器２６に加えられる。比較器２６は、バス２４の上のハッシュ・アドレスを値２Ｂと比較して、バス２４の上のハッシュ・アドレスが２Ｂより大きいかまたは２Ｂ以下であるかどうかを指示する信号をリード２７を介して制御装置１３に与える。
　バス２４の上のハッシュ・アドレスはまた、ＣビットＲＡＭアドレス・レジスタ２８にも加えられる。ＲＡＭアドレス・レジスタ２８にロードされたアドレスは、圧縮装置ストリング・テーブルを記憶するのに用いられるＲＡＭ２９を呼出す。ＲＡＭ２９は、２ＣのＣビット記憶場所を含んでいる。各ストリングは、そのストリングに割当てられた符号によってアドレス指定された記憶場所にあるその接頭符号を記憶することによってＲＡＭ２９の中に記憶される。そのストリングに割当てられた符号は、後述のようにして、ストリング拡張文字と接頭部符号をハッシュすることにより得られる。
　ＲＡＭ２９は、「読出し」指令および「書込み」指令を制御装置１３から受けてＲＡＭ２９の「読出し」、「書込み」機能を制御する。ＲＡＭ２９は、２Ｂに等しいＣビットの値またはＣビット符号番号信号をレジスタ１９からバス３０を介して受取るように制御装置１３によって制御される。
　「書込み」指令をＲＡＭ２９に加えるのに従って、一定値２Ｂまたはバス３０の上の符号番号のいずれかが制御装置１３からの制御信号に従ってレジスタ２８の中のＲＡＭアドレスによって呼出された記憶場所に書込まれる。ＲＡＭ２９はまた、「読出し」指令に応答して呼出された記憶場所のＣビット内容をバス３１に与える。バス３１の上のＲＡＭ出力および符号レジスタ１９の出力は、比較器３２へ入力として加えられる。比較器３２はまた、２Ｂに等しい一定値信号を受ける。比較器３２は、ＲＡＭ２９の出力を符号番号レジスタ１９の出力および２Ｂと比較する。比較の結果は、リード３３を経て制御装置１３に与えられる。リード３３の上の比較信号は、バス３１の上のＲＡＭ出力レジスタ１９からの符号番号に等しいか、または２Ｂに等しいか、またはどちらでもないかを制御装置１３に指示する。あとで説明する理由のために、制御装置１３は、ＲＡＭアドレス・レジスタ２８を制御して、その内容をバス３４を経て符号番号レジスタ１９に転送する。
　図２の圧縮装置は、Ｃビット信号をバス３６を経てＲＡＭアドレス・レジスタ２８に与える初期設定計数器３５を備えている。計数器３５はそれに加わるゼロの値をもつ信号を介してゼロにセットできる。制御装置１３は、計数器３５を計数指令を介して制御して、計数指令を加えるごとに計数器の内容に１を加える。計数器３５は、それが計数値２Ｃに達したときを制御装置１３にリード３７の上のキャリアウトまたはオーバフロー信号を経て知らせる。初期設定計数器３５はＲＡＭ２９を初期設定するのに用いられ、ＲＡＭ２９の記憶場所のすべてを逐次に呼出して空状態を指示するように選択された一定値２Ｂを書込むことによって空にする。
　図２の圧縮装置の基本動作を要約すると次の通りである。
　１．各データブロックごとに、ＲＡＭを空に初期設定する。
　２．各バイト・ストリングの最初の文字について：
　　　最初の符号番号として、文字を符号番号レジスタに入れる。
　３．相次ぐ文字について：
　　　ハッシュ（符号、文字）→一連のＮ個のＲＡＭアドレス；各記憶場所ごとにつぎつぎに、
　　　ＲＡＭ出力＝符号番号であれば：ＲＡＭアドレス→符号番号レジスタ；もう一つの文字でこのステップに再び入る。
　　　ＲＡＭ記憶場所が空であれば：符号番号レジスタからＲＡＭに書込み、符号値を出力として伝送する。次にステップ２へ行く。
　　　そうでないときは、すべてのハッシュ・アドレスの後、符号値を出力として伝送する；ステップ２へ行く。
　図２を続けて参照すると、以下のものが図２の圧縮装置の状態機械語記述である。
　状態０：各データブロックの始めにおける待ち状態
　　　　　初期設定計数器をゼロにセット。
　　　　　データ使用可能信号を待つ：次いで状態１へ行く。
　状態１：ＲＡＭを初期設定する
　　　　　初期設定計数器→ＲＡＭアドレス・レジスタ
　　　　　２Ｂ→ＲＡＭデータ入力
　　　　　ＲＡＭを書込む
　　　　　＋１を初期設定計数器に加える
　　　　　初期設定計数器＜２Ｃなら、状態１を繰返す、そうでなければ状態２へ行く。
　状態２：符号を開始するブロックの最初の文字を読出す。
　　　　　文字を符号番号レジスタ（下位Ｂ個のビット）に入力する
　　　　　ゼロを符号レジスタ（上位Ｃ−Ｂ個のビット）に入力する
　　　　　状態３へ行く。
　状態３：このストリングの中の次の文字を処理する
　　　　　次の文字を読出す、
　　　　　使用できる新しい入力文字がなければ：符号番号レジスタの内容を出力に伝送する；状態０へ行く。
　　　　　ハッシュ（符号番号レジスタ、次の文字）→ＲＡＭ
　【外１】
　　　　　ＲＡＭを読出す。
　　　　　（ＲＡＭ出力）＝（符号番号レジスタ）ならば：
　　　　　ＲＡＭアドレス→符号番号レジスタ；状態３へ行く。
　　　　　（ＲＡＭ記憶場所）＝２Ｂならば：状態５へ行く。
　　　　　その他の場合：状態４へ行く。
　状態４：探索を継続する
　　　　　次のハッシュ（符号、文字）→ＲＡＭアドレス
　【外２】
　　　　　その他の場合：状態４を繰返す。
　　　　　ＲＡＭを読出す
　　　　　（ＲＡＭ出力）＝（符合レジスタ）であれば：
　　　　　であれば、
　　　　　ＲＡＭアドレス→符合番号レジスタ；状態３へ行く。
　　　　　（ＲＡＭ出力）＝２Ｂならば：状態５は行く。
　　　　　　その他の場合：最終ハッシュ繰返しであれば：
　　　　　状態６へ行き、そうでなければ状態４を繰返す。
　状態５：新ストリングを作る
　　　　　（符合レジスタ）をＲＡＭに書込む、状態６へ行く。
　状態６：ストリングの終り
　　　　　（符号番号レジスタ）→出力
　　　　　文字レジスタ→符号番号レジスタに（下位Ｂビット）
　　　　　ゼロ＝符号番号レジスタ（上位Ｃ−Ｂ個のビット）、状態３へ行く。
　　　　　上に与えられた状態機械語記述に関する図２の圧縮装置の動作のさらに詳細な説明を次に行う；
〔０〕．
待ち状態
〔１〕．
初期設定状態
〔２〕．
最初の文字の状態
〔３〕．
次の文字状態
　しかし、そのデータブロックの終りに達しないで、新しい文字が利用できて、文字レジスタ１７に入れられたとすれば、このＢビットの文字は、バス２２を経てハッシュ関数回路２３の中ヘバス２１を通して与えられたレジスタ１９の中のＣビットの符号番号と結合される。制御装置１３からの「新ハッシュ」指令の制御を受けて、ハッシュ関数回路２３は、この符号と文字の組合せに対する第１のＲＡＭアドレスを与える。バス２４の上のこのハッシュ・アドレスは、比較器２６によって値２Ｂと比較される。バス２４の上のハッシュ・アドレスが２Ｂ以下であれば、この記憶場所は、呼出し不能で、次のハッシュ・アドレスが「次のハッシュ状態」へゆくことによって選択される。２Ｂ以下のアドレス値は、２Ｂより小さな値が単一文字のストリングに対する符号値であるようにあらかじめ割当てられており、かつ値２Ｂは、空記憶場所（未使用の符号値）を識別するためにあらかじめ割当てられたので、新しい符号値として認められない。
　ハッシュ・アドレスが２Ｂより大きければ（通常の場合）、バス２４の上のハッシュ・アドレスがＲＡＭアドレス・レジスタ２８にゲートされ、ＲＡＭ２９がそのアドレスの内容を読取るように制御される。バス３１の上のＣビットの結果は、比較器３２においてレジスタ１９からの符号値と値２Ｂとの両方に比較される。バス３１の上のＲＡＭ２９の出力がレジスタ１９からの符号番号に等しければ、拡張ストリングは、前に出てきて既に一つの符号値を割当てられており、すなわち丁度読出された記憶場所のＲＡＭアドレス値である。新符号番号はＲＡＭアドレス・レジスタ２８からバス３４を経て符号番号レジスタ１９にゲートされ、新しい文字についての手順を繰返すためにこの「次の文字状態」に再び入る。
　代りにバス３１の上のＲＡＭ出力が２Ｂに等しければ、この記憶場所は、空であり、拡張ストリングがテーブルにないので、入力データをパースするのに利用できないことを意味する。これによって、現在のストリングの構成作業を終りにしてこんどは「新ストリング状態」に入る。
　しかし、バス３１の上のＲＡＭ出力が２Ｂにもまたレジスタ１９からの符号番号にも等しくない場合、ＲＡＭ２９の中の他の記憶場所を探索しなければならず、それは「次のハッシュ状態」において実行される。
〔４〕．
次のハッシュ状態
　しかし、ハッシュ・アドレスが２Ｂより大きければ、バス２４の上のアドレスはＲＡＭアドレス・レジスタ２８にゲートされて、ＲＡＭ２９がその記憶場所において内容を読出すように制御される。ＲＡＭ出力のバス３１の上に与えられた結果は、比較器３２においてレジスタ１９の中の符号番号および２Ｂの両方と比較される。ＲＡＭ出力が符号番号に等しければ、ＲＡＭアドレス・レジスタ２８からの新しい符号番号がバス３４を経てレジスタ１９にゲートされ、「次の文字状態」に入る。この代りに、バス３１の上のＲＡＭ出力が値２Ｂに等しければ、「新ストリング状態」に入る。バス３１の上のＲＡＭ出力が２Ｂおよび符号値のいずれにも等しくなければ、この処理は、この新アドレス値に対するこの「次のハッシュ状態」に再び入ることによってＮ回まで繰返す。ハッシュ関数回路２３からのリード２５の上の信号によって示されているように、Ｎ個の記憶場所が試みられたとき、このストリングは終りにされて「ストリング終了状態」に入る。
〔５〕．
新ストリング状態
〔６〕．
ストリング終了状態
　次に図３を参照すると、図２の圧縮装置からの圧縮符号信号に対応するデータ文字列を回復する本発明の伸長装置の実施例が示されている。図３の伸長装置は、その出力を外部ランダム・アクセス・バッファに直接におくことのできるように回路を構成され、その構成は、出力文字ストリングの急速な反転をできるようにする。この伸長装置の実施例は、出力記憶場所のアドレスの明示管理を用いている。ストリング・テーブル内の記述項には接頭部ストリング内の文字の数を示す「レベル」値がある。このレベル値を用いて出力バッファ内の各文字の適当な位置決めを達成する。伸長装置からの伸長文字ストリングを受ける外部装置は、そのデータを格納するのにランダム・アクセス記憶装置を用いると仮定されている。外部ランダム・アクセス・バッファを用いるとき伸長装置は、各出力データ文字にアドレスを与え、そのアドレスが出力ストリング内のその文字の記憶場所を限定する。最初の記憶場所は、ゼロのアドレスに対応する。外部装置はその特定の記憶アドレス指定の要求事項にマッチするように記憶場所のアドレスを操作できる。
　図３の伸長装置は、出力文字をそれらが図２の圧縮装置によって受けられるのと違う順序で与えるが、各文字に付随して記憶場所の値を与えることによって、最後のアセンブルされたデータストリームは、正しい順序になる。ランダム・アクセス記憶装置を外部装置に用いない場合、図５に関して以下に説明するようなストリング反転へのスタック機構アプローチを用いることができる。
　図３の伸長装置は、バス５０の上の圧縮符号信号を受けて、バス５１の上に回復したデータ文字信号の対応するストリングを与える。圧縮符号信号は、外部装置からバス５０の上に与えられる。この外部装置はまた、圧縮信号がその外部装置から入手できて、バス５０に加えられるときは常に、ライン５２にデータ使用可能信号を与える。ライン５２の上のデータ使用可能信号は、伸長装置の制御装置５３に加えられる。制御装置５３は図３の伸長装置のすべてのブロックにリード５４を経て制御信号を与える。伸長装置の制御装置５３は、図３の伸長装置をその制御状態を介して、以下に詳細に説明する方法で順序づける。制御装置５３はまた、追加の入力符号信号を要求する入力データ・ストローブ信号をライン５５を通して外部装置に与える。一つの出力文字がバス５１の上で使用可能なとき、制御装置５３はリード５６の上の外部装置に出力データ・ストローブ信号を与える。
　バス５０の上の圧縮符号信号は、Ｃビット符号レジスタ５７に入れられる。単一文字のストリングを表す符号と複数文字のストリングを表す符号との区別をするために、符号レジスタ５７の出力を比較器５８で２Ｂの一定値信号と比較する。従って、比較器５８は、レジスタ５７の中の符号信号が２Ｂより大きいか小さいかを示す信号を制御装置５３にリード５９を経て送る。レジスタ５７の中の符号値が２Ｂより小さく、従って単一文字のストリングを表すとき、レジスタ５７の低位ビットがバス６０を経てＢビットの最終文字レジスタ６１に転送される。上述のように、単一文字のストリングに対する符号値は、その文字と同じであるから、最終文字レジスタ６１ヘバス６０を経て転送された単一文字のストリングは直接バス５１に出力される。
　レジスタ５７の中の圧縮符号信号が比較器５８によって決められるように２Ｂより大きいとき、レジスタ５７の中の符号値は、ＲＡＭアドレス・レジスタ６２ヘバス６３を介して転送される。圧縮符号信号の伸長の間のある幾つかの時点で、レジスタ５７の中の圧縮符号は、その値を後の処理のために保存するためＣビット符号レジスタ６４ヘバス６５を介して転送される。後で説明するある幾つかの条件ではレジスタ６４の中の符号値をＲＡＭアドレス・レジスタ６２ヘバス６６を介して転送できる。
　適当なアドレスを伸長装置の中の文字ストリングの記憶域に与えるために、最終文字レジスタ６１に格納された文字信号および符号レジスタ６４に格納された符号信号がバス６７および６８をそれぞれ介してハッシュ関数回路６９へ加えられる。ハッシュ関数回路６９は、図２に関して前に述べたハッシュ関数回路２３と同一である。ハッシュ関数回路６９は、バス６８の上のＣビット符号信号をバス６７の上のＢビット文字信号と結合してＮ個のＣビットアドレスをバス７０を経てＲＡＭアドレス・レジスタ６２へ順次に与える。ハッシュ関数回路６９は、制御装置５３ヘリード７１を介してバス７０の上に与えられたハッシュ・アドレスがその列の中のＮ番目のアドレスであるかどうかを知らせる。
　ハッシュ関数回路６９はまた「新ハッシュ」指令および「次のハッシュ」指令を制御装置５３から受ける。制御装置５３は「新ハッシュ」指令に応じてＮ個のハッシュ・アドレスの中の第１のものを与え、次に「次のハッシュ」指令の相次いで起るのに応じて、相次ぐハッシュ・アドレスを与えるようにハッシュ関数回路６９に指令する。前に述べたように、ハッシュ関数回路６９がＮ番目のハッシュ・アドレスを与えたとき、一つの信号が制御回路５３ヘリード７１を介して戻される。
　ＲＡＭアドレス・レジスタ６２からのＲＡＭアドレスは、バス７３を介して比較器７２および最終文字レジスタ６１の両方に加えられる。比較器７２はまた２Ｂに等しい一定値信号を受ける。比較器７２は、バス７３の上のＲＡＭアドレスを値２Ｂと比較して、バス７３の上のアドレスが２Ｂより大きいか小さいかを示す信号を制御装置５３ヘリード７４を介して与える。それが２Ｂより小さいとき、ＲＡＭアドレス・レジスタ６２の中の値は、文字ストリングの中の最初の文字を後述のようにして回復するために最終文字レジスタ６１に加えられる。
　ＲＡＭアドレス・レジスタ６２の中にロードされたアドレスが伸長装置ストリング・テーブルを記憶するのに用いられるＲＡＭ７５を呼出す。ＲＡＭ７５には、各々がＣ＋Ｂ＋Ｌビットの幅である２Ｃの記憶場所がある。各ストリングは、それのＣビット接頭部符号、それのＢビット拡張文字およびＬビットレベル値を記憶することによってＲＡＭに記憶される。レベル欄の値は、そのストリングの接頭部内のビットの数に等しい。各ストリングは、そのストリングに割当てられた符号によってアドレス指定された記憶場所においてＲＡＭ７５に記憶される。そのストリングに割当てられた符号は、接頭部符号を後述のようにしてストリング拡張文字でハッシュすることによって引出される。
　ＲＡＭ７５は、ＲＡＭ７５の「読出し」、「書込み」機能を制御するために「読出し」指令と「書込み」指令を制御装置５３から受ける。後で説明するようにして初期設定するために、ＲＡＭ７５は、一定値信号２Ｂ、ゼロおよびゼロをそれぞれＲＡＭアドレス・レジスタ６２によってアドレス指定されたＲＡＭ記憶場所の接頭部符号、文字およびレベルの各欄に書込むために受ける。これらの値は制御装置５３の制御のもとで加えられて、「書込み」指令の加わったときに入れられる。ＲＡＭ７５はまた制御装置５３によって制御されて、バス７６を経て符号レジスタ６４からくる符号値、バス７７を経て最終文字レジスタ６１からくる文字値およびバス７９を経てレベル・レジスタ７８からくるレベル値をＲＡＭアドレス・レジスタ６２によってアドレス指定されたＲＡＭ記憶場所の接頭部、文字およびレベルの各欄にそれぞれ入れるために選択的に受ける。これらの値は、制御装置５３からの「書込み」指令に応じてそれぞれの欄に書き込まれる。
　制御装置５３はまた、「読出し」指令に応じてＲＡＭ７５を制御して、ＲＡＭアドレス・レジスタ６２によってアドレス指定されたＲＡＭ記憶場所の接頭部符号欄に格納された接頭部符号値をバス８０に与える。このバス８０の上の符号値は、検出器８１のほかにＲＡＭアドレス・レジスタ６２にも加えられる。検出器８１は、ＲＡＭ出力のバス８０上の接頭部符号が２Ｂに等しいかどうかを決定して、それ相応に信号をリード８２を介して制御装置５３に与える。
　制御装置５３はまた、文字値を文字欄からバス８３を経て最終文字レジスタ６１へ選択的に与えるようにＲＡＭ７５を制御する。文字値は、「読出し」指令に応じてＲＡＭアドレス・レジスタ６２によってアドレス指定されたＲＡＭ記憶場所の文字欄からバス８３の上に与えられる。同様にして、制御装置５３は、レベル値をバス８４を経てレベル・レジスタ８５またはアドレス加算器８６のいずれかに与えるようにＲＡＭ７５を制御する。レベル値は、ＲＡＭアドレス・レジスタ６２によって呼出されたＲＡＭ記憶場所のレベル欄からバス８４へ加えられる。バス８４上のレベル値のレベル・レジスタ８５およびアドレス加算器８６への経路指定は、伸長装置の現存の状態に従って制御装置５３によって制御される。
　図３の伸長装置は外部ランダム・アクセス記憶装置内で適当に位置が合うようにするために出力文字信号にアドレスを割当てる装置を含んでいる。従って、アドレス加算器８６はそのような記憶場所アドレスを外部装置にバス８７を通して与える。アドレス加算器８６は、アウトポインタ・レジスタ８８からの入力、ＲＡＭ７５からのバス８４を通してのレベル値およびレベル・レジスタ７８からバス８９を通してのレベル値を受ける。アドレス加算器８６はまた、バス９０を通してゼロ値信号を受ける。制御装置５３は、アドレス加算器８６を制御して、バス８４の上のレベル値、バス８９の上のレベル値またはバス９０の上のレベル値のいずれかを伸長装置の現存の状態およびその状態の間に存在する論理的諸条件に従うアウトポインタ・レジスタ８８の中の値を後で説明するようにして加える。加算の結果は、記憶場所アドレスをバス８７の上に与える。
　アドレス加算器８６の出力はまた、アウトポインタ・レジスタ８８への入力としても加えられる。制御装置５３は、アウトポインタ・レジスタ８８を制御して、現存のアウトポインタの値を加算器８６における加算の結果で置き換えるか、または単にバス８７の上に記憶場所のアドレスを発生するためのベース・アドレスを加算器８６に与えるだけにする。制御装置５３はまた、レベル・レジスタ７８および８５を制御して、レベル・レジスタ８５からレベル・レジスタ７８ヘレベル値を転送して、その転送経路にある加算器９１を介してその値を１だけ大きくする。なお、制御装置５３は、レベル・レジスタ７８および８５を制御して、レベル・レジスタ７８の内容をレベル・レジスタ８５ヘバス９２を介して転送する。この装置はまた、レベル・レジスタ８５およびアウトポインタ・レジスタ８８への入力を備え、あとで説明する諸条件のもとでこれらのレジスタをゼロにする。
　図３の伸長装置はまた、Ｃビット信号ＲＡＭアドレス・レジスタ６２へのバス９４を経て与える初期設定計数器９３を備えている。計数器９３をそれに加わるゼロの値にされた信号を介してゼロにセットできる。制御装置５３は、「計数」指令を介して計数器９３を制御して、「計数」指令の加わるごとに計数器の内容に１を加える。計数器９３は、それが計数値２Ｃに達したとき、制御装置５３にリード９５の上のキャリアウトまたはオーバフロー信号を介して合図する。初期設定計数器９３は、ＲＡＭ７５を初期設定するのに用いられ、それの記憶場所のすべてを逐次に呼出して一定値２Ｂ、ゼロおよびゼロを接頭部符号、文字およびレベルの各欄にそれぞれ書込むことによって空にする。
　図３の伸長装置の基本動作は、次のように要約される。
１．各データブロックごとに、ＲＡＭを空に初期設定する。
２．各入力符号ごとに、符号を符号番号レジスタに読出す。前の符号からのあるデータをストリング・テーブル更新のために保存する。
３．符号レジスタ→ＲＡＭアドレス
　接頭部符号、拡張文字、ストリング長さを作るＲＡＭを読出す。
　接頭部符号→２Ｂなら；文字をストリング長さによって決まった記憶場所において出力；
　接頭部符号→符号番号レジスタ；ステップ３を繰返す、
　接頭部符号＜２Ｂなら；符号値を文字として出力；ステップ４へ行く。
４．ストリング・テブルの終りにおいて文字ストリングを更新：
　前に受けた符号および最終出力文字をハッシュ（前の符号、最終文字）によって作られた列から最初の空の記憶場所に書込む；ステップ２へ行く。
　図３を続けて参照すると、以下のものが図３の伸長装置の状態機械記述語である。
状態０：各データブロックの始めにおける「待ち状態」
　　　　初期設定計数器＝ゼロ
　　　　アウトポインタ＝ゼロ
　　　　データ使用可能信号を待つ；状態１へ行く。
状態１：「ＲＡＭを初期設定」
　　　　初期設定計数器→ＲＡＭアドレス２Ｂ、ゼロ、ゼロ→ＲＡＭ入力
　　　　ＲＡＭを書込む
　　　　初期設定計数器へ＋１を加える
　　　　初期設定計数器＜２Ｃならば、状態１を繰返す；そうでなければ状態２へ行く。
状態２：「最初の入力符号を処理する」
　　　　入力符号記号→符号レジスタ１
　　　　入力データ・ストローブ
　　　　符号値（下位Ｂビット）→最終文字レジスタ
　　　　記憶場所アドレス＝アウトポインタ；出力データ・ストローブ
　　　　レベル・レジスタ１＝ゼロ
　　　　状態３へ行く。
状態３：「次の入力符号」
　　　　符号レジスタ１→符号レジスタ２
　　　　（レベル・レジスタ１）＋１→レベル・レジスタ２
　　　　（レベル・レジスタ２）＋（アウトポインタ）→アウトポインタ
　　　　新しい入力が使用可能でなければ；状態０へ行く。
　　　　入力符号を読出す→符号レジスタ１
　　　　入力データ・ストローブ
　　　　符号レジスタ１≧２Ｂなら：
　　　　レベル・レジスタ１＝０
　　　　　　符号レジスタ１→ＲＡＭアドレス
　　　　　　状態４へ行く。
　　　　符号レジスタ１＜２Ｂならば：
　　　　　　符号値（符号レジスタ１の下位Ｂビット）→最終文字レジスタ
　　　　　　記憶位置アドレス＝アウトポインタ：出力データ・ストローブ
　　　　　　状態５へ行く。
状態４：「最初の文字サイクル」
　　　　ＲＡＭを読出す
　　　　符号（ＲＡＭ）≠２Ｂならば［正常の場合］：
　　　　　　レベル（ＲＡＭ）→レベル・レジスタ１
　　　　　　符号（ＲＡＭ）→ＲＡＭアドレス
　　　　　　文字（ＲＡＭ）→最終文字レジスタ
　　　　記憶場所アドレス＝アウトポインタ＋レベル（ＲＡＭ）；
　　　　　　出力データ・ストローブ
　　　　　　符号（ＲＡＭ）＝２Ｂならば［異常の場合］：
　　　　　　レベル・レジスタ２→レベル・レジスタ１
　　　　　　符号レジスタ２→ＲＡＭアドレス
　　　　記憶場所アドレス＝アウトポインタ＋レベル・レジスタ２；出力データ・ストローブ
　　　　状態５へ行く。
状態５：「後の文字サイクル」
　　　　ＲＡＭアドレス≧２Ｂならば：ＲＡＭを読出す
　　　　　　符号（ＲＡＭ）→ＲＡＭアドレス
　　　　　　文字（ＲＡＭ）→最終文字レジスタ
　　　　記憶場所アドレス＝アウトポインタ＋レベル（ＲＡＭ）；出力データ・ストローブ
　　　　状態５へ行く。
　　　　ＲＡＭアドレス＜２Ｂならば：
　　　　ＲＡＭアドレス（下位Ｂビット）→最終文字レジスタ
　　　　記憶場所アドレス＝アウトポインタ；出力データ・ストローブ
　　　　状態６へ行く。
状態６：「ストリング・テーブル更新」
　　　　ハッシュ（符号レジスタ２、最終文字レジスタ）→ＲＡＭアドレス
　　　　　　ＲＡＭを読出す
　　　　符号（ＲＡＭ）＝２ＢおよびＲＡＭアドレス＞２Ｂならば：
　　　　　　状態７へ行く。
　　　　その他の場合：新ハッシュ値で状態６を繰返す。
　　　　これが最終ハッシュならば、状態３へ行く。
状態７：「書込みサイクル」
　　　　ＲＡＭアドレスを変えないで
　　　　符号レジスタ２→符号（ＲＡＭ）
　　　　最終文字レジスタ→文字（ＲＡＭ）
　　　　レベル・レジスタ２→レベル（ＲＡＭ）
　　　　ＲＡＭを書込む。
　　　　状態３へ行く。
　上に与えられた状態機械記述語に関する図３の伸長装置の動作のさらに詳細な説明を次に行う。
［０］　
待ち状態
［１］　
初期設定状態
　初期設定は、Ｃビット初期設定計数器９３の中の値をバス９４を経てＲＡＭアドレス・レジスタ６２ヘゲートすることによってメモリ・サイクルを繰返して達成される。ＲＡＭの入力は、一定値２Ｂおよびゼロであるように選ばれる。ＲＡＭ７５は、選択された入力データをＲＡＭアドレス・レジスタ６２によって指定された記憶場所に書込むように制御される。初期設定計数器９３は、その現在の内容に１を加えることによって数え上げるように指令される。この一連の事象は、各記憶場所ごとに１回あて合計２Ｃ回繰返される。２Ｃのそのような計数ののちに、初期設定計数器９３は、２Ｃの計数が発生したことを合図するオーバフローまたはキャリアウト信号を制御装置５３にリード９５に介して与える。これによって図３の伸長装置が「最初の符号状態」に進む。
［２］　
最初の符号状態
　続く伸長装置サイクルに備えて、レベル・レジスタ８５は、ゼロにセットされる。これは受取ったストリング内の接頭部ストリングの長さであるとわかっているかである。次に「次の入力状態」の主処理サイクルに入る。
［３］　
次の入力状態
　次に、新入力符号信号は、もしそれが使用可能であれば読出されている。新入力符号が使用できないことをライン５２の上のデータ使用可能信号が指示する場合、そのメッセージを完全に処理してしまっており、「待ち状態」に新しいメッセージを待つために再び入る。正規の状態においては、新入力符号信号が使用可能で、それは入力バス５０から符号レジスタ５７にゲートされる。ライン５５の上の入力データ・ストローブ信号は、外部装置に向けて発せられて、その装置に次の符号信号を入力バス５０に与えさせる。
　レジスタ５７にある新符号信号は、比較器５８を用いて２Ｂと比較される。符号レジスタ５７にある新符号値が２Ｂより大きければ、これは、ＲＡＭ７５の中のストリング・テーブル索引によって翻訳される正規の符号である。従って、レジスタ５７にあるこの符号値は、バス６３を経てＲＡＭアドレス・レジスタ６２へ転送され、制御装置５３は、伸長装置を「最初の文字状態」に入るように制御する。
　図２および図３のデータ圧縮装置およびデータ伸長装置が適正な動作をしているときは、符号レジスタ５７が値２Ｂを含むことができない理由は、その符号が図２の圧縮装置によって正しく与えられないからである。実際に、符号レジスタ５７が値２Ｂを含んでいれば、任意の都合のよい誤り手順を実施できる。
　符号レジスタ５７の中の値が２Ｂより小さければ、この符号値は、単一文字のストリングを定めるので、そのストリングを処理するのにＲＡＭ７５にアクセスする必要がない。この状況において、レベル・レジスタ８５がゼロにセットされる理由は、単一文字によって予め定められたストリングの接頭部ストリング内に文字がないからである。符号レジスタ５７の下位Ｂビットである文字値は、バス６０を経て最終文字レジスタ６１へ転送され、そこから外部装置へ出力バス５１を通って転送される。この状況において、アウトポインタ・レジスタ８８が正しい外部アドレスを含み、それでアウトポインタ・レジスタ８８の中の値がアドレス加算器８６を通過して、バス８７の上に記憶場所アドレスを与えるので、その値にゼロが加えられる。次に、ライン５６の上の出力データ・ストローブ信号が外部装置に正しいデータが出力文字ラインおよびアドレス・ラインを通して使用できることを指示するために発せられる。１文字のストリングの処理を完了したのちに「更新状態」に入る。
［４］　
最初の文字状態
　バス８０の上の接頭部符号が２Ｂに等しくない場合（これは正常な場合である）、それは、それ以上の文字を得るためにさらに処理されるべき正当な接頭部ストリング符号である。バス８３の上の拡張文字は、最終文字レジスタ６１に転送される。バス８４の上のレベル値は、そのストリング内のこの文字の位置を示し、この位置の値は、アドレス加算器８６を経てアウトポインタ・レジスタ８８の中の値に加えられて、その文字に対する出力記憶場所アドレスをバス８７に与える。次に、ライン５６の上の出力データ・ストローブ信号は、正しいデータが使用できることを外部装置に指示するために発せられる。なお、バス８４の上のレベル値は、あとの更新において用いるためにレベル・レジスタ８５に格納される。バス８０の上の接頭部ストリング符号値が２Ｂに等しければ、これは、アドレス指定されたＲＡＭ記憶場所が空であり、受けたストリング符号がストリング・テーブル内の一つの記述項に対応しないことを示す。この状況は、次の保留中のテーブル更新がそのストリング記述項を作り出すような異常な場合に起る可能性があるだけである。すなわち、受けたばかりの符号は、処理されたばかりのストリング（符号レジスタ６４の中の符号とレベル・レジスタ７８の中のレベル値）である接頭部ストリングをもつストリングを表す。現在のストリングの最初の復号された文字は、前のストリングの拡張文字であり、現在のストリングの中に見出されるべき最終の復号された文字と同じ文字であって、それは、それらの文字が同じ接頭部ストリングをもつので、前のストリングの最終の復号された文字と同じ値を有し、それは最終文字レジスタ６１に現在ある文字である。従って、この異常な場合を実現するために、符号レジスタ６４の中の値をバス６６を経てＲＡＭアドレス・レジスタ６２へ接頭部ストリング符号として転送する。最終文字レジスタ６１の中の値は、出力文字バス５１を駆動するのに変更しないで用いられるが、一方、レベル・レジスタ７８の中の値は適当な出力記憶場所アドレスをバス８７に作るためにアドレス加算器８６を介してアウトポイント・レジスタ８８の中の値に加えられる。次に、制御装置５３は、正しい出力を外部装置に指示するために出力データ・ストローブをライン５６に発する。レベル・レジスタ７８の中の値は、あとでの更新のために長さ情報を与えるのにバス９２を経てレベル・レジスタ８５に転送される。
　このストリングから１文字を出力してしまうと、残りの文字は「後の文字状態」に入ることによって発生される。
［５］　
後の文字状態
　比較器７２がＲＡＭアドレス・レジスタ６２の中の符号値が２Ｂより小さいことを示す場合、そのストリングの終りがきたことになる。この予め定めた符号値は、最終文字を含んでいるのでＲＡＭアドレス・レジスタ６２の下位Ｂビットがバス７３を経て最終文字レジスタ６１に転送される。ゼロがアウトポインタ・レジスタ８８の中の値にアドレス加算器８６を介して加えられ、バス８７に適当な出力記憶場所アドレスを発生する。次に出力データ・ストローブ信号がライン５６に与えられる。現在ストリングについての処理が終ると、「更新状態」に入ってストリング・テーブルに一つの記述項を加える。
［６］　
更新状態
［７］　
書込み状態
　上述のハッシュ関数回路を以下のように装置として実現できる。Ｂビット文字およびＣビット符号の場合、Ｎ個のハッシュ値は次のように発生される：
　最初のハッシュ（符号、文字）＝符号０文字′
　ここで文字′は入力文字をビットを左右逆にし、位相反転され、左Ｃ−Ｂビットを符号の左側の位置へ移したものである。
　すなわち、符号においてＣ（左に）から１（最下位ビット）および文字においてＢないし１と番号をつけられたビット位置に対して、ハッシュ出力ＨはＣないし１の番号をつけられる。
　【外３】
　　　Ｈ（Ｃ）＝符号（Ｃ）▲＋▼文字（１）▲＋▼１
　　　Ｈ（Ｃ−１）＝符号（Ｃ−１）▲＋▼文字（２）▲＋▼１
　　　Ｈ（Ｃ−２）＝符号（Ｃ−２）＋文字（３）＋１
　　　Ｈ（Ｃ−Ｂ−１）＝符号（Ｃ−Ｂ−１）▲＋▼文字（Ｂ）▲＋▼１
　　　Ｈ（Ｃ−Ｂ−２）＝符号（Ｃ−Ｂ−２）
　　　Ｈ（１）＝符号（１）
　残りのハッシュは、一定値を各前の値に、Ｃビット以上のキャリーを無視して加えることによって作られる。
　【外４】
　次のハッシュ＝前のハッシュ＋［（２＊符号＋１）▲＋▼０１０１・・・０１００２］（モジュロ２Ｃ）
　このハッシング関数は、任意のシステムの論理ゲートで実現でき、本発明において使用できるハッシング関数の単なる一例であることがわかる。上に論じた基準を満足する他のハッシング関数を当業者が容易に得ることができる。
　図４および図５は、最高の圧縮を実施するための圧縮装置および伸長装置をそれぞれ示す。図４および図５の実施例は、図２および図３の高性能実施例よりわずかに値段が高く、かつ動作がわずかに遅い。この実施例は、高性能実施例とほぼ同じ適応圧縮手順を用いるが、高性能実施例とは違って、圧縮装置は、可変長さの圧縮された出力符号信号を発生する。高性能実施例に関して上述したものと同様にして、図４および図５の高圧縮実施例は、Ｂビット・バイト入力文字信号および２Ｃの記憶場所のストリング・テーブルを用いる。圧縮符号記号は、ストリング・テーブルがいっぱいになるにつれて、大きさを増してＣビットの最大長さに達する。必要に応じて、この符号信号は、新しい文字に出合ったときＢビットだけ拡張される。
　このテーブル内の各ストリングにＣビット識別子を割当てて、これらの識別子は１で始まる数の順序で割当てられる。２Ｄ以下の数の符号を割当てられたとき、これらの符号の下位Ｄビットだけを圧縮データ信号として伝送する。ストリング・テーブル内の各記憶場所は、Ｃビットの接頭部ストリング識別子およびその記憶場所にあるストリングに割当てられた新しいＣビット符号を含んでいる。従ってストリング・テーブルの２Ｃの記憶場所の各々は、２Ｃビットの幅である。この高圧縮実施例の圧縮装置で用いられるハッシュ関数は、先に説明した高性能実施例で用いられたものと同一である。しかし、この高圧縮実施例においては、ハッシュ関数回路は、圧縮装置に用いられるだけである。
　この高圧縮実施例の本発明による伸長装置においては、圧縮装置におけると論理的に同じストリング・テーブルが記憶されているが、各記憶場所は、接頭部に対して割当てられた識別子符号および拡張文字からなっている。各ストリングは、そのストリングに割当てられた圧縮符号識別子によってアドレス指定された記憶場所に記憶されている。この高圧縮実施例においては、ストリング間文字反転手順は、そのストリング内の文字の順序を逆にする「後入れ先出し」スタックによって行われる。従って、この高圧縮実施例の伸長器は各ストリングの出力文字をそれらの正しい順序で与える。
　次に図４を参照すると、本発明の最高圧縮実施例の圧縮装置が示されている。この圧縮装置は、入力文字信号をバス１１０を通して受けて、圧縮出力符号記号信号をビット直列形式でライン１１１に与える。この入力文字は、外部装置からバス１１０に与えられる。この外部装置はまた、入力文字信号が外部装置から使用できて、バス１１０に加えられるときは常に、データ使用可能信号をライン１１２に与える。ライン１１２上のデータ使用可能信号は、圧縮装置制御装置１１３に加えられる。圧縮装置制御装置１１３は、図４の圧縮装置のブロックのすべてに制御信号をリード１１４を介して与える。圧縮装置制御装置１１３は、図４の圧縮装置をそれの制御状態を介して以下に詳細に説明する方法で順序づけする。制御装置１１３はまた、追加の入力文字を要求する文字ストローブ信号をライン１１５を通して外部装置に与える。
　バス１１０の上の入力文字はＢビット文字レジスタ１１６に入れられる。単一文字を出力線１１１に転送することになっているとき、文字レジスタ１１６は、その文字のＢビットをバス１１７を介してシフト回路網１１８にゲートするように制御装置１１３によって制御される。シフト回路網１１８は、ビット直列出力をライン１１１に与え、バス１１７の上のＢビットを受けて、これらのビットをライン１１１に直列に与えるように制御装置１１３によって制御される。
　図４の圧縮装置は、さらに、圧縮ストリング符号信号を保持して出力ストリング符号をシフト回路網１１８にバス１２０を介して与えるビット符号番号レジスタ１１９を備えている。符号番号レジスタ１１９をそれに加わるゼロの値にされた信号によってゼロに初期設定できる。
　図４の圧縮装置は、さらに、入力バス１１０に加えられる入力データ・ストリームのパースされたストリングにストリング符号記号信号を数の昇順に割当てるＣビット符号計数器１２１を備えている。制御装置１１３の制御のもとに、符号計数器１２１をそれに加わるゼロの値にされた信号を介してゼロにリセットしてもよいし、「計数」指令信号を介して現存の計数を１だけ大きくしてもよい。計数器１２１は、符号計数器１２１の中の計数値が値２Ｃ−１に達したときに制御装置１１３にライン１２３を介して信号を出力する検出器１２２に出力を与える。この値は、計数器がオール１の状態に達するとき、Ｃビット計数器１２１によって達成される。符号計数器１２１の出力はまた、シフト回路網１１８によってシフトアウトされるべきビットの数を定める信号をシフト回路網１１８にバス１２４を介して与える符号大きさ回路１２３に加えられる。上述のように、Ｄビットがシフトアウトされる（ここでＤはＣ以下である）。
　符号大きさ回路１２３をＳＮ７４１４８優先順位回路網のような標準Ｃビット優先順位符号器回路によって実現できる。符号計数器１２１は優先順位符号器に結合され、そして計数器１２１の昇順重みのビットを優先順位符号器の昇順優先順位に並んだ優先順位入力にそれぞれ結合される。次に優先順位符号器は、Ｄに対する値である２進数信号を与える。数Ｄをシフト回路網１１８の中で用いて、Ｄシフト・クロック・パルスのパケットをゲートして、シフト回路網１１８がバス１２０に与えられた出力符号信号のＤビットをライン１１１に直列に与えるようにしてもよい。優先順位符号器を符号大きさ回路１２３に用いることに対する多くの代替のものが論理設計の当業者には容易に明らかであろう。
　例えば、シフト回路網１１８は、出力符号をバス１２０に受けて符号大きさ回路１２３によって制御されたシフトクロックパルスに応答して出力符号のＤビットをシフトアウトするシフト・レジスタを用いて実現できる。符号大きさ回路１２３によって制御されるＤクロックパルスのパケットに応答して、シフト回路網１１８の中に入っているシフト・レジスタにはクロック信号がＤ回与えられる。シフト・レジスタの構成は、この技術分野では周知であり、その正確な詳細は、データを受ける外部装置のインタフェースによって変る。上述のように、シフト回路網１１８はまた、Ｂ文字ビットをバス１１７からライン１１１のシフト回路網１１８によって伝送するのを制御する普通のクロック制御回路を備えている。
　レジスタ１１９からの符号記号信号およびレジスタ１１６からの文字信号は、それぞれバス１２５および１２６を経てハッシュ関数回路１２７へ加えられる。ハッシュ関数回路１２７は、上述の本発明の高性能実施例に関して用いられたハッシュ関数回路と同一である。ハッシュ関数回路１２７は、バス１２５の上のＣビット符号信号をバス１２６の上のＢビット文字信号と組合わせて、バス１２８の上に順次にＮ個のＣビットアドレスを与える。ハッシュ関数回路１２７は、リード１２９を介して制御装置１１３にバス１２８の上に与えられたハッシュアドレスがその列の中のＮ番目のアドレスであるかどうかを知らせる。
　ハッシュ関数回路１２７はまた、制御装置１１３から「新ハッシュ」指令および「次のハッシュ」指令を受ける。制御装置１１３は「新ハッシュ」指令に応じてＮ個のハッシュアドレスの最初のものを与え、また「次のハッシュ」指令の相次ぐ発生に応じて相次ぐハッシュドレスを与えるようにハッシュ関数回路１２７に指令する。上述のように、ハッシュ関数回路１２７がＮ番目のハッシュアドレスを与えたとき、一つの信号をリード１２９を経て制御装置１１３に戻す。
　バス１２８の上のハッシュ・アドレスは、ＣビットＲＡＭアドレス・レジスタ１３０に加えられる。ＲＡＭアドレス・レジスタ１３０にロードされたアドレスが圧縮装置ストリング・テーブルを記憶するのに用いられるＲＡＭ１３１を呼出す。ＲＡＭ１３１は各々２Ｃビット幅の２Ｃの記憶場所に編成される。一つの文字ストリングが一つの記憶場所に符号計数器１２１によって割当てられたそのストリングに対する符号番号およびその接頭部符号、すなわち、そのストリングの最終文字を除くすべての文字を含むストリングの符号番号を入れることによって記憶される。ＲＡＭ１３１は、すべての記憶場所が最初に空であることを示すオール・ゼロをストリング符号欄に含むように初期設定される。文字をもたないストリンである符号ゼロのストリングは、ＲＡＭ１３１の中に記述項をもたない。
　ＲＡＭ１３１は、ＲＡＭ１３１の「読出し」および「書込み」機能を制御するために制御装置１１３から「読出し」指令および「書き込み」指令を受ける。制御装置１１３がＲＡＮ１３１に「書込み」機能を実行するように指令すると、ＲＡＭアドレス・レジスタ１３０によって呼出された記憶場所のストリング符号欄がバス１３２を経て符号計数器１２１のＣビット出力を受け、また呼出された記憶場所の接頭部符号欄が符号番号レジスタ１１９からの入力をバス１３３を経て受ける。制御装置１１３がＲＡＭ１３１にＲＡＭアドレス・レジスタ１３０によって呼出された記憶場所の内容を読出すように指令すると、呼出された記憶場所の接頭部符号がバス１３５を経て比較器１３４に加えられ、また呼出された記憶場所のストリング符号がバス１３６を経て符号番号レジスタ１１９へ加えられると共に、ゼロ検出器１３７にも加えられる。比較器１３４はまた、バス１３８にゼロの値をもつ信号を受ける。図４の圧縮装置の現存の状態次第で、制御装置１１３は、バス１３５の上の接頭部符号とレジスタの中に記憶された符号とが等しいか等しくないかを試験するか、またはレジスタ１１９の中の符号信号がゼロに等しいか等しくないかを試験するように比較器１３４を制御する。これらの試験の結果は、リード１３９を経て制御装置１１３に与えられる。図４の圧縮装置の現存の状態に従えば、制御装置１１３は、バス１３６の上のストリング符号がゼロに等しいか等しくないかを決めるためのゼロ検出器１３７を始動させる。決定の結果は、リード１４０を経て制御装置１１３に与えられる。
　図４の圧縮装置はまた、Ｃビット信号をバス１４２を経てＲＡＭアドレスレジスタ１３０に与える初期設定計数器１４１を備えている。制御装置１１３は、計数指令を介して計数器１４１を制御してその計数器の内容を計数指令を加えるごとに１だけ増やす。計数器１４１は、それが計数値２Ｃに達したときを制御装置１１３にリード１４３の上のキャリアウトまたはオーバーフロー信号を介して知らせる。初期設定計数器１４１は、ＲＡＭ１３１の記憶場所のすべてを順次に呼出してストリング符号欄にバス１３２から得た値ゼロを書込むことによってＲＡＭ１３１を空に初期設定するのに用いられる。必ずしも必要ではないけれども、接頭部符号欄を、実現の便宜上、バス１３３から得た値ゼロを書込むことによって、初期設定してもよい。
　一般的にいえば、図４の圧縮装置に関しては、ライン１１１に与えられる各出力符号記号信号は、符号計数器１２１の中に現存する値によって定められたＤビットの長さをもっている。符号計数器内のゼロでない最高のビットがＤ番目のビットであって、その結果、圧縮装置の出力符号の大きさが符号計数器内の値の大きさに等しい。圧縮装置によって伝送されるべき最初の符号記号信号は、ゼロビットの幅であるが、それに付加されたＢビットの文字記号信号をもっている。二番目の符号記号信号は、１ビットの長さで、次の二つの符号記号信号は、二つのビットを各々含んでいる。次の四つの符号記号信号は、３ビットを各々含んでいる、などである。これらの符号記号の幾つかはまたそれらに追加されたＢビットの文字値をもっている。値Ｄは、Ｃビットで最大に達する。
　次に図５を参照すると、図４の圧縮装置からの圧縮符号信号に対応するデータ文字列を回復する本発明伸長装置の実施例が示されている。図５の伸長装置においては、その伸長装置によって回復されるバイト・ストリングの順序を逆にするのにスタック機構が用いられる。このスタックは、各々Ｂビットの幅の１組のレジスタを含む通常の機構である。このスタックヘのアクセスは、読出し及び書込み能力を与えられている唯一のレジスタである先頭レジスタを通して行われる。このスタックは、スタック内の各レジスタを次の下のレジスタに複写する「プッシュ」能力をもっている。このスタックはまた、スタック内に各レジスタを次の上のレジスタに複写する「ポップ」能力をももっている。説明を簡明にするために、図５の伸長装置の実施例は、スタック内の正しい記述項の数を記録する独立のスタック計数器を用いて示されている。スタックの標準の実現装置においては、スタック計数器は、スタック機構に一体化されていることが多い。
　図５の伸長装置において、ストリング・テーブルは、２Ｃの記録場所を含み、各記憶場所は、Ｃ＋Ｂビットを含んでいる。各ストリング符号に対応する記憶場所は、接頭部ストリングに対する符号とそのストリングに対する拡張文字とを含んでいる。その記憶場所は、そのストリングに割当てられたストリング符号によってアドレス指定される。図５の伸長装置のストリング・テーブルは、それの記憶場所がどれもそれが書込まれる前に呼び出されないので、初期設定されない。
　図５の伸長装置は、リード１５０の上に図４の圧縮装置によって発生されたビット直列圧縮符号信号を受けて回復されたデータ文字信号の対応するストリングをバス１５１の上に与える。ビット直列圧縮符号信号は、外部装置からリード１５０の上に与えられる。この外部装置はまた、圧縮符号信号をリード１５０に加えるための外部装置から使用できるときは常に、リード１５２の上にデータ使用可能信号を与える。リード１５２の上のデータ使用可能信号は、伸長装置制御装置１５３に加えられる。制御装置１５３は、図６の伸長装置のすべてのブロックに制御信号をリード１５４を介して与える。伸長装置制御装置１５３は、図５の伸長装置を以下に詳細に説明するようにしてそれの制御状態を通して順序づける。バス１５１の上で出力文字が使用できるとき制御装置１５３は出力データ・ストローブ信号を外部装置経リード１５５を通して与える。
　図５の伸長装置は、ビット直列圧縮符号信号をリード１５０を通して受けて、これらの信号をＣビット符号レジスタ１５７ヘバス１５８を経て与えるシフト回路網１５６を備えている。シフト回路網１５６は、符号大きさ回路１５９によって制御されてレジスタ１５７ヘバス１５８を経てＤビットを与える（ここでＤはＣ以下である）。符号大きさ回路１５９によって制御される符号の大きさは、Ｃビット符号計数器１６０によって決められる。シフト回路網１５６、符号大きさ回路１５９および符号計数器１６０は、図４の圧縮装置の匹敵する構成要素に類似の方法で構成され、図４の圧縮装置に関して前述したものと同様の機能を行う。シフト回路網１５６は、リード１５０の上に与えらえたＤビット圧縮符号信号をレジスタ１５７のＤ個の下位ビットに入れる。図５の伸長装置の中に存在する既存の状態と論理的条件とに従って、制御装置１５３はまた、図４の圧縮装置によって与えられた単一文字を処理するためにスタック１６１の先頭にバス１６２を経てＢビットを与えるようにシフト回路網１５６を制御する。シフト回路網１５６の単一文字を処理するための制御は、図４に関して上述したものと同様の方法で行われてもよい。
　圧縮符号信号を処理するのに先立って、符号計数器１６０は、それに与えられるゼロの値をもつ信号を介してゼロにセットされる。計数器１６０はまた、制御装置１５３からの計数指令信号によって制御されて、その中に現存する計数を１だけ増分するようにできる。符号計数器１６０はまた、符号計数器１６０の中の計数値が値２Ｃ−１に達したときを制御装置１５３にライン１６４を経て知らせる出力を検出器１６３に与える。この値は、Ｃビット計数器１６０がオール１の状態になったとき、計数器１６０によって達成される。符号計数器１６０は、図４の圧縮装置の符号計数器１２１に関して説明したのと同様な方法で昇順にストリング符号記号信号を割当てる。これらのストリング符号信号は、ＲＡＭアドレス・レジスタ１６５にバス１６６を経て加えられる。
　符号レジスタ１５７は、図５の伸長装置の現存する状態とその中に存在する論理諸条件とに従ってそれに加わるゼロの値をもつ信号を介して制御装置１５３の制御を受けてゼロにリセットできる。符号計数器１６０の出力および符号レジスタ１５７の出力は、比較器１６７への入力として加えられる。あとで説明する理由により、比較器１６７は、符号計数器１６０の出力が符号レジスタ１５７の出力より小さいときおよび符号計数器出力が符号レジスタ出力以上であるときを制御装置１５３にリード１６８を介して知らせる。あとで説明する諸条件のもとで、符号レジスタ１５７は、その内容をＲＡＭアドレス・レジスタ１６５ヘバス１７１を介して加えるように制御できると共に、また、あとのストリング・テーブル更新のための符号信号を保存するためにその内容を第２の符号レジスタ１７２ヘバス１７３を介して転送できるように制御できる。
　図５の伸長装置は、さらにあとで説明する諸条件のもとで、符号レジスタ１７２の内容がゼロであるときを制御装置１５３にリード１７５を経て知らせるゼロ検出器１７４を備えている。制御装置１５３はまたその内容をＲＡＭアドレスレジスタ１６５ヘバス１７６を経て与えるように符号レジスタ１７２を制御する。
　ＲＡＭアドレス・レジスタ１６５にロードされたアドレスが伸長装置ストリング・テーブルを記憶するのに用いられるＲＡＭ１７７を呼び出す。ＲＡＭ１７７は２Ｃの記憶場所を含み、各記憶場所はＣ＋Ｂビットの幅である。各ストリングは、そのストリングへ割当てられた符号によってアドレス指定された記憶場所においてそのＣビット接頭部符号およびそのＢビット拡張文字を記憶することによってＲＡＭ１７７の中に記憶される。各符号値は、符号計数器１６０によって昇順に伸長装置ストリング・テーブルに入れられた各ストリングに割当てられる
　ＲＡＭ１７７は、制御装置１５３から「読出し」指令および「書込み」指令を受けてＲＡＭ１７７の「読出し」および「書込み」機能を制御する。ＲＡＭ１７７は、符号レジスタ１７２からの符号値をバス１７８を経て受けスタック１６１の先頭から文字値をバス１７９を経て受けて、ＲＡＭアドレスレジスタ１６５によってアドレス指定されたＲＡＭ記憶場所の接頭部欄および文字欄にそれぞれエントリーする。これらの値は、制御装置１５３からの「書込み」指令に応じてそれぞれの欄に書込まれる。
　制御装置はまた、ＲＡＭアドレスレジスタ１６５によってアドレス指定されたＲＡＭ記憶場所の接頭部符号欄に記憶された接頭部符号の値を「読出し」指令に応じてバス１８０に与えるようにＲＡＭ１７７を制御する。バス１８０の上のこの符号値は、ＲＡＭアドレス・レジスタ１６５へ加えられると共に、ゼロ検出器１８１へも加えられる。検出器１８１は、ＲＡＭ出力１８０にある接頭部符号がゼロに等しいか等しくないかを定め、かつ制御装置１５３への一つの信号をリード１８２を経て適宜に与える。
　制御装置１５３はまた、文字欄からの文字値をバス１８３を経てスタック１６１の先頭に与えてその中にエントリーするようにＲＡＭ１７７を制御する。文字の値は、ＲＡＭアドレス・レジスタ１６５によってアドレス指定されたＲＡＭ記憶場所の文字欄から「読出し」指令に応じてバス１８３の上に与えられる。ＲＡＭ出力１８０および１８３にある値は、図５の伸長装置の現存の状態および論理的諸条件とに従って選択的に与えられる。
　スタック１６１は、制御装置１５３からの「プッシュ」および「ポップ」信号の制御のもとにプッシュまたはポップすることができる。スタック１６１に記憶された文字の数の計数を維持するためにスタック計数器１８４が備えられている。制御装置１５３の制御を受けて、スタック計数器１８４は、それに加わるゼロの値になった信号を介してゼロにセットできる。計数器１８４の中の現存の計数を制御装置１５３の制御のもとにそれに加わるＡＤＤ＋１およびＡＤＤ−１信号によってそれぞれ１だけ増分または減分できる。ゼロ検出器１８５がスタック計数器１８４の出力を受け、スタック計数器１８４にある値がゼロに達するとき制御装置１５３ヘリード１８６を介して信号を与える。
　図５の伸長装置の基本動作は、次のように要約される。
１．最初の記号：圧縮データの最初のビットを読出し、
　　出力へ送る；ＲＡＭの記憶場所１に最初のストリングのエントリーをする
２．入力のＤビットを読出す→符号レジスタ
　　ゼロであれば、さらにＢ個の入力ビットを出力スタックに読出す；ステップ４へ行く。
３．符号レジスタ→ＲＡＭアドレス；ＲＡＭを読出す
　　文字（ＲＡＭ）→出力スタック
　　接頭部符号（ＲＡＭ）→ＲＡＭアドレス
　　接頭部符号がゼロでなければ、ステップ３を繰返す；
　　　そうでなければステップ４へ行く
４．符号計数器→ＲＡＭアドレス；
　　前の符号、最終文字をＲＡＭに書込む
　　出力スタックから文字を取って出力へ置く、ＬＩＦＯ：
　　符号計数器を増分する；ステップ２へ行く。
　図５を続けて参照すると、以下のものが、図５の伸長装置の状態機械記述語である。
状態０：「待ち状態」
　　　　データ使用可能信号を待つ；状態１へ行く。
状態１：「最初の符号」
　　　　符号計数器＝ゼロ
　　　　スタック計数器＝ゼロ
　　　　符号レジスタ１＝ゼロ
　　　　入力空のＢビットをスタックの先頭に読出す；出力データ・ストローブ
　　　　状態２へ行く。
状態２：「ゼロ・ストリング状態」
　　　　符号レジスタ２＝符号レジスタ１
　　　　符号計数器＋１を加える
　　　　符号計数器→ＲＡＭアドレス・レジスタ
　　　　ＲＡＭ＝符号レジスタ２、スタックの先頭を書込む。
状態３：「新符号」
　　　　符号レジスタ１→レジスタ２
　　　　どのデータも使用可能でなければ：状態０へ行く。
　　　　Ｄ入力ビットを符号レジスタ１（下位）Ｄビットに読出す
　　　　符号レジスタ１＝ゼロならば：入力からのＢビットをスタックの先頭に読出す；出力データ・ストローブ
　　　　符号計数器２Ｃ−１ならば：状態３へ行く
　　　　符号計数器＜２Ｃ−１ならば：状態７に行く
　　　　符号レジスタ１＞符号計数器〔異常な場合〕：
　　　　スタック計数値に１を加える；スタックをプッシュ
　　　　〔複製文字がすでに存在する〕
　　　　符号レジスタ→ＲＡＭアドレス
　　　　状態４へ行く
　　　　符号レジスタ１＝０および符号計数器なら〔正常な場合〕：
　　　　符号レジスタ１→ＲＡＭアドレス
　　　　状態４へ行く
状態４：「次の文字」
　　　　ＲＡＭを読出す
　　　　文字（ＲＡＭ）→出力スタック；
　　　　「プッシュ」、スタック計数器を増分する
　　　　接頭部符号（ＲＡＭ）＝非０ならば：
　　　　　　接頭部符号（ＲＡＭ）→ＲＡＭアドレス；状態４を繰返す
　　　　接頭部符号（ＲＡＭ）＝０ならば：状態５へ行く
状態５：「ストリング・テーブル更新」
　　　　符号レジスタ２＝０ならば：状態６へ行く
　　　　符号計数器２Ｃ−１ならば：状態６へ行く
　　　　その他の場合、符号計数器に＋１を加える。
　　　　符号計数器→ＲＡＭアドレス
　　　　（符号レジスタ２、スタックの先頭）をＲＡＭに書込む
　　　　状態６へ行く
状態６：「出力を発生」
　　　　ポップ；出力データ・ストローブ
　　　　スタック計数器＝非０ならば：状態６を繰返す
　　　　スタック計数器＝０ならば：状態３へ行く
状態７：「単一文字更新」
　　　　符号レジスタ２＝非０ならば：
　　　　　　符号計数器に１を加える
　　　　　　符号計数器→ＲＡＭアドレス
　　　　　　（符号レジスタ２、スタックの先頭）をＲＡＭに書込む
　　　　　　符号計数器＝２Ｃ−１ならば、：状態３へ行く
　　　　状態２へ行く
　上に与えられた状態機械記述語に関する図５の伸長装置の動作のさらに詳細な説明を次に行う。
［０］　
待ち状態
［１］　
最初の符号状態
　どのゼロ符号に関しても、この最初の符号は、Ｂビット文字信号を伴っている。従って、制御装置１５３は、スタック１６１の先頭に記憶するために経路１６２を経て伝送される最初のＢビットを読取るようにシフト回路網１５６を制御する。スタック１６１の先頭にある文字は、出力文字バス１５０を通して使用可能である。制御装置１５３は、ライン１５５を通して出力ストローブ信号を伝送することによってこの出力文字の使用可能なことを知らせる。この初めの文字が伝送されるので、それはあとの伝送に備えてスタック１６１の中に保持されない。従って、スタック計数器１８４は、ゼロ値を含むように初期設定される。初期符号を処理し終わると、制御装置１５３は、この最初のストリングをストリング・テーブルに入れるために「ゼロストリング更新状態」に入るように図５の伸長装置を制御する。
［２］　
ゼロストリング更新状態
［３］　
新符号状態
　データが使用可能な場合は、入力の次のＤビットが入力ライン１５０から符号レジスタ１５７の下位Ｄビットにシフト回路網１５６およびバス１５８を介して読込まれる。Ｄの値は、符号計数器１６０の中の現在の値に従って符号大きさ回路１５９によって決定される。
　この新符号値は、それが追加された新しい文字のついたゼロ符号ストリングであるかどうかを決めるためにゼロに対して試験される。従って、ゼロ検出器１６５が制御装置１５３にリード１７０を介して符号レジスタ１５７の内容がゼロであるかどうかを知らせる。ゼロが検出されれば、以下のアクションが行われる。入力データの次のＢビットは、シフト回路網１５６によって入力ライン１５０から読出される。そのＢビットは、バス１６２を経てスタック１６１の先頭に伝送され、ライン１５５の上の出力ストローブは、新しい正しい文字が使用できることを外部装置に知らせるように起動される。次に、検出器１６３は、符号計数器１６０の中の現存する計数値が計数器１６０のオール１の状態である２Ｃ−１に等しいかどうかを決定する。符号計数器１６０がオール１を含む場合、ＲＡＭ１７７の中のストリング・テーブルは、一杯であって、そこにはそれ以上の更新データを加えない。現在の入力符号の処理は、そのとき完了していて、伸長装置は、この「新符号状態」に再び入って、次の圧縮符号信号を処理するように制御される。しかし、符号計数器１６０が２Ｃ−１より小さい値を含む場合、受けたばかりの文字は、前に受けた符号信号の拡張としてストリング・テーブルを更新すると共に当然に新単一文字ストリングとしてそのストリング・テーブルを更新するのに用いられる。図５の伸長装置は、この更新を「単一文字更新状態」に入ることによって行う。
　符号レジスタ１５７がゼロ値を含まなかった場合、その内容は、比較器１６７を介して符号計数器１６０の中の既存の計数値と比較される。符号レジスタ１５７が符号計数器１６０より大きな値を含む場合、比較器１６７は、制御装置１５３にリード１６８を介して受取ったばかりの符号がまだストリング・テーブルに入れられていない前の符号の延長である異常な特殊の場合が起こったことを知らせる。この状態において、新符号ストリングの最終文字は、前のストリングの拡張文字に等しく、前のストリングはまた、新符号ストリングの最初の文字であり、新符号ストリングは、前のストリングの始めの文字であり、前のストリングは、復号されたばかりでスタック１６１の先頭にある文字である。従って、「プッシュ」が新ストリングに対してこの文字を保持するためにスタック１６１において実行され、スタック計数器１８４は、１だけ増分される。そのあとで、現在のストリングに対する接頭部符号である符号レジスタ１７２の中の符号信号は、バス１７６を経てＲＡＭアドレスレジスタ１６５に転送され、「次の文字状態」に入ってこのストリングの残部の正常な処理を行う。
　しかし、符号レジスタ１５７の中の値がゼロでもなく、また符号計数器１６０の中の既存の計数値より大きくもない場合、符号レジスタ１５７の中の値は、正常なストリング符号である。この符号は、符号レジスタ１５７からの符号値をバス１７１を経てＲＡＭアドレス・レジスタ１６５に転送し、そのストリングの各文字を処理し始めるために「次の文字状態」に入ることによって処理される。
［４］　
次の文字状態
　バス１８０の上の接頭部符号は、それがゼロであるかどうかを決めるためにゼロ検出器１８１によって試験される。その接頭部符号がゼロであれば、ストリング・テーブル内のアドレス指定された記憶場所は、現在のストリング内の最終バイトを含み、「更新ストリング・テーブル状態」に入ってスタック１６１の中に現在あるストリング・データの処理を完了する。その接頭部符号がゼロでなければ、接頭部ストリングは、その接頭部符号をバス１８０を通してＲＡＭアドレス・レジスタ１６５に転送して、この「次の文字状態」に再び入ることによって処理される一つ以上の文字を含んでいる。
［５］　
ストリング・テーブル更新状態
［６］　
出力作成状態
［７］　
単一文字更新状態
　次に符号計数器１６０の内容は、計数器１６０が値２Ｃ−１に達したかどうかを決めるために検出器１６３によって試験される。この値に達した場合、ストリング・テーブルは、一杯であって、それ以上の更新は、行われない。次に「次の符号状態」に入って次のストリングの処理を始める。しかし、計数器１６０の内容が２Ｃ−１より小さければ、「ゼロストリング更新状態」に入ってストリング・テーブルを受けたばかりの単一文字ストリングで更新する。
　図２〜図５に示した本発明の上述の実施例は、例えば、ディスクリートなディジタル論理部品を用いてハードウェアで実現される。表１〜４は、本発明によるデータ信号の圧縮および伸長を行うプログラム記憶式ディジタル計算機にロードするソフトウェアで実現された本発明の１実施例を示している。明確に言えば、本発明のプログラム格納計算機の実施例は、図２および図３に関して先に述べた本発明の最高性能実施例をソフトウェアで実現する。表１〜４のプログラム格納計算機の実施例はＦＯＲＴＲＡＮで実現されるので、互換性のあるＦＯＲＴＲＡＮコンパイラを備えた計算機ならどれでも実行できる。圧縮装置および伸長装置は、それぞれ入力および出力データを管理する主プログラムの中で呼出されるべきサブルーチンとして実現される。圧縮装置および伸長装置のサブルーチンは、基礎になっている計算機のワードの大きさに関係のない任意の長さで密につめられた記号の配列について取る動作と置く動作をそれぞれ行うＩＢＩＴＳＧおよびＩＢＩＴＳＰという名の文字操作サブプログラムを用いる。ＩＢＩＴＳＧおよびＩＢＩＴＳＰサブプログラムは、それぞれ等しい大きさの記号の直線配列の指定された位置にある選択されたビット長の一つの記号をそれぞれ取ったり、置いたりする。ＩＢＩＴＳＧは、圧縮装置および伸長装置サブルーチンにおいて用いるための機能サブプログラムとして実現され、ＩＢＩＴＳＰは、圧縮装置および伸長装置サブルーチンの実行において呼び出されるべきサブルーチン・サブプログラムとして実現される。表３および表４は、それぞれＩＢＩＴＳＧおよびＩＢＩＴＳＰを示す。これらのサブプログラムは、一例として与えられたものであって、等価なサブプログラムが通常の熟練した計算機プログラマによって容易に作られる。
◎【表１】
◎【表２】
◎【表３】
◎【表４】
　表１および表２にそれぞれ示した圧縮装置および伸長装置のサブルーチンは、それぞれＣＯＭＰおよびＤＥＣＯＭＰという名称である。ＣＯＭＰサブルーチンは、９ビット文字信号のストリングを１２ビット符号記号信号に圧縮し、ＤＥＣＯＭＰサブルーチンは、１２ビット符号記号信号を９ビット文字信号のストリングに伸長する。例示したサブルーチンは、３６ビットワード長を有する計算機を用いる。これらのサブルーチンは、３２ビット計算機を用いて８ビット文字で動作するように容易に変換される。ＣＯＭＰおよびＤＥＣＯＭＰは、サブルーチンとして構成されるけれども、それらは当然別々のプログラムとして等価に構成できる可能性のあることがわかる。ＦＯＲＴＲＡＮがこれらのルーチンを実施するために用いられるが、他の等価なプログラム言語を同じ効果に用いることができるであろう。
　さて、表１を参照すると、ＣＯＭＰ（ＩＢＵＦＡ，ＮＡ，ＩＢＵＦＢ，ＮＢ）サブルーチンが示されている。ＣＯＭＰサブルーチンは、配列ＩＢＵＦＡに含まれたＮＡ個の９ビット文字のブロックについてデータ圧縮を行う。ＣＯＭＰは、配列ＩＢＵＦＢの中のＮＢ個の１２ビット記号で構成された圧縮符号を作る。
　表２を参照すると、バッファＩＢＵＦＢの中に受け入れられたＮＢ個の１２ビット圧縮符号記号信号のブロックについて伸長を行い、結果として生じた回復された９ビットの文字信号を出力バッファＩＢＵＦＡにつめて、結果として生じた文字の数の計数ＮＡを戻す伸長サブルーチンＤＥＣＯＭＰ（ＩＢＵＦＢ、ＮＢ、ＩＢＵＦＡ、ＮＡ）が示されている。
　表２の伸長装置ＤＥＣＯＭＰは、それのストリング・テーブルを文１０の中に合うように寸法を与えられた４０９６ワード配列ＩＴＡＢＬＥの中に記憶する。文１１は、表２の実施例に対して９にセットされたデータ定数ＮＢＩＴＳＡを用いて出力文字信号の中のビットの数をパラメータ化する。文１２は、読出されるべき次の入力記号信号を示す入力圧縮記号計数変数ＮＣＨＢを確定する。文１２はまた、ＮＣＨＢを１に初期設定する。文１３は、出力バッファＩＢＵＦＡの中に置かれていた文字の数を示す出力文字計数変数ＮＡを確定する。文１３はまた、出力バッファの中に置かれるべき最初の出力文字を加えるときに、ＮＡを１に初期設定する。これは、文１８においてあとで説明するような方法で起る。ＩＴＡＢＬＥの中の各ストリング・テーブル記憶場所は、三つの整数の値をもつ欄で編成される。各ストリング・テーブル記憶場所は、記憶場所の内容を経て遭遇した文字のストリングをビット１〜１２にある接頭部ストリング符号、ビット１３〜２４にある接頭部ストリングの長さおよびビット２５〜３６にあるストリング拡張文字を介して記憶する。本実施例においては、このアドレスは、表１に関して上に検討した理由のために符号信号に１を加えたものである。
　文１４および１５は、すべての記憶場所が空であるということを示すようにストリング・テーブルＩＴＡＢＬＥを初期設定する。オールゼロは、プログラムする便宜上、空状態を指示するように任意に選択される。オールゼロは、適合ストリングを記憶するときに決して起り得ない不法構成である。適合ストリングがゼロの接頭部符号をもつとき、それは１の接頭部ストリング長さをもつもので、オールゼロ構成は、この初期設定の手順の間ストリング・テーブル内になされ得るだけである。
　初期処理が文１６において最初の入力符号記号を読取って、最も最近読取られた符号記号を含むために用いられる変数ＮＯＣＯＤＥの中にこのノード符号を記憶することによって始められる。文１６は、最初の入力符号記号の読取りを表３のＩＢＩＴＳＧ機能サブプログラムを用いてＩＢＵＦＢの中のＮＣＨＢ番目の１２ビット項目を入力することによって行う。文１７は、最も最近発生された文字を含むために用いられる変数ＩＣＨＡＲを定める。文１６において、ＮＯＣＯＤＥの中に置かれたばかりの値が単一文字符号であるとわかっているので、それは、文１７においてＩＣＨＡＲを満たすために直ちに用いられる。文１８は、出力バッファＩＢＵＦＡの中のこの文字をＮＢＩＴＳＡの大きさの項目のＮＡ番目のサイトに置く。文１８は、表４のＩＢＩＴＳＰサブルーチンを呼び出すことによってこの文字出力動作を行う。そのあとで、ストリング・テーブルのこのストリングの拡張によるあとでの更新に備えて、文１９は変数ＮＯＤＯＬＤの中にＮＯＣＯＤＥの中のストリング符号を保存し、文２０はＬＥＶＯＬＤの中のストリングの長さをこの最初のストリングに対する長さの既知の値と一緒に保存する。伸長処理を初期設定にこのようにしたとき、文２１において主繰返し入る。文２１は、それへのあとでの転送を行うために１００のラベルを備えている。
　主ループのはじめにおいて、文２１は、記号計数ＮＣＨＢを１だけ増分し、次に、文２２は、入力記号計数ＮＣＨＢが処理されるべき記号の番号ＮＢを超えるかどうかを決めるための試験を行う。現存の記号計数ＮＣＨＢが伸長されるべき使用可能な記号の番号より大きければ、その過程は完了であって、ＤＥＣＯＭＰがサブルーチン・リターン文５７に転送することによって終了になる。文５７は、その転送を行うためにラベル５１０を備えている。しかし、伸長されるべきそれ以上の入力データが使用可能なとき、文２３は、ＩＢＵＦＢのＮＣＨＢ番目の１２ビット位置から次の使用可能な記号を読取る。文２３は、表３のＩＢＩＴＳＧ機能サブプログラムを用いてこの動作を行う。文２３は、読取り符号記号を処理されている現存の部分ストリングの符号を保持するために用いられる変数であるＮＯＤＥＮＯの中に置く。文２４はまた、入力符号記号を最も最近の入力符号を入れておくのに用いられるＮＯＣＯＤＥに置く。文２５は、ＮＯＤＥＮＯの中の符号値を試験して、それが５１２を超えるかどうかを決め、５１２を超えれば、そのプログラムは、文２８に移って、正常な伸長過程を始める。値５１２は、図２、図３に関して前に検討した理由によって２Ｂに等しい。文２８は、それへの転送を行うためにラベル１２０を割当てられる。しかし、文２５の試験がＮＯＤＥＮＯの中の新しい記号が５１２より小さい値をもっていると決定すれば、その符号は、直接に解釈される予め割当てられた符号値の単一文字ストリングを表す。この単一文字ストリングは、接頭部ストリングの長さがゼロである。従って、文２６は、処理されているストリングの接頭部ストリング長さを保持するために作業用変数ＬＥＶＥＬを確定する。この場合にＬＥＶＥＬは、ゼロにセットされる。そのあとで、文２７は、すべての単一文字ストリングの処理が達成される場所である文４０にプログラムを転送する。文４０はそれへの転送を行うためのラベル２１０を備えている。
　文２５がラベル１２０を介して文２８への転送を行うと、新しい符号値が多重文字ストリングを表すとわかっているＮＯＤＥＮＯに常駐している。文２８は、現在のストリングがいままでのところストリング・テーブルに入っていない直前のストリングの拡張である異常な特殊な状況に対して試験する。この試験は、このストリング符号値を前に定めたことかどうかを決定するために新しい符号のストリング・テーブル記憶場所の内容を調べることによって行われる。実際には、テーブルは、上に検討したＦＯＲＴＲＡＮの必要条件を満たすためにＮＯＤＥＮＯ＋１のところにアドレス指定される。テーブル・エントリがゼロでなければ、そのストリングは、前に定められたのであって、転送が文３３に行われて正常の処理を続ける。ラベル１３０は、その転送を行うために文３３に割当てられる。しかし、文２８の試験がテーブル・エントリが空であることを決定すれば、現在の符号は、直前のストリングの拡張であるとわかる。従って、現在のストリングの接頭部ストリング長さは、前のストリング長さに等しい。従って文２９は、ＬＥＶＯＬＤの中の前のストリング長さを接頭部ストリング長さ変数ＬＥＶＥＬの中に置く。その特殊な場合には、与えられるべき最初の文字は、この現在のストリングの親文字である直前のストリングの拡張文字であるとわかり、その親文字は、直前のストリングの親文字に等しく、その親文字または変数ＩＣＨＡＲに常駐する文字である。従って、文３０は、表４のＩＢＩＴＳＰサブルーチンを呼出してＩＯＨＡＲにある既存の値を新しいストリングの終りにある記憶場所において出力バッファＩＢＵＦＡの中に置く。この記憶場所は、伸長装置によって与えられていたすべての前の文字のＮＡ計数にＬＥＶＥＬ＋１の中の接頭部ストリングの長さの値を加えたものから決定される。新ストリングの最初の文字を出力したのち、文３１は、ＮＯＤＯＬＤにある前のストリング符号を復号されるべき接頭部ストリングとしてＮＯＤＥＮＯに転送し、文３２は、ストリングを復号する場所である主ループに入るために文３４への転送を行う。ラベル２００は、文３４への転送を行うために文３４に割当てられている。
　文２８によって行われた試験が現在の符号がテーブル内に既にあるストリングを表すことを示すとき、ラベル１３０を介して文３３への正常の符号解釈経路がたどられる。ＦＯＲＴＲＡＮ　ＢＩＴＳ関数を用いる文３３は、呼出されたストリングの接頭部の長さをＮＯＤＥＮＯ＋１の内容によってアドレス指定されたＩＴＡＢＬＥの記憶場所のビット１３において始まる１２ビットから読取る。この接頭部ストリング長さは、このストリングの拡張が入れられるストリング・テーブルのあとでの更新のためにＬＥＶＥＬに保存される。
　文３４は、ＮＯＤＥＮＯ内の符号によって表された部分ストリングをその接頭部ストリングと拡張文字に分解する主ループに入る入口である。文３４は、部分ストリングが接頭部ストリングをもっているかどうかを決定するために部分ストリングの符号を５１２より大きな値に対して調べる。部分ストリングの符号が５１２より小さければ、それは単一文字によって予約された値であり、文４０への転送が行われて、この単一文字ストリングを処理して終りにする。文４０に割当てられたラベル２１０は、その転送を行うために用いられる。ＮＯＤＥＮＯが適合多重符号信号を与える継続的な場合には、それのテーブル記憶位置の内容は、ＦＯＲＴＲＡＮのＢＩＴＳ関数を用いて呼出される。従って、文３５は、ビット１３において始まる１２ビットの接頭部ストリング長さを一時変数ＩＮＤＥＸの中に保存する。文３６は、ビット２５において開始するＮＢＩＴＳＡビット拡張文字をＩＣＨＡＲに置く。文３７は、次に、表４のＩＢＩＴＳＰサブルーチンを呼出して、この文字をすべての前のストリングの合計ＮＡにＩＮＤＥＸに記憶されたこの文字に関連した接頭部ストリングの長さを加えたものを１位置越えたところでその文字の記憶場所にある出力バッファＩＢＵＦＡへ入れる。そのあとで文３８は、ＢＩＴＳ関数を用いて、呼び出された記憶場所からの１２ビット接頭部ストリング符号をＩＴＡＢＬＥに置いて、その符号のビット１で開始して、この符号値をそれ以降の処理を行うためにＮＯＤＥＮＯに入れる。このストリング分解手順は、次に文３９を介してラベル２００を用いて文３４へ逆に送り返すことによって繰返される。
　文４０は、ＮＯＤＥＮＯ内の残りの部分ストリング符号が単一文字ストリングを表すとき、処理を移す先のプログラム内の記憶場所を切分ける。文４０への転送は、各ストリングに対する処理の終りに行われる。単一文字ストリングに対する符号は、文字値であるので、文４０は、ＮＯＤＥＮＯの内容をＩＣＨＡＲに転送する。次の文４１は、表４のサブルーチンＩＢＩＴＳＰを呼出すことによってその文字を出力し、その文字を前のストリングの合計ＮＡを過ぎた最初の文字位置において出力バッファＩＢＵＦＡの中に入れる。そのあとで、このプログラムのテーブル更新段階に文４２で入って、この最終文字によって拡張された直前のストリングをストリング・テーブルに入れることができるかどうかを決定する。このプログラムのテーブル更新段階は、文４２において１に初期設定された探索された計数変数Ｎを使って前述の多重探索ハッシング手順を用いる。文４３は、ＩＣＨＡＲ内の拡張文字値およびＮＯＤＯＬＤ内の前の文字符号とからの更新を試みる場所である最初のハッシュアドレスを計算する。量１は、それを上述の理由でＦＯＲＴＲＡＮ適法テーブル記憶場所に変換するために、ハッシュアドレスに加えられ、この記憶場所アドレスはＬＯＣの中に記憶される。
　文４４および４５は、その探索サイトを調べてそれが拡張文字を記憶するのに適当であるかどうかを決定する。文４４は、拡張ストリングの記憶に使用できないあらかじめ割当てられた記憶場所１ないし５１３（符号ゼロないし５１２に対応する）の一つに当たるかどうかを決定する。ＬＯＣの中のアドレスがあらかじめ割当てられた記憶場所１ないし５１３の中の一つに対応すれば、文４６への転送が行われ、さらにハッシュアドレスを発生する。その転送は、文４６に割当てられたラベル２１８によって行われる。しかし、そのアドレスが５１３より大きければ、文４５は、ＬＯＣ記憶場所の内容を試験してその記憶場所が空であるかどうかを決定する。その探索サイトが空であれば、文５０への転送がラベル２２０を介して行われ、そのストリング・テーブルを更新する。しかし、その探索サイトが空でなければ、そのプログラムは、文４６に進んでもう一つの記憶場所のためのハッシュアドレスを計算する。文４６は、探索計数Ｎを１だけ増分し、文４７は、増分された探索計数を探索長さ限界（この実施例の場合７にセットされている）に対して試験して、それ以上の探索サイトを試みるべきかどうかを決める。探索長さ限界を越えていなかったならば、そのテーブルの中に受入れできるスペースが拡張ストリングに対して残っておらず、文５３への転送がストリング処理を終らせるために行われる。ラベル２２５がその転送を行うために文５３に割当てられる。しかし、もう１回の探索が認められれば、文４８は、ＬＯＣに対する新しいハッシュ・アドレス値をＦＯＲＴＲＡＮの必要条件を満たすために用いられたばかりの値（モジュロ４０９６）に加えられたＮＯＤＯＬＤについての第２のハッシュ関数に１を足したものにより計算する。次に文４９は、文４４への再入をラベル２１５を介して行って、その探索を再開する。
　文４５を介して適法アドレスをもつ探索サイトが空であることがわかったとき、文５０への転送が行われた。突きとめられたサイトのアドレスは、この拡張ストリングに対する表１の圧縮プログラムによって作られたものであり、従って、このアドレスは、そのストリングの符号番号として用いられる。これは、そのストリングに対する記述データを呼出された記憶場所に書込むことによって達成される。従って、文５０は、ＮＯＤＯＬＤからの接頭部ストリング符号をその記憶場所の最初の１２ビットの中に書込むためにＢＩＴＳ　ＦＯＲＴＲＡＮ関数を用いる。ＢＩＴＳ　ＦＯＲＴＲＡＮ関数を用いる文５２は、ＬＥＶＯＬＤからの接頭部ストリング長さをその記憶場所の次の１２ビットに書込み、文５１は、ＩＣＨＡＲからの拡張文字をその記憶場所の残りのビットに書込む。そのあとで、文５３〜５５において、ストリング記帳（ｂｏｏｋｋｅｅｐｉｎｇ）の終りが行われる。文５３は、ＮＯＣＯＤＥの内容をＮＯＤＯＬＤに転送し、それによってＮＯＣＯＤＥの中の最も最近読取られた符号記号を前の符号ＮＯＤＯＬＤに変換する。文５４は、この前の符号のＬＥＶＥＬ内の接頭部ストリング長さを１だけ増分して、前のストリングが次のテーブル更新の際に接頭部ストリングとして入れられるとき、前のストリングのストリング長さを与える。この接頭部ストリング長さの量は、ＬＥＶＯＬＤに記憶される。文５５は、出力文字の計数ＮＡを処理されたばかりの最終のストリングの長さであるＬＥＶＥＬ＋１の大きさだけ大きくする。ストリング記帳のこの終りが行われたのち、文５６は、ラベル１００を介して文２１への再入を行い、次の入力圧縮符号記号信号を処理する。
　文５７は、データ・ブロック処理の終りを切分ける。表２のプログラムにおいて、クリーンアップ処理は、必要ないので、制御が表２のサブルーチンＤＥＣＯＭＰを呼出した主プログラムに戻されて、入力バッファＩＢＵＦＢに記憶された圧縮符号記号信号のブロックを伸長する。
　表１ないし表４に関して説明した本発明の実施例は、ＦＯＲＴＲＡＮプログラミング言語で与えられた圧縮および伸長サブルーチンとして例示されたが、その圧縮および伸長サブルーチンは、当然に主プログラムとしてフォーマットを作ることができた。これらのプログラムは、例えばコンピュータまたはマイクロプロセッサにおいて、ソフトウェアとして用いることができるし、または、例えば、磁気ディスクまたはテープの制御装置の入出力電子回路において用いるためのＲＯＭチップの形でファームウェアとして構成してもよい。なお、ＦＯＲＴＲＡＮ以外のプログラミング言語を用いることもできるし、または同じ言語または他の言語における他のプログラムコーディングを、ここで説明した機能を行うのに用いて、本発明のデータ信号圧縮および伸長の諸手順を実施することもできる。
　マイクロプロセッサまたは他の形式のコンピュータのプログラム格納式のものが、ここで説明した能力と技術の１実施例を、すなわち、基本的データ操作の選択および状態順序づけ制御インプリメンテーションの選択における以外は、ここで述べたデジタル論理式のものと区別できない実施例を与えることが分る。汎用コンピュータにおける標準化されたデータ操作の動作を、ワイヤおよび論理ゲートの形でなく再書込みできる記憶装置に記憶されたものとしての容易に変更された形式の制御ロジックと共に作ることの経済性はによって、実行速度のある程度の相対的低下で特定の適用業務に対して経済的に作ることができ、さ細な方法で経済的に製造でき、かつ迅速に変更できる実施例を提案できる。
　本発明のハードウェア実施例に関する上述のハッシュ関数は、２０ビットの項目（１２の符号ビットと８の文字ビット）を含む符号、文字タプルを１２ビット・アドレス・スペースにマップする。ソフトウェア実施例に関して用いられたハッシュ関数は、２１ビット項目（１２符号ビットと９文字ビット）を２１ビット・アドレス・スペースにマップする。２０ビットの値および２１ビットの値のすべてが起こるわけではないので、そのようなハッシュ関数を用いることができる。上述のハッシュ関数を前に述べた基準を満たすように設計した。なお、このハッシュ関数は、その諸仮定から生ずる撞着を最小にするように設計され、第１には、幾つかの個々の入力文字がほかのものよりより頻繁に用いられ、低い番号の文字が頻繁に使われ易く、そして、第２には、幾つかの符号が他のものよりより頻繁に用いられ、早期に生ずる符号が最も頻繁に用いられるであろう。上述のものに代るハッシュ関数は、符号の左５ビットを回転することによって最初のハッシュアドレスを発生し、その文字ビットに排他的論理和演算を施して回転された符号の高位ビットにすることにより実施できる。三つの順次のアドレスが前の１２ビット・ハッシュ・アドレスにモジュロ４０９６を加えることによって発生され、新しい１２ビット番号が終端間で反転され、かつ結果として生じた番号の最下位ビットを１に強制して左３ビットを回転した符号番号を含んでいる。
　図２ないし図５に関して説明した本発明の実施例は、本発明の代りの実施例を与えるために上述のものと異なる組合わせで結合できる種々の随意選択的技術を用いる。図２および図３の圧縮装置−伸長装置は、単一文字ストリングのすべてでストリング・テーブルを初期設定するが、一方、図４および図５の圧縮装置−伸長装置は、ゼロストリングだけでストリング・テーブルを初期設定する。図２および図３については、単一文字ストリングの初期設定を単一文字そのものをこれらのストリングの符号番号として用い、２Ｂより大きいアドレスに対してのみストリング・テーブルにアクセスすることを可能にすることによって行われる。圧縮されるべき文字のすべては、Ｂビット・バイトであるから、全ての文字は、２Ｂより小さな値をもっている。従って、２Ｂより小さい符号値をもつ単一文字ストリングが図２の圧縮装置によってストリング・テーブルのアクセスなしで伝送される。図３の伸長装置において単一文字ストリングとして認識され、それによって直接伝送されてもよい。図４および図５の圧縮装置−伸長装置は、ゼロストリングだけでテーブル初期設定を行うのであって、それのストリング・テーブルをゼロないし２Ｃ−１のすべてのアドレスで呼出す。従って、図４の圧縮装置の実施例においては、単一文字ストリングが、受けた文字を符号番号ゼロでハッシュして、結果として生じたハッシュ・アドレスにあるゼロのストリング接頭部符号を入れることによってストリング・テーブルに入れられる。図５の伸長装置もまた接頭部符号ゼロを適当なストリング・テーブルの記憶場所に入れることによって単一文字のストリングを記憶する。
　このほかの変形例としては、図２および図３の圧縮装置−伸長装置は、ストリングのハッシュ・テーブル・アドレスをそれのストリング符号記号信号として割当てるが、一方、図４および図５の圧縮装置−伸長装置は、新ストリング・エントリーが作られるストリング符号記号信号を各ストリングに逐次に割当てる。
　なお別の変形例としては、図２および図３の圧縮装置−伸長装置は、固定長符号値を各ストリングに割当てるが、一方、図４および図５の圧縮装置−伸長装置は、可変する長さの符号記号を各ストリングに割当てる。図２および図３の実施例において、固定長はＣビットの全アドレス長であるが、一方図４および図５の実施例においては圧縮符号記号の長さはＣビットの長さが得られるまでデータブロックの処理の間増える。
　なお別の変形例としては、図３の伸長装置は、伸長ストリング反転を行うためのストリング長さインデクシング機構を用いるが、一方、図５の伸長装置は、この目的に後入れ先出しスタックを用いる。
　前述のように、各変形例は、図２ないし図５に開示された実施例において実施される。当業者がこれらの変形例を別途組合せて本発明の範囲内で追加の実施例を作ることができる。上述の四つの変形例の各々は、二つの可能性をもっているので、１６の別々の実施例を構成できる。例えば図４の圧縮装置に関して、逐次割当てストリング符号をＣビットの固定長出力として伝送できる。その場合、符号大きさ回路１２３を除去できる。そのような実施例においては、図５の伸長装置は、そのときやはり符号大きさ回路１５９を除くことになろう。そのような圧縮装置−伸長装置においてストリング・テーブルをゼロストリングだけで初期設定する変形例が組入れられると（図４および図５で説明したように）、図４の圧縮装置のシフト回路網１１８を用いてオールゼロの空白符号の伝送に続くＢビット・バイトと同様に固定長Ｃビット圧縮符号信号を伝送するのに用いることができる。同様にして、図５の伸長装置は、オールゼロの空白符号を受取ったのに続いて、Ｂビットバイト信号を受取るためと共に固定長Ｃビット符号信号を受け入れるためにシフト回路網１５６を用いるであろう。しかし、図４および図５の圧縮装置−伸長装置を上述のように固定長符号の変形例を含むように変更し、さらにすべての単一符号のストリングを使うストリング・テーブル初期設定を用いるように変更するとすれば、図４の圧縮装置のシフト回路網１１８を符号番号レジスタ１１９からバス１２０を通して与えられる出力と共に除去することになろう。そのような実施例においては、図５の伸長装置はそのときバス１５８を介して符号レジスタ１５７に直接に加えられる入力符号をもったシフト回路網１５６を除去するであろう。さらに、図４の符号計数器１２１をストリング・テーブル初期設定が行われたのちに、２Ｂにセットすることになり、図５の符号計数器１６０をゼロの代りに２Ｂに初期設定することになろう。なお、符号レジスタ１１６からの図４のバス１１７は、Ｂビット文字をレジスタ１１９の最下位位置に挿入するために符号番号レジスタ１１９に加えることになろう。レジスタ１１９のＣ−Ｂの最上上位位置をゼロにセットすることになろう。図４および図５の圧縮装置−伸長装置に対する上述の変更は、圧縮効率を犠牲にして性能を向上させることになろう。
　上述のことから、変更された図４のレジスタ１１６および１１９とそれらの動作との間の関係は、図２のレジスタ１７および１９とその動作との間の関係と同一であることが分る。なお、すべての単一文字ストリングを使ったテーブル初期設定を用いる変更された実施例においては、図４の比較器１３４へのゼロの値をもった入力は、用いられない。初めて遭遇する文字の単一符号ストリングを含む単一文字のストリングは、新しく遭遇した文字に対して、新しい文字に先立つオールゼロの空白符号信号を伝送するのではなく、図２に関して述べたものと同一の方法で伝送される。
　なお、すべての単一文字ストリングと固定長圧縮符号信号とでのテーブル初期設定を用いる図４および図５の変形された圧縮装置−伸長装置の実施例においては、図５の伸長装置は、多重文字ストリングまたは単一文字ストリングを受取ったかどうかを決定するために符号レジスタ１５７の内容をゼロにではなく２Ｂに比較することによって変更される。バス１６２は、符号レジスタ１５７から出されて、単一文字ストリングを直接にスタック１６１に伝送する。バス１８０の上の符号は、一つのストリングの中の最初の文字にＲＡＭ１７７のストリング・テーブルを通る逆方向トレースにおいて遭遇したときを決定するためにゼロにではなく２Ｂに比較される。ＲＡＭアドレスレジスタ１６５からスタック１６１に先頭へのバスは、図３の伸長装置に関して前述したのと同様のやり方でトレースされたストリングの最終文字をスタック１６１へ転送するように接続される。図５のゼロ検出器１７４は、この変更実施例においてもはや必要ではなくなる。レジスタに入るゼロの値をもった入力も必要なくなる。
　単一文字のストリングのすべてでストリング・テーブルを初期設定し、新しいストリング・エントリが作られるとき、ストリング符号記号を逐次に割当て、そして変化する長さの圧縮符号信号を伝送する圧縮装置−伸長装置の実施例を作りたい場合は、図４および図５の装置をそれ相応に変更できる。図４の圧縮装置は、ストリング・テーブルの初期設定が行われたのちに、符号計数器１２１を２Ｂにセットして、図５の計数器１６０をゼロの代りに２Ｂに初期設定することによって変更できる。なお、文字レジスタ１１６からの図４のバス１１７は、上述のように符号番号レジスタ１１９へ加えられる。同様に図５の伸長装置は、多重文字ストリングまたは単一文字ストリングを受取ったかどうかを決定するために符号レジスタ１５７の内容をゼロとではなく２Ｂと比較することによって変更される。なお、バス１８０の上の符号は、一つのストリング内の最初の文字にＲＡＭ１７７のストリング・テーブルを通る逆方向トレースで遭遇したときを決定するのにゼロとではなく２Ｂと比較される。この実施例においては、図５のゼロ検出器１７４もレジスタ１５７に入るゼロの値をもった入力も必要でなくなる。
　空白ストリングだけでストリング・テーブルを初期設定するように図２および図３の圧縮装置−伸長装置の実施例を変更したい場合、比較器２６は空白符号および空符号に等しいハッシュ関数アドレスを放棄するように変更される。なお、比較器３２は、文字レジスタ１７の中のＢビット文字を空白符号の伝送のあとに伝送すべきかどうかを決定するために符号番号レジスタ１９の中の値をゼロと比較するように変更される。Ｂビット文字をゼロを満たされたＣビット文字として伝送できるし、またはその代りにシフト回路網機構を前述のものと同様に用いることもできる。同様にして、図３の伸長装置は、２Ｂではなくゼロを検出するためと符号レジスタ５７を制御するためとに比較器５８を用いることによって空白符号に直接続く単一文字を伝送するように変更できる。
　上述のことから図２および図３の実施例は、圧縮効率を犠牲にして最高性能を与えることがわかるであろう。なお、図４および図５の実施例は、性能を犠牲にして最高圧縮を与える。各変形例、すなわち、全ての単一文字ストリングを用いてのテーブル初期設定；新しいストリングを作るとき逐次に割当てられるストリング符号記号；固定長符号値を伝送すること；および後入れ先出しスタックを用いるストリング反転、を組合わせる上述の変更は応用業務（アプリケーション）に従って好ましい実施例を与えることのできる最高性能と最高圧縮との間の中間のものである。ストリング反転のための図５のスタック機械化は、図３のストリング長さインデクシング機構と容易に相互交換できる。ストリング長さインデクシングを用いるとき、レベル欄は、ＲＡＭ記憶場所に追加され、図３のインデクシング機構の構成要素６１，７８，８５，８６，８８および９１が用いられる。スタック機構が用いられるとき、ＲＡＭのレベル欄は必要でなく、図５の構成要素１６１，１８４および１８５が用いられる。
　上述のように、表１〜表４は図２および図３の最高性能ハードウェア実施例の各変形例を用いる本発明のプログラム格納式コンピュータの実施例を示す。本発明の種々のソフトウェア実施例は、上述の各変形例の種々の組合せを通常の熟練したコンピュータ・プログラマによって普通に与えられるそのためのプログラムコーディングと共に用いることによって提供することができる。
　まとめると、本発明は入力データの中で観察された文字のストリングを、多分、圧縮されるべきデータブロックの始めにおいてテーブルを初期設定できる単一文字ストリングなどのストリングを除いて記憶するストリング・テーブルを用いる。それらのストリングは、各ストリングの記憶されたセットが処理されているデータの統計に適応するようにストリングが入力データの文字ストリームの中に観測されるとき、テーブルに動的に入れられる。Ｘ文字の各ストリングは、Ｘ−１文字の接頭部ストリングと一つの拡張文字とを含み、その場合に接頭部ストリングもまたテーブルの１構成要素である。各ストリングは、一つの符号記号を割当てられ、記憶されたストリングが入力データ文字ストリームの中で遭遇されると、遭遇したストリングは、圧縮データの中のその符号信号によって表される。各ストリングは、ストリングの符号記号、接頭部ストリングの符号記号、およびストリング拡張文字とによって判然とまたは暗黙裏に（すなわち、直接にまたは間接的に）、のいずれかで記憶される。データ文字信号のストリームは、各文字のストリングにそのストリームをパースすることによって処理され、各ストリングは、ストリング・テーブルの中に既に置かれている。このパーシングは、始めの文字から出発して１度に１文字ずつ分離するデータ文字ストリームの中への唯１回のパスにおいて達成される。各文字は、拡張されたストリングがストリング・テーブル内にあるものに一致する場合、前のストリングを拡張するのに用いられる。そうでなければ、その文字は、新しいストリングを開始するのに用いられる。基本的には、圧縮処理は、入力データストリームの中で各文字が出てきたとき、以下のように各文字に次々に加えられる循環ステップとして考えてもよい。
　入力データストリームからのストリングＳがストリング・テーブル内に置かれていたとする。その入力データ・ストリームの中で次に続く文字ｃに対して、そのテーブルは、拡張ストリングＳｃがその中に存在するかどうかを決定するために探索される。ストリングＳｃがそのテーブルの中に存在すれば、次に続く文字が試験されてその手続きが再び適用される。拡張ストリングがそのテーブルに存在しなければ、ストリングＳに対する符号記号が圧縮出力として伝送され、ストリングＳｃがそのテーブルに入れられる。次に文字ｃは、次のストリングの最初の文字として用いられて、その手続きは、次に続く入力文字を用いて再び適用される。
　ストリングＳｃに対する探索は、一つのストリング・テーブルアドレスを与えるために文字ｃをストリングＳに対する符号と組合せることによって行われる。拡張ストリングＳｃは、既にそのアドレスの記憶場所に記憶されていれば、そのストリングＳｃは、そのテーブルの中に存在していることになる。その記憶場所が空であれば、そのストリングは、そのテーブルの中に存在しない。その場合には、ストリングＳに対する符号記号が伝送され、ストリングＳｃが空記憶場所に入れられる。できれば、文字ｃとストリングＳに対する符号との組合せが上述の限定探索ハッシュ手順によって行われるのが好ましい。圧縮の間、圧縮手順の中の１点において定められた可能なストリングの数がストリングの実際の数およびある本質的なファクタによる経済的記憶装置の大きさを超えることになるので、ハッシュ・テーブル機械化は、あらかじめ割当てられていないストリングを記憶するのに用いられる。一般的には、ハッシュ・テーブルの各記憶場所が選択された数学的関数によって割当てられた可能な項目の割当てられたセットを含むことのできるものがハッシュ・テーブルである。前述の限定探索ハッシュ・テーブル・プロセスにおいて、各可能なアドレスが限られた数の記憶アドレスの小さなグループ内でのみ現れる。この基準は、可能なエントリを探すためまたはそれがテーブルの中にないことを定めるために必要な探索の量を限定する。
　圧縮の間ストリングが少なくともそれを識別するためのその接頭部符号を用いて検索される。伸長の間、ストリングがその符号記号によって直接に識別される。伸長装置のストリング・テーブルは、各ストリング記憶場所に接頭部ストリング符号および拡張文字を記憶し、そのストリング記憶場所は、そのストリングに対する符号によってアドレス指定可能である。従って、入力符号記号は、接頭部ストリングおよび拡張文字を与えるテーブル内で探索される。次に接頭部ストリングは新接頭部ストリングおよび新拡張文字を与えるテーブル内で探索される。この過程は始めの単一文字ストリングに出合うまで繰返される。
　本発明の上述の各実施例において、ハッシュアドレスまたは数が大きくなってゆく次々の値がストリングのための圧縮符号記号信号として用いられる。これらの値の矛盾のない変更またはアイソモルフィズムもまたそれらのストリングに対する圧縮符号記号信号として用いることができるとわかる。
　本発明の上述の実施例の若干の変形を以下のように容易にわかる設計変更を用いて行うことができる。
　本発明では、圧縮装置がディスク装置またはテープ装置のような同期チャネルに圧縮データを与えている場合、その出力速度がバッファリングを最小にするためにチャネルの入力速度に一致するように圧縮装置の速度を増減するのが望ましいことがある。圧縮装置の出力速度を達成された圧縮比によって制御し、その圧縮比は遭遇したデータの形式に従って変わる。圧縮装置が高すぎる速度で出力記号を作るように、その圧縮装置が圧縮しにくいデータに遭遇した場合、圧縮装置を入力文字の間で待機させることによって減速できる。圧縮装置が非常に圧縮しやすいデータに遭遇するので、それが出力記号をあまりゆっくり作る場合、その圧縮装置を圧縮装置の効率を減らすことによってスピードアップできる。これは、出力符号記号を必要とするときは常に、文字ストリング拡張を中止することによって行われてもよい。従って、圧縮装置が必要な出力速度を遅くするときは常に最長マッチより少ないストリングを選ぶことができる。なお、圧縮有効度は、データブロックの初期部分を処理するとき低くなり、そのブロックの処理が続くとき増加する傾向があるので、圧縮符号ストリームの転送を開始する前に圧縮を始めて圧縮速度の変化を相殺することが望ましいことがある。この待ち時間損失は、圧縮データを圧縮装置から外部装置に書込むときにのみ起こることがわかる。圧縮データを外部装置から読出すときには、圧縮データが外部信号源から使用できるようになったら直ちに伸長を開始できる。
　さらに別の変更が選択された値より小さくなるようにパースされたストリング長さを制御するために圧縮装置の一部分として計数器を用いることを含むことがある。この特徴は、圧縮データの出力速度がさらに予測しやすくなるように瞬時圧縮比の変動を小さくするであろう。なお、そのような計数器は、最大ストリング長さに敏感な伸長装置内の装置の価格を引下げるであろう。そのような装置には、図５の後入れ先出しスタック１６１のほかに、レベル・レジスタ７８および８５、アドレス加算器８６、アウトポインタ・レジスタ８８ならびに図３のＲＡＭ７５のレベル欄がある。
　本発明のさらに別の変更は、同時にではないけれども圧縮および伸長の両方に対して同じハードウェア装置のセットを用いることであることがある。圧縮および伸長の必要条件の間には、特にＲＡＭについて、同時性を失ってもよいとき、かなりの価格の節約をこの変更によって得ることができるという十分な類似性がある。なお、圧縮を実行する際に連想記憶装置をＲＡＭの代りに用いることもできよう。そのような変更は、ハッシングの必要をなくして制御の複雑さを減らす。
　【発明の効果】
　本発明は、非常に様々なデータの種類について適応性のある可逆データ圧縮および伸長をデータ統計またはデータ冗長度の形式について前もって何ら知ることなしに達成し、かつその圧縮符号の伸長を実現する方法および経済的な装置を提供する。従って、関連のデータ圧縮装置と共同して、良好な圧縮比を、最も速い今日の磁気テープおよび磁気ディスクデータ記憶装置ならびに最も速い今日の商用通信リンクと共に用いるのに適する高性能動作で達成することができる。
【図面の簡単な説明】
　【図１】
　データ文字信号のストリームのパースされた部分の略図である。
　【図２】
　最高性能を与えるように実施された本発明によるデータ圧縮装置の略ブロック図である。
　【図３】
　最高性能を与えるように実施された、図２の圧縮装置からの符号信号の圧縮ストリームを伸長するのに適応された本発明によるデータ伸長装置の略ブロック図である。
　【図４】
　最高圧縮を与えるように実施された本発明によるデータ圧縮装置の略ブロック図である。
　【図５】
　図４の圧縮装置からの符号信号の圧縮ストリームを伸長するように実施された本発明によるデータ伸長装置の略ブロック図である。
　【符号の説明】
　１３　制御装置
　１７　文字レジスタ
　１９　符号番号レジスタ
　２３　ハッシュ関数回路
　２６，３２　比較器
　２８　ＲＡＭアドレス・レジスタ
　２９　ＲＡＭ
　３５　初期設定計数器
　５３　制御装置
　５７，６４　符号レジスタ
　５８，７２　比較器
　６１　最終文字レジスタ
　６２　ＲＡＭアドレス・レジスタ
　６９　ハッシュ関数回路
　７５　ＲＡＭ
　７８，８５　レベル・レジスタ
　８１　検出器
　８６　アドレス加算器
　８８　アウトポインタ・レジスタ
　９１　加算器
　９３　初期設定計数器
　１１３　制御装置
　１１６　文字レジスタ
　１１８　シフト回路網
　１１９　符号番号レジスタ
　１２１　符号計数器
　１２３　符号大きさ回路
　１２７　ハッシュ関数回路
　１３０　ＲＡＭアドレス・レジスタ
　１３１　ＲＡＭ
　１４１　初期設定計数器
　１５３　制御装置
　１５６　シフト回路網
　１５７，１７２　符号レジスタ
　１５９　符号大きさ回路
　１６０　符号計数器
　１６１　スタック
　１６３　検出器
　１６５　ＲＡＭアドレス・レジスタ
　１６７　比較器
　１６９，１７４，１８１，１８５　ゼロ検出器
　１７７　ＲＡＭ
　１８４　スタック計数器