HW3.ipynb

{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": 71,
   "id": "519f1156",
   "metadata": {},
   "outputs": [],
   "source": [
    "import re\n",
    "from collections import Counter\n",
    "from more_itertools import sliced\n",
    "import random\n",
    "import numpy as np\n",
    "from copy import copy"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 72,
   "id": "41ed5d22",
   "metadata": {},
   "outputs": [],
   "source": [
    "SEED = 42\n",
    "np.random.seed(SEED)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 73,
   "id": "a0af994f",
   "metadata": {},
   "outputs": [],
   "source": [
    "with open('WarAndPeace.txt' ,'r', encoding='utf-8') as file:\n",
    "    corpus1 = file.readlines()\n",
    "with open('AnnaKarenina.txt' ,'r', encoding='utf-8') as file:\n",
    "    corpus2 = file.readlines()\n",
    "corpus = corpus1 + corpus2"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "6e0faf14",
   "metadata": {},
   "source": [
    "## Реализуйте базовый частотный метод по Шерлоку Холмсу"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 74,
   "id": "87df1e6d",
   "metadata": {},
   "outputs": [],
   "source": [
    "def preprocess_text(text):\n",
    "    reg = re.compile(\"[а-я ]\")\n",
    "    text = ''.join(text).lower()\n",
    "    text = ''.join(reg.findall(text))\n",
    "    return text"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 75,
   "id": "090fadf3",
   "metadata": {},
   "outputs": [],
   "source": [
    "def count_freq(corpus, n):\n",
    "    tokens = set(list(sliced(corpus, n)))\n",
    "    freq_dict = {token : corpus.count(token) for token in tokens} \n",
    "    freq_dict = {k: v / len(corpus) for k, v in freq_dict.items()}\n",
    "    freq_dict = {k: v for k, v in sorted(freq_dict.items(), key=lambda item: item[1], reverse=True)}\n",
    "    return freq_dict"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 76,
   "id": "bbe56542",
   "metadata": {},
   "outputs": [],
   "source": [
    "def encode(text, freq_dict, n):\n",
    "    alphabet = list(freq_dict.keys())\n",
    "    shuffled = random.sample(alphabet, len(alphabet))\n",
    "    mapping = dict(zip(alphabet, shuffled))\n",
    "    encoded_text = ''.join(list(map(lambda x: mapping[x], list(sliced(text, n)))))\n",
    "    return encoded_text"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 77,
   "id": "0eaf493c",
   "metadata": {},
   "outputs": [],
   "source": [
    "def decode(text, freq_dict, n):\n",
    "    decoded_freq = count_freq(text, n)\n",
    "    mapping = dict(zip(decoded_freq.keys(), freq_dict.keys()))\n",
    "    decoded_text = ''.join(list(map(lambda x: mapping[x], list(sliced(text, n)))))\n",
    "    return decoded_text"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 78,
   "id": "2221b66d",
   "metadata": {},
   "outputs": [],
   "source": [
    "def check_accuracy(real_text, decoded_text):\n",
    "    return sum(np.array(list(real_text)) == np.array(list(decoded_text))) / len(decoded_text)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 79,
   "id": "0d64617a",
   "metadata": {},
   "outputs": [],
   "source": [
    "corpus = preprocess_text(corpus)\n",
    "unigramm_freq = count_freq(corpus, 1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 82,
   "id": "22d495e6",
   "metadata": {},
   "outputs": [],
   "source": [
    "text = 'Все смешалось в доме Облонских. Жена узнала, что муж был в связи с бывшею в их доме француженкою гувернанткой, и \\\n",
    "объявила мужу, что не может жить с ним в одном доме. Положение это продолжалось уже третий день и мучительно чувствовалось \\\n",
    "и самими супругами, и всеми членами семьи, и домочадцами. Все члены семьи и домочадцы чувствовали, что нет смысла в их \\\n",
    "сожительстве и что на каждом постоялом дворе случайно сошедшиеся люди более связаны между собой, чем они, члены семьи \\\n",
    "и домочадцы Облонских. Жена не выходила из своих комнат, мужа третий день не было дома.'\n",
    "text = preprocess_text(text)\n",
    "encoded_text = encode(text, unigramm_freq, 1)\n",
    "decoded_text = decode(encoded_text, unigramm_freq, 1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 83,
   "id": "a40e595c",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Предобработанный текст:\t все смешалось в доме облонских жена узнала что муж был в связи с бывшею в их доме француженкою гувернанткой и объявила мужу что не может жить с ним в одном доме положение это продолжалось уже третий день и мучительно чувствовалось и самими супругами и всеми членами семьи и домочадцами все члены семьи и домочадцы чувствовали что нет смысла в их сожительстве и что на каждом постоялом дворе случайно сошедшиеся люди более связаны между собой чем они члены семьи и домочадцы облонских жена не выходила из своих комнат мужа третий день не было дома \n",
      "\n",
      "Зашифрованный текст:\t нцьмцйьзлвтцфмнмстйьмтхвтацяопмшьалме алвлмщгтмйешмхувмнмцнж омцмхунзькмнмопмстйьмиылачешьаяткмбеньыалагятрмомтхджновлмйешемщгтмаьмйтшьгмшогфмцмаоймнмтсатймстйьмютвтшьаоьмэгтмюытствшлвтцфмешьмгыьгормсьафмомйещогьвфатмщенцгнтнлвтцфмомцлйойомцеюыеблйомомнцьйомщвьалйомцьйфомомстйтщлсчлйомнцьмщвьаумцьйфомомстйтщлсчумщенцгнтнлвомщгтмаьгмцйуцвлмнмопмцтшогьвфцгньмомщгтмалмялшстймютцгтжвтймснтыьмцвещлратмцтзьсзоьцжмвксомхтвььмцнж лаумйьшсемцтхтрмщьймтаомщвьаумцьйфомомстйтщлсчумтхвтацяопмшьалмаьмнуптсовлмо мцнтопмятйалгмйешлмгыьгормсьафмаьмхувтмстйл \n",
      "\n",
      "Расшифрованный с помощью униграмм текст:\t вие инехтлоип в коне оьлосиыаб уест дйстлт мро нду ьял в ивчйа и ьявхею в аб коне цгтсшдуесыою эдвегстсрыоз а оьфчвалт ндуд мро се ноуер уарп и сан в оксон коне жолоуесае щро жгоколутлоип дуе ргераз кесп а ндмарелпсо мдвирвовтлоип а итнана иджгдэтна а виена млестна иенпа а кономткштна вие млеся иенпа а кономткшя мдвирвовтла мро сер иняилт в аб иоуарелпирве а мро ст ытукон жоирочлон квоге илдмтзсо иохекхаеич люка ьолее ивчйтся неукд иоьоз мен оса млеся иенпа а кономткшя оьлосиыаб уест се вябокалт ай ивоаб ыонстр ндут ргераз кесп се ьяло конт \n",
      "\n",
      "Точность:\t 0.4249084249084249\n"
     ]
    }
   ],
   "source": [
    "print('Предобработанный текст:\\t', text, '\\n')\n",
    "print('Зашифрованный текст:\\t', encoded_text, '\\n')\n",
    "print('Расшифрованный с помощью униграмм текст:\\t', decoded_text, '\\n')\n",
    "print('Точность:\\t', check_accuracy(text, decoded_text))"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "bb14505c",
   "metadata": {},
   "source": [
    "## Базовый частотный метод на биграммах"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 84,
   "id": "14d9afa2",
   "metadata": {},
   "outputs": [],
   "source": [
    "bigramm_freq = count_freq(corpus, 2)\n",
    "encoded_text = encode(text, bigramm_freq, 2)\n",
    "decoded_text = decode(encoded_text, bigramm_freq, 2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 85,
   "id": "d50add26",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Зашифрованный текст:\t жозбрпузхбюмроъ будкэгмэыммвдртгдньхбмгецнжлиюуадхйсьгюшь  яйиь йстхмффтъ дргжбкзбсхврзетувъщоомбнтогеьс зштаэпуирэнцнуадхдшячб йкуазцаятгкмрозшобудъ йэгуудбудкживтзцднпыпчиюжикцбуысхбюмродхзбпкаяллгжднроаэижэричяггужлбнлчзмыг лшфхль тфпюаэитоидетфаэаэжофиаэкоднтфаэсзлбаэаэбуч тнлмтфаэжозбкодналсзлбаэаэбуч тнлмалгржо окюхбаэячб йкффрпынцнюшхлдиярюжичяглчюбхлжлиюл ьхтдрвбкжиюмиюцббкгжзмфнь нытнтьб ярмфввпыизчткдаэшсукзбюнухвралдкрвдшяршсштычудымаэкодналсзлбаэаэбуч тнлмалпу лширядитугел збуфяиаюцнхлснюнюсди збиенуадхьхпкаяллгжднройкйсьгб буцэ \n",
      "\n",
      "Расшифрованный с помощью биграмм текст:\t неа елчеко б н чи оны емт чтпрзае л аменнаво сст окалек алол уалкасьм ма чпрноя а велиасри зслннлотеентв дтьо й в менаст оваодпоосстору заль натая п чегта пи он кныоре роим с кжеи ивко б н оа виу анное  но автрн сктаволо  дему ммоь алто го омвымитоо о необо ове тоо нигоо о и  т илатоо неа ове  внигоо о и  т ила веснедонукоо одпоос еелазнак ь раотогн ск  руь во сетл итакя  к б серя нодеылалти и эпоотм серою  а ро ребыа илвсли вонакваотретьой пт о ове  внигоо о и  т ила вй  мкисярариенета арэтиннаь х илс ра ддаейст ол виу анное  носкалепои  л \n",
      "\n",
      "Точность:\t 0.08058608058608059\n"
     ]
    }
   ],
   "source": [
    "print('Зашифрованный текст:\\t', encoded_text, '\\n')\n",
    "print('Расшифрованный с помощью биграмм текст:\\t', decoded_text, '\\n')\n",
    "print('Точность:\\t', check_accuracy(text, decoded_text))"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "8102aa7f",
   "metadata": {},
   "source": [
    "## MCMC-сэмплирование"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "d2a25073",
   "metadata": {},
   "source": [
    "Алгоритм итеративно выполняет следующие шаги:\n",
    "- Меняет местами две случайные буквы в закодированном тексте\n",
    "- Исходя из частоты встречаемости биграмм, оцененной на тренировочном корпусе, оценивается веротяность закодированного текста (произведение вероятностей биграмм)\n",
    "- Если веротяность оказалось лучше, то она принимается за текущую с веротяностью прямо пропорциональной новой и обратно пропорциональной текущей вероятности"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 98,
   "id": "410727a6",
   "metadata": {},
   "outputs": [],
   "source": [
    "alphabet = 'абвгдеёжзийклмнопрстуфхцчшщъыьэюя '\n",
    "replacement = 1 / len(alphabet) ** 2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 38,
   "id": "0f5c1212",
   "metadata": {},
   "outputs": [],
   "source": [
    "def get_proba(text, known_freqs, replacement):\n",
    "    tokens = set(list(sliced(text, 2)))\n",
    "    new_freq_dict = {token : text.count(token) for token in tokens} \n",
    "    probability = np.sum([count * np.log(known_freqs.get(bigram, replacement)) \n",
    "                          for bigram, count in new_freq_dict.items()])\n",
    "    return probability\n",
    "\n",
    "def mutate(text, alphabet):\n",
    "    buf = '@'\n",
    "    [l1, l2] = random.sample(alphabet, 2)\n",
    "    text = text.replace(l1, buf)\n",
    "    text = text.replace(l2, l1)\n",
    "    text = text.replace(buf, l2)\n",
    "    return text\n",
    "\n",
    "def accept(prob, new_prob):\n",
    "    if new_prob > prob:\n",
    "        return True\n",
    "    return np.random.rand() < np.exp(new_prob - prob)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 70,
   "id": "a3809ede",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "вдюпдьюгхъыдопвпбыьюпыаъылднйшпфюлхпицлхъхпжзыпьифпащъпвпдвкцйпдпащвгютпвпйшпбыьюпр хлёифюлнытпеивю лхлзнычпйпыауквйъхпьифипжзыплюпьыфюзпфйзопдплйьпвпыблыьпбыьюпмыъыфюлйюпязыпм ыбыъфхъыдопифюпз юзйчпбюлопйпьижйзюъолыпживдзвывхъыдопйпдхьйьйпдим иехьйпйпвдюьйпжъюлхьйпдюьойпйпбыьыжхбёхьйпвдюпжъюлщпдюьойпйпбыьыжхбёщпживдзвывхъйпжзыплюзпдьщдъхпвпйшпдыфйзюъодзвюпйпжзыплхпнхфбыьпмыдзыкъыьпбвы юпдъижхчлыпдыгюбгйюдкпътбйпаыъююпдвкцхлщпьюфбипдыаычпжюьпылйпжъюлщпдюьойпйпбыьыжхбёщпыаъылднйшпфюлхплюпвщшыбйъхпйцпдвыйшпныьлхзпьифхпз юзйчпбюлоплюпащъыпбыьх \n",
      "\n",
      "\n",
      "сте тремидоть с горе окдонтпаю чени узниди жво руч кыд с тсяза т кысмей с аю горе шлинёученпой эуселнинвпох а окъясади ручу жво не рочев чавь т нар с огнор горе бодоченае фво блогодчидоть уче влевах гень а ружаведьно жуствсосидоть а тирара тублуэира а стера жденира терьа а горожигёира сте ждены терьа а горожигёы жуствсосида жво нев трытди с аю точаведьтвсе а жво ни пичгор ботвоядор гсоле тдужихно томегмаетя дйга кодее тсязины речгу токох жер она ждены терьа а горожигёы окдонтпаю чени не сыюогади аз тсоаю порнив ручи влевах гень не кыдо гори \n",
      "\n",
      "\n",
      "все снешалось в доне облорским жера узрала что нуж был в связи с бывшею в им доне фъарёужеркою гувеърарткой и общявила нужу что ре ножет жить с рин в одрон доне положерие это пъодолжалось уже тъетий дерь и нучительро чувствовалось и санини супъугани и всени члерани сеньи и доночадёани все члеры сеньи и доночадёы чувствовали что рет снысла в им сожительстве и что ра каждон постоялон двоъе случайро сошедшиеся люди более связары нежду собой чен ори члеры сеньи и доночадёы облорским жера ре вымодила из своим конрат нужа тъетий дерь ре было дона \n",
      "\n",
      "\n",
      "все снешалось в доне облорским жера узрала что нуж был в связи с бывшею в им доне фъарёужеркою гувеърарткой и общявила нужу что ре ножет жить с рин в одрон доне положерие это пъодолжалось уже тъетий дерь и нучительро чувствовалось и санини супъугани и всени члерани сеньи и доночадёани все члеры сеньи и доночадёы чувствовали что рет снысла в им сожительстве и что ра каждон постоялон двоъе случайро сошедшиеся люди более связары нежду собой чен ори члеры сеньи и доночадёы облорским жера ре вымодила из своим конрат нужа тъетий дерь ре было дона \n",
      "\n",
      "\n",
      "все снешалось в доне облорским жера узрала что нуж был в связи с бывшею в им доне фъарёужеркою гувеърарткой и общявила нужу что ре ножет жить с рин в одрон доне положерие это пъодолжалось уже тъетий дерь и нучительро чувствовалось и санини супъугани и всени члерани сеньи и доночадёани все члеры сеньи и доночадёы чувствовали что рет снысла в им сожительстве и что ра каждон постоялон двоъе случайро сошедшиеся люди более связары нежду собой чен ори члеры сеньи и доночадёы облорским жера ре вымодила из своим конрат нужа тъетий дерь ре было дона \n",
      "\n",
      "\n",
      "все снешалось в доне облорским жера узрала что нуж был в связи с бывшею в им доне фъарёужеркою гувеърарткой и общявила нужу что ре ножет жить с рин в одрон доне положерие это пъодолжалось уже тъетий дерь и нучительро чувствовалось и санини супъугани и всени члерани сеньи и доночадёани все члеры сеньи и доночадёы чувствовали что рет снысла в им сожительстве и что ра каждон постоялон двоъе случайро сошедшиеся люди более связары нежду собой чен ори члеры сеньи и доночадёы облорским жера ре вымодила из своим конрат нужа тъетий дерь ре было дона \n",
      "\n",
      "\n"
     ]
    }
   ],
   "source": [
    "text = encoded_text\n",
    "best_decoded_text = copy(text)\n",
    "cur_proba = best_proba =  get_proba(text, bigram_freqs, replacement)\n",
    "for iteration in range(30000):\n",
    "    new_text = mutate(copy(text), alphabet)\n",
    "    new_proba = get_proba(new_text, bigram_freqs, replacement)\n",
    "    if accept(cur_proba, new_proba):\n",
    "        text = new_text\n",
    "        cur_proba = new_proba\n",
    "        if cur_proba > best_proba:\n",
    "            best_proba = cur_proba\n",
    "            best_decoded_text = copy(text)\n",
    "\n",
    "    if iteration % 5000 == 0:\n",
    "        print(best_decoded_text, '\\n\\n')"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "1313a6a8",
   "metadata": {},
   "source": [
    "В целом, результат намного лучше, чем в частотном методе, но не все буквы корректно расшифровались. Еще один минус в том, что разные запуски дают разный результат, порой не осмысленный."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "5e84346e",
   "metadata": {},
   "source": [
    "## Расшифруйте сообщение"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 133,
   "id": "3e4fe1de",
   "metadata": {},
   "outputs": [],
   "source": [
    "text = '←⇠⇒↟↹↷⇊↹↷↟↤↟↨←↹↝⇛⇯↳⇴⇒⇈↝⇊↾↹↟⇒↟↹⇷⇛⇞↨↟↹↝⇛⇯↳⇴⇒⇈↝⇊↾↹↨←⇌⇠↨↹⇙↹⇸↨⇛↙⇛↹⇠⇛⇛↲⇆←↝↟↞↹⇌⇛↨⇛⇯⇊↾↹⇒←↙⇌⇛↹⇷⇯⇛⇞↟↨⇴↨⇈↹⇠⇌⇛⇯←←↹↷⇠←↙⇛↹↷⇊↹↷⇠←↹⇠↤←⇒⇴⇒↟↹⇷⇯⇴↷↟⇒⇈↝⇛↹↟↹⇷⇛⇒⇙⇞↟↨←↹↳⇴⇌⇠↟↳⇴⇒⇈↝⇊↾↹↲⇴⇒⇒↹⇰⇴↹⇷⇛⇠⇒←↤↝←←↹⇞←↨↷←⇯↨⇛←↹⇰⇴↤⇴↝↟←↹⇌⇙⇯⇠⇴↹↘⇛↨↞↹⇌⇛↝←⇞↝⇛↹↞↹↝↟⇞←↙⇛↹↝←↹⇛↲←⇆⇴⇏'"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 134,
   "id": "02eda22a",
   "metadata": {},
   "outputs": [],
   "source": [
    "unigram_decoded = decode(text, unigramm_freq, 1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 137,
   "id": "96b4a3f3",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "олна км кагасо иевьънуимы ана педса иевьънуимы сорлс ч хсеяе леезжоиаб ресевмы нояре пведасъсу лревоо клояе км кло лгонъна пвъкануие а пенчдасо ьърлаьънуимы зънн йъ пелногиоо досковсео йъгъиао рчвлъ шесб реиодие б иадояе ио езожъю \n",
      "\n",
      "\n",
      "отла кы казано верёилувыь ала педна верёилувыь ностн г фнеже теемйовая сенерыь ложсе преданину тсероо ктоже кы кто тзолила прикалуве а пелгдано ёистаёилувыь милл чи петлозвоо донкорнео чизивао сгрти беня севодве я вадоже во емойиц \n",
      "\n",
      "\n",
      "если вы вижите нордальный или почти нордальный текст у бтого соомёения который легко прочитать скорее всего вы все сжелали правильно и получите даксидальный малл за послежнее четвертое зажание курса эотя конечно я ничего не омеёаъ \n",
      "\n",
      "\n",
      "если вы вимите нодральный или пожти нодральный текст ч хтого сообёения котодый легко пдожитать скодее всего вы все смелали пдавильно и полчжите раксиральный балл за послемнее жетведтое замание кчдса уотя конежно я нижего не обеёаю \n",
      "\n",
      "\n",
      "если вы вимите нодральный или пожти нодральный текст у чтого сообёения котодый легко пдожитать скодее всего вы все смелали пдавильно и полужите раксиральный балл за послемнее жетведтое замание кудса эотя конежно я нижего не обеёаю \n",
      "\n",
      "\n",
      "если вы вимите нодральный или пожти нодральный текст у чтого сообёения котодый легко пдожитать скодее всего вы все смелали пдавильно и полужите раксиральный балл за послемнее жетведтое замание кудса эотя конежно я нижего не обеёаю \n",
      "\n",
      "\n"
     ]
    }
   ],
   "source": [
    "text = unigram_decoded\n",
    "best_decoded_text = copy(text)\n",
    "cur_proba = best_proba =  get_proba(text, bigram_freqs, replacement)\n",
    "for iteration in range(30000):\n",
    "    new_text = mutate(copy(text), alphabet)\n",
    "    new_proba = get_proba(new_text, bigram_freqs, replacement)\n",
    "    if accept(cur_proba, new_proba):\n",
    "        text = new_text\n",
    "        cur_proba = new_proba\n",
    "        if cur_proba > best_proba:\n",
    "            best_proba = cur_proba\n",
    "            best_decoded_text = copy(text)\n",
    "\n",
    "    if iteration % 5000 == 0:\n",
    "        print(best_decoded_text, '\\n\\n')"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.8.3"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}