Difference between revisions of "Compression"

From Data Crystal
Jump to: navigation, search
(spam revert)
Line 7: Line 7:
  
 
Here is an example of RLE. Given the data
 
Here is an example of RLE. Given the data
:<tt>4B 68 61 61 61 61 61 61 61 6E 21</tt>
+
:<tt>4B 68 61 61 61 61 61 61 61 6E 21</tt>
 
a naive implementation of RLE might compress it as follows. The run-length bytes are shown in '''bold'''.
 
a naive implementation of RLE might compress it as follows. The run-length bytes are shown in '''bold'''.
:&#060;tt&#062;4B '''01''' 68 '''01''' 61 '''07''' 6E '''01''' 21 '''01'''&#060;/tt&#062;
+
:<tt>4B '''01''' 68 '''01''' 61 '''07''' 6E '''01''' 21 '''01'''</tt>
 
The string of 61s has been shrunk, but the one-byte "runs" have doubled in size, making the compressed data almost as long as the original. If it is known that the original data never uses the most significant bit (i.e. every byte is in the range of 00-7F), then this can be improved by using that bit to indicate a run, eliminating the need to store the length for single bytes. Now the data will become
 
The string of 61s has been shrunk, but the one-byte "runs" have doubled in size, making the compressed data almost as long as the original. If it is known that the original data never uses the most significant bit (i.e. every byte is in the range of 00-7F), then this can be improved by using that bit to indicate a run, eliminating the need to store the length for single bytes. Now the data will become
:&#060;tt&#062;4B 68 E1 '''07''' 6E 21&#060;/tt&#062;
+
:<tt>4B 68 E1 '''07''' 6E 21</tt>
 
which is almost half the original size.
 
which is almost half the original size.
  
Line 36: Line 36:
 
LZSS is sometimes confused with LZ77, an older compression type that it is based on. LZ77 did not use flag bytes, instead the compressed data just alternated between bytes and references.
 
LZSS is sometimes confused with LZ77, an older compression type that it is based on. LZ77 did not use flag bytes, instead the compressed data just alternated between bytes and references.
  
LZSS works well for large blocks of data, but poorly for small blocks due to the lack of repetition. It is often used for graphics, tiles, and maps. [[Chrono Trigger]] uses LZSS, as does the standard [[Nintendo Game Boy Advance|GBA]] compression  
+
LZSS works well for large blocks of data, but poorly for small blocks due to the lack of repetition. It is often used for graphics, tiles, and maps. [[Chrono Trigger]] uses LZSS, as does the standard [[Nintendo Game Boy Advance|GBA]] compression format.
  
<div style="overflow:auto;height:1px;">
+
==Super Mario World==
Excuse for my post but I do not have money to buy meal to my children. Forgive me please.
+
[[Super Mario World]] uses a very "ad-hoc" compression format, with 5 different commands. Variations of it are used in many other SNES games by Nintendo, such as [[Yoshi's Island]], [[Super Mario Kart]], and [[EarthBound]].
[http://hrentut.org/games/motivational-games.html motivational games]
+
 
[http://hrentut.org/girls/young-sweet-girls.html young sweet girls]
+
==See also==
[http://hrentut.org/dogs/history-of-dogs.html history of dogs]
+
*[[Wikipedia:Data compression]]
[http://hrentut.org/adult/michigan-adult-clubs.html michigan adult clubs]
 
[http://hrentut.org/home/microsoft-windows-xp-home-edition-japanese-language-download.html microsoft windows xp home edition japanese language download]
 
[http://hrentut.org/job/preemployment-job-verification-specialists.html preemployment job verification specialists]
 
[http://hrentut.org/dogs/free-dogs.html free dogs]
 
[http://hrentut.org/auto/vip-auto.html vip auto]
 
[http://hrentut.org/music/free-hindi-music-downloading.html free hindi music downloading]
 
[http://hrentut.org/music/caitlin-corbett--music.html caitlin corbett  music]
 
[http://hrentut.org/dogs/hog-catch-dogs.html hog catch dogs]
 
[http://hrentut.org/dogs/hog-dogs-for-sale.html hog dogs for sale]
 
[http://hrentut.org/dogs/hog-dogs.html hog dogs]
 
[http://hrentut.org/music/rich-mullins-sheet-music.html rich mullins sheet music]
 
[http://hrentut.org/adult/adult-entertainment-in-jacksonville-fla-.html adult entertainment in jacksonville fla ]
 
[http://hrentut.org/college/st-joseph-s-college-suffolk.html st joseph s college suffolk]
 
[http://hrentut.org/adult/free-adult-catalog.html free adult catalog]
 
[http://hrentut.org/car/discount-car-rental-honolulu.html discount car rental honolulu]
 
[http://hrentut.org/games/download-playstation-games.html download playstation games]
 
[http://hrentut.org/furniture/tony-s-furniture-troy-nc.html tony s furniture troy nc]
 
[http://hrentut.org/furniture/french-provincial-furniture.html french provincial furniture]
 
[http://hrentut.org/sex/sex-gadgets.html sex gadgets]
 
[http://hrentut.org/estate/las-vegas-real-estate-agents.html las vegas real estate agents]
 
[http://hrentut.org/home/sharpe-spray-gun-home-page.html sharpe spray gun home page]
 
[http://hrentut.org/air/vortox-air-filters.html vortox air filters]
 
[http://hrentut.org/music/music-sounds.html music sounds]
 
[http://hrentut.org/dogs/home-remedy-for-garden-repellent-for-dogs-and-cats.html home remedy for garden repellent for dogs and cats]
 
[http://hrentut.org/home/home-made-spells.html home made spells]
 
[http://hrentut.org/dogs/home-security-dogs.html home security dogs]
 
[http://hrentut.org/home/stevie-wonder-home.html stevie wonder home]
 
[http://hrentut.org/sex/pics-of-sex-postions.html pics of sex postions]
 
[http://hrentut.org/game/world-cup2006-fantasy-game.html world cup2006 fantasy game]
 
[http://hrentut.org/sex/sex-slave-torture.html sex slave torture]
 
[http://hrentut.org/estate/real-estate-in-mn.html real estate in mn]
 
[http://hrentut.org/dog/how-to-tell-if-your-dog-is-pregnant.html how to tell if your dog is pregnant]
 
[http://hrentut.org/car/herts-car-rental.html herts car rental]
 
[http://hrentut.org/dogs/hoodles-of-dogs.html hoodles of dogs]
 
[http://hrentut.org/estate/norris-real-estate.html norris real estate]
 
[http://hrentut.org/dogs/hopkinton-ma-sheep-dogs.html hopkinton ma sheep dogs]
 
[http://hrentut.org/games/free-online-games-largest-shooter.html free online games largest shooter]
 
[http://hrentut.org/sex/lunasarabella-email-sex-couple-network.html lunasarabella email sex couple network]
 
[http://hrentut.org/girls/girls-and-hand-jobs.html girls and hand jobs]
 
[http://hrentut.org/cheats/call-of-duty--finest-hour-cheats.html call of duty  finest hour cheats]
 
[http://hrentut.org/estate/real-estate-sale-prescott-arizona.html real estate sale prescott arizona]
 
[http://hrentut.org/girl/sexy-cartoon-girl-desktops.html sexy cartoon girl desktops]
 
[http://hrentut.org/games/getting-what-you-both-want-without-playing-games.html getting what you both want without playing games]
 
[http://hrentut.org/estate/closing-costs-for-real-estate-sale-illinois.html closing costs for real estate sale illinois]
 
[http://hrentut.org/html/basic-html-codes.html basic html codes]
 
[http://hrentut.org/dogs/hot-dogs-at-wedding-receptions.html hot dogs at wedding receptions]
 
[http://hrentut.org/jobs/jobs-and-southpole.html jobs and southpole]
 
[http://hrentut.org/cheats/midnight-club-2-cheats.html midnight club 2 cheats]
 
[http://hrentut.org/sex/kamatari-sex.html kamatari sex]
 
[http://hrentut.org/adult/free-adult-online-flash-games.html free adult online flash games]
 
[http://hrentut.org/car/the-best-car-for-the-best-price.html the best car for the best price]
 
[http://hrentut.org/sex/sex-christians-honeymoon.html sex christians honeymoon]
 
[http://hrentut.org/furniture/colibre-furniture.html colibre furniture]
 
[http://hrentut.org/girls/marydale-catholic-school-for-girls-indianapolis-indiana.html marydale catholic school for girls indianapolis indiana]
 
[http://hrentut.org/gay/gay-gods.html gay gods]
 
[http://hrentut.org/furniture/brandon-furniture-store.html brandon furniture store]
 
[http://hrentut.org/home/home-beer-brew-kit.html home beer brew kit]
 
[http://hrentut.org/football/english-football-live-songs.html english football live songs]
 
[http://hrentut.org/auto/paper-auto-floor-mats.html paper auto floor mats]
 
[http://hrentut.org/dogs/hotels-chantilly--va--dogs.html hotels chantilly  va  dogs]
 
[http://hrentut.org/sex/bizzaro-sex.html bizzaro sex]
 
[http://hrentut.org/college/rank-philadelphia-college-of-osteopathic-medicine-pschology.html rank philadelphia college of osteopathic medicine pschology]
 
[http://hrentut.org/music/mexico-music-and-art.html mexico music and art]
 
[http://hrentut.org/hotels/belfast-hotels.html belfast hotels]
 
[http://hrentut.org/music/html-codes-for-music-on-page.html html codes for music on page]
 
[http://hrentut.org/air/air-vice-marshalls.html air vice marshalls]
 
[http://hrentut.org/college/wilson-community-college-north-carolina.html wilson community college north carolina]
 
[http://hrentut.org/cheats/pokemon-cheats-game-boy-advance.html pokemon cheats game boy advance]
 
[http://hrentut.org/dogs/house-dogs.html house dogs]
 
[http://hrentut.org/furniture/lawn-furniture-tables.html lawn furniture tables]
 
[http://hrentut.org/games/freeware-games-kids.html freeware games kids]
 
[http://hrentut.org/dog/greek-dog.html greek dog]
 
[http://hrentut.org/air/air-rifles--springer-.html air rifles  springer ]
 
[http://hrentut.org/music/music-file-conversions.html music file conversions]
 
[http://hrentut.org/game/cheap-dropshipping-game-video-wholesale.html cheap dropshipping game video wholesale]
 
[http://hrentut.org/home/home-business-opportunity-canada.html home business opportunity canada]
 
[http://hrentut.org/estate/caldwell-idaho-real-estate.html caldwell idaho real estate]
 
[http://hrentut.org/games/white-wolf-games.html white wolf games]
 
[http://hrentut.org/home/heartland-home-care---hospice.html heartland home care  hospice]
 
[http://hrentut.org/jobs/part-time-home-jobs.html part time home jobs]
 
[http://hrentut.org/dogs/how-are-dogs-related-to-wolves.html how are dogs related to wolves]
 
[http://hrentut.org/job/job-opportunity-in-hawaii.html job opportunity in hawaii]
 
[http://hrentut.org/music/teenage-music-purchase-trends-preipod.html teenage music purchase trends preipod]
 
[http://hrentut.org/gay/gay-sex-artist.html gay sex artist]
 
[http://hrentut.org/auto/auto-blog.html auto blog]
 
[http://hrentut.org/air/last-minute-deals-air.html last minute deals air]
 
[http://hrentut.org/dog/dog-repellents.html dog repellents]
 
[http://hrentut.org/football/lawrence-o-toole--football.html lawrence o toole  football]
 
[http://hrentut.org/home/home-improvement-companies-in-toledo.html home improvement companies in toledo]
 
[http://hrentut.org/girl/normal-obs-for-a-3-yr-old-girl.html normal obs for a 3 yr old girl]
 
[http://hrentut.org/car/japanese-car-sterios.html japanese car sterios]
 
[http://hrentut.org/home/steps-to-buying-a-home.html steps to buying a home]
 
[http://hrentut.org/dogs/how-do-dogs-see.html how do dogs see]
 
[http://hrentut.org/music/garage-music-haverfordwest.html garage music haverfordwest]
 
[http://hrentut.org/girls/horny-girls.html horny girls]
 
[http://hrentut.org/dogs/how-do-dogs-sleep.html how do dogs sleep]
 
[http://hrentut.org/hotels/red-sea-hotels.html red sea hotels]
 
[http://hrentut.org/estate/real-estate-research.html real estate research]
 
[http://hrentut.org/home/home-made-gate-latch.html home made gate latch]
 
[http://hrentut.org/jobs/sports-and-entertainment-marketing-jobs.html sports and entertainment marketing jobs]
 
[http://hrentut.org/jobs/what-kind-of-jobs-can-i-get-with-a-psychology-degree-.html what kind of jobs can i get with a psychology degree ]
 
[http://hrentut.org/adult/adult-group-activities.html adult group activities]
 
[http://hrentut.org/estate/real-estate-mortgage-form.html real estate mortgage form]
 
[http://hrentut.org/home/starband-360-home-network.html starband 360 home network]
 
[http://hrentut.org/sex/haunted-house-on-sex-hill-thor.html haunted house on sex hill thor]
 
[http://hrentut.org/dogs/how-does-a-hairball-cough-sound-in-dogs.html how does a hairball cough sound in dogs]
 
[http://hrentut.org/sex/lesbian-sex-comic.html lesbian sex comic]
 
[http://hrentut.org/sex/sex-bratislava.html sex bratislava]
 
[http://hrentut.org/air/compressed-air-powered-vehicle.html compressed air powered vehicle]
 
[http://hrentut.org/girl/southern-oaks-girl-school.html southern oaks girl school]
 
[http://hrentut.org/girl/renoir---young-girl-in-pink--cma.html renoir  young girl in pink  cma]
 
[http://hrentut.org/estate/discount-real-estate-listing-in-phoenix-az.html discount real estate listing in phoenix az]
 
[http://hrentut.org/estate/real-estate-in-arkansasbentonville.html real estate in arkansasbentonville]
 
[http://hrentut.org/dogs/how-dogs-evolved-from-wolves.html how dogs evolved from wolves]
 
[http://hrentut.org/girls/gorgeous-page-3-girls.html gorgeous page 3 girls]
 
[http://hrentut.org/gay/gay-adonis.html gay adonis]
 
[http://hrentut.org/cheats/cheats-for-starwars-battlefront-2-for-pc.html cheats for starwars battlefront 2 for pc]
 
[http://hrentut.org/air/philippine-air-lines.html philippine air lines]
 
[http://hrentut.org/music/music-box-memories-lyrics.html music box memories lyrics]
 
[http://hrentut.org/air/delta-air-cargo.html delta air cargo]
 
[http://hrentut.org/estate/kentucky-real-estate-for-sale.html kentucky real estate for sale]
 
[http://hrentut.org/jobs/city-of-fort-bragg-nc-jobs.html city of fort bragg nc jobs]
 
[http://hrentut.org/dogs/how-long-do-dogs-stay-in-heat-.html how long do dogs stay in heat ]
 
[http://hrentut.org/job/take-this-job-and-shove-it-lyric.html take this job and shove it lyric]
 
[http://hrentut.org/jobs/neonatologist-jobs-in-newzealand.html neonatologist jobs in newzealand]
 
[http://hrentut.org/job/will-new-job-come-out-in-maplestory.html will new job come out in maplestory]
 
[http://hrentut.org/home/free-home-job-legitimate-work.html free home job legitimate work]
 
[http://hrentut.org/dogs/how-many-breeds-of-dogs-are-there.html how many breeds of dogs are there]
 
[http://hrentut.org/dog/pembroke-and-petawawa-dog-breeders.html pembroke and petawawa dog breeders]
 
[http://hrentut.org/music/kid-rap-music.html kid rap music]
 
[http://hrentut.org/girl/girl-next-door-movie.html girl next door movie]
 
[http://hrentut.org/dogs/how-many-dogs-are-aloud-on-a-jr-iditarod-sled-team.html how many dogs are aloud on a jr iditarod sled team]
 
[http://hrentut.org/gay/hardcore-gay-male-porn-stories.html hardcore gay male porn stories]
 
[http://hrentut.org/home/linon-home-decor-product.html linon home decor product]
 
[http://hrentut.org/music/personal-fan-with-color-and-music.html personal fan with color and music]
 
[http://hrentut.org/dogs/kennels-for-dogs.html kennels for dogs]
 
[http://hrentut.org/sex/is-it-normal-not-to-have-oral-sex-.html is it normal not to have oral sex ]
 
[http://hrentut.org/cheats/resident-evil-4-cheats-and-walkthroughs.html resident evil 4 cheats and walkthroughs]
 
[http://hrentut.org/girl/not-that-kind-of-girl-lyrics-by-jojo.html not that kind of girl lyrics by jojo]
 
[http://hrentut.org/dogs/how-many-dogs-survived-the-sinking-of-the-titanic-steamship-.html how many dogs survived the sinking of the titanic steamship ]
 
[http://hrentut.org/html/html-image-fade-code.html html image fade code]
 
[http://hrentut.org/music/westers-music.html westers music]
 
[http://hrentut.org/estate/wisconsin-real-estate-for-sale.html wisconsin real estate for sale]
 
[http://hrentut.org/game/download-sims-game.html download sims game]
 
[http://hrentut.org/job/1-euro-job-zwangsarbeit.html 1 euro job zwangsarbeit]
 
[http://hrentut.org/car/car-parking-at-manchester-airport.html car parking at manchester airport]
 
[http://hrentut.org/dogs/how-much-chocolate-is-fatle-to-dogs.html how much chocolate is fatle to dogs]
 
</div>
 

Revision as of 09:17, 20 May 2006

Compression is any process that transforms data so that it takes less storage. The process must be reversible, so that the original data can be obtained. Compression works by exploiting the fact that most data has high redundancy; that is, that given a set of data there will generally be strings that occur much more frequently than others.

Below, some common compression methods used in games are described. When looking at the examples, keep in mind that they are only to illustrate the concepts, and actual implementations may store the data very differently.

RLE (Run Length Encoding)

RLE is the simplest type of compression, in which a run (a sequence consisting of one byte repeated) is replaced with the byte along with the length of the run.

Here is an example of RLE. Given the data

4B 68 61 61 61 61 61 61 61 6E 21

a naive implementation of RLE might compress it as follows. The run-length bytes are shown in bold.

4B 01 68 01 61 07 6E 01 21 01

The string of 61s has been shrunk, but the one-byte "runs" have doubled in size, making the compressed data almost as long as the original. If it is known that the original data never uses the most significant bit (i.e. every byte is in the range of 00-7F), then this can be improved by using that bit to indicate a run, eliminating the need to store the length for single bytes. Now the data will become

4B 68 E1 07 6E 21

which is almost half the original size.

RLE was often used to compress maps in NES games. The NES had very little RAM, so a large map generally could not be loaded all at once. Because RLE allows the program to decompress from any point by counting lengths, the desired sections could be loaded while ignoring the rest of the map.

Dictionary

In dictionary compression, commonly used strings are replaced with one- or two- byte sequences that don't occur in the original data. For example, if the character ~ is defined as representing " dog", then the string

If you dog a dog during the dog days of summer, you'll be a dog tired dogcatcher.

would become

If you~ a~ during the~ days of summer, you'll be a~ tired~catcher.

In dictionary compression, one dictionary can be used to compress many small blocks, making it a good method for text.

Huffman coding

In Huffman coding, each character is assigned a sequence of bits to represent it. More common characters get shorter codes, while rarer characters get longer codes. It is named after David Huffman, who discovered an algorithm for generating an optimal code given a set of character frequencies.

Example: With the code 000=e, 001=g, 010=C, 011=(end), 10=a, 11=b, the string "Cabbage" will become 010 10 11 11 10 001 000 011. Putting the bits into groups of 8 to form bytes, this becomes 01010111 11000100 00110000, or "WÄ0".

Like dictionary compression, Huffman coding is often used for text because one Huffman code can be used to compress many small blocks of text.

LZSS (Lempel-Ziv-Storer-Szymanski)

LZSS is sort of like dictionary compression, except that instead of a fixed dictionary, the dictionary is a "sliding window" that consists of the last few kilobytes of data. In LZSS there are single bytes, and references to strings inside the sliding window. These references contain a displacement that says how many bytes before the current position the string starts at, and the length. These are distinguished by the use of "flag bytes", in which each bit determines whether a byte or a reference is to come.

LZSS is sometimes confused with LZ77, an older compression type that it is based on. LZ77 did not use flag bytes, instead the compressed data just alternated between bytes and references.

LZSS works well for large blocks of data, but poorly for small blocks due to the lack of repetition. It is often used for graphics, tiles, and maps. Chrono Trigger uses LZSS, as does the standard GBA compression format.

Super Mario World

Super Mario World uses a very "ad-hoc" compression format, with 5 different commands. Variations of it are used in many other SNES games by Nintendo, such as Yoshi's Island, Super Mario Kart, and EarthBound.

See also