Skip to main content
LibreTexts - Ukrayinska

3: Стиснення

  1. Last updated
  2. Save as PDF
  • Page ID
    29754

    • \( \newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } \) \( \newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}} \)\(\newcommand{\id}{\mathrm{id}}\) \( \newcommand{\Span}{\mathrm{span}}\) \( \newcommand{\kernel}{\mathrm{null}\,}\) \( \newcommand{\range}{\mathrm{range}\,}\) \( \newcommand{\RealPart}{\mathrm{Re}}\) \( \newcommand{\ImaginaryPart}{\mathrm{Im}}\) \( \newcommand{\Argument}{\mathrm{Arg}}\) \( \newcommand{\norm}[1]{\| #1 \|}\) \( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\) \( \newcommand{\Span}{\mathrm{span}}\) \(\newcommand{\id}{\mathrm{id}}\) \( \newcommand{\Span}{\mathrm{span}}\) \( \newcommand{\kernel}{\mathrm{null}\,}\) \( \newcommand{\range}{\mathrm{range}\,}\) \( \newcommand{\RealPart}{\mathrm{Re}}\) \( \newcommand{\ImaginaryPart}{\mathrm{Im}}\) \( \newcommand{\Argument}{\mathrm{Arg}}\) \( \newcommand{\norm}[1]{\| #1 \|}\) \( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\) \( \newcommand{\Span}{\mathrm{span}}\)

    У главі 1 ми розглянули фундаментальну одиницю інформації, біт та різні його абстрактні зображення: булевий біт, біт схеми, керуючий біт, фізичний біт, квантовий біт та класичний біт. Наше нескінченне прагнення до вдосконалення змусило нас захотіти уявлення про окремі біти, які менші, швидші, сильніші, розумніші, безпечніші та дешевші.

    У главі 2 ми розглянули деякі питання, пов'язані з представленням складних об'єктів масивами бітів (на даний момент булевими бітами). Відображення між представленими об'єктами (символами) та масивом бітів, що використовуються для цієї мети, відоме як код. Ми, природно, хочемо, щоб коди були сильнішими і меншими, тобто, які призводять до представлення об'єктів, які є як меншими, так і менш сприйнятливими до помилок. У цьому розділі ми розглянемо методи стиснення, які можуть бути використані для генерації особливо ефективних уявлень. У розділі 4 ми розглянемо прийоми уникнення помилок.

    У розділі 2 ми розглянули системи сортування, показані на малюнку 3.1, в яких символи кодуються в бітові рядки, які транспортуються (у просторі та/або часі) в декодер, який потім відтворює оригінальні символи.

    Знімок екрана 2021-05-01 в 1.32.52 PM.png
    Малюнок 3.1: Узагальнена система зв'язку

    Зазвичай один і той же код використовується для послідовності символів, один за іншим. Роль стиснення даних полягає в перетворенні рядка бітів, що представляють послідовність символів, в коротший рядок для більш економічної передачі, зберігання або обробки. В результаті виходить система на рис. 3.2, як з компресором, так і з розширювачем. В ідеалі розширювач точно змінив би дію компресора, щоб кодер і декодер могли бути незмінними.

    На першу думку, такий підхід може здатися дивним. Чому є підстави вважати, що те ж саме

    Знімок екрана 2021-05-01 в 1.34.16 PM.png
    Малюнок 3.2: Більш досконала система зв'язку

    інформація може міститися в меншій кількості біт? Ми розглянемо два види стиснення, використовуючи різні підходи:

    • Стиснення без втрат або оборотне (що можна зробити лише в тому випадку, якщо оригінальний код був неефективним, наприклад, маючи невикористані бітові шаблони або не скориставшись тим, що деякі символи використовуються частіше, ніж інші)
    • Втрата або незворотне стиснення, при якому оригінальний символ або його закодоване подання не можуть бути реконструйовані з меншої версії точно, але замість цього розширювач виробляє наближення, яке є «досить хорошим»

    Нижче описано шість методів, які надзвичайно ефективні при стисненні файлів даних. Перші п'ять оборотні, а остання - незворотні. Кожна техніка має деякі випадки, для яких вона особливо добре підходить (найкращі випадки) та інші, для яких вона погано підходить (найгірші випадки).