Tue Aug 28, 2007 1:56 pm
Right take a deep breath.... (and this is ultra basic stuff).... and follow me down the rabbit hole that is data compression ....
I'll use lossless compression of the type used in Lempel-Ziv-Welch (LZW) style compression (such as ZIP).
I'll touch on lossy at the end but without regard to specific examples like JPG as you can't really draw direct working analogies outside of the specific purpose (ie the theory behind JPeG for pictures works totally differently to MP3 for audio - which is why they use both of them, together, to compress movies ie MPeG's)
Lossless compression LZW style...
OK first thing to realise is that even though your data is a picture it is made up of the same binary "bits" (0's & 1's) that are used to store text files on disk... when several sets of binary are joined together they are said to be a "word".
When a program runs LZW type compression it builds a table of all the "words" that it finds (patterns of bits) it does this by examining all the possible contiguous combinations with in it's "word size" limit.
Now it looks at this index (called a "dictionary") and finds "words" that occur frequently and assigns a smaller "look up word" to represent this.
it then writes a file that includes the table (the original "words" and the new, smaller "look up words" that now represent the old longer "words"), it then writes the data in to the file using original "words" that didn't happen frequently enough to warrant their own "look up words" as well as the "look up words" that represent the now discarded longer "words".
when a program wises to read/display this data it looks at the table and reads all the original words and their "look up" replacements and then starts reading the actual data if a word in the data is a "look up word" instead of displaying the word written in the file it replaces it with the original "word" in the table...
ie
lets use the modern UK version of the lords prayer:
Our Father in heaven,
hallowed be your name.
Your Kingdom come,
your will be done,
on earth as in heaven
Give us today our daily bread.
Forgive us our sins,
as we forgive those who sin against us.
Lead us not into temptation,
but deliver us from evil.
For the kingdom, the power and the glory are yours.
Now and for ever. Amen
we can see that several words appear numerous times
so a table might look like this
Original word lookup word
heaven 1
your 2
in 3
be 4
our 5
give 6
sin 7
us 8
as 9
etc... etc ..etc...
running just this small sample against the original we get a file that looks like this:
table:
heaven 1, your 2, in 3, be 4, our 5, give 6, sin 7, us 8, as 9
Data:
5 Father 3 1,
hallowed 4 2 name.
2 K3gdom come,
2 will 4 done,
on earth 0 3 1
6 8 today 5 daily bread.
Forgive 8 5 7s,
0 we forgive those who 7 aga3st 8.
Lead 8 not 3to temptation,
but deliver 8 from evil.
For the k3gdom, the power and the glory are y5s.
Now and for ever. Amen
so you can see here that no data is lost... every thing is there just represented differently. running it back using a reverse look up your reconstitute the EXACT same data with no loss at all.
now in this short example you won't get any real saving, and in fact you get a bigger file : 332 characters in the original and 360 in the "compressed" file, in this case mainly because the table takes up room and the fact that while the look up words replace bigger original words they still take up some space.
further more the compression algorithm will now repeat the process to see if, in the process of compressing the file it's made any new patterns of frequent new words it can replace. this may be repeated several times (and the file keeps a record of how many times it's repeated as it has to run the replace (uncompress)process that same number of times.
Each repeat is almost always a diminishing return until there no more compression to be gained (or you set a limit of repeats based on if the user will run out of patience waiting for it)
the reason why different RAW formats can produce different files sizes is what compression algorithm they use and... well this comes down to 2 things
1: how fast can the camera's hardware run different levels/types of compression related to what is a reasonable user level of patiense of waiting (cheap powershot A model ... heck you can wait on the slow as a wet weekend cheap processor, D1nIII slamm 'em out as fast as you can with a highly optomised processor (or 2)
2: what compression algorithm can you afford to license?
ZIP/LZW is now free (out of patent) but it is slow and it is inefficient
newer faster and more efficient algorithms that can compress files faster and in to smaller sizes cost serious money to license and the bigger the company (ie Canon, Adobe) the better they can afford them (or afford to employ researchers to write their own even better ones)
in the end I would bet good money (note: all my money is bad money (ie debt)so don't call me in on this) stuff like DNG is so efficient is simply because Adobe owns their very own meanest nastiest alpha dog of all lossless compression algorithms and that Olympus and to a lesser extent Canon have their smaller beta dog algorithms that arn't quite champs (and also they have to squeeze their dogs in to a smaller kennel (your camera) than Adobe (who house it in your nice fast computer).
Now lossy compression.. like JPG and MP3
first off all you generally run a lossless algorithm on your data... now we'll use the same example so before losing anything we have:
table:
heaven 1, your 2, in 3, be 4, our 5, give 6, sin 7, us 8, as 9
Data:
5 Father 3 1,
hallowed 4 2 name.
2 K3gdom come,
2 will 4 done,
on earth 0 3 1
6 8 today 5 daily bread.
Forgive 8 5 7s,
0 we forgive those who 7 aga3st 8.
Lead 8 not 3to temptation,
but deliver 8 from evil.
For the k3gdom, the power and the glory are y5s.
Now and for ever. Amen
now we throw away anything that the user won't notice....
now here we see why the analogy can't be directly compared between media that your compressing... in pictures your _BRAIN_ sees things that eyes' don't and doesn't see things that are there.. in music your BRAIN hears things that don't exist and doesn't hear things that do exist.
with text your brain already doe's a lot of implicit "reading" you skip over without registering many grammatical and spelling mistakes, incorrect punctuation and poor formating... now imagine your brain did this to the extent that it does it with pictures and music... you can now remove all those pesky page breaks, carriage returns, turn all the "sounds the same but spelt different words (homonyms) like "to" "too" "two" and "2" in to one single word... "2"
sounds strange? just look at kids/teenagers doing mobile/cell phone, and online text messages, L33t 5p34k (leet speak (elite speak) and lolcat macro's)
all of this is throwing raw data away that is implicitly reconstructed by the the reader (given they are "in the know" of how it works)
hate "those type of kids and their curse'ed desecration of language"? well? tough, other languages have been there and done that before and "compressed" their language we no longer speak the wordy and verbose language of Shakespearian type English, Hebrew has no writen vowels, Japanese almost always leaves out subject ("you" "me" "them") in both written and spoken words in all cases the listener reconstructs them mentally with in their lingustic context.
so just a simple homonym/punctuation pass turns the example in too
table:heven1,ur2,in3,B4,our5,give6,sin7,us8,as9.Data:5Father31
helloed42name2K3gdomcome2will4doneonearth03168today5daily
breadForgive857s0weforgivethosewho7aga3st8Lead8not3to
temptationbutdeliver8fromevilforthek3gdomthepowerandtheglory
ry5sNowandforeverAmen
now THAT takes up a whole lot less space... but you've thrown out a lot of data that, if you train your brain to ignore it all in the first place (like those pesky kids), you'd have no trouble processing it the same way you look at a JPG with 4/5ths of it's data thrown out and listen to a MP3 with 9/10'ths of it's information stripped away.
Last edited by marxz on Wed Aug 29, 2007 4:20 am, edited 1 time in total.
there is no .sig