fork download
copy 
  1. #!/usr/bin/env python
  2.  
  3. #-*- coding: utf8 -*-
  4.  
  5.  
  6. from math import floor, log, ceil
  7.  
  8.  
  9. class Arithmetic:
  10.  
  11.  
  12.     def __init__(self, freqs_tuples, MAX):
  13.  
  14.         # верхняя граница интервала
  15.  
  16.         self.max = MAX
  17.  
  18.         # подготовка словаря с интервалами вероятностей символов
  19.  
  20.         self.__freqs2dict( freqs_tuples )
  21.  
  22.  
  23.     def encode(self, s):
  24.  
  25.         u"""
  26.  
  27.             Кодирование строки s на основе вероятностей в self.freqs
  28.  
  29.             Возвращает число из итогового диапазона
  30.  
  31.         """
  32.  
  33.         # начинает с полного интервала [0,1)
  34.  
  35.         (f, t) = (0, self.max)
  36.  
  37.         for c in s:
  38.  
  39.             # координаты нового интервала
  40.  
  41.             (cf, ct) = self.freqs[c]
  42.  
  43.             # длина базового интервала
  44.  
  45.             t_f = t-f
  46.             print("base: %d\n" % t_f)
  47.  
  48.             # Получение нового интервала.
  49.  
  50.             # Важно: т.к. в вычислении фигурирует f, то его
  51.  
  52.             # изменение выполняется только после вычисления t.
  53.  
  54.             # Т.е. не надо менять строки местами : )
  55.  
  56.             t = int( floor( ct*t_f / self.max + f ) )
  57.  
  58.             f = int( floor( cf*t_f / self.max + f ) )
  59.             print("f: %d, t: %d, cf: %d, ct: %d, self.max: %d\n" % (f,t,cf,ct,self.max))
  60.  
  61.         return ( f, t )
  62.  
  63.  
  64.     def decode(self, i):
  65.  
  66.         u"""
  67.  
  68.             Декодирование числа в строку на основе вероятностей в self.freqs
  69.  
  70.         """
  71.  
  72.         res = []
  73.  
  74.         c = None
  75.  
  76.         while c != '#':
  77.  
  78.             c = self.__find_interval( i )
  79.  
  80.             res.append( c )
  81.  
  82.             (f,t) = self.freqs[c]
  83.  
  84.             i = int( ( i-f ) * self.max / ( t-f ) )
  85.  
  86.         return ''.join(res)
  87.  
  88.  
  89.     def __freqs2dict(self, freqs_tuples):
  90.  
  91.         u"""
  92.  
  93.             Преобразование кортежа вероятностей символов строки в
  94.  
  95.               словарь интервалов с учетом self.max
  96.  
  97.         """
  98.  
  99.         self.freqs = {}
  100.  
  101.         left = 0
  102.  
  103.         for (k,v) in freqs:
  104.  
  105.             self.freqs[k] = ( int(left*self.max), int((left+v)*self.max) )
  106.  
  107.             left += v
  108.  
  109.  
  110.     def __optimize(self, f, t):
  111.  
  112.         u"""
  113.  
  114.             Подбор числа из диапазона [f, t) такого, чтобы в нем
  115.  
  116.             было максимально возможное на интервале число нулевых младших бит
  117.  
  118.         """
  119.  
  120.         #return int( (t-f)/2 + f )
  121.  
  122.         f = int(f)
  123.  
  124.         t = int(t)
  125.  
  126.         x = f ^ t
  127.  
  128.         if not x: return f
  129.  
  130.  
  131.         xl = int( ceil( log(x, 2) ) )
  132.  
  133.         if not xl: return f
  134.  
  135.  
  136.         mask_and = ~((1<<xl)-1)
  137.  
  138.         mask_or  = 1<<(xl-1)
  139.  
  140.  
  141.         r = (f & mask_and) | mask_or
  142.  
  143.  
  144.         return r
  145.  
  146.  
  147.     def __find_interval(self, v):
  148.  
  149.         u"""
  150.  
  151.             Ищем интервал, которому принадлежит значение v
  152.  
  153.         """
  154.  
  155.         for ( c, (cf, ct) ) in self.freqs.items():
  156.  
  157.             if v>=cf and v<ct:
  158.  
  159.                 return c
  160.  
  161.  
  162. freqs = ( ('a',0.4), ('b',0.2), ('h',0.1), ('r',0.25), ('#',0.05) )
  163.  
  164. src = 'abraha#'
  165.  
  166. MAX = 100000000
  167.  
  168.  
  169. coder = Arithmetic( freqs, MAX )
  170.  
  171.  
  172. print 'SOURCE:  ', src
  173.  
  174.  
  175. enc = coder.encode( src )
  176.  
  177. print 'ENCODED: ', enc
  178.  
  179.  
  180. #dec = coder.decode( enc )
  181.  
  182. #print 'DECODED: ', dec
  183.  
  184.  
Success #stdin #stdout 0s 23304KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
SOURCE:   abraha#
base: 100000000

f: 0, t: 40000000, cf: 0, ct: 40000000, self.max: 100000000

base: 40000000

f: 16000000, t: 24000000, cf: 40000000, ct: 60000000, self.max: 100000000

base: 8000000

f: 21600000, t: 23600000, cf: 70000000, ct: 95000000, self.max: 100000000

base: 2000000

f: 21600000, t: 22400000, cf: 0, ct: 40000000, self.max: 100000000

base: 800000

f: 22080000, t: 22160000, cf: 60000000, ct: 70000000, self.max: 100000000

base: 80000

f: 22080000, t: 22112000, cf: 0, ct: 40000000, self.max: 100000000

base: 32000

f: 22110400, t: 22112000, cf: 95000000, ct: 100000000, self.max: 100000000

ENCODED:  (22110400, 22112000)
https://ideone.com/sALvvl
language:
Python (cpython 2.7.16)
created:
7 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!