Създаване на честотен речник въз основа на анализа на художествена библиотека

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

Изглежда, че задачата е много проста и със сигурност се решава, когато се учи програмиране на преден план. Но за анализа на такава тромава библиотека и библиотеката, която използвам, се простира на 157 хектара, средствата на средния домашен компютър са достатъчни с намеса. За да бъдем по-точни, библиотеката се съхранява в петдесет zip архива от 0,5 - 2 GB, всеки от които съдържа 20-30 хиляди произведения във формат fb2. Тежи 60 GB компресиран.

Проблемът беше решен в c #. Резултатът трябва да се получи за подходящо време, за което избрах не повече от 8 часа, за да можете да започнете изпълнението вечер и да получите резултата сутрин.

Намиране на решение

Най-очевидният метод за решение, който се нарича „челен” - два масива, в първия - думи, във втория - число. След като срещнахме нова дума, ние я добавяме към първия масив, ако той липсва там, или добавяме една към индекса във втория масив, ако намерихме дума в първия. След като изпробвах тази опция, веднага се разочаровах от нея, след няколко часа програмата изскърца, пълзейки по първата половина на първия архив. Всеки професионален програмист вероятно вече се смее на този подход. Признавам обаче - дори не си представях, че чакам улов.

След това започнах да търся - къде е пречка, която не позволява на програмата да диша. Тесното място се появи в момента на добавяне на нова дума. За да поддържа масивът подреден, думата трябва да се вмъкне някъде в средата, а понякога и в самото начало. За да направите това, трябва да изместите всеки елемент от масива, разположен вдясно от избраната позиция вдясно. Що се отнася до милиони думи, тази дейност става много досадна за процесора и той отмъщава, като отлага завършването на програмата със седмици предварително.

Подреден списък

Трябваше да потърся такава структура на данни, която да позволява добавянето на всеки елемент просто в края на тази структура, но в същото време щеше да позволи да бъдат подредени. Тогава попаднах на подредени списъци. Клетката на подредения списък съхранява самата част от данните и указател към друга клетка. Всичко е чудесно, просто добавяме нова дума и променяме 2 индекса, индексът на предишната дума, посочващ дадената, и индексът на дадената дума, показваща следващата. Но лош късмет, търсенето в такъв списък е много изчислително изискващо. Ако в подреден масив можем да започнем да търсим от средата и да го разделим наполовина в една итерация, тогава в подреден списък трябва да се изкачим над указателите от един на друг, като низ, докато намерим правилното място в цяла плетеница. Не опитах тази опция, след като се поучих от предишния провал, веднага забелязах засадата.

Двоично дърво за търсене

Намерих следната структура от данни само няколко часа по-късно. Попаднах на бинарни дървета за търсене. След като прочетох малко за различни варианти, се спрях на самобалансиращо се дърво AVL, създадено между другото от съветските учени Adelson-Velsky Georgy Maksimovich и Landis Evgeny Mikhailovich, и наследих името му от техните имена.

Структурата на двоично дърво е подобна на подреден списък, но всеки елемент, с изключение на няколко окончателни (така наречените листа) се отнася до два елемента. Основният елемент е този, който ще бъде в средата на подредения масив. Той се отнася до елемента по-малък (вляво) и по-голям (вдясно), освен това е гарантирано, че всички елементи от левия клон ще бъдат по-малки от дадения, а всички елементи от десния клон ще бъдат по-големи. Разглеждайки левия или десния елемент, до който сме стигнали, ще видим една и съща йерархия, тя също се отнася до два елемента, левият клон също е по-малък, десният клон е по-голям. За да разберете как да балансирате такова дърво, най-добре е да прочетете съответната статия, например тук: AVL дървета. Важно е да се отбележи, че бинарното дърво за търсене напълно отговаря на моите изисквания. Бързо търсене и бързо добавяне на нов елемент.

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

Ето няколко реда от резултатите на програмата, вляво - думата, вдясно - честотата. Това са най-често срещаните думи с различна дължина:

  • i 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 Mb/s.

Сега можете да използвате получените данни, за да прецизирате моя морфологичен речник, а след като сте получили речника, можете да подобрите "анализатора на честотата", тъй като ще бъде възможно да се групират еднокоренни думи. Освен това работата на „честотния анализатор“ с различни кодирания и т.н. изисква подобрение. Следва разбор на изречението. В крайна сметка искам да получа донякъде адекватна семантична мрежа.

Въпреки факта, че моят „доклад“ засяга както темата за програмирането, така и лингвистиката - моля, не ме обвинявайте за неточности в писмеността (особено пунктуацията) или не за най-гладкото решение на проблема, но моля, посочете тези грешки или предложите по-елегантни решения, ще се радвам.