LZW

LZW84 (Lempel-Ziv-Welch 84) je bezeztrátový kompresní algoritmus vyvinutý Abrahamem Lempelem, Jacobem Zivem a Terry Welchem. Byl publikován v roce 1984 jako vylepšení algoritmů LZ77 a LZ78 publikovaných v letech 1977 a 1978. Je relativně jednoduchý a rychlý, ale nedosahuje zdaleka tak dobré komprese jako náročnější algoritmy jako LZMA, je většinou horší než Deflate a neprovádí analýzu dat. Data prošlá algoritmem LZW84 jsou dále nekomprimovatelná, toto je rozdíl oproti algoritmu LZ77, po kterém lze data dále komprimovat pomocí algoritmu Huffman nebo podobného. Algoritmus byl až do roku 2004 zatížený patentem, dnes je patent prošlý, ale algoritmus byl mezitím překonán. Byl využíván (a je částečně dodnes) v archívech ARC a ZOO, starých verzích ZIPu (PKZIP 0.x a 1.x), unixovém komprimačním programu compress (soubory s příponou „Z“), grafickém formátu GIF a dokumentech PDF.

Popis algoritmu

Algoritmus nepotřebuje žádný slovník. Při kompresi a dekompresi si pouze vytváří pomocný seznam frází. Jedinou další informaci, kterou potřebuje znát, je seznam znaků, ze kterých si má vytvořit jednoznakový seznam frází (typicky 256 znaků ASCII). Algoritmus se tak hodí především pro síťové účely, kde ještě není znám konec přijímaných dat, ale jejich začátek už se může dekomprimovat.

Komprese

Nejdříve se do nalezených frází zapíší všechny znaky abecedy. Pro demonstraci budeme předpokládat, že má abeceda pouze znaky a, b, c a d. Poté se opakují následující kroky, dokud je na vstupu text.

  1. Na vstupu se najde nejdelší fráze, která je už zapsaná v nových frázích, a její index se zapíše na výstup.
  2. Nalezená fráze se pak ze vstupu odstraní.
  3. Jako nová fráze se pak zapíše nalezená fráze + první znak ze vstupu.
Řetězec abacdacacadaad
krok text vstupu nalezená fráze výstup nová fráze index nové fráze
a 0
b 1
c 2
d 3
1 abacdacacadaad a 0 ab 4
2 bacdacacadaad b 1 ba 5
3 acdacacadaad a 0 ac 6
4 cdacacadaad c 2 cd 7
5 dacacadaad d 3 da 8
6 acacadaad ac 6 aca 9
7 acadaad aca 9 acad 10
8 daad da 8 daa 11
9 ad a 0 ad 12
10 d d 3

Výstupem je pak řetězec 0102369803.

Dekomprese

Opět je nejprve potřeba zapsat do nových frází všechny znaky abecedy. My budeme vycházet opět z abecedy obsahující znaky a, b, c a d. Poté se opakují následující kroky, dokud je na vstupu číslo.

  1. Ze vstupu se odstraní číslo a na výstup se přidá odpovídající fráze (podle seznamu frází, které už jsou).
  2. Jako nová fráze se doplní ta z minulého kroku + první znak fráze z tohoto kroku.
Vstup 0102369803
krok vstup výstup nová fráze index nové fráze
a 0
b 1
c 2
d 3
1 0 a
2 1 b ab 4
3 0 a ba 5
4 2 c ac 6
5 3 d cd 7
6 6 ac da 8
7 9 aca aca 9
8 8 da acad 10
9 0 a daa 11
10 3 d ad 12

Výstupem je pak řetězec abacdacacadaad.

Tento postup má však jednu výjimku. Pokud je na vstupu větší číslo, než je index poslední nalezené fráze, vloží se znovu na výstup poslední výstup + jeho první znak. To samé se přidá také do nových frází...

Odkazy

Reference

V tomto článku byl použit překlad textu z článku Lempel–Ziv–Welch na anglické Wikipedii.

Související články

Externí odkazy

Read other articles:

Nat Pendleton

Untuk politikus, lihat Nathanael G. Pendleton. Nat PendletonCuplikan dari trailer untuk The Great Ziegfeld (1936)LahirNathaniel Greene Pendleton(1895-08-09)9 Agustus 1895Davenport, Iowa, Amerika SerikatMeninggal12 Oktober 1967(1967-10-12) (umur 72)San Diego, California, Amerika SerikatAlmamaterUniversitas Columbia (Sarjana)PekerjaanPemeran, pegulatTahun aktif1913–1956Suami/istriBarbara Evelyn (m.?-1967; kematiannya)Juanita Alfonzo (m.?-?) Rekam medali Gulat gaya bebas putra Me...

 

Pangian, Lintau Buo, Tanah Datar

PangianNagariNgalau Indah PangianNegara IndonesiaProvinsiSumatera BaratKabupatenTanah DatarKecamatanLintau BuoKodepos2792[1]Kode Kemendagri13.04.06.2004 Luas21,73 km²Jumlah penduduk3,367 jiwa [[Kategori:Nagari di {{{provinsi}}}]] Pangian merupakan salah satu nagari yang termasuk ke dalam wilayah kecamatan Lintau Buo, Tanah Datar, Sumatera Barat, Indonesia. Nagari ini terletak di dekat Batusangkar, ibu kota dari kabupaten Tanah Datar. Nagari Pangian adalah salah satu empat nagari...

 

Andrew Cuomo

Andrew CuomoCuomo pada September 2010 Gubernur New YorkMasa jabatan1 Januari 2011 – 24 Agustus 2021WakilRobert Duffy (2011–2014) Kathy Hochul (2015–2021) PendahuluDavid PatersonPenggantiKathy HochulJaksa Tinggi New York ke-64Masa jabatan1 Januari 2007 – 31 Desember 2010GubernurEliot SpitzerDavid Paterson PendahuluEliot SpitzerPenggantiEric SchneidermanMenteri Perumahan dan Pengembangan Perkotaan ke-11Masa jabatan29 Januari 1997 – 20 Januari 2001PresidenBil...

Orang Tiochiu

Opera Tiochiu Orang Tiochiu atau Teochew (Romanisasi Tiochiu:Diô-jiǔ-nâng) adalah sebuah subgrup Min Selatan yang dominan disamping Orang Hokkian. Orang Tiochiu merupakan salah satu kelompok Tionghoa yang banyak merantau ke berbagai tempat keluar Tiongkok.[1] Orang Tiochiu juga disebut Orang Tio-soa （Diô-soàⁿ/ Mandarin： Chaoshan）, kependekan dari dua daerah asal mereka Diô-jiǔ dan Sòaⁿ-thâu . Sejarah singkat Tempat asal mula orang Tiochiu adalah Provinsi Fujian.[...

 

2024 IIHF World Women's U18 Championship Division II

Women's ice hockey tournament 2024 IIHF World Women's U18 Championship Division IITournament detailsHost countries Netherlands BulgariaVenue(s)2 (in 2 host cities)Dates15–21 January 20248–14 January 2024Teams12← 20232025 → See also: 2024 IIHF World Women's U18 Championship The 2024 IIHF World Women's U18 Championship Division II was a pair of international under-18 women's ice hockey tournaments organized by the International Ice Hockey Federation (IIH...

 

Modern Family

Modern FamilyGenre Sitcom mockumentary Pembuat Christopher Lloyd Steven Levitan Pemeran Ed O'Neill Sofía Vergara Julie Bowen Ty Burrell Jesse Tyler Ferguson Eric Stonestreet Sarah Hyland Ariel Winter Nolan Gould Rico Rodriguez Aubrey Anderson-Emmons Jeremy Maguire Reid Ewing Penggubah lagu temaGabriel MannPenata musik Gabriel Mann Daniel Licht (episode pilot) Negara asalUnited StatesBahasa asliEnglishJmlh. musim11Jmlh. episode250 (+1 special)ProduksiProduser eksekutif Steven Levitan C...

Pittsburgh–New Castle–Weirton combined statistical area

Metropolitan area in the United States For a metropolitan area within this combined statistical area, see Greater Pittsburgh. Metropolitan Area in Pennsylvania, United StatesGreater Pittsburgh Pittsburgh, PA Metropolitan Statistical AreaMetropolitan AreaDowntown Pittsburgh seen from Mount Washington in September 2018Pittsburgh–Weirton–Steubenville, PA–OH–WV CSA   City of Pittsburgh   Pittsburgh, PA MSA   Weirton–Steubenville, OH–WV MSA  Herm...

 

Bilingual vase painting

Ancient Greek method for painting pottery Heracles resting on a couch, black-figure side of a belly amphora by the Andokides Painter, circa 520/510 BC. Munich: Staatliche Antikensammlungen. Bilingual vase painting is a special form of ancient Greek vase painting. The term, derived from linguistics, is essentially a metaphorical one; it describes vases that are painted both in the black-figure and in the red-figure techniques. It also describes the transitional period when black-figure was bei...

 

2014–15 UCI Track Cycling World Cup

Cycling competition 2014–2015 UCI Track Cycling World CupTwenty-third edition of the UCI Track Cycling World CupWorld Cup medals and jerseyDetailsDates8 November 2014 – 18 January 2015LocationMexico, United Kingdom and ColombiaRaces3← 2013–2014 2015–2016 → The 2014–2015 UCI Track Cycling World Cup was a multi-race tournament over a track cycling season. It was the 23rd series of the UCI Track Cycling World Cup organised by the Union Cycliste Internationale. The...

Toccoa, Georgia

City in Georgia, United StatesToccoa, GeorgiaCityStephens County Courthouse in ToccoaNickname: Toccoa the Beautiful[1]Motto: The Heart of Northeast Georgia[2]Location in Stephens County and the state of GeorgiaCoordinates: 34°34′29″N 83°19′12″W / 34.57472°N 83.32000°W / 34.57472; -83.32000CountryUnited StatesStateGeorgiaCountyStephensArea[3] • Total9.23 sq mi (23.90 km2) • Land9.16...

 

Apple

Fruit that grows on a tree This article is about the fruit. For the technology company, see Apple Inc. For other uses, see Apple (disambiguation). Apple tree redirects here. For other uses, see Apple tree (disambiguation). Apple 'Cripps Pink' apples Flowers Scientific classification Kingdom: Plantae Clade: Tracheophytes Clade: Angiosperms Clade: Eudicots Clade: Rosids Order: Rosales Family: Rosaceae Genus: Malus Species: M. domestica Binomial name Malus domesticaBorkh., 1803 Synonyms[...

 

List of British films of 1927

Cinema of theUnited Kingdom List of British films British horror 1888–1919 1920s 1920 1921 1922 1923 19241925 1926 1927 1928 1929 1930s 1930 1931 1932 1933 19341935 1936 1937 1938 1939 1940s 1940 1941 1942 1943 19441945 1946 1947 1948 1949 1950s 1950 1951 1952 1953 19541955 1956 1957 1958 1959 1960s 1960 1961 1962 1963 19641965 1966 1967 1968 1969 1970s 1970 1971 1972 1973 19741975 1976 1977 1978 1979 1980s 1980 1981 1982 1983 19841985 1986 1987 1988 1989 1990s 1990 1991 1992 1993 19941995...

Camandona

Camandona komune di Italia Tempat Negara berdaulatItaliaDaerah di ItaliaPiemonteProvinsi di ItaliaProvinsi Biella NegaraItalia Ibu kotaCamandona PendudukTotal309  (2023 )GeografiLuas wilayah9,2 km² [convert: unit tak dikenal]Ketinggian792 m Berbatasan denganBioglio Callabiana Pettinengo Piatto Valdilana (en) Vallanzengo Valle San Nicolao Veglio SejarahSanto pelindungGratus of Aosta (en) Informasi tambahanKode pos13821 Zona waktuUTC+1 UTC+2 Kode telepon015 ID ISTAT096009 Kode kadast...

 

المرأة في مصر القديمة

جزء من سلسلةالمرأة في المجتمع مجتمع قطاع الأعمال التعليم القوى العاملة (مجالس الإدارة) السياسة (في أستراليا) الخدمة العسكرية للمرأة في التاريخ الحقوق القانونية التاريخ جائزة نوبل حقوق الحيوانات العلوم والتكنولوجيا الطب العلوم الهندسة الحوسبة الفنون والعلوم الإنسانية ال...

 

Oxyrhynchus

City in Ptolemaic/Roman Egypt This article is about the Egyptian city. For the genus of legumes, see Oxyrhynchus (plant). For the fish, see Freshwater elephantfish. Place in Minya, EgyptOxyrhynchus البهنسا (Arabic)ⲡⲉⲙϫⲉ (Coptic)Ὀξυρρυγχος (Ancient Greek)Al-BahnasaAl-Bahnasa Martyr district, a cemetery of 5,000 prominent early Muslims during Early Muslim conquestsOxyrhynchusCoordinates: 28°31′52″N 30°38′49″E / 28.531°N 30.647...

List of premiers of British Columbia

David Eby has been premier of British Columbia since 2022. The premier of British Columbia is the first minister for the Canadian province of British Columbia. The province was a British crown colony governed by the governors of British Columbia[1] before joining Canadian Confederation in 1871.[2] Since then, it has had a unicameral Westminster-style parliamentary government, in which the premier is the leader of the party that controls the most seats in the legislative assem...

 

Apachen

Dieser Artikel beschreibt den Stamm. Zum Film siehe Apachen (Film); zu weiteren Bedeutungen siehe Die Apachen. Sigesh, eine unverheiratete Apachenfrau (Fotografie von Edward Curtis, ca. 1907) Apache-sprachige Stammesgruppen (18. Jahrhundert): Ch: Chiricahua Apache, M: Mescalero Apache, J: Jicarilla Apache, L: Lipan Apache, Pl: Plains Apache (Kiowa Apache), WA: Westliche Apache, N: Navajo (Diné) Heutige Reservationen der Apachen, Navajo (Diné) oder mit großer Apachen-Bevölkerung Als Apach...

 

Ettore Santi

Ettore Santi Deputato dell'Assemblea CostituenteGruppoparlamentarerepubblicano CircoscrizionePerugia- Terni- Rieti Sito istituzionale Dati generaliPartito politicoPRIPSI Titolo di studiodiploma di ragioneria Professioneimpiegato Ettore Santi (Spoleto, 12 marzo 1882 – Spoleto, 26 settembre 1966) è stato un politico italiano. Iscritto al Partito Repubblicano, di professione ragioniere, viene eletto come rappresentante alla Costituente nel 1946. Biografia Quarto di dieci figli,...

藤原大祐

ふじわら たいゆ藤原 大祐本名 藤原 大祐[1]別名義 TiU生年月日 (2003-10-05) 2003年10月5日（20歳）出身地 日本 東京都[2]身長 178 cm[3]血液型 AB型[2]職業 俳優ジャンル テレビドラマ・映画活動期間 2019年 -事務所 アミューズ[2]公式サイト 藤原 大祐 アミューズWEBサイト主な作品 テレビドラマ『柚木さんちの四兄弟。』映画『追想ジャーニー』配信ド...

 

Equestrian events at the 2020 Summer Paralympics

Equestrianat the XVI Paralympic GamesEquestrian pictogram of the 2020 Summer ParalympicsVenueTokyo Equestrian ParkSetagaya, Tokyo, JapanDates25–30 August 2021Competitors78 in 11 events←20162024→ Equestrian events at the 2020 Summer Paralympics in Tokyo, Japan were held at the Tokyo Equestrian Park. There were eleven gender free events taking place: ten individual events and one mixed team event. The 2020 Summer Olympic and Paralympic Games were postponed to 2021 due to the COVID-19 pan...