Статистическая обработка текстов и сборка N-грамм

Программа Эмпирика

Модуль empirika, входящий в состав SDK, имеет много функций, связанных со статистической обработкой текстов на естественном языке с учетом грамматики. Среди прочего она выполняет частотный лексемный анализ произвольного текстового файла или подборки файлов и накопление N-грамм. При этом либо анализируются отдельные лексемы без учета их взаимовлияния, либо строятся частотные таблицы встречаемости пар слов типа прилагательное+существительное, с учетом грамматического согласования элементов пары, либо таблицы частот групп слов - от диграмм до пентаграмм. По результатам работы строятся несколько файлов, содержащих частотные характеристики обработанных текстов - в том числе частоты отдельных слов (см. список файлов далее). Информацию из базы N-грамм можно получить через функции API.

Другой режим анализа текстов включает в себя синтаксический анализ предложений, то есть построение для них грамматических деревьев. С помощью этого режима можно оценивать качество синтаксического анализатора, в частности - скорость его работы.

Кроме чисто исследовательских задач, программа empirika выполняет также подготовку статистических данных о языке, используемых в словаре в поисковом движке φaind . Полнотекстовый переводчик использует накопленные N-граммы для отбора переводов в контексте.

Для использования программы empirika необходимо иметь откомпилированный словарь (как его получить см. здесь), в котором используется лемматизатор (для приведения словоформ к базовым грамматическим формам), так и синтаксические правила. Получить исполнимый модуль программы можно в составе SDK Грамматического Словаря - смотрите подробнее здесь.

Утилита портирована на 32х и 64-битные версии MS Windows, Linux и Mac OS X (Darwin).

Утилита Chars

При обучении модулей распознавания текста на одном из этапов для генетического алгоритма OCR возникает задача получения списка N-грамм символов, реально присутствующих в текстах. Обычно требуются ди-, три- и тетраграммы.

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

Для получения необходимых данных на языке C# была написана небольшая консольная утилита, которая получает на вход имя текстового файла в кодировке utf-8, обрабатывает его содержимое и формирует в результате текстовые файлы в формате txt и csv со списками N-грамм и гистограммами распределения. Эти результаты затем читаются утилитой генерации изображений text2bmp.

Грамматический словарь и его файл конфигурации

Для своей работы программа empirika обязательно требует наличия в текущем или явно указанном каталоге файла скомпилированного словаря. В составе SDK есть готовый словарный модуль, который без дополнительных усилий применим для empirika. Путь к файлам словаря указывается опцией -dictdir. Эта опция задает либо путь к каталогу с файлом dictionary.xml, либо путь к конфигурационному файлу с любым другим именем, если оно отличается от дефолтного dictionary.xml.

Формируемые файлы

Программа анализирует все файлы с заданным расширением в указанных каталогах (см. опции определения области поиска поискового движка - они полностью работают и для empirika), накапливает статистику, а по завершении формирует ряд файлов, записывая их либо в текущий каталог, либо в указанный командой -outdir.

Для схемы 1 - статистика использования слов:

empir.rez - общие результаты в кратком читабельном виде.

words.xml и words.xsd - частоты слов в формате XML. Эти файлы можно прямо загружать в MS Access 2003 и анализировать (мы используем связку Access и Excel). Подробнее об этом можно прочитать здесь.

unfound.res, unfound.xml - список не найденных в лексиконе слов (простой текстовый формат и XML).

entry_freqs.dat - частоты слов (отсортированы по убыванию)

classes_freq.dat - частоты грамматических классов

word_lengths.dat - гистограмма частот лексем разной длины

Для схемы накопления N-грамм:

В зависимости от настроек хранилища это может быть один файл NGRAMS, несколько файлов NGRAM1, NGRAM2 ..., а при использовании в качестве хранилища серверной версии СУБД - вообще никаких локальных файлов.

Минимальные и рабочие требования к объему памяти

Приготовьтесь к тому, что использование программы на 256 Мб приведет к свопингу, так как после загрузки словаря и подготовки внутренних структур к работе программа выделяет примерно 140 Мб. По мере обработки файлов выделенная память увеличивается, хотя каких-то априорных оценок здесь дать невозможно. Рекомендуем иметь на машине не менее 1 Гб памяти для обработки больших объемов текстовых выборок. Для накопления N-грамм крайне желательно иметь 2 Гб памяти для 32-битной версии. 64-битная версия при использовании NoSQL хранилища может использовать под буферизацию данных всю имеющуюся память, при указании в командной строке предельного размера, поэтому и 8 Гб может быть использовано для ускорения работы.

Опции запуска программы

Вид обработки

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

1. Режим частотной статистической обработки. Накапливаются частоты слов в обработанных файлах. Работает быстро, но требует значительных ресурсов оперативной памяти для хранения частотных списков слов. Включается опцией:

-scheme1

2. Режим накопления N-грамм в обработанных файлах. Работает достаточно быстро, но может потребовать очень больших объемов дисковой памяти для хранения результатов. Суммарный объем обработанных текстов и накопленный объем N-грамм лимитируется только производительностью компьютера и ресурсами дисковой памяти. Включается опцией:

-ngrams

Несколько опций позволяют выбрать один из видов N-грамм для накопления:

-correl_an обрабатывает пары слов прилагательное+существительное (спиральная галактика)

-correl_nv обрабатывает пары слов существительное+глагол (кошка мышкует),

-correl_nn обрабатывает пары слов существительное+существительное (восход солнца),

-correl_adva обрабатывает пары слов наречие+прилагательное (очень яркий),

-correl_advv обрабатывает пары слов наречие+глагол (много спит).

-correl_pn обрабатывает пары предлог+существительное (на диване).

-correl_vobj обрабатывает пары слов глагол+управляемый объект (видит мышку).

-correl_any накапливает любые пары рядом стоящих слов, даже отсутствующих в лексиконе, так называемые несогласованные N-граммы.

Для несогласованных N-грамм по умолчанию собираются только 2-граммы, но можно включить другие режимы:

-1grams собирать монограммы (фактически частоту одиночных слов)

-1grams- не собирать монограммы

-2grams- не собирать 2-граммы.

-2grams собирать 2-граммы (умолчание).

-3grams собирать 3-граммы.

-3grams- не собирать 3-граммы (умолчание).

-4grams собирать 4-граммы.

-4grams- не собирать 4-граммы (умолчание).

-5grams собирать 5граммы.

-5grams- не собирать 5граммы (умолчание).

-segmentation аккуратный (но достаточно медленный) учет слов типа don't и кого-либо, то есть фактически состоящих из нескольких слов с разделителями. Используются правила сегментации для выбранного языка. К примеру, данная опция используется при подготовке базы N-грамм для фильтрации переводов, так как размер файла эталонов в этом сценарии относительно невелик, но обязательно требуется аккуратность при учете лексем.

-lemmatization для несогласованных N-грамм выполнять приведение словоформ к базовым формам (лемматизацию). Эта опция используется с -correl_any и переключает сбор ненормализованных несогласованных N-грамм на сбор нормализованных.

-eol_breaks перевод строки считать концом предложения.

-source_format 'csv' загрузка N-грамм, которые читаются из текстового файла в формате CSV; каждое слово отделено точкой с запятой, последний токен интерпретируется как частота.

Собираемые движком N-граммы можно разделить на 3 большие группы:

Согласованные - в базу попадают пары слов, между которыми существует грамматическая связь. К примеру, сочетание русского предлога и существительного попадет в базу, если во-первых они стоят рядом (существительное после предлога, возможно разделенные прилагательным), и во-вторых выполнено условие согласования падежной валентности предлога и существительного. Для данного типа записей автоматически выполняется лемматизация - слова автоматически приводятся к базовой форме. Поэтому пары 'на дереве' и 'на деревьях' дадут в базе одну запись с частотой 2. Этот тип N-грамм удобен в случаях, когда необходимо выяснить, к примеру, с какими предлогами сочетается существительное или какие глаголы сочетаются с подлежащим. Один из примеров использования - генератор случайного текста. Основное ограничение данного типа - накапливаются только диграммы.

Несогласованные нормализованные (raw) - в эту категорию попадают любые соседние слова, даже если грамматически они не связаны. К примеру, из фразы "большая собака и пушистая кошка" будет выделена, кроме прочего, диграмма "собака и" и триграмма "собака и пушистая". Для этих N-грамм выполняется лемматизация - приведение слов к базовой грамматической форме. Поэтому "белая ворона" и "белые вороны" дадут в базе одну запись с частотой 2.

Несогласованные ненормализованные (literal) - в целом аналогичны нормализованным, но для них не выполняется лемматизация. Поэтому в базе полностью сохраняется информацию об использовании словоформ, а не словарных статей. Это может быть важных для некоторых приложений и для языков с развитым формообразованием. При накоплении такого типа N-грамм следует учитывать, что количество таких записей в несколько раз больше, чем при лемматизации.

Для управления размером кэша в сборщике используются опции

-doccache NNN задает максимальное количество записей в первичном кэше, по умолчанию это значение равно 5000000. N-граммы копятся в этом буфере по мере обработки документов и после достижениz указанного значения сбрасываются на диск. Так как распределение частоты появления N-грамм имеет явно выраженную асимметрию, то самые частые N-граммы эффективно буферизуются этим кэшем и уменьшают количество записей на диск.

-ngramscache NNN задает максимальное количество записей во вспомогательном кэше. По умолчанию это значение равно 10000000. Этот кэш позволяет ускорить обновление записей в базе данных.

-dbcache NNN - объем оперативной памяти, предоставляемой движку СУБД SQLite для выполнения своих операций (в байтах). Чем больше выделенный объем, тем легче движку выполнять построение индексов и поиск по таблицам. Для большинства СУБД, включая все серверные варианты, данный параметр игнорируется.

-use_disk_cache - использовать специализированную NoSQL СУБД для накопления N-грамм. Эта СУБД использует очень много дискового пространства (вплоть до десятков Гб), и оптимизирована для обработки многогигабайтных текстовых корпусов, которые порождают сотни миллионов N-грамм. Чтобы явно запретить использовать этот движок, когда объемы обрабатываемого текста малы или требуется функциональность старого движка - возможность дообработки текста или объединения двух БД, используется опция -use_disk_cache-. Недостатком данного движка является большое время, затрачиваемое перед началом работы на формирование дискового файла базы.

Опция -segment_n NNN заставляет движок накапливать N-граммы в отдельный сегмент в рамках единой базы N-граммы. Технически это означает, что можно разбить большой набор документов на несколько относительно небольших (допустим по 1 Гб) и накопить для каждого набора N-граммы в отдельном сегменте. Движок СУБД при этом гораздо лучше справляется с несколькими сегментами по 100000000 записей в таблицах, чем с единой базой с 1000000000 записей. Утилиты, которые обращаются к БД N-грамм автоматически объединяют результаты для всех сегментов, хотя конечно при этом происходит пропорциональное увеличение времени выборки.

Для дополнительной обработки собранной статистики используется опция

-erase_freq1 - удаление записей с частотой =1, то есть встретившихся однократно.

Дополнительные опции включают формирование по итогам работы списков отсутствующих в словаре и тезаурусе слов и синонимов:

-dump_unfound_words - записывать в текстовый файл (каталог указывается через -outdir) не-словарные слова.

-dump_unfound_synonyms - записывать в текстовый файл (каталог указывается через -outdir) отсутствующие в тезаурусе синонимы. Для реализацтт этого режима обрабатываемый текстовый файл с образцами-предложениями должен иметь специальный вид: пары (или больше в цепочке) предложений с одним изменяющимся словом, которое предполагается синонимом. Например "Большая собака. Большая псина. Массивная псина." Предложения в цепочке отделяются точкой.

Для просмотра получившейся базы N-грамм можно использовать программу Lexicon, входящую в SDK. У нее через начальное меню можно выбрать режим запросов к БД N-грамм.

3. Режим построения грамматических деревьев для предложений в обработанных файлах. Очень медленный (в сравнении с другими схемами) режим работы, но не требует много памяти для работы. Включается опцией:

-sentan

4. Обработка статистики на уровне букв, включается опцией

-chars

Языки

По умолчанию программа обрабатывает слова с любыми символами. В некоторых случаях это может оказаться нежелательным, например если текстовый файл содержит английские и русские слова, то статистические результаты будут представлять собой "суперпозицию", непригодную для анализа. С помощью опций можно включить фильтрацию определенных алфавитов.

Чтобы заставить обрабатывать слова только с базовой латиницей, необходимо указать опцию

-english

При этом слова с кириллицей, а также с латинскими буквами с диакритическими значками будут игнорироваться. Чтобы заставить программу учитывать только кириллицу (в рамках русского алфавита), используется опция:

-russian

Для статистической обработки слов, состоящих из букв, корректных для французского языка (латиница плюс некоторые диактрические значки-"акценты"), используется опция

-french

Кроме указания на язык обрабатываемых текстов в некоторых случаях необходимо задать кодировку текста в plain ascii файлах. По умолчанию в этом случае используется кодовая страница текущей пользовательской сессии, но можно переопределить ее опцией

-cp XXX

где XXX - имя кодировки (например big5 или cp1251).

Каталоги

Для указания каталога, куда будут записаны файлы результатов, используется опция

-outdir XXX

Для указания каталога с файлами словаря используется команда

-dictdir XXX 

Сканируемые файлы

Для указания каталога с документами, подлежащими обработке, используются команды -file и -dir.Например:

empirika -dir путь_к_каталогу

В нижеприведенном примере показано начало обработки библиотеки Мошкова:

Утилита умеет использовать плагины поисковой системы Интегра для извлечения текста из документов разных форматов (PDF, DjVu и др.).

Скрипты типовых сценариев

Для выполнения нескольких типовых сценариев подготовлены командные файлы, собранные в каталоге \scripts\empir. При запуске этих скриптов в качестве аргумента командной строки необходимо указать путь к каталогу с обрабатываемыми файлами. Результаты статистической обработки записываются в каталоги \tmp и \bin-windows\bin-windows64/bin-linux или /bin-linux64.

freq-ru каталог_с_текстами - частотная обработка текстов, для русского языка.

freq-en каталог_с_текстами - частотная обработка текстов, для английского языка.

ngrams-huge-ru каталог_с_текстами - накопление несогласованных 1,2,3,4,5-грамм для русского языка. В качестве хранилища используется специализированная реляционная NoSQL СУБД, позволяющая собирать оперировать миллиардами записей и десятками гигабайтов дисковой памяти. При запуске на платформе x64 скрипт настроен на использование 8 Гб оперативной памяти - если памяти меньше, параметры скрипта надо изменить во избежание ненужного своппинга виртуальной памяти.

ngrams-ru каталог_с_текстами в целом аналогичен ngrams-huge-ru, но в качестве хранилища используется SQL СУБД, выбранная при сборке утилиты. В силу этого существует ограничение на объем обрабатываемых данных, для 32-битной версии база данных начинает замедляться после обработки ~1-4 Гб текстов, для x64 версии предел составляет примерно 4-8 Гб.

ngrams-en каталог_с_текстами - накопление 1,2,3,4,5-грамм для английского языка. Технические нюансы аналогичны скрипту ngrams-ru.

Хранилище для N-грамм

Собираемые программой N-граммы могут запоминаться либо в SQL СУБД, либо в специализированной базе данных, специально разработанной для N-грамм.

В случае хранилища SQL СУБД используется выбираемая в конфигурационном файле база - в текущей версии это может быть SQLite или MySQL. Создаваемые в базе записи будут доступны прикладному коду с помощью SQL операторов наравне с API N-грамм.

Если используется специализированный движок хранилища (опция -use_disk_cache), то серьезно изменяются используемые программой дисковые ресурсы. Сразу после запуска утилита создаст и отформатирует один или больше дисковых файлов очень большого размера - для пентаграмм под x64 получается файл размером до 30 Гб. Создание и форматирование этих файлов данных занимает немало времени - несколько минут. Накладные расходы полностью окупаются возможностями данного движка - на платформе x64 он позволяет без ощутимого замедления накапливать более миллиарда 5-грамм, обрабатывая более 40 Гб текстов. После завершения обработки всех данных движок выполняет сжатие данных и копирование их в финальные файлы - это занимет десятки минут, но приводит к улучшению времени выборки данных и обычно серьезно уменьшает дисковый файл хранилища.

Вне зависимости от выбранного типа хранилища прикладной код может получить доступ к базе N-грамм с помощью процедур API.

Поддерживаемые форматы документов

Программа автоматически загружает все установленные вместе с поисковой системой content-плагины, поэтому обрабатываются любые документы, которые поддерживаются поисковой системой.

Примеры результатов работы для русского языка

Результаты работы программы для некоторой выборки:

гистограмма частот длин лексем

корреляция между длиной слова и его частотой

гистограмма частот грамматических классов

частоты словарных статей (первые 1024 статьи)

Обработано примерно 1.2 Гб текстов в формате HTML. Объем выборки -примерно 216,421,809 слов. Тексты - художественная литература (библиотека Мошкова).

Распределение длин слов

Words length distribution (stored also in 'word_lengths.dat'):
/* Max frequency position (X) */ MAX_P_X= 9.000000000000000e+000
/* Average */ M1= 9.392647322917467e+000
/* Dispersy */ M2= 9.036219772198516e+000
/* Square root of dispersy */ SIGMA= 3.006030567409206e+000
/* Coefficient of variation sqrt(M2)/M1 */ KV= 3.200408217260198e-001
/* 3rd central moment */ M3= 1.645842294366026e+001
/* Coefficient of assimetry */ Ka= 6.059098895889813e-001

1.00000e+000-+----------------------------------------------------------------++
2.00000e+000-+----------------------------------------------------------------+
3.00000e+000-+##--------------------------------------------------------------+
4.00000e+000-+##########------------------------------------------------------+
5.00000e+000-+########################----------------------------------------+
6.00000e+000-+########################################------------------------+
7.00000e+000-+#######################################################---------+
8.00000e+000-+###############################################################-+
9.00000e+000-+################################################################+
1.00000e+001-+###########################################################-----+
1.10000e+001-+#################################################---------------+
1.20000e+001-+#####################################---------------------------+
1.30000e+001-+#########################---------------------------------------+
1.40000e+001-+#################-----------------------------------------------+
1.50000e+001-+##########------------------------------------------------------+
1.60000e+001-+######----------------------------------------------------------+
1.70000e+001-+###-------------------------------------------------------------+
1.80000e+001-+##--------------------------------------------------------------+
1.90000e+001-+#---------------------------------------------------------------+
2.00000e+001-+----------------------------------------------------------------+
2.10000e+001-+----------------------------------------------------------------+
2.20000e+001-+----------------------------------------------------------------+
2.30000e+001-+----------------------------------------------------------------+
2.40000e+001-+----------------------------------------------------------------+
2.50000e+001-+----------------------------------------------------------------+
2.60000e+001-+----------------------------------------------------------------+
2.70000e+001-+----------------------------------------------------------------+
2.80000e+001-+----------------------------------------------------------------+
2.90000e+001-+----------------------------------------------------------------+

Средняя длина слова - 9.4 буквы (кстати, для английского - чуть меньше).

Частоты слов (при этом отдельные формы слова - к примеру КОШКА и КОШКИ считаются разными словами) - график . Также можно посмотреть на таблицу с частотами (первая сотня слов). Число показанных слов по оси абсцисс - примерно 32000. Шкала по оси ординат - логарифмическая. Обращаю внимание, что распределение частот не подвергалось никакой обработке - гладкость получаемого результата есть реальность языка, а не артефакт обработки.

Результаты работы для английского языка

Обработано примерно 610 Мб текстов в виде HTML - исключительно художественнаялитература. Объем выборки составил примерно 102,748,300слов.

корреляция между длиной слова и его частотой

Распределение длины слов

/* Average */ M1= 7.825363763678226e+000
/* Square root of dispersy */ SIGMA= 2.734136356381027e+000 1.00000e+000-+----------------------------------------------------------------++ 2.00000e+000-+#---------------------------------------------------------------+ 3.00000e+000-+###########-----------------------------------------------------+ 4.00000e+000-+##########################--------------------------------------+ 5.00000e+000-+#########################################-----------------------+ 6.00000e+000-+########################################################--------+ 7.00000e+000-+################################################################+ 8.00000e+000-+##############################################################--+ 9.00000e+000-+####################################################------------+ 1.00000e+001-+########################################------------------------+ 1.10000e+001-+##########################--------------------------------------+ 1.20000e+001-+###############-------------------------------------------------+ 1.30000e+001-+#########-------------------------------------------------------+ 1.40000e+001-+####------------------------------------------------------------+ 1.50000e+001-+##--------------------------------------------------------------+ 1.60000e+001-+#---------------------------------------------------------------+ 1.70000e+001-+----------------------------------------------------------------+ 1.80000e+001-+----------------------------------------------------------------+ 1.90000e+001-+----------------------------------------------------------------+ 2.00000e+001-+----------------------------------------------------------------+ 2.10000e+001-+----------------------------------------------------------------+ 2.20000e+001-+----------------------------------------------------------------+ 2.30000e+001-+----------------------------------------------------------------+ 2.40000e+001-+----------------------------------------------------------------+ 2.50000e+001-+----------------------------------------------------------------+ 2.60000e+001-+----------------------------------------------------------------+ 2.70000e+001-+----------------------------------------------------------------+ 2.80000e+001-+----------------------------------------------------------------+ 2.90000e+001-+----------------------------------------------------------------+

Средняя длина слова - 7.8 буквы (сравните с русским).

Частоты слов (при этом отдельные формы слова - к примеру CAT и CATS считаются разными словами) - график. Число показанных слов по оси абсцисс - примерно 20000. Шкала по оси ординат - логарифмическая. Обращаю внимание, что распределение частот не подвергалось никакой обработке - гладкость получаемого результата есть реальность языка, а не артефакт обработки.

Дополнительные материалы

API доступа к базе N-грамм

API синонимизатора

  © Elijah Koziev 2010
прикладные проекты на основе грамматического словаря API грамматической машины компоненты для доступа к грамматическому словарю условия получения SDK токенизатор и сегментатор морфологический анализ и синтез лемматизатор база N-грамм синтаксический анализатор словоформы морфология и синтаксис русского языка падеж число род совершенный и несовершенный вид экспорт в SQL формат экспорт в XML формат скрипт SQL словаря структура SQL словаря структура XML словаря компоненты для доступа к грамматическому словарю ORM Persistent Dictionary Library лемматизация стемминг примеры использования грамматического словаря склонение существительных в русском языке склонение русских прилагательных спряжение глаголов в русском языке поиск текста с учетом морфологии OCR подсистема расширенные регулярные выражения генератор текста генератор случайного текста и имитатор рандомизатор синонимизатор перефразировщик Статистика буквенных паттернов

Грамматический словарь русского языка



Грамматический словарь
склонение и спряжение глаголов, существительных, прилагательных

В состав входит русский и английский словарь.

платформа:  Windows 2000 ... Windows 7
требования: 512 Mb свободной памяти, 300 Мб на диске
размер:         34 Мб

  скачать грамматический словарь купить грамматический словарь SDK грамматического словаря
грамматический словарь русского языка



SDK Грамматического словаря



SDK Грамматического Словаря
склонение и спряжение глаголов, существительных, прилагательных

В состав входит русский и английский словарь.

платформа:  Windows 2000 ... Windows 7
размер:         13 Мб

SQL словарь (демо):
sqlite mysql oracle firebird mssql

скачать демо-версию SDK купить SDK API грамматического словаря



Поисковая система



Integra
настольная и сетевая поисковая система 

платформа:  Windows XP ... Windows 7
требования: 512 Mb свободной памяти
размер:         21 Мб

Дополнительные компоненты:
MySQL поисковый сервер 13.5 Мб
Integra.Premium MySQL 3.9 Мб

скачать поисковую систему SDK поисковой системыописание поисковой системы



SDK Поисковой системы



SDK Поискового движка
API для настольной и сетевой поисковая система 

платформа:  Windows XP ... Windows 7
размер:         17 Мб

Дополнительные компоненты:

MySQL поисковый сервер 13.5 Мб
Integra.Premium MySQL 3.9 Мб

скачать SDK SDK поисковой системы



Экранный переводчик



Translator
экранный переводчик

платформа:  Windows XP ... Windows 7
требования: 256 Mb свободной памяти
размер:         4.4 Мб

Дополнительные компоненты:
расширенный англо-русский словарь 6.4 Мб


скачать экранный переводчикописание экранного переводчика



изменено 29-Jul-12