Обратная RLE сортировка

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

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

Алгоритм сжатия данных, заменяющий повторяющиеся символы (серии) на один символ и число его повторов. Серией называется последовательность, состоящая из нескольких одинаковых символов. При кодировании (упаковке, сжатии) строка одинаковых символов, составляющих серию, заменяется строкой, содержащей сам повторяющийся символ и количество его повторов (более подробно на вики)

Пример:

AAAABBAAABBBA = 13 символов

4A 2B 3A 3B 1A = 10 символов

Таким образом, мы уменьшили запись строки на 3 символа. Так работает один из простых алгоритмов сжатия. Идем дальше…

Обратный RLE.

Итак, рассмотрев RLE алгоритм, мы понимаем, как сжимаются одинаковые длинные цепочки символов. Обратный RLE – это декодирование уже сжатых данных.

Пример:

4A 2B 3A 3B 1A = 10 символов

 AAAA BB AAA BBB A = 13 символов

Вы спросите: «Где же здесь сортировка?». И будете правы, ее здесь нет ;). Я лишь объяснил основы алгоритма, чтобы вы понимали, как позже RLE будет работать в сортировке. Давайте приступим к самому главному!

Сортировка. Создаем словарь.

Словарь – это заранее подобранные сортированные символы, которые есть в строке. Грубо говоря – это алфавит, из которого состоит строка. У разных данных алфавит может быть разным. Словарь можно создать как строгую постоянную для определенных данных, либо вычислить, пройдя по данным и отсортировав его каким-нибудь из простых алгоритмов сортировки (быстрой сортировкой, шейкерной, шелла и т.п.). Суть в том, что для этого не придется делать сложные вычисления, да и размер словаря не особо велик для сортировки. Таким образом, не должно возникнуть сложности в его создании.

Вот, к примеру, для строки:

BBXBBFFXFFDBB

Если проходить по порядку символ за символом, можно собрать алфавит, а после его упорядочить:

Далее проходя по строке, мы записываем количество символов каждому символу в словаре и таким образом получается:

Но для такого метода понадобиться лишний проход по данным. Второй вариант создания словаря — это взять максимально фиксированый алфавит для данных. К примеру, для все той же строки:

BBXBBFFXFFDBB

Можно в качестве словаря задать латинский алфавит(A-Z) и проходя по данным заносить в него подсчет:

0A6B0C1D0E4F…0V0W2X0Y0Z

После останется лишь удалить из словаря нулевые значения и в итоге получить такой результат:

6B 1D 4F 2X

Вам это ничего не напоминает? Верно – это RLE запись.

Сортировка. Расшифровка RLE.

Наконец-то добрались-таки до самого главного. Сортировка уже сделана была еще в словаре так, что нам остается только расшифровать запись обратно из RLE:

6B 1D 4F 2X

И расшифровываем:

BBBBBB D FFFF XX

Все! Сортировка удалась 🙂

Как вы могли заметить, основой сортировки служит правильно подобранный заранее алфавит, а запись в RLE формате лишь ускоряет работу с данными. Особенностью является то, что размер данных может несоизмеримо большим, но от этого алгоритм не станет сложнее. Притом алгоритм использует лишь один проход по данным.