Алгоритмы сжатия списков чисел для передачи в тестовом виде. В реализацию входят парсер строк и поле для django-rest-framework.
Поддерживаются 2 способа сжатия: диапазоны с выносом за скобку и дельта-строки.
Для данного алгоритма применяется 2 способа сжатия:
- диапазон чисел можно записать в виде
min-max - минимальное вычесть из остальных и вынести за скобку:
min(n1 - min, n2 - min, n3 - min, ...)
Например, есть последовательный набор чисел: [1, 2, 3, 4, 5, 6].
Его можно представить как 1-6.
Вынос минимального имеет смысл для чисел с большим количеством разрядов.
Например, набор чисел [2135, 2138, 2142, 2143] можно представить как 2135(0,3,7,8)
Эти способы можно комбинировать.
Например, диапазон больших чисел: [1345, 1346, 1347, 1348] будет 1345(0-3)
Способ сжатия строки, при котором выполняется по шагам:
- Дельта-компрессия
- Выделение x-диапазонов
- Объединение в одну строку с использованием последовательностей по количеству разрядов
Чтобы отличить данный способ от предыдущего, перед сжатой строкой указывается знак ~.
Каждый элемент представляется как разность текущего и предыдущего значений. По сути этот способ только уменьшает количество разрядов.
Например, [105, 108, 130] можно предствить как [105, 3, 22], где:
- 105 - 0 = 105
- 108 - 105 = 3
- 130 - 108 = 22
Таким образом мы получаем набор неуникальных значений. Для наилучшего результата первоначальный набор чисел имеет смысл отсортировать.
Для объединения повторяющихся значений можно использовать "x-диапазоны" -
запись формата NxM, где N - количество повторений, M - повторяющееся значение.
По сути это те же диапазоны, но со свободным шагом. Идущие подряд числа будут образовывать последовательность одинаковых чисел.
Например, в случае диапазона с 1 до 4 ([1, 2, 3, 4])
после первого шага набор будет иметь вид [1, 1, 1, 1].
Такую последовательность можно представить как "4 раза по 1": [4x1].
Но, в отличие от способа "Диапазоны с выносом за скобку", такой вид диапазонов обрабатывает диапазоны с шагом, отличным от единицы.
Например, нечётные числа от 1 до 10 ([1, 3, 5, 7, 9])
после дельта-компрессии будут иметь вид [1, 2, 2, 2, 2].
После выделения x-диапазонов такую строку можно сократить до [1, 4x2] (1 и 4 раза по 2).
Самым простым способом представить последовательность в виде строки - перечислить все элементы через разделитель (например, через запятую). Но это добавляет N-1 символов (где N - количество элементов).
В данном алгоритме последовательности можно представить двумя способами:
- перечисление через запятую
- маркировка по количеству разрядов
Пункт "перечисление через запятую" говорит сам за себя, не буду на нём останавливаться.
Маркировка по количеству разрядов подразумевает некий идентификатор перед перечислением. Таких маркеров поддерживается 2:
- точка - один разряд
- двоеточие - два разряда
При этом x-диапазоны также могут быть в последовательности с маркером, если оба числа в записи диапазона по разрядам соответствуют разрядности маркера.
Маркированная последовательность представляет собой один токен. Следовательно, несколько последовательностей и отдельных значений можно перечислить через запятую. Маркер также можно использовать как разделитель, поэтому между двух маркированных последовательностей запятую ставить не нужно.
Примеры:
| Последовательность | Сжатая строка | Пояснение |
|---|---|---|
| [1, 3, 5, 6] | ~.1356 |
Набор чисел по одному разряду. Представляем одним токеном с маркером "точка" |
| [1, 22, 123] | ~1,22,123 |
Все разряды разные, перечисляем через запятую |
| [1, 2x3, 2] | ~.12x32 |
Числа в диапазоне 2x3 одноразрядные, значит можно поместить в один ряд с остальными |
| [13, 15, 10, 5, 6, 7] | ~:131510.567 |
Две последовательности подряд - по 2 и по одному разряду |
| [2, 3, 10x3, 123] | ~.23,10x3,123 |
В диапазоне 10x3 числа разных разрядов, а значит он не может использоваться в последовательностях |
На небольших примерах этого не видно, но для наборов чисел с небольшим случайным шагом этот способ даёт гораздо больший уровень компрессии, чем диапазоны с выносом за скобку.