Biblecode-complete.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "id": "8538e0ae",
   "metadata": {},
   "source": [
    "# Der Bibelcode"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "46f1bc0b",
   "metadata": {},
   "source": [
    "### Einführung\n",
    "\n",
    "\n",
    "1997 hat ein Buch des Journalisten Michael Drosnin grosse Aufmerksamkeit erregt. Das Buch mit dem Namen *Bible code* postuliert, dass in der Bibel (genauer gesagt in der Tora) versteckte Botschaften codiert sind. Diese Botschaften sind durch equidistante Folgen von Zeichen codiert, wie im folgenden Bild gezeigt ist (Quelle: Wikipedia)\n",
    "<figure style=\"align:center\">\n",
    "    <img src=\"images/bible-code.png\" width=200px/>\n",
    "</figure>\n",
    "\n",
    "In dieser Fallstudie werden wir überprüfen, ob wir auch in anderen Werken solche Botschaften finden. Wir nutzen dazu das Buch Krieg und Frieden von Leo Tolstoy, welches frei auf [Projekt Gutenberg](https://www.gutenberg.org) verfügbar ist. "
   ]
  },
  {
   "cell_type": "markdown",
   "id": "8e78ea27",
   "metadata": {},
   "source": [
    "### Aufgabe\n",
    "\n",
    "Unser Ziel ist es in einem Text alle als *Bible code* versteckten Wörter zu finden welche in einem Wörterbuch vorkommen. Dabei ist der Text in einer einfachen `.txt`-Datei gegeben und das Wörterbuch als eine `.json`-Datei."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "13f7e56e",
   "metadata": {},
   "source": [
    "### Problem Analyse und Zerlegung\n",
    "\n",
    "Wir wollen als erstes das ganze Problem in Teilprobleme zerlegen. Dabei sollen die Teilprobleme einfach zu implementieren sein und sich auch gut zur gesamten Lösung zusammensetzten lassen.\n",
    "\n",
    "Überlegen Sie sich Teilprobleme und ergänzen Sie die Liste damit. Überlegen Sie sich auch, welche Teilprobleme Sie einfach als Funktion implementieren können:\n",
    "\n",
    "- Einlesen des Textes aus einer .txt-Datei.\n",
    "- Einlesen eines Wörterbuches aus einer .json-Datei.\n",
    "- ...\n",
    "- *Entfernen von Sondernzeichen aus einem Text (und umwandeln in Kleinbuchstaben).*\n",
    "- *Extrahieren eines Wortes aus einem Text an einer Stelle mit gegebener Distanz zwischen den Buchstaben.*\n",
    "- *Stellen finden wo der Anfangsbuchstabe des Wortes vorkommt.*\n",
    "- *Testen von allen Worten im Dictionary.*\n",
    "- *Speichern einer Stelle wo ein Wort gefunden wurde.*\n",
    "- *Ausgabe aller Stellen wo ein Wort gefunden wurde.*\n",
    "- *Ausgabe wie oft ein Wort gefunden wurde.*"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "1162f942",
   "metadata": {},
   "source": [
    "### Vorbereiten der Daten\n",
    "\n",
    "Als Erstes wollen wir die Vorverarbeitung der Daten erstellen. Wir wollen unsere Chancen auf einen Treffer erhöhen indem wir von einem Text möglichst nur die Buchstaben behalten. Dazu schreiben wir uns eine erste Hilfsfunktion. Diese soll: \n",
    "- auf Basis eines übergebenen Textes einen neuen Text erstellen.\n",
    "- möglichst nur Buchstaben behalten.\n",
    "- die Buchstaben in Kleinbuchstaben umwandeln."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "id": "867a37c3",
   "metadata": {},
   "outputs": [],
   "source": [
    "def clean_text(text):\n",
    "    s = \"\" \n",
    "    for c in text:\n",
    "        if not c in ['.', ',', '?', '!', ' ']:\n",
    "            s += c.lower()\n",
    "    return s"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "4e90c403",
   "metadata": {},
   "source": [
    "Da wir all unseren Code den wir schreiben immer auch testen sollen, rufen wir die Funktion mit einem einfachen Text auf. Wir schauen dann ob die Funktion das tut was wir erwarten."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "id": "54ba7749",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "'einefrageeinausrufezeichenundeinpunkt'"
      ]
     },
     "execution_count": 2,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "clean_text(\"Eine Frage? ein Ausrufezeichen! und ein Punkt.\")"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "100aa6a2",
   "metadata": {},
   "source": [
    "### Text laden\n",
    "Als nächstes wollen wir das laden des Textes aus einem File implementieren. Auch dazu schreiben wir uns eine Funktion welche den Inhalt des Files `war-and-peace.txt` laden soll. Der Text soll dann gleich noch von Sonderzeichen befreit werden."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "id": "994a06d2",
   "metadata": {},
   "outputs": [],
   "source": [
    "def load_preprocessed_text():\n",
    "    f = open(\"war-and-peace.txt\", 'r')\n",
    "    text = f.read()\n",
    "    f.close()\n",
    "    return clean_text(text)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "787fbafa",
   "metadata": {},
   "source": [
    "Test wir doch auch diese Funktion gleich indem wir die ersten 100 Zeichen ausgeben."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "id": "7a037451",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "'ï»¿theprojectgutenbergebookofwarandpeacebyleotolstoy\\n\\nthisebookisfortheuseofanyoneanywhereatnocostan'"
      ]
     },
     "execution_count": 4,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "load_preprocessed_text()[0:100]"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "541d2d9f",
   "metadata": {},
   "source": [
    "### Äquidistante Buchstaben\n",
    "Ein weiteres Teilproblem ist, dass wir an einer Stelle eines Textes ein Wort extrahieren können mit einer gegebener Distanz der Buchstaben. Dafür schreiben wir uns eine Funktion, welche:\n",
    "- ab einer gegebenen Position `start_position` Buchstaben aus dem Text `text` extrahiert.\n",
    "- wenn möglich `number_of_letters` Buchstaben mit Distanz `distance` extrahiert.\n",
    "- die extrahierten Buchstaben als neues Wort zurückgibt."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "id": "fb1703a2",
   "metadata": {},
   "outputs": [],
   "source": [
    "def equidistant_letter_seq(text, start_position, number_of_letters, distance):\n",
    "    s = \"\" \n",
    "    end_position = start_position + number_of_letters * distance\n",
    "    end_position = min(end_position, len(text))\n",
    "    \n",
    "    # Der dritte Parameter in range-Aufruf ist, um wieviel erhöht wird\n",
    "    # für das nächste Element. Ohne diesen würde jeweils um 1 erhöht.\n",
    "    character_positions = range(start_position, end_position, distance)\n",
    "    \n",
    "    for i in character_positions:\n",
    "        s += text[i]\n",
    "    return s"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "a260eaae",
   "metadata": {},
   "source": [
    "Testen! Ja, auch diese Funktion testen wir."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "id": "1f18aafe",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "'ro tu'"
      ]
     },
     "execution_count": 6,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "equidistant_letter_seq(\"Der Mond ist aufgegangen\", 2, 5, 3)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "4f13f883",
   "metadata": {},
   "source": [
    "### Mögliche Startpositionen\n",
    "\n",
    "Nun können wir durch einen Text gehen, und schauen wo der Anfangsbuchstaben eines zu suchenden Wortes vorkommt. So wissen wir wo im Text wir überhaupt suchen müssen."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "id": "9619d677",
   "metadata": {},
   "outputs": [],
   "source": [
    "def locate_char_in_text(text, character):\n",
    "    possible_start_locations = []\n",
    "    for i in range(0, len(text)):\n",
    "        if text[i] == character:\n",
    "            possible_start_locations.append(i)\n",
    "    return possible_start_locations"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "e0ec1d73",
   "metadata": {},
   "source": [
    "Auch diese Funktion können wir ganz einfach kurz testen."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "id": "2a3e0e9b",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[1, 2, 5, 12, 25]"
      ]
     },
     "execution_count": 8,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "locate_char_in_text(\"Abba bringt brandneue Tonbändchen auf den Markt.\", 'b')"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "edf07ad1",
   "metadata": {},
   "source": [
    "### Ist das Wort gefunden?\n",
    "\n",
    "Als nächstes wollen wir in einem Text nachschauen ob an einer bestimmten Position mit einer bestimmten Distanz zwischen den Buchstaben ein Wort vorkommt. Die Funktion soll also nur die Wahrheitswerte `True` oder `False` zurück geben."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "id": "ccf8e5a0",
   "metadata": {},
   "outputs": [],
   "source": [
    "def word_is_found(text, word_to_search, start_pos, distance):\n",
    "    word_length = len(word_to_search)\n",
    "    word_in_text = equidistant_letter_seq(text, start_pos, word_length, distance)\n",
    "    return word_in_text == word_to_search"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "d496a8bd",
   "metadata": {},
   "source": [
    "Genau - wir wollen die Funktion testen."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "id": "7487d8c3",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "True"
      ]
     },
     "execution_count": 10,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "word_is_found(\"foo p y t h o n bar\", \"python\", 4, 2)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "98c59b96",
   "metadata": {},
   "source": [
    "### Der Fundort\n",
    "Wenn wir ein Wort gefunden haben, dann wollen wir uns ein paar Dinge merken. Dafür verwenden wir eine ganz simple Klasse. Die Klasse soll das gefundene Wort, die Anfangsposition sowie die Distanz zwischen den Buchstaben speichern. Zudem soll die Klasse sich noch einfach über eine `print` Methode auf die Konsole ausgeben lassen."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "id": "8b8ff7b8",
   "metadata": {},
   "outputs": [],
   "source": [
    "class WordOccurrence:\n",
    "    def __init__(self, word, pos, distance):\n",
    "        self.word = word\n",
    "        self.pos = pos\n",
    "        self.distance = distance\n",
    "        \n",
    "    def print(self):\n",
    "        print(\"found word \\\"{}\\\" at position {} with distance {}\".format(self.word, self.pos, self.distance))"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "82d13160",
   "metadata": {},
   "source": [
    "Testen? - Na gut ...."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "id": "0bbfde89",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "found word \"love\" at position 7 with distance 42\n"
     ]
    }
   ],
   "source": [
    "match = WordOccurrence(\"love\", 7, 42)\n",
    "match.print()"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "fc3f69b1",
   "metadata": {},
   "source": [
    "### Suchen\n",
    "Jetzt können wir viele unserer Teile zusammenfügen und in einem Text alle vorkommen eines Wortes mit einer bestimmten Distanz zwischen den Buchstaben suchen."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "id": "ef92d105",
   "metadata": {},
   "outputs": [],
   "source": [
    "def find_word_with_distance(text, word_to_search, distance):\n",
    "    occurences = []\n",
    "    possible_starting_locations = locate_char_in_text(text, word_to_search[0])\n",
    "    for start_position in possible_starting_locations:\n",
    "        if word_is_found(text, word_to_search, start_position, distance):\n",
    "            occurences.append(WordOccurrence(word_to_search, start_position, distance))\n",
    "    return occurences"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "9cfdbeb4",
   "metadata": {},
   "source": [
    "Ok - sag nichts! Ich teste ja schon..."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "id": "90a620cd",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "found word \"emknG\" at position 5 with distance 4\n"
     ]
    }
   ],
   "source": [
    "matches = find_word_with_distance(\"ein Text mit kleinen Geheimnissen\", \"emknG\", 4)\n",
    "matches[0].print()"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "0b20a9a9",
   "metadata": {},
   "source": [
    "### Ausgabe"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "f12e2942",
   "metadata": {},
   "source": [
    "Wir wollen noch die Ausgabe von einer Liste von gefundenen Wörtern vereinfachen. Dazu schreiben wir - genau - auch wider eine Funktion."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "id": "07d8c883",
   "metadata": {},
   "outputs": [],
   "source": [
    "def print_occurences(found_occurences):\n",
    "    print(\"{} occurences found\".format(len(found_occurences)))\n",
    "    for word_info in found_occurences:\n",
    "        word_info.print()\n"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "49299e7c",
   "metadata": {},
   "source": [
    "Testen obligatorisch!"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "id": "00339cea",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "1 occurences found\n",
      "found word \"emknG\" at position 5 with distance 4\n"
     ]
    }
   ],
   "source": [
    "print_occurences(matches)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "a891c43d",
   "metadata": {},
   "source": [
    "### Die erste Anwendung\n",
    "Endlich können wir nun auch eine Anwendung schreiben und nachschauen ob `corona` im Text vorkommt."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 17,
   "id": "5df43f95",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "0 occurences found\n"
     ]
    }
   ],
   "source": [
    "text = load_preprocessed_text()\n",
    "word_to_find = \"corona\"\n",
    "distance = 2\n",
    "found_words = find_word_with_distance(text, word_to_find, distance)\n",
    "print_occurences(found_words)\n"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "a1d1b98c",
   "metadata": {},
   "source": [
    "Wir können natürlich nicht nur nach Distanz 2, sondern z.B. nach allen Distanzen von 15 bis 25 suchen. Oder wir können nach anderen Wörtern suchen."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 18,
   "id": "4e721891",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "0 occurences found\n",
      "0 occurences found\n",
      "0 occurences found\n",
      "0 occurences found\n",
      "1 occurences found\n",
      "found word \"corona\" at position 2493083 with distance 19\n",
      "0 occurences found\n",
      "0 occurences found\n",
      "1 occurences found\n",
      "found word \"corona\" at position 1207766 with distance 22\n",
      "0 occurences found\n",
      "0 occurences found\n"
     ]
    }
   ],
   "source": [
    "text = load_preprocessed_text()\n",
    "word_to_find = \"corona\"\n",
    "#word_to_find = \"soccer\"\n",
    "#word_to_find = \"dinner\"\n",
    "for dist in range(15,25):\n",
    "    found_words = find_word_with_distance(text, word_to_find, dist)\n",
    "    print_occurences(found_words)\n"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "2953dd8e",
   "metadata": {},
   "source": [
    "## Die letzten Schritte zum Ziel\n",
    "\n",
    "Zuletzt wollen wir noch unsere Aufgabe vom Anfang angehen. Wir wollen herausfinden welche Wörter aus einem Dictionary es gibt, die als solche Equidistant Letter Sequences vorkommen. Dazu müssen wir zuerst noch ein Dictionary laden können. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 19,
   "id": "a43a3f88",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "102217 words loaded into the dictionary\n"
     ]
    }
   ],
   "source": [
    "def load_dictionary():\n",
    "    import json\n",
    "    f = open(\"dictionary.json\", \"r\")\n",
    "    dictionary = json.load(f)\n",
    "    f.close()\n",
    "    return dictionary\n",
    "\n",
    "# Testen inklusive\n",
    "dictionary = load_dictionary()\n",
    "print(\"{} words loaded into the dictionary\".format(len(dictionary)))"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "5e3258d3",
   "metadata": {},
   "source": [
    "Wir schreiben uns nun noch eine etwas andere Suchfunktion um diese Aufgabe effizienter zu lösen."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 20,
   "id": "b1158768",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "1 occurences found\n",
      "found word \"python\" at position 4 with distance 2\n"
     ]
    }
   ],
   "source": [
    "def find_all_words(text, dictionary, word_length, distance):\n",
    "    occurrences = []\n",
    "    for start_position in range(0,len(text)):\n",
    "        word = equidistant_letter_seq(text, start_position, word_length, distance)\n",
    "        if len(word) == word_length and word in dictionary:\n",
    "            occurrences.append(WordOccurrence(word, start_position, distance))\n",
    "    return occurrences\n",
    "\n",
    "# Wir wissen was raus kommen sollte...\n",
    "dictionary = load_dictionary()\n",
    "print_occurences(find_all_words(\"foo p y t h o n bar\", dictionary, 6, 2))"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "256f74ed",
   "metadata": {},
   "source": [
    "Und nun die Anwendung die uns alle gefundenen Wörter mit bestimmten Längen und Distanzen rausschreibt, welche auch in einem Dictionary stehen."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 21,
   "id": "7aedaf5b",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "checking words of length 8 with distance 3 ...\n",
      "3 occurences found\n",
      "found word \"hematoma\" at position 224367 with distance 3\n",
      "found word \"tethydan\" at position 824229 with distance 3\n",
      "found word \"oscinine\" at position 920755 with distance 3\n",
      "checking words of length 8 with distance 4 ...\n",
      "4 occurences found\n",
      "found word \"oratorio\" at position 423407 with distance 4\n",
      "found word \"aerolite\" at position 866327 with distance 4\n",
      "found word \"crannied\" at position 1737674 with distance 4\n",
      "found word \"hesitate\" at position 2061381 with distance 4\n",
      "checking words of length 8 with distance 5 ...\n",
      "5 occurences found\n",
      "found word \"entender\" at position 174061 with distance 5\n",
      "found word \"biometry\" at position 181727 with distance 5\n",
      "found word \"direness\" at position 1204932 with distance 5\n",
      "found word \"sepiment\" at position 1219818 with distance 5\n",
      "found word \"intonate\" at position 1271553 with distance 5\n",
      "checking words of length 9 with distance 3 ...\n",
      "0 occurences found\n",
      "checking words of length 9 with distance 4 ...\n",
      "1 occurences found\n",
      "found word \"editorial\" at position 2102863 with distance 4\n",
      "checking words of length 9 with distance 5 ...\n",
      "0 occurences found\n",
      "checking words of length 10 with distance 3 ...\n",
      "0 occurences found\n",
      "checking words of length 10 with distance 4 ...\n",
      "0 occurences found\n",
      "checking words of length 10 with distance 5 ...\n",
      "0 occurences found\n"
     ]
    }
   ],
   "source": [
    "text = load_preprocessed_text()\n",
    "dictionary = load_dictionary()\n",
    "for word_length in range(8, 11):\n",
    "    for distance in range(3, 6):\n",
    "        print(\"checking words of length {} with distance {} ...\".format(word_length, distance))\n",
    "        found_words = find_all_words(text, dictionary, word_length, distance)\n",
    "        print_occurences(found_words)\n"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "1c44a7e5",
   "metadata": {},
   "source": [
    "Die Fallstudie ist nun zu Ende. Wenn Sie Spass daran haben, dann können Sie die Fallstudie gerne noch erweitern. Einige Idee sind:\n",
    "- Sammeln Sie alle Wörter um Doppelte auszusortieren und eine \"saubere\" Liste auszugeben.\n",
    "- Geben Sie die Liste alphabetisch sortiert aus.\n",
    "- Verbessern Sie die Aufbereitung des Textes und eliminieren Sie alle Zeichen ausser Buchstaben.\n",
    "- Was kommt Ihnen noch für eine Erweiterung in den Sinn?\n",
    "\n",
    "Viel Erfolg!"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "bdf358bf",
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "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.7.3"
  },
  "toc": {
   "base_numbering": 1,
   "nav_menu": {},
   "number_sections": false,
   "sideBar": false,
   "skip_h1_title": false,
   "title_cell": "Table of Contents",
   "title_sidebar": "Contents",
   "toc_cell": false,
   "toc_position": {},
   "toc_section_display": false,
   "toc_window_display": false
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}