Биграмма — это два слова, которые в тексте или, в нашем случае в корпусе текстов, являются соседними. Например в предложении:
Это было жарким летом . 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. Хотя там возможно придётся использовать блоки меньшего размера и чаще скидывать промежуточные результаты на диск.
Как мы и говорили в начале, детали реализации заслуживают отдельного разговора и о них мы расскажем в следующей статье.
Комментарии (19)
buriy
13.10.2016 01:58+1Есть усовершенствование вашего алгоритма, ускоряющее его работу в несколько раз и значительно снижающее требования к памяти.
Вам же скорее всего не нужен единый многогигабайтный файл со всеми биграммами, отсортированными по частоте.
Поэтому сохраняйте биграммы с разными начальными буквами в разные файлы (количество букв — 1 или 2, в других случаях вместо первых букв можно использовать хеш), и сортируете/мержите потом только соответствующий файл или группу этих файлов. При мерже каждой группы тогда всё войдёт в память компьютера.
При объединении группы в один файл можете так же делать морфологическую нормализацию и отсечку.
kdenisk
13.10.2016 18:17Идея интересная, но я бы не стал так делать. Бегать по корпусу 33 раза вместо одного выйдет гораздо дороже по времени, чем пробежаться один раз и потом объединить результаты.
buriy
13.10.2016 22:291) А ничего, что куски стали в 32 раза меньше? Поэтому вам не надо бегать по всему корпусу 33 раза — вы делите его один раз, и потом пробегаетесь уже по его кускам.
2) Во время merge вы тоже бегаете по корпусу — да и вообще, всегда, когда не получается бегать в памяти, мы бегаем по диску.
Эх, не хотел я вам приводить арифметику, думал, сами посчитаете выгоду.
Пусть вместо N строк после обработки кусков имеем K строк суммарно.
У меня N + K (вместо дисковых мержей можно сортировать в памяти)
У вас N + K log M (для мержей)kdenisk
14.10.2016 00:15Понял, экономим на слияниях. Не соглашусь, что экономия будет в несколько раз, т.к. самое дорогое — это сбор биграмм, а не агрегация. Но экономия, пусть и небольшая, определённо будет.
Получается такая статистика по корпусу:
Скрытый текста => 185.8M б => 421.7M в => 1121.2M г => 208.1M д => 475.4M е => 270.8M ж => 110.0M з => 303.9M и => 792.5M й => 5.1M к => 620.2M л => 167.8M м => 451.4M н => 1192.0M о => 791.1M п => 1136.1M р => 282.8M с => 1076.1M т => 512.9M у => 285.6M ф => 43.4M х => 88.7M ц => 31.6M ч => 363.2M ш => 48.3M щ => 11.0M ъ => 0.1M ы => 0.1M ь => 0.0M э => 191.4M ю => 7.9M я => 175.1M ё => 0.5M . => 9.3M SUM: 11381M
где цифра — количество в миллионах единиц биграмм на буквy X без учёта регистра. В память влезет.
GreyCat
13.10.2016 09:38+2По-моему, вы только что придумали и реализовали заново map-reduce. Чем не устроило взять готовый Hadoop?
kdenisk
13.10.2016 17:52Вы отчасти правы. Но порог вхождения в Hadoop довольно высокий и в данной задаче вполне достаточно использования стандартных инструментов Java.
GreyCat
13.10.2016 18:05Высокий?! Вы предлагаете написать ровно те же самые spill-merge-repeat штуки самостоятельно. Субъективно, это задача по хорошему на месяц-два. И граблей там на порядки больше, чем вы описали. Надо следить за состоянием JVM, надо уметь следить за состоянием подсистем сервера, на котором все выполняется. Довольно быстро станет ясно, что мультитредовость там абсолютно не нужна, зато нужно запускать пачки JVM и отслеживать их деятельность. Потребуются определенные средства диагностики и агрегации статистики. И т.д. и т.п.
Для сравнения — задача, которую вы описываете, делается из Hadoop'овского «hello world'а» (который «посчитать частотность слов в документах») одним тривиальным изменением map-функции. У меня студенты, которые ничего не знали про Hadoop и map-reduce вообще, осваивали такое максимум за час — и это включая «скачать hadoop», «подключить библиотеки к своей среде разработки» и т.д.kdenisk
13.10.2016 18:11Обязательно посмотрю в этом направлении. Скажу, однако, что реализация всей идеи заняла у меня несколько часов и все вычисления, а также действия по агрегации, производятся в рамках одной JVM.
trapwalker
13.10.2016 18:17+1Какая-то статья неполная. Вызывает недоумение нераскрытостью довольно очевидных вопросов. Я понимаю, что всё это можно найти через гугл и разобраться, но зачем тогда статья?
Так вот, почему-то нет ссылок на примеры корпусов для поиграться. Почему-то нет и намёка на хотя бы порядок размера такого корпуса. Нет никаких данных о том, какого порядка получаются размеры итоговых словарей N-грамм.
Те цифры, что я увидел на сайте opencorpora говорят, что все эти счетчики N-грамм вполне помещаются в памяти. Наверно автор не просто так поднимает проблему, а речь идет не о сотых пентиумах, но тогда тема явно не раскрыта.
И ещё. Я вот не понял один момент. Допустим корпус весит гигабайт. Не значит ли это, что перечень всех пар рядом стоящих слов будет не более чем вдвое превышать размер корпуса? А если убрать повторяения, то перечень уникальных пар будет ощутимо меньше удвоенного размера корпуса. Корпус весь в память помещать не нужно, достаточно обрабатывать его в потоке извлекая с HDD через буффер. А несколько гигов разместить в памяти современного компьютера в виде хеш-таблицы… по-моему это не проблема. Где я не прав?kdenisk
13.10.2016 18:29Давайте по порядку. Речь идёт о размере корпуса, скажем, в сто гигабайт. Из корпуса меньшего размера не получится вытащить информацию о редких двусочетаниях, она смешается с шумом. К сожалению в интернете чистого корпуса, чтобы вот так взять, скачать и работать — нет. Приходится собирать его по кусочкам, например:
https://dumps.wikimedia.org/ruwiki/ — дампы Википедии
http://lib.ru/ — художественная литература
и просто погулять по интернету, собирая недостающие пласты лексики.
Отвечая на второй вопрос. Сам корпус в память не загружается, вся память уходит только на счётчики. Если брать корпус размером в 100 гигабайт, то на выходе получается 12 гигабайт грязных биграмм из которых после отсечения по частотности >= 5 остаётся всего 2 гигабайта.
Ради них всё и делается.trapwalker
13.10.2016 20:44-1Вот отчего было в статье об этом не обмолвиться? Риторический вопрос.
А по задаче вашей забавно выходит. Счетчики самой редкой N-граммы и самой часто встречающейся занимают в памяти одинаковое количество места. Зато часто встречающиеся случаи нужно гораздо чаще инкрементировать. Это значит, что в оперативке можно держать столько высокочастотных N-грамм, сколько влезает, а остальные хранить на диске. Ещё нужно держать на заметке самую редкую N-грамму из тех что в оперативке. Тогда при обработке очередной пары мы ищем ее сперва в ОЗУ, а если не найдём, то на диске. После инкремента смотрим не стала ли эта пара более высокочастотной, чем самая редкая в ОЗУ. Если стала, то меняем их местами. Так высокочастотники будут всплывать с диска в ОЗУ вытесняя более редких сородичей на медленное хранилище. Дисковые операции медленные, поэтому их можно отделить через очередь в отдельный поток.
Это еще не все, что можно придумать. Слова N-грамм можно однозначно сжимать. Имея таблицу частот встречаемости символов или даже слогов можно выделять под них неодинаковое количество бит. То есть создать фактически свою бинарную кодировку, в которой буквы будут занимать меньше 8 бит. Это своеобразная обратимая «хеш-функция» без коллизий.
Ещё можно держать в ОЗУ небольшой индекс блоков медленного хранилища. Ключ там будет, например, CRC16 от N-граммы, а значение — номер блока в массиве на жестком диске. Это ускорит поиск по медленному хранилищу не вынуждая нас держать его полный индекс в оперативке (ведь он довольно большой получился бы).
Ну и, если поверх всего этого ваш блочный подход со слиянием прикрутить, то все получится еще и параллелить. Сливая пару таких словарей, разделенных по частотам между ОЗУ и диском мы можем быстро сливать оперативные их части, подтягивая с дисков всплывающие на освободившееся более редкие N-граммы.kdenisk
13.10.2016 22:28Наблюдение в самом деле интересное. Я посчитал, получается 1.5 миллиарда инкрементов на редкие двусочетания (меньше пяти единиц на корпус) и около 10 миллиардов на частые.
Но если брать реальные цифры, то получается следующее. Предложенный в статье подход работает со скоростью 2 минуты на гигабайт или 3.5 часа на корпус — расчёт. Плюс 1.5 часа на слияние, т.е. 5 часов на всё. Если включать время на разработку в общую стоимость решения задачи, то практически любое инженерное усложнение с большой вероятностью не окупится. Разве что при многократных пересчётах (но зачем?)
В любом случае спасибо вам за предложение возможных путей развития алгоритма — это ценно с точки зрения обсуждения и получения идей из решаемой задачи.trapwalker
13.10.2016 23:28+1Само собой все должно быть целесообразно. Вы, конечно, правы учитывая время на разработку и соотнося его с получаемой пользой. Даже если бы ваш алгоритм над ЭТОЙ задачей работал несколько суток или две недели, то, думаю, все равно самый простой подход был бы наиболее эффективным с практической точки зрения. Действительно, соберете ли вы за эти дни где-то еще столько разнообразного текста, чтобы нагрузить этот алгоритм на следующую неделю? Не думаю. Это одноразовая задача.
Однако, поупражняться в решении таких задач никогда не вредно. Сейчас у вас задача одноразовая, а, возможно, завтра у кого-то из читателей хабра появится похожая задача, но уже из области обработки биологических, статистических или физических данных, которые прут с неимоверной скоростью и в огромных количествах. Не знаю даже что бы это могло быть: может быть цепочки нуклеотидов ДНК или данные с большого адронного коллайдера, но какие-то похожие потребности могут возникнуть и полезно придумать пару приемчиков «про запас».
Вот, к примеру, давайте представим, что мы гугл и через наш мессенджер льётся гигабайтами текст и всякая переписка. Очевидно, что там не совсем тот язык, что встречается в литературе или википедии, а нам нужно настроить экранную клавиатуру так, чтобы она работала особенно хорошо в нашем мессенджере. На какие-нибудь аж пол процента лучше аналогов (или 15% что уже не так и смешно). Тут нам надо сидеть на потоке и постоянно мониторить тенденции.
Кстати! Можно же отслеживая динамику по журналу всплытия и опускания n-грамм в отсортированном частотном словаре попробовать проследить за тенденциями и закономерностями в нашем хаотичном мире.
temp
13.10.2016 19:13Биграмма — это два слова, которые в тексте или, в нашем случае в корпусе текстов, являются соседними.
Вообще n-gram и в частности bi-gram может также применятся к буквам и фонемам. Например n-gram фонем используются в speach recognition, а n-gram букв в language identification.
По теме статьи, имеет смысл обратить внимание на Spark MLib feature Extraction, который решает проблему генерации n-gram в map-reduce и множество других.kdenisk
13.10.2016 20:33Вообще n-gram и в частности bi-gram может также применяться к буквам и фонемам. Например n-gram фонем используются в speach recognition, а n-gram букв в language identification.
Хорошее замечание. Не было в статье, чтобы не перегружать вводную часть излишними сведениями.
Спасибо за ссылку на Spark, будет интересно покопаться.
trapwalker
13.10.2016 23:36Кстати. Сейчас же бурно растут микросервисы! Наверняка, возьмись, скажем, umputun решать эту задачу, он не стал бы греть воздух своим макбуком, а снял бы на амазоне минут на 10 виртуалочку, которая этот корпус протянет через оперативку целиком и не подавится. Тоже, кстати, прокатило бы простое решение, правда с большей заточкой на очереди и потоки.
grossws
Если вым нужны только частотные биграммы, то можно пойти от следующего утверждения: в любую биграмму с встречаемостью не ниже
sвходят токены с встречаемостью не нижеs.Т. е. можно в первый проход посчитать статистику токенов и получить в итоге множество токенов (hash set с доступом за
O(1)) имеющих встречаемость не ниже некоторогоs.Далее, при построение биграмм необходимо проверять оба токена, и, если, хотя бы один токен не входит в построенное множество, то эта биграмма не может быть частотной.
Такое подход сильно уменьшит требования к памяти для работы. В англоязычной литературе группа таких алгоритмов называется a-priori.
Рекомендую курс MMDS от Ульмана и ко (лекции и бесплатную книжку). Про a-priori см. главу 6.
Следующим улучшением будет PCY который позволяет отфильтровать кандидатов на высокочастотные пары с использованием структуры напоминающей фильтр Блума.
kdenisk
Совершенно верное и правильно замечание. К сожалению для подсчёта двусочетаний такой подход не применим, т.к. у юниграмм частотность высокая почти у всех. Для триграмм и выше — очень помогает.
grossws
Если все униграммы более-менее высокочастотны, то можно взять PCY и отбросить первый шаг (фильтрацию по частотке униграмм), но оставить их аналог фильтра Блума. Он с некоторой вероятностью позволит отбросить группы низкочастотных биграмм.