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

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

Завдання, начебто дуже проста і напевно вирішується щодо програмування у перших рядах. Але для аналізу такої громіздкої бібліотеки, а бібліотека, що використовується мною, простягається на 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 мб/сек.

Тепер можна використовувати отримані дані для доопрацювання мого морфологічного словничка, а отримавши словничок можна буде покращити частотний аналізатор, т.к. з'явиться можливість угруповання однокорінних слів. Крім того, доопрацювання вимагає робота «частотного аналізатора» з різними кодуваннями тощо. Далі – синтаксичний аналіз пропозиції. Зрештою хочу отримати якось адекватну семантичну мережу.

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