1. Intro.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Natural Language Processing\n",
    "\n",
    "## Оксана Дереза\n",
    "\n",
    "###  Школа лингвистики НИУ ВШЭ \n",
    "\n",
    "#### oksana.dereza@gmail.com"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Основные задачи\n",
    "* Машинный перевод\n",
    "* Классификация текстов\n",
    "    * Фильтрация спама\n",
    "    * По тональности\n",
    "    * По теме или жанру\n",
    "* Кластеризация текстов\n",
    "* Извлечение информации\n",
    "    * Фактов и событий\n",
    "    * Именованных сущностей (NER)\n",
    "* Вопросно-ответные системы\n",
    "* Суммаризация текстов\n",
    "* Генерация текстов\n",
    "* Распознавание речи\n",
    "* Проверка правописания\n",
    "* Оптическое распознавание символов (впрочем, это больше про компьютерное зрение)\n",
    "\n",
    "### State of the Art\n",
    "* [Сборник SOTA](https://nlpprogress.com/) по разным задачам NLP от Sebastian Ruder\n",
    "* [И еще один, NLPub](https://nlpub.ru/) (много для русского языка)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Основные техники \n",
    "* Уровень символов:\n",
    "    * Токенизация: разбиение текста на слова\n",
    "    * Разбиение текста на предложения\n",
    "* Уровень слов – морфология:\n",
    "    * Разметка частей речи\n",
    "    * Снятие морфологической неоднозначности\n",
    "* Уровень предложений – синтаксис:\n",
    "    * Выделенние именных или глагольных групп (chunking)\n",
    "    * Выделенние семантических ролей\n",
    "    * Деревья составляющих и зависимостей\n",
    "* Уровень смысла – семантика и дискурс:\n",
    "    * Разрешение кореферентных связей\n",
    "    * Выделение синонимов\n",
    "    * Анализ аргументативных связей"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "![pipeline](img/nlp_pipeline.png)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Основные проблемы\n",
    "* Неоднозначность\n",
    "    * Лексическая неоднозначность: *орган, парить, рожки, атлас*\n",
    "    * Морфологическая неоднозначность: *Хранение денег в банке. Что делают белки в клетке?*\n",
    "    * Синтаксическая неоднозначность: *Мужу изменять нельзя. Его удивил простой солдат. Эти типы стали есть в цехе.*\n",
    "* Неологизмы: *печеньки, заинстаграммить, репостнуть, расшарить, биткоины*\n",
    "* Разные варианты написания: *Россия, Российская Федерация, РФ*\n",
    "* Нестандартное написание (в т.ч. орфографические ошибки и опечатки): *каг дила? куптиь телфон*"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Синтаксическая неоднозначность \n",
    "#### I saw a man on the hill with a telescope\n",
    "![синтаксическая неоднозначность](http://78.media.tumblr.com/d6552ff51881937371c94dc18865d711/tumblr_mo1nl6Nt9n1rwewyjo1_400.jpg)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### NLP-библиотеки\n",
    "\n",
    "NLP-библиотеки для питона:\n",
    "* Natural Language Toolkit (NLTK)\n",
    "* Apache OpenNLP\n",
    "* Stanford NLP suite\n",
    "* Gate NLP library\n",
    "* Spacy\n",
    "* Yargy\n",
    "* DeepPavlov\n",
    "* CLTK (для древних языков)\n",
    "* и т.д.\n",
    "\n",
    "Самая старая и известная — NLTK. В NLTK есть не только различные инструменты для обработки текста, но и данные — текстовые корпуса, предобученные модели для анализа тональности и морфологической разметки, списки стоп-слов для разных языков и т.п.\n",
    "\n",
    "* [Учебник по NLTK](https://www.nltk.org/book/) от авторов библиотеки и [тьюториалы](https://github.com/hb20007/hands-on-nltk-tutorial) по решению разных задач NLP с помощью NLTK.\n",
    "* [Документация Spacy](https://spacy.io/)\n",
    "* [Документация Yargy](https://yargy.readthedocs.io/)\n",
    "* [Документация DeepPavlop](http://docs.deeppavlov.ai/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Предобработка текста\n",
    "\n",
    "1. **Токенизация** — самый первый шаг при обработке текста. \n",
    "2. **Нормализация** — приведение к одному регистру, удаляются пунктуации, исправление опечаток и т.д.\n",
    "3. \n",
    "    * **Стемминг** —  выделение псевдоосновы слова.\n",
    "    * **Лемматизация** — приведение слов к словарной (\"начальной\") форме.\n",
    "4. **Удаление стоп-слов** — слов, которые не несут никакой смысловой нагрузки (предлоги, союзы и т.п.) Список зависит от задачи!\n",
    "5. **Part-of-Speech tagging (морфологическая разметка)** — приписывание частеречного тега или цепочки грамматических тегов (полный грамматический разбор) токену.\n",
    "\n",
    "**NB!** Не всегда нужны все этапы, все зависит от задачи!"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Токенизация\n",
    "\n",
    "#### Сколько слов в этом предложении?\n",
    "\n",
    "*На дворе трава, на траве дрова, не руби дрова на траве двора.*\n",
    "\n",
    "* 12 токенов: На, дворе, трава, на, траве, дрова, не, руби, дрова, на, траве, двора\n",
    "* 8 - 9 типов: Н/на, дворе, трава, траве, дрова, не, руби, двора. \n",
    "* 6  лексем: на, не, двор, трава, дрова, рубить\n",
    "\n",
    "\n",
    "### Токен и тип\n",
    "\n",
    "**Тип**  – уникальное слово из текста\n",
    "\n",
    "**Токен**  – тип и его позиция в тексте\n",
    "\n",
    "Объем корпуса измеряется в токенах, объем словаря — в типах или лексемах.\n",
    "\n",
    "### Обозначения \n",
    "$N$ = число токенов\n",
    "\n",
    "$V$ = словарь (все типы)\n",
    "\n",
    "$|V|$ = количество типов в словаре"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Токен ≠ слово\n",
    "\n",
    "Что в данном тексте является токенами?\n",
    "\n",
    "    Продаётся LADA 4x4. ПТС 01.12.2018, куплена 20 января 19 года, 10 000 км пробега. Комплектация полная. Новая в салоне 750 000, отдам за 650 000. Возможен обмен на ВАЗ-2110 или ВАЗ 2109 с вашей доплатой.\n",
    "\n",
    "    * Модификация: 1.6 MT (89 л.с.) \n",
    "    * Владельцев по ПТС: 4+ \n",
    "    * VIN или номер кузова: XTA21104*50****47 \n",
    "    * Мультимедиа и навигация: CD/DVD/Blu-ray \n",
    "    * Шины и диски: 14\" \n",
    "\n",
    "    Краснодар, ул. Миклухо-Маклая, д. 4/5, подъезд 1 \n",
    "\n",
    "    Тел. 8(999)1234567, 8 903 987-65-43, +7 (351) 111 22 33 \n",
    "    \n",
    "    e-mail: ivanov.ivan-61@mail.ru \n",
    "    \n",
    "    И.И. Иванов (Иван Иванович) "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 34,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "['Продаётся', 'LADA', '4x4.', 'ПТС', '01.12.2018,', 'куплена', '20', 'января', '19', 'года,', '10', '000', 'км', 'пробега.', 'Комплектация', 'полная.', 'Новая', 'в', 'салоне', '750', '000,', 'отдам', 'за', '650', '000.', 'Возможен', 'обмен', 'на', 'ВАЗ-2110', 'или', 'ВАЗ', '2109', 'с', 'вашей', 'доплатой.', 'Краснодар,', 'ул.', 'Миклухо-Маклая,', 'д.', '4/5,', 'подьезд', '1', 'Тел.', '8(999)1234567,', '8', '903', '987-65-43,', '+7', '(351)', '111', '22', '33', 'И.И.', 'Иванов', '(Иван', 'Иванович)']\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "56"
      ]
     },
     "execution_count": 34,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# самая банальная токенизация: разбиение по пробелам\n",
    "\n",
    "text = '''\n",
    "Продаётся LADA 4x4. ПТС 01.12.2018, куплена 20 января 19 года, 10 000 км пробега. \n",
    "Комплектация полная. Новая в салоне 750 000, отдам за 650 000. \n",
    "Возможен обмен на ВАЗ-2110 или ВАЗ 2109 с вашей доплатой. \n",
    "Краснодар, ул. Миклухо-Маклая, д. 4/5, подьезд 1 \n",
    "Тел. 8(999)1234567, 8 903 987-65-43, +7 (351) 111 22 33 \n",
    "И.И. Иванов (Иван Иванович) \n",
    "'''\n",
    "\n",
    "tokens = text.split()\n",
    "print(tokens)\n",
    "len(tokens)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 35,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "['\\n', 'Продаётся', 'LADA', '4', 'x', '4', '.', 'ПТС', '01', '.', '12', '.', '2018', ',', 'куплена', '20', 'января', '19', 'года', ',', '10', '000', 'км', 'пробега', '.', '\\n', 'Комплектация', 'полная', '.', 'Новая', 'в', 'салоне', '750', '000', ',', 'отдам', 'за', '650', '000', '.', '\\n', 'Возможен', 'обмен', 'на', 'ВАЗ', '-', '2110', 'или', 'ВАЗ', '2109', 'с', 'вашей', 'доплатой', '.', '\\n', 'Краснодар', ',', 'ул', '.', 'Миклухо', '-', 'Маклая', ',', 'д', '.', '4', '/', '5', ',', 'подьезд', '1', '\\n', 'Тел', '.', '8', '(', '999', ')', '1234567', ',', '8', '903', '987', '-', '65', '-', '43', ',', '+', '7', '(', '351', ')', '111', '22', '33', '\\n', 'И', '.', 'И', '.', 'Иванов', '(', 'Иван', 'Иванович', ')', '\\n']\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "107"
      ]
     },
     "execution_count": 35,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# максимально разбивает\n",
    "from yargy.tokenizer import MorphTokenizer\n",
    "\n",
    "tknzr = MorphTokenizer()\n",
    "tokens = [_.value for _ in tknzr(text)]\n",
    "print(tokens)\n",
    "len(tokens)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "showing info https://raw.githubusercontent.com/nltk/nltk_data/gh-pages/index.xml\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "True"
      ]
     },
     "execution_count": 1,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "import nltk\n",
    "nltk.download()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "В открывшемся окошке нужно выбрать и скачать следующие пакеты:\n",
    "1. Models\n",
    "    * punkt\n",
    "    * snowball_data\n",
    "    * perluniprops\n",
    "    * universal_tagset\n",
    "2. Corpora\n",
    "    * stopwords\n",
    "    * nonbreaking_prefixes\n",
    "    * wordnet"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 36,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "['Продаётся', 'LADA', '4x4', '.', 'ПТС', '01.12.2018', ',', 'куплена', '20', 'января', '19', 'года', ',', '10', '000', 'км', 'пробега', '.', 'Комплектация', 'полная', '.', 'Новая', 'в', 'салоне', '750', '000', ',', 'отдам', 'за', '650', '000', '.', 'Возможен', 'обмен', 'на', 'ВАЗ-2110', 'или', 'ВАЗ', '2109', 'с', 'вашей', 'доплатой', '.', 'Краснодар', ',', 'ул', '.', 'Миклухо-Маклая', ',', 'д', '.', '4/5', ',', 'подьезд', '1', 'Тел', '.', '8', '(', '999', ')', '1234567', ',', '8', '903', '987-65-43', ',', '+7', '(', '351', ')', '111', '22', '33', 'И.И', '.', 'Иванов', '(', 'Иван', 'Иванович', ')']\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "81"
      ]
     },
     "execution_count": 36,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "from nltk.tokenize import word_tokenize, ToktokTokenizer\n",
    "\n",
    "tokens = word_tokenize(text)\n",
    "print(tokens)\n",
    "len(tokens)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 37,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "['Продаётся', 'LADA', '4x4.', 'ПТС', '01.12.2018', ',', 'куплена', '20', 'января', '19', 'года', ',', '10', '000', 'км', 'пробега.', 'Комплектация', 'полная.', 'Новая', 'в', 'салоне', '750', '000', ',', 'отдам', 'за', '650', '000.', 'Возможен', 'обмен', 'на', 'ВАЗ-2110', 'или', 'ВАЗ', '2109', 'с', 'вашей', 'доплатой.', 'Краснодар', ',', 'ул.', 'Миклухо-Маклая', ',', 'д.', '4/5', ',', 'подьезд', '1', 'Тел.', '8(', '999', ')', '1234567', ',', '8', '903', '987-65-43', ',', '+7', '(', '351', ')', '111', '22', '33', 'И.И.', 'Иванов', '(', 'Иван', 'Иванович', ')']\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "71"
      ]
     },
     "execution_count": 37,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "tknzr = ToktokTokenizer()\n",
    "tokens = tknzr.tokenize(text)\n",
    "print(tokens)\n",
    "len(tokens)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "['@remy',\n",
       " 'This',\n",
       " 'is',\n",
       " 'a',\n",
       " 'cooool',\n",
       " '#dummysmiley',\n",
       " ':',\n",
       " ':-)',\n",
       " ':-P',\n",
       " '<3',\n",
       " 'and',\n",
       " 'some',\n",
       " 'arrows',\n",
       " '<',\n",
       " '>',\n",
       " '->',\n",
       " '<--']"
      ]
     },
     "execution_count": 7,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# специальный токенизатор для твитов\n",
    "from nltk.tokenize import TweetTokenizer\n",
    "\n",
    "tknzr = TweetTokenizer()\n",
    "tweet = \"@remy This is a cooool #dummysmiley: :-) :-P <3 and some arrows < > -> <--\"\n",
    "tknzr.tokenize(tweet)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "['Good',\n",
       " 'muffins',\n",
       " 'cost',\n",
       " '$3.88',\n",
       " 'in',\n",
       " 'New',\n",
       " 'York',\n",
       " '.',\n",
       " 'Please',\n",
       " 'buy',\n",
       " 'me',\n",
       " 'two',\n",
       " 'of',\n",
       " 'them',\n",
       " '.',\n",
       " 'Thanks',\n",
       " '.']"
      ]
     },
     "execution_count": 8,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# токенизатор на регулярных выражениях\n",
    "from nltk.tokenize import RegexpTokenizer\n",
    "\n",
    "s = \"Good muffins cost $3.88 in New York.  Please buy me two of them. \\n\\nThanks.\"\n",
    "tknzr = RegexpTokenizer('\\w+|\\$[\\d\\.]+|\\S+')\n",
    "tknzr.tokenize(s)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Сегментация предложений\n",
    "\n",
    "Сегментацию предложений иногда называют **сплиттингом**. \n",
    "\n",
    "Основные признаки — знаки препинания. \"?\", \"!\" как правило однозначны, проблемы возникают с \".\"  Возможное решение: бинарный классификатор для сегментации предложений. Для каждой точки \".\" определить, является ли она концом предложения или нет.\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 39,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "10\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "['\\nПродаётся LADA 4x4.',\n",
       " 'ПТС 01.12.2018, куплена 20 января 19 года, 10 000 км пробега.',\n",
       " 'Комплектация полная.',\n",
       " 'Новая в салоне 750 000, отдам за 650 000.',\n",
       " 'Возможен обмен на ВАЗ-2110 или ВАЗ 2109 с вашей доплатой.',\n",
       " 'Краснодар, ул.',\n",
       " 'Миклухо-Маклая, д.',\n",
       " '4/5, подьезд 1 \\nТел.',\n",
       " '8(999)1234567, 8 903 987-65-43, +7 (351) 111 22 33 \\nИ.И.',\n",
       " 'Иванов (Иван Иванович)']"
      ]
     },
     "execution_count": 39,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "from nltk.tokenize import sent_tokenize\n",
    "\n",
    "sents = sent_tokenize(text)\n",
    "print(len(sents))\n",
    "sents"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 79,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "6\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "['Продаётся LADA 4x4.',\n",
       " 'ПТС 01.12.2018, куплена 20 января 19 года, 10 000 км пробега.',\n",
       " 'Комплектация полная.',\n",
       " 'Новая в салоне 750 000, отдам за 650 000.',\n",
       " 'Возможен обмен на ВАЗ-2110 или ВАЗ 2109 с вашей доплатой.',\n",
       " 'Краснодар, ул. Миклухо-Маклая, д. 4/5, подьезд 1 \\nТел. 8(999)1234567, 8 903 987-65-43, +7 (351) 111 22 33 \\nИ.И. Иванов (Иван Иванович)']"
      ]
     },
     "execution_count": 79,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "from rusenttokenize import ru_sent_tokenize\n",
    "sents = ru_sent_tokenize(text)\n",
    "\n",
    "print(len(sents))\n",
    "sents"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Нормализация\n",
    "\n",
    "### Удаление пунктуации"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 40,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "['Продаётся', 'LADA', '4x4', 'ПТС', '01122018', 'куплена', '20', 'января', '19', 'года', '10', '000', 'км', 'пробега', 'Комплектация', 'полная', 'Новая', 'в', 'салоне', '750', '000', 'отдам', 'за', '650', '000', 'Возможен', 'обмен', 'на', 'ВАЗ-2110', 'или', 'ВАЗ', '2109', 'с', 'вашей', 'доплатой', 'Краснодар', 'ул', 'Миклухо-Маклая', 'д', '45', 'подьезд', '1', 'Тел', '89991234567', '8', '903', '987-65-43', '+7', '351', '111', '22', '33', 'ИИ', 'Иванов', 'Иван', 'Иванович']\n",
      "['Продаётся', 'LADA', '4x4', '', 'ПТС', '01.12.2018', '', 'куплена', '20', 'января', '19', 'года', '', '10', '000', 'км', 'пробега', '', 'Комплектация', 'полная', '', 'Новая', 'в', 'салоне', '750', '000', '', 'отдам', 'за', '650', '000', '', 'Возможен', 'обмен', 'на', 'ВАЗ-2110', 'или', 'ВАЗ', '2109', 'с', 'вашей', 'доплатой', '', 'Краснодар', '', 'ул', '', 'Миклухо-Маклая', '', 'д', '', '4/5', '', 'подьезд', '1', 'Тел', '', '8', '', '999', '', '1234567', '', '8', '903', '987-65-43', '', '+7', '', '351', '', '111', '22', '33', 'И.И', '', 'Иванов', '', 'Иван', 'Иванович', '']\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "False"
      ]
     },
     "execution_count": 40,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# Способ №1\n",
    "import re\n",
    "\n",
    "# набор пунктуационных символов зависит от задачи и текста\n",
    "punct = '!\"#$%&()*+,-./:;<=>?@[\\]^_`{|}~„“«»†*—/\\-‘’'\n",
    "clean_text = re.sub(punct, r'', text)\n",
    "print(clean_text.split())\n",
    "\n",
    "# Способ №2\n",
    "clean_words = [w.strip(punct) for w in word_tokenize(text)]\n",
    "print(clean_words)\n",
    "\n",
    "clean_words == clean_text"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Преобразование регистра"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 41,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "['продаётся', 'lada', '4x4', 'птс', '01.12.2018', 'куплена', '20', 'января', '19', 'года', '10', '000', 'км', 'пробега', 'комплектация', 'полная', 'новая', 'в', 'салоне', '750', '000', 'отдам', 'за', '650', '000', 'возможен', 'обмен', 'на', 'ваз-2110', 'или', 'ваз', '2109', 'с', 'вашей', 'доплатой', 'краснодар', 'ул', 'миклухо-маклая', 'д', '4/5', 'подьезд', '1', 'тел', '8', '999', '1234567', '8', '903', '987-65-43', '+7', '351', '111', '22', '33', 'и.и', 'иванов', 'иван', 'иванович']\n"
     ]
    }
   ],
   "source": [
    "clean_words = [w.lower() for w in clean_words if w != '']\n",
    "print(clean_words)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Исправление опечаток\n",
    "\n",
    "Как правило, спеллчекеры основаны на **расстоянии Левенштейна** (редакционное расстояние, edit distance). Это минимальное количество операций вставки одного символа, удаления одного символа и замены одного символа на другой, необходимых для превращения одной строки в другую. Модификация этого алгоритма — расстояние Дамерау-Левенштейна — включает также операцию перестановки символов.\n",
    "\n",
    "* [Простейший спеллчекер Норвига](https://norvig.com/spell-correct.html)\n",
    "* [Hunspell](http://hunspell.github.io/)\n",
    "* [JamSpell](https://github.com/bakwc/JamSpell)\n",
    "* [Yandex Speller API](https://tech.yandex.ru/speller/doc/dg/concepts/api-overview-docpage/)\n",
    "* etc. etc."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Стоп-слова\n",
    "\n",
    "**Стоп-слова** — высокочастотные слова, которые не дают нам никакой информации о конкретном тексте. Они составляют верхушку частотного списка в любом языке. Набор стоп-слов не универсален, он будет зависеть от вашей задачи!\n",
    "\n",
    "В NLTK есть готовые списки стоп-слов для многих языков. Хороший стписок стоп-слов есть у яндекс.директа, на его основе составлен мой [список стоп-слов для анализа художественных текстов](./data/rus_stopwords.txt)."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 21,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "['arabic',\n",
       " 'azerbaijani',\n",
       " 'danish',\n",
       " 'dutch',\n",
       " 'english',\n",
       " 'finnish',\n",
       " 'french',\n",
       " 'german',\n",
       " 'greek',\n",
       " 'hungarian',\n",
       " 'indonesian',\n",
       " 'italian',\n",
       " 'kazakh',\n",
       " 'nepali',\n",
       " 'norwegian',\n",
       " 'portuguese',\n",
       " 'romanian',\n",
       " 'russian',\n",
       " 'spanish',\n",
       " 'swedish',\n",
       " 'turkish']"
      ]
     },
     "execution_count": 21,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "from nltk.corpus import stopwords\n",
    "\n",
    "# смотрим, какие языки есть\n",
    "stopwords.fileids()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 42,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "['и', 'в', 'во', 'не', 'что', 'он', 'на', 'я', 'с', 'со', 'как', 'а', 'то', 'все', 'она', 'так', 'его', 'но', 'да', 'ты', 'к', 'у', 'же', 'вы', 'за', 'бы', 'по', 'только', 'ее', 'мне', 'было', 'вот', 'от', 'меня', 'еще', 'нет', 'о', 'из', 'ему', 'теперь', 'когда', 'даже', 'ну', 'вдруг', 'ли', 'если', 'уже', 'или', 'ни', 'быть', 'был', 'него', 'до', 'вас', 'нибудь', 'опять', 'уж', 'вам', 'ведь', 'там', 'потом', 'себя', 'ничего', 'ей', 'может', 'они', 'тут', 'где', 'есть', 'надо', 'ней', 'для', 'мы', 'тебя', 'их', 'чем', 'была', 'сам', 'чтоб', 'без', 'будто', 'чего', 'раз', 'тоже', 'себе', 'под', 'будет', 'ж', 'тогда', 'кто', 'этот', 'того', 'потому', 'этого', 'какой', 'совсем', 'ним', 'здесь', 'этом', 'один', 'почти', 'мой', 'тем', 'чтобы', 'нее', 'сейчас', 'были', 'куда', 'зачем', 'всех', 'никогда', 'можно', 'при', 'наконец', 'два', 'об', 'другой', 'хоть', 'после', 'над', 'больше', 'тот', 'через', 'эти', 'нас', 'про', 'всего', 'них', 'какая', 'много', 'разве', 'три', 'эту', 'моя', 'впрочем', 'хорошо', 'свою', 'этой', 'перед', 'иногда', 'лучше', 'чуть', 'том', 'нельзя', 'такой', 'им', 'более', 'всегда', 'конечно', 'всю', 'между']\n"
     ]
    }
   ],
   "source": [
    "sw = stopwords.words('russian')\n",
    "print(sw)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 43,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "в\n",
      "за\n",
      "на\n",
      "или\n",
      "с\n",
      "['продаётся', 'lada', '4x4', 'птс', '01.12.2018', 'куплена', '20', 'января', '19', 'года', '10', '000', 'км', 'пробега', 'комплектация', 'полная', 'новая', None, 'салоне', '750', '000', 'отдам', None, '650', '000', 'возможен', 'обмен', None, 'ваз-2110', None, 'ваз', '2109', None, 'вашей', 'доплатой', 'краснодар', 'ул', 'миклухо-маклая', 'д', '4/5', 'подьезд', '1', 'тел', '8', '999', '1234567', '8', '903', '987-65-43', '+7', '351', '111', '22', '33', 'и.и', 'иванов', 'иван', 'иванович']\n"
     ]
    }
   ],
   "source": [
    "print([w if w not in sw else print(w) for w in clean_words])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Стемминг\n",
    "\n",
    "**Стемминг** — отсечение от слова окончаний и суффиксов, чтобы оставшаяся часть, называемая stem, была одинаковой для всех грамматических форм слова. Стем необязательно совпадает с морфлогической основой слова. Одинаковый стем может получиться и не у однокоренных слов и наоборот — в этом проблема стемминга. \n",
    "\n",
    "* 1-ый вид ошибки: белый, белка, белье $\\implies$  бел\n",
    "\n",
    "* 2-ой вид ошибки: трудность, трудный $\\implies$  трудност, труд \n",
    "\n",
    "* 3-ий вид ошибки: быстрый, быстрее $\\implies$  быст, побыстрее $\\implies$  побыст\n",
    "\n",
    "Самый простой алгоритм, алгоритм Портера, состоит из 5 циклов команд, на каждом цикле – операция удаления / замены суффикса. Возможны вероятностные расширения алгоритма.\n",
    "\n",
    "### Snowball stemmer\n",
    "Улучшенный вариант стеммера Портера; в отличие от него умеет работать не только с английским текстом."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 33,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "('arabic',\n",
       " 'danish',\n",
       " 'dutch',\n",
       " 'english',\n",
       " 'finnish',\n",
       " 'french',\n",
       " 'german',\n",
       " 'hungarian',\n",
       " 'italian',\n",
       " 'norwegian',\n",
       " 'porter',\n",
       " 'portuguese',\n",
       " 'romanian',\n",
       " 'russian',\n",
       " 'spanish',\n",
       " 'swedish')"
      ]
     },
     "execution_count": 33,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "from nltk.stem.snowball import SnowballStemmer\n",
    "\n",
    "SnowballStemmer.languages  "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 54,
   "metadata": {},
   "outputs": [],
   "source": [
    "poem = '''\n",
    "По морям, играя, носится\n",
    "с миноносцем миноносица.\n",
    "Льнет, как будто к меду осочка,\n",
    "к миноносцу миноносочка.\n",
    "И конца б не довелось ему,\n",
    "благодушью миноносьему.\n",
    "Вдруг прожектор, вздев на нос очки,\n",
    "впился в спину миноносочки.\n",
    "Как взревет медноголосина:\n",
    "Р-р-р-астакая миноносина!\n",
    "'''\n",
    "\n",
    "words = [w.strip(punct).lower() for w in word_tokenize(poem)]\n",
    "words = [w for w in words if w not in sw and w != '']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 55,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "морям: мор\n",
      "играя: игр\n",
      "носится: нос\n",
      "миноносцем: миноносц\n",
      "миноносица: миноносиц\n",
      "льнет: льнет\n",
      "меду: мед\n",
      "осочка: осочк\n",
      "миноносцу: миноносц\n",
      "миноносочка: миноносочк\n",
      "конца: конц\n",
      "б: б\n",
      "довелось: довел\n",
      "благодушью: благодуш\n",
      "миноносьему: минонос\n",
      "прожектор: прожектор\n",
      "вздев: вздев\n",
      "нос: нос\n",
      "очки: очк\n",
      "впился: впил\n",
      "спину: спин\n",
      "миноносочки: миноносочк\n",
      "взревет: взревет\n",
      "медноголосина: медноголосин\n",
      "р-р-р-астакая: р-р-р-астак\n",
      "миноносина: миноносин\n"
     ]
    }
   ],
   "source": [
    "snowball = SnowballStemmer(\"russian\")\n",
    "\n",
    "for w in words:\n",
    "    print(\"%s: %s\" % (w, snowball.stem(w)))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Морфологический анализ\n",
    "\n",
    "Задачи морфологического анализа:\n",
    "\n",
    "* Разбор слова — определение нормальной формы (леммы), основы (стема) и грамматических характеристик слова\n",
    "* Синтез словоформы — генерация словоформы по заданным грамматическим характеристикам из леммы\n",
    "\n",
    "Морфологический анализ — не самая сильная сторона NLTK.  Для этих задач лучше использовать `pymorphy2` и `pymystem3` для русского языка и, например, `Spacy` для европейских.\n",
    "\n",
    "## Лемматизация\n",
    "\n",
    "**Лемматизация** — процесс приведения словоформы к лемме, т.е. нормальной (словарной) форме. Это более сложная задача, чем стемминг, но и результаты дает гораздо более осмысленные, особенно для языков с богатой морфологией.\n",
    "\n",
    "* кошке, кошку, кошкам, кошкой $\\implies$ кошка\n",
    "* бежал, бежит, бегу $\\implies$  бежать\n",
    "* белому, белым, белыми $\\implies$ белый\n",
    "\n",
    "## POS-tagging\n",
    "\n",
    "**Частеречная разметка**, или **POS-tagging** _(part of speech tagging)_ —  определение части речи и грамматических характеристик слов в тексте (корпусе) с приписыванием им соответствующих тегов.\n",
    "\n",
    "Для большинства слов возможно несколько разборов (т.е. несколько разных лемм, несколько разных частей речи и т.п.). Теггер генерирует  все варианты, ранжирует их по вероятности и по умолчанию выдает наиболее вероятный. Выбор одного разбора из нескольких называется **снятием омонимии**, или **дизамбигуацией**.\n",
    "\n",
    "### Наборы тегов\n",
    "\n",
    "Существует множество наборов грамматических тегов, или тегсетов:\n",
    "* НКРЯ\n",
    "* Mystem\n",
    "* UPenn\n",
    "* OpenCorpora (его использует pymorphy2)\n",
    "* Universal Dependencies\n",
    "* ...\n",
    "\n",
    "Есть даже [библиотека](https://github.com/kmike/russian-tagsets) для преобразования тегов из одной системы в другую для русского языка, `russian-tagsets`. Но важно помнить, что любое такое преобразование будет с потерями! \n",
    "\n",
    "На данный момент стандартом является **Universal Dependencies**. Подробнее про проект можно почитать [вот тут](http://universaldependencies.org/), а про теги — [вот тут](http://universaldependencies.org/u/pos/). Вот список основных (частереных) тегов UD:\n",
    "\n",
    "* ADJ: adjective\n",
    "* ADP: adposition\n",
    "* ADV: adverb\n",
    "* AUX: auxiliary\n",
    "* CCONJ: coordinating conjunction\n",
    "* DET: determiner\n",
    "* INTJ: interjection\n",
    "* NOUN: noun\n",
    "* NUM: numeral\n",
    "* PART: particle\n",
    "* PRON: pronoun\n",
    "* PROPN: proper noun\n",
    "* PUNCT: punctuation\n",
    "* SCONJ: subordinating conjunction\n",
    "* SYM: symbol\n",
    "* VERB: verb\n",
    "* X: other\n",
    "\n",
    "### pymystem3\n",
    "\n",
    "**pymystem3** — это питоновская обертка для яндексовского морфологичекого анализатора Mystem. Его можно скачать отдельно и использовать из консоли.\n",
    "\n",
    "* [Документация Mystem](https://tech.yandex.ru/mystem/doc/index-docpage/)\n",
    "* [Документация pymystem3](http://pythonhosted.org/pymystem3/)\n",
    "\n",
    "Инициализируем Mystem c дефолтными параметрами. А вообще параметры есть такие:\n",
    "* mystem_bin - путь к `mystem`, если их несколько\n",
    "* grammar_info - нужна ли грамматическая информация или только леммы (по дефолту нужна)\n",
    "* disambiguation - нужно ли снятие омонимии - дизамбигуация (по дефолту нужна)\n",
    "* entire_input - нужно ли сохранять в выводе все (пробелы всякие, например), или можно выкинуть (по дефолту оставляется все)\n",
    "\n",
    "Методы Mystem принимают строку, токенизатор вшит внутри. Можно, конечно, и пословно анализировать, но тогда он не сможет учитывать контекст."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 59,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "['море', ' ', 'играть', ' ', 'носиться', ' ', 'миноносец', ' ', 'миноносица', ' ', 'льнуть', ' ', 'мед', ' ', 'осочка', ' ', 'миноносец', ' ', 'миноносочек', ' ', 'конец', ' ', 'б', ' ', 'доводиться', ' ', 'благодушие', ' ', 'миноносий', ' ', 'прожектор', ' ', 'вздевать', ' ', 'нос', ' ', 'очки', ' ', 'впиваться', ' ', 'спина', ' ', 'миноносочек', ' ', 'взреветь', ' ', 'медноголосина', ' ', 'р', '-', 'р', '-', 'р', '-', 'астакать', ' ', 'миноносина', '\\n']\n"
     ]
    }
   ],
   "source": [
    "from pymystem3 import Mystem\n",
    "\n",
    "m = Mystem()\n",
    "lemmas = m.lemmatize(' '.join(words))\n",
    "print(lemmas)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 67,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[{'text': '\\n'},\n",
       " {'analysis': [{'lex': 'по', 'wt': 1, 'gr': 'PR='}], 'text': 'По'},\n",
       " {'text': ' '},\n",
       " {'analysis': [{'lex': 'море', 'wt': 1, 'gr': 'S,сред,неод=дат,мн'}],\n",
       "  'text': 'морям'},\n",
       " {'text': ', '},\n",
       " {'analysis': [{'lex': 'играть', 'wt': 1, 'gr': 'V,несов,пе=непрош,деепр'}],\n",
       "  'text': 'играя'},\n",
       " {'text': ', '},\n",
       " {'analysis': [{'lex': 'носиться',\n",
       "    'wt': 1,\n",
       "    'gr': 'V,несов,нп=непрош,ед,изъяв,3-л'}],\n",
       "  'text': 'носится'},\n",
       " {'text': '\\n'},\n",
       " {'analysis': [{'lex': 'с', 'wt': 0.9999778271, 'gr': 'PR='}], 'text': 'с'}]"
      ]
     },
     "execution_count": 67,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "parsed = m.analyze(poem)\n",
    "parsed[:10]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 69,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "По PR\n",
      "морям S\n",
      "играя V\n",
      "носится V\n",
      "с PR\n",
      "миноносцем S\n",
      "миноносица S\n",
      "Льнет V\n",
      "как ADVPRO\n"
     ]
    }
   ],
   "source": [
    "# как достать части речи\n",
    "\n",
    "for word in parsed[:20]:\n",
    "    if 'analysis' in word:\n",
    "        gr = word['analysis'][0]['gr']\n",
    "        pos = gr.split('=')[0].split(',')[0]\n",
    "        print(word['text'], pos)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "###  pymorphy2\n",
    "\n",
    "**pymorphy2** — это полноценный морфологический анализатор, целиком написанный на Python. Он также умеет ставить слова в нужную форму (спрягать и склонять). Оба они могут работать с незнакомыми словами (out-of-vocabulary words, OOV).\n",
    "\n",
    "[Документация pymorphy2](https://pymorphy2.readthedocs.io/en/latest/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 72,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[Parse(word='стали', tag=OpencorporaTag('VERB,perf,intr plur,past,indc'), normal_form='стать', score=0.984662, methods_stack=((<DictionaryAnalyzer>, 'стали', 904, 4),)),\n",
       " Parse(word='стали', tag=OpencorporaTag('NOUN,inan,femn sing,gent'), normal_form='сталь', score=0.003067, methods_stack=((<DictionaryAnalyzer>, 'стали', 13, 1),)),\n",
       " Parse(word='стали', tag=OpencorporaTag('NOUN,inan,femn sing,datv'), normal_form='сталь', score=0.003067, methods_stack=((<DictionaryAnalyzer>, 'стали', 13, 2),)),\n",
       " Parse(word='стали', tag=OpencorporaTag('NOUN,inan,femn sing,loct'), normal_form='сталь', score=0.003067, methods_stack=((<DictionaryAnalyzer>, 'стали', 13, 5),)),\n",
       " Parse(word='стали', tag=OpencorporaTag('NOUN,inan,femn plur,nomn'), normal_form='сталь', score=0.003067, methods_stack=((<DictionaryAnalyzer>, 'стали', 13, 6),)),\n",
       " Parse(word='стали', tag=OpencorporaTag('NOUN,inan,femn plur,accs'), normal_form='сталь', score=0.003067, methods_stack=((<DictionaryAnalyzer>, 'стали', 13, 9),))]"
      ]
     },
     "execution_count": 72,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "from pymorphy2 import MorphAnalyzer\n",
    "\n",
    "morph = MorphAnalyzer()\n",
    "p = morph.parse('стали')\n",
    "p"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 73,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Слово: стали\n",
      "Тэг: VERB,perf,intr plur,past,indc\n",
      "Лемма: стать\n",
      "Вероятность: 0.984662\n"
     ]
    }
   ],
   "source": [
    "first = p[0]  # первый разбор\n",
    "print('Слово:', first.word)\n",
    "print('Тэг:', first.tag)\n",
    "print('Лемма:', first.normal_form)\n",
    "print('Вероятность:', first.score)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Из каждого тега можно достать более дробную информацию. Если граммема есть в разборе, то вернется ее значение, если ее нет, то вернется None. [Список граммем](https://pymorphy2.readthedocs.io/en/latest/user/grammemes.html)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 76,
   "metadata": {},
   "outputs": [],
   "source": [
    "first.normalized        # лемма\n",
    "first.tag.POS           # Part of Speech, часть речи\n",
    "first.tag.animacy       # одушевленность\n",
    "first.tag.aspect        # вид: совершенный или несовершенный\n",
    "first.tag.case          # падеж\n",
    "first.tag.gender        # род (мужской, женский, средний)\n",
    "first.tag.involvement   # включенность говорящего в действие\n",
    "first.tag.mood          # наклонение (повелительное, изъявительное)\n",
    "first.tag.number        # число (единственное, множественное)\n",
    "first.tag.person        # лицо (1, 2, 3)\n",
    "first.tag.tense         # время (настоящее, прошедшее, будущее)\n",
    "first.tag.transitivity  # переходность (переходный, непереходный)\n",
    "first.tag.voice         # залог (действительный, страдательный)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 77,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Parse(word='стать', tag=OpencorporaTag('INFN,perf,intr'), normal_form='стать', score=1.0, methods_stack=((<DictionaryAnalyzer>, 'стать', 904, 0),))\n",
      "VERB\n",
      "perf\n",
      "None\n"
     ]
    }
   ],
   "source": [
    "print(first.normalized)      \n",
    "print(first.tag.POS)\n",
    "print(first.tag.aspect)\n",
    "print(first.tag.case)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Частотность\n",
    "Многие компьтерные методы анализа текста основаны на статистике — в нашем случае это частотность символов / словоформ / слов / биграмм / триграмм / частей речи и т.д., ее отношение к длине текста, средняя длина текстов и т.д.\n",
    "\n",
    "Зачем нам знать частотность слов в тексте? Например, она говорит о том, какие слова наиболее характеры для того или иного текста. Сравнивая частотные слова в разных текстах можно определить степень их близости, классифицировать по жанру, теме и т.п., а также выявить явления, характерные для языка в целом. \n",
    "\n",
    "**Частотный словарь русского языка**, составленный на основе [НКРЯ](http://ruscorpora.ru/search-main.html) О.Н. Ляшевской и С.А. Шаровым, можно найти [вот тут](http://dict.ruslang.ru/freq.php).\n",
    "\n",
    "**Абсолютная частота слова** — это количество употреблений слова в тексте. Она не очень показательна, т.к. тексты различаются по длине и тематике. Например, если мы захотим узнать, кто популярнее: котики или пёсики, и возьмем для анализа один длинный текст про котиков и один короткий текст про пёсиков, то слово \"котик\", вероятно, окажется частотнее. А если наоборот — то частотнее будет \"пёсик\", и это никак не поможет нам ответить на поставленный вопрос, или - что ещё хуже — приведёт к ложным выводам.\n",
    "\n",
    "**Относительная частота слова** — это отношение его абсолютной частоты к какой-нибудь другой величине, например, к длине текста. Существуют разные способы подсчета относительной частоты, чаще всего используется **ipm** *(items per million).* Как следует из названия, это отношение абсолютной частоты какого-либо элемента к объему корпуса, умноженное на миллион.\n",
    "\n",
    "$$ ipm_{word} = \\dfrac{f_{word}}V_{corpus} \\        \\times \\  1,000,000 $$ \n",
    "\n",
    "Например, если текст состоит из 500 слов, и слово \"котик\" встречается там 50 раз, то \n",
    "\n",
    "$$ ipm_{kotik} = \\dfrac{50}{500} \\       \\times \\  1,000,000 \\     = 100,000 $$ \n",
    "\n",
    "\n",
    "### Закон Ципфа\n",
    "\n",
    "**Закон Ципфа** («ранг—частота») — эмпирическая закономерность распределения частоты слов естественного языка: если все слова языка (или просто достаточно длинного текста) упорядочить по убыванию частоты их использования, то частота n-го слова в таком списке окажется приблизительно обратно пропорциональной его порядковому номеру n (т.н. рангу этого слова). Например, второе по используемости слово встречается примерно в два раза реже, чем первое, третье — в три раза реже, чем первое, и т.д.\n",
    "\n",
    "$f = \\frac{a}{r}$\n",
    "\n",
    "$f$ – частота типа, $r$  – ранг типа, $a$  – параметр, для славянских языков – около 0.07\n",
    "\n",
    "![zipf](https://i.pics.livejournal.com/eponim2008/17443609/234916/234916_original.jpg)\n",
    "\n",
    "Закон назван именем американского лингвиста Джорджа Ципфа (правда, популяризировал он данную закономерность не для лингвистических данных, а для описания распределения экономических сил и социального статуса). Если закон Ципфа соблюдается — значит, перед вами нормальный текст на естественном языке. Если нет, то что-то с ним не так. \n",
    "\n",
    "### Закон Хипса\n",
    "\n",
    "**Закон Хипса** — эмпирическая закономерность в лингвистике, описывающая распределение числа уникальных слов в документе (или наборе документов) как функцию от его длины. C увеличением длины текста (количества токенов), количество типов увеличивается сдедующим образом:\n",
    "\n",
    "$|V| = K*N^b$\n",
    "\n",
    "$N$  –  число токенов, $|V|$  – количество типов в словаре, $K, b$  –  свободные параметры (определяются эмпирически), обычно $K \\in [10,100], b \\in [0.4, 0.6]$\n",
    "\n",
    "![heaps](http://nordbotten.com/ADM/ADM_book/figures/F4-5_Heaps.gif)\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## N-граммы\n",
    "\n",
    "\n",
    "**N-граммы** — это сочетания из N элементов (слов, символов), идущих друг за другом. Одиночные элементы называются униграммами, сочетания из двух элементов — биграммами, из трёх — триграммами, а дальше 4-граммы, 5-граммы и т.д\n",
    "\n",
    "![ngrams](img/ngrams.png)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Полезные ссылки\n",
    "\n",
    "Вообще-то по конспекту разбросано очень много полезных ссылок, но этих еще не было. :)\n",
    "\n",
    "### Корпусная лингвистика\n",
    "\n",
    "Все написано для первокурсников, с картинками и примерами про котиков.\n",
    "\n",
    "* [Про работу с НКРЯ](https://ancatmara.gitbooks.io/digital-literacy-for-sfl/content/seminar-6.html) \n",
    "* [Корпусные приложения](https://ancatmara.gitbooks.io/digital-literacy-for-sfl/content/seminar-7.html): AntConc, Google Ngrams, SketchEngine\n",
    "* [Корпусные приложения](https://github.com/ancatmara/DL-SFL-2019/blob/master/seminar-10.md): Voyant Tools\n",
    "\n",
    "\n",
    "### Python для лингвистов\n",
    "\n",
    "* [Python для гуманитариев](https://github.com/ancatmara/python-for-dh) (с нуля)\n",
    "* [Для 2 курса бакалавров](https://github.com/ancatmara/learnpython2018) программы \"Компьютерная лингвистика\" НИУ ВШЭ\n",
    "* [Общеуниверситетский факультатив по Python](http://math-info.hse.ru/2015-16/%D0%9F%D1%80%D0%BE%D0%B3%D1%80%D0%B0%D0%BC%D0%BC%D0%B8%D1%80%D0%BE%D0%B2%D0%B0%D0%BD%D0%B8%D0%B5_%D0%BD%D0%B0_%D1%8F%D0%B7%D1%8B%D0%BA%D0%B5_Python_%D0%B4%D0%BB%D1%8F_%D1%81%D0%B1%D0%BE%D1%80%D0%B0_%D0%B8_%D0%B0%D0%BD%D0%B0%D0%BB%D0%B8%D0%B7%D0%B0_%D0%B4%D0%B0%D0%BD%D0%BD%D1%8B%D1%85#.D0.9C.D0.B0.D1.82.D0.B5.D1.80.D0.B8.D0.B0.D0.BB.D1.8B) от Ильи Щурова (НИУ ВШЭ)\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Задание\n",
    "\n",
    "Скачать текст [\"Капитанской дочки\"](https://www.dropbox.com/s/aky2md6724r3yww/%D0%BA%D0%B0%D0%BF%D0%B8%D1%82%D0%B0%D0%BD%D1%81%D0%BA%D0%B0%D1%8F%20%D0%B4%D0%BE%D1%87%D0%BA%D0%B0.txt?dl=0)\n",
    "\n",
    "1. Найти длину текста в токенах, типах и леммах (после удаления пунктуации).\n",
    "2. Проверить, соблюдается ли закон Ципфа и построить диаграмму с 20 самыми частотными словами (после удаления стоп-слов).\n",
    "3. Найти среднюю длину предложения.\n",
    "4. Найти самую частотную часть речи до удаления стоп-слов и после удаления. Постороить графики частотности частей речи. "
   ]
  }
 ],
 "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.6.7"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}