«Hello, World!» от мира сжатия данных. Канонический алгоритм Хаффмана

[hokusi]

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

На самом есть случай, когда не хватило бы uint64_t, но размер сжимаемого файла должен быть больше 27777890035 байт, что равно почти 28 Гбайтам, не запредельный размер, но вряд-ли кто-то стал использовать данную реализацию для столь большого объёма данных. Для размышлений использовал последовательность чисел Фибоначчи.

#include <iostream>

#define array_length 64

int main()
{
    uint64_t fr[array_length];
    
    fr[array_length - 1] = 1;
    fr[array_length - 2] = 1;
    
    uint64_t sum = 2;
    
    for (size_t i = array_length - 2, j = 3; i; i--, j++){
        fr[i - 1] = fr[i] + fr[i + 1];
        sum += fr[i - 1];
        std::cout << j << "-ое число Фиббоначи - " << fr[i - 1] << ", сумма - " << sum << '\n';
    }

    return 0;
}

[hokusi]

Здравствуйте, не совсем пынял, что Вы имеете в виду. В любом случае мы не можем напрямую работать с данными на дисках, всегда будет использоваться ОЗУ в качестве буфера. Данное замечание было сделано, так как изначально, до 2 редакции, реализация считывала данные из файла и писала по-байтово в динамический массив. Или Вы имеете в виду то, что так как поток на чтение был открыт, то часть данных останется в ОЗУ? Если честно не разбирался, но если Вам известны источники раскрывающие данную тему, то прошу Вас поделиться, был бы рад почитать.

[hokusi]

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

[zzzzzzerg]

1. Вы же в курсе что вы таким образом теряете оригинальный callstack ошибки?

2. Ваш вариант CalcMapFast принципиально ничем не отличается от CalcMap, можете посмотреть на реализацию ReadAllBytes

[hokusi]

Крайне поверхностно знаком с языком Ассемблера, но данная ошибка вылезет же только в том случае, если процедура будет вызываться рекурсивно, разве нет?

[zzzzzzerg]

Хм, если это вопрос ко мне - то тут нет языка Ассемблера и нет рекурсии. Поэтому не понимаю, о чем вы спрашиваете.

[hokusi]

Не совсем пынямаю как может произойти call stack ошибка.

[zzzzzzerg]

Не "call stack ошибка", а call stack или stack trace ошибки. Т.е. список вызовов до вызова, который выбросит исключение. В данном случае вызов любой системной функции внутри блока try/catch может выбросить исключение, которое будет отловлено в блоке catch и выброшено снова, но без информации об оригинальном списке вызовов.

[zzzzzzerg]

В ReadAllBytes практически такой же цикл как у вас.

[zzzzzzerg]

Ваш текст "я взял за основу 16 Мб и всё что меньше идёт через CalcMapFast" - так что вы маленькие файлы читаете полностью в ОЗУ и они полностью влезают в ваши 16Мб, если читать их через CalcMapFast, так что ограничение на Int.MaxValue оно не про ваш случай. И в вашем цикле в CalcMap чуть меньше телодвижений (как раз про сдвиги смещений). И вы таже будете вычитывать данные в массив пока не прочтете весь файл (даже если он маленький и ОС будет вам отдавать его частями).

Эквивалентность кода довольно очевидна, но убеждать вас я не хочу.

[voldemar_d]

Куча библиотек, а именно <vector>, <string> и <algorithm>

Почему это отнесено к недостаткам?

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

[hokusi]

Использование сторонних библиотек всегда отпугивало, но решил включить, так как сам могу реализовать данные СД и алгоритм сортировки, пусть и в стократ хуже, чем в это представлено в данных библиотеках. Личная оценка автора статьи, грубо говоря.

Не совсем понял, что Вы имеете в виду. Если говорить в терминах теории информации, где слово - это R-бит, но чаще всего R-байт, то канонический алгоритм Хаффмана работает с однобайтовыми словами. Но мы можем в теории обрабатывать и 8-байтовые слова, то есть uint64_t, да и алгоритм Хаффмана относится к алгоритм сжатия на основе алфавита, сжатие данных на основе словаря это уже скорее про LZ.

[voldemar_d]

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

Я примерно это и имел ввиду - обычно изобретение велосипеда результат дает вряд ли лучше.

сжатие данных на основе словаря это уже скорее про LZ

Действительно, я и забыл.

[hokusi]

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

На самом есть случай, когда не хватило бы uint64_t, но размер сжимаемого файла должен быть больше 27777890035 байт, что равно почти 28 Гбайтам, не запредельный размер, но вряд-ли кто-то стал использовать данную реализацию для столь большого объёма данных. Для размышлений использовал последовательность чисел Фибоначчи.

#include <iostream>

#define array_length 64

int main()
{
    uint64_t fr[array_length];
    
    fr[array_length - 1] = 1;
    fr[array_length - 2] = 1;
    
    uint64_t sum = 2;
    
    for (size_t i = array_length - 2, j = 3; i; i--, j++){
        fr[i - 1] = fr[i] + fr[i + 1];
        sum += fr[i - 1];
        std::cout << j << "-ое число Фиббоначи - " << fr[i - 1] << ", сумма - " << sum << '\n';
    }

    return 0;
}