Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.lang.python > #99120 > unrolled thread

shorten "compress" long integer to short ascii.

Back to article view | Back to comp.lang.python

Contents

  shorten "compress" long integer to short ascii. Vincent Davis <vincent@vincentdavis.net> - 2015-11-19 20:45 -0700
    Re: shorten "compress" long integer to short ascii. Paul Rubin <no.email@nospam.invalid> - 2015-11-19 20:27 -0800
      Re: shorten "compress" long integer to short ascii. Vincent Davis <vincent@vincentdavis.net> - 2015-11-20 07:18 -0700
        Re: shorten "compress" long integer to short ascii. Grant Edwards <invalid@invalid.invalid> - 2015-11-20 15:55 +0000

#99120 — shorten "compress" long integer to short ascii.

My goal is to shorten a long integer into a shorter set of characters.
Below is what I have which gets me about a 45-50% reduction. Any suggestion
on how to improve upon this?
I not limited to ascii but I didn't see how going to utf8 would help.
The resulting string needs to be something I could type/paste into twitter
for example.

On a side note string.punctuation contains "\\" what is \\ ?

import string
import random

# Random int to shorten
r = random.getrandbits(300)
lenofr = len(str(r))

l = string.ascii_lowercase + string.ascii_uppercase +
'!"#$%&\'()*+,-./:;<=>?@[]^_`{|}~'
n = [str(x) for x in list(range(10,93))]
decoderdict = dict(zip(l, n))
encoderdict = dict(zip(n, l))

def encoder(integer):
    s = str(integer)
    ls = len(s)
    p = 0
    code = ""
    while p < ls:
        if s[p:p+2] in encoderdict.keys():
            code = code + encoderdict[s[p:p+2]]
            p += 2
        else:
            code = code + s[p]
            p += 1
    return code

def decoder(code):
    integer = ""
    for c in code:
        if c.isdigit():
            integer = integer + c
        else:
            integer = integer + decoderdict[c]
    return int(integer)

short = encoder(r)
backagain = decoder(short)

print(lenofr, len(short), len(short)/lenofr, r==backagain)

[toc] | [next] | [standalone]

#99123

Vincent Davis <vincent@vincentdavis.net> writes:
> My goal is to shorten a long integer into a shorter set of characters.
> Below is what I have which gets me about a 45-50% reduction. Any suggestion
> on how to improve upon this?

You can't improve much.  A decimal digit carries log(10,2)=3.32 bits
of information.  A reasonable character set for Twitter-style links
might have 80 or so characters (upper/lower alphabetic, digits, and
a dozen or so punctuation characters), or log(80,2)=

> I not limited to ascii but I didn't see how going to utf8 would help.

If you could use Unicode characters like Chinese ideographs, that gives
you a much larger alphabet to work with, so you'd need fewer chars
displayed in the link, but they'd be hard for most people to type.

> l = string.ascii_lowercase + string.ascii_uppercase +
> '!"#$%&\'()*+,-./:;<=>?@[]^_`{|}~'

OK, 83 chars, but it may not be ok to use some of them like #, /, and ?,
since they can have special meanings in urls.

Your algorithm looks basically ok though I didn't examine it closely.
Here is my shortened version:

  import string

  # alphabet here is 83 chars
  alphabet = string.ascii_lowercase + \
       string.ascii_uppercase +'!"#$%&\'()*+,-./:;<=>?@[]^_`{|}~'
  alphabet_size = len(alphabet)

  decoderdict = dict((b,a) for a,b in enumerate(alphabet))

  def encoder(integer):
      a,b = divmod(integer, alphabet_size)
      if a == 0: return alphabet[b]
      return encoder(a) + alphabet[b]

  def decoder(code):
    return reduce(lambda n,d: n*alphabet_size + decoderdict[d], code, 0)

  def test():
      n = 92928729379271
      short = encoder(n)
      backagain = decoder(short)
      nlen = len(str(n))
      print (nlen, len(short), float(len(short))/nlen)
      assert n==backagain, (n,short,b)

  test()

[toc] | [prev] | [next] | [standalone]

#99151

On Thu, Nov 19, 2015 at 9:27 PM, Paul Rubin <no.email@nospam.invalid> wrote:

> You can't improve much.  A decimal digit carries log(10,2)=3.32 bits
> of information.  A reasonable character set for Twitter-style links
> might have 80 or so characters (upper/lower alphabetic, digits, and
> a dozen or so punctuation characters), or log(80,2)=
>

​Where do I find out more about the how to calculate information per digit?
​
Lots of nice little tricks you used below. Thanks for sharing.


> Here is my shortened version:
>
>   import string
>
>   # alphabet here is 83 chars
>   alphabet = string.ascii_lowercase + \
>        string.ascii_uppercase +'!"#$%&\'()*+,-./:;<=>?@[]^_`{|}~'
>   alphabet_size = len(alphabet)
>
>   decoderdict = dict((b,a) for a,b in enumerate(alphabet))
>
>   def encoder(integer):
>       a,b = divmod(integer, alphabet_size)
>       if a == 0: return alphabet[b]
>       return encoder(a) + alphabet[b]
>
>   def decoder(code):
>     return reduce(lambda n,d: n*alphabet_size + decoderdict[d], code, 0)
>
>   def test():
>       n = 92928729379271
>       short = encoder(n)
>       backagain = decoder(short)
>       nlen = len(str(n))
>       print (nlen, len(short), float(len(short))/nlen)
>       assert n==backagain, (n,short,b)
>
>   test()
>




Vincent Davis
720-301-3003

[toc] | [prev] | [next] | [standalone]

#99159

On 2015-11-20, Vincent Davis <vincent@vincentdavis.net> wrote:
> On Thu, Nov 19, 2015 at 9:27 PM, Paul Rubin <no.email@nospam.invalid> wrote:
>
>> You can't improve much.  A decimal digit carries log(10,2)=3.32 bits
>> of information.  A reasonable character set for Twitter-style links
>> might have 80 or so characters (upper/lower alphabetic, digits, and
>> a dozen or so punctuation characters), or log(80,2)=
>>
>
> ​Where do I find out more about the how to calculate information per
> digit?

There are 10 possible states for a decimal digit.

The number of digits required to represent N states in base M is
log(N,M).

-- 
Grant Edwards               grant.b.edwards        Yow! Are we on STRIKE yet?
                                  at               
                              gmail.com            

[toc] | [prev] | [standalone]

Back to top | Article view | comp.lang.python

csiph-web