Строковое кодирование для оптимизации памяти

Question

У меня есть поток строк в формате, похожем на этот a:b, d:a, t:w, i:r и т. Д. Так как я продолжаю добавлять эти строки, в конце концов, это становится очень большой строкой.

Я пытаюсь кодировать, например:

a:b -> 1
d:a -> 2
etc.

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

Я имею в виду следующий метод:

Создать: map<string, int> - это сохранит строку и ее количество. В конце я заменю строку с максимальным количеством на 1, затем на 2 и так до последнего элемента карты.

В настоящее время размер конечной строки составляет ~ 100 000 символов.

Я не могу пойти на компромисс по скорости, пожалуйста, предложите, если у кого-то есть лучшая техника для достижения этого.

Answer 1

Если я правильно понимаю, что ваши входные строки имеют диапазон "a: a" ... "z: z", и вам просто нужно посчитать появления каждого в потоке, независимо от порядка. Если вашего дистрибутива достаточно, вы можете сосчитать их, используя uint16_t. Карта реализована с использованием дерева, поэтому массив гораздо более эффективен, чем карта как по памяти, так и по времени. Таким образом, вы можете определить массив

array<array<uint16_t, 26>, 26> counters = {{}};

и, предполагая, что вы введете, например, input = "c:d", вы можете заполнить массив следующим образом

    counters[input[0]-'a'][input[2]-'a']++;

Тогда, наконец, вы можете распечатать частоты входа, как это

for (auto i=0; i < counters.size() ; ++i) {
  for (auto j=0; j < counters[i].size(); ++j) {
    cout<<char(i+'a')<<":"<<char(j+'a')<<" "<<counters[i][j]<<endl;
  }
}