Kompresja danych
1838 Powstanie kodu Morse’a. Stworzona przez Samuela Morse’a i Alfreda Vaila metoda reprezentacji alfabetu, cyfr i znaków specjalnych za pomocą dźwięków, błysków światła, impulsów elektrycznych lub znaków popularnie zwanych kreską i kropką (1), koduje najczęściej występujące znaki, takie jak "e" lub "t" w maksymalnie skróconej postaci, co jest zalążkiem kompresji danych.
1948 Pojawienie się kodowania Shannona-Fano, techniki kompresji bezstratnej, które dla dyskretnego źródła danych znajduje kod prefiksowy, używanej m. in. w kompresorze ZIP. Nazwana na cześć Claude’a Shannona i Roberta Fano, jest nazwą nadaną dwu różnym, ale powiązanym technikom konstruowania kodu prefiksowego na podstawie zestawu symboli i ich prawdopodobieństw.
W metodzie Shannona wybierany jest kod prefiksowy, w którym symbolowi źródłowemu nadawana jest długość słowa kodowego. Metoda ta została zaproponowana w artykule Shannona "A Mathematical Theory of Communication" (1948), wprowadzającym do teorii informacji. Metoda Fano dzieli symbole źródłowe na dwa zbiory ("0" i "1") o prawdopodobieństwach zbliżonych do 1/2. Następnie te zestawy są dzielone na dwa, i tak dalej, aż każdy zestaw będzie zawierał tylko jeden symbol. Słowo kodowe dla tego symbolu jest ciągiem "0" i "1".
1952 Powstaje kodowanie Huffmana, jedna z najprostszych i łatwych w implementacji metod kompresji bezstratnej. Została opracowana przez Amerykanina Davida Huffmana. Algorytm Huffmana nie należy do najefektywniejszych obliczeniowo systemów bezstratnej kompresji danych, dlatego też w praktyce nie używa się go samodzielnie. Często wykorzystuje się go jako ostatni etap w różnych systemach kompresji, zarówno bezstratnej, jak i stratnej, np. MP3 lub JPEG. Pomimo że nie jest doskonały, stosuje się go ze względu na prostotę oraz brak ograniczeń patentowych.
Kodowanie Huffmana polega na utworzeniu słów kodowych (ciągów bitowych), których długość jest odwrotnie proporcjonalna do prawdopodobieństwa. Tzn. im częściej dany symbol występuje (może wystąpić) w ciągu danych, tym mniej zajmie bitów (trochę na podobnej zasadzie, co kod Morse’a).
Lata 70. XX wieku - 1998 Niemiecki profesor Dieter Seitzer (2) z niemieckiego Instytutu Fraunhofera postanowił opracować nowy sposób przesyłania dźwięku za pośrednictwem sieci telefonicznej. Chciał przy tym, żeby przesyłany dźwięk był w zakresie co najmniej 20 Hz do 20 kHz, bez żadnych słyszalnych zniekształceń i na dodatek stereofoniczny. Próbował nawet swój pomysł opatentować, ale Urząd Patentowy odmówił, uznając go za niewykonalny. Choć więc ówczesna technologia nie pozwalała na realizację tak zaawansowanych projektów, Seitzer postanowił udowodnić słuszność swojego pomysłu. Jego realizację zlecił doktorantowi Karlheinzowi Brandenburgowi.
W roku 1986 Brandenburg w swojej pracy doktorskiej zawarł pomysł, aby w zapisie piosenek lub symfonii pominąć te składniki, które są maskowane przez inne głośniejsze dźwięki i nasz mózg ich nie odbiera. Za kluczową datę powstania formatu przyjmuje się rok 1991. Przy tworzeniu jego pierwszej implementacji wykorzystywany był m.in. utwór Suzanne Vegi "Tom’s Diner". W 1992 roku wynalazek otrzymał nazwę MPEG Audio Layer-3, lepiej znaną jako MP3. Popularność format zaczął zdobywać pod koniec lat 90-tych. W 1998 pojawił się pierwszy odtwarzacz muzyki MP3.
1977 Opracowanie algorytmu Lempel-Ziv 77, którego nazwa skracana jest zwykle do LZ77. Algorytm został przedstawiony przez Abrahama Lempela oraz Jacoba Ziva (3) i opisany w artykule "A universal algorithm for sequential data compression opublikowanym w IEEE Transactions on Information". Rok później autorzy opublikowali ulepszoną wersję metody, znaną pod nazwą LZ78. To metoda strumieniowej słownikowej kompresji danych.
Metoda LZ77 wykorzystuje fakt, że w danych powtarzają się ciągi bitów (np. w tekstach naturalnych będą to słowa, frazy lub całe zdania). Kompresja polega na zastępowaniu powtórzonych ciągów o wiele krótszymi liczbami wskazującymi, kiedy wcześniej wystąpił ciąg i z ilu bitów się składał. Algorytm LZ77 jest wolny od wszelkich patentów, co w dużej mierze przyczyniło się do jego popularności i szerokiego rozpowszechnienia. Doczekał się wielu ulepszeń i modyfikacji, dających lepsze współczynniki kompresji albo dużą szybkość działania. Na LZ77 opiera się m.in. algorytm deflate, używany jest również w formatach ZIP, gzip, ARJ, RAR, PKZIP, a także PNG.
1972–92 Termin "JPEG" jest skrótem nazwy organizacji Joint Photographic Experts Group, która stworzyła ten standard kompresji w 1992 roku. Podstawą JPEG jest dyskretna transformata kosinusowa (DCT), technika stratnej kompresji obrazu, która została po raz pierwszy zaproponowana przez Nasira Ahmeda w 1972 r. Prace nad standardem rozpoczęły się w kwietniu 1983 roku w organizacji ISO.
W 1991 r. powstał standard o nazwie ISO/IEC IS 10918-1, który definiował podstawowy, sekwencyjny tryb kompresji stratnej, oparty na dyskretnej transformacji kosinusowej (DCT) oraz jego różne rozszerzenia. Opublikowany standard JPEG nie opisywał dokładnych implementacji algorytmów kompresji i nie określał też dokładnego formatu plików graficznych (4), zdefiniowano tylko podstawy znane pod nazwą JPEG Interchange Format. W rezultacie największą popularność uzyskał wprowadzony przez firmę C-cube Microsystems format JFIF (ang. JPEG File Interchange Format), stanowiący rozszerzenie wobec standardu i posługujący się rozszerzeniem "jpeg" albo "jpg", dlatego często błędnie identyfikowany ze standardem JPEG.
1984 Powstanie LZW (Lempel-Ziv-Welch), metody strumieniowej bezstratnej kompresji słownikowej. Pomysłodawcą algorytmu jest Terry A. Welch. Metodę opisał w 1984 roku, w artykule "A technique for high-performance data compression", opublikowanym w "Computer". Wykorzystywany jest m.in. w programach ARC, PAK i UNIX-owym compress, w formacie zapisu grafiki GIF, w formatach PDF i PostScript (filtry kodujące fragmenty dokumentu) oraz w modemach (V.42bis).
1986 Początki TIFF (ang. Tagged Image File Format), formatu plików graficznych. Został opracowany w 1986 roku przez Aldus Corporation, w porozumieniu z Microsoft i Hewlett-Packard. Prawa do formatu należą obecnie do spółki Adobe Systems, w których posiadanie weszła przez przejęcie Aldus. Format ten powstał z myślą o wykorzystaniu przez PostScript, pierwotnie dla programu PageMaker. Jest to de facto standard w DTP. Format TIFF przechowuje informacje o kanałach alfa, ścieżkach, profilu kolorów, komentarzach, umożliwia także zapisywanie dokumentów wielostronicowych. TIFF pozwala na kompresję LZW, format CCITT (Consultative Committee for International Telegraphy & Telephony), PackBits Apple’a i ZIP. Od rewizji TIFF 6.0 możliwa jest kompresja JPEG.
1987 Narodziny GIF (ang. Graphics Interchange Format), formatu pliku graficznego z kompresją bezstratną. Został stworzony przez firmę CompuServe. Pliki tego typu są powszechnie używane na stronach WWW, gdyż pozwalają na tworzenie prostych animacji ze zdefiniowanym kolorem tła jako przezroczystym i określonym opóźnieniem przy odtwarzaniu poszczególnych klatek animacji (5). Ze względu na to, iż do kompresji w formacie GIF może być używany algorytm LZW, na którym ciążą patenty w kilku krajach świata, w 1995 został opracowany konkurencyjny format PNG używający do kompresji algorytmu deflate.
1988–2020 Pierwsze spotkanie grupy roboczej ISO/IEC o nazwie MPEG (ang. Moving Picture Experts Group) zajmującej się rozwojem standardów kodowania audio i wideo (6). Jej celem było opracowanie standardu kodowania wideo wraz z dźwiękiem. Rozwój technik kompresji był konieczny, gdyż np. każda sekunda obrazu PAL składającego się z 25 klatek na sekundę, 720 punktów w poziomie i 576 punktów w pionie, z których każdy ma kolor opisany 24 bitami, miała prawie 29,2 megabajtów, zaś 1,5-godzinny film - ponad 156 gigabajtów, czyli do jego zapisania potrzebne byłyby 224 płyty CD! W 1991 opracowano oficjalną specyfikację standardu MPEG-1. Obraz (7) ma w nim rozdzielczość 352x240 punktów i jest wyskalowany do odtwarzania pełnoekranowego, a przepustowość wynosi 1,5 Mb/s.
Trzecia warstwa standardu MPEG-1 dotyczy kodowania dźwięku i jest wykorzystywana w MP3. W roku 1994 pojawiła się specyfikacja standardu MPEG-2, w którym maksymalna rozdzielczość obrazu wynosi 1920x1152 punktów, a prędkość transferu waha się między 3 a 13 Mb/s. MPEG-3 został oryginalnie zaprojektowany dla HDTV, porzucono go jednak, gdy okazało się, że format MPEG-2 jest dla telewizji wysokiej rozdzielczości wystarczający. MPEG-4 jest przystosowany głównie do kompresji danych strumieniowych (wideokonferencje), dlatego posiadał zaimplementowane funkcje chroniące przed błędami przesyłu. Część trzecia standardu MPEG-4 opisuje kodek audio AAC.
Część dziesiąta opisuje jeszcze wydajniejszy algorytm kompresji, nazwany AVC - Advanced Video Coding. Inne opracowane przez grupę standardy to także MPEG-7 do opisu danych multimedialnych, umożliwiający zapis informacji o cechach obrazu: kształtach, kolorach, teksturach i MPEG-21, przyszłościowy standard do standaryzacji treści multimedialnych. Grupa opracowała też wiele standardów dla treści cyfrowych i multimedialnych od opracowanego w 2007 r. MPEG-A po wydanie w 2020 standardu dla mediów immeryswnych - MPEG-I.
1989 Data stworzenia ZIP (8), jednego z najczęściej używanych formatów kompresji bezstratnej i archiwizacji danych na platformie PC, zwłaszcza w środowisku Windows Microsoftu. Format ten został zaprojektowany w 1989 roku przez Phila Katza, założyciela firmy PKWare, i wydany w formie programu PKZIP, obsługującego ten format kompresji i archiwizacji.
Format ZIP był bardziej odporny na utratę danych dzięki przechowywaniu katalogu pliku w kilku miejscach, jak i był również bardziej elastyczny, zapewniając dodatkowe, opcjonalne metody kompresji i/lub szyfrowania i możliwość dalszego rozwoju formatu, nie wpływając istotnie na samą jego strukturę.
Program PKZIP był szybszy i wydajniejszy od wcześniej stosowanego ARC, wobec czego PKZIP szybko zyskał na popularności i ostatecznie wyparł format ARC. Obecnie jest to najbardziej rozpowszechniony standard wśród programów do kompresji. Ponadto, począwszy od systemu operacyjnego Windows ME, obsługa archiwów ZIP została wcielona do obsługi systemowej. Pojedynczy plik ZIP może zawierać jeden lub więcej plików oraz folderów z opcjonalną kompresją.
W obecnej wersji formatu dostępnych jest kilkanaście algorytmów kompresji, m.in. deflate, bzip2, LZMA, DCL, Implode, WavPack. Format ZIP jest też używany przez wiele programów jako nośnik danych rozbitej na dużą liczbę elementów większej logicznej struktury. Za przykład takiego zbiornika danych mogą posłużyć np. dokumenty OpenOffice, archiwa JAR, czy dodatki do programu Firefox. Na początku lat 90-tych, gdy systemy Windows zyskiwały na popularności, przydatne okazywały się różnorakie graficzne nakładki na oryginalny program PKZIP, najbardziej znaną jest WinZip - którego popularność znacznie przyćmiła opublikowanie PKZIP w wersji dla Windows.
1993 Pojawia się RAR (od ang. Roshal archive), format bezstratnej kompresji danych (9), stworzony przez Rosjanina Jewgienija Roszała. Używa odmiany kompresji LZSS, który jest ulepszonym wariantem metody LZ77.
Format zapewnia tworzenie i obsługę archiwów ciągłych, danych i woluminów naprawczych, ochronę spójności danych poprzez sumę kontrolną opartą o kryptograficzną funkcję hashującą BLAKE2 oraz szyfrowanie algorytmem AES-256 w trybie CBC dla formatu RAR 5.0 i AES-128 dla formatu RAR 4.x.
M.U.
