notebooks/spelling/Spellchecking.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Семинар 3. Исправление опечаток"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [],
   "source": [
    "# !pip install razdel tqdm"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "import os, re\n",
    "from string import punctuation\n",
    "import numpy as np\n",
    "import json\n",
    "from collections import Counter\n",
    "from pprint import pprint\n",
    "from nltk import sent_tokenize\n",
    "punctuation += \"«»—…“”\"\n",
    "punct = set(punctuation)\n",
    "from sklearn.metrics import classification_report, accuracy_score\n",
    "from string import punctuation\n",
    "from razdel import sentenize\n",
    "from razdel import tokenize as razdel_tokenize\n",
    "import numpy as np\n",
    "from collections import Counter"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [],
   "source": [
    "# библиотека для отслеживания прогресса\n",
    "from tqdm.notebook import tqdm"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Возьмем данные с соревнования [Dialog Evaluation 2016](http://www.dialog-21.ru/evaluation/2016/spelling_correction/) по исправлению опечаток. Данные представляют собой набор предложений (правильное - ошибочное). Задача найти слова с ошибками и заменить их на правильный вариант.\n",
    "\n",
    "Я удалили из данных случаи, когда в словах пропущен или вставлен пробел, чтобы было проще сопоставить слова в предложении. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [],
   "source": [
    "bad = open('data/sents_with_mistakes.txt', encoding='utf8').read().splitlines()\n",
    "true = open('data/correct_sents.txt', encoding='utf8').read().splitlines()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "915"
      ]
     },
     "execution_count": 4,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "len(true)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Пояним эту мысль.\n",
      "Поясним эту мысль\n"
     ]
    }
   ],
   "source": [
    "# Посмотрим на пары предложений\n",
    "print(bad[2])\n",
    "print(true[2])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [],
   "source": [
    "# напишем функцию, которая будет сопоставлять слова в правильном и ошибочном варианте\n",
    "# разобьем предложение по пробелам и удалим пунктуация на границах слов\n",
    "def align_words(sent_1, sent_2):\n",
    "    tokens_1 = sent_1.lower().split()\n",
    "    tokens_2 = sent_2.lower().split()\n",
    "    \n",
    "    tokens_1 = [token.strip(punctuation) for token in tokens_1]\n",
    "    tokens_2 = [token.strip(punctuation) for token in tokens_2]\n",
    "    \n",
    "    tokens_1 = [token for token in tokens_1 if token]\n",
    "    tokens_2 = [token for token in tokens_2 if token]\n",
    "    \n",
    "    assert len(tokens_1) == len(tokens_2)\n",
    "    \n",
    "    return list(zip(tokens_1, tokens_2))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[('апофеозом', 'опофеозом'),\n",
      " ('дня', 'дня'),\n",
      " ('для', 'для'),\n",
      " ('меня', 'меня'),\n",
      " ('сегодня', 'сегодня'),\n",
      " ('стала', 'стала'),\n",
      " ('фраза', 'фраза'),\n",
      " ('услышанная', 'услышанная'),\n",
      " ('в', 'в'),\n",
      " ('новостях', 'новостях')]\n"
     ]
    }
   ],
   "source": [
    "pprint(align_words(true[1], bad[1]))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Вытащим только неправильные варианты и заодно посчитаем процент ошибок."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {},
   "outputs": [],
   "source": [
    "mistakes = []\n",
    "total = 0\n",
    "for i in range(len(true)):\n",
    "    word_pairs = align_words(true[i], bad[i])\n",
    "    \n",
    "    \n",
    "    for pair in word_pairs:\n",
    "        if pair[0] != pair[1]:\n",
    "            mistakes.append(pair)\n",
    "        total += 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Доля ошибок -  0.12886443221610805\n"
     ]
    }
   ],
   "source": [
    "print('Доля ошибок - ', len(mistakes)/total )"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Обернем в Counter, чтобы сразу увидеть частотные ошибки."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[(('сегодня', 'седня'), 24),\n",
       " (('вообще', 'вобще'), 18),\n",
       " (('вообще', 'ваще'), 17),\n",
       " (('естественно', 'естесственно'), 17),\n",
       " (('хочется', 'хочеться'), 16),\n",
       " (('кстати', 'кстате'), 16),\n",
       " (('очень', 'ооочень'), 14),\n",
       " (('как-то', 'както'), 9),\n",
       " (('очень', 'оооочень'), 9),\n",
       " (('это', 'ето'), 9)]"
      ]
     },
     "execution_count": 10,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "Counter(mistakes).most_common(10)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Из-за того, что процент ошибок довольно низкий, не очень выгодно будет находить исправление для каждого слова. Нужен какой-то более простой классификатор, который выделит ошибочные слова, чтобы потом только их и редактировать."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Самый простой способ это сделать - составить словарь правильных слов и потом сравнивать с ним. Чтобы не делать этого вручную, можно взять какой-нибудь корпус текстов, прошедщих редактуру. Тексты из википедии для этого хорошо подходят."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {},
   "outputs": [],
   "source": [
    "corpus = open('data/wiki_data.txt', encoding='utf8').read()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Попробуем предсказать ошибку простым заглядыванием в словарь. Если слово не в словаре - оно неправильное."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 33,
   "metadata": {},
   "outputs": [],
   "source": [
    "# создаем словарь\n",
    "vocab = Counter(re.findall('\\w+', corpus.lower()))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {},
   "outputs": [],
   "source": [
    "def predict_mistaken(word, vocab):\n",
    "    return 0 if word in vocab else 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "metadata": {},
   "outputs": [],
   "source": [
    "# для оценки создаем два списка y_true и y_pred\n",
    "# проходимся по предложениям\n",
    "# сопоставляем слова с помощью функции align_words\n",
    "# проходимся по парам слов и\n",
    "# если слова одинаковые добавляем в y_true 0 \n",
    "# если слова разные добавляем в y_true 1\n",
    "# предказываем ошибочность слова из bad списка \n",
    "# добавляем предсказание в список y_pred\n",
    "\n",
    "y_true = []\n",
    "y_pred = []\n",
    "\n",
    "for i in range(len(true)):\n",
    "    word_pairs = align_words(true[i], bad[i])\n",
    "    for pair in word_pairs:\n",
    "        if pair[0] == pair[1]:\n",
    "            y_true.append(0)\n",
    "        else:\n",
    "            y_true.append(1)\n",
    "        \n",
    "        y_pred.append(predict_mistaken(pair[1], vocab))\n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "              precision    recall  f1-score   support\n",
      "\n",
      "           0       0.98      0.91      0.94      8707\n",
      "           1       0.59      0.88      0.71      1288\n",
      "\n",
      "    accuracy                           0.91      9995\n",
      "   macro avg       0.79      0.90      0.83      9995\n",
      "weighted avg       0.93      0.91      0.91      9995\n",
      "\n"
     ]
    }
   ],
   "source": [
    "# оцените качество с помощью classification_report\n",
    "print(classification_report(y_true, y_pred, ))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Генерация исправлений"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Теперь нужно думать о том, как исправить неправильные слова. Посмотрим как это можно делать на примере известного алгоритма Питера Норвига. Идея алгоритма очень простая - для каждого неправильного слова нужно сгенерировать варианты исправлений и выбрать из них тот , что есть в словаре, а если таких несколько, то выбрать наиболее вероятный. \n",
    "\n",
    "Неправильными считаются слова, которых нет в словаре (также как в функции выше). А вероятность слова расчитывается по формуле - абсолютная частота слова в корпусе разделить на количество слов в корпусе."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Абсолютные частоты лежат в счетчике"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 22,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[('в', 267296),\n",
       " ('и', 147115),\n",
       " ('на', 81926),\n",
       " ('с', 61681),\n",
       " ('года', 43894),\n",
       " ('по', 37235),\n",
       " ('году', 32197),\n",
       " ('из', 29150),\n",
       " ('был', 23293),\n",
       " ('не', 23228)]"
      ]
     },
     "execution_count": 22,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "vocab.most_common(10)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "В вероятности они преобразуются вот такой функцией"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 23,
   "metadata": {},
   "outputs": [],
   "source": [
    "N = sum(vocab.values())\n",
    "\n",
    "def P(word, N=N):\n",
    "    return vocab[word] / N\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Во втором подготовительном семинаре немного разбиралась работа с вероятностями в питоне (представление маленьких и больших чисел в питоне, свойства логарифмов вероятностей), будет полезно повторить - https://github.com/mannefedov/compling_nlp_hse_course/blob/master/notebooks/first_module_intro/02_ngrams.ipynb (раздел про вероятности в конце)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Теперь самое интересное - способ генерации вариантов исправлений. Они генерируются 4 типами эвристик: удаление, перестановка, замена, вставка. \n",
    "\n",
    "1) удаление - по очереди выбрасываем из слова 1 букву (слово - лово, сово, слво, слоо, слов)  \n",
    "2) перестановка - по очереди меняем соседние буквы (слово - лсово, солво, слвоо, слоов)  \n",
    "3) замена - по очереди заменям каждую букву на другую букву алфавита (слово - алово, блово, влово, глово...)  \n",
    "4) вставка - по очереди вставляем между соседними буквами букву алфавита (слово - салово, сблово, свлово, сглово...)  \n",
    "\n",
    "В алгоритма два уровня генерации - сначала генерируются варианты для оригинального слова, а потом варианты для каждого варианта. Таким образом, максимальное допустимое отличие для ошибки и предсказания - 2 буквы."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 25,
   "metadata": {},
   "outputs": [],
   "source": [
    "# оригинальный код вот тут - https://norvig.com/spell-correct.html\n",
    "# я только адаптировал его под русский язык\n",
    "\n",
    "def correction(word): \n",
    "    \"Находим наиболее вероятное похожее слово\"\n",
    "    return max(candidates(word), key=P)\n",
    "\n",
    "def candidates(word): \n",
    "    \"Генерируем кандидатов на исправление\"\n",
    "    return (known([word]) or known(edits1(word)) or known(edits2(word)) or [word])\n",
    "\n",
    "def known(words): \n",
    "    \"Выбираем слова, которые есть в корпусе\"\n",
    "    return set(w for w in words if w in vocab)\n",
    "\n",
    "\n",
    "def edits1(word):\n",
    "    \"Создаем кандидатов, которые отличаются на одну букву\"\n",
    "    letters    = 'йцукенгшщзхъфывапролджэячсмитьбюё'\n",
    "    splits     = [(word[:i], word[i:])    for i in range(len(word) + 1)]\n",
    "    deletes    = [L + R[1:]               for L, R in splits if R]\n",
    "    transposes = [L + R[1] + R[0] + R[2:] for L, R in splits if len(R)>1]\n",
    "    replaces   = [L + c + R[1:]           for L, R in splits if R for c in letters]\n",
    "    inserts    = [L + c + R               for L, R in splits for c in letters]\n",
    "    return set(deletes + transposes + replaces + inserts)\n",
    "\n",
    "def edits2(word): \n",
    "    \"Создаем кандидатов, которые отличаются на две буквы\"\n",
    "    return (e2 for e1 in edits1(word) for e2 in edits1(e1))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Попробуем исправить"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 35,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "CPU times: user 582 µs, sys: 58 µs, total: 640 µs\n",
      "Wall time: 908 µs\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "'солнце'"
      ]
     },
     "execution_count": 35,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "%%time\n",
    "correction('сcолнце')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 32,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "CPU times: user 820 µs, sys: 43 µs, total: 863 µs\n",
      "Wall time: 1.06 ms\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "'чаще'"
      ]
     },
     "execution_count": 32,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "%%time\n",
    "correction('ваще')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 33,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "CPU times: user 648 µs, sys: 1 µs, total: 649 µs\n",
      "Wall time: 655 µs\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "'апофеоз'"
      ]
     },
     "execution_count": 33,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "%%time\n",
    "correction('опофеоз')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Выводов по единичным примерам не сделаешь, поэтому давайте запустим на всем нашем корпусе"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Для оценки используем будем использовать три метрики:  \n",
    "1) процент правильных слов;  \n",
    "2) процент исправленных ошибок  \n",
    "3) процент ошибочно исправленных правильных слов"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 37,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "application/vnd.jupyter.widget-view+json": {
       "model_id": "ebbb425047ff455997758fbf2cc686e8",
       "version_major": 2,
       "version_minor": 0
      },
      "text/plain": [
       "  0%|          | 0/915 [00:00<?, ?it/s]"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "correct = 0\n",
    "total = 0\n",
    "\n",
    "total_mistaken = 0\n",
    "mistaken_fixed = 0\n",
    "\n",
    "total_correct = 0\n",
    "correct_broken = 0\n",
    "\n",
    "cashed = {}\n",
    "for i in tqdm(range(len(true))):\n",
    "    word_pairs = align_words(true[i], bad[i])\n",
    "    for pair in word_pairs:\n",
    "        # чтобы два раза не исправлять одно и тоже слово - закешируем его\n",
    "        # перед тем как считать исправление проверим нет ли его в кеше\n",
    "        \n",
    "        predicted = cashed.get(pair[1], correction(pair[1]))\n",
    "        cashed[pair[1]] = predicted\n",
    "        \n",
    "        \n",
    "        if predicted == pair[0]:\n",
    "            correct += 1\n",
    "        total += 1\n",
    "        \n",
    "        if pair[0] == pair[1]:\n",
    "            total_correct += 1\n",
    "            if pair[0] !=  predicted:\n",
    "                correct_broken += 1\n",
    "        else:\n",
    "            total_mistaken += 1\n",
    "            if pair[0] == predicted:\n",
    "                mistaken_fixed += 1\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Получается, что в целом не стало лучше. Хотя 50% опечаток исправляются корректно"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 38,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "0.8708354177088544\n",
      "0.5116459627329193\n",
      "0.07603077983231882\n"
     ]
    }
   ],
   "source": [
    "print(correct/total)\n",
    "print(mistaken_fixed/total_mistaken)\n",
    "print(correct_broken/total_correct)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Ещё проблема тут в том, что алгоритм медленно работает для длинных слов."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 36,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "CPU times: user 492 µs, sys: 32 µs, total: 524 µs\n",
      "Wall time: 716 µs\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "'солнце'"
      ]
     },
     "execution_count": 36,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "%%time\n",
    "correction('солнвце')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 37,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "CPU times: user 1.49 s, sys: 4.36 ms, total: 1.5 s\n",
      "Wall time: 1.52 s\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "'насмехатьсяаававттававаываываы'"
      ]
     },
     "execution_count": 37,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "%%time\n",
    "correction('насмехатьсяаававттававаываываы')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Посмотрим, как исправляются самые частотные ошибки."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 41,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[('сегодня', 'седня', 'седая'),\n",
       " ('вообще', 'вобще', 'вообще'),\n",
       " ('вообще', 'ваще', 'чаще'),\n",
       " ('естественно', 'естесственно', 'естественно'),\n",
       " ('хочется', 'хочеться', 'хочется'),\n",
       " ('кстати', 'кстате', 'кстати'),\n",
       " ('очень', 'ооочень', 'очень'),\n",
       " ('как-то', 'както', 'факто'),\n",
       " ('очень', 'оооочень', 'сорочень'),\n",
       " ('это', 'ето', 'что')]"
      ]
     },
     "execution_count": 41,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "[(wt[0], wt[1], correction(wt[1])) for wt, _ in Counter(mistakes).most_common(10)]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Метрики близости слов."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Вместо того, чтобы генерировать все варианты, можно искать похожие слова в словаре. Для этого нужно задать метрику похожести. Для исправления опечаток часто используются расстояния редактирования"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Самое известное расстояние редактирования - расстояние Левенштейна. Тут мы не будет поднобно разбирать алгоритм, можете почитать [тут](https://ru.wikipedia.org/wiki/%D0%A0%D0%B0%D1%81%D1%81%D1%82%D0%BE%D1%8F%D0%BD%D0%B8%D0%B5_%D0%9B%D0%B5%D0%B2%D0%B5%D0%BD%D1%88%D1%82%D0%B5%D0%B9%D0%BD%D0%B0), посмотреть более понятный разбор [тут](https://www.youtube.com/watch?v=MiqoA-yF-0M), а код на питоне есть [тут](https://ru.wikibooks.org/wiki/%D0%A0%D0%B5%D0%B0%D0%BB%D0%B8%D0%B7%D0%B0%D1%86%D0%B8%D0%B8_%D0%B0%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC%D0%BE%D0%B2/%D0%A0%D0%B0%D1%81%D1%81%D1%82%D0%BE%D1%8F%D0%BD%D0%B8%D0%B5_%D0%9B%D0%B5%D0%B2%D0%B5%D0%BD%D1%88%D1%82%D0%B5%D0%B9%D0%BD%D0%B0).\n",
    "Про самого Левенштейна можно почитать вот тут - https://nplus1.ru/material/2017/09/25/vladimir-levenshtein\n",
    "\n",
    "Основная идея - найти минимальное число исправлений, которое нужно сделать в слове А, чтобы получить слово Б. Причем допустимы только три вида исправлений - удаление, вставка, замена. \n",
    "\n",
    "Ещё есть расстояние Дамерау-Левенштейна - почти то же самое, только разрешена ещё операция перестановки."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Есть библиотека textdistance, в которой реализованы многие методы нахождения расстояний."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 42,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Collecting textdistance\n",
      "  Downloading textdistance-4.5.0-py3-none-any.whl (31 kB)\n",
      "Installing collected packages: textdistance\n",
      "Successfully installed textdistance-4.5.0\n"
     ]
    }
   ],
   "source": [
    "!pip install textdistance"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 38,
   "metadata": {},
   "outputs": [],
   "source": [
    "import textdistance"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 39,
   "metadata": {},
   "outputs": [],
   "source": [
    "def get_closest_match_with_metric(text, lookup, topn=20, metric=textdistance.levenshtein):\n",
    "    # Counter можно использовать и с не целыми числами\n",
    "    similarities = Counter()\n",
    "    \n",
    "    for word in lookup:\n",
    "        similarities[word] = metric.normalized_similarity(text, word) \n",
    "    \n",
    "    return similarities.most_common(topn)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 45,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "CPU times: user 11.8 s, sys: 322 ms, total: 12.1 s\n",
      "Wall time: 12 s\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "[('солнце', 0.8333333333333334),\n",
       " ('конце', 0.8),\n",
       " ('монце', 0.8),\n",
       " ('соне', 0.8),\n",
       " ('сонче', 0.8),\n",
       " ('донце', 0.8),\n",
       " ('солнцем', 0.7142857142857143),\n",
       " ('солнцев', 0.7142857142857143),\n",
       " ('солнца', 0.6666666666666667),\n",
       " ('сочное', 0.6666666666666667),\n",
       " ('синице', 0.6666666666666667),\n",
       " ('солнцу', 0.6666666666666667),\n",
       " ('сочные', 0.6666666666666667),\n",
       " ('свинце', 0.6666666666666667),\n",
       " ('сфорце', 0.6666666666666667),\n",
       " ('монцей', 0.6666666666666667),\n",
       " ('ньонце', 0.6666666666666667),\n",
       " ('соньер', 0.6666666666666667),\n",
       " ('сорное', 0.6666666666666667),\n",
       " ('донцем', 0.6666666666666667)]"
      ]
     },
     "execution_count": 45,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "%%time\n",
    "get_closest_match_with_metric('сонце', vocab, 20, textdistance.levenshtein)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 46,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "CPU times: user 15.7 s, sys: 25.6 ms, total: 15.7 s\n",
      "Wall time: 15.8 s\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "[('солнце', 0.8333333333333334),\n",
       " ('конце', 0.8),\n",
       " ('монце', 0.8),\n",
       " ('соне', 0.8),\n",
       " ('сонче', 0.8),\n",
       " ('донце', 0.8),\n",
       " ('солнцем', 0.7142857142857143),\n",
       " ('солнцев', 0.7142857142857143),\n",
       " ('солнца', 0.6666666666666667),\n",
       " ('сочное', 0.6666666666666667),\n",
       " ('синице', 0.6666666666666667),\n",
       " ('солнцу', 0.6666666666666667),\n",
       " ('сочные', 0.6666666666666667),\n",
       " ('свинце', 0.6666666666666667),\n",
       " ('сфорце', 0.6666666666666667),\n",
       " ('монцей', 0.6666666666666667),\n",
       " ('ньонце', 0.6666666666666667),\n",
       " ('соньер', 0.6666666666666667),\n",
       " ('сорное', 0.6666666666666667),\n",
       " ('донцем', 0.6666666666666667)]"
      ]
     },
     "execution_count": 46,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "%%time\n",
    "get_closest_match_with_metric('сонце', vocab, 20, textdistance.damerau_levenshtein)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": 46,
   "metadata": {
    "scrolled": true
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "CPU times: user 20.1 s, sys: 39.2 ms, total: 20.2 s\n",
      "Wall time: 20.2 s\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "[('апофеоз', 0.8571428571428572),\n",
       " ('апофеоза', 0.75),\n",
       " ('апофеозом', 0.6666666666666667),\n",
       " ('апофеты', 0.5714285714285714),\n",
       " ('опорной', 0.5714285714285714)]"
      ]
     },
     "execution_count": 46,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "%%time\n",
    "get_closest_match_with_metric('опофеоз', vocab, 5, textdistance.damerau_levenshtein)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 47,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "CPU times: user 9.39 s, sys: 18.5 ms, total: 9.41 s\n",
      "Wall time: 9.41 s\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "[('кул', 1.0), ('акул', 0.75), ('коул', 0.75), ('куль', 0.75), ('кулл', 0.75)]"
      ]
     },
     "execution_count": 47,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "%%time\n",
    "get_closest_match_with_metric('кул', vocab, 5, textdistance.damerau_levenshtein)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Можно немного ускорить поиск, сократив количество слов в словаре. Возьмем только те, что встречаются больше 5 раз."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 47,
   "metadata": {},
   "outputs": [],
   "source": [
    "vocab_top = {word:count for word, count in vocab.items() if count > 5}"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 48,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "CPU times: user 2.92 s, sys: 6 ms, total: 2.93 s\n",
      "Wall time: 2.96 s\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "[('солнце', 0.8333333333333334),\n",
       " ('конце', 0.8),\n",
       " ('монце', 0.8),\n",
       " ('соне', 0.8),\n",
       " ('солнцем', 0.7142857142857143),\n",
       " ('солнца', 0.6666666666666667),\n",
       " ('солнцу', 0.6666666666666667),\n",
       " ('сочные', 0.6666666666666667),\n",
       " ('союзе', 0.6),\n",
       " ('зоне', 0.6),\n",
       " ('сносе', 0.6),\n",
       " ('фоне', 0.6),\n",
       " ('концу', 0.6),\n",
       " ('конца', 0.6),\n",
       " ('конец', 0.6),\n",
       " ('гонке', 0.6),\n",
       " ('донец', 0.6),\n",
       " ('сотне', 0.6),\n",
       " ('сон', 0.6),\n",
       " ('синие', 0.6)]"
      ]
     },
     "execution_count": 48,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "%%time\n",
    "get_closest_match_with_metric('сонце', vocab_top, 20, textdistance.damerau_levenshtein)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Сильно быстрее не стало"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Еще в питоне есть встроенная библиотека для нахождения близких строк"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 50,
   "metadata": {},
   "outputs": [],
   "source": [
    "from difflib import get_close_matches"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 52,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "CPU times: user 155 ms, sys: 2.25 ms, total: 157 ms\n",
      "Wall time: 161 ms\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "['солнце', 'соне', 'солнцем', 'сотне']"
      ]
     },
     "execution_count": 52,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "%%time\n",
    "get_close_matches('сонце', vocab_top.keys(), n=4)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Работает тоже не очень быстро."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "С большим словарем даже оптимизированные версии будут работать очень долго. И принципиально с этим ничего не сделаешь, т.к. поиск минимального расстояния редактирования - сложный алгоритм, а хороший словарь должен быть большим. \n",
    "\n",
    "Но можно обратить внимание на то, что расстояние редактирование до большинства слов в словаре считать бессмысленно, т.к. они очевидно отличаются слишком сильно (например, слово \"лес\" и \"заноза\" настолько разные, что нам неважно какое между ними расстояние редактирования). Нам нужно придумать способ, который бы позволил нам выделить из словаря только те слова, до которых имеет смысл считать расстояние редактирования. \n",
    "\n",
    "Кажется, что **косинусное расстояние по мешку символов** хорошо для этого подходит. Близкими будут слова, состоящие из одинаковых символов. Расстояние редактирования между такими словами может быть и большим (акула-лука),  и маленьким (акула-акул), поэтому их придется проверить расстоянием левенштейна прежде, чем предсказывать. При этом мы можем быть уверены, что далекими по косинусу точно не будут слова с маленьким расстоянием редактирования! И соответственно их можно сразу отбросить из кандидатов на исправление."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Косинусное расстояние работает на векторах, а векторные операции сильно быстрее любых циклов (а внутри расстояния левенштейна иммено циклы)."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Сделаем поиск похожих по векторам символов, из которых состоит слово. Косинусное расстояние между векторами слов не равно расстоянию редактирования, т.к. в нем не учитывается порядок символов. Близкими будут слова, состоящие из одинаковых символов. Но мы можем быть уверены, что близкими точно не будут слова с большим косинсным расстоянием, и можем их не проверять их честной метрикой редактирования."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 53,
   "metadata": {},
   "outputs": [],
   "source": [
    "import numpy as np\n",
    "from sklearn.feature_extraction.text import CountVectorizer, TfidfVectorizer\n",
    "from sklearn.metrics.pairwise import cosine_similarity, cosine_distances"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 64,
   "metadata": {},
   "outputs": [],
   "source": [
    "vocab = Counter(re.findall('\\w+', corpus.lower()))\n",
    "\n",
    "word2id = list(vocab.keys())\n",
    "id2word = {i:word for i, word in enumerate(vocab)}\n",
    "\n",
    "\n",
    "vec = CountVectorizer(analyzer='char', max_features=10000, ngram_range=(1,3))\n",
    "X = vec.fit_transform(vocab)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 65,
   "metadata": {},
   "outputs": [],
   "source": [
    "# vec.get_feature_names()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 66,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(368802, 10000)"
      ]
     },
     "execution_count": 66,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "X.shape"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 67,
   "metadata": {},
   "outputs": [],
   "source": [
    "def get_closest_match_vec(text, X, vec, topn=20):\n",
    "    v = vec.transform([text])\n",
    "    \n",
    "    # вся эффективноть берется из того, что мы сразу считаем близость \n",
    "    # 1 вектора ко всей матрице (словам в словаре)\n",
    "    # считать по отдельности циклом было бы дольше\n",
    "    # вместо одного вектора может даже целая матрица\n",
    "    # тогда считаться в итоге будет ещё быстрее\n",
    "    \n",
    "    similarities = cosine_distances(v, X)[0]\n",
    "    topn = similarities.argsort()[:topn] \n",
    "    \n",
    "    return [(id2word[top], similarities[top]) for top in topn]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 68,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "CPU times: user 225 ms, sys: 23.7 ms, total: 249 ms\n",
      "Wall time: 253 ms\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "[('монце', 0.24999999999999978),\n",
       " ('донце', 0.24999999999999978),\n",
       " ('конце', 0.24999999999999978),\n",
       " ('херсонцев', 0.2640199278060129),\n",
       " ('саксонцев', 0.2640199278060129),\n",
       " ('сон', 0.2928932188134523),\n",
       " ('олонце', 0.2998599579859951),\n",
       " ('ньонце', 0.2998599579859952),\n",
       " ('соне', 0.3264246859454365),\n",
       " ('донцем', 0.3291796067500631),\n",
       " ('монцей', 0.3291796067500631),\n",
       " ('солнце', 0.3291796067500631),\n",
       " ('концессионное', 0.33217692887937167),\n",
       " ('концерн', 0.3545027756320972),\n",
       " ('монцезе', 0.3545027756320972),\n",
       " ('концессионном', 0.35948738477965136),\n",
       " ('концессионера', 0.36155760193093855),\n",
       " ('концессионером', 0.36555873142548445),\n",
       " ('лондонцев', 0.367544467966324),\n",
       " ('эстонцев', 0.3700592116512881)]"
      ]
     },
     "execution_count": 68,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "%%time\n",
    "get_closest_match_vec('сонце', X, vec) # это расстояние - чем меньше тем лучше"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Напишем функцию, которая принимает слово и находит ближайшее к нему в словаре с помощью косинусного расстояния, а затем проверяет варианты честной метрикой редактирования. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 69,
   "metadata": {},
   "outputs": [],
   "source": [
    "def get_closest_hybrid_match(text, X, vec, topn=3, metric=textdistance.damerau_levenshtein):\n",
    "    candidates = get_closest_match_vec(text, X, vec, topn*4)\n",
    "    lookup = [cand[0] for cand in candidates]\n",
    "    closest = get_closest_match_with_metric(text, lookup, topn, metric=metric)\n",
    "\n",
    "    \n",
    "    return closest"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 70,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "CPU times: user 74.2 ms, sys: 25.7 ms, total: 99.9 ms\n",
      "Wall time: 106 ms\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "[('солнце', 0.8333333333333334), ('монце', 0.8), ('донце', 0.8)]"
      ]
     },
     "execution_count": 70,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "%%time\n",
    "get_closest_hybrid_match('сонце', X, vec)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Оценим такой метод исправления."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 71,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "application/vnd.jupyter.widget-view+json": {
       "model_id": "6b7310769f05474692061c96191cbda6",
       "version_major": 2,
       "version_minor": 0
      },
      "text/plain": [
       "  0%|          | 0/915 [00:00<?, ?it/s]"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "mistakes = []\n",
    "total_mistaken = 0\n",
    "mistaken_fixed = 0\n",
    "\n",
    "total_correct = 0\n",
    "correct_broken = 0\n",
    "\n",
    "total = 0\n",
    "correct = 0\n",
    "\n",
    "cashed = {}\n",
    "for i in tqdm(range(len(true))):\n",
    "    word_pairs = align_words(true[i], bad[i])\n",
    "    for pair in word_pairs:\n",
    "        if predict_mistaken(pair[1], vocab):\n",
    "            pred = cashed.get(pair[1], get_closest_hybrid_match(pair[1], X, vec)[0][0])\n",
    "            cashed[pair[1]] = pred\n",
    "        else:\n",
    "            pred = pair[1]\n",
    "        \n",
    "            \n",
    "        if pred == pair[0]:\n",
    "            correct += 1\n",
    "        else:\n",
    "            mistakes.append((pair[0], pair[1], pred))\n",
    "        total += 1\n",
    "            \n",
    "        if pair[0] == pair[1]:\n",
    "            total_correct += 1\n",
    "            if pair[0] != pred:\n",
    "                correct_broken += 1\n",
    "        else:\n",
    "            total_mistaken += 1\n",
    "            if pair[0] == pred:\n",
    "                mistaken_fixed += 1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 72,
   "metadata": {
    "scrolled": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "0.8533266633316658\n",
      "0.4704968944099379\n",
      "0.09004249454461927\n"
     ]
    }
   ],
   "source": [
    "print(correct/total)\n",
    "print(mistaken_fixed/total_mistaken)\n",
    "print(correct_broken/total_correct)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "К сожалению лучше не стало. Но возможно дело в том, что в алгоритме Норвига мы учитывали вероятности слов, а тут нет. Попробуйте добавить ранжирование равнозначных по расстоянию редактирования кандидатов по вероятности и оцените качество."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Готовые инструменты"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Есть несколько готовых опечаточников:  \n",
    "1) Hunspell - https://pypi.org/project/hunspell/  \n",
    "2) Jamspell - https://github.com/bakwc/JamSpell#python  \n",
    "3) Яндекс.Спеллер - https://yandex.ru/dev/speller/ (только через API)\n",
    "\n",
    "\n",
    "Если вам понадобится в серьезной задаче исправлять опечатки, то начните с них, а не с алгоритма Норвига."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Для Яндекс Спеллера есть питоновская библиотека, которая упрощает его использование. У него есть некоторые ограничения (10 к запросов в день), но для небольших проектов этого вполне достаточно."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 73,
   "metadata": {
    "scrolled": true
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Collecting pyaspeller\n",
      "  Downloading pyaspeller-2.0.0-py3-none-any.whl (12 kB)\n",
      "Requirement already satisfied: requests<3.0.0,>=2.27.1 in /Users/mnefedov/miniforge3/envs/tf1/lib/python3.8/site-packages (from pyaspeller) (2.28.1)\n",
      "Requirement already satisfied: certifi>=2017.4.17 in /Users/mnefedov/miniforge3/envs/tf1/lib/python3.8/site-packages (from requests<3.0.0,>=2.27.1->pyaspeller) (2022.9.24)\n",
      "Requirement already satisfied: idna<4,>=2.5 in /Users/mnefedov/miniforge3/envs/tf1/lib/python3.8/site-packages (from requests<3.0.0,>=2.27.1->pyaspeller) (3.4)\n",
      "Requirement already satisfied: urllib3<1.27,>=1.21.1 in /Users/mnefedov/miniforge3/envs/tf1/lib/python3.8/site-packages (from requests<3.0.0,>=2.27.1->pyaspeller) (1.26.12)\n",
      "Requirement already satisfied: charset-normalizer<3,>=2 in /Users/mnefedov/miniforge3/envs/tf1/lib/python3.8/site-packages (from requests<3.0.0,>=2.27.1->pyaspeller) (2.1.1)\n",
      "Installing collected packages: pyaspeller\n",
      "Successfully installed pyaspeller-2.0.0\n"
     ]
    }
   ],
   "source": [
    "!pip install pyaspeller"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 76,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "'Для Яндекс Спеллера есть питоновская библиотека, которая упрощает его использование. У него есть некоторые ограничения (10 к запросов в день), но для небольших проектов этого вполне достаточно.'"
      ]
     },
     "execution_count": 76,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# Так можно исправить предложение целиком\n",
    "from pyaspeller import YandexSpeller\n",
    "speller = YandexSpeller()\n",
    "fixed = speller.spelled('Для Яндекс Спеллера есть питоновская библиотека, которая упрощает его использование. У него есть некоторые ограничения (10 к запросов в день), но для небольших проектов этого вполне достаточно.')\n",
    "fixed"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 75,
   "metadata": {},
   "outputs": [
    {
     "name": "stderr",
     "output_type": "stream",
     "text": [
      "/Users/mnefedov/miniforge3/envs/tf1/lib/python3.8/site-packages/pyaspeller/word.py:17: UserWarning: Class Word is deprecated. Use YandexSpeller().spelled(text) instead\n",
      "  warnings.warn(\"Class Word is deprecated. Use YandexSpeller().spelled(text) instead\")\n"
     ]
    },
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "приджлажение False предложение ['предложение', 'придлажение', 'приджложение']\n"
     ]
    }
   ],
   "source": [
    "# А так проверить и исправить отдельное слово\n",
    "from pyaspeller import Word\n",
    "check = Word('приджлажение')\n",
    "print(check.text, check.correct, check.spellsafe, check.variants)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "anaconda-cloud": {},
  "kernelspec": {
   "display_name": "Python 3 (ipykernel)",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.8.14"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 1
}