Сжатие без потерь: как это работает

Мы уже разо­бра­лись с тем, как оциф­ро­вы­ва­ет­ся звук. Одна из про­блем — если каче­ствен­но его оциф­ро­вы­вать, то нам нуж­но очень мно­го дан­ных, а это зна­чит боль­шие фай­лы, боль­шой рас­ход места на дис­ке, доро­гие флеш­ки, мно­го тра­фи­ка в интер­не­те. Хочет­ся, что­бы фай­ли­ки были помень­ше.

Для это­го исполь­зу­ет­ся сжа­тие — раз­лич­ные алго­рит­мы, кото­рые тво­рят с дан­ны­ми свою магию и на выхо­де полу­ча­ют­ся дан­ные мень­ше­го объ­ё­ма.

Сжатие с потерями и без потерь

Есть два прин­ци­пи­аль­ных вида сжа­тия — с поте­ря­ми и без.

Сжа­тие с поте­ря­ми озна­ча­ет, что в про­цес­се мы лиши­лись части инфор­ма­ции. Алго­рит­мы сжа­тия с поте­ря­ми ста­ра­ют­ся сде­лать так, что­бы мы поте­ря­ли толь­ко те дан­ные, кото­рые нам не слиш­ком важ­ны.

Пред­ставь­те, что сжа­тие с поте­ря­ми — это крат­кий пере­сказ про­из­ве­де­ния из школь­ной про­грам­мы: школь­ни­ку не так важ­ны опи­са­ния при­ро­ды и автор­ский стиль, ему глав­ное сюжет. Крат­кий пере­сказ сохра­нил толь­ко важ­ное, но пере­дал это намно­го быст­рее.

Сжа­тие без потерь — это когда мы умень­ша­ем раз­мер фай­ла, при этом не теряя в каче­стве. Для это­го исполь­зу­ют­ся инте­рес­ные мате­ма­ти­че­ские при­ё­мы и коди­ро­ва­ние. Глав­ная мысль — что­бы при рас­ко­ди­ро­ва­нии все дан­ные оста­лись на месте.

Алгоритмы сжатия без потерь

Есть два основ­ных вари­ан­та: алго­ритм Хафф­ма­на или LZW. LZW исполь­зу­ет­ся повсе­мест­но, но объ­яс­нить его доволь­но слож­но, он неин­ту­и­тив­ный и тре­бу­ет целой лек­ции. Гораз­до при­ят­нее объ­яс­нить алго­ритм Хафф­ма­на.

Алго­ритм Хафф­ма­на берёт файл, раз­би­ва­ет его на фраг­мен­ты, с кото­ры­ми ему удоб­но рабо­тать, а потом смот­рит, насколь­ко часто встре­ча­ет­ся каж­дый фраг­мент. Самые частые сло­ва этот алго­ритм обо­зна­ча­ет корот­ким кодом, а самые ред­кие — кодом под­лин­нее. Так как самые частые сло­ва зани­ма­ют теперь гораз­до мень­ше места, то и гото­вый файл ста­но­вит­ся мень­ше.

Но есть и минус: ино­гда нуж­но хра­нить эту таб­ли­цу соот­вет­ствий слов и кода пря­мо в этом же фай­ле, а она может сама по себе полу­чить­ся боль­шой. Чаще все­го алго­ритм Хафф­ма­на при­ме­ня­ет­ся для сжа­тия тек­сто­вых фай­лов и видео без потерь.

Вот при­мер: берём пес­ню Beyonce — All The Single Ladies. Там есть два таких пас­са­жа:

All the single ladies
All the single ladies
All the single ladies
Now put your hands up
...
If you like it then you shoulda put a ring on it
If you like it then you shoulda put a ring on it
Don't be mad once you see that he want it
If you like it then you shoulda put a ring on it

Здесь 281 знак. Мы видим, что неко­то­рые строч­ки повто­ря­ют­ся. Зако­ди­ру­ем их:

ТАБЛИЦА СЖАТИЯ
\a\ All the single ladies
\b\ Now put your hands up
\c\ If you like it then you shoulda put a ring on it
\d\ Don't be mad once you see that he want it

ТЕКСТ ПЕСНИ
\a\ \a\ \a\ \b\

\c\ \c\ \d\ \c\

Вме­сте таб­ли­цей сжа­тия этот текст теперь зани­ма­ет 187 зна­ков — мы сжа­ли текст почти на треть бла­го­да­ря тому, что он доволь­но моно­тон­ный.

Сжатие без потерь на примере аудио

В сред­нем мину­та несжа­то­го аудио зани­ма­ет 10 мега­байт. Это доволь­но мно­го: если у вас, напри­мер, часо­вая запись кон­цер­та, то она будет зани­мать пол­ги­га­бай­та. С дру­гой сто­ро­ны, в этой запи­си захва­че­ны все нюан­сы зву­ка, есть мно­го высо­ких частот и вооб­ще кра­со­та.

Для таких ситу­а­ций исполь­зу­ют сжа­тие без потерь: оно умень­ша­ет файл в 2–3 раза, не иска­жая звук. Алго­рит­мы, кото­рые сжи­ма­ют аудио, назы­ва­ют­ся коде­ка­ми. FLAC и Apple Lossless — два попу­ляр­ных коде­ка для сжа­тия аудио без потерь.

Срав­ни­те сами раз­мер и каче­ство двух­ми­нут­но­го аудио:

Ори­ги­нал — без сжа­тия, фор­мат WAV, 23 мега­бай­та
Сжа­тие без потерь — фор­мат FLAC с теми же пара­мет­ра­ми, что и WAV, 10 мега­байт

Где ещё применяется сжатие без потерь

В архи­ва­то­рах. Зада­ча программ-архиваторов — упа­ко­вать выбран­ные фай­лы так, что­бы архив зани­мал как мож­но мень­ше места, при этом не повре­ждая то, что внут­ри. Напри­мер, тек­сто­вая вер­сия «Вой­ны и мира» может зани­мать 4 мега­бай­та, а заар­хи­ви­ро­ван­ная — 100 кило­байт, в 40 раз мень­ше.

В про­грам­ми­ро­ва­нии. Есть спе­ци­аль­ные упа­ков­щи­ки, кото­рые берут гото­вую про­грам­му и опти­ми­зи­ру­ют код так, что­бы он зани­мал мень­ше места, но сохра­нил свою рабо­то­спо­соб­ность. Напри­мер:

  • Уда­ля­ют ком­мен­та­рии
  • Сокра­ща­ют до мини­му­ма назва­ния пере­мен­ных и функ­ций
  • Уда­ля­ют сим­во­лы, кото­рые нуж­ны были чело­ве­ку для удо­бо­чи­та­е­мо­сти

Что дальше

В сле­ду­ю­щей части раз­бе­рём, как рабо­та­ет сжа­тие с поте­ря­ми и поче­му бла­го­да­ря это­му у нас есть ТикТок и Ютуб.

Сжатие без потерь — это тоже алгоритмы.
А алго­рит­мам и тому, как на них зара­ба­ты­вать, учат в Прак­ти­ку­ме. Пер­вые 20 часов — бес­плат­но.