Comments 19
Если вым нужны только частотные биграммы, то можно пойти от следующего утверждения: в любую биграмму с встречаемостью не ниже s входят токены с встречаемостью не ниже s.
Т. е. можно в первый проход посчитать статистику токенов и получить в итоге множество токенов (hash set с доступом за O(1)) имеющих встречаемость не ниже некоторого s.
Далее, при построение биграмм необходимо проверять оба токена, и, если, хотя бы один токен не входит в построенное множество, то эта биграмма не может быть частотной.
Такое подход сильно уменьшит требования к памяти для работы. В англоязычной литературе группа таких алгоритмов называется a-priori.
Рекомендую курс MMDS от Ульмана и ко (лекции и бесплатную книжку). Про a-priori см. главу 6.
Следующим улучшением будет PCY который позволяет отфильтровать кандидатов на высокочастотные пары с использованием структуры напоминающей фильтр Блума.
Есть усовершенствование вашего алгоритма, ускоряющее его работу в несколько раз и значительно снижающее требования к памяти.
Вам же скорее всего не нужен единый многогигабайтный файл со всеми биграммами, отсортированными по частоте.
Поэтому сохраняйте биграммы с разными начальными буквами в разные файлы (количество букв — 1 или 2, в других случаях вместо первых букв можно использовать хеш), и сортируете/мержите потом только соответствующий файл или группу этих файлов. При мерже каждой группы тогда всё войдёт в память компьютера.
При объединении группы в один файл можете так же делать морфологическую нормализацию и отсечку.
Вам же скорее всего не нужен единый многогигабайтный файл со всеми биграммами, отсортированными по частоте.
Поэтому сохраняйте биграммы с разными начальными буквами в разные файлы (количество букв — 1 или 2, в других случаях вместо первых букв можно использовать хеш), и сортируете/мержите потом только соответствующий файл или группу этих файлов. При мерже каждой группы тогда всё войдёт в память компьютера.
При объединении группы в один файл можете так же делать морфологическую нормализацию и отсечку.
Идея интересная, но я бы не стал так делать. Бегать по корпусу 33 раза вместо одного выйдет гораздо дороже по времени, чем пробежаться один раз и потом объединить результаты.
1) А ничего, что куски стали в 32 раза меньше? Поэтому вам не надо бегать по всему корпусу 33 раза — вы делите его один раз, и потом пробегаетесь уже по его кускам.
2) Во время merge вы тоже бегаете по корпусу — да и вообще, всегда, когда не получается бегать в памяти, мы бегаем по диску.
Эх, не хотел я вам приводить арифметику, думал, сами посчитаете выгоду.
Пусть вместо N строк после обработки кусков имеем K строк суммарно.
У меня N + K (вместо дисковых мержей можно сортировать в памяти)
У вас N + K log M (для мержей)
2) Во время merge вы тоже бегаете по корпусу — да и вообще, всегда, когда не получается бегать в памяти, мы бегаем по диску.
Эх, не хотел я вам приводить арифметику, думал, сами посчитаете выгоду.
Пусть вместо N строк после обработки кусков имеем K строк суммарно.
У меня N + K (вместо дисковых мержей можно сортировать в памяти)
У вас N + K log M (для мержей)
Понял, экономим на слияниях. Не соглашусь, что экономия будет в несколько раз, т.к. самое дорогое — это сбор биграмм, а не агрегация. Но экономия, пусть и небольшая, определённо будет.
Получается такая статистика по корпусу:
Получается такая статистика по корпусу:
Скрытый текст
где цифра — количество в миллионах единиц биграмм на буквy X без учёта регистра. В память влезет.
а => 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 без учёта регистра. В память влезет.
По-моему, вы только что придумали и реализовали заново map-reduce. Чем не устроило взять готовый Hadoop?
Вы отчасти правы. Но порог вхождения в Hadoop довольно высокий и в данной задаче вполне достаточно использования стандартных инструментов Java.
Высокий?! Вы предлагаете написать ровно те же самые spill-merge-repeat штуки самостоятельно. Субъективно, это задача по хорошему на месяц-два. И граблей там на порядки больше, чем вы описали. Надо следить за состоянием JVM, надо уметь следить за состоянием подсистем сервера, на котором все выполняется. Довольно быстро станет ясно, что мультитредовость там абсолютно не нужна, зато нужно запускать пачки JVM и отслеживать их деятельность. Потребуются определенные средства диагностики и агрегации статистики. И т.д. и т.п.
Для сравнения — задача, которую вы описываете, делается из Hadoop'овского «hello world'а» (который «посчитать частотность слов в документах») одним тривиальным изменением map-функции. У меня студенты, которые ничего не знали про Hadoop и map-reduce вообще, осваивали такое максимум за час — и это включая «скачать hadoop», «подключить библиотеки к своей среде разработки» и т.д.
Для сравнения — задача, которую вы описываете, делается из Hadoop'овского «hello world'а» (который «посчитать частотность слов в документах») одним тривиальным изменением map-функции. У меня студенты, которые ничего не знали про Hadoop и map-reduce вообще, осваивали такое максимум за час — и это включая «скачать hadoop», «подключить библиотеки к своей среде разработки» и т.д.
Какая-то статья неполная. Вызывает недоумение нераскрытостью довольно очевидных вопросов. Я понимаю, что всё это можно найти через гугл и разобраться, но зачем тогда статья?
Так вот, почему-то нет ссылок на примеры корпусов для поиграться. Почему-то нет и намёка на хотя бы порядок размера такого корпуса. Нет никаких данных о том, какого порядка получаются размеры итоговых словарей N-грамм.
Те цифры, что я увидел на сайте opencorpora говорят, что все эти счетчики N-грамм вполне помещаются в памяти. Наверно автор не просто так поднимает проблему, а речь идет не о сотых пентиумах, но тогда тема явно не раскрыта.
И ещё. Я вот не понял один момент. Допустим корпус весит гигабайт. Не значит ли это, что перечень всех пар рядом стоящих слов будет не более чем вдвое превышать размер корпуса? А если убрать повторяения, то перечень уникальных пар будет ощутимо меньше удвоенного размера корпуса. Корпус весь в память помещать не нужно, достаточно обрабатывать его в потоке извлекая с HDD через буффер. А несколько гигов разместить в памяти современного компьютера в виде хеш-таблицы… по-моему это не проблема. Где я не прав?
Так вот, почему-то нет ссылок на примеры корпусов для поиграться. Почему-то нет и намёка на хотя бы порядок размера такого корпуса. Нет никаких данных о том, какого порядка получаются размеры итоговых словарей N-грамм.
Те цифры, что я увидел на сайте opencorpora говорят, что все эти счетчики N-грамм вполне помещаются в памяти. Наверно автор не просто так поднимает проблему, а речь идет не о сотых пентиумах, но тогда тема явно не раскрыта.
И ещё. Я вот не понял один момент. Допустим корпус весит гигабайт. Не значит ли это, что перечень всех пар рядом стоящих слов будет не более чем вдвое превышать размер корпуса? А если убрать повторяения, то перечень уникальных пар будет ощутимо меньше удвоенного размера корпуса. Корпус весь в память помещать не нужно, достаточно обрабатывать его в потоке извлекая с HDD через буффер. А несколько гигов разместить в памяти современного компьютера в виде хеш-таблицы… по-моему это не проблема. Где я не прав?
Давайте по порядку. Речь идёт о размере корпуса, скажем, в сто гигабайт. Из корпуса меньшего размера не получится вытащить информацию о редких двусочетаниях, она смешается с шумом. К сожалению в интернете чистого корпуса, чтобы вот так взять, скачать и работать — нет. Приходится собирать его по кусочкам, например:
https://dumps.wikimedia.org/ruwiki/ — дампы Википедии
http://lib.ru/ — художественная литература
и просто погулять по интернету, собирая недостающие пласты лексики.
Отвечая на второй вопрос. Сам корпус в память не загружается, вся память уходит только на счётчики. Если брать корпус размером в 100 гигабайт, то на выходе получается 12 гигабайт грязных биграмм из которых после отсечения по частотности >= 5 остаётся всего 2 гигабайта.
Ради них всё и делается.
https://dumps.wikimedia.org/ruwiki/ — дампы Википедии
http://lib.ru/ — художественная литература
и просто погулять по интернету, собирая недостающие пласты лексики.
Отвечая на второй вопрос. Сам корпус в память не загружается, вся память уходит только на счётчики. Если брать корпус размером в 100 гигабайт, то на выходе получается 12 гигабайт грязных биграмм из которых после отсечения по частотности >= 5 остаётся всего 2 гигабайта.
Ради них всё и делается.
Вот отчего было в статье об этом не обмолвиться? Риторический вопрос.
А по задаче вашей забавно выходит. Счетчики самой редкой N-граммы и самой часто встречающейся занимают в памяти одинаковое количество места. Зато часто встречающиеся случаи нужно гораздо чаще инкрементировать. Это значит, что в оперативке можно держать столько высокочастотных N-грамм, сколько влезает, а остальные хранить на диске. Ещё нужно держать на заметке самую редкую N-грамму из тех что в оперативке. Тогда при обработке очередной пары мы ищем ее сперва в ОЗУ, а если не найдём, то на диске. После инкремента смотрим не стала ли эта пара более высокочастотной, чем самая редкая в ОЗУ. Если стала, то меняем их местами. Так высокочастотники будут всплывать с диска в ОЗУ вытесняя более редких сородичей на медленное хранилище. Дисковые операции медленные, поэтому их можно отделить через очередь в отдельный поток.
Это еще не все, что можно придумать. Слова N-грамм можно однозначно сжимать. Имея таблицу частот встречаемости символов или даже слогов можно выделять под них неодинаковое количество бит. То есть создать фактически свою бинарную кодировку, в которой буквы будут занимать меньше 8 бит. Это своеобразная обратимая «хеш-функция» без коллизий.
Ещё можно держать в ОЗУ небольшой индекс блоков медленного хранилища. Ключ там будет, например, CRC16 от N-граммы, а значение — номер блока в массиве на жестком диске. Это ускорит поиск по медленному хранилищу не вынуждая нас держать его полный индекс в оперативке (ведь он довольно большой получился бы).
Ну и, если поверх всего этого ваш блочный подход со слиянием прикрутить, то все получится еще и параллелить. Сливая пару таких словарей, разделенных по частотам между ОЗУ и диском мы можем быстро сливать оперативные их части, подтягивая с дисков всплывающие на освободившееся более редкие N-граммы.
А по задаче вашей забавно выходит. Счетчики самой редкой N-граммы и самой часто встречающейся занимают в памяти одинаковое количество места. Зато часто встречающиеся случаи нужно гораздо чаще инкрементировать. Это значит, что в оперативке можно держать столько высокочастотных N-грамм, сколько влезает, а остальные хранить на диске. Ещё нужно держать на заметке самую редкую N-грамму из тех что в оперативке. Тогда при обработке очередной пары мы ищем ее сперва в ОЗУ, а если не найдём, то на диске. После инкремента смотрим не стала ли эта пара более высокочастотной, чем самая редкая в ОЗУ. Если стала, то меняем их местами. Так высокочастотники будут всплывать с диска в ОЗУ вытесняя более редких сородичей на медленное хранилище. Дисковые операции медленные, поэтому их можно отделить через очередь в отдельный поток.
Это еще не все, что можно придумать. Слова N-грамм можно однозначно сжимать. Имея таблицу частот встречаемости символов или даже слогов можно выделять под них неодинаковое количество бит. То есть создать фактически свою бинарную кодировку, в которой буквы будут занимать меньше 8 бит. Это своеобразная обратимая «хеш-функция» без коллизий.
Ещё можно держать в ОЗУ небольшой индекс блоков медленного хранилища. Ключ там будет, например, CRC16 от N-граммы, а значение — номер блока в массиве на жестком диске. Это ускорит поиск по медленному хранилищу не вынуждая нас держать его полный индекс в оперативке (ведь он довольно большой получился бы).
Ну и, если поверх всего этого ваш блочный подход со слиянием прикрутить, то все получится еще и параллелить. Сливая пару таких словарей, разделенных по частотам между ОЗУ и диском мы можем быстро сливать оперативные их части, подтягивая с дисков всплывающие на освободившееся более редкие N-граммы.
Наблюдение в самом деле интересное. Я посчитал, получается 1.5 миллиарда инкрементов на редкие двусочетания (меньше пяти единиц на корпус) и около 10 миллиардов на частые.
Но если брать реальные цифры, то получается следующее. Предложенный в статье подход работает со скоростью 2 минуты на гигабайт или 3.5 часа на корпус — расчёт. Плюс 1.5 часа на слияние, т.е. 5 часов на всё. Если включать время на разработку в общую стоимость решения задачи, то практически любое инженерное усложнение с большой вероятностью не окупится. Разве что при многократных пересчётах (но зачем?)
В любом случае спасибо вам за предложение возможных путей развития алгоритма — это ценно с точки зрения обсуждения и получения идей из решаемой задачи.
Но если брать реальные цифры, то получается следующее. Предложенный в статье подход работает со скоростью 2 минуты на гигабайт или 3.5 часа на корпус — расчёт. Плюс 1.5 часа на слияние, т.е. 5 часов на всё. Если включать время на разработку в общую стоимость решения задачи, то практически любое инженерное усложнение с большой вероятностью не окупится. Разве что при многократных пересчётах (но зачем?)
В любом случае спасибо вам за предложение возможных путей развития алгоритма — это ценно с точки зрения обсуждения и получения идей из решаемой задачи.
Само собой все должно быть целесообразно. Вы, конечно, правы учитывая время на разработку и соотнося его с получаемой пользой. Даже если бы ваш алгоритм над ЭТОЙ задачей работал несколько суток или две недели, то, думаю, все равно самый простой подход был бы наиболее эффективным с практической точки зрения. Действительно, соберете ли вы за эти дни где-то еще столько разнообразного текста, чтобы нагрузить этот алгоритм на следующую неделю? Не думаю. Это одноразовая задача.
Однако, поупражняться в решении таких задач никогда не вредно. Сейчас у вас задача одноразовая, а, возможно, завтра у кого-то из читателей хабра появится похожая задача, но уже из области обработки биологических, статистических или физических данных, которые прут с неимоверной скоростью и в огромных количествах. Не знаю даже что бы это могло быть: может быть цепочки нуклеотидов ДНК или данные с большого адронного коллайдера, но какие-то похожие потребности могут возникнуть и полезно придумать пару приемчиков «про запас».
Вот, к примеру, давайте представим, что мы гугл и через наш мессенджер льётся гигабайтами текст и всякая переписка. Очевидно, что там не совсем тот язык, что встречается в литературе или википедии, а нам нужно настроить экранную клавиатуру так, чтобы она работала особенно хорошо в нашем мессенджере. На какие-нибудь аж пол процента лучше аналогов (или 15% что уже не так и смешно). Тут нам надо сидеть на потоке и постоянно мониторить тенденции.
Кстати! Можно же отслеживая динамику по журналу всплытия и опускания n-грамм в отсортированном частотном словаре попробовать проследить за тенденциями и закономерностями в нашем хаотичном мире.
Однако, поупражняться в решении таких задач никогда не вредно. Сейчас у вас задача одноразовая, а, возможно, завтра у кого-то из читателей хабра появится похожая задача, но уже из области обработки биологических, статистических или физических данных, которые прут с неимоверной скоростью и в огромных количествах. Не знаю даже что бы это могло быть: может быть цепочки нуклеотидов ДНК или данные с большого адронного коллайдера, но какие-то похожие потребности могут возникнуть и полезно придумать пару приемчиков «про запас».
Вот, к примеру, давайте представим, что мы гугл и через наш мессенджер льётся гигабайтами текст и всякая переписка. Очевидно, что там не совсем тот язык, что встречается в литературе или википедии, а нам нужно настроить экранную клавиатуру так, чтобы она работала особенно хорошо в нашем мессенджере. На какие-нибудь аж пол процента лучше аналогов (или 15% что уже не так и смешно). Тут нам надо сидеть на потоке и постоянно мониторить тенденции.
Кстати! Можно же отслеживая динамику по журналу всплытия и опускания n-грамм в отсортированном частотном словаре попробовать проследить за тенденциями и закономерностями в нашем хаотичном мире.
Биграмма — это два слова, которые в тексте или, в нашем случае в корпусе текстов, являются соседними.
Вообще n-gram и в частности bi-gram может также применятся к буквам и фонемам. Например n-gram фонем используются в speach recognition, а n-gram букв в language identification.
По теме статьи, имеет смысл обратить внимание на Spark MLib feature Extraction, который решает проблему генерации n-gram в map-reduce и множество других.
Вообще n-gram и в частности bi-gram может также применяться к буквам и фонемам. Например n-gram фонем используются в speach recognition, а n-gram букв в language identification.
Хорошее замечание. Не было в статье, чтобы не перегружать вводную часть излишними сведениями.
Спасибо за ссылку на Spark, будет интересно покопаться.
Кстати. Сейчас же бурно растут микросервисы! Наверняка, возьмись, скажем, umputun решать эту задачу, он не стал бы греть воздух своим макбуком, а снял бы на амазоне минут на 10 виртуалочку, которая этот корпус протянет через оперативку целиком и не подавится. Тоже, кстати, прокатило бы простое решение, правда с большей заточкой на очереди и потоки.
Sign up to leave a comment.
Как собрать биграммы для корпуса любого размера на домашнем компьютере