Huffman Algoritme, I think It can be enhanced

[jacsoft]

Are there people here how know how the huffman algoritme works?? (For compression). I think I know, and if my theory is right I think I found a way to improve it. The only thing is I haven't got the time to make it and test it so I was wondering is there anyone how knows how it works and can make it, then I will first share my ideas and then I hope the person can make it.

[plenderj]

I know how it works... what are you suggesting ?

[jacsoft]

Well The huffman algoritme works with bytes (8 bits) and with 1 character. So if you make a binary tree from a file and the file will contain all 256 characters then there won't be anything to speed up. So all files with all characters in it won't be compressed by the huffman algoritm. But If you make it a Huffman32 algoritme (for the current computers), it takes 32/8 = 4 characters at a time. Then there are much more possibilities but also more compression. Let's say one must compress an english text. With the new Huffman32 the words: "the " and " the" will be alot in the text. So if the come above in the binary tree then You can make the binary tree from 32 bits into maybe 1 or 2 bits. Whereas there are more chracters there must be at least 256^4 different characters before the Huffman32 doesn't works anymore.

And For the new processors (64 bit) One can make better the Huffman64 with 8 characters compression beacuse when everything is going to be 64 bit the that one will be optomised.

Now we leave I slight problem. For Instance If I want to compress a file of 3 characters then it won't work. So I suggest to make a header . A 0(bit) then the last characters (1,2 or 3 (fully in bits) (in Huffman32 style) Then a characters to say that the compression is starting. So when you uncompress you start for the compression position (at high 3*8 + 1 +1 = 26 posioton). Then compress everything and the at the end at the first characters from the header. The compression method (I think) will save a lot of data for big file. Files wich include all 256 characters. So all files above +- 5 kb.

[jacsoft]

I hope Anyone gets the general idea. I know it might not be very clear.

[plenderj]

What you're saying is true, that yes there is obviously room for improvement for the mathematics, but the problem is representing the compressed characters.

We still only have the range 0-255.
So we can only work with 8bit characters.
Once we go above that, we can no longer represent that encoded character using normal computer systems

[jacsoft]

Now cause huffman works with bits. So we make a bit representation of it and when we have a bit represntation we convert it back to characters . and by decompressing we convert the characters back to a bit representation and then decompres it so let's say we have the string eeeabeeaeae. The we create a binary tree of it. We got 3 characters. ab and e. e is must so we put it right in the binary tree. SO binary tree becomes:

-
- -e
-a -b

Now a bit 0 says we must go left in the tree and a 1 is we must go right. So the conversion will be:

a= 00
b= 01
e =1

so the string: eeeabeeaeae will be 111000111001001

That is bit representation. Just convert it to ascii characters and you will save a lot of data. Maybe this will clear up the idea

[plenderj]

But my point is that you can't convert anything higher than 11111111 into a character

Anything above 11111111 is out of the range of ASCII characters

[jacsoft]

No but you can convert a larger bitstring into multiple characters. So I you have 1111111111111111 you can convert that into 2 characters

[plenderj]

Thus defeating the purpose then surely ?

[jacsoft]

No, just enhancing. The normal Huffman works with 8 bit codes. But if you work with for example 16 bits. The we compress characters by pairs. And because one have made a binary tree one knows when we have another characters and cause we use two characters the are more possiblities of code, but much more possiblities of bit representation to store the data and so pairs of characters (16 bit) can be much more reduced (to 1 bit if lucky) in stead of 8 bit to 1 bit

[Dyolf Knip]

This sounds like it might be fairly effective when used on text data where, as you said, the high occurence of certain words would lend itself to being compressed. Problem is, normal Huffman compression is already quite effective on text. And the 4-byte version would not be nearly as useful on binaries, in which plaintext usually comprises only a small portion, if anything. So what kind of files do you envision using this on?

Also, Huffman can still be effective on data even if it contains all 256 possible character values. The most commonly occuring characters get assigned the shortest ID's. Data that would render a Huffman algortihm useless would have all 256 characters, but with each occuring about as many times as one another.

--
Dyolf Knip

[jacsoft]

Well my id was to use it on big files > 500 kb.

But if what you suggest is it possible then that huffman if a char doesn't appear often be enlarged because the other characters use less space then .In other words is it possible that Huffman converts a character to a character larger then 8 bit?? If not then my algoritm really Kicks Ass !! else I think my algoritm will win from the normal algoritm by files above let's say 10 mb. But I think I will make it one day if none one else wants to give it a try around here. But that will maybe take up a year before I will start on it.

But my algoritm don't work on plain text. Then the normal algoritm is better.

Ps. I was thinking of this cause I made a new messenger at wich you can send whole directorys. So I was thinking how to good compress files wich are quite large if someone hasn't got a great connection. So I figured out this idea. Also because the normal computers and os works with 32 bit so my algoritm will also be good supported my computer and OS. And For the new 64 bit computers and OS there could be a Huffman64. Optimized for that kind of PC's

[DiGiTaIErRoR]

My thought.

You're just making the code take a larger input and create a larger output.

thus:

2/1 = 4/2

[jacsoft]

No, if you think that you don't get the idea of the Huffman algoritm.

I will explain it briefly here.

The huffman algoritm first scan all code and saves how many times a character exists in the file/string. Then it is creating a binary tree. It puts the characters wich appear most in text above in the tree and with less appereance lower in the tree. Then for each character it makes a binary code from the root of the tree to the leaf wich represents the character. A 0 = left a 1 = right. Cause of the fact the it's a binary tree it has 2 things or nothing unther it. That way you now when a bit string has to be converted to a character. Then it also saves the tree (wich character wich bit representation)

So with normal files with all 255 code in it Huffman will make a binary tree of dept 8. But that way everything is just represented as a normal char. So if you take 4 char then there must be at least 2^8^4 different 4 character string to not compress. This will save a lot of data because a string of 4 characters (normal 32 bits) can be represented as 1 bit.

[jian2587]

jacsoft,i know wut u mean. but will such 32byte length data occur
dat much 4 u to put it on top of the tree so u can use 1 bit only?

Good compression program is a combination of multiple algorithms
just like winzip, but I'm sure they do have their own customized
version of algorithms like LZW and huffman.

Instead of improving, I recommend u think of a new algorithm,
just like me

more than 6 months ago I thought of a new algorithm, the idea is
like this:
Since LZW and Huffman relies on data redundancy, why dont I
create an algorithm which help increases the redundancy? I end
up trying to reorganised the data with my homegrown algorithm
and yielding up more data redundancy thus help winzip to squeez
more!

However, the most unfortunate, while I was thinking of applying a
patent 4 it, I found a compression-related article on the net which
talks about a new algorithm called BWT algorithm which is pretty
much the same as mine.

Sob...sob...

[jian2587]

Read this...
http://www.vbforums.com/showthread.p...ht=compression

http://www.wired.com/news/technology...,49599,00.html

[jacsoft]

jian2587, Do you have a working sample of your own algoritm or something, cause I think reorganising the data is quite a hard job. But I think that the best compression algoritm is a recursive algoritm. So just compress your data, but instead of stopping after you compressed once, just start compressing twice, cause even compressed data can be compressed if one uses a good algoritm.

BTW the link on your first thread:

http://www.vbforums.com/showthread....ght=compression

isn't working anymore, so I could find more info about it.


The problem is the speed of compressing. Thinking of a real good (recursive) algoritm to minimize data will maybe take that long that in the mean time all speed of data will be upgraded. So when one finally figure out a good algoritm, I may not be usefull cause who wants to compress a file of 10 mb when it has got 10 TerraByte of memory or a internet connection of 100 mb (like I do).

So thats why I started thinking of just improving Huffman instead of creating my own algoritm. And because of the fact the Huffman already exists one only have to change a couple of things and it will compress data a lot .

[jian2587]

doesn't matter if it doesn't work anymore, just goto Google and
search for this term:
Zeosync Compression

It'll turn up lots of results regarding a new breakthrough in
compression. Some disappointment,though, the company who
announced 'bout this breakthrough apparently had fled
away I guess this so-called breakthrough is just a
prank But worth it u read articles 'bout them

This so called recursive compression or iterate compression is
not possible as far as I'm concerned. Not sure,though, it might
work on certain data strings, but really really randomized or
entropy strings may not.

As for my algorithm, I admit it did work,does work, as well as will
work! If only more research is on the way. I've abandoned it since
I found out that there's similar algorithm, really. Now even myself
donno wut's my code doin', if u really really want, I might give it a
try to rewrite the codes, but I'm on a large project of my own now
so wait ok?

[DiGiTaIErRoR]

I had a thought about a compression, converting ascii to their numeric counter-parts then performing mathematical operations on stuff.... Of course this was so long ago... I didn't know data types had lengths.

So I thought I'd just convert it all to a number, then do roots and stuff... make a really small number, the expand it back out and convert to ascii again.

Like I said, long time ago. It'd be a good idea though. If it worked....

[jacsoft]

Allright Jian, I will search a little with Google

And DigitalError,about your ideas. I was also thinking about mathematical functions, but found out there isn't a good compression. I was thinking of primes. Cause of the fact all numbers can be split into primes and then use a byte to represent wich prime number are used so for example the first 8 primes are:

1,2,3,5,7,9,11,13. This could be represented in 1 byte (1 char). Cause then 11010001 would represent 1*2*5*13, but that won't work cause for example the number 16 must be split into 8*2 and then there are more bytes needed. The modolo and Div functions also don't work. Then I tried the sqrt. But with most numbers it gives a decimal number and that also won't really compress it. So I couldn't figure out a good arthematic function yet, but keep on trying cause I also think that will be the best method.

[jian2587]

I admit and confirm that all the ideas we expressed here have
already been exploited by profs long b4 we r here
Bout dat prime num/div/sqrt stuffs, I believe all compression
geeks've thought 'bout that b4, it's actually called arithmetic
compression.
Actually this arithmetic compression, u better make it better since
it takes computationally lots of resources 4 example from one
encoded byte u can generate 2-4 bytes of original data

During encoding, it takes lot of time but surely decoding it just
zap accross!!!

Yea, better we all think 'bout that together, perhaps we can form
an open-source organization to create new algorithm, just like
this ogg Vorbis format?

Alrite who's with me!?

[The_Fog]

I don't have to much experience conserning compression algorithms, but I'd gladely participate in a idea like that! :-)

Could we perhaps get in thouch, set a time, and meet on irc and discuss?

[jacsoft]

jian2587, about your idea. I am willing to participate, but there are a few BIG problems.

One: how do you set it up.
Two: the communication.
Three: Figuring out an idea
Four: Time (I'm a student so I don't have much time and when I have time for programming I have got so many programs wich I must make, but I'm always willing to make time and I can involve some of my co-students in the project ofcourse, I bet there are some how want to join.


SO tell me whats your plan, but we can better start a new thread then about it to attract more people. Just let me know, I will do whatever I can.

[jian2587]

Alrite, here's the ingredients:
1.setup it at sourceforge.net/otherwise, go on 4 my own plan
below
2.Brainy people
-Mathematicians
-C and VB programmers
-etc
3.Time(Time? even if u r student/no time u still can participate)
4.Effort(this is a must )
5.etc

OK, I need brainy people most, especially mathematicians

to setup a place 4 meeting, either the first step or through a
networking software I developed(this software quite useful in
such occasions, but still under development, better forget 'bout it)

Create an organization we must appoint the leader(with good
leader we can coordinate our activities smoothly)

I need suggestions now, more suggestions!

[jacsoft]

Ofcourse I can make time, for a good project I will definitely make time.

to setup a place 4 meeting, either the first step or through a
networking software I developed(this software quite useful in
such occasions, but still under development, better forget 'bout it)

Well I made a Peer 2 Peer Messenger Called AMP. This really works Peer 2 Peer, so no one ever can see your data (unlike with MSN, where Microsoft can see all your messages). This Messenger (ALWAYS UNDER CONSTURCTION ) allows plug-ins wich can use the whole AMP networking system. We figured out we work the same as KAZAA, with most P2P messengers people behind a Gateway can't chat (have no normal IP) but we managed to get it right. Maybe we could use that and write a plug-in for it, cause it also supports file resuming and sending whole directories.

But enough advertising for my project now

And ofcourse we need people who can really program. I worked on some projects with other people but most time I had to correct and speed up the other peoples code cause the where really ****.

Create an organization we must appoint the leader(with good
leader we can coordinate our activities smoothly)

Have you got a suggestion. I think one of the most important things the leader must have got is time and a good internet connection so he/she is always available for support etc. (One thing I really don't have)

But I thing "we" must first start a new thread here to find some people who are willing to cooperate

And ofcourse: all people must have good englishs skills, else we also slow down the project

That's my 2 cents

[The_Fog]

We don't only need one leader. We need at least a pair of them. We need one leader that are capable of managing projects of this size. This one leader coordinats the work and takes care of administrative issues, spreads the name, etc.
Then, we need a developer-leader who coordinates the developers and coordinates their efforts.

So what we need, besides brainy people, are a pair of well structured people that can take care of these issues. Without these leaders, their will be no kind of structure in the project, thus, it will probably fail.

Before any work is begun we _must have_ a good idea and generall specifications on what we wish to accomplish. For this we need a good way to communicate. The *****peer chat program, AMP, sounds as a good base to work with.

We need to, just as you said, start a thread about this, create a site, and spread the name. But before we do, thoose of us that really want to do this, should sit down, chat, and make up the guidelines for this project. Create the rules, or whatever you wanna call it. Set up some chain of command, etc. This must be done before too many people are involved.

Pulling thru a project like this is hard and req. good managament, but I don't doubt that our efforts will be successfull.

Still interested?
I am!

[jacsoft]

I will always be interested in projects like this, but don't feel myself the person to start it. So I don't know who will start the project but I will definitely join. Just keep me updated:

[email protected]

or start a new thread, just let me know and I will do what I can.

And I know I can make use of the brains of my fellow students.

[Tec-Nico]

I have been following this post because I like programming and developing algorithms... But when I went to sleep Jian asked "Who is with me" and nobody had answered her yet. I thought about answering today and so here I am... I really like this idea and I would like to be able to cooperate.

As Jacsoft, I am just a student and I have not a lot of time but I can always try to give some to a project like this. I don't consider myself as Newton or something but I feel I am a good mathematician and programmer. I felt kind of shy to reply to this thread since in my course of algorithms we are just in the Unique Interpolation Polynomial part and we have not seen any compresion algorithms yet. Anyway, when in my course of Assembler, we discussed something like this.

I also consider communication is the key for the success of this project and here we can find some very valuable ideas like The_Fog's. I consider Jian a natural leader and looking at her posts I can tell she is a really smart person. So far I am just telling I would like to join this effort. Most of people stop replying when I answer... I hope this is not the case for this project. It looks great with all the opinions and idea it has until now and we can make it work if we all are willing to achieve this goal. The_Fog is right about getting all organized between the founder members before this grows very big.

I would like to suggest to designate the leader after testing the capabilities of the members to know who are those that will get the team to the right direction. But that is all my opinion... What do you all think?

[jian2587]

good idea tec-nico and I really appreciate ur praise but surely
I'm not da leader since I've not much time to coordinate all these.

I'd vote jacsoft, perhaps, to hold this position.
But b4 that lets have good planning, setup a place to meet is the
most important as for now.

[Tec-Nico]

Time is not a factor for leadership...
But I agree.. We need a place to meet and a time too. I like this forum so far. Maybe in Chitchat?

I think they should add an "Algorithm" section... Whenever I come here with Algorithm problems people just go around them.

[jian2587]

For the meeting place factor...
I dont have mIRC & neither will I ever use it
We'll definitely need a site manager, he/she'll setup the
organization site, we'll have sum stuffs 4 visitors to browse
around, a forum/feedback, and another forum just 4 the
members only(that's us!)
Perhaps we need a CGI and mySQL supported site, I recommend
LyCos UK hosting 4 that.
In the first phase, we'll just communicate through our site's forum
Later on we shall develop homegrown communication tool so we
can collaborate.

Remember our primary goal is to develop a better compression
algorithm, make it a breakthrough! okay?

OK, wut'll our algorithm emphasize on? of-course it's compression
but how'd we compress it? Just as LZW relies on data redundancy
we should think of a better idea. I donno if my earlier mentioned
algorithm will work better, but let's all give out sum idea.

If anyone interested but not quite good in these stuffs never mind
I still welcome we'll teach da foundations coz' I need brainy ideas,
not necessarily a genius, but of coz if there's one dat's better.

[Tec-Nico]

I was thinking about a couple of ideas...

One of them has to do with an algorithm that would do a mathematical polynomial for each row of a picture (In this case) and then in the second iteration perform another mathematical polynomial to save the important data of this polynomial in a field (Say like a sumatory or multiplicatory) And the iterations of the algorithm in another field until we finally get just a mathematical expression, the important fields describing it and the field of the iterations.

What do you think?

[jian2587]

computationally expensive, I guess, but worth a try

Elaborate more! tec-nico

[Tec-Nico]

I know it is.. I thought that when I got the idea but I also thought it would be worth the try if the compression could be as good as it sounds.

I am going to work on it... I just wanted to know your opinion. I will think of more... You set the place of meeting, please.

[jian2587]

b4 that does this organization needs a name? haha...
so I can register 4 dat name...

[vbud]

hi all,

how is it going jian?
I have followed this thread too since I once tried a program once on Huffman Algorithm. I'm not that good at compression algos but I'm pretty good at VB so if you need any help on this team, you can count me on.

[Pony]

to Jian:
One suggestion, maybe first we should list the most important compression algortihms,just like the Humm, which we can find whether throught internet or through the labs. The fact is that we must be clear of our aim. I think it's a good way to create our own algorithm by researching on the known's deficient.

Just a talk,heihei

[jacsoft]

BREAK THROUGH (maybe)

Alright Jian thank you for voting me for leader but I don't think I'm suitable for it. I would also vote for you, but that's not the most important why I reply.

I have been thinking for 2 whole days and I think I've really got a break through in compression. It may not look like a break thought, because I think my algoritm can compress 8 byte of raw data into approx 8, but when I use it with a standard compress method I think I can really get a small file. Because of the fact that I first compress the file, the use my algoritm, then compress, then my algoritm etc. This can (for what I have in my head right now) go up to 65536 levels deep (wich will be saved in the header). The compress method will take long but the decompress will be really quick.

I have not yet found an error in my idea (but perhaps I will find it soon). So I won't tell anything right now, cause I first want to check if it could work, but I think that it could compress 1 to 1000 at least. I will check (wich may take a while), but when I think it is suitable I will surely let you know and you may crack your brains on it and even try to improve it better. I have got the whole idea in my head right now with header and footer and everything.

Thats all I can say for now, but I will come back here after I have my first results (wich may take a while), but I am really excited.

[jian2587]

U mean compress then reorganized da data or encode in some
form then recompress again? hmm...then the most important
thing is the encoding stage.

Yea Pony,good idea!

OK,vbud,I trust everyone here, so give ur best if u r in.

[Dmitri K]

I just was browsing around looking for some useful stuff while waiting for an answer to my post. Anyway, someone said this above, I'm not reading all these posts again but people have already tried everything possible to optimize the compression. And, and only if, say you do create an algorhythm to compress data more efficiently. Would it be worth it? You might be able to save a second of compression time and few bytes or even kilobytes. But do you think companies will jump to your algorhytm just because it compresses by 0.001% better than all others? I don't think so. And plus, writing a compression program in VB is just a waste of time. Most compress utilities are written with at least C language, if not Assembly. If you do want to write something that might be actually a break thru, try writing a better voice recognition or even better AI.