В современной компьютерной лингвистике биграммы, или в общем случае n-граммы, являются важным статистическим инструментом. В статье мы расскажем с какими трудностями можно столкнуться при расчёте биграмм на большом корпусе текстов и приведём алгоритм, который можно использовать на любом домашнем компьютере.
Биграмма — это два слова, которые в тексте или, в нашем случае в корпусе текстов, являются соседними. Например в предложении:
Это было жарким летом . 1 2 3 4 5 (пробел после "летом" не является опечаткой или ошибкой)
будут такие биграммы:
- Это было
- было жарким
- жарким летом
- летом .
Строго говоря биграммы состоят не из слов, а из токенов. Токеном, т.е. неделимой единицей в рамках нашей задачи, будет либо слово, либо пунктуационный знак. Токенизация — непростая тема, поэтому будем считать, что наш корпус уже токенизирован и разбит на предложения, а чтобы преобразовать предложение в список токенов, достаточно разбить его по пробелу.
Нашей задачей будет получить такой список:
- Это было 190360
- было жарким 1017
- жарким летом 2621
- летом . 42146
где число показывает сколько раз встречается биграмма во всём корпусе.
Иногда в тексте мы позволим себе использовать термин двусочетание в качестве синонима к слову биграмма.
В данной статье мы намерено опустили все детали реализации, т.к. подход интересен сам по себе и реализовать его несложно на вашем любимом языке программирования. К тому же реализация содержит в себе достаточное количество интересных деталей, чтобы поговорить о ней в отдельной статье. Минимальное количество поясняющих ремарок будет даваться на языке Java.
Наивный подход
- бежать по корпусу
- из каждого предложения выделять биграммы
- считать их с помощью структуры данных мультимножество (на Java это Multiset<String> или ConcurrentHashMultiset<String> в многопоточном варианте)
На относительно небольшом и чистом корпусе может сработать, но в общем случае при наивном подходе память у вас закончится раньше, чем вы успеете посчитать весь массив текстов.
Добавляем промежуточные отсечения
Наивный подход очень просто превратить в рабочий, если немного его модифицировать:
- бежать по корпусу
- из каждого предложения выделять биграммы
- считать их с помощью мультимножества
- как только видим, что заканчивается память — чистим счётчик, удаляя биграммы, которые встретились к этому моменту меньше чем пороговое число раз
Эта модификация даёт вполне рабочий алгоритм, но отсечения приносят одну неприятность: вместе с ненужным шумом, каким являются нерегулярные опечатки и ошибки, мы удалим множество полезной информации о редких словах. Например, если лексема (набор словоформ) встречается в корпусе 1000 раз, то каждая её отдельная словоформа может встречаться, скажем, меньше 200 раз на корпус, а что уже говорить о двусочетаниях.
Наша задача состоит в том, чтобы посчитать биграммы максимально честно, не используя промежуточных отсечений.
Используем диск в качестве временной памяти
Оперативная память сейчас стоит относительно недорого, но всё же стоит. К тому же на многие варианты ноутбуков больше 16 гигабайт вы не установите при всём желании — ограничение платформы. С дисковым же пространством никаких проблем нет — стоит оно существенно дешевле и при желании вы всегда можете использовать внешний накопитель.
При упоминании смысловых тегов #жёсткий_диск и #алгоритм в памяти всплывают алгоритмы сортировки слиянием (merge sort) и объединения упорядоченных списков, которые многие писали в школе ещё на языке Pascal. Идеи, заложенные в основе этих алгоритмов, как никак хорошо подходят для решения нашей задачи.
Принципиальная схема решения задачи
Прежде чем перейти к деталям, представим принципиальную схему решения поставленной задачи:
- Разбить корпус на примерно равные блоки, скажем по 1 гигабайту.
- Посчитать биграммы отдельно для каждого блока, отсортировать их в лексикографическом порядке и записать на диск.
- Используя алгоритм слияния упорядоченных списков, объединить отдельные файлы с двусочетаниями в один, суммируя количество вхождений для совпадающих биграмм.
Размер каждого блока можно выбирать по вкусу (читай: по количеству установленной оперативной памяти), но в большинстве задач размер в гигабайт оказывается более чем удобным. Также можно работать с монолитным корпусом, делая в программе отсечки по размеру обработанного текста, скидывая результат на диск и очищая структуры данных.
Посмотрев на алгоритм с высоты птичьего полёта можно перейти к деталям.
Считаем биграммы для каждого блока
Чтобы построить оптимальную архитектуру для счётчика двусочетаний, учтём два важных требования:
- Хотим считать в несколько потоков.
- На выходе нужно получить отсортированный в лексикографическом порядке список биграмм.
Так получается, что эти две задачи можно эффективно решать вместе. Предлагается вместо использования одноуровневой карты (мультимножество это по сути карта ключ-счётчик)
ConcurrentHashMultiset<String>
для подсчёта биграмм использовать карту карт:
ConcurrentMap<String, ConcurrentHashMultiset<String>>
Эксперимент показывает, что многопоточный расчёт двусочетаний с использованием обеих структур данных выполняется примерно за одинаковое время, а вот сортировка при использовании двухуровневой карты выполняется намного быстрее, т.к. можно сортировать ключи внешней и внутренней карты независимо.
Ещё одно важнейшее преимущество, которое даёт использование двухуровневой карты: можно очень быстро делать дополнительную фильтрацию по словам биграммы. Например проверить их вхождение в словарь или даже выполнить нормализацию (быстрой ездой -> быстрая езда). Производить эти операции до того, как вы сгруппировали одинаковые двусочетания очень накладно, т.к. одна и та же операция будет производится множество раз.
Объединяем результаты по всем блокам
Итак, на выходе предыдущего алгоритма мы имеем множество файлов с записями вида:
bigram1 count1
bigram2 count2
...
bigramN countN
где ключи отсортированы в лексикографическом порядке. Наша задача объединить эти файлы в один, суммируя количество вхождений для совпадающих ключей. Задачу суммирования двух файлов будем считать тривиальной и оставим без дополнительных пояснений.
Общую задачу объединения всех файлов можно решить с использованием файла-аккумулятора, последовательно прибавляя к нему файлы отдельных блоков:
((((((N1 + N2) + N3) + N4) + N5) + N6) + N7)...
Однако этот поход неэффективен, т.к. спустя некоторое количество итераций мы будем прибавлять к относительно большому аккумулятору сравнительно небольшие файлы отдельных блоков и большую часть времени тратить на чтение данных с диска и запись на диск. Гораздо выгоднее выстроить такую стратегию, где на каждой итерации будут суммироваться блоки примерно равного размера, ведь совпадающие ключи схлопнутся в одну запись и итоговый файл получится по размеру меньше суммы двух исходных.
Для реализации отлично подходит костяк сортировки слиянием, использующий рекурсию. Схематично для 15 файлов это будет выглядеть так (у функции merge первый индекс включен, второй — исключён):
|_ merge(0, 15) = merge(0, 7) + merge(7, 15)
|_ merge(0, 7) = merge(0, 3) + merge(3, 7)
|_ merge(0, 3) = 0 + merge(1, 3)
|_ merge(1, 3) = 1 + 2
|_ merge(3, 7) = merge(3, 5) + merge(5, 7)
|_ merge(3, 5) = 3 + 4
|_ merge(5, 7) = 5 + 6
|_ merge(7, 15) = merge(7, 11) + merge(11, 15)
|_ merge(7, 11) = merge(7, 9) + merge(9, 11)
|_ merge(7, 9) = 7 + 8
|_ merge(9, 11) = 9 + 10
|_ merge(11, 15) = merge(11, 13) + merge(13, 15)
|_ merge(11, 13) = 11 + 12
|_ merge(13, 15) = 13 + 14
В результате алгоритм сделает те же 14 слияний, но отработает при этом гораздо эффективнее варианта с аккумулятором. Теоретические требования по памяти у алгоритма слияния O(1), а на практике память выделяется только под буферы чтения и записи.
В заключение
Используя приведённый подход можно собирать по корпусу не только биграммы, но и n-граммы для любого n. Хотя там возможно придётся использовать блоки меньшего размера и чаще скидывать промежуточные результаты на диск.
Как мы и говорили в начале, детали реализации заслуживают отдельного разговора и о них мы расскажем в следующей статье.
Автор: kdenisk
