L5Z1.ipynb

{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "import numpy as np\n",
    "from collections import defaultdict as dd\n",
    "from typing import List, Dict, Set\n",
    "import nltk\n",
    "from math import log, ceil\n",
    "import time\n",
    "import sys\n",
    "import itertools\n",
    "from numba import jit, njit, jitclass"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [],
   "source": [
    "import pickle\n",
    "with open(\"Dane/wiki_list\", \"rb\") as ifile:\n",
    "    wiki_list = pickle.load(ifile)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "('Calvados (napój alkoholowy)',\n",
       " [['Calvados', '(', 'napój', 'alkoholowy', ')'],\n",
       "  ['Calvados',\n",
       "   '–',\n",
       "   'wytrawny',\n",
       "   'winiak',\n",
       "   'francuski',\n",
       "   ',',\n",
       "   'charakteryzujący',\n",
       "   'się',\n",
       "   'wytrawnym',\n",
       "   'smakiem',\n",
       "   'owocowym',\n",
       "   '(',\n",
       "   'jabłkowym',\n",
       "   ')',\n",
       "   'i',\n",
       "   'charakterystycznym',\n",
       "   'jabłkowym',\n",
       "   'bukietem',\n",
       "   '.',\n",
       "   'Wyrabiany',\n",
       "   'jest',\n",
       "   'głównie',\n",
       "   'w',\n",
       "   'departamencie',\n",
       "   'Calvados',\n",
       "   'w',\n",
       "   'Normandii',\n",
       "   'poprzez',\n",
       "   'destylację',\n",
       "   'cydru',\n",
       "   '.'],\n",
       "  ['Nazwa',\n",
       "   '``',\n",
       "   'calvados',\n",
       "   '``',\n",
       "   '(',\n",
       "   'będąca',\n",
       "   'pochodną',\n",
       "   'nazwy',\n",
       "   'departamentu',\n",
       "   ')',\n",
       "   ',',\n",
       "   'podobnie',\n",
       "   'jak',\n",
       "   'nazwy',\n",
       "   'koniak',\n",
       "   'i',\n",
       "   'armagnac',\n",
       "   ',',\n",
       "   'jest',\n",
       "   'prawnie',\n",
       "   'zastrzeżona',\n",
       "   ',',\n",
       "   'dostępna',\n",
       "   'tylko',\n",
       "   'dla',\n",
       "   'produktów',\n",
       "   'z',\n",
       "   'Normandii',\n",
       "   ',',\n",
       "   'dlatego',\n",
       "   'też',\n",
       "   'produkowane',\n",
       "   'np',\n",
       "   '.',\n",
       "   'w',\n",
       "   'Polsce',\n",
       "   'wypalanki',\n",
       "   'jabłkowe',\n",
       "   'noszą',\n",
       "   'nazwy',\n",
       "   'wódek',\n",
       "   'w',\n",
       "   'typie',\n",
       "   'calvadosu',\n",
       "   '.',\n",
       "   'Do',\n",
       "   'najbardziej',\n",
       "   'popularnych',\n",
       "   'należą',\n",
       "   'wódki',\n",
       "   '„',\n",
       "   'Złota',\n",
       "   'jesień',\n",
       "   '”',\n",
       "   'i',\n",
       "   '„',\n",
       "   'Złota',\n",
       "   'reneta',\n",
       "   '”',\n",
       "   ',',\n",
       "   'będące',\n",
       "   'mieszankami',\n",
       "   'destylatu',\n",
       "   'jabłecznego',\n",
       "   'ze',\n",
       "   'spirytusem',\n",
       "   'zbożowym',\n",
       "   'lub',\n",
       "   'ziemniaczanym',\n",
       "   '.'],\n",
       "  []])"
      ]
     },
     "execution_count": 3,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "wiki_list[549]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {
    "jupyter": {
     "source_hidden": true
    }
   },
   "outputs": [],
   "source": [
    "class TrieNode:\n",
    "    def __init__(self):\n",
    "        self.word = None\n",
    "        self.index = None\n",
    "        self.children = {}\n",
    "\n",
    "    def insert( self, word, index = None):\n",
    "        word = word.lower()\n",
    "        node = self\n",
    "        for letter in word:\n",
    "            if letter not in node.children: \n",
    "                node.children[letter] = TrieNode()\n",
    "\n",
    "            node = node.children[letter]\n",
    "\n",
    "        node.word = word\n",
    "        node.index = index"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [
    {
     "ename": "NameError",
     "evalue": "name 'trie' is not defined",
     "output_type": "error",
     "traceback": [
      "\u001b[0;31m---------------------------------------------------------------------------\u001b[0m",
      "\u001b[0;31mNameError\u001b[0m                                 Traceback (most recent call last)",
      "\u001b[0;32m<ipython-input-5-ebf2c419fd06>\u001b[0m in \u001b[0;36m<module>\u001b[0;34m\u001b[0m\n\u001b[0;32m----> 1\u001b[0;31m \u001b[0mprint\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mtrie\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0mchildren\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0m",
      "\u001b[0;31mNameError\u001b[0m: name 'trie' is not defined"
     ]
    }
   ],
   "source": [
    "print(trie.children)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# read dictionary file into a trie\n",
    "trie = TrieNode()\n",
    "word_set = set()\n",
    "title_mapping = dd(lambda:-1)\n",
    "for i, el in enumerate(wiki_list):\n",
    "    title_mapping[\" \".join(el[1][0])] = i\n",
    "#     for w in el[1][0]:\n",
    "#         if not w.isalpha():\n",
    "#             continue\n",
    "#         w = w.lower()\n",
    "#         word_set.add(w)\n",
    "#         trie.insert(w, i)\n",
    "    trie.insert(el[0], i)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# The search function returns a list of all words that are less than the given\n",
    "# maximum distance from the target word\n",
    "# @jit\n",
    "def search( word, maxCost ):\n",
    "\n",
    "    # build first row\n",
    "    currentRow = range( len(word) + 1 )\n",
    "\n",
    "    results = []\n",
    "\n",
    "    # recursively search each branch of the trie\n",
    "    for letter in trie.children:\n",
    "        searchRecursive( trie.children[letter], letter, word, currentRow, \n",
    "            results, maxCost )\n",
    "\n",
    "    return results"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from multiprocessing import Pool"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "_word = \"\"\n",
    "_maxCost = 2\n",
    "def _search(letter):\n",
    "    global _word\n",
    "    global _maxCost\n",
    "    currentRow = range( len(_word) + 1 )\n",
    "    results = []\n",
    "    searchRecursive(trie.children[letter], letter, _word, currentRow, \n",
    "            results, _maxCost )\n",
    "    return results\n",
    "def search_parallel(word, maxCost):\n",
    "    global _word\n",
    "    global _maxCost\n",
    "    _word = word\n",
    "    _maxCost = maxCost\n",
    "    p = Pool(100)\n",
    "    res = p.map(_search, trie.children.keys())\n",
    "    of_the_jedi = []\n",
    "    for el in res:\n",
    "        of_the_jedi += el\n",
    "    return of_the_jedi"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# This recursive helper is used by the search function above. It assumes that\n",
    "# the previousRow has been filled in already.\n",
    "# @jit\n",
    "def searchRecursive( node, letter, word, previousRow, results, maxCost ):\n",
    "\n",
    "    columns = len( word ) + 1\n",
    "    currentRow = [ previousRow[0] + 1 ]\n",
    "\n",
    "    # Build one row for the letter, with a column for each letter in the target\n",
    "    # word, plus one for the empty string at column 0\n",
    "    for column in range( 1, columns ):\n",
    "\n",
    "        insertCost = currentRow[column - 1] + 1\n",
    "        deleteCost = previousRow[column] + 1\n",
    "\n",
    "        if word[column - 1] != letter:\n",
    "            replaceCost = previousRow[ column - 1 ] + 1\n",
    "        else:                \n",
    "            replaceCost = previousRow[ column - 1 ]\n",
    "\n",
    "        currentRow.append( min( insertCost, deleteCost, replaceCost ) )\n",
    "\n",
    "    # if the last entry in the row indicates the optimal cost is less than the\n",
    "    # maximum cost, and there is a word in this trie node, then add it.\n",
    "    if currentRow[-1] <= maxCost and node.word != None:\n",
    "        results.append( (node.index, currentRow[-1] ) )\n",
    "#         results.append( (node.word) )\n",
    "\n",
    "\n",
    "    # if any entries in the row are less than the maximum cost, then \n",
    "    # recursively search each branch of the trie\n",
    "    if min( currentRow ) <= maxCost:\n",
    "        for letter in node.children:\n",
    "            searchRecursive( node.children[letter], letter, word, currentRow, \n",
    "                results, maxCost )"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# @jit\n",
    "def search_title(title):\n",
    "    limit = 2\n",
    "    title = title.lower()\n",
    "    while limit <= 512:\n",
    "        res = search(title, limit)\n",
    "        if len(res) > 0:\n",
    "            return [wiki_list[el[0]][0] for el in sorted(res, key = lambda el: el[1])]\n",
    "        limit *= 2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# @jit\n",
    "def search_title_parallel(title):\n",
    "    limit = 2\n",
    "    title = title.lower()\n",
    "    while limit <= 512:\n",
    "        res = search_parallel(title, limit)\n",
    "        if len(res) > 0:\n",
    "            return [wiki_list[el[0]][0] for el in sorted(res, key = lambda el: el[1])]\n",
    "        limit *= 2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "%%timeit\n",
    "print(search_title(\"uniwersytet wroclawaski\"))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "%%timeit\n",
    "print(search_title_parallel(\"uniwersytet wroclawaski\"))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def search_title1(title):\n",
    "    corrected = []\n",
    "    for w in nltk.word_tokenize(title):\n",
    "        w = w.lower()\n",
    "        if not w.isalpha() or w in corrected:\n",
    "            corrected.append([w])\n",
    "            continue\n",
    "        limit = 2\n",
    "        prop = []\n",
    "        while limit <= 8 and prop == []:\n",
    "            prop = search(title, limit)\n",
    "            limit *= 2\n",
    "        corrected.append(prop)\n",
    "    propositions = itertools.product(*corrected)\n",
    "    print(propositions)\n",
    "    of_the_jedi = [title_mapping[p] for p in propositions if title_mapping[p] >= 0]\n",
    "    return of_the_jedi"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "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.7"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}