jakobsen.py

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