simstring.ipynb

{
  "nbformat": 4,
  "nbformat_minor": 0,
  "metadata": {
    "kernelspec": {
      "display_name": "venv-simstring",
      "language": "python",
      "name": "venv-simstring"
    },
    "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.6"
    },
    "colab": {
      "name": "simstring.ipynb",
      "provenance": [],
      "include_colab_link": true
    }
  },
  "cells": [
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "view-in-github",
        "colab_type": "text"
      },
      "source": [
        "<a href=\"https://colab.research.google.com/github/TurkuNLP/Text_Mining_Course/blob/master/simstring.ipynb\" target=\"_parent\"><img src=\"https://colab.research.google.com/assets/colab-badge.svg\" alt=\"Open In Colab\"/></a>"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "Sx2texyrUNof"
      },
      "source": [
        "# Simstring\n",
        "\n",
        "* A very (very!) fast approximate string matching algorithm and its implementation [paper](https://www.researchgate.net/publication/221101753_Simple_and_Efficient_Algorithm_for_Approximate_Dictionary_Matching)  [code](https://github.com/chokkan/simstring)\n",
        "* Allows you to index a large number of strings (100+ million not a problem)\n",
        "* Can be queried for approximate hits of your query string\n",
        "\n",
        "## Installation\n",
        "\n",
        "* simstring needs a little effort to get running\n",
        "    * the necessary steps to follow are here: https://github.com/chokkan/simstring/issues/27\n",
        "    * that will give you a file called `simstring-1.1-cp37-cp37m-linux_x86_64.whl` (on current colab, differs by versions of things)\n",
        "    * You don't need to follow these steps, but if you want then it is possible on Colab but you will need to `! apt install automake swig` to make it work\n",
        "* I pre-compiled simstring for you, you can install it directly: http://dl.turkunlp.org/textual-data-analysis-course-data/simstring-1.1-cp37-cp37m-linux_x86_64.whl"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "dYjeMoxFYf7_",
        "outputId": "cee5e394-a915-4de4-fc26-3f5f7c422623"
      },
      "source": [
        "!pip install http://dl.turkunlp.org/textual-data-analysis-course-data/simstring-1.1-cp37-cp37m-linux_x86_64.whl"
      ],
      "execution_count": 1,
      "outputs": [
        {
          "output_type": "stream",
          "text": [
            "Collecting simstring==1.1\n",
            "\u001b[?25l  Downloading http://dl.turkunlp.org/textual-data-analysis-course-data/simstring-1.1-cp37-cp37m-linux_x86_64.whl (893kB)\n",
            "\u001b[K     |████████████████████████████████| 901kB 278kB/s \n",
            "\u001b[?25hInstalling collected packages: simstring\n",
            "Successfully installed simstring-1.1\n"
          ],
          "name": "stdout"
        }
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "7EvbApVvUNow",
        "outputId": "8016a06b-9880-4e89-9994-11563c1ee72d"
      },
      "source": [
        "import simstring\n",
        "help(simstring)"
      ],
      "execution_count": 2,
      "outputs": [
        {
          "output_type": "stream",
          "text": [
            "Help on module simstring:\n",
            "\n",
            "NAME\n",
            "    simstring\n",
            "\n",
            "DESCRIPTION\n",
            "    # This file was automatically generated by SWIG (http://www.swig.org).\n",
            "    # Version 3.0.12\n",
            "    #\n",
            "    # Do not make changes to this file unless you know what you are doing--modify\n",
            "    # the SWIG interface file instead.\n",
            "\n",
            "CLASSES\n",
            "    builtins.object\n",
            "        StringVector\n",
            "        SwigPyIterator\n",
            "        reader\n",
            "        writer\n",
            "    \n",
            "    class StringVector(builtins.object)\n",
            "     |  StringVector(*args)\n",
            "     |  \n",
            "     |  Methods defined here:\n",
            "     |  \n",
            "     |  __bool__(self)\n",
            "     |  \n",
            "     |  __del__ lambda self\n",
            "     |  \n",
            "     |  __delitem__(self, *args)\n",
            "     |  \n",
            "     |  __delslice__(self, i, j)\n",
            "     |  \n",
            "     |  __getattr__ lambda self, name\n",
            "     |  \n",
            "     |  __getitem__(self, *args)\n",
            "     |  \n",
            "     |  __getslice__(self, i, j)\n",
            "     |  \n",
            "     |  __init__(self, *args)\n",
            "     |      Initialize self.  See help(type(self)) for accurate signature.\n",
            "     |  \n",
            "     |  __iter__(self)\n",
            "     |  \n",
            "     |  __len__(self)\n",
            "     |  \n",
            "     |  __nonzero__(self)\n",
            "     |  \n",
            "     |  __repr__ = _swig_repr(self)\n",
            "     |  \n",
            "     |  __setattr__ lambda self, name, value\n",
            "     |  \n",
            "     |  __setitem__(self, *args)\n",
            "     |  \n",
            "     |  __setslice__(self, *args)\n",
            "     |  \n",
            "     |  append(self, x)\n",
            "     |  \n",
            "     |  assign(self, n, x)\n",
            "     |  \n",
            "     |  back(self)\n",
            "     |  \n",
            "     |  begin(self)\n",
            "     |  \n",
            "     |  capacity(self)\n",
            "     |  \n",
            "     |  clear(self)\n",
            "     |  \n",
            "     |  empty(self)\n",
            "     |  \n",
            "     |  end(self)\n",
            "     |  \n",
            "     |  erase(self, *args)\n",
            "     |  \n",
            "     |  front(self)\n",
            "     |  \n",
            "     |  get_allocator(self)\n",
            "     |  \n",
            "     |  insert(self, *args)\n",
            "     |  \n",
            "     |  iterator(self)\n",
            "     |  \n",
            "     |  pop(self)\n",
            "     |  \n",
            "     |  pop_back(self)\n",
            "     |  \n",
            "     |  push_back(self, x)\n",
            "     |  \n",
            "     |  rbegin(self)\n",
            "     |  \n",
            "     |  rend(self)\n",
            "     |  \n",
            "     |  reserve(self, n)\n",
            "     |  \n",
            "     |  resize(self, *args)\n",
            "     |  \n",
            "     |  size(self)\n",
            "     |  \n",
            "     |  swap(self, v)\n",
            "     |  \n",
            "     |  ----------------------------------------------------------------------\n",
            "     |  Static methods defined here:\n",
            "     |  \n",
            "     |  __swig_destroy__ = delete_StringVector(...)\n",
            "     |  \n",
            "     |  ----------------------------------------------------------------------\n",
            "     |  Data descriptors defined here:\n",
            "     |  \n",
            "     |  __dict__\n",
            "     |      dictionary for instance variables (if defined)\n",
            "     |  \n",
            "     |  __weakref__\n",
            "     |      list of weak references to the object (if defined)\n",
            "     |  \n",
            "     |  ----------------------------------------------------------------------\n",
            "     |  Data and other attributes defined here:\n",
            "     |  \n",
            "     |  __swig_getmethods__ = {}\n",
            "     |  \n",
            "     |  __swig_setmethods__ = {}\n",
            "    \n",
            "    class SwigPyIterator(builtins.object)\n",
            "     |  SwigPyIterator(*args, **kwargs)\n",
            "     |  \n",
            "     |  Methods defined here:\n",
            "     |  \n",
            "     |  __add__(self, n)\n",
            "     |  \n",
            "     |  __del__ lambda self\n",
            "     |  \n",
            "     |  __eq__(self, x)\n",
            "     |      Return self==value.\n",
            "     |  \n",
            "     |  __getattr__ lambda self, name\n",
            "     |  \n",
            "     |  __iadd__(self, n)\n",
            "     |  \n",
            "     |  __init__(self, *args, **kwargs)\n",
            "     |      Initialize self.  See help(type(self)) for accurate signature.\n",
            "     |  \n",
            "     |  __isub__(self, n)\n",
            "     |  \n",
            "     |  __iter__(self)\n",
            "     |  \n",
            "     |  __ne__(self, x)\n",
            "     |      Return self!=value.\n",
            "     |  \n",
            "     |  __next__(self)\n",
            "     |  \n",
            "     |  __repr__ = _swig_repr(self)\n",
            "     |  \n",
            "     |  __setattr__ lambda self, name, value\n",
            "     |  \n",
            "     |  __sub__(self, *args)\n",
            "     |  \n",
            "     |  advance(self, n)\n",
            "     |  \n",
            "     |  copy(self)\n",
            "     |  \n",
            "     |  decr(self, n=1)\n",
            "     |  \n",
            "     |  distance(self, x)\n",
            "     |  \n",
            "     |  equal(self, x)\n",
            "     |  \n",
            "     |  incr(self, n=1)\n",
            "     |  \n",
            "     |  next(self)\n",
            "     |  \n",
            "     |  previous(self)\n",
            "     |  \n",
            "     |  value(self)\n",
            "     |  \n",
            "     |  ----------------------------------------------------------------------\n",
            "     |  Static methods defined here:\n",
            "     |  \n",
            "     |  __swig_destroy__ = delete_SwigPyIterator(...)\n",
            "     |  \n",
            "     |  ----------------------------------------------------------------------\n",
            "     |  Data descriptors defined here:\n",
            "     |  \n",
            "     |  __dict__\n",
            "     |      dictionary for instance variables (if defined)\n",
            "     |  \n",
            "     |  __weakref__\n",
            "     |      list of weak references to the object (if defined)\n",
            "     |  \n",
            "     |  ----------------------------------------------------------------------\n",
            "     |  Data and other attributes defined here:\n",
            "     |  \n",
            "     |  __hash__ = None\n",
            "     |  \n",
            "     |  __swig_getmethods__ = {}\n",
            "     |  \n",
            "     |  __swig_setmethods__ = {}\n",
            "    \n",
            "    class reader(builtins.object)\n",
            "     |  reader(filename)\n",
            "     |  \n",
            "     |  Methods defined here:\n",
            "     |  \n",
            "     |  __del__ lambda self\n",
            "     |  \n",
            "     |  __getattr__ lambda self, name\n",
            "     |  \n",
            "     |  __init__(self, filename)\n",
            "     |      Initialize self.  See help(type(self)) for accurate signature.\n",
            "     |  \n",
            "     |  __repr__ = _swig_repr(self)\n",
            "     |  \n",
            "     |  __setattr__ lambda self, name, value\n",
            "     |  \n",
            "     |  check(self, query)\n",
            "     |  \n",
            "     |  close(self)\n",
            "     |  \n",
            "     |  retrieve(self, query)\n",
            "     |  \n",
            "     |  ----------------------------------------------------------------------\n",
            "     |  Static methods defined here:\n",
            "     |  \n",
            "     |  __swig_destroy__ = delete_reader(...)\n",
            "     |  \n",
            "     |  ----------------------------------------------------------------------\n",
            "     |  Data descriptors defined here:\n",
            "     |  \n",
            "     |  __dict__\n",
            "     |      dictionary for instance variables (if defined)\n",
            "     |  \n",
            "     |  __weakref__\n",
            "     |      list of weak references to the object (if defined)\n",
            "     |  \n",
            "     |  measure\n",
            "     |  \n",
            "     |  threshold\n",
            "     |  \n",
            "     |  ----------------------------------------------------------------------\n",
            "     |  Data and other attributes defined here:\n",
            "     |  \n",
            "     |  __swig_getmethods__ = {'measure': <built-in function reader_measure_ge...\n",
            "     |  \n",
            "     |  __swig_setmethods__ = {'measure': <built-in function reader_measure_se...\n",
            "    \n",
            "    class writer(builtins.object)\n",
            "     |  writer(filename, n=3, be=False, unicode=False)\n",
            "     |  \n",
            "     |  Methods defined here:\n",
            "     |  \n",
            "     |  __del__ lambda self\n",
            "     |  \n",
            "     |  __getattr__ lambda self, name\n",
            "     |  \n",
            "     |  __init__(self, filename, n=3, be=False, unicode=False)\n",
            "     |      Initialize self.  See help(type(self)) for accurate signature.\n",
            "     |  \n",
            "     |  __repr__ = _swig_repr(self)\n",
            "     |  \n",
            "     |  __setattr__ lambda self, name, value\n",
            "     |  \n",
            "     |  close(self)\n",
            "     |  \n",
            "     |  insert(self, string)\n",
            "     |  \n",
            "     |  ----------------------------------------------------------------------\n",
            "     |  Static methods defined here:\n",
            "     |  \n",
            "     |  __swig_destroy__ = delete_writer(...)\n",
            "     |  \n",
            "     |  ----------------------------------------------------------------------\n",
            "     |  Data descriptors defined here:\n",
            "     |  \n",
            "     |  __dict__\n",
            "     |      dictionary for instance variables (if defined)\n",
            "     |  \n",
            "     |  __weakref__\n",
            "     |      list of weak references to the object (if defined)\n",
            "     |  \n",
            "     |  ----------------------------------------------------------------------\n",
            "     |  Data and other attributes defined here:\n",
            "     |  \n",
            "     |  __swig_getmethods__ = {}\n",
            "     |  \n",
            "     |  __swig_setmethods__ = {}\n",
            "\n",
            "FUNCTIONS\n",
            "    StringVector_swigregister(...)\n",
            "    \n",
            "    SwigPyIterator_swigregister(...)\n",
            "    \n",
            "    reader_swigregister(...)\n",
            "    \n",
            "    writer_swigregister(...)\n",
            "\n",
            "DATA\n",
            "    cosine = 2\n",
            "    dice = 1\n",
            "    exact = 0\n",
            "    jaccard = 3\n",
            "    overlap = 4\n",
            "\n",
            "FILE\n",
            "    /usr/local/lib/python3.7/dist-packages/simstring.py\n",
            "\n",
            "\n"
          ],
          "name": "stdout"
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "Ua9dxbnPUNoy"
      },
      "source": [
        "# Usage\n",
        "\n",
        "* Index a number of strings\n",
        "* Use the index for lookup\n",
        "* Simple test first:\n",
        "  * 100 famous Finn names\n",
        "  * (you can pick any other data you want for these tests)"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "1T5rFB22UNpC",
        "outputId": "016f3786-0c99-41e6-91f9-161dad339e0a"
      },
      "source": [
        "!wget -nc http://dl.turkunlp.org/textual-data-analysis-course-data/names.txt.bz2\n",
        "!bzcat names.txt.bz2 | head -n 10\n",
        "\n"
      ],
      "execution_count": 3,
      "outputs": [
        {
          "output_type": "stream",
          "text": [
            "--2021-03-10 16:31:32--  http://dl.turkunlp.org/textual-data-analysis-course-data/names.txt.bz2\n",
            "Resolving dl.turkunlp.org (dl.turkunlp.org)... 195.148.30.23\n",
            "Connecting to dl.turkunlp.org (dl.turkunlp.org)|195.148.30.23|:80... connected.\n",
            "HTTP request sent, awaiting response... 200 OK\n",
            "Length: 918 [application/octet-stream]\n",
            "Saving to: ‘names.txt.bz2’\n",
            "\n",
            "names.txt.bz2       100%[===================>]     918  --.-KB/s    in 0s      \n",
            "\n",
            "2021-03-10 16:31:32 (78.5 MB/s) - ‘names.txt.bz2’ saved [918/918]\n",
            "\n",
            "Mikael Agricola\n",
            "Adolf Ehrnrooth\n",
            "Tarja Halonen\n",
            "Urho Kekkonen\n",
            "Aleksis Kivi\n",
            "Elias Lönnrot\n",
            "Kalevala\n",
            "C. G. E. Mannerheim\n",
            "Risto Ryti\n",
            "Jean Sibelius\n"
          ],
          "name": "stdout"
        }
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "T8eK5DMztD8t",
        "outputId": "72afbc17-5104-440c-8da8-572de415d871"
      },
      "source": [
        "import bz2\n",
        "names=bz2.open(\"names.txt.bz2\",\"rt\").read().splitlines()\n",
        "print(len(names))\n",
        "print(names)"
      ],
      "execution_count": 4,
      "outputs": [
        {
          "output_type": "stream",
          "text": [
            "101\n",
            "['Mikael Agricola', 'Adolf Ehrnrooth', 'Tarja Halonen', 'Urho Kekkonen', 'Aleksis Kivi', 'Elias Lönnrot', 'Kalevala', 'C. G. E. Mannerheim', 'Risto Ryti', 'Jean Sibelius', 'Arvo Ylppö', 'Matti Nykänen', 'Väinö Myllyrinne', 'Ville Valo', 'Lalli', 'Väinö Linna', 'Linus Torvalds', 'Spede Pasanen', 'Pentti Linkola', 'Tove Jansson', 'Veikko Hursti', 'Paavo Nurmi', 'Minna Canth', 'Juho Kusti Paasikivi', 'J. V. Snellman', 'Hertta Kuusinen', 'Arto Saari', 'Miina Sillanpää', 'Väinö Tanner', 'Lucina Hagman', 'Kristfrid Ganander', 'Mika Waltari', 'Mika Häkkinen', 'Alvar Aalto', 'Eugen Schauman', 'Tapio Rautavaara', 'Eino Leino', 'Jaakko Pöyry', 'Otto Wille Kuusinen', 'Juice Leskinen', 'Anders Chydenius', 'Uno Cygnaeus', 'Jari Litmanen', 'Katri Helena Kalaoja', 'Fanni Luukkonen', 'Anneli Jäätteenmäki', 'Karl Fazer', 'K. J. Ståhlberg', 'Mauno Koivisto', 'Helene Schjerfbeck', 'Reino Helismaa', 'Jorma Ollila', 'Lauri Törni', 'Georg Henrik von Wright', 'Arndt Pekurinen', 'Tauno Palo', 'Akseli Gallen-Kallela', 'Johan Ludvig Runeberg', 'Kyösti Kallio', 'Paavo Ruotsalainen', 'Lars Levi Laestadius', 'Lasse Virén', 'Helvi Sipilä', 'Yrjö Kallinen', 'A. I. Virtanen', 'Nils-Aslak Valkeapää', 'Armi Kuusela', 'Pehr Evind Svinhufvud', 'Aki Kaurismäki', 'Kalle Päätalo', 'Paavo Lipponen', 'Aurora Karamzin', 'Sakari Topelius', 'Alli Vaittinen-Kuikka', 'Simo Häyhä', 'Jaakko Ilkka', 'Arto Javanainen', 'Leena Palotie', 'Karita Mattila', 'Veikko Hakulinen', 'Helle Kannila', 'Olavi Virta', 'Hannu Salama', 'Irwin Goodman', 'Laila Kinnunen', 'Arvi Lind', 'Kirsti Paakkanen', 'Larin Paraske', 'Mathilda Wrede', 'Erno Paasilinna', 'Antti Tuisku', 'Annikki Tähti', 'Elisabeth Rehn', 'Esa Saarinen', 'Maiju Gebhard', 'Kalevi Sorsa', 'Aksel Airo', 'Lauri Ylönen', 'Raimo Helminen', 'Armi Ratia', 'Veikko Sinisalo']\n"
          ],
          "name": "stdout"
        }
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "7mwveAMtUNpF"
      },
      "source": [
        "# Index\n",
        "import os\n",
        "os.makedirs(\"test_names\",exist_ok=True) #produces a lot of files, make directory to save these\n",
        "db=simstring.writer(\"test_names/test_names.db\") \n",
        "for name in names:\n",
        "    db.insert(name)\n",
        "db.close()\n"
      ],
      "execution_count": 6,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "IW-pYq7oUNpH",
        "outputId": "d3f6040b-2c57-4325-a5a4-5a8818c58e12"
      },
      "source": [
        "# Query\n",
        "db=simstring.reader(\"test_names/test_names.db\")\n",
        "db.measure=simstring.cosine\n",
        "db.threshold=0.5\n",
        "print(db.retrieve(\"Karita Matila\"))\n",
        "print(db.retrieve(\"Arvi Lund\")) #short name, similarity decreases steeply!"
      ],
      "execution_count": 8,
      "outputs": [
        {
          "output_type": "stream",
          "text": [
            "('Karita Mattila',)\n",
            "('Arvi Lind',)\n"
          ],
          "name": "stdout"
        }
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "1BezLLIWUNpJ",
        "outputId": "f365a279-6ec3-427c-fabf-4deefb11c838"
      },
      "source": [
        "db.retrieve(\"Kaarlo Juho Stahlberg\")"
      ],
      "execution_count": 9,
      "outputs": [
        {
          "output_type": "execute_result",
          "data": {
            "text/plain": [
              "()"
            ]
          },
          "metadata": {
            "tags": []
          },
          "execution_count": 9
        }
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "MjPXLi-AUNpK",
        "outputId": "4cdb0c77-5b80-4438-8a64-35c09ef6050d"
      },
      "source": [
        "db.retrieve(\"Kaarlo Juho Ståhlberg\")"
      ],
      "execution_count": 10,
      "outputs": [
        {
          "output_type": "execute_result",
          "data": {
            "text/plain": [
              "('K. J. Ståhlberg',)"
            ]
          },
          "metadata": {
            "tags": []
          },
          "execution_count": 10
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "AnVa5fMuUNpf"
      },
      "source": [
        "* Many limitations shown above\n",
        "* Generic string matching needs further customization\n",
        "* simstring is a great fast first filter for more costly techniques"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "i8vWNVDxUNpg"
      },
      "source": [
        "# Larger index\n",
        "\n",
        "* all Finnish wikidata strings"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "mI0_5ogIjh75",
        "outputId": "271f9e68-7d63-47c4-eff4-dae4091d5092"
      },
      "source": [
        "!wget -nc http://dl.turkunlp.org/textual-data-analysis-course-data/wikidata.fi.bz2"
      ],
      "execution_count": 11,
      "outputs": [
        {
          "output_type": "stream",
          "text": [
            "--2021-03-10 16:39:52--  http://dl.turkunlp.org/textual-data-analysis-course-data/wikidata.fi.bz2\n",
            "Resolving dl.turkunlp.org (dl.turkunlp.org)... 195.148.30.23\n",
            "Connecting to dl.turkunlp.org (dl.turkunlp.org)|195.148.30.23|:80... connected.\n",
            "HTTP request sent, awaiting response... 200 OK\n",
            "Length: 56380139 (54M) [application/octet-stream]\n",
            "Saving to: ‘wikidata.fi.bz2’\n",
            "\n",
            "wikidata.fi.bz2     100%[===================>]  53.77M  14.4MB/s    in 3.7s    \n",
            "\n",
            "2021-03-10 16:39:56 (14.4 MB/s) - ‘wikidata.fi.bz2’ saved [56380139/56380139]\n",
            "\n"
          ],
          "name": "stdout"
        }
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "oF7UjZVTj0HF",
        "outputId": "1d4ac9f7-868c-45b5-b0b4-6a7c5745aaa4"
      },
      "source": [
        "!bzcat wikidata.fi.bz2 | head -n 30"
      ],
      "execution_count": 12,
      "outputs": [
        {
          "output_type": "stream",
          "text": [
            "Belgia\thttps://fi.wikipedia.org/wiki/Belgia\thttps://en.wikipedia.org/wiki/Belgium\tBelgia\n",
            "Belgian kuningaskunta\thttps://fi.wikipedia.org/wiki/Belgia\thttps://en.wikipedia.org/wiki/Belgium\tBelgia\n",
            "onnellisuus\thttps://fi.wikipedia.org/wiki/Onnellisuus\thttps://en.wikipedia.org/wiki/Happiness\tonnellisuus\n",
            ":)\thttps://fi.wikipedia.org/wiki/Onnellisuus\thttps://en.wikipedia.org/wiki/Happiness\tonnellisuus\n",
            "George Washington\thttps://fi.wikipedia.org/wiki/George_Washington\thttps://en.wikipedia.org/wiki/George_Washington\tGeorge Washington\n",
            "Jack Bauer\thttps://fi.wikipedia.org/wiki/Jack_Bauer\thttps://en.wikipedia.org/wiki/Jack_Bauer\tJack Bauer\n",
            "Douglas Adams\thttps://fi.wikipedia.org/wiki/Douglas_Adams\thttps://en.wikipedia.org/wiki/Douglas_Adams\tDouglas Adams\n",
            "Paul Otlet\thttps://fi.wikipedia.org/wiki/Paul_Otlet\thttps://en.wikipedia.org/wiki/Paul_Otlet\tPaul Otlet\n",
            "Wikidata\thttps://fi.wikipedia.org/wiki/Wikidata\thttps://en.wikipedia.org/wiki/Wikidata\tWikidata\n",
            "Portugali\thttps://fi.wikipedia.org/wiki/Portugali\thttps://en.wikipedia.org/wiki/Portugal\tPortugali\n",
            "República Portuguesa\thttps://fi.wikipedia.org/wiki/Portugali\thttps://en.wikipedia.org/wiki/Portugal\tPortugali\n",
            "Portugalin tasavalta\thttps://fi.wikipedia.org/wiki/Portugali\thttps://en.wikipedia.org/wiki/Portugal\tPortugali\n",
            "PT\thttps://fi.wikipedia.org/wiki/Portugali\thttps://en.wikipedia.org/wiki/Portugal\tPortugali\n",
            "Etelämanner\thttps://fi.wikipedia.org/wiki/Etelämanner\thttps://en.wikipedia.org/wiki/Antarctica\tEtelämanner\n",
            "siitin\thttps://fi.wikipedia.org/wiki/Siitin\thttps://en.wikipedia.org/wiki/Penis\tsiitin\n",
            "penis\thttps://fi.wikipedia.org/wiki/Siitin\thttps://en.wikipedia.org/wiki/Penis\tsiitin\n",
            "tietokone\thttps://fi.wikipedia.org/wiki/Tietokone\thttps://en.wikipedia.org/wiki/Computer\ttietokone\n",
            "internet\thttps://fi.wikipedia.org/wiki/Internet\thttps://en.wikipedia.org/wiki/Internet\tinternet\n",
            "netti\thttps://fi.wikipedia.org/wiki/Internet\thttps://en.wikipedia.org/wiki/Internet\tinternet\n",
            "verkko\thttps://fi.wikipedia.org/wiki/Internet\thttps://en.wikipedia.org/wiki/Internet\tinternet\n",
            "Internet\thttps://fi.wikipedia.org/wiki/Internet\thttps://en.wikipedia.org/wiki/Internet\tinternet\n",
            "pneumonoultra mikroskopiko silikovulkanokonioosi\thttps://fi.wikipedia.org/wiki/Pneumonoultra­mikroskopiko­silikovulkanokonioosi\thttps://en.wikipedia.org/wiki/Pneumonoultramicroscopicsilicovolcanoconiosis\tpneumonoultra mikroskopiko silikovulkanokonioosi\n",
            "superoptihupilystivekkuloistokainen\tNone\thttps://en.wikipedia.org/wiki/Supercalifragilisticexpialidocious\tsuperoptihupilystivekkuloistokainen\n",
            "supercalifragilisticexpialidocious\tNone\thttps://en.wikipedia.org/wiki/Supercalifragilisticexpialidocious\tsuperoptihupilystivekkuloistokainen\n",
            "marraskuu\thttps://fi.wikipedia.org/wiki/Marraskuu\thttps://en.wikipedia.org/wiki/November\tmarraskuu\n",
            "marraskuuta\thttps://fi.wikipedia.org/wiki/Marraskuu\thttps://en.wikipedia.org/wiki/November\tmarraskuu\n",
            "leijona\thttps://fi.wikipedia.org/wiki/Leijona\thttps://en.wikipedia.org/wiki/Lion\tleijona\n",
            "koira\thttps://fi.wikipedia.org/wiki/Koira\thttps://en.wikipedia.org/wiki/Dog\tkoira\n",
            "kesykoira\thttps://fi.wikipedia.org/wiki/Koira\thttps://en.wikipedia.org/wiki/Dog\tkoira\n",
            "kissanpentu\tNone\thttps://en.wikipedia.org/wiki/Kitten\tkissanpentu\n"
          ],
          "name": "stdout"
        }
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "HmsOFfqlUNpg",
        "outputId": "f0079d36-644e-4d9b-9c5b-9a9d60a68a4a"
      },
      "source": [
        "from tqdm import tqdm #progress-bar\n",
        "os.makedirs(\"wikidata.db\",exist_ok=True)\n",
        "db=simstring.writer(\"wikidata.db/wikidata.db\")\n",
        "with bz2.open(\"wikidata.fi.bz2\",\"rt\") as f:\n",
        "    for line in tqdm(f):\n",
        "        line=line.strip()\n",
        "        # 4-col file with string, two urls, and official label\n",
        "        # let us index the strings\n",
        "        s,url1,url2,label=line.split(\"\\t\")\n",
        "        db.insert(s)\n",
        "db.close()"
      ],
      "execution_count": 13,
      "outputs": [
        {
          "output_type": "stream",
          "text": [
            "3995911it [01:38, 40708.00it/s]\n"
          ],
          "name": "stderr"
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "Fd1-yT-jUNph"
      },
      "source": [
        "* 4M strings - 2min index time"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "T3LQdJk2UNph",
        "outputId": "11a23988-5f47-47a8-d40a-98bf1f573f21"
      },
      "source": [
        "db=simstring.reader(\"wikidata.db/wikidata.db\")\n",
        "db.retrieve(\"Tarja Halonen\")"
      ],
      "execution_count": 14,
      "outputs": [
        {
          "output_type": "execute_result",
          "data": {
            "text/plain": [
              "('Ona Halonen',\n",
              " 'Esa Halonen',\n",
              " 'Mia Halonen',\n",
              " 'Tarja Halonen',\n",
              " 'Tarja Salonen',\n",
              " 'Tuija Halonen',\n",
              " 'Maija Halonen',\n",
              " 'Luokka:Tarja Halonen',\n",
              " 'Tarja Kaarina Halonen')"
            ]
          },
          "metadata": {
            "tags": []
          },
          "execution_count": 14
        }
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "7MbN_tSqUNpi",
        "outputId": "341af8f4-c558-4cb3-8621-5ca1cdf40072"
      },
      "source": [
        "db.retrieve(\"Turun yliopisto\")"
      ],
      "execution_count": 15,
      "outputs": [
        {
          "output_type": "execute_result",
          "data": {
            "text/plain": [
              "('yliopisto',\n",
              " 'Turun yliopisto',\n",
              " 'Oulun yliopisto',\n",
              " 'Oulun yliopisto',\n",
              " 'Ségoun yliopisto',\n",
              " 'Tohokun yliopisto',\n",
              " 'Turun kesäyliopisto',\n",
              " 'Luokka:Turun yliopisto',\n",
              " 'Turun yliopiston kuoro',\n",
              " 'Malline:Turun yliopisto',\n",
              " 'Turun yliopistosäätiö',\n",
              " 'Turun yliopiston alue 10',\n",
              " 'Turun yliopiston kuoro ry',\n",
              " 'Turun yliopiston kirjasto',\n",
              " 'Kansatiede Turun yliopisto',\n",
              " 'Turun yliopiston kasvimuseo',\n",
              " 'Turun yliopiston eläinmuseo')"
            ]
          },
          "metadata": {
            "tags": []
          },
          "execution_count": 15
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "DJ_QKCC7UNpj"
      },
      "source": [
        "## Lookup speed"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "y9GCbn0aUNpj",
        "outputId": "4cb9edb7-ccf8-4e24-af0d-df5549bd29e2"
      },
      "source": [
        "import os\n",
        "from tqdm import tqdm\n",
        "with bz2.open(\"wikidata.fi.bz2\",\"rt\") as f:\n",
        "    for i,line in enumerate(tqdm(f)):\n",
        "        line=line.strip()\n",
        "        db.retrieve(line)\n",
        "        if i==10000:\n",
        "            break\n"
      ],
      "execution_count": 16,
      "outputs": [
        {
          "output_type": "stream",
          "text": [
            "9925it [00:09, 1017.10it/s]\n"
          ],
          "name": "stderr"
        }
      ]
    }
  ]
}