morpher.ru 8 (499) 647 86 54
nowhere@morpher.ru
 
 

Частотный словарь полутора гигабайт русских текстов

Сентябрь 2002

У меня давно было желание провести статистическое исследование достаточно представительной выборки русских слов, чтобы найти среди них самые часто употребимые, самые длинные, самые средние... в общем, все самые-самые.

И вот, когда у меня в руках оказался диск «Библиотека в кармане» (выпуск 4), я понял, что моя мечта близка к осуществлению. Написание программы заняло совсем немного времени, и теперь я с удовольствием представляю вам результаты этого эксперимента.

Основные результаты

Было просканировано около 1,5Гб (более полумиллиона печатных страниц) русских текстов различной тематики: классика, детективы, фантастика, специальная литература, словари и энциклопедии. Общая длина всех текстов составила более двухсот миллионов слов. (Точнее, словоформ. Здесь и далее речь будет идти только о словоформах.) Среди этих двухсот миллионов уникальными оказались всего лишь чуть более двух миллионов словоформ, причём 47% из них встретились только один раз. (Любители точных цифр найдут их в результатах одного из прогонов ниже.)

Наиболее часто употребимыми оказались, как и следовало ожидать, служебные слова – союзы, предлоги, частицы и местоимения. А именно (первые два десятка): и, в, не, на, что, я, с, он, а, как, но, его, к, это, все, по, из, у, она, за, от... См. также: 300 наиболее часто употребимых словоформ.

Интересно отметить высокую частотность однобуквенных сокращений:

  • п пункт, тому подобное;
  • г господин, грамм, город;
  • м метр, мадам, месье, мост и т.п.

Однако, наиболее часто «одинокие» буквы встречаются как инициалы.

Статистика корпуса текстов

Вот статистика одного из прогонов. Точнее было бы назвать эти числа статистикой диска «Библиотека в кармане», так как от одного прогона к другому меняется только время, остальные числа остаются те же. (Правда, я добавил к этому диску несколько своих файлов, что в общем-то, неважно.) Итак:


Всего просканировано:
  - Байт: 1.513.487.254
  - Файлов: 3.676
  - Словоформ: 205.448.447 
  - Из них уникальных: 2.133.715

Динамика роста размера словаря

На следующем графике показана динамика роста размера словаря. В качестве единицы «времени» (горизонтальной оси) выбран миллион слов входного текста. По вертикальной оси отложен размер словаря в словах.

Те же самые данные, представленные в виде приращения числа незнакомых слов на каждый миллион слов входного текста (производная первого графика):

Как видно, после примерно 60 млн. слов устанавливается относительно ровное приращение в несколько тысяч слов на миллион, продолжающееся до конца графика. Ярковыраженный всплеск в области 32 млн. соответствует периоду прохождения словарей (из которых самые большие – Даля и Мюллера).

Проведя линейную аппроксимацию по области за 60 млн. слов, получаем показанную на первом графике формулу для оценки размера словаря в зависимости от объёма проиндексированных текстов. Полученное число необходимо умножить на средний размер одной словарной статьи. Он может быть оценен как средняя длина слова + размер служебной информации, зависящий от формата хранения данных.

Средняя длина слова по результатам измерений на материале диска «Библиотека в кармане» составила 5.36282 буквы. При этом не учитывались слова длиной более 40 букв.

Детали реализации на C++

Следующая информация будет более интересна программистам, нежели лингвистам.

На доработку и оптимизацию этой программы, на «доведение её до ума» ушло около двух месяцев и, признаться, я очень доволен полученным результатом. У программы большой потенциал: она может быть развита в реальную систему индексации текстов, ничуть не уступающую уже имеющимся в производительности.

Вот краткое описание функциональности программы и её возможностей. Программа просматривает указанный каталог, его подкаталоги и архивы RAR в поисках текстовых файлов (*.txt). Все найденные файлы пословно анализируются, составляется словарь уникальных словоформ со счётчиками появлений в тексте каждой словоформы. Программа «понимает» две кодировки русского текста, DOS-866 и Windows-1251. Пока программа безразлична к морфологии, формально «кодировкой» считается и латиница, так что для выбора кодировки предусмотрены три ключа (-dos, -win и -lat). Конечно же, число поддерживаемых кодировок может быть легко расширено.

Несколько замечаний по сути проведённых оптимизаций.

  • Выбрана оптимальная структура словаря, исходя из требований быстрого поиска и вставки. Кандидатов, по сути, не так уж много, а именно std::map (двоичное дерево) и hash_map (список с хэш-таблицей). Класс hash_map пока не является частью стандартной библиотеки C++, но присутствует во многих её реализациях. В частности, я пытался применить hash_map из Visual C++ .Net и SGI STL (www.sgi.com/Technology/STL). SGI STL мне так и не удалось заставить работать с VC. К тому же, моя собственная реализация hash_map для данного приложения оказалась гораздо более эффективной (более чем в 2 раза), чем та, что поставляется с VC7, поэтому я остановил свой выбор на ней.
  • Использование строк фиксированного размера (класс FixedString <size_t>) для представления слов в словаре позволило существенно снизить требования к памяти. Если недостатка свободной оперативной памяти нет, то с точки зрения производительности предпочтительнее использование std::string. Программа имеет ключи для выбора структуры словаря (map или hash_map) и представления слов в нем (string или FixedString), что позволяет варьировать производительность програмы и её требования к памяти на этапе выполнения.
  • Вызов streambuf::sbumpc () вместо обычного istream::get () ещё немного повысил производительность. istream::get в VC реализована не очень эффективно.

Исходный текст программы может стать хорошим обучающим примером для тех, кто изучает программирование на C++ (не для новичков).

Вы можете использовать приведённые здесь исходные коды в своих проектах. Если такое произойдёт, я буду рад узнать о том, какое применение нашли мои разработки. Любые отзывы и замечания по программе будут также кстати.

Требования к программному и аппаратному обеспечению

Windows 95 и выше. Процессор класса Pentium.

Необходимый объём оперативной памяти зависит от объёма анализируемых текстов. Для диска «Библиотека в кармане» необходимо 128 мегабайт (умеренное использование файла подкачки), рекомендуется 256М.

Производительность

Время индексирования всего диска вместе с распаковкой архивов на различных компьютерах:

КомпьютерОСВремя, средняя скорость
до оптимизациипосле
PII-350/128W2K Pro52 мин, 65000 слов/с 
PII-350/196W2K Pro43 мин, 79000 слов/с21 мин, 163000 слов/с
PIII-750/256NT426 мин, 133000 слов/с 
PIII-1100/240XP24 мин, 135000 слов/с10 мин, 342000 слов/с

Достижению такой высокой производительности во многом способствовало использование хэшированного ассоциативного массива (см. hash_map.h) для представления словаря.

Переносимость

Проверено на Visual C++ 6.0, Visual C++ .NET, Borland C++ 5.5.

В связи с неполной поддержкой исключений в VC6.0 некоторые ошибки диагностируются как "Unknown error". Этих проблем нет у VC.NET и BC5.5.

Модули dirrec.cpp (рекурсивный просмотр подкаталогов) и unrar.cpp (распаковка RAR-архивов) используют WINAPI, поэтому потребуют переписывания при их переносе на не-Windows платформу.

Скачать

Вот и собственно программа:

statsbin.zip (195K) – исполняемые файлы (stats.exe и unrar.dll)

statssrc.zip (15K) – исходный код на C++

Ссылки


Комментарии

Добавить комментарий
nowinter 23.07.2009 07:20 UTC

не работают ссылки на программу и код



Сергей Слепов 23.07.2009 22:02 UTC

Исправил, спасибо за замечание.



nowinter 26.07.2009 14:51 UTC

Спасибо Вам!!



Assaf 16.11.2009 09:06 UTC

Dear Sir,
I am looking for a Russian word frequency list (with capital letters)
I will appreciate very much whether you could let me know where I could download such a list.
With many thanks
Best,
Assaf



Eprinter 16.11.2009 13:12 UTC

Супер программа!
Работает в самом деле очень быстро, однако есть одна досадность. Для пробы натравил программу на Войну и Мир Л.Н.Толстого (файл txt), например в файле freq_dic.txt вместо "вознагражденным" стоит "вознагсажденн", вместо "притворно-сладкое" - "восно-сладкое"... И так очень часто, с потерянными частями слов, с буквой "с" вместо "р".
Может я что-то не так делаю?



Сергей Слепов 17.11.2009 22:28 UTC

Hello Assaf, here is the list of top 300 russian words. Let me know if you need a longer list. Would be nice if you could tell us what kind of project you are working on.
Regards,
Sergey



Сергей Слепов 17.11.2009 22:40 UTC

Eprinter - по умолчанию программа использует кодировку CP866 (давно была написана, еще под DOS). Укажите ключ -win.



Visitor_z 12.06.2010 10:33 UTC

Здравствуйте! Пишет вот так:

...
Using encoding: DOS-866 Cyrillic
Dictionary structure: ternary_tree <string, Stats>

Failed to recurse into obelisk-win-text\
(FindFirstFile returned INVALID_HANDLE_VALUE)
0 elements, 0 nodes, 0 empty nodes (-1.#IND%)
freeing memory... done

press enter...

..........

что не правильно делаю? (windows xp sp3)
Спасибо!



Visitor_z 12.06.2010 10:36 UTC

ps файл хоть и назван win, но в кодировке 866



Visitor_z 12.06.2010 12:00 UTC

Спасибо, все наладилось! (программа открывалась из под wine)/
Отличная работа.
Еще раз спасибо.



Валерий 04.08.2010 23:15 UTC

Здравствуйте!
Объясните чайнику, как запускается программа?
Если просто запускаю stats.exe, выводится в консоли текст функции Help() где в конце press enter...

Если нужно предварительные настройки установить - указать файл с текстом, не пойму где. Если в коде исходника и скомпилировать, не найду куда. Пробовал просто скомпилировать и собрать в VC++2008 - выдает 58 ошибок.
Ничего не понимаю, С++ только начал изучать.



Валерий 05.08.2010 08:12 UTC

Наверное, запуск нужно производить из командной строки.
Если так, пожалуйста, покажите полную запись для запуска программы.
Я написал так: stats.exe file.txt
В консоли вывелось то же самое, что и у Visitor_z.



Валерий 05.08.2010 16:18 UTC

Помучался день, есть кое-какие успехи.
Похоже пишу сам себе, ну да ладно.
Тяжело осваивать компьютер и интернет, когда тебе уже 50.

Программа теперь работает. Нужно было писать полный путь к каталогу, в котором нужно обработать текстовые файлы, а не просто имя файла.
Написал в cmd вот так: c:\stats\stats -win -hs c:\catalog\
В результате программа в консоли стала выводить обрабатываемые файлы и их размер. В конце вывела время работы и вот это:

sorting... done
writing... done
freeing memory... done

press enter...

Теперь другая проблема - не могу найти файл с результатами обработки, т.е. составленный частотный словарь.

Когда я неправильно запускал программу, сами создавались чистые файлы: growth.txt и freq_dic.txt. Теперь они не создаются и никакие другие созданные файлы найти не могу.

Как указать файл, в который нужно записать результаты не пойму. Если для этого нужно указать ключ -freq, то я пробовал писать так: -freq file.txt -freq c:\stats\file.txt, но программа при этом перестает работать и выдает сообщение: Invalid key -freq.
Теперь осталось эту проблему методом тыка решить.



Валерий 09.08.2010 09:36 UTC

Нашелся файл с частотным словарем.
Но слова в нем никак не отранжированы, не по алфавиту, ни по частоте. Это, конечно, минус. А так, программа шустрая, спасибо Сергею.
А ранжирование попробую сам дописать. Вот книжки по С++ дочитаю и буду пробовать. Еще хочу сделать подсчет средней длины предложения и очистку от стоп-слов, предварительно задав их список в отдельном файле. Наподобие, как это работает в апплете у А.Попова с его кораблями в бутылках. Только его апплет, почему-то, выдает отличные от данной программы результаты, и в частотности и в количестве слов. Посчитал на калькуляторе, аппелт Попова врет.



Сергей Слепов 09.08.2010 12:30 UTC

Валерий, спасибо за интерес к моей программе. Восхищаюсь Вашей настойчивостью!

Ошибки при компиляции в Visual Studio 2003 и выше возникают из-за изменений в компиляторе начиная с этой версии. Как сказано в MSDN:

"This is a breaking change in the Visual C++ .NET 2003 compiler, made in order to conform to the ISO C++ standard."

Чтобы исправить эти ошибки, нужно в объявлениях вида

template MyClass ::NestedClass ...

вставить слово typename:

template typename MyClass ::NestedClass ...

Хорошее упражнение, если вы изучаете C++. Чтобы сохранить совместимость с ранними версиями VC++, сделайте

#if (_MSC_VER >= 1300) // VS 2003
#define TEMPLATE_TYPENAME typename
#endif

template TEMPLATE_TYPENAME MyClass ::NestedClass ...

Еще функция allocate принимает один аргумент - просто сотрите второй.

На сортировку еще не смотрел - но подтверждаю, что работае как-то странно. Если исправите, выложу Вашу версию.

С уважением,

Сергей



Валерий 09.08.2010 19:18 UTC

Спасибо, Сергей!
Освоюсь в С++ и буду пробовать Ваши рекомендации. А сейчас мне еще тяжело понять все тонкости. Осваиваю С++ одновременно по трем разным книгам: одна перевод, другая нашего автора, а третья интернет-версия учебника. Только так стал разбираться. Иначе ошибки в книгах заводят, порой, в тупик. Но при сравнении одного и того же материала в разных книгах, понимаю, как должно быть правильно.
Ваша программа заинтересовала, поскольку недавно научился строить сайты, теперь дополнительный доход у фирмы появился. Но появилась необходимость в продвижении сайтов, а здесь понял, что нужно применять математический анализ, в частности, контента сайтов, на предмет соответствия текста естественным параметрам, с точки зрения поисковых систем (Яндекс в первую очередь). Вот и начал поиск соответствующего материала. Нашел Ваш сайт. По ссылкам с него нашел словари. Ну и всякое полезное для этих целей.
Конечно, есть разный софт для подобных целей, но функциональность и алгоритмы даже платных программ меня не устраивают. Это все для работы на уровне новичка. А мне нужен профессиональный подход.
С использования Вашей программы и начал. Еще раз спасибо за работу!



Василий 11.11.2010 09:21 UTC

Здравствуйте, Сергей.
Я программист, только начинаю изучать тему морфологии, хочу сделать частотный анализатор текста с учетом словоформ, не знаю с чего начать, для образования словоформ программа наверное должна использовать словарь с описанием таких параметров слова, как часть речи, род, склонение и т.д.?

И еще такой вопрос, как из слова можно выделить корень, это тоже делается в зависимости от параметров слова путем удаления аффиксов?

Спасибо.



Сергей Слепов 14.11.2010 03:16 UTC

Василий, я перенес ваш вопрос на эту страницу. Ваш вопрос про корень очень неоднозначный. Какой корень вам нужно выделить? Например, слова ХОД, ХОЖУ, ХОЖДЕНИЕ - однокоренные. Какой из трех корней вам нужен? Слова ВОДА и ВОДИТЬ имеют корень ВОД, но это не один корень, а два омонимичных.

Опишите вашу задачу, что на входе и что на выходе.



Дмитрий 19.11.2010 12:38 UTC

Здравствуйте!

Попробовал использовать вашу программу и получил следующие данные, хотя анализировал сборник Вознесенского:

52038 р
23986 с
2401 рёр
1472 рёс
1642 рё
961 в
44 рёрё
6 рё-р
6 рё-с
7 рёв
1 рёрёр
1 рёрёс
1 п

Что я не так делал?



Дмитрий 19.11.2010 12:49 UTC

Я поправил кодировку и все получилось. Огромное спасибо!



Дмитрий 19.11.2010 13:09 UTC

Продвигаемся дальше. Возникают новые вопросы ;)

Как можно упорядочить слова по частотности?

Как можно сделать, чтобы слова с разными окончаниями программа объединяла в одно?

Спасибо большое!



anon 07.12.2010 09:33 UTC

А где сам словарь?



Саша 01.07.2012 23:14 UTC

Опа, а у меня на делфи почти точь-в-точь такая же штуковина написана! Невероятно, но факт - использовался диск той же самой "библиотеки в кармане" :-D Правда, первой версии. Специально глянул скорость - шпарит примерно 320 тыс. слов в минуту, но это без распаковки, распаковывал я заранее, винраром. Из отличий - имеется модуль самообучения: пользователь указывает тему (exp "Средневековая культура"), программа ищет в Яндексе соответствующие статьи и разбирает на слова (для этого пришлось прикрутить поддержку юникода).

Должен сказать, что после анализа моей собственной библиотечки (fb2), довольно скромной, первые места распределились по-другому, причём отличия уже в первых 20-ти:

и, в, не, на, что, я, с, он, а, как, но, его, к, это, по, все, из, у, за, от, она...

Видимо, нужно расширять выборку, 1,5 ГБ недостаточно))) Где-то в торрентах был архив Флибусты, 175.33 GB... ;-)



Сергей Слепов 24.05.2013 22:13 UTC

Саша, здравствуйте!

Пропустил ваш комментарий, отвечаю спустя почти год... Рад, что у нас похожие интересы и даже один источник текстов использовали. Один, да не совсем. Вы первый выпуск диска, я четвертый. Отсюда и разница в результатах:

1. и в не на что я с он а как но его к это по все из у за от она...
2. и в не на что я с он а как но его к это все по из у она за от...
3. и в не на что с то я он как а по к его все из за это у же от...

Где 1 - ваш ряд, 2 - мой, 3 - Сергея Шарова.

Про скорость - у меня она составила 342000 слов в секунду, а не в минуту.



Саша 25.05.2013 08:54 UTC

Да, действительно, в секунду)))

Скормил stats.exe три сотни файлов в win-1251, общей суммой в 202 мб, 27'768'517 слов. У него всё заняло 14 секунд (против 60 моих, т.е. в 4 раза быстрее). Кажется, я уже знаю в чём проблема...)



Азиз 11.10.2014 11:54 UTC

Спасибо вам



Essiggi 08.02.2015 05:59 UTC

Здравствуйте, Сергей. Я бы хотел узнать, что нужно для запуска вашей программы на платформе Windows 7?



Сергей Слепов 08.02.2015 10:32 UTC

Должна запускаться как есть. У меня без проблем запустилась на Windows 8.



Remark 30.03.2015 14:02 UTC

Тут два архива....
Вы можете поэтапно описать запуск и работу программы. Которую из них запускать и куда вводить текст. Спасибо



Добавить комментарий


 

Библиотеки

Заметили опечатку? Выделите слово мышкой и нажмите Ctrl-Enter. Система Orphus

© Сергей Слепов, 2003 - 2017. Перепечатка материалов сайта только с разрешения автора.