Как эффективно составить гистограмму слов (big data)?

Question

[Александр Куракин]

Есть набор (десятки гигабайт) файлов, в которых приведены слова в нижнем регистре, разделённые пробельными символами.

Ищу эффективный способ составить гистограмму слов. До чего там сейчас техника дошла?

1. a library (I'm a programmer), one node;
   
2. a library (I'm a programmer), many nodes;
   
3. a GUI tool, one node;
   
4. a GUI tool, many node.
   

Comments

[Михаил]

С помощью либы PySpark можно (обёртка над Apache Spark)

[d'Ivan]

Что за гистограмма слов?

[Александр Куракин]

Мойше Рабинович, слово - количество

[Александр Куракин]

Михаил, спасибо! а может есть какая-то реализация готовая для моей задачи?

[Михаил]

Александр Куракин, тут уже не подскажу по реализациям)
Есть готовые инструменты типа Amazon EMR и Google Dataproc, но это уже копаться надо как там и что)

[Модератор]

Не надо ставить как можно больше тэгов. Лучше оставить один, но конкретный, с которым проблема.
См.п.3.1 Регламента. Также обратите внимание на п.3.4

[Модератор]

На вопрос «как сделать» отвечает документация и поиск в интернет.

Тут отвечают на вопросы «почему я сделал, как в документации, а оно не работает. Поискал в интернет, вот запросы, в ответах не нашел. Что я делаю не так?»

Покажите, как вы пробовали решить проблему, приведите код попытки (пусть неудачной), опишите, как запускали, что ожидали и что получилось.
За готовыми решениями - на фриланс. В текущем виде это не вопрос, а задание. Нарушен п.5.12 Регламента.

[Александр Куракин]

Модератор, спасибо за замечание.

Касаемо самого вопроса, то он подразумевает современных, эффективных, лучших подходов среди тех, что есть в документациях.

Answer 1

[Wataru]

Если реализовывать самостоятельно, то самый эффективный вариант - использовать структуру бор. Правда, тут надо чтобы все файлы влезли в память.

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

Если памяти на компьютере не 64-128гб, и писать что-то не хочется, то можно файл отсортировать и потом подсчитать там повторения за один проход. Это будет чуть медленнее теоретически оптимального решения. rPman уже привел линуксовую команду, которая это делает. Только разбивать на части просто так нельзя, надо чтобы одинаковые строки остались вместе, иначе собирать ответ с нескольких кусков надо будет хитро. Но это и не надо в вашей задаче.

Если же вы что-то распределенное все-таки хотите использовать, то ваша задача - это фактически обучающий пример для всяких map-reduce фреймворков типа hadoop. Но там придется повозиться с установкой и настройкой этого добра и код с примера скопировать.

Comments

[Александр Куракин]

спасибо!

[rPman]

Надо подчеркнуть что эта структура нужна для хранения словаря слово => количество
не уверен, какая именно технология используется в stdlib c++ для map (вполне возможно что на основе hashmap), и если честно, объемы (количество слов а не данных) при которых имеет смысл заморачиваться с древовидными структурами, должны быть ну очень огромными, столько нет слов в естественных языках.
upd.

maps are implemented as Binary Search Trees, unordered maps as hash tables

сортировать и считать как я показал эффективно,только если отдельные куски (файлы) будут небольшого размера, итоговые числа нужно будет складывать другим способом (например отдельным потоковым приложением или даже базой данных), в итоге если заморачиваться со своим приложением, все что я описал можно заменить простеньким и эффективным кодом на основе std map

[Wataru]

rPman, map занимает больше памяти, чем бор. И работает в log n раз медленнее (так же, как и сортировка). unordered_map на основе хеш таблицы будет быстрее, но все равно больше памяти требует.

Но, опять же, если все помещается на один компьютер, то писать ничего и не надо.

[Александр Куракин]

Wataru, А с теоретической точки зрения, есть же ещё пространство для оптимизаций "как быстрее определить слово (т.е. ключ)" и т.п.? Т.е. оптимизации за счёт инструкций CPU (при задаче - исходные данные уже лежат в RAM).

[Wataru]

Александр Куракин, в боре итак обработка посимвольно идет. Там не надо даже весь ключ выделять. Встретили пробельный символ - увеличили счетчик в текущей внршине и перешли на корень. Иначе перешли по дуге с этим символом. Если ее нет - создали новую вершину.

[Александр Куракин]

Wataru, так, а следующий шаг есть? (далее - утрированно!) Скажем, инструкции CPU, позволяющие "захватывать" несколько байтов (пусть кодировка односимвольная).

[Wataru]

Александр Куракин, в боре можно считать несколько символов одним символом более большого алфавита, но от этого будет расти расход памяти. Лучше не надо. Если текст влезает в память, вы его за минуту весь в простой бор положите. И за минуту же потом обойдете и выведите ответ.

[Александр Куракин]

Wataru, спасибо!

Answer 2

[rPman]

wc
утилита командной строки, часть coreutils любого linux - в один поток считает количество строк/слов/символов в текстовых файлах

разделение слов в файле с помощью xargs, сортировка sort, подсчет уникальных слов uniq -c
cat file | xargs -n 1 | sort | uniq -c

если файлы упакованы, распаковка запускается параллельно с помощью потоков (команда распаковки в stdout | wc )

parallel (одноименный пакет linux) - позволяет максимально просто запускать параллельно несколько процессов (список команд указываются в stdin, по мере необходимости они читаются и запускаются)

На нескольких нодах запускай команду сам.

Итого, любым языком программирования подготавливаешь список команд, обрабатывающих текстовые данные по частям (с учетом их размещения на разных носителях, так как обычно именно они часто являются самым узким местом тут), скармливаешь его parallel и так же своими утилитами читаешь логи на предмет ошибок и результатов.

типа такого:

for a in *.zst;do echo "zstd -d --stdout $a |(printf \"%s\\t\" $a;wc)";done | parallel -j 5

данный код выводит по строчкам имя архива zstd со сжатым текстом и 3 числа, количество строк, слов и символов, параллельно запуская распаковку и подсчет символов в 5 потоков, утилизируя 12 ядер (12-gen intel) по максимуму посчитав 38гб несжатых (4.4гб сжатых) коротких json-файлов (построчно записаны в кучу файлов) за 121сек (узкое место тут распаковка)

Comments

[Александр Куракин]

Спасибо! Только `awk`, наверное, не `wc`, нам же уникальные слова считать...

[rPman]

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

единственное нужно думать о том где хранить файлы, правильно - каждая нода и хранит и обрабатывает, неправильно - все файлы сложить на одно NAS и упереться уже с 10 нодами в гигабитные сети даже со сжатыми файлами

upd. если в строке не много слов, то можно воспользоваться xargs
cat file | xargs -n 1 | sort | uniq -c

[Александр Куракин]

rPman, спасибо!

Получается - по Вашим ответам и https://unix.stackexchange.com/a/39044/407539 -

cat file | tr -s '[:space:]' '[\n*]' | grep -v "^\s*$" | sort | uniq -c | sort -bgr

А если между словами не только пробелы, и сам файл в UTF-8, то - https://unix.stackexchange.com/a/228570/407539 - `gsed`/`gawk` поможет.
В моём реальном случае:

cat file | gsed -E 's/[^[:alpha:]]+/ /g' | gsed -E 's/[[:space:]]+/\n/g' | grep -v "^\s*$" | sort | uniq -c | sort -bgr

P.S. Просто я хотел что-то пооптимальнее, замены и конвейеры вряд ли таковое, по определению :) Но, Вы правы, всё всё равно упрётся во ввод-вывод...

[rPman]

задача странная, сомневаюсь что у нее есть сверхоптимальное решение в виде единой утилиты

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

p.s. utf8 это проблема, регулярки с ней работают не очень шустро, рекомендую перекодировать сначала текст в однобайтовые кодировки, и только потом отдавать ее sed

p.p.s. приложение на c++ можно написать за 15 минут
не пытайся одной командой считать ВСЕ слова, один файл/кусок - свой набор, потом сложишь результаты
не пользуйся базами данных в процессе этого промежуточного подсчета, собирай все в оперативной памяти

вообще задачка то не простая, если данных терабайты

[d'Ivan]

вообще задачка то не простая, если данных терабайты

десятки ГБ, не ТБ данных.

[Александр Куракин]

Мойше Рабинович, rPman, про теребайты тоже интересно :)

Задачка кажется странной, потому что я выбросил предо обработку. А так: есть текст, нужно посчитать количество включений каждого слова.

А в такой формулировке похоже на модельную задачу (подсчёта элементов множества, текстовый вариант).

Answer 3

[mayton2019]

Это стандартный туториал из книжки Изучаем Apache Spark. Там за 5 строчек кода ведется подсчет частоты слов.

Answer 4

[d'Ivan]

Пришел в голову такой вариант:
В текстовом потоке берём каждый токен и делаем инкремент количества, и т.д.
Затем сортируем результаты - здесь вопрос какую структуру данных выбрать, чтобы сортировать находу.

Comments

[d'Ivan]

Какая-то алгоритмическая задача. Наверное, Wataru подскажет вариант получше.

[Wataru]

Мойше Рабинович, Ответил.

[d'Ivan]

Wataru, спасибо за ответ.