HK7895A - Data compression method - Google Patents

Data compression method Download PDF

Info

Publication number
HK7895A
HK7895A HK7895A HK7895A HK7895A HK 7895 A HK7895 A HK 7895A HK 7895 A HK7895 A HK 7895A HK 7895 A HK7895 A HK 7895A HK 7895 A HK7895 A HK 7895A
Authority
HK
Hong Kong
Prior art keywords
string
dictionary
data stream
strings
empty slot
Prior art date
Application number
HK7895A
Other languages
German (de)
English (en)
Inventor
Saul Miller Victor
N Wegman Mark
Original Assignee
International Business Machines Corporation
Priority date (The priority date is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the date listed.)
Filing date
Publication date
Application filed by International Business Machines Corporation filed Critical International Business Machines Corporation
Publication of HK7895A publication Critical patent/HK7895A/en

Links

Classifications

    • H—ELECTRICITY
    • H03—ELECTRONIC CIRCUITRY
    • H03M—CODING; DECODING; CODE CONVERSION IN GENERAL
    • H03M7/00—Conversion of a code where information is represented by a given sequence or number of digits to a code where the same, similar or subset of information is represented by a different sequence or number of digits
    • H03M7/30—Compression; Expansion; Suppression of unnecessary data, e.g. redundancy reduction
    • H03M7/3084—Compression; Expansion; Suppression of unnecessary data, e.g. redundancy reduction using adaptive string matching, e.g. the Lempel-Ziv method
    • H03M7/3088—Compression; Expansion; Suppression of unnecessary data, e.g. redundancy reduction using adaptive string matching, e.g. the Lempel-Ziv method employing the use of a dictionary, e.g. LZ78
    • G—PHYSICS
    • G06—COMPUTING OR CALCULATING; COUNTING
    • G06T—IMAGE DATA PROCESSING OR GENERATION, IN GENERAL
    • G06T9/00—Image coding
    • G06T9/005—Statistical coding, e.g. Huffman, run length coding

Landscapes

  • Engineering & Computer Science (AREA)
  • Theoretical Computer Science (AREA)
  • Multimedia (AREA)
  • Physics & Mathematics (AREA)
  • General Physics & Mathematics (AREA)
  • Compression, Expansion, Code Conversion, And Decoders (AREA)
  • Character Discrimination (AREA)

Claims (8)

  1. Procédé pour la compression des données des séquences individuelles dans un train de données, comprenant les étapes consistant à :    initialiser un dictionnaire constitué d'un ensemble de chaînes avec un index pour chacune desdites chaînes et comportant toutes les chaînes possibles de longueur 1 ;    établir une position d'entrée courante au commencement dudit train de données et répéter les étapes suivantes jusqu'à ce que le train de données qui doit être comprimé soit sorti ;    déterminer une chaîne S la plus longue dans ledit dictionnaire qui s'apparie avec une chaîne courante dans le train de données commençant à partir de la position d'entrée courante ;    produire un identificateur I pour S qui est constitué du codage de l'index associé à ladite chaîne la plus longue appariée S ;    avancer la position d'entrée courante à ladite chaîne courante immédiatement suivante dans le train de données ;    modifier ledit dictionnaire basé sur la chaîne précédente la plus longue appariée S, les symboles successifs immédiatement suivants dans la prochaine chaîne dans le train de données et la séquence des chaînes précédentes appariées ;    transmettre I vers un dispositif utilisateur, et    décoder I audit dispositif utilisateur pour récupérer ladite chaîne S.
  2. Procédé selon la revendication 1, dans lequel ladite étape de modification comprend les étapes consistant à :    ajouter une nouvelle chaîne S' audit ensemble, où S' constitue une concaténation dudit appariement de chaîne courante et d'un symbole immédiatement suivant dans ledit train de données, et    affecter un identificateur I' à ladite chaîne S'.
  3. Procédé selon la revendication 2, comprenant de plus l'étape consistant à :    tester un dictionnaire de volume fixe dans la mémoire contenant ledit ensemble de chaînes pour un emplacement vide afin de mémoriser ladite nouvelle chaîne S' et si la place vide n'est pas trouvée, supprimer une chaîne du dictionnaire afin de créer un emplacement vide.
  4. Procédé selon la revendication 3, dans lequel l'étape consistant à supprimer une chaîne comprend la suppression de la chaîne la moins récemment utilisée à partir du dictionnaire pour créer un emplacement vide, si aucun emplacement vide n'est trouvé.
  5. Dispositif pour la compression des données des séquences individuelles disposées en un train de données, comprenant :    un moyen pour initialiser un dictionnaire constitué d'un ensemble de chaînes avec un index pour chacune desdites chaînes et comportant toutes les chaînes possibles de longueur 1 ;    un moyen pour établir une position d'entrée courante au début dudit train de données ;    un moyen pour déterminer une chaîne la plus longue S dans ledit dictionnaire qui s'apparie à une chaîne courante dans ledit train de données commençant à partir de la position d'entrée courante ;    un moyen pour produire un identificateur I pour S constitué de l'encodage de l'index associé à ladite chaîne la plus longue appariée S ;    un moyen pour avancer la position d'entrée courante à ladite chaîne courante immédiatement suivante dans ledit train de données ;    un moyen pour modifier ledit dictionnaire basé sur la chaîne précédente appariée la plus longue S, les symboles immédiatement suivants dans la prochaine chaîne dans le train de données et la séquence des chaînes précédemment appariées ;    un moyen pour transmettre I à un dispositif utilisateur, et    un moyen pour décoder I audit dispositif utilisateur pour récupérer ladite chaîne S, et    un moyen pour répéter les étapes consistant à initialiser, établir une position d'entrée courante, produire, déterminer, avancer, modifier, transmettre et décoder jusqu'à ce que le train de données qui doit être comprimé soit sorti.
  6. Dispositif selon la revendication 5, dans lequel ledit moyen de modification comprend :    un moyen pour ajouter une nouvelle chaîne S' audit ensemble, où S' comprend une concaténation dudit appariement de chaînes courantes et d'un symbole immédiatement suivant dans ledit train de données, et    un moyen pour affecter un identificateur I' à ladite chaîne S'.
  7. Dispositif selon la revendication 6, comprenant de plus :    la mémorisation d'un dictionnaire de volume fixe contenant ledit ensemble des chaînes,    un moyen pour tester ledit dictionnaire pour un emplacement libre afin de mémoriser ladite nouvelle chaîne S', et    un moyen pour supprimer une chaîne du dictionnaire afin d'en créer une, si un emplacement vide n'est pas trouvé.
  8. Dispositif selon la revendication 7, dans lequel le moyen pour supprimer une chaîne comprend un moyen pour supprimer une chaîne la moins récemment utilisée à partir du dictionnaire pour créer un emplacement vide, si aucun emplacement vide n'est trouvé.
HK7895A 1983-06-01 1995-01-19 Data compression method HK7895A (en)

Applications Claiming Priority (1)

Application Number Priority Date Filing Date Title
US49994383A 1983-06-01 1983-06-01

Publications (1)

Publication Number Publication Date
HK7895A true HK7895A (en) 1995-01-27

Family

ID=23987404

Family Applications (1)

Application Number Title Priority Date Filing Date
HK7895A HK7895A (en) 1983-06-01 1995-01-19 Data compression method

Country Status (4)

Country Link
EP (1) EP0127815B1 (fr)
JP (1) JPS59231683A (fr)
DE (1) DE3485824T2 (fr)
HK (1) HK7895A (fr)

Families Citing this family (20)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
US4558302A (en) * 1983-06-20 1985-12-10 Sperry Corporation High speed data compression and decompression apparatus and method
JPS63209228A (ja) * 1987-02-25 1988-08-30 Oki Electric Ind Co Ltd デ−タ圧縮方法
JPS63209229A (ja) * 1987-02-25 1988-08-30 Oki Electric Ind Co Ltd デ−タ文圧縮符号化方法
US4899147A (en) * 1988-06-03 1990-02-06 Unisys Corporation Data compression/decompression apparatus with throttle, start-up and backward read controls
GB8815978D0 (en) * 1988-07-05 1988-08-10 British Telecomm Method & apparatus for encoding decoding & transmitting data in compressed form
GB8828796D0 (en) * 1988-12-09 1989-01-18 British Telecomm Data compression
DE3914589A1 (de) * 1989-05-03 1990-11-08 Bosch Gmbh Robert Verfahren zur datenreduktion bei strassennamen
US5001478A (en) * 1989-12-28 1991-03-19 International Business Machines Corporation Method of encoding compressed data
US5184126A (en) * 1989-12-28 1993-02-02 International Business Machines Corporation Method of decompressing compressed data
US5010345A (en) * 1989-12-28 1991-04-23 International Business Machines Corporation Data compression method
US5010344A (en) * 1989-12-28 1991-04-23 International Business Machines Corporation Method of decoding compressed data
US5142282A (en) * 1990-11-07 1992-08-25 Hewlett-Packard Company Data compression dictionary access minimization
US5455577A (en) * 1993-03-12 1995-10-03 Microsoft Corporation Method and system for data compression
EP0718980A1 (fr) * 1994-12-20 1996-06-26 International Business Machines Corporation Méthode de compression de données sous forme de séquences individuelles de suites d'un flux de données qui est basée sur l'utilisation d'un dictionnaire et dispositif pour la mise en oeuvre de ladite méthode
JP3426385B2 (ja) * 1995-03-09 2003-07-14 富士通株式会社 ディスク制御装置
RU2190295C2 (ru) * 1996-07-24 2002-09-27 Юнисиз Корпорейшн Система уплотнения и разуплотнения данных с непосредственным обновлением каталога, которое чередуют с поиском строк
EP1895663A3 (fr) * 2000-07-25 2008-06-11 Juniper Networks, Inc. Système et procédé pour la compression incrémentielle et continue de données
US6856651B2 (en) 2000-07-25 2005-02-15 Peribit Networks, Inc. System and method for incremental and continuous data compression
DE60134255D1 (de) 2000-07-25 2008-07-10 Juniper Networks Inc Netzwerkarchitektur und verfahren zur transparenten online-querschnittskodierung und zum transport von netzwerkkommunikationsdaten
US10210246B2 (en) 2014-09-26 2019-02-19 Oracle International Corporation Techniques for similarity analysis and data enrichment using knowledge sources

Family Cites Families (3)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
GB2060226A (en) * 1979-10-02 1981-04-29 Ibm Data compression-decompression
US4386416A (en) * 1980-06-02 1983-05-31 Mostek Corporation Data compression, encryption, and in-line transmission system
US4558302A (en) * 1983-06-20 1985-12-10 Sperry Corporation High speed data compression and decompression apparatus and method

Also Published As

Publication number Publication date
DE3485824T2 (de) 1993-03-04
DE3485824D1 (de) 1992-08-27
EP0127815A2 (fr) 1984-12-12
JPS6356726B2 (fr) 1988-11-09
EP0127815B1 (fr) 1992-07-22
JPS59231683A (ja) 1984-12-26
EP0127815A3 (en) 1988-07-27

Similar Documents

Publication Publication Date Title
US4814746A (en) Data compression method
EP0127815B1 (fr) Procédé de compression de données
US5999949A (en) Text file compression system utilizing word terminators
Miller et al. Variations on a theme by Ziv and Lempel
US5229768A (en) Adaptive data compression system
JP3278297B2 (ja) データ圧縮方法及びデータ復元方法並びにデータ圧縮装置及びデータ復元装置
US5253325A (en) Data compression with dynamically compiled dictionary
US5239298A (en) Data compression
US5384568A (en) Data compression
WO1990000837A1 (fr) Procede et appareil pour encoder, decoder et transmettre des donnees sous forme condensee
JPH09153818A (ja) データ圧縮・伸長装置
JP2531508B2 (ja) デ―タ列圧縮の方法
US8947272B2 (en) Decoding encoded data
US5610603A (en) Sort order preservation method used with a static compression dictionary having consecutively numbered children of a parent
KR100906041B1 (ko) 폰트 압축 및 검색 방법 및 장치
JP2536422B2 (ja) デ―タ圧縮装置及びデ―タ復元装置
Reznik Coding of sets of words
CN120729323A (zh) 数据压缩方法、数据解压方法、计算设备、存储介质及程序产品
JP3241787B2 (ja) データ圧縮方式
JPH0554077A (ja) 単語辞書検索装置
JPH05152971A (ja) データ圧縮・復元方法
JPH02190080A (ja) 画像符号化装置
Klein et al. Parallel Lempel Ziv Coding
JPH06326616A (ja) ハフマン復号化テーブルの構成方法
Mukherjee et al. Text compression

Legal Events

Date Code Title Description
PE Patent expired

Effective date: 20040515

PE Patent expired