Jump to content
  • Advertisement

ragonastick

Member
  • Content Count

    829
  • Joined

  • Last visited

Community Reputation

134 Neutral

About ragonastick

  • Rank
    Advanced Member

Recent Profile Visitors

The recent visitors block is disabled and is not being shown to other users.

  1. ragonastick

    Compression algorithm

    I don't know if this has a fancy name or anything, it is just an idea which I came up with. In terms of compression ratios it doesn't do brilliantly (it compressed the text of dracula to about 70% of its original size) but there is a lot of room for improvement. The basic idea is that you can encode a number in binary in such a way that it is self delimiting, so when you write two of these numbers next to each other, you can actually tell that there are two numbers. I won't go into full details, but instead of having a 1, 2, 4, 8, 16... "column", you have 1, 2, 3, 5, 8, 13... (Fibonacci numbers). But, the restriction is that two 1s never appear in a row except to signal that this is the end of a number. eg 1 -> 11 = 1 2 -> 011 = 2 3 -> 0011 = 3 4 -> 1011 = 1 + 3 5 -> 00011 = 5 6 -> 10011 = 1 + 5 7 -> 01011 = 2 + 5 ... So, with this encoding scheme, you can see that smaller numbers get smaller representations. My naive compression routine had a table of size 256, which initially contained the numbers 0-255. I would read a byte, and then look for that byte in the table. Once I found it, I would write down where it was in the table and then put it at the front of the table, shifting everything else back. What happens is that the common letters get put at the start, while the uncommon things don't, hence common things have shorter representations. The compression isn't brilliant, but it is easy to understand and implement. You can also extend it by various methods: 1) Rather than moving it to the front of the list, is there a better place to put something when it has been used (possibly based on its history) 2) Meta-characters - have a bigger table with things like "caps-lock" or "capitalise next value" or "store next 3 bytes to buffer" and "put buffer here" There may be a proper name for it which might help you. But since this idea was just one of my thoughts (probably unoriginal too), you'll have to find it yourself. Andy
  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

We are the game development community.

Whether you are an indie, hobbyist, AAA developer, or just trying to learn, GameDev.net is the place for you to learn, share, and connect with the games industry. Learn more About Us or sign up!

Sign me up!