Как найти часто встречающиеся тексте последовательности?

Question

[anikavoi]

Есть большой текстовый файл. Около 120 гигабайт русскоязычного текста.
Нужно найти 30-40 наиболее часто встречающихся последовательностей символов, длиной более 4-5 символов.
С помощью чего можно решить эту задачу?
Если есть стандартные программы - отлично.
Если есть исходники на c\c++, rust, nim - хорошо.
На худой конец подскажите алгоритм (писать очень не хочется, занятость сильная, но куда деться в крайнем случае)

Спасибо!

Comments

[Модератор]

anikavoi дорогой пользователь, настоятельно рекомендуем еще раз обратить самое пристальное внимание на п. 3.1 регламента работы сервиса (и, в особенности, на его последний абзац). В противном случае, ваши вопросы будут удаляться по причине тег-спама, а систематические нарушения приведут к блокировке учетной записи.

[anikavoi]

Модератор, прошу прощения, но мне действительно подойдет любое из решений, или алгоритм, или исходник, или решение средствами утилит линукс, поэтому я и поставил три тэга.
Буду аккуратнее.

Answer 1

[Антон Жилин]

Обратите внимание, что std::string использует SBO, то есть не выделяет доп. память в куче для коротких строк. Ещё стандартные мапы в C++ крайне неэффективны, подключите библиотеку. Идея такова:

1. Хешмап "строки -> счётчики" для строк длины 3
   
2. Хешмап "строки -> счётчики" для строк длины 4, но добавляем туда только строки, у которых начало длины 3 входит в мапу из (1) не менее 2 раз
   
3. Хешмап "строки -> счётчики" для строк длины 5, но добавляем туда только строки, у которых начало длины 4 входит в мапу из (2) не менее 2 раз
   

Answer 2

[jcmvbkbc]

С помощью чего можно решить эту задачу?

С помощью массива std::hashmap<std::string, size_t>, по одному для последовательности каждой длины?

Comments

[anikavoi]

120 гиг запулить в память с довеском структур хешмапа?
Вы сейчас пошутили, да?

[jcmvbkbc]

anikavoi, вовсе нет. Если смущает размер можно заменить std::string на целочисленный хэш. После нахождения хэшей-лидеров можно восстановить исходные символьные последовательности вторым проходом.

[anikavoi]

jcmvbkbc, кажется я понял о чем речь.
Завтра попробую. Спасибо!

Answer 3

[mayton2019]

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

Если удасться это сделать то реализация написанная на Python может работать быстрее во много раз за счет параллелизма. Я не говорю что на С++ не надо делать. Я просто акцентирую внимание что задача имеет специфику распаралелливания. Грубо говоря задача тяготеет к big-data и шаблонам паралельного процессинга для которых язык не особо важен а важна имеено эта опция.

По алгоритму. Ну я +1 к Антону.