Лучший Алгоритм сжатия для последовательности целых чисел
Указатели являются понятием, которое для многих может сбивать с толку сначала, в особенности когда дело доходит до копирования значений указателя вокруг и все еще ссылки на тот же блок памяти.
я нашел, что лучшая аналогия должна рассмотреть указатель как листок бумаги с адресом дома на нем и блоком памяти, на который это ссылается как фактический дом. Все виды операций могут таким образом быть легко объяснены.
я добавил некоторый код Дельфи вниз ниже и некоторые комментарии в соответствующих случаях. Я выбрал Delphi, так как мой другой основной язык программирования, C#, не показывает вещи как утечки памяти таким же образом.
, Если Вы только хотите изучить высокоуровневое понятие указателей, тогда необходимо проигнорировать части, маркировал "Memory layout" в объяснении ниже. Они предназначаются для предоставления примеров того, на что память могла быть похожей после операций, но они - больше низкого уровня по своей природе. Однако, чтобы точно объяснить, как переполнение буфера действительно работает, было важно, чтобы я добавил эти схемы.
Правовая оговорка: Во всех отношениях, это объяснение и разметки памяти в качестве примера значительно упрощены. Существует больше служебное и намного больше деталей, которые необходимо было бы знать, необходимо ли иметь дело с памятью на основе низкого уровня. Однако для намерений объяснения памяти и указателей, это достаточно точно.
<час>Позволяют нам предположить, что класс THouse, используемый ниже, похож на это:
type
THouse = class
private
FName : array[0..9] of Char;
public
constructor Create(name: PChar);
end;
при инициализации объекта дома имя, данное конструктору, копируется в частное поле FName. Существует причина, она определяется как массив фиксированного размера.
В памяти, будут немного служебные связаны с выделением дома, я проиллюстрирую это ниже подобного это:
---[ttttNNNNNNNNNN]---
^ ^
| |
| +- the FName array
|
+- overhead
"tttt" область является служебной, обычно будет больше из этого для различных типов времени выполнения и языков, как 8 или 12 байтов. Обязательно, чтобы независимо от того, что значения были сохранены в этой области, никогда не изменяется ничем кроме средства выделения памяти или базовых системных стандартных программ, или Вы рискуете разрушать программу.
<час>Выделяют память
, Заставляют предпринимателя создавать Ваш дом и давать Вам адрес дому. В отличие от реального мира, выделение памяти не может быть сказано, где выделить, но найдет подходящее место с достаточным количеством комнаты и сообщит адрес выделенной памяти.
, Другими словами, предприниматель выберет пятно.
THouse.Create('My house');
расположение Памяти:
---[ttttNNNNNNNNNN]---
1234My house
<час> Сохраняют переменную с адресом
Запись адрес в Ваш новый дом вниз на листке бумаги. Данная статья будет служить Вашей ссылкой на Ваш дом. Без этого листка бумаги Вы потеряны и не можете найти дом, если Вы уже не находитесь в нем.
var
h: THouse;
begin
h := THouse.Create('My house');
...
расположение Памяти:
h
v
---[ttttNNNNNNNNNN]---
1234My house
<час> значение указателя Копии
Просто пишут адрес на новом листке бумаги. У Вас теперь есть два листка бумаги, которые получат Вас в тот же дом, не два отдельных здания. Любые попытки следовать за адресом из одной бумаги и переставить мебель в том доме заставят его казаться, что другой дом был изменен таким же образом, если Вы не можете явно обнаружить, что это - на самом деле всего один дом.
Примечание Это обычно - понятие, что у меня есть большая часть объяснения задач людям, два указателя не означает два объекта или блоки памяти.
var
h1, h2: THouse;
begin
h1 := THouse.Create('My house');
h2 := h1; // copies the address, not the house
...
h1
v
---[ttttNNNNNNNNNN]---
1234My house
^
h2
<час> Освобождение памяти
Уничтожают дом. Можно тогда позже снова использовать бумагу для нового адреса если Вы, так пожелайте или очистите ее для упущения адреса в дом, который больше не существует.
var
h: THouse;
begin
h := THouse.Create('My house');
...
h.Free;
h := nil;
Здесь я сначала создаю дом и овладеваю его адресом. Тогда я делаю что-то в дом (используйте его... код, оставленный как осуществление для читателя), и затем я освобождаю его. Наконец я очищаю адрес от своей переменной.
расположение Памяти:
h <--+
v +- before free
---[ttttNNNNNNNNNN]--- |
1234My house <--+
h (now points nowhere) <--+
+- after free
---------------------- | (note, memory might still
xx34My house <--+ contain some data)
<час> Висячие указатели
Вы говорите Вашему предпринимателю уничтожать дом, но Вы забываете стирать адрес из своего листка бумаги. Позже при рассмотрении листка бумаги Вы забыли, что дом больше не там и идет для посещения его с неудавшимися результатами (см. также часть о недопустимой ссылке ниже).
var
h: THouse;
begin
h := THouse.Create('My house');
...
h.Free;
... // forgot to clear h here
h.OpenFrontDoor; // will most likely fail
Используя [1 126] после того, как вызов к [1 127] мог бы работа, но это - просто чистая удача. Скорее всего, это перестанет работать, в потребительском месте, посреди критической операции.
h <--+
v +- before free
---[ttttNNNNNNNNNN]--- |
1234My house <--+
h <--+
v +- after free
---------------------- |
xx34My house <--+
, Как Вы видите, h неподвижные точки к остаткам данных в памяти, но так как это не могло бы быть завершено, с помощью него в качестве прежде, мог бы перестать работать.
<час>Утечка памяти
Вы теряете листок бумаги и не можете найти дом. Дом все еще стоит где-нибудь, хотя, и когда Вы позже хотите создать новый дом, Вы не можете снова использовать то пятно.
var
h: THouse;
begin
h := THouse.Create('My house');
h := THouse.Create('My house'); // uh-oh, what happened to our first house?
...
h.Free;
h := nil;
Здесь мы перезаписали содержание h переменная с адресом нового дома, но старый все еще стоит... где-нибудь. После этого кода нет никакого способа достигнуть того дома, и это оставят, стоя. Другими словами, выделенная память останется выделенной до завершений приложения, в которой точке операционная система разъединит ее.
расположение Памяти после первого выделения:
h
v
---[ttttNNNNNNNNNN]---
1234My house
расположение Памяти после второго выделения:
h
v
---[ttttNNNNNNNNNN]---[ttttNNNNNNNNNN]
1234My house 5678My house
А более распространенный способ получить этот метод состоит в том, чтобы только забыть освобождать что-то, вместо того, чтобы перезаписать его как выше. В терминах Дельфи это произойдет со следующим методом:
procedure OpenTheFrontDoorOfANewHouse;
var
h: THouse;
begin
h := THouse.Create('My house');
h.OpenFrontDoor;
// uh-oh, no .Free here, where does the address go?
end;
После того, как этот метод выполнился, нет никакого места в наших переменных, что адрес в дом существует, но дом все еще там.
расположение Памяти:
h <--+
v +- before losing pointer
---[ttttNNNNNNNNNN]--- |
1234My house <--+
h (now points nowhere) <--+
+- after losing pointer
---[ttttNNNNNNNNNN]--- |
1234My house <--+
, Как Вы видите, старые данные оставляет неповрежденными в памяти и не снова использует средство выделения памяти. Средство выделения отслеживает, которых областей памяти использовался и не снова использует их, если Вы не освобождаете его.
<час>Освобождение памяти, но хранение (теперь недопустимый) ссылка
Уничтожает дом, стирает один из листков бумаги, но у Вас также есть другой листок бумаги со старым адресом на нем, когда Вы перейдете к адресу, Вы не найдете дом, но Вы могли бы найти что-то, что напоминает руины одного.
, Возможно, Вы даже найдете дом, но это не дом, Вам первоначально дали адрес, и таким образом любые попытки использовать его, как будто это принадлежит Вам, мог бы перестать работать ужасно.
Иногда Вы могли бы даже найти, что соседний адрес имеет довольно большой агрегат собственных нужд на нем, который занимает три, обращаются (Мэйн-Стрит 1-3), и Ваш адрес переходит к середине дома. Любые попытки рассматривать ту часть большого 3-адресного дома как единственный небольшой дом могли бы также перестать работать ужасно.
var
h1, h2: THouse;
begin
h1 := THouse.Create('My house');
h2 := h1; // copies the address, not the house
...
h1.Free;
h1 := nil;
h2.OpenFrontDoor; // uh-oh, what happened to our house?
Здесь дом был разъединен через ссылку в [1 129], и в то время как h1 был очищен также, h2 все еще имеет старое, устаревшее, адрес. Доступ к дому, который больше не стоит, мог бы или не мог бы работать.
Это - изменение висячего указателя выше. Посмотрите его расположение памяти.
<час>Переполнение буфера
Вы перемещаете больше материала в дом, чем можно возможно соответствовать, устремляясь в соседний дом или двор. Когда владелец того соседнего дома позже придет домой, он найдет все виды вещей, он рассмотрит свое собственное.
Это - причина, я выбрал массив фиксированного размера. Чтобы готовить почву, предположите, что второй дом, который мы выделяем, будет, по некоторым причинам, помещен перед первым в памяти. Другими словами, второй дом будет иметь более низкий адрес, чем первый. Кроме того, они выделяются друг прямо рядом с другом.
Таким образом, этот код:
var
h1, h2: THouse;
begin
h1 := THouse.Create('My house');
h2 := THouse.Create('My other house somewhere');
^-----------------------^
longer than 10 characters
0123456789 <-- 10 characters
расположение Памяти после первого выделения:
h1
v
-----------------------[ttttNNNNNNNNNN]
5678My house
расположение Памяти после второго выделения:
h2 h1
v v
---[ttttNNNNNNNNNN]----[ttttNNNNNNNNNN]
1234My other house somewhereouse
^---+--^
|
+- overwritten
часть, которая будет чаще всего вызывать катастрофический отказ, - при перезаписи важных частей данных, Вы сохранили, это действительно не должно быть случайным образом изменено. Например, это не могла бы быть проблема, что части названия h1-дома были изменены, с точки зрения катастрофического отказа программы, но перезапись издержек объекта, скорее всего, откажет, когда Вы попытаетесь использовать поврежденный объект, как будет, перезаписывая ссылки, который хранится к другим объектам в объекте.
<час>Связанные списки
, Когда Вы следуете за адресом на листке бумаги, Вы добираетесь до дома, и в том доме существует другой листок бумаги с новым адресом на нем, для следующего дома в цепочке, и так далее.
var
h1, h2: THouse;
begin
h1 := THouse.Create('Home');
h2 := THouse.Create('Cabin');
h1.NextHouse := h2;
Здесь мы создаем ссылку от нашего домашнего дома до нашей каюты. Мы можем следовать за цепочкой, пока дом не имеет никакой NextHouse ссылка, что означает, что это - последнее. Для посещения всех наших зданий мы могли использовать следующий код:
var
h1, h2: THouse;
h: THouse;
begin
h1 := THouse.Create('Home');
h2 := THouse.Create('Cabin');
h1.NextHouse := h2;
...
h := h1;
while h <> nil do
begin
h.LockAllDoors;
h.CloseAllWindows;
h := h.NextHouse;
end;
расположение Памяти (добавил NextHouse как ссылку в объекте, отмеченном с четырьмя LLLL's в ниже схемы):
h1 h2
v v
---[ttttNNNNNNNNNNLLLL]----[ttttNNNNNNNNNNLLLL]
1234Home + 5678Cabin +
| ^ |
+--------+ * (no link)
<час> В основных условиях, что такое адрес памяти?
адрес памяти А находится в основных условиях просто число. При размышлении об о памяти как большом массиве байтов самый первый байт имеет адрес 0, следующий адрес 1 и так далее вверх. Это упрощаемое, но достаточно хорошее.
Так это расположение памяти:
h1 h2
v v
---[ttttNNNNNNNNNN]---[ttttNNNNNNNNNN]
1234My house 5678My house
иметь эти два адрес (крайнее левое - адресом 0):
- h1 = 4
- h2 = 23
, Что означает, что наш связанный список выше мог бы фактический взгляд как это:
h1 (=4) h2 (=28)
v v
---[ttttNNNNNNNNNNLLLL]----[ttttNNNNNNNNNNLLLL]
1234Home 0028 5678Cabin 0000
| ^ |
+--------+ * (no link)
Это типичное, чтобы хранить адрес, который "указывает нигде" как нулевое адресное.
<час>В основных условиях, что такое указателем?
указатель А просто переменной, содержащей адрес памяти. Вы обычно просит, чтобы язык программирования давать Вам свое число, но большинство языков программирования и времени выполнения попытавшиеся скрывать то, что быть число под, просто потому что само число действительно содержит значение Вам. Лучше думать об указателе как черном квадрате, т.е. Вы действительно знает или заботящиеся о том, как это на самом деле реализовываемое, пока это работает.
4 ответа
В дополнение к другим решениям:
Вы можете находить «плотные» области и использовать растровые изображения для их хранения.
Так, например:
Если у вас есть 1000 чисел в 400 диапазонах от 1000 до 3000, вы можете использовать один бит для обозначения существования числа и два целых числа для обозначения диапазона. Общий объем хранилища для этого диапазона составляет 2000 бит + 2 целых числа, поэтому вы можете хранить эту информацию в 254 байтах, что довольно круто, поскольку даже короткие целые числа будут занимать по два байта каждое, поэтому в этом примере вы получите экономию в 7 раз.
Чем плотнее области, тем лучше будет этот алгоритм, но в какой-то момент просто сохранение начала и конца будет дешевле.
Основная идея, которую вы, вероятно, должны использовать, состоит в том, что для каждого диапазона последовательных целых чисел (я назову эти диапазоны), чтобы сохранить начальный номер и размер диапазона. Например, если у вас есть список из 1000 целых чисел, но есть только 10 отдельных диапазонов, вы можете сохранить всего 20 целых чисел (1 начальный номер и 1 размер для каждого диапазона) для представления этих данных, что будет иметь степень сжатия 98. %. К счастью, вы можете сделать еще несколько оптимизаций, которые помогут в случаях, когда количество диапазонов больше.
Сохраните смещение начального числа относительно предыдущего начального числа, а не само начальное число. Преимущество здесь в том, что для сохраняемых чисел обычно требуется меньше бит (это может пригодиться в последующих предложениях по оптимизации). Кроме того, если вы сохранили только начальные числа, все эти числа будут уникальными, а сохранение смещения дает шанс, что числа близки или даже повторяются, что может позволить еще большее сжатие с применением другого метода после этого.
Используйте минимальное возможное количество битов для обоих типов целых чисел. Вы можете перебирать числа, чтобы получить наибольшее смещение начального целого числа, а также размер наибольшего диапазона. Затем вы можете использовать тип данных, который наиболее эффективно хранит эти целые числа, и просто указать тип данных или количество бит в начале сжатых данных. Например, если наибольшее смещение начального целого числа составляет всего 12000, а самый большой диапазон составляет 9000, тогда вы можете использовать 2-байтовое целое число без знака для всех этих случаев. Затем вы можете втиснуть пару 2,2 в начало сжатых данных, чтобы показать, что 2 байта используются для обоих целых чисел. Конечно, вы можете уместить эту информацию в один байт, немного манипулируя битами. Если вам удобно выполнять много тяжелых манипуляций с битами, вы можете хранить каждое число как минимально возможное количество битов, а не в соответствии с 1, 2, 4 или 8-байтовыми представлениями.
С этими двумя оптимизациями давайте посмотрим на пара примеров (каждый по 4000 байтов):
- 1000 целых чисел, наибольшее смещение - 500, 10 диапазонов
- 1000 целых чисел, наибольшее смещение - 100, 50 диапазонов
- 1000 целых чисел, наибольшее смещение - 50, 100 диапазонов
БЕЗ ОПТИМИЗАЦИИ
- 20 целых чисел по 4 байта каждое = 80 байтов. СЖАТИЕ = 98%
- 100 целых чисел, 4 байта каждое = 400 байтов. СЖАТИЕ = 90%
- 200 целых чисел по 4 байта каждое = 800 байтов. СЖАТИЕ = 80%
С ОПТИМИЗАЦИЯМИ
- 1 байт заголовка + 20 чисел, по 1 байту каждое = 21 байт. СЖАТИЕ = 99,475%
- 1 байт заголовка + 100 чисел, по 1 байту каждое = 101 байт. СЖАТИЕ = 97,475%
- 1 байт заголовка + 200 чисел, по 1 байту каждое = 201 байт. СЖАТИЕ = 94.975%
Какой размер у чисел? В дополнение к другим ответам вы могли бы рассмотреть вариант кодирования длины base-128, который позволяет хранить меньшие числа в отдельных байтах, при этом позволяя использовать более крупные числа. MSB означает «есть еще один байт» - это описано здесь.
Объедините это с другими методами, чтобы вы сохраняли «размер пропуска», «размер взятия», «размер пропуска», » взять размер », но с учетом того, что ни« пропустить », ни« взять » будет когда-либо равным нулю, поэтому мы вычтем единицу из каждого (что позволит вам сохранить дополнительный байт для нескольких значений)
Итак:
1-100, 110-160
- это «пропустить 1» (предположим, что начало с нуля, поскольку это упрощает задачу ), «дубль 100», «пропустить 9», «дубль 51»; вычтите 1 из каждого, получив (в виде десятичных знаков)
0,99,8,50
, который кодируется как (шестнадцатеричный):
00 63 08 32
Если бы мы хотели пропустить / взять большее число - например, 300; мы вычитаем 1 и получаем 299, но это превышает 7 бит; начиная с малого конца, мы кодируем блоки из 7 бит и старший бит для обозначения продолжения:
299 = 100101100 = (in blocks of 7): 0000010 0101100
поэтому, начиная с малого конца:
1 0101100 (leading one since continuation)
0 0000010 (leading zero as no more)
давая:
AC 02
Таким образом, мы можем легко кодировать большие числа, но маленькие числа (которые звук типичный для пропуска / взятия) занимает меньше места.
Вы можете попробовать запустить это через "deflate", но это может не помочь больше ...
Если вы не сделаете ' Я хочу разобраться со всей этой грязной кодировкой самостоятельно ... если вы можете создать целочисленный массив значений (0,99,8,60) - вы можете использовать буферы протокола с упакованными повторяющимися uint32 / uint64 - и он сделает всю работу за вас ;-p
Я не «делаю» Java, но вот полная реализация C # (заимствованная часть битов кодирования из моего protobuf-net project):
using System;
using System.Collections.Generic;
using System.IO;
using System.Linq;
static class Program
{
static void Main()
{
var data = new List<int>();
data.AddRange(Enumerable.Range(1, 100));
data.AddRange(Enumerable.Range(110, 51));
int[] arr = data.ToArray(), arr2;
using (MemoryStream ms = new MemoryStream())
{
Encode(ms, arr);
ShowRaw(ms.GetBuffer(), (int)ms.Length);
ms.Position = 0; // rewind to read it...
arr2 = Decode(ms);
}
}
static void ShowRaw(byte[] buffer, int len)
{
for (int i = 0; i < len; i++)
{
Console.Write(buffer[i].ToString("X2"));
}
Console.WriteLine();
}
static int[] Decode(Stream stream)
{
var list = new List<int>();
uint skip, take;
int last = 0;
while (TryDecodeUInt32(stream, out skip)
&& TryDecodeUInt32(stream, out take))
{
last += (int)skip+1;
for(uint i = 0 ; i <= take ; i++) {
list.Add(last++);
}
}
return list.ToArray();
}
static int Encode(Stream stream, int[] data)
{
if (data.Length == 0) return 0;
byte[] buffer = new byte[10];
int last = -1, len = 0;
for (int i = 0; i < data.Length; )
{
int gap = data[i] - 2 - last, size = 0;
while (++i < data.Length && data[i] == data[i - 1] + 1) size++;
last = data[i - 1];
len += EncodeUInt32((uint)gap, buffer, stream)
+ EncodeUInt32((uint)size, buffer, stream);
}
return len;
}
public static int EncodeUInt32(uint value, byte[] buffer, Stream stream)
{
int count = 0, index = 0;
do
{
buffer[index++] = (byte)((value & 0x7F) | 0x80);
value >>= 7;
count++;
} while (value != 0);
buffer[index - 1] &= 0x7F;
stream.Write(buffer, 0, count);
return count;
}
public static bool TryDecodeUInt32(Stream source, out uint value)
{
int b = source.ReadByte();
if (b < 0)
{
value = 0;
return false;
}
if ((b & 0x80) == 0)
{
// single-byte
value = (uint)b;
return true;
}
int shift = 7;
value = (uint)(b & 0x7F);
bool keepGoing;
int i = 0;
do
{
b = source.ReadByte();
if (b < 0) throw new EndOfStreamException();
i++;
keepGoing = (b & 0x80) != 0;
value |= ((uint)(b & 0x7F)) << shift;
shift += 7;
} while (keepGoing && i < 4);
if (keepGoing && i == 4)
{
throw new OverflowException();
}
return true;
}
}
Хотя вы можете разработать собственный алгоритм, специфичный для вашего потока данных, вероятно, проще использовать готовый алгоритм кодирования. Я провел несколько тестов алгоритмов сжатия, доступных в Java , и обнаружил следующие степени сжатия для последовательности из миллиона последовательных целых чисел:
None 1.0
Deflate 0.50
Filtered 0.34
BZip2 0.11
Lzma 0.06