@anikavoi

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

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

Спасибо!
  • Вопрос задан
  • 154 просмотра
Пригласить эксперта
Ответы на вопрос 3
Обратите внимание, что std::string использует SBO, то есть не выделяет доп. память в куче для коротких строк. Ещё стандартные мапы в C++ крайне неэффективны, подключите библиотеку. Идея такова:
  1. Хешмап "строки -> счётчики" для строк длины 3
  2. Хешмап "строки -> счётчики" для строк длины 4, но добавляем туда только строки, у которых начало длины 3 входит в мапу из (1) не менее 2 раз
  3. Хешмап "строки -> счётчики" для строк длины 5, но добавляем туда только строки, у которых начало длины 4 входит в мапу из (2) не менее 2 раз
Ответ написан
Комментировать
jcmvbkbc
@jcmvbkbc
"I'm here to consult you" © Dogbert
С помощью чего можно решить эту задачу?

С помощью массива std::hashmap<std::string, size_t>, по одному для последовательности каждой длины?
Ответ написан
mayton2019
@mayton2019
Bigdata Engineer
120 гигабайт - это размер еще не Биг-дата но уже близкий к выходу за рамки оперативной памяти. Если исходный материал побит на файлы (небольшого размера) то я-бы предложил решать эту задачу через map-reduce.

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

По алгоритму. Ну я +1 к Антону.
Ответ написан
Комментировать
Ваш ответ на вопрос

Войдите, чтобы написать ответ

Войти через центр авторизации
Похожие вопросы