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

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

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

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

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

www.tgoop.com/the_algorithms/4958

4.39K viewsJul 7 at 08:59

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

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

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

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

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