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

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

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

Требования к программному и аппаратному обеспечению
Производительность
Переносимость
Скачать

Ссылки

Сентябрь 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/128 W2K Pro 52 мин, 65000 слов/с

PII-350/196 W2K Pro 43 мин, 79000 слов/с 21 мин, 163000 слов/с

PIII-750/256 NT4 26 мин, 133000 слов/с

PIII-1100/240 XP 24 мин, 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++

Ссылки

Ссылки на другие частотные словари русского языка в Сети
Частотный словарь диска «Библиотека в кармане» был использован в программе «Рифмовник» Николая Кецариса для отсеивания малоупотребимых форм, сгенерированных на основе словаря Зализняка.

Супер программа!
Работает в самом деле очень быстро, однако есть одна досадность. Для пробы натравил программу на Войну и Мир Л.Н.Толстого (файл 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

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