 |
 |
| View previous topic :: View next topic |
| Author |
Message |
chingB
Joined: 29 Dec 2003
Posts: 81
|
| String Compression |
 Posted: Sat Dec 04, 2004 8:36 am |
 |
|
Hello,
Anybody in the community have a wild ideas on how to implement a string compression?
Any info, help, comments and/or suggesstions is appreciated.
It will be great if a code snipet /psuedo code is provided.
Thanx |
|
 |
Ttelmah
Guest
|
| Re: String Compression |
| Posted: Sun Dec 05, 2004 3:52 am |
|
|
| chingB wrote: | Hello,
Anybody in the community have a wild ideas on how to implement a string compression?
Any info, help, comments and/or suggesstions is appreciated.
It will be great if a code snipet /psuedo code is provided.
Thanx |
Unfortunately, 'generic' compression, requires quite a lot of code, and is unlikely to save any space on the small strings involved in most PIC applications. Basically, the commonest 'style' of algorithm, relies on finding 'common' sections of the text, and then storing these just once, and replacing the character code at this point, with a 'marker' to say that the stored version should be used. So (for instance), if you have two strings:
The rain in Spain.
The quick brown fox.
Then you could potentially use an otherwise unused character (one of the control characters), as a marker. Replace the only 'common' word (The), with the marker, and a 'key number' to say which of the library strings to use. You then have to have a library containing the common words. The problem is that compression of this sort, only works efficiently when there are a _lot_ of common words, since the library has to be included in the stored data. If (for instance), you run PKZIP, on text, you will find that under about 10K characters, the algorithm will not compress at all, knowing that the relatively low number of comon strings, and the overhead of adding the library, will outweigh any savings.
Probably the best way of saving space, if you are needing to handle a number of messages, is to take full advantage of the 8bit range for an integer. Either saving two bits per character, by coding your own 'subset' of the ASCII set involving only 64 characters, and then storing these 'nose to tail' inside the available space (a potential saving of 25% on the size needed), or to generate your own library of commonly used words, and use values over 127, as 'keys' to these.
Doing generic 'on the fly' compression, uses a lot of code space, and RAM. I did an algorithm some time ago, on a PIC18F252 (proprietary so I can't post it), and had to use 80% of the ROM space, and 90% of the RAM, just to implement the compression...
Best Wishes |
|
|
treitmey
Joined: 23 Jan 2004
Posts: 1094
Location: Appleton,WI USA
|
|
|
|
|
You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot vote in polls in this forum
|
Powered by phpBB © 2001, 2005 phpBB Group
|
FAQ 
Search
Register
Profile 
Log in to check your private messages 
Log in
