Senda inn spurningu
Sólin Sólin Rís 05:12 • sest 21:41 í Reykjavík
Tunglið Tunglið Rís 00:00 • Sest 00:00 í Reykjavík
Flóð Flóð Árdegis: 08:09 • Síðdegis: 20:27 í Reykjavík
Fjaran Fjara Árdegis: 02:12 • Síðdegis: 14:14 í Reykjavík
Visit the English version

Flokkun:

Náttúruvísindi og verkfræði Tölvunarfræði

Hversu mikið er hægt að þjappa gögnum?

Hjálmtýr Hafsteinsson

Í stuttu máli er svarið að það eru engin sérstök neðri mörk á því hversu mikið hægt er að þjappa gögnum. Það er þó ekki hægt að þjappa þeim niður í ekki neitt, því að gögnin verða að komast til skila. En það fer eftir eðli gagnanna og þeim forsendum sem við gefum okkur, hversu mjög við getum þjappað.

Tökum einfalt dæmi: Við ætlum að senda aðra af tveimur textaskrám til kunningja okkar. Hvor skráin um sig er um 500 KB, segjum að önnur innihaldi allan texta Njálssögu, en hin texta Grettissögu. Ef móttakandinn veit fyrirfram að við ætlum að senda honum aðra hvora skrána, þá þurfum við ekki að senda honum alla skrána, heldur bara einn bita, þar sem 0 stendur fyrir Njálssögu, en 1 fyrir Grettissögu. Með þessu höfum við "þjappað" 500 KB skrá niður í einn bita!

Ef móttakandinn hefur ekki þessa vitneskju, það er að segja að hann veit ekkert um gögnin sem á að senda, þá náum við auðvitað ekki þessari miklu þjöppun. En athugið að ég hef í raun þjappað Njálssögu niður í 9 bókstafi með því að nota orðið "Njálssaga" um eitthvað sem er í raun um 500 KB texti! Þú sem lesandi þarft ekki að vita meira, heldur get ég vísað í sameiginlega þekkingu okkar.

En þá má kannski umorða spurninguna og spyrja hversu mikið hægt sé að þjappa gögnum án þess að nota sér sameiginlega þekkingu. Flest gagnaþjöppunarforrit á tölvum eru þannig úr garði gerð að þar er ekki notuð nein utanaðkomandi vitneskja. Þetta er gert bæði til þess að þjappaða skráin geti staðið sjálfstætt og einnig til þess að ekki verði gerðar of miklar kröfur til afþjöppunarhluta forritsins. Það væri þó ekkert úr vegi fyrir þjöppunarforrit að reyna að átta sig á því hvers konar skrár er um að ræða (til dæmis Word 2000 skrá, EXE-skrá, eða JPEG-skrá) og senda þær upplýsingar sem kóða til að ná betri þjöppun. Afþjöppunarforritið yrði þá að vita hvað hver kóði þýddi og við værum ekki með eins almenna þjöppun. Það koma til dæmis öðru hverju út nýjar útgáfur af MS Word, sem búa til skrár með annari uppbyggingu en fyrri útgáfur og þá þarf að uppfæra öll þjöppunarforrit.

Ef við skoðum eingöngu þjöppun án utanaðkomandi þekkingar, þá er hægt að skipta henni í tvo flokka eftir því hvort gögnin varðveitist öll eða tapist að einhverju leyti. Svonefnd viðsnúanleg þjöppun (e. lossless compression) varðveitir upplýsingarnar í gögnunum nákvæmlega. Við afþjöppun fæst nákvæmlega sama bitaruna og sú sem þjappað var. Tapandi þjöppun (e. lossy compression) nær fram meiri þjöppun með því að breyta upplýsingunum. Í mörgum tilfellum er óþarfi að nota nákvæmlega sömu bitarunu, því að notandinn sér lítinn eða engan mun á upphaflegu gögnunum og afþjöppuðu gögnunum. Slíkt á til dæmis við um tónlist, ljósmyndir og kvikmyndir.

Tapandi þjöppun hefur í raun engin eiginleg neðri mörk. Við getum tekið dæmi af þjöppun á stafrænni ljósmynd þar sem blár himinn þekur stórt svæði. Hægt væri að þjappa svæðinu með því að skilgreina það sem til dæmis "200x200 blátt" í stað þess að telja upp alla 40 þúsund myndpunktana á svæðinu og segja nákvæmlega hvaða tón af bláum lit þeir hefðu. Það kemur auðvitað ekki alveg sama mynd út, en ef þetta er góð nálgun þá tekur enginn eftir því. Sama má segja um tónlist. Mannseyrað hefur ákveðnar takmarkanir sem hægt er að nýta sér við þjöppun tónlistar. Til dæmis nemur eyrað ekki hvað gerist næstu millisekúndur eftir að mjög hátt hljóð heyrist. Það má því henda út heilu bútunum úr lögum án þess að nokkur heyri mun á því!

Viðsnúanlegri þjöppun er heldur þrengri stakkur skorinn, því þar má ekki einn einasti biti breytast eftir þjöppun og afþjöppun. Undir vissum kringumstæðum er þetta nauðsynlegt, til dæmis ef þjappa á keyrsluskrá (EXE-skrá). Keyrsluskrá samanstendur af skipunum sem örgjörvinn á að framkvæma og breyting á einum bita getur orðið til þess að skipunin hefur allt aðra merkingu en áður. Forritið mundi þá gefa aðra niðurstöðu eða, sem er líklegra, ekki geta lokið keyrslu. Það er óviðunandi fyrir notendur að keyrsluskrá sem hefur verið þjöppuð og síðan afþjöppuð, verki ekki lengur. Sama gildir um textaskrár, Excel-skjöl og ýmsar fleiri gerðir gagna.

Viðsnúanleg þjöppun verður því aldrei eins mikil og tapandi þjöppun. Hversu mikil þjöppunin getur orðið ræðst af eðli gagnanna. Þá skiptir mestu máli hversu mikið er af endurtekningum (e. redundancy) í gögnunum. Skoðið eftirfarandi tvær 20 stafa talnarunur:
77777777777777777777
og
35897932384626433832.
Hvora rununa er auðveldara að muna? Þá fyrri, auðvitað, því við getum lýst henni í styttra máli ("tuttugu eintök af 7"). Það virðist engin regla vera í seinni rununni og engar endurtekningar. Fyrri talnarunan þjappast því betur en sú seinni. Reyndar er til önnur lýsing á seinni rununni, "tölustafir númer 10 til 29 í pí". Sú "þjöppun" mundi reyndar nota sér utanaðkomandi þekkingu, sem er vitneskja um töluna pí.

Hægt er að prófa þetta með því að búa til eina skrá með 10 þúsund eintökum af tölustafnum 7 og aðra með fyrstu 10 þúsund tölustöfunum í pí. Hvor skrá um sig er 10.000 bæti. Þegar skránni með tölustöfum úr pí er þjappað með forritinu WinZip þá verður hún 5.209 bæti, sem er um 52% af upphaflegri stærð. En skráin með 10 þúsund eintökum af 7 fer niður í 143 bæti, sem er aðeins 1,4% af upphaflegri stærð skrárinnar. Í forritum eins og WinZip er alltaf einhver lágmarksstærð úttaksskráa, þannig að þjöppunin yrði hlutfallslega meiri eftir því sem skráin stækkaði. Til dæmis verður skrá með 100 þúsund eintökum af 7 ekki nema 247 bæti, eða 0,25% af upphaflegri stærð.

Frekara lesefni af Vîsindavefnum:

Höfundur

Hjálmtýr Hafsteinsson

Hjálmtýr Hafsteinsson

dósent í tölvunarfræði við HÍ

Útgáfudagur

11.11.2003

Spyrjandi

Sigurður Júníusson

Efnisorð

Tilvísun

Hjálmtýr Hafsteinsson. „Hversu mikið er hægt að þjappa gögnum?“ Vísindavefurinn, 11. nóvember 2003. Sótt 27. apríl 2024. http://visindavefur.is/svar.php?id=3852.

Hjálmtýr Hafsteinsson. (2003, 11. nóvember). Hversu mikið er hægt að þjappa gögnum? Vísindavefurinn. Sótt af http://visindavefur.is/svar.php?id=3852

Hjálmtýr Hafsteinsson. „Hversu mikið er hægt að þjappa gögnum?“ Vísindavefurinn. 11. nóv. 2003. Vefsíða. 27. apr. 2024. <http://visindavefur.is/svar.php?id=3852>.

Chicago | APA | MLA

Þessi síða notar vafrakökur Nánari upplýsingar

Ég samþykki
Spyrja

Sendu inn spurningu LeiðbeiningarTil baka

Hér getur þú sent okkur nýjar spurningar um vísindaleg efni.

Hafðu spurninguna stutta og hnitmiðaða og sendu aðeins eina í einu. Einlægar og vandaðar spurningar um mikilvæg efni eru líklegastar til að kalla fram vönduð og greið svör. Ekki er víst að tími vinnist til að svara öllum spurningum.

Persónulegar upplýsingar um spyrjendur eru eingöngu notaðar í starfsemi vefsins, til dæmis til að svör verði við hæfi spyrjenda. Spurningum er ekki sinnt ef spyrjandi villir á sér heimildir eða segir ekki nægileg deili á sér.

Spurningum sem eru ekki á verksviði vefsins er eytt.

Að öðru leyti er hægt að spyrja Vísindavefinn um allt milli himins og jarðar!

=

Senda grein til vinar

=

Hversu mikið er hægt að þjappa gögnum?
Í stuttu máli er svarið að það eru engin sérstök neðri mörk á því hversu mikið hægt er að þjappa gögnum. Það er þó ekki hægt að þjappa þeim niður í ekki neitt, því að gögnin verða að komast til skila. En það fer eftir eðli gagnanna og þeim forsendum sem við gefum okkur, hversu mjög við getum þjappað.

Tökum einfalt dæmi: Við ætlum að senda aðra af tveimur textaskrám til kunningja okkar. Hvor skráin um sig er um 500 KB, segjum að önnur innihaldi allan texta Njálssögu, en hin texta Grettissögu. Ef móttakandinn veit fyrirfram að við ætlum að senda honum aðra hvora skrána, þá þurfum við ekki að senda honum alla skrána, heldur bara einn bita, þar sem 0 stendur fyrir Njálssögu, en 1 fyrir Grettissögu. Með þessu höfum við "þjappað" 500 KB skrá niður í einn bita!

Ef móttakandinn hefur ekki þessa vitneskju, það er að segja að hann veit ekkert um gögnin sem á að senda, þá náum við auðvitað ekki þessari miklu þjöppun. En athugið að ég hef í raun þjappað Njálssögu niður í 9 bókstafi með því að nota orðið "Njálssaga" um eitthvað sem er í raun um 500 KB texti! Þú sem lesandi þarft ekki að vita meira, heldur get ég vísað í sameiginlega þekkingu okkar.

En þá má kannski umorða spurninguna og spyrja hversu mikið hægt sé að þjappa gögnum án þess að nota sér sameiginlega þekkingu. Flest gagnaþjöppunarforrit á tölvum eru þannig úr garði gerð að þar er ekki notuð nein utanaðkomandi vitneskja. Þetta er gert bæði til þess að þjappaða skráin geti staðið sjálfstætt og einnig til þess að ekki verði gerðar of miklar kröfur til afþjöppunarhluta forritsins. Það væri þó ekkert úr vegi fyrir þjöppunarforrit að reyna að átta sig á því hvers konar skrár er um að ræða (til dæmis Word 2000 skrá, EXE-skrá, eða JPEG-skrá) og senda þær upplýsingar sem kóða til að ná betri þjöppun. Afþjöppunarforritið yrði þá að vita hvað hver kóði þýddi og við værum ekki með eins almenna þjöppun. Það koma til dæmis öðru hverju út nýjar útgáfur af MS Word, sem búa til skrár með annari uppbyggingu en fyrri útgáfur og þá þarf að uppfæra öll þjöppunarforrit.

Ef við skoðum eingöngu þjöppun án utanaðkomandi þekkingar, þá er hægt að skipta henni í tvo flokka eftir því hvort gögnin varðveitist öll eða tapist að einhverju leyti. Svonefnd viðsnúanleg þjöppun (e. lossless compression) varðveitir upplýsingarnar í gögnunum nákvæmlega. Við afþjöppun fæst nákvæmlega sama bitaruna og sú sem þjappað var. Tapandi þjöppun (e. lossy compression) nær fram meiri þjöppun með því að breyta upplýsingunum. Í mörgum tilfellum er óþarfi að nota nákvæmlega sömu bitarunu, því að notandinn sér lítinn eða engan mun á upphaflegu gögnunum og afþjöppuðu gögnunum. Slíkt á til dæmis við um tónlist, ljósmyndir og kvikmyndir.

Tapandi þjöppun hefur í raun engin eiginleg neðri mörk. Við getum tekið dæmi af þjöppun á stafrænni ljósmynd þar sem blár himinn þekur stórt svæði. Hægt væri að þjappa svæðinu með því að skilgreina það sem til dæmis "200x200 blátt" í stað þess að telja upp alla 40 þúsund myndpunktana á svæðinu og segja nákvæmlega hvaða tón af bláum lit þeir hefðu. Það kemur auðvitað ekki alveg sama mynd út, en ef þetta er góð nálgun þá tekur enginn eftir því. Sama má segja um tónlist. Mannseyrað hefur ákveðnar takmarkanir sem hægt er að nýta sér við þjöppun tónlistar. Til dæmis nemur eyrað ekki hvað gerist næstu millisekúndur eftir að mjög hátt hljóð heyrist. Það má því henda út heilu bútunum úr lögum án þess að nokkur heyri mun á því!

Viðsnúanlegri þjöppun er heldur þrengri stakkur skorinn, því þar má ekki einn einasti biti breytast eftir þjöppun og afþjöppun. Undir vissum kringumstæðum er þetta nauðsynlegt, til dæmis ef þjappa á keyrsluskrá (EXE-skrá). Keyrsluskrá samanstendur af skipunum sem örgjörvinn á að framkvæma og breyting á einum bita getur orðið til þess að skipunin hefur allt aðra merkingu en áður. Forritið mundi þá gefa aðra niðurstöðu eða, sem er líklegra, ekki geta lokið keyrslu. Það er óviðunandi fyrir notendur að keyrsluskrá sem hefur verið þjöppuð og síðan afþjöppuð, verki ekki lengur. Sama gildir um textaskrár, Excel-skjöl og ýmsar fleiri gerðir gagna.

Viðsnúanleg þjöppun verður því aldrei eins mikil og tapandi þjöppun. Hversu mikil þjöppunin getur orðið ræðst af eðli gagnanna. Þá skiptir mestu máli hversu mikið er af endurtekningum (e. redundancy) í gögnunum. Skoðið eftirfarandi tvær 20 stafa talnarunur:
77777777777777777777
og
35897932384626433832.
Hvora rununa er auðveldara að muna? Þá fyrri, auðvitað, því við getum lýst henni í styttra máli ("tuttugu eintök af 7"). Það virðist engin regla vera í seinni rununni og engar endurtekningar. Fyrri talnarunan þjappast því betur en sú seinni. Reyndar er til önnur lýsing á seinni rununni, "tölustafir númer 10 til 29 í pí". Sú "þjöppun" mundi reyndar nota sér utanaðkomandi þekkingu, sem er vitneskja um töluna pí.

Hægt er að prófa þetta með því að búa til eina skrá með 10 þúsund eintökum af tölustafnum 7 og aðra með fyrstu 10 þúsund tölustöfunum í pí. Hvor skrá um sig er 10.000 bæti. Þegar skránni með tölustöfum úr pí er þjappað með forritinu WinZip þá verður hún 5.209 bæti, sem er um 52% af upphaflegri stærð. En skráin með 10 þúsund eintökum af 7 fer niður í 143 bæti, sem er aðeins 1,4% af upphaflegri stærð skrárinnar. Í forritum eins og WinZip er alltaf einhver lágmarksstærð úttaksskráa, þannig að þjöppunin yrði hlutfallslega meiri eftir því sem skráin stækkaði. Til dæmis verður skrá með 100 þúsund eintökum af 7 ekki nema 247 bæti, eða 0,25% af upphaflegri stærð.

Frekara lesefni af Vîsindavefnum:...