Math Is Fun Forum

lekkie

Member

Registered: 2007-02-10

Posts: 9

Encoding Algo

Hi guys,

Its really nice having this forum. I just googled and this came up. I ve always love maths.

I am having a prob and I ve got limited time.

I ned and algorithm to encode a 256 long encrypted msg into a 32 long msg. I need this so as to be able to transfer the data over a medium.

Any algothm that can help. EWven if its just an idea, I could develop on it.

Thnx

lekkie

Member

Registered: 2007-02-10

Posts: 9

Re: Encoding Algo

Yea, I knew abt the RLE Algorithm. However, wot I want is quite different.

I have encrypted a pwd, and I need to compress it. RLE only works with data wit consecutively repeated data.

My encrypted data are not usually consecutively repeated. Is there a way of may be, representing (encoding) data in a compressed format?

lekkie

Member

Registered: 2007-02-10

Posts: 9

Re: Encoding Algo

Alright guys,

I ve made it simpler.

I av a string of 800 integers and I want to compress them to around 50 digits. Does anybody know how I can add them together and a way of expanding the compressed numbers to retrieve the original 800 integers.

Thnx

Ricky

Moderator

Registered: 2005-12-04

Posts: 3,791

Re: Encoding Algo

what is the range of these integers?

---

"In the real world, this would be a problem.  But in mathematics, we can just define a place where this problem doesn't exist.  So we'll go ahead and do that now..."

lekkie

Member

Registered: 2007-02-10

Posts: 9

Re: Encoding Algo

between 0 and 9

Ricky

Moderator

Registered: 2005-12-04

Posts: 3,791

Re: Encoding Algo

Just format it: Number of 0's, number of 1's, number of 2's, number of 3's, etc

So if you integers are:

1
3
3
5
4
6
4
9
2
3
5
9
8

Your list would be:

0 1 1 3 2 2 1 0 1 2

---

"In the real world, this would be a problem.  But in mathematics, we can just define a place where this problem doesn't exist.  So we'll go ahead and do that now..."

lekkie

Member

Registered: 2007-02-10

Posts: 9

Re: Encoding Algo

Now I get.

But how do I know the order the numbers are pre-arranged initially when I want to re-arrange them back?

Last edited by lekkie (2007-02-10 06:32:15)

Ricky

Moderator

Registered: 2005-12-04

Posts: 3,791

Re: Encoding Algo

If you wish to preserve order, this is impossible.  I assume by "50 digits" you mean characters, 8 bits each.  This means you need to store something with 10^800 different possible "states" into something that can contain 2^(8*50) = 2^400.  But 10^800 > 2^400, and thus, this is impossible.

---

"In the real world, this would be a problem.  But in mathematics, we can just define a place where this problem doesn't exist.  So we'll go ahead and do that now..."

lekkie

Member

Registered: 2007-02-10

Posts: 9

Re: Encoding Algo

So to be realistic, what is the least possible number that I can use to store a 800 (character range btw 0-9) character data and still be able to retain the order?

How about the least possible number for a 256 charactered data but with characters ranging btw [A-Z][a-z][0-9]?

Let me tell you my prob....

I have a 256 character data with the of [A-Za-z0-9] possibilities. I want to encode it. What is the barest minimum (length-wise) I can encode this data without losing the order in whihc they are arranged and How will I encode em?

Thnx.

Last edited by lekkie (2007-02-10 07:18:43)

Ricky

Moderator

Registered: 2005-12-04

Posts: 3,791

Re: Encoding Algo

There isn't a "best" algorithm.  Different algorithms fair differently on different pieces of data.  And there are literally hundreds of different algorithms to choose from.

Many such algorithms use things such as patterns of bytes to reduce the size.  In many (most) cases, this will reduce the number of bits it takes to represent some piece of information.  However, there are some where such method will actually take more.  So a piece of data is added to the front of the data saying which encryption algorithm is used, and in this way, you may use different algorithms on different pieces of data, choosing which ever one works best.  But this in turn adds overhead.

---

"In the real world, this would be a problem.  But in mathematics, we can just define a place where this problem doesn't exist.  So we'll go ahead and do that now..."

John E. Franklin

Member

Registered: 2005-08-29

Posts: 3,588

Re: Encoding Algo

I have a suggestion, however, the data is only reduced to 75% its original size.
Sorry only 25% reduction, but here is how it works, it is very, very simple.
Keep in mind that after doing this easy way, then you could try pkzip'ing it up for good luck.
Each 8 bit character, for which you have 26 + 26 + 10 = 62, can be assigned to
one of the 64 six bit numbers. (

)
For the other 2 remaining ones, just assign a spacebar character and a period for fun.
Now pack these 6 bit numbers end to end in 8 bit bytes, thus creating usable 8-bit data, but
75% its original length.  Hope you like it!!!!!!!!!

---

igloo myrtilles fourmis

lekkie

Member

Registered: 2007-02-10

Posts: 9

Re: Encoding Algo

I have thot abt that. I have thot abt that. But the 196 character reduction was not enof. I needed to reduce it further. I thot abt re-encoding to a 16bit instead of a 8-bit, but that looks too ambigous.

I will keep working around it. Even if I can get a 50% reduction, I could manage and make do with it.

Actually, I looking at doing this so that I can help compress large numbers and re-encode for easy transmission. Note, I dont want any added zipping. I just want a raw data compressed. Or may be I really dont get the zippin concept cos, i am lookin at mobile phones who had to send sms and must be less than 160 xter.

Ricky

Moderator

Registered: 2005-12-04

Posts: 3,791

Re: Encoding Algo

If this is for an actual product (rather than an assignment from a teacher), you may wish to look at open source compression methods like 7zip.

---

"In the real world, this would be a problem.  But in mathematics, we can just define a place where this problem doesn't exist.  So we'll go ahead and do that now..."

John E. Franklin

Member

Registered: 2005-08-29

Posts: 3,588

Re: Encoding Algo

Here's just another thought.
Reduce your character set down to

or 32.
This will only take 5 bits now for each character, except the
occasional capital letter will take 10 bits: 5 bits (the #27) to
say that the next 5 bits to follow is the lowercase letter that
should be capitalized. (Just like in Braille, they have a preceding capitalize character).
And further the numbers 3,4,7,8, and 9 don't look like letters, so leave them
for #28,#29,#30,#31, and #32. (or 27 to 31 if you start with zero)
The letters 1 looks like an el, the 2 looks like a zee, the 5 like an es, the 6 like a bee, and
the zero looks like an oh.
So for 1,2,5,6,and 0, just use the lower case letters.
So now you can use 0 to 25 for lower case alphabet.
#26 for capital-comes-next character.
#27 to #31 for 3,4,7,8,and 9.
Hope this idea comes in handy.
If not, hope you find something else!!

---

igloo myrtilles fourmis

lekkie

Member

Registered: 2007-02-10

Posts: 9

Re: Encoding Algo

So, when decoding, How will I differentiate btw a 5 and a small case s or a b and 6?