Алгоритмы и структуры данных

Кодирование длин серий (Run-Length Encoding, RLE)

Метод сжатия данных, который основан на замене повторяющихся последовательностей символов кодом, состоящим из символа и длины этой последовательности.

Алгоритм:
1. Читаем символы исходной строки один за другим.
2. Если текущий символ повторяется, увеличиваем счетчик повторений.
3. Если текущий символ отличается от предыдущего или достигнут максимальный предел длины серии, записываем в выходной поток код, состоящий из повторяющегося символа и длины серии.
4. Повторяем шаги 2-3 до тех пор, пока не прочитаем все символы исходной строки.
5. Завершаем сжатие.

Сложность алгоритма зависит от размера исходной строки и количества повторяющихся символов. В худшем случае сложность: O(n^2), где n - размер строки.

www.tgoop.com/the_algorithms/4606

6.1K viewsNov 17, 2023 at 09:00

Кодирование длин серий (Run-Length Encoding, RLE)

Метод сжатия данных, который основан на замене повторяющихся последовательностей символов кодом, состоящим из символа и длины этой последовательности.

Алгоритм:
1. Читаем символы исходной строки один за другим.
2. Если текущий символ повторяется, увеличиваем счетчик повторений.
3. Если текущий символ отличается от предыдущего или достигнут максимальный предел длины серии, записываем в выходной поток код, состоящий из повторяющегося символа и длины серии.
4. Повторяем шаги 2-3 до тех пор, пока не прочитаем все символы исходной строки.
5. Завершаем сжатие.

Сложность алгоритма зависит от размера исходной строки и количества повторяющихся символов. В худшем случае сложность: O(n^2), где n - размер строки.

BY Алгоритмы и структуры данных