Създаване на честотен речник въз основа на анализа на художествена библиотека
Наскоро, за да изгладя морфологичния речник, способен (вероятно) да генерира всички възможни форми на дума от инфинитива, се нуждаех от доста обемен честотен речник на руския език. Честотният речник е много просто нещо, думите в него са подредени според честотата, с която се срещат в анализирания текст.
Изглежда, че задачата е много проста и със сигурност се решава, когато се учи програмиране на преден план. Но за анализа на такава тромава библиотека и библиотеката, която използвам, се простира на 157 хектара, средствата на средния домашен компютър са достатъчни с намеса. За да бъдем по-точни, библиотеката се съхранява в петдесет zip архива от 0,5 - 2 GB, всеки от които съдържа 20-30 хиляди произведения във формат fb2. Тежи 60 GB компресиран.
Проблемът беше решен в c #. Резултатът трябва да се получи за подходящо време, за което избрах не повече от 8 часа, за да можете да започнете изпълнението вечер и да получите резултата сутрин.
Намиране на решение
Най-очевидният метод за решение, който се нарича „челен” - два масива, в първия - думи, във втория - число. След като срещнахме нова дума, ние я добавяме към първия масив, ако той липсва там, или добавяме една към индекса във втория масив, ако намерихме дума в първия. След като изпробвах тази опция, веднага се разочаровах от нея, след няколко часа програмата изскърца, пълзейки по първата половина на първия архив. Всеки професионален програмист вероятно вече се смее на този подход. Признавам обаче - дори не си представях, че чакам улов.
След това започнах да търся - къде е пречка, която не позволява на програмата да диша. Тесното място се появи в момента на добавяне на нова дума. За да поддържа масивът подреден, думата трябва да се вмъкне някъде в средата, а понякога и в самото начало. За да направите това, трябва да изместите всеки елемент от масива, разположен вдясно от избраната позиция вдясно. Що се отнася до милиони думи, тази дейност става много досадна за процесора и той отмъщава, като отлага завършването на програмата със седмици предварително.
Подреден списък
Трябваше да потърся такава структура на данни, която да позволява добавянето на всеки елемент просто в края на тази структура, но в същото време щеше да позволи да бъдат подредени. Тогава попаднах на подредени списъци. Клетката на подредения списък съхранява самата част от данните и указател към друга клетка. Всичко е чудесно, просто добавяме нова дума и променяме 2 индекса, индексът на предишната дума, посочващ дадената, и индексът на дадената дума, показваща следващата. Но лош късмет, търсенето в такъв списък е много изчислително изискващо. Ако в подреден масив можем да започнем да търсим от средата и да го разделим наполовина в една итерация, тогава в подреден списък трябва да се изкачим над указателите от един на друг, като низ, докато намерим правилното място в цяла плетеница. Не опитах тази опция, след като се поучих от предишния провал, веднага забелязах засадата.