Data Warehousing Essay, Research Paper

Data Compaction

Data Compression merely sounds complicated. Don T be afraid, compaction is our good friend for many grounds. It saves difficult thrust infinite. It makes informations files easier to manage. It besides cuts down those huge file download times from the Internet. Wouldn t it be nice if we could compact all files down to merely a few bytes?

There is a bound to how much you can compact a file. How random the file is, is the finding factor to how far it can be compressed. If the file is wholly random and no form can be found, so the shortest representation of the file is the file it self. The existent cogent evidence that proves this is at the terminal of my paper. The key to compacting a file is to happen some kind of exploitable form. Most of this paper will be explicating those forms that are normally used.

Null suppression is the most crude signifier of informations compaction that I could happen. Basically,

it says that if you have different Fieldss that information is in ( perchance a dispersed sheet ) , and any of them have merely zeros in them, so the plan merely eliminates the information and goes directly from the empty informations set to the following.

Merely one measure up from void suppression is Run Length Encoding. Run length encoding

merely tells you how many of what you have in a row. It would alter a set of binary informations like { 0011100001 } into what the computing machine reads as ( 2 ) nothing, ( 3 ) 1s, ( 4 ) nothing, 1. As you can see, it works on the same basic thought of happening a series of 0 s ( void suppression ) and 1 s in this instance excessively and abridging them.

Once the whole thought of informations compaction caught on, more people started working on plans for it. From these people we got some new premises to work with. Substitution encryption is a large 1. It was invented jointly by two people: Abraham Lempel and Jakob Ziv. Most compaction algorithms ( large word significance approximately plan ) utilizing permutation encoding start with LZ

for Lempel-Ziv.

LZ-77 is a truly orderly compaction in which the plan starts away merely copying the beginning file over to the new mark file, but when it recognizes a phrase of informations that it has antecedently written, it replaces the 2nd set of informations in the mark file with waies on how to acquire to the first happening of it and copy it in the waies topographic point. This is more normally called a sliding-window compaction because the focal point of the plan is ever skiding all around the file.

LZ-78 is the compaction that most people have in their places. Some of the more common 1s are ZIP, LHA, ARJ, ZOO, and GZIP. The chief thought behind LZ-78 is a dictionary. Yet it works

rather a spot like the LZ-77. For every phrase it comes across, it indexes the twine by a figure and writes it in a lexicon. When the plan comes across the same twine, it uses the associated figure in the dictionary alternatively of the twine. The lexicon is so written along side the compressed file to be used in decrypting.

There is a combined version of LZ-77 and LZ-78. It is called LZFG. It merely writes to the lexicon when it finds the perennial phrase, non on every phrase. Then alternatively of LZFG replacing the

2nd set of informations with waies on how to acquire to the first happening of it, the plan puts in the figure mention for the dictionary s interlingual rendition. Not merely is it faster, but it compresses better because of the fact that it doesn t have every bit large of a dictionary attached.

Statistical encryption is another 1 of the new compaction constructs. It is an outgrowth of the LZ household of compressors ; it uses fundamentally the same manner as LZFG, but alternatively of delegating

the Numberss in order that the strings come out of the beginning file, statistical compressors do some research. It calculates the figure of times each twine is used and so ranks the twine with the most figure of utilizations at the top of the hash tabular array. The twine with the least is ranked at the underside. ( A hash tabular array is where the rank is figured ) The higher up a twine is on this list, the smaller of a mention figure it gets to minimise the entire spot usage. This gives this compaction merely a little border on the others, but every small spot helps. ( ha hour angle -bit- )

Beware! There are a few compaction plans out at that place that claim fantastic compaction ratios ; ratios that beat the compaction bound for that file s entropy. These plans aren t truly compression plans. They are OWS and WIC. Never compress anything with these. What they do is divide up the file that you desired to compact and conceal most of it on another portion of your

difficult thrust. OWS puts it in a specific topographic point on the physical difficult thrust disc. WIC puts the excess information in a hidden file called winfile.dll. The existent jobs with these plans are that if you don Ts have the winfile.dll or the information on the certain topographic point on your thrust, so the plan won t set your file back together.

My original purpose with this undertaking was to contrive a new compaction algorithm. I started with

the thought that if you took the file in its pure binary signifier and laid it out in a matrix, there were certain rows and columns that you could add up to acquire an end product that would be able to animate the original matrix. I was near excessively. I had four different end products that really would be what would do up the compressed file that combined together to make one end product for each spot. From this individual end product I could find if the spot was 1 or 0. It worked absolutely for matrixes of 1 & # 215 ; 1, 2 & # 215 ; 2, and 3 & # 215 ; 3. Except that with this little of a matrix, I wasn t compacting it at all. It was more of a cryptography system that took up more infinite than did the original file. I even found a manner to shrivel

the size of the four end products but it was non plenty to even interrupt even on spot count. When I got to the 4 & # 215 ; 4 s I found an convergence. An convergence is a term I made up for this algorithm. It means that I got the same individual end product for a 1 as I did a zero. When that happens, I can t figure out which it is a 1 or 0. When you can t animate the original file, informations compaction has failed. It becomes louse. I needed a 5th original end product. If you want more information on how I thought the algorithm would hold worked, delight refer to my Inventor s Log that I included. It s manner excessively much to re-type here and it would function no existent intent in this paper.

If you were paying attending before, you would be stating, Why don T you find a form? Otherwise you can t compress it. You are handling it like a random file. I didn t find out that it was

impossible to compact random informations until about the clip my algorithm was neglecting.

Because of my reverses I started looking for an wholly new manner to compact informations,

utilizing a form of some kind. I got to believing about all of the bing algorithms. I wanted to unite a hash tabular array, statistical programmer, and a tally length programmer. The lone difficult portion that I would see in that would be seeking to acquire the patent holders of each of those algorithms to let me to unite them and really modify them somewhat.

In its current algorithm, the statistical programmer merely accepts alphameric phrases. I would wish to modify it to non read the characters that the binary codification spells out, but the binary codification it

ego. I don t know what organize the end product is aside from compressed, but for my intents it wouldn t affair what the signifier the end product is. I would plan into the plan all of the 32 combinations of 5 spots ( 2^5 ) . Each of the combinations would be labeled in the plan 1 through 32. I would so do a hash tabular array of all of the 5 spot combinations. This would give me an end product, which I would

run through a tally length programmer. Since the full algorithm is reliant on binary codification and non on characters, it can be recursable, or it can compact farther an already compressed file. LZ s can t make that because one time they convert a twine into it s dictionary/sliding window signifier, it ceases to be one of the characters that it compresses.

Now that you are aquatinted with our friend, Data Compression, I hope he will be able to function you better. Now you can download plans faster, salvage infinite, and who knows? Maybe you will contrive the following new compaction algorithm. Until so, maintain your mice happy and your

proctors warm.

Proof that random informations is non compressible: Let s say the file to be compressed is 8 spots long ( ten plants, but this is easier ) and is random There are precisely 2^8 different possible 8 spot informations strings. ( 2^x ) To compact the file it must shrivel it by at least one spot ( 2^x ) -1 So there are at most 2^7 different compressed files 2^ ( x-1 ) . Therefore at least two beginning files compress down to the same file. Therefore the compaction can non be loss less.

Bibliography

Aronson, Jules Data Compression- a comparing of Methods

Washington D.C. : Institute for Computer Science and Technology

hypertext transfer protocol: //simr02.si.ehu.es/DOCS/mice/compression-faq/part1/faq-doc-x.html

x=Intro,8,9, and 10

hypertext transfer protocol: //www.epl.co.uk/genit18.htm

hypertext transfer protocol: //www.sees.bangor.ac.uk/ gerry/sp_summary.html

hypertext transfer protocol: //Literacy.com//mkp/pages/3468/index.html