Общий привет.
Недавно, для шлифовки морфологического словаря, способного (предположительно) генерировать все возможные формы слова из инфинитива — мне понадобился достаточно объемный частотный словарь русского языка. Частотный словарь — вещь очень простая, слова в нем упорядочены по частоте, с которой они встречаются в анализируемом тексте.
Задачка, казалось бы весьма простая и наверняка решается при изучении программирования в первых рядах. Но для анализа такой громоздкой библиотеки, а используемая мной библиотека простирается на 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 мб/сек.
Теперь можно использовать полученные данные для доработки моего морфологического словарика, а заполучив словарик можно будет улучшить «частотный анализатор», т.к. появится возможность группировки однокоренных слов. Кроме того, доработки требует работа «частотного анализатора» с различными кодировками и т.п. Далее — синтаксический анализ предложения. В конечном итоге хочу заполучить сколь-нибудь адекватную семантическую сеть.
Несмотря на то, что мой «отчет» затрагивает как тему программирования, так и лингвистику — прошу не винить меня за неточности в написании (особенно пунктуации) или не самое гладкое решение задачи, но прошу указать на эти ошибки или предлагать более изящные решения, я буду рад.
Всем спасибо.
Автор: CoruNethron
