jakobsen3.py

   1 """Modul pro praci s Jakobsenovym algoritmem."""
   2
   3 from itertools import combinations
   4 import pickle
   5 from ocesavac import ocesat
   6 from spolecne import MABECEDA
   7
   8 def nova_tabulka(zprava, abc=MABECEDA):
   9     """Vraci tabulku cetnosti bigramu ve zprave nad danou abecedou."""
  10     tabulka = dict()
  11     for i in abc:
  12         tabulka[i] = dict()
  13         for j in abc:
  14             tabulka[i][j] = 0
  15     for i in range(len(zprava) - 1):
  16         tabulka[zprava[i]][zprava[i+1]] += 1
  17     celkem = sum(sum(tab2.values()) for tab2 in tabulka.values())
  18     for i in abc:
  19         for j in abc:
  20             tabulka[i][j] /= float(celkem)
  21     return tabulka
  22
  23 def vzdalenost(tab1, tab2, abc=MABECEDA):
  24     """Vraci soucet strednich kvadratickych odchylek pro dve tabulky cetnosti
  25     bigramu nad danou abecedou."""
  26     rozdil = 0
  27     for i in abc:
  28         for j in abc:
  29             rozdil += abs(tab1[i][j] - tab2[i][j])
  30     return rozdil
  31
  32 def substituce(zprava, slovnik):
  33     """Vrati zpravu, ve ktere jsou znaky dane abecedy nahrazenypodle daneho
  34     slovniku."""
  35     pole = []
  36     for char in zprava:
  37         if char in slovnik:
  38             pole.append(slovnik[char])
  39         else:
  40             pole.append(char)
  41     return pole
  42
  43 def poradi_dle_frekvence(zprava, abc=MABECEDA):
  44     """Vrati znaky dane abecedy v poradi podle frekvence v dane zprave."""
  45     freq = dict()
  46     for char in abc:
  47         freq[char] = 0
  48     for char in zprava:
  49         if char in abc:
  50             freq[char] += 1
  51     return sorted(freq.keys(), key=freq.get, reverse=True)
  52
  53 class reference:
  54     pass
  55
  56 def jakobsen(zprava, ref):
  57     """Pro danou sifrovanou zpravu vrati substitucni slovnik odvozeny s pomoci
  58     Jakobsenova algoritmu s danou referencni tabulkou."""
  59     # s lepsim poradim prohazovani
  60     slovnik = dict(zip(poradi_dle_frekvence(zprava, ref.abeceda), ref.poradi))
  61     tabulka = nova_tabulka(
  62                   substituce(zprava, slovnik),
  63                   ref.abeceda
  64                   )
  65     vzdal = vzdalenost(tabulka, ref.tabulka, ref.abeceda)
  66
  67     a, b = 1, 1
  68
  69     slvnk = ref.poradi
  70
  71     while b < len(ref.abeceda):
  72         x, y = slvnk[a-1], slvnk[a+b-1]
  73         slovnik[x], slovnik[y] = slovnik[y], slovnik[x]
  74         nova_vzdalenost = vzdalenost(
  75                     nova_tabulka(
  76                         substituce(zprava, slovnik),
  77                         ref.abeceda),
  78                     ref.tabulka,
  79                     ref.abeceda)
  80         if  nova_vzdalenost < vzdal:
  81             vzdal = nova_vzdalenost
  82             slvnk[a-1], slvnk[a+b-1] = slvnk[a+b-1], slvnk[a-1]
  83             a, b = 1, 1
  84         else:
  85             slovnik[x], slovnik[y] = slovnik[y], slovnik[x]
  86             a += 1
  87             if a + b > len(ref.abeceda):
  88                 a, b = 1, b + 1
  89     return slovnik
  90
  91
  92 def desifruj(zprava, mezery=True):
  93     """Vrati vysledek pokusu dekodovat zpravu Jakobsenovym algoritmem."""
  94     if mezery:
  95         soubor = open('ref')
  96     else:
  97         soubor = open('bref')
  98     ref = pickle.load(soubor)
  99     soubor.close()
 100     slovnik = jakobsen(ocesat(zprava, mezery), ref)
 101     return '\n'.join([''.join(substituce(zprava, slovnik)),
 102                       ' '.join(ref.abeceda),
 103                       ' '.join([slovnik[c] for c in ref.abeceda])])
 104
 105 def __test():
 106     print desifruj('Mxbhfxn cbfbhinpr, wnx fv f gvzuyr cbenqv.'.upper())
 107
 108 def __test2():
 109     print desifruj('Sel pes do lesa a potkal dlazebni kostku. Chtelo by to jeste o neco delsi test, to tedy jo.'.upper())