Pull to refresh

Создание частотного словаря на основе анализа библиотеки художественной литературы

Reading time 4 min
Views 8.5K
Общий привет.

Недавно, для шлифовки морфологического словаря, способного (предположительно) генерировать все возможные формы слова из инфинитива — мне понадобился достаточно объемный частотный словарь русского языка. Частотный словарь — вещь очень простая, слова в нем упорядочены по частоте, с которой они встречаются в анализируемом тексте.

Задачка, казалось бы весьма простая и наверняка решается при изучении программирования в первых рядах. Но для анализа такой громоздкой библиотеки, а используемая мной библиотека простирается на 157 гектаров, средств среднего домашнего компьютера хватает с натягом. Если сказать точнее, то библиотека хранится в пятидесяти zip архивах по 0.5 — 2 Гб, в каждом из которых 20-30 тыс. произведений в формате fb2. В сжатом виде весит она 60 Гб.

Решалась задачка на языке c#. Результат нужно получить за адекватное время, в качестве которого я выбрал не более 8 часов, чтобы можно было запустить исполнение вечером и получить результат утром.

Поиск решения

Массив

Самый очевидный метод решения, что называется «в лоб» — два массива, в первом — слова, во втором — число. Встретив новое слово, добавляем его в первый массив, если оно там отсутствует или прибавляем единичку к индексу во втором массиве, если нашли слово в первом. Опробовав данный вариант я незамедлительно в нем разочаровался, по прошествии нескольких часов программа скрипя ползла по первой половине первого — же архива. Любой профессиональный программист, наверняка уже смеется над таким подходом. Однако, признаюсь — я даже не предполагал что меня ждёт подвох.

Тогда я стал искать — где же то самое узкое место, которое не дает программе вздохнуть. Узкое место оказалось в моменте добавления нового слова. Чтобы сохранить массив упорядоченным — слово приходится вставлять где-то посередине, а иногда и в самое начало. Для этого приходится сдвигать каждый элемент массива расположенный правее выбранной позиции вправо. Когда речь идёт о миллионах слов — это занятие становится очень утомительным для процессора и он мстит, откладывая завершение программы на недели вперед.

Упорядоченный список

Пришлось искать такую структуру данных, которая позволит добавить каждый элемент просто в конец оной структуры, но позволит в то-же время их упорядочить. Тут-же я наткнулся на упорядоченные списки. В ячейке упорядоченного списка хранится сам кусочек данных и указатель на другую ячейку. Все превосходно, мы просто добавляем новое слово и меняем 2 индекса, индекс предыдущего слова, указывающий на данное и индекс данного слова, указывающие на следующее. Но, вот незадача, поиск в таком списке весьма вычислительно требователен. Если в упорядоченном массиве мы могли начинать поиск с середины и делить его пополам за одну итерацию, то в упорядоченном списке приходится карабкаться по указателям от одного к другому, как по ниточке, пока не найдем нужное место во всем клубке. Пробовать этот вариант я не стал, наученный предыдущим провалом я сразу пронюхал засаду.

Бинарное дерево поиска

Следующую структуру данных я нашел лишь через несколько часов. Мне попались бинарные деревья поиска. Немного почитав о различных вариантах я остановился на самобалансирующемся AVL дереве, созданном, кстати советскими учёными Адельсон-Вельским Георгием Максимовичем и Ландисом Евгением Михайловичем, и унаследовавшем от их фамилий своё название.

Структура бинарного дерева схожа с упорядоченным списком, но каждый элемент, кроме нескольких конечных (т.н. листьев) ссылается на два элемента. Корневой элемент — это тот, что находился бы в середине упорядоченного массива. Он ссылается на элемент меньший (левый) и больший (правый), кроме того — гарантированно, что все элементы левой ветви будут меньше данного, а все элементы правой ветви — больше. Рассмотрев левый или правый элемент, к которому мы пришли — мы увидим ту-же иерархию, он так-же ссылается на два элемента, левая ветвь так-же меньше, правая — больше. Чтобы понять способ балансировки такого дерева — лучше всего прочитать соответствующую статью, например тут: АВЛ-деревья. Важно заметить, что двоичное дерево поиска полностью удовлетворило моим требованиям. Быстрый поиск и быстрое добавление нового элемента.

Результат


В итоге, потратив еще несколько часов на оптимизацию я получил многопоточное приложение, которое распаковывает архив в оперативную память, считает частоту различных слов и с помощью AVL дерева обрабатывает полученные данные.

Вот несколько строк по результатам работы программы, слева — слово, справа — частота. Это самые часто встречаемые слова различной длины:

  • я 34361402
  • а 36192092
  • с 52479822
  • в 126422246
  • и 158458227


  • по 23978868
  • он 32602346
  • то 42163693
  • на 83001625
  • не 97183097


  • все 19576264
  • это 21318968
  • его 27719894
  • как 30228770
  • что 63106338


  • даже 6789652
  • была 6832494
  • если 7750404
  • меня 12381969
  • было 15450767


  • может 5455561
  • очень 5477013
  • время 6317279
  • когда 9788599
  • чтобы 9987225


  • человеконенавистничества 296
  • высококвалифицированного 350
  • высокопревосходительству 384
  • высокопревосходительства 489
  • высокопревосходительство 3739


  • человеконенавистнического 46
  • человеконенавистничеством 52
  • частнопредпринимательской 60
  • высокопревосходительством 91
  • националсоциалистическата 96


В общем было получено 9.5 млн. слов, анализ длился 8482 сек., средняя скорость обработки распакованного текста — 18.57 мб/сек.

Теперь можно использовать полученные данные для доработки моего морфологического словарика, а заполучив словарик можно будет улучшить «частотный анализатор», т.к. появится возможность группировки однокоренных слов. Кроме того, доработки требует работа «частотного анализатора» с различными кодировками и т.п. Далее — синтаксический анализ предложения. В конечном итоге хочу заполучить сколь-нибудь адекватную семантическую сеть.

Несмотря на то, что мой «отчет» затрагивает как тему программирования, так и лингвистику — прошу не винить меня за неточности в написании (особенно пунктуации) или не самое гладкое решение задачи, но прошу указать на эти ошибки или предлагать более изящные решения, я буду рад.

Всем спасибо.
Tags:
Hubs:
+12
Comments 12
Comments Comments 12

Articles