main_HMM_homophonic.ipynb

{
 "cells": [
  {
   "attachments": {},
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# HMM for decryption\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 196,
   "metadata": {},
   "outputs": [],
   "source": [
    "from src.CipherUtils import CipherGenerator\n",
    "from src.CipherUtils import TextEncoder\n",
    "from src.ProbabilityMatrix import ProbabilityMatrix\n",
    "from src.CipherUtils import TextPreProcessor\n",
    "\n",
    "from src.HMM_utils import map_alphabet_to_numbers, string_to_numbers\n",
    "from src.HMM_utils import find_mapping, numbers_to_string, invert_mapping\n",
    "from src.HMM_utils import convert_numbers_to_letters\n",
    "\n",
    "# from src.HMM_functions import Baum_Welch\n",
    "# from src.HMM_functions import compute_f_log, Viterbi_log, reconstruct\n",
    "\n",
    "import numpy as np"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 197,
   "metadata": {},
   "outputs": [],
   "source": [
    "import random \n",
    "def Homophonic_Cipher_Generator(extended_alphabet = list(\"abcdefghijklmnopqrstuvwxyz1234567890\")):\n",
    "    \"\"\"\n",
    "    Generates a permutation assigning to each letter one or potentially two of the symbols in the extended alphabet provided.\n",
    "    In this simple example it assigns letters as before + it assigns to some letters the numbers as well (can be generalized) \n",
    "    The output is kept as a dictionary.\n",
    "    \"\"\"\n",
    "    letters = extended_alphabet.copy()\n",
    "    letters = letters[0:26]\n",
    "    random.shuffle(letters)\n",
    "\n",
    "    letters_list = [letters[i:i+1] for i in range(0, len(letters), 1)]\n",
    "    for i in range(len(extended_alphabet) - 26):\n",
    "        index = random.randint(0, 25) # Select one of the existing letters\n",
    "        while(len(letters_list[index]) > 1):\n",
    "            index = random.randint(0, 25) # Select one of the existing letters\n",
    "        letters_list[index].append(i)\n",
    "\n",
    "    # print(letters_list)\n",
    "    d = {k:v for k,v in zip(extended_alphabet[0:26], letters_list)}\n",
    "    return(d)\n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 198,
   "metadata": {},
   "outputs": [],
   "source": [
    "def Encode_using_homophonic(text, cipher_dict):\n",
    "    \"\"\"\n",
    "    Encodes using the homophonic dictionary provided\n",
    "    We assume text has already been preprocessed to remove all puntctuation ...\n",
    "    \"\"\"\n",
    "    encoded_text = []\n",
    "    for char in text:\n",
    "        if char == ' ':\n",
    "            encoded_text.append(char)\n",
    "            continue\n",
    "            \n",
    "        if len(cipher_dict[char]) == 1:\n",
    "            encoded_char = cipher_dict[char]\n",
    "        else:\n",
    "            encoded_char = str(cipher_dict[char][random.randint(0,len(cipher_dict[char])-1)])  \n",
    "        \n",
    "        if isinstance(encoded_char, list):\n",
    "            encoded_char = str(encoded_char[0])\n",
    "        encoded_text.append(encoded_char)\n",
    "    \n",
    "    \n",
    "    return \"\".join(encoded_text)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 199,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "{'a': ['c'], 'b': ['a', 5], 'c': ['x'], 'd': ['y', 1], 'e': ['r'], 'f': ['q'], 'g': ['g', 4], 'h': ['j'], 'i': ['s', 9], 'j': ['m', 7], 'k': ['b'], 'l': ['k'], 'm': ['w', 6], 'n': ['v'], 'o': ['t'], 'p': ['z', 0], 'q': ['d', 8], 'r': ['i'], 's': ['h', 2], 't': ['l'], 'u': ['n'], 'v': ['e'], 'w': ['f'], 'x': ['o'], 'y': ['p', 3], 'z': ['u']}\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "'jrkkt 4tt1 cqlrivttv cv1 frkxt6r lt'"
      ]
     },
     "execution_count": 199,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "d = Homophonic_Cipher_Generator()\n",
    "print(d)\n",
    "t = Encode_using_homophonic(\"hello good afternoon and welcome to\", d)\n",
    "t"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 200,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "good afternoon today we will show\n",
      "veed r3x90qeeq 2ed7o at aucc ikea\n"
     ]
    }
   ],
   "source": [
    "#hidden_sequence = \"Hello how are you doing\"\n",
    "hidden_sequence = \"good afternoon today we will show \"\n",
    "preprocessor = TextPreProcessor()\n",
    "hidden_sequence = preprocessor.lower(text=hidden_sequence)\n",
    "hidden_sequence = preprocessor.remove_unknown_chars(\n",
    "    text=hidden_sequence, unknown_chars=preprocessor.unknown_chars(hidden_sequence)\n",
    ")\n",
    "hidden_sequence = preprocessor.remove_additional_spaces(text=hidden_sequence)\n",
    "\n",
    "d = Homophonic_Cipher_Generator()\n",
    "observed_sequence = Encode_using_homophonic(hidden_sequence, d)\n",
    "print(hidden_sequence)\n",
    "print(observed_sequence)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 173,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "hello banana xilophone key queue zebra cock pussy tits dandy fart though jolly world mum today i was going through the park and noticed that some people where looking at me in a weird way and thought that i was being silly\n",
      "sxdd5 obebeb u3dwzs5ex cx9 gr0rx p0okb i5ic zrmmh ql8m abe49 vbkq 8sw6ys jwddh 7wkd4 n6n 85ab9 l fbm y53ey 8sk56ys qsx zbkc bea ewq3i0a qsbq m5nx z05zd0 7s0k0 dw5cl1y bq nx l1 b 7x3ka fb9 b1a qs5rysq 8sb8 l fbm oxl1y m3dd9\n"
     ]
    }
   ],
   "source": [
    "#hidden_sequence = \"Hello how are you doing\"\n",
    "hidden_sequence = \"hello banana xilophone key queue dandy fart though jolly world mum today I was going through the park and noticed that some people where looking at me in a weird way and thought that I was being silly\"\n",
    "\n",
    "preprocessor = TextPreProcessor()\n",
    "hidden_sequence = preprocessor.lower(text=hidden_sequence)\n",
    "hidden_sequence = preprocessor.remove_unknown_chars(\n",
    "    text=hidden_sequence, unknown_chars=preprocessor.unknown_chars(hidden_sequence)\n",
    ")\n",
    "hidden_sequence = preprocessor.remove_additional_spaces(text=hidden_sequence)\n",
    "\n",
    "d = Homophonic_Cipher_Generator()\n",
    "observed_sequence = Encode_using_homophonic(hidden_sequence, d)\n",
    "print(hidden_sequence)\n",
    "print(observed_sequence)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 174,
   "metadata": {},
   "outputs": [],
   "source": [
    "# List of text file paths to build our corpus (where we learn the transitions probs)\n",
    "file_paths = [\n",
    "    \"texts/moby_dick.txt\",\n",
    "    \"texts/shakespeare.txt\",\n",
    "    \"texts/james-joyce-a-portrait-of-the-artist-as-a-young-man.txt\",\n",
    "    \"texts/james-joyce-dubliners.txt\",\n",
    "    \"texts/james-joyce-ulysses.txt\",\n",
    "]\n",
    "\n",
    "texts = []\n",
    "for file_path in file_paths:\n",
    "    with open(file_path, \"r\") as file:\n",
    "        texts.append(file.read())\n",
    "\n",
    "corpus = \"\".join(texts)\n",
    "alphabet = list(\"abcdefghijklmnopqrstuvwxyz \")\n",
    "\n",
    "preprocessor = TextPreProcessor()\n",
    "corpus = preprocessor.lower(text=corpus)\n",
    "corpus = preprocessor.remove_unknown_chars(\n",
    "    text=corpus, unknown_chars=preprocessor.unknown_chars(corpus)\n",
    ")\n",
    "corpus = preprocessor.remove_additional_spaces(text=corpus)\n",
    "\n",
    "# compute probabilities\n",
    "p = ProbabilityMatrix(corpus)\n",
    "p.compute_probability_matrix()\n",
    "p.compute_normalized_matrix()\n",
    "# p.compute_probability_table()"
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Go on\n",
    "\n",
    "Here we have to be more careful as we have to encode more.\n",
    "In our case (used here) 27 hidden states (letters + spaces) and these are emitted to 37 observed states (27 hidden + 10 digits), so we need to be careful in the conversion.\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 175,
   "metadata": {},
   "outputs": [],
   "source": [
    "def string_to_numbers(text, mapping):\n",
    "    \"\"\"\n",
    "    Converts a string of characters to a list of numbers based on the provided mapping.\n",
    "\n",
    "    Args:\n",
    "        text (str): The input string to be converted.\n",
    "        mapping (dict): A dictionary mapping characters to numbers.\n",
    "\n",
    "    Returns:\n",
    "        list: A list of numbers representing the characters in the input string.\n",
    "    \"\"\"\n",
    "    numbers = [mapping[char] for char in text]\n",
    "    return numbers"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 176,
   "metadata": {},
   "outputs": [],
   "source": [
    "mapping = {'a': 0, 'b': 1, 'c': 2, 'd': 3, 'e': 4, 'f': 5, 'g': 6, 'h': 7, 'i': 8, 'j': 9,\n",
    "           'k': 10, 'l': 11, 'm': 12, 'n': 13, 'o': 14, 'p': 15, 'q': 16, 'r': 17, 's': 18,\n",
    "           't': 19, 'u': 20, 'v': 21, 'w': 22, 'x': 23, 'y': 24, 'z': 25,\n",
    "           '0': 26, '1': 27, '2': 28, '3': 29, '4': 30, '5': 31, '6': 32, '7': 33, '8': 34,\n",
    "           '9': 35, ' ': 36}\n",
    "\n",
    "def string_to_numbers_updated(text, mapping):\n",
    "    \"\"\"\n",
    "    We convert a->0, b->1, ..., z->25, 0->26, 1->27, 2->28, ..., 9->35, ' '-> 36\n",
    "    \"\"\"\n",
    "    converted_string = [mapping[char] for char in text]\n",
    "    return converted_string"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 177,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[7, 4, 11, 11, 14, 36, 1, 0, 13, 0, 13, 0, 36, 23, 8, 11, 14, 15, 7, 14, 13, 4, 36, 10, 4, 24, 36, 16, 20, 4, 20, 4, 36, 25, 4, 1, 17, 0, 36, 2, 14, 2, 10, 36, 15, 20, 18, 18, 24, 36, 19, 8, 19, 18, 36, 3, 0, 13, 3, 24, 36, 5, 0, 17, 19, 36, 19, 7, 14, 20, 6, 7, 36, 9, 14, 11, 11, 24, 36, 22, 14, 17, 11, 3, 36, 12, 20, 12, 36, 19, 14, 3, 0, 24, 36, 8, 36, 22, 0, 18, 36, 6, 14, 8, 13, 6, 36, 19, 7, 17, 14, 20, 6, 7, 36, 19, 7, 4, 36, 15, 0, 17, 10, 36, 0, 13, 3, 36, 13, 14, 19, 8, 2, 4, 3, 36, 19, 7, 0, 19, 36, 18, 14, 12, 4, 36, 15, 4, 14, 15, 11, 4, 36, 22, 7, 4, 17, 4, 36, 11, 14, 14, 10, 8, 13, 6, 36, 0, 19, 36, 12, 4, 36, 8, 13, 36, 0, 36, 22, 4, 8, 17, 3, 36, 22, 0, 24, 36, 0, 13, 3, 36, 19, 7, 14, 20, 6, 7, 19, 36, 19, 7, 0, 19, 36, 8, 36, 22, 0, 18, 36, 1, 4, 8, 13, 6, 36, 18, 8, 11, 11, 24]\n",
      "[18, 23, 3, 3, 31, 36, 14, 1, 4, 1, 4, 1, 36, 20, 29, 3, 22, 25, 18, 31, 4, 23, 36, 2, 23, 35, 36, 6, 17, 26, 17, 23, 36, 15, 26, 14, 10, 1, 36, 8, 31, 8, 2, 36, 25, 17, 12, 12, 7, 36, 16, 11, 34, 12, 36, 0, 1, 4, 30, 35, 36, 21, 1, 10, 16, 36, 34, 18, 22, 32, 24, 18, 36, 9, 22, 3, 3, 7, 36, 33, 22, 10, 3, 30, 36, 13, 32, 13, 36, 34, 31, 0, 1, 35, 36, 11, 36, 5, 1, 12, 36, 24, 31, 29, 4, 24, 36, 34, 18, 10, 31, 32, 24, 18, 36, 16, 18, 23, 36, 25, 1, 10, 2, 36, 1, 4, 0, 36, 4, 22, 16, 29, 8, 26, 0, 36, 16, 18, 1, 16, 36, 12, 31, 13, 23, 36, 25, 26, 31, 25, 3, 26, 36, 33, 18, 26, 10, 26, 36, 3, 22, 31, 2, 11, 27, 24, 36, 1, 16, 36, 13, 23, 36, 11, 27, 36, 1, 36, 33, 23, 29, 10, 0, 36, 5, 1, 35, 36, 1, 27, 0, 36, 16, 18, 31, 17, 24, 18, 16, 36, 34, 18, 1, 34, 36, 11, 36, 5, 1, 12, 36, 14, 23, 11, 27, 24, 36, 12, 29, 3, 3, 35]\n"
     ]
    }
   ],
   "source": [
    "mapping = {'a': 0, 'b': 1, 'c': 2, 'd': 3, 'e': 4, 'f': 5, 'g': 6, 'h': 7, 'i': 8, 'j': 9,\n",
    "           'k': 10, 'l': 11, 'm': 12, 'n': 13, 'o': 14, 'p': 15, 'q': 16, 'r': 17, 's': 18,\n",
    "           't': 19, 'u': 20, 'v': 21, 'w': 22, 'x': 23, 'y': 24, 'z': 25,\n",
    "           '0': 26, '1': 27, '2': 28, '3': 29, '4': 30, '5': 31, '6': 32, '7': 33, '8': 34,\n",
    "           '9': 35, ' ': 36}\n",
    "hidden_ = string_to_numbers_updated(hidden_sequence, mapping = mapping)\n",
    "print(hidden_)\n",
    "\n",
    "observed_ = string_to_numbers(observed_sequence, mapping)\n",
    "print(observed_)"
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Now the emission probability has to be a 27 x 36 matrix, since there are more possible emissions than before.\n",
    "Update the code to reflect that."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 178,
   "metadata": {},
   "outputs": [],
   "source": [
    "def forward_HMM(A, B, pi, observed):\n",
    "    \"\"\"\n",
    "    A: transition\n",
    "    B: emission\n",
    "    pi: initial\n",
    "    n_nodes: number of nodes in the chain\n",
    "    observed: list containing observed ones.\n",
    "    \"\"\"\n",
    "    n_nodes = len(observed)\n",
    "    n_states = A.shape[0]\n",
    "    alpha = np.zeros((n_nodes, n_states))\n",
    "    c = np.zeros(n_nodes)\n",
    "    alpha_hat = np.zeros((n_nodes, n_states))\n",
    "\n",
    "    for j in range(n_states):\n",
    "        alpha[0, j] = pi[j] * B[j, observed[0]]\n",
    "\n",
    "    c[0] = np.sum(alpha[0])\n",
    "    alpha_hat[0] = alpha[0] / np.sum(alpha[0])\n",
    "    # print(\"alpa[0]\", alpha[0])\n",
    "\n",
    "    for i in range(1, n_nodes):\n",
    "        for j in range(n_states):\n",
    "            for k in range(n_states):\n",
    "                alpha[i, j] += A[k, j] * B[j, observed[i]] * alpha_hat[i - 1, k]\n",
    "        c[i] = np.sum(alpha[i])\n",
    "        alpha_hat[i] = alpha[i] / c[i]\n",
    "    return alpha_hat, c\n",
    "\n",
    "\n",
    "def backward_HMM(A, B, observed, c):\n",
    "    \"\"\"\n",
    "    A: transition\n",
    "    B: emission\n",
    "    n_nodes: number of nodes in the chain\n",
    "    observed: list containing observed ones.\n",
    "    \"\"\"\n",
    "    n_nodes = len(observed)\n",
    "    n_states = A.shape[0]\n",
    "    beta = np.zeros((n_nodes - 1, n_states))\n",
    "    beta_hat = np.zeros((n_nodes - 1, n_states))\n",
    "\n",
    "    for j in range(n_states):\n",
    "        for k in range(n_states):\n",
    "            beta[-1, j] += A[j, k] * B[k, observed[n_nodes - 1]]\n",
    "\n",
    "    beta_hat[-1] = beta[-1] / c[-1]\n",
    "\n",
    "    for i in range(n_nodes - 3, -1, -1):\n",
    "        for j in range(n_states):\n",
    "            for k in range(n_states):\n",
    "                beta[i, j] += A[j, k] * B[k, observed[i + 1]] * beta_hat[i + 1, k]\n",
    "        beta_hat[i] = beta[i] / c[i + 1]\n",
    "\n",
    "    return beta_hat\n",
    "\n",
    "\n",
    "def compute_all_conditional(alpha, beta):\n",
    "    \"\"\"\n",
    "    alpha: list containing forward messages\n",
    "    beta: list containing backward messages\n",
    "    \"\"\"\n",
    "    n_nodes = alpha.shape[0]\n",
    "    n_states = alpha.shape[1]\n",
    "\n",
    "    gamma = np.zeros((n_nodes, n_states))\n",
    "\n",
    "    gamma[n_nodes - 1] = alpha[n_nodes - 1] / np.sum(alpha[n_nodes - 1])\n",
    "\n",
    "    for i in range(n_nodes - 1):\n",
    "        tmp = alpha[i] * beta[i]\n",
    "        gamma[i] = tmp / np.sum(tmp)\n",
    "\n",
    "    return gamma\n",
    "\n",
    "\n",
    "def divide_row_by_sum(matrix):\n",
    "    row_sums = np.sum(matrix, axis=1)  # Calculate the sum of each row\n",
    "    divided_matrix = (\n",
    "        matrix / row_sums[:, np.newaxis]\n",
    "    )  # Divide each element by the corresponding row sum\n",
    "    return divided_matrix\n",
    "\n",
    "\n",
    "def update_B(gamma, observed):\n",
    "    # n_nodes = gamma.shape[0]\n",
    "    n_states = gamma.shape[1]\n",
    "\n",
    "    B = np.zeros((n_states, 37))\n",
    "\n",
    "    for i in range(n_states):\n",
    "        for j in range(37):\n",
    "            for k in range(len(observed)):\n",
    "                if observed[k] == j:\n",
    "                    B[i, j] += gamma[k, i]\n",
    "\n",
    "    return divide_row_by_sum(B)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 179,
   "metadata": {},
   "outputs": [],
   "source": [
    "def Baum_Welch(A, B_start, pi, observed, maxIter=100, tol = 1e-4):\n",
    "    B = np.copy(B_start)\n",
    "    changed = 0 # change is set to 1 whenever at least one coordinate increases by more than tol\n",
    "    for it in range(maxIter):\n",
    "        #print(\"computing alpha\")\n",
    "        alpha_hat, c = forward_HMM(A, B, pi, observed)\n",
    "        #print(\"alpha_hat\", alpha_hat.sum(axis = 1))\n",
    "        #print(\"computing beta\")\n",
    "        beta_hat = backward_HMM(A, B, observed, c)\n",
    "        #print(\"beta_hat\", beta_hat.sum(axis = 1))\n",
    "        #print(\"computing gamma\")\n",
    "        gamma = compute_all_conditional(alpha_hat, beta_hat)\n",
    "        #print(\"gamma\", gamma.sum(axis = 1))\n",
    "        B_old = B\n",
    "\n",
    "        #print(\"updating B\")\n",
    "        #print(B.sum(axis = 1))\n",
    "        B = update_B(gamma, observed)\n",
    "        #print(\"computing B\", B.sum(axis = 1))\n",
    "        # Check if conerged or still changing\n",
    "        change = np.abs(B - B_old)\n",
    "        max_change = np.max(change)\n",
    "\n",
    "        if(max_change < tol):\n",
    "            print(\"Not updating anymore after iteration\", it)\n",
    "            break\n",
    "\n",
    "\n",
    "        # following lines only for encryption\n",
    "        B[:, -1] = np.zeros(27)\n",
    "        B[-1, :] = np.zeros(37)\n",
    "        B[-1, -1] = 1\n",
    "    return B"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 186,
   "metadata": {},
   "outputs": [],
   "source": [
    "B_start = np.zeros((27, 37)) + 1 / 36\n",
    "B_start[:, -1] = np.zeros(27) # last column\n",
    "B_start[-1, :] = np.zeros(37) # last row\n",
    "B_start[-1, -1] = 1           # last entr\n",
    "\n",
    "emission = Baum_Welch(\n",
    "    A=p.normalized_matrix,\n",
    "    B_start=B_start,\n",
    "    pi=p.normalized_matrix[-1, :],\n",
    "    observed=observed_,\n",
    "    maxIter=100,\n",
    ")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 187,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "array([ 3,  8, 12, 10, 25, 22, 19, 24, 15,  5, 17,  0,  9,  1, 15,  1,  5,\n",
       "       17,  7,  0, 16, 22, 14,  4,  6,  2,  4, 13,  0, 20,  4, 23, 20,  2,\n",
       "       19, 18, 26])"
      ]
     },
     "execution_count": 187,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "emission.argmax(axis = 0) # I want the maximum by column to see to what letter each symbol is associated"
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Now let us proceed to apply the Viterbi algorithm to obtain the most likely reconstruction and compare how it performs with the one obtained just by using the emissions.\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 188,
   "metadata": {},
   "outputs": [],
   "source": [
    "\n",
    "def compute_f_log(A, B, observed):\n",
    "    \"\"\"\n",
    "    It constructs the factors of the HMM which are needed to perform the forward pass of the message passing algorithm.\n",
    "    Input:\n",
    "        - A : the transition matrix\n",
    "        - B : the emission matrix\n",
    "        - observed: an array containing the observed values\n",
    "    Output:\n",
    "        - f0: the factor corresponding to the initial factor to first latent variable message\n",
    "        - f: an array containig the all the other factors (n_states - 1)\n",
    "    \"\"\"\n",
    "    pi = A[-1]\n",
    "    n_nodes = len(observed)\n",
    "    n_states = A.shape[0]\n",
    "    f = np.zeros((n_nodes - 1, n_states, n_states))\n",
    "\n",
    "    tmp = np.zeros((n_states, 1))\n",
    "    for k in range(n_states):\n",
    "        tmp[k] = np.log(pi[k]) + np.log(B[k, observed[0]])\n",
    "\n",
    "    f0 = tmp\n",
    "\n",
    "    for i in range(1, n_nodes):\n",
    "        tmp = np.zeros((n_states, n_states))\n",
    "\n",
    "        for j in range(n_states):  # over z1\n",
    "            for k in range(n_states):  # over z2\n",
    "                tmp[j, k] = np.log(A[j, k]) + np.log(B[k, observed[i]])\n",
    "\n",
    "        f[i - 1] = tmp\n",
    "\n",
    "    return f0, f\n",
    "\n",
    "\n",
    "def Viterbi_log(f0, f):\n",
    "    \"\"\"\n",
    "    Performs the forward pass of the max plus algorithm (known as Viterbi algorithm for Hidden-Markov models).\n",
    "    Input: \n",
    "        - f0: the factor corresponding to the initial factor to first latent variable message\n",
    "        - f: an array containig the all the other factors (n_states - 1)\n",
    "    Output:\n",
    "        - pmax: the array containing the messages of the forward pass\n",
    "        - phi: the array storing the most probable preceding state stored during the forward pass\n",
    "    \"\"\"\n",
    "    n_nodes = f.shape[0] + 1\n",
    "    n_states = f.shape[1]\n",
    "\n",
    "    pmax = np.zeros((n_nodes, n_states))  # Need one for every node\n",
    "    phi = np.zeros(\n",
    "        (n_nodes - 1, n_states)\n",
    "    )  # Need one for every node other than the first one (no need to reconstruct it)\n",
    "\n",
    "    pmax[0] = f0.flatten()\n",
    "\n",
    "    for i in range(1, n_nodes):\n",
    "        tmp = ((f[i - 1]).T + pmax[i - 1]).T\n",
    "\n",
    "        pmax[i] = np.max(tmp, axis=0)  # by column\n",
    "\n",
    "        phi[i - 1] = np.argmax(\n",
    "            tmp, axis=0\n",
    "        )  # i-1 cause this contains the reconstruction about the (i-1)th element\n",
    "\n",
    "    return pmax, phi\n",
    "\n",
    "\n",
    "def reconstruct(pmax, phi):\n",
    "    \"\"\"\n",
    "    Given the output of a max-plus forward pass it returns the most probable hidden states.\n",
    "    Input:\n",
    "        - pmax: the array containing the messages of the forward pass\n",
    "        - phi: the array storing the most probable preceding state stored during the forward pass\n",
    "    Output:\n",
    "        - An array of int that coincides with the most probable latent states\n",
    "    \"\"\"\n",
    "    reconstruction = np.empty(len(phi) + 1)\n",
    "\n",
    "    curr = np.argmax(pmax[-1])\n",
    "    reconstruction[-1] = curr\n",
    "\n",
    "    for i in range(len(phi) - 1, -1, -1):\n",
    "        curr = int(phi[i, curr])\n",
    "        reconstruction[i] = curr\n",
    "\n",
    "    return reconstruction\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 189,
   "metadata": {},
   "outputs": [
    {
     "name": "stderr",
     "output_type": "stream",
     "text": [
      "/var/folders/tv/ysw0jsvs2t331mtk7hdh35kc0000gn/T/ipykernel_2450/845287397.py:19: RuntimeWarning: divide by zero encountered in log\n",
      "  tmp[k] = np.log(pi[k]) + np.log(B[k, observed[0]])\n",
      "/var/folders/tv/ysw0jsvs2t331mtk7hdh35kc0000gn/T/ipykernel_2450/845287397.py:28: RuntimeWarning: divide by zero encountered in log\n",
      "  tmp[j, k] = np.log(A[j, k]) + np.log(B[k, observed[i]])\n"
     ]
    }
   ],
   "source": [
    "f0, f = compute_f_log(A=p.normalized_matrix, B=emission, observed=observed_)\n",
    "pmax, phi = Viterbi_log(f0, f)\n",
    "reconstruction = reconstruct(pmax, phi)\n",
    "reconstruction = reconstruction.astype(int)\n",
    "viterbi_reconstruction = convert_numbers_to_letters(reconstruction)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 193,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "hello banana xilophone key queue zebra cock pussy tits dandy fart though jolly world mum today i was going through the park and noticed that some people where looking at me in a weird way and thought that i was being silly\n",
      "hello pivind qulowhave mes there bepri pond whemy tate wives wint though folly corke bur towis s wis goung thyough the wind ind fofured thit more wexcke chere loomang it be an i cound wis ind thanghe thit s wis peang jully\n"
     ]
    }
   ],
   "source": [
    "print(hidden_sequence)\n",
    "print(viterbi_reconstruction)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 194,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "0.5138121546961326"
      ]
     },
     "execution_count": 194,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "np.mean(np.array(list(hidden_sequence.replace(\" \", \"\"))) == np.array(list(viterbi_reconstruction.replace(\" \", \"\"))))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 195,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "True sequence:\n",
      " hello banana xilophone key queue zebra cock pussy tits dandy fart though jolly world mum today i was going through the park and noticed that some people where looking at me in a weird way and thought that i was being silly\n",
      "Reconstruction using Viterbi:\n",
      " hello pivind qulowhave mes there bepri pond whemy tate wives wint though folly corke bur towis s wis goung thyough the wind ind fofured thit more wexcke chere loomang it be an i cound wis ind thanghe thit s wis peang jully\n"
     ]
    }
   ],
   "source": [
    "print(\"True sequence:\\n\", hidden_sequence)\n",
    "print(\"Reconstruction using Viterbi:\\n\", viterbi_reconstruction)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 204,
   "metadata": {},
   "outputs": [],
   "source": [
    "preprocess = TextPreProcessor()\n",
    "def prepare_subtexts(path_to_file, lengths):\n",
    "    \"\"\"\n",
    "    This function returns the subtext to use to assess accuracy in decryption\n",
    "\n",
    "    Input:\n",
    "        - path_to_file (str) giving the path to the text file\n",
    "        - lengths (list of int) giving the text lengths to consider\n",
    "    \"\"\"\n",
    "\n",
    "    with open(path_to_file, \"r\") as input_file:\n",
    "        full_text = input_file.read()\n",
    "\n",
    "    full_text = preprocess.lower(full_text)\n",
    "    unknown_chars = preprocess.unknown_chars(full_text)\n",
    "    full_text = preprocess.remove_unknown_chars(full_text, unknown_chars=unknown_chars)\n",
    "    full_text = preprocess.remove_additional_spaces(full_text)\n",
    "\n",
    "    subtexts = [\n",
    "        \" \".join(full_text.split()[: lengths[i]]) for i in range(len(lengths))\n",
    "    ]  # Contains the ones for the varying lengths\n",
    "\n",
    "    return subtexts\n",
    "\n",
    "# Use it on the war message text\n",
    "lengths = [100]\n",
    "subtext = prepare_subtexts(\"texts/eisenhower_speech.txt\", lengths)[0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 209,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "twntqw nz lwjewhf w3hn9w k qkf25f0 lkj xkdw emaj xnhf5fy nf emw unkje nz 6hkf4w c8 ehnn9j nz emw kqqaw2 wo9w2aeanfkh8 6nhuw em5j qkfd5fy aj 9khe n6 emw 4nf4whewd bf5ewd fkeanfj tqkf znh emw qacwhke5nf n6 w3hntw xk2w af unfsbfueanf l5em n3h yhwke hbjj5kf kqqawj 5 mkrw emaj xwjjkyw znh kqq nz inb kqemnbym emw 5faeakq kjjk3qe xki fne mkrw cwwf xkdw 5f 8nbh nlf unbfeh8 emw mnbh n6 in3h qacwhkeanf aj k99hnk4m5fy kqq tkehanej xwf kfd lnxwf 8nbf0 kf2 nq2 mkrw k tkhe en tqk8 5f emw kumawrwxwfe n6 6afkq ra4enh8 en xwxcwhj nz hwj5jekf4w xnrwxwfej a jk8 6nqqnl\n"
     ]
    }
   ],
   "source": [
    "cipher = Homophonic_Cipher_Generator()\n",
    "encoded_text = Encode_using_homophonic(subtext, cipher)\n",
    "print(encoded_text)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 210,
   "metadata": {},
   "outputs": [
    {
     "name": "stderr",
     "output_type": "stream",
     "text": [
      "/var/folders/tv/ysw0jsvs2t331mtk7hdh35kc0000gn/T/ipykernel_2450/845287397.py:19: RuntimeWarning: divide by zero encountered in log\n",
      "  tmp[k] = np.log(pi[k]) + np.log(B[k, observed[0]])\n",
      "/var/folders/tv/ysw0jsvs2t331mtk7hdh35kc0000gn/T/ipykernel_2450/845287397.py:28: RuntimeWarning: divide by zero encountered in log\n",
      "  tmp[j, k] = np.log(A[j, k]) + np.log(B[k, observed[i]])\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "'pexple of western qurope a landing was mave this morning on the coust of france by troous of the allied expedithonary force this landing is part of the concerted united mathons plan for the liverathon of qurope mave in conqunckion with our great busshan allies i have this message for all of you although the inithal assauld may not have been mave in your own country the hour of your liverathon is approuching all pathiots men and women young and old have a part to play in the achievement of final wictory to members of resistance movements i say follow'"
      ]
     },
     "execution_count": 210,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "mapping = {'a': 0, 'b': 1, 'c': 2, 'd': 3, 'e': 4, 'f': 5, 'g': 6, 'h': 7, 'i': 8, 'j': 9,\n",
    "    'k': 10, 'l': 11, 'm': 12, 'n': 13, 'o': 14, 'p': 15, 'q': 16, 'r': 17, 's': 18,\n",
    "    't': 19, 'u': 20, 'v': 21, 'w': 22, 'x': 23, 'y': 24, 'z': 25,\n",
    "    '0': 26, '1': 27, '2': 28, '3': 29, '4': 30, '5': 31, '6': 32, '7': 33, '8': 34,\n",
    "    '9': 35, ' ': 36}\n",
    "    \n",
    "hidden_ = string_to_numbers_updated(encoded_text, mapping = mapping)\n",
    "#print(hidden_)\n",
    "\n",
    "observed_ = string_to_numbers_updated(subtext, mapping)\n",
    "#print(observed_)\n",
    "\n",
    "\n",
    "    ######################################################### HMM #########################################################\n",
    "B_start = np.zeros((27, 37)) + 1 / 36\n",
    "B_start[:, -1] = np.zeros(27) # last column\n",
    "B_start[-1, :] = np.zeros(37) # last row\n",
    "B_start[-1, -1] = 1           # last entr\n",
    "emission = Baum_Welch(\n",
    "        A=p.normalized_matrix,\n",
    "        B_start=B_start,\n",
    "        pi=p.normalized_matrix[-1, :],\n",
    "        observed=observed_)\n",
    "\n",
    "        # Now we use Viterbi to obtain the most likely one\n",
    "f0, f = compute_f_log(\n",
    "    A=p.normalized_matrix, B=emission, observed=observed_\n",
    ")\n",
    "pmax, phi = Viterbi_log(f0, f)\n",
    "reconstruction = reconstruct(pmax, phi)\n",
    "reconstruction = reconstruction.astype(int)\n",
    "viterbi_reconstruction = convert_numbers_to_letters(reconstruction)\n",
    "viterbi_reconstruction"
   ]
  }
 ],
 "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.10.8"
  },
  "orig_nbformat": 4
 },
 "nbformat": 4,
 "nbformat_minor": 2
}