Общий привет. Недавно для полировки морфологического словаря, способного (предположительно) образовывать все возможные формы слова из инфинитива, мне понадобился довольно большой частотный словарь русского языка.
Частотный словарь — очень простая вещь; слова в нем упорядочены по частоте их появления в анализируемом тексте.
Проблема кажется очень простой и, безусловно, может быть решена путем изучения программирования на переднем крае.
Но для анализа такой громоздкой библиотеки, а площадь библиотеки, которую я использую, превышает 157 гектаров, ресурсов среднестатистического домашнего компьютера едва хватает. Если быть точнее, то библиотека хранится в пятидесяти zip-архивах по 0,5 – 2 ГБ, каждый из которых содержит 20–30 тысяч произведений в формате fb2. В сжатом виде весит 60 ГБ.
Проблема была решена на C#.
Результат должен быть получен в адекватное время, для которого я выбрал не более 8 часов, чтобы можно было запустить выполнение вечером и получить результат утром.
Поиск решения
Множество Самый очевидный способ решения того, что называется «в лоб», — это два массива, в первом — слова, во втором — числа.Встретив новое слово, мы добавляем его в первый массив, если его там нет, или добавляем его в индекс во втором массиве, если мы нашли слово в первом.
Попробовав этот вариант, я сразу в нем разочаровался; через несколько часов программа со скрипом пролезла первую половину первого архива.
Любой профессиональный программист, наверное, уже смеется над таким подходом.
Однако, признаюсь, я даже не предполагал, что меня ждет подвох.
Тогда я начал искать, где находится узкое место, не позволяющее программе дышать.
Узким местом оказался момент добавления нового слова.
Чтобы массив оставался упорядоченным, слово приходится вставлять где-то в середине, а иногда и в самом начале.
Для этого вам придется сдвинуть вправо каждый элемент массива, расположенный справа от выбранной позиции.
Когда речь идет о миллионах слов, эта задача становится очень утомительной для процессора и он мстит, откладывая завершение программы на недели вперед. Упорядоченный список Мне пришлось искать структуру данных, которая бы позволяла добавлять каждый элемент просто в конец структуры, но в то же время позволяла бы их упорядочивать.
Именно тогда я наткнулся на упорядоченные списки.
Ячейка упорядоченного списка хранит сам фрагмент данных и указатель на другую ячейку.
Все нормально, мы просто добавляем новое слово и меняем 2 индекса, индекс предыдущего слова, указывающий на данное, и индекс данного слова, указывающий на следующее.
Но, к несчастью, поиск в таком списке требует очень больших вычислительных ресурсов.
Если в упорядоченном массиве мы могли начать поиск с середины и за одну итерацию разделить его пополам, то в упорядоченном списке нам приходится лазить по указателям от одного к другому, как по нитке, пока не найдём нужное место во всей этой путанице.
Я не пробовал этот вариант; научившись предыдущей неудаче, я сразу учуял засаду.
Бинарное дерево поиска Я нашел следующую структуру данных только через несколько часов.
Я столкнулся с двоичными деревьями поиска.
Немного почитав о различных вариантах, я остановился на самобалансирующемся дереве АВЛ, созданном, кстати, советскими учеными Георгием Максимовичем Адельсоном-Вельским и Евгением Михайловичем Ландисом и унаследовавшим его название от их фамилий.
Структура двоичного дерева аналогична упорядоченному списку, но каждый элемент, за исключением нескольких листовых элементов (называемых листьями), относится к двум элементам.
Корневой элемент — это тот, который находится в середине упорядоченного массива.
Он относится к элементу меньшему (левому) и большему (правому), кроме того, гарантируется, что все элементы левой ветви будут меньше этого, а все элементы правой ветви будут больше.
Рассмотрев левый или правый элемент, к которому мы пришли, мы увидим одну и ту же иерархию, она также относится к двум элементам, левая ветвь тоже меньше, правая ветвь больше.
Чтобы понять, как сбалансировать такое дерево, лучше всего прочитать соответствующую статью, например здесь: Деревья АВЛ .
Важно отметить, что двоичное дерево поиска полностью удовлетворило мои требования.
Быстрый поиск и быстрое добавление нового элемента.
Результат
В итоге, потратив еще несколько часов на оптимизацию, я получил многопоточное приложение, которое распаковывает архив в оперативную память, считает частоту появления различных слов и обрабатывает полученные данные с помощью 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
Теперь я могу использовать полученные данные для уточнения своего морфологического словаря, а получив словарь, можно будет улучшить «частотный анализатор», т.к.
появится возможность группировать слова с одним корнем.
Кроме того, требует доработки работа «анализатора частот» с различными кодировками и т.п.
Далее следует синтаксический анализ предложения.
В конечном итоге я хочу получить хоть сколько-нибудь адекватную семантическую сеть.
Несмотря на то, что мой «доклад» затрагивает и тему программирования, и лингвистики – прошу не упрекать меня в неточностях в написании (особенно в пунктуации) или не самом гладком решении задачи, а указать на эти ошибки или предложить более изящное решения, я буду рад. Спасибо всем.
Теги: #компьютерная лингвистика #структуры данных #оптимизация кода #Семантика
-
Различные Методы Внедрения Erp-Системы
19 Oct, 24 -
Объединение Вашего Дома В Сеть
19 Oct, 24 -
Обзор Сравнения Программного Обеспечения
19 Oct, 24 -
Как Должен Работать Хештег #Followfriday
19 Oct, 24 -
Многоножки Заменяют Флешки
19 Oct, 24 -
Asus Pro P31/41: Тестирование На Эвересте
19 Oct, 24 -
Adoffer Приглашает Вас Начать Работу
19 Oct, 24
