обзор
Относительное кодирование — это еще один алгоритм сжатия данных. В то время как кодирование длин серий , кодирование битовой карты и диаграмма и схема замещение пыталось уменьшить повторение данных, с относительными кодирующими целями немного отличается. Действительно, кодирование длин серий искал длинные серии повторяющихся элементов, в то время как подстановка шаблонов и кодирование растровых изображений пытались «отобразить», где происходят повторения.
Единственная проблема с этими алгоритмами состоит в том, что входной поток данных не всегда состоит из повторяющихся элементов. Ясно, что если входной поток содержит много повторяющихся элементов, должен быть какой-то способ их уменьшения. Однако это не означает, что мы не можем сжимать данные, если нет повторений. Все зависит от данных. Допустим, у нас есть следующий поток для сжатия.
1, 2, 3, 4, 5, 6, 7
Трудно представить, как этот поток данных может быть сжат. Та же проблема может возникнуть при попытке сжать алфавит. На самом деле буквы алфавита являются самой основой слов, поэтому это минимальная часть для построения слов, и поэтому их трудно сжать.
К счастью, это не всегда так. Алгоритм, который пытается работать с неповторяющимися данными, является относительным кодированием. Давайте посмотрим на следующий поток ввода — годы из данного десятилетия (90-х).
1991, 1991, 1999, 1998, 1991, 1993, 1992, 1992
Здесь у нас есть 39 символов, и мы можем уменьшить их. Естественным подходом является удаление ведущей «19», как мы, люди, часто делаем.
91, 91, 99, 98, 91, 93, 92, 92
Теперь у нас есть более короткая строка, но мы можем пойти еще дальше, сохранив только первый год. Все остальные годы будут относительно этого года.
91, 0, 8, 7, 0, 2, 1, 1
В настоящее время объем передаваемых данных значительно уменьшен (с 39 до 16 — более чем на 50%). Однако есть несколько вопросов, на которые мы должны ответить в первую очередь, потому что поток не всегда будет отформатирован таким красивым способом. Как насчет следующего потока символов?
91, 94, 95, 95, 98, 100, 101, 102, 105, 110
Мы видим, что значение 100 как-то находится в середине интервала, и его удобно использовать в качестве базового значения для относительного кодирования. Таким образом, поток выше станет:
-9, -6, -5, -5, -2, 100, 1, 2, 5, 10
Проблема в том, что мы не всегда можем так легко решить, какое значение будет базовым . Что делать, если данные были распределены по-другому:
96, 97, 98, 99, 100, 101, 102, 103, 999, 1000, 1001, 1002
Теперь значение «100» бесполезно, потому что сжатие потока будет выглядеть примерно так:
-4, -3, -2, -1, 100, 1, 2, 3, 899, 900, 901, 902
Группировать относительные значения вокруг «некоторых» базовых значений будет гораздо удобнее.
(-4, -3, -2, -1, 100, 1, 2, 3) (-1, 1000, 1, 2)
Однако решить, какое значение будет базовым, не так просто. Также формат кодирования не так тривиален. С другой стороны, этот тип кодирования может быть полезен в некоторых конкретных случаях, как мы можем видеть ниже.
Реализация
Реализация этого алгоритма зависит от конкретной задачи и формата потока данных. Предполагая, что нам нужно перенести поток лет в JSON с веб-сервера в браузер, вот небольшой фрагмент PHP.
// JSON: [1991,1991,1999,1998,1999,1998,1995,1997,1994,1993]
$years = array(1991,1991,1999,1998,1999,1998,1995,1997,1994,1993);
function relative_encoding($input)
{
$output = array();
$inputLength = count($input);
$base = $input[0];
$output[] = $base;
for ($i = 1; $i < $inputLength; $i++) {
$output[] = $input[$i] - $base;
}
return $output;
}
// JSON: [1991,0,8,7,8,7,4,6,3,2]
echo json_encode(relative_encoding($years));
заявка
Этот алгоритм может быть очень полезен во многих случаях, таких как этот: существует множество картографических приложений по всему Интернету. Некоторые продукты, такие как Google Maps , Yahoo! Карты , Bing Maps довольно известны, но есть и очень полезные проекты с открытым исходным кодом, такие как OpenStreetMap . Количество сайтов, использующих эти приложения, исчисляется тысячами.
Типичный вариант использования — передача большого количества координат Geo с веб-сервера в браузер с использованием JSON. Действительно, любая точка GEO на Земле относится к точке (0,0), которая расположена недалеко от западного побережья Африки, однако при больших уровнях масштабирования, когда есть тонны маркеров, мы можем передавать информацию с относительным кодированием.
Например, следующая диаграмма показывает Сан-Франциско с некоторыми маркерами на нем. Координаты относятся к точке (0,0) на Земле.
Маркеры карты могут быть относительно точки (0, 0) на Земле, что иногда может быть бесполезным.
Гораздо более полезным может быть кодирование этих маркеров относительно центра города, поэтому мы можем сэкономить место.
Относительное кодирование может быть полезно для маркеров карты с большим уровнем масштабирования, однако этот тип сжатия может быть сложным. Например, при перетаскивании карты и обновлении массива маркеров. С другой стороны, мы должны сгруппировать маркеры, если нам нужно загрузить более одного города. Вот почему мы должны быть осторожны при его реализации. Но это может быть очень полезно — например, при начальной загрузке карты мы можем уменьшить данные и ускорить время загрузки.
Дело в том, что при относительном кодировании мы можем сохранять только изменения в базовом значении (данных) — что-то вроде систем контроля версий и, таким образом, сокращать передачу и загрузку данных. Вот графический пример. В первом случае на диаграмме ниже мы видим, что каждый элемент хранится отдельно. Это не зависит от соседних предметов и может быть полностью независимым от них.
Однако мы можем хранить полную информацию только для первого элемента, и любой другой элемент будет относиться к нему, как показано на диаграмме ниже.
Источник: http://www.stoimen.com/blog/2012/01/30/computer-algorithms-data-compression-with-relative-encoding/