jakobsen1.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 vzdalenost2(tab1, tab2):
  33     """Vraci soucet strednich kvadratickych odchylek pro dve tabulky cetnosti
  34     bigramu nad danou abecedou."""
  35     rozdil = 0
  36     for i in range(len(tab1)):
  37         for j in range(len(tab1)):
  38             rozdil += abs(tab1[i][j] - tab2[i][j])
  39     return rozdil
  40
  41 def substituce(zprava, slovnik, abc=MABECEDA):
  42     """Vrati zpravu, ve ktere jsou znaky dane abecedy nahrazenypodle daneho
  43     slovniku."""
  44     pole = []
  45     for char in zprava:
  46         if char in abc:
  47             pole.append(slovnik[char])
  48         else:
  49             pole.append(char)
  50     return pole
  51
  52 def poradi_dle_frekvence(zprava, abc=MABECEDA):
  53     """Vrati znaky dane abecedy v poradi podle frekvence v dane zprave."""
  54     freq = dict()
  55     for char in abc:
  56         freq[char] = 0
  57     for char in zprava:
  58         if char in abc:
  59             freq[char] += 1
  60     return sorted(freq.keys(), key=freq.get, reverse=True)
  61
  62 class reference:
  63     pass
  64
  65 def prohod(sl_a, sl_b, tabulka):
  66     """Vrati tabulku s prohozenou dvojici sloupcu a radku."""
  67     tabulka[sl_a], tabulka[sl_b] = tabulka[sl_b], tabulka[sl_a]
  68     for c in tabulka.keys():
  69         tabulka[c][sl_a], tabulka[c][sl_b] = tabulka[c][sl_b], tabulka[c][sl_a]
  70     return
  71
  72 def prohod2(sl_a, sl_b, tabulka):
  73     """Vrati tabulku s prohozenou dvojici sloupcu a radku."""
  74     tabulka[sl_a], tabulka[sl_b] = tabulka[sl_b], tabulka[sl_a]
  75     for c in range(len(tabulka)):
  76         tabulka[c][sl_a], tabulka[c][sl_b] = tabulka[c][sl_b], tabulka[c][sl_a]
  77     return
  78
  79 def dicty_na_listy(tabulka, abeceda):
  80     listy = []
  81     for a in abeceda:
  82         listy.append([tabulka[a][b] for b in abeceda])
  83     return listy
  84
  85 def jakobsen(zprava, ref):
  86     """Pro danou sifrovanou zpravu vrati substitucni slovnik odvozeny s pomoci
  87     Jakobsenova algoritmu s danou referencni tabulkou."""
  88     slovnik = poradi_dle_frekvence(zprava, ref.abeceda)
  89     tab = nova_tabulka(zprava, ref.abeceda)
  90
  91     tabulka = dicty_na_listy(tab, slovnik)
  92     reftab = dicty_na_listy(ref.tabulka, ref.poradi)
  93
  94     vzdal = vzdalenost2(tabulka, reftab)
  95
  96     vzdal_old = vzdal + 1
  97     while vzdal_old > vzdal:
  98         vzdal_old = vzdal
  99         for (x, y) in combinations(range(len(ref.abeceda)), 2):
 100             prohod2(x, y, tabulka)
 101             nova_vzdalenost = vzdalenost2(tabulka, reftab)
 102             if nova_vzdalenost < vzdal:
 103                 vzdal = nova_vzdalenost
 104                 slovnik[x], slovnik[y] = slovnik[y], slovnik[x]
 105             else:
 106                 prohod2(x, y, tabulka)
 107     return dict(zip(slovnik, ref.poradi))
 108
 109 def desifruj(zprava, mezery=True):
 110     """Vrati vysledek pokusu dekodovat zpravu Jakobsenovym algoritmem."""
 111     if mezery:
 112         soubor = open('ref')
 113     else:
 114         soubor = open('bref')
 115     ref = pickle.load(soubor)
 116     soubor.close()
 117     slovnik = jakobsen(ocesat(zprava, mezery), ref)
 118     return '\n'.join([''.join(substituce(zprava, slovnik, ref.abeceda)),
 119                       ' '.join(ref.abeceda),
 120                       ' '.join([slovnik[c] for c in ref.abeceda])])
 121
 122 def __test():
 123     print desifruj('Mxbhfxn cbfbhinpr, wnx fv f gvzuyr cbenqv.'.upper())
 124
 125 def __test2():
 126     print desifruj('Sel pes do lesa a potkal dlazebni kostku. Chtelo by to jeste o neco delsi test, to tedy jo.'.upper())