Козиев Илья (kelijah) wrote,
Козиев Илья
kelijah

Categories:

Частота употребления предлогов (черновик)

Краткая постановка задачи

Есть набор файлов с текстами на русском языке от художественной литературы разных жанров до новостных сообщений. Нужно собрать статистику употребления предлогов с другими частями речи.

Важные моменты в задаче

1. Среди предлогов есть не только у и к, но устойчивые сочетания слов, употребляющиеся в качестве предлогов, например в сравнении с или несмотря на. Поэтому просто покрошить тексты по пробелам нельзя.

2. Текстов много, несколько Гб, поэтому обработка должна быть достаточно быстрой, по крайней мере укладываться в несколько часов.

Наброски решения и результаты

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

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

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

Разбивка текста на слова

Так как исходные тексты, подлежащие обработке, уже хранятся как плоские файлы в кодировке utf-8, то нулевой этап - парсинг документов, выдергивание из них текстового содержимого и сохранение в виде простых текстовиков, пропускаем, сразу переходя к задаче токенизации.

Все было бы просто и скучно, если бы не тот простой факт, что некоторые предлоги в русском языке состоят из нескольких "строк", разделяемых пробелом, а иногда и запятой. Чтобы не раскрошить такие многословные предлоги, сначала я привлек функцию токенизации в API словаря. Макет на C# получился простой и незамысловатый, буквально сотня строк. Вот исходник. Если отбросить вступительную часть, загрузку словаря и финальную часть с его удалением, то все сводится к паре десятков строк.

Все это успешно перемалывает файлы, но на тестах обнаружился существенный недостаток - очень низкая скорость. На x64 платформе получилось примерно 0.5 Мб в минуту. Конечно, токенизатор учитывает всевозможные особые случаи типа "А.С. Пушкин", но для решения исходной задачи такая точность излишня.

В качестве ориентира на возможную скорость имеется утилита статистической обработки файлов Empirika. Она делает частотную обработку 22 Гб текстов примерно за 2 часа. Там внутри есть и более шустрое решение проблемы многословных предлогов, поэтому я добавил новый сценарий, включаемый опцией -tokenize в командной строке. По результатам прогона получилось примерно 500 секунд на 900 Мб, то есть около 1.6 Мб в секунду.

Результат работы с этими 900 Мб текста - файл примерно такого же размера, 900 Мб. Каждое слово сохранено на отдельной строке.

Частота употребления предлогов

Теперь можно подсчитать количество употреблений предлогов с другими словами.

Так как вбивать список предлогов в текст программы не хотелось, я опять-таки подцепил к C# проекту грамматический словарь, с помощью функции sol_ListEntries получил полный список предлогов, около 140 штук, ну а далее все тривиально. Текст програмки на C# лежит здесь. Она собирает только пары предлог+слово, но расширить проблем не составит.

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

ПРО    РАЗБИТЫЕ    3
ПРО    ЗАБИТЫЕ    1
ПРО    ФОРМУ    1
ПРО    НОРМУ    1
ПРО    ГОЛОДАВШИЙ    1
В    ЗАКОННОМ    9
С    ТЕРРАСКИ    1
НЕСМОТРЯ НА    ЛЕНТУ    1
НАД    ЯЩИКОМ    14

Всего из исходных 900 Мб текста получилось примерно 600 тысяч пар.

Анализ и просмотр результатов

Таблицу с результатами удобно анализировать в Excel или Access. Я в силу привычки к SQL загрузил данные в Access.

Первое, что можно сделать - отсортировать результаты в порядке убывания частоты, чтобы увидеть самые частые пары. Исходный объем обработанного текста слишком мал, поэтому выборка не очень репрезентативна и может отличаться от итоговых результатов, но вот первая десятка:

У НАС    29193
В ТОМ    26070
У МЕНЯ    25843
О ТОМ    24410
У НЕГО    22768
В ЭТОМ    22502
В РАЙОНЕ    20749
ВО ВРЕМЯ    20545
ОБ ЭТОМ    18761
С НИМ    18411

Теперь можно построить график, так чтобы частоты было по оси OY, а паттерны выстроились вдоль OX по убыванию. Это даст вполне ожидаемое распределение с длиннющим хвостом:



Зачем нужна эта статистика

Кроме того факта, что две утилитки на C# могут использоваться для демонстрации работы с процедурным API, есть еще важная цель - дать переводчику и алгоритму реконструкции текста статистическое сырье. Кроме пар слов еще потребуются триграммы, для этого надо будет немного расширить вторую из упомянутых утилиту.
Tags: N-граммы, статистика
Subscribe
  • Post a new comment

    Error

    Anonymous comments are disabled in this journal

    default userpic

    Your reply will be screened

  • 0 comments