Veszteségmentes szövegtömörítés

Hogyan tud egy számítógép szöveget tömöríteni? Gondolj arra, hogy sokan tömörítenek szöveget nap mint nap, amikor sms-eket írnak, és nem akarnak sokat gépelni. Angol nyelven ez a szokás különösen elterjedt.

Például, ha azt szeretném írni angolul, hogy „Great, see you later!”, írhatom azt, hogy „Gr8, see u l8r!”

Ezt a szöveget úgy rövidítettem le, hogy megkerestem az ismétlődő részeket, és ezeket a részeket rövidebbekkel („8” és „u”) helyettesítettem.

A számítógépek hasonló módon tudják tömöríteni a szöveget: az ismétlődő részeket megkeresik, és rövidebb jelsorozattal helyettesítik őket. Nem kell törődniük azzal sem, mint az embereknek, hogy a végeredmény ugyanúgy hangozzon, így még jobban tudják tömöríteni a szöveget.

Próbáljuk ki ezzel az angol nyelvű William Shakespeare idézettel:

A legnyilvánvalóbb ismétlődő karaktersorozatok a „to” és a „be”, így a számítógép ezeket olyan karakterekkel is ábrázolhatja, amelyek nem részei az eredeti szövegnek, például:

Bármilyen ismétlődő karaktersorozat helyettesíthető, akkor is, ha az nem egy teljes szó, így a számítógép a „th”-t is helyettesítheti:

A számítógépnek tárolnia kell az általa elvégzett helyettesítések táblázatát is, hogy elő tudja hívni az eredetit.

Amint láthatod, vannak olyan szövegek, amelyeket jelentősen le lehet tömöríteni – több ismétlés több tömörítést jelent.

Vannak olyan szövegek, melyek egyáltalán nem tömöríthetőek, például az ábécé:

Sőt, az ábécé „tömörített” változatához több bájt is szükséges lehet, mint az eredeti változathoz, attól függően, hogy elhelyez-e az algoritmus további metaadatokat a fájlban.

🤔 Tudsz más példát is mondani olyan szövegre, amely nem lesz kisebb a tömörítéstől? És olyanokat, amelyek igazán jól tömöríthetők?

Nem baj, hogy a tömörítés nem garantálja minden esetben a kisebb fájlt. A legtöbb fájl tartalmaz ismétlődő jelsorozatokat, így a tömörítés összességében előnyös.

🔍 Ha többet szeretnél megtudni erről a tömörítési módról, nézz utána a Lempel-Ziv-Welch (LZW) algoritmusnak.

🙋🏽🙋🏻‍♀️🙋🏿‍♂️Kérdésed van a témával kapcsolatban? Szívesen válaszolunk, csak kérdezz alább, a „Kérdések” részben!