Независимо от того, насколько быстры современные компьютеры и сети, пользователям постоянно будут нужны все более быстрые и быстрые услуги. Чтобы уменьшить объем передаваемых данных, мы обычно используем какое-то сжатие. Именно поэтому эта область компьютерных наук всегда будет интересна для исследований и разработок.
Существует много алгоритмов сжатия данных, некоторые из которых без потерь, другие с потерями, но их главной целью всегда будет сэкономить место для хранения и трафик. Эти алгоритмы очень полезны, когда речь идет о передаче данных между двумя удаленными местами. Возможно, лучшим примером является передача между веб-сервером и браузером.
В последние несколько лет было проведено много исследований по сжатию файлов, выполняемых на стороне клиента. Такими файлами являются javascript, css, htmls и изображения. На самом деле серверы и клиенты уже имеют некоторые методы сжатия данных, такие как, например, использование GZIP , которые могут значительно уменьшить передачу. С другой стороны, существует множество инструментов и приемов для уменьшения размера данных.
На самом деле, когда файл исполняется виртуальной машиной клиента, не имеет значения, насколько «красиво» он отформатирован с точки зрения программиста. Таким образом, пробелы, вкладки и новые строки не несут никакой важной информации для окружающей среды. Вот почему такие инструменты сжатия, как YUI Compressor , Google Closure Compiler и т. Д., Удаляют эти символы. Ну, они могут достичь еще большего, чтобы улучшить степень сжатия. В этом посте я не буду рассказывать об этом, но это показывает, насколько важны алгоритмы сжатия данных.
Было бы здорово, если бы мы могли просто сжать данные с помощью какого-либо инструмента. К сожалению, это не так, и обычно степень сжатия зависит от самих данных. Очевидно, что выбор алгоритма сжатия данных зависит главным образом от данных, и в первую очередь мы должны исследовать данные.
Здесь я расскажу об одном очень простом алгоритме сжатия данных без потерь, называемом «кодирование по длине прогона», который может быть очень полезен в некоторых случаях.
обзор
Этот алгоритм состоит в замене больших последовательностей повторяющихся данных только одним элементом этих данных, за которым следует счетчик, показывающий, сколько раз этот элемент повторяется. Чтобы было понятнее, давайте посмотрим на пример строки.
aaaaaaaaaabbbaxxxxyyyzyx
Длина этой строки равна 24, и, как мы видим, существует много повторений. Используя алгоритм длины прогона, мы заменяем любой прогон более короткой строкой, за которой следует счетчик.
a10b3a1x4y3z1y1x1
Длина этой строки равна 17 , что составляет примерно 70% от начальной длины.Очевидно, что это не оптимальный способ сжатия данной строки. Например, нам не нужно использовать цифру «1», когда символ повторяется только один раз. В некоторых случаях такой подход может увеличить длину исходной строки, что в точности противоположно тому, что нам нужно. В этом случае мы получим строку ниже.
a10b3ax4y3zyx
Теперь длина полученной строки равна 13 , что составляет 54% от начальной длины! Разновидностью приведенного выше примера является не счетчик повторений персонажа, а его позиция. Таким образом, исходная строка будет сжата следующим образом.
a0b10a13x14y18z21y22x23
Какой из этих двух подходов вы будете использовать, зависит от цели. Во втором случае мы можем добиться хорошей оптимизации бинарного поиска .
Понятно, что этот алгоритм применим не только к строкам. Мы можем добиться очень хороших результатов на массивах. Типичным примером является передача JSON с сервера на клиент. Тогда, если есть большие последовательности повторяющихся данных, мы можем достичь отличных результатов.
Реализация
Реализация ниже предполагает, что мы сжимаем строку, и она написана на PHP. Однако природа этого алгоритма не ограничивает нас в использовании только строк. Как я уже говорил, с небольшими изменениями мы можем использовать его с другими структурами данных. Важно только понимать, что алгоритм длины цикла очень полезен для больших последовательностей повторяющихся элементов, независимо от того, являются ли они символами или элементами массива.
$message = 'aaaaaaaaaabbbaxxxxyyyzyx';
function run_length_encode($msg)
{
$i = $j = 0;
$prev = '';
$output = '';
while ($msg[$i]) {
if ($msg[$i] != $prev) {
if ($i)
$output .= $j;
$output .= $msg[$i];
$prev = $msg[$i];
$j = 0;
}
$j++;
$i++;
}
$output .= $j;
return $output;
}
// a10b3a1x4y3z1y1x1
echo run_length_encode($message);
И немного оптимизирован.
$message = 'aaaaaaaaaabbbaxxxxyyyzyx';
function run_length_encode($msg)
{
$i = $j = 0;
$prev = '';
$output = '';
while ($msg[$i]) {
if ($msg[$i] != $prev) {
if ($i && $j > 1)
$output .= $j;
$output .= $msg[$i];
$prev = $msg[$i];
$j = 0;
}
$j++;
$i++;
}
if ($j > 1)
$output .= $j;
return $output;
}
// a10b3ax4y3zyx
echo run_length_encode($message);
Наконец небольшое изменение — теперь мы сохраняем положение персонажа.
$message = 'aaaaaaaaaabbbaxxxxyyyzyx';
function run_length_encode($msg)
{
$i = 0;
$prev = '';
$output = '';
while ($msg[$i]) {
if ($msg[$i] != $prev) {
$output .= $msg[$i] . $i;
$prev = $msg[$i];
}
$i++;
}
return $output;
}
// a0b10a13x14y18z21y22x23
echo run_length_encode($message);
Сложность и сжатие данных
Мы привыкли говорить о сложности алгоритма измерения времени и обычно стараемся найти самую быструю реализацию, как в алгоритмах поиска. Здесь не так важно быстро сжимать данные, но сжимать как можно больше, чтобы выходные данные были как можно меньше без потери данных. Отличительной особенностью кодирования длин серий является то, что этот алгоритм прост в реализации.
заявка
Мы можем использовать кодирование длин серий во многих случаях. Он обычно используется для сжатия изображений и очень успешен, когда мы имеем дело только с черно-белыми изображениями. Здесь я расскажу о другом случае использования, о котором я упоминал только выше Допустим, нам нужно перенести очень большой массив данных в наше приложение на основе AJAX с использованием JSON. Скажем также, что данные за несколько лет, например, годы премьеры фильма. Есть много фильмов с премьерой в том же году, поэтому, хотя данные отсортированы, мы на самом деле не можем получить никакой выгоды. Более важно то, что у нас есть большие последовательности данных. Здесь мы можем использовать кодирование длин серий.
$data = array( 0 => 1991, 1 => 1991, ... 2223 => 1991, 2224 => 1992, ... 19298 => 1995, 19299 => 1996, ... );
Как видите, передача всего массива может стать кошмаром, особенно в медленных сетях. Лучше сжать его (т.е. с помощью json_encode в PHP ).
// {"0":1991,"1":1991, ..., "2223":1991,"2224":1992, ..., "19298":1995,"19299":1996, ...}
echo json_encode($data);
После запуска кодирования по длине прогона мы можем получить что-то вроде следующего массива (обратите внимание, что это только примерные данные, и вам решать, какой формат лучше всего хранить для хранения данных).
$data = array( 0 => array(1991, 2224), 1 => array(1992, 3948), 2 => array(1995, 2398), 3 => array(1996, 3489), );
И вывод JSON.
// [[1991,2224],[1992,3948],[1995,2398],[1996,3489]] echo json_encode($data);
Обратите внимание, что если данные отсортированы, мы можем добиться большого успеха, сжимая их !!! Этот подход может использоваться для изображений, графики или координат карты.
Это только один пример того, как сжатие данных может быть полезным в нашей повседневной работе. Хотя связь между сервером и клиентом может быть оптимизирована и сжата, мы можем улучшить ее. Другими словами, мы не всегда уверены, что противоположная сторона поддерживает сжатие.
Что ж, это правда, что клиент должен распаковывать данные, что также может быть медленным. Теперь в первом случае у нас есть только время для передачи, как на диаграмме ниже.
Время передавать данные без сжатия!
Во втором случае мы должны суммировать время для сжатия, передачи и распаковки.
Время отправлять данные со сжатием!
Все это важно, но в целом сжатие данных может быть удобно во многих случаях в нашей повседневной работе.