Индексирование и сжатие

71

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

Кодировка переменной длины

Пусть имеется коллекция 50 000 000 положительных целых чисел, которую требуется сохранить на диске, при этом мы можем гарантировать, что все значения в коллекции смогут уместиться в 32-разрядной переменной типа int. В простейшем случае можно просто сохранить 50 000 000 32-разрядных целых чисел на диске, заняв 200 000 000 байт. Но нам нужна более эффективная альтернатива, которая позволила бы сэкономить дисковое пространство. (Одной из причин применения сжатия может быть более высокая скорость загрузки данных в память.)

Кодировка переменной длины (variable length encoding) - это методика сжатия, пригодная для применения к последовательностям чисел, в которых присутствуют маленькие значения. Прежде чем приступать к знакомству с ней, необходимо убедиться в наличии большого количества маленьких чисел в коллекции, чего, похоже, в настоящий момент не наблюдается.

Если 50 000 000 целых чисел равномерно распределены в диапазоне [0, 232], тогда более 99% из них не уместятся в 3 байта и для их хранения потребуется все 4 байта. Однако, перед сохранением на диск числа можно отсортировать и вместо самих чисел сохранять на диске только пустые промежутки. Этот трюк так и называется - сжатие промежутков (gap compression). Он наверняка позволит уменьшить числа в сохраняемой последовательности и восстановить первоначальную последовательность.

Например, последовательность (38, 14, 77, 5, 90) сначала сортируется и получается последовательность (5, 14, 38, 77, 90), а затем кодируется с использованием приема сжатия промежутков в последовательность (5, 9, 24, 39, 13). Обратите внимание, что числа в результате получаются намного меньше и среднее количество битов, необходимое для их хранения, уменьшается значительно. В нашем случае, когда 50 000 000 целых чисел равномерно распределены в диапазоне [0, 232], числа, описывающие большинство промежутков, наверняка будут укладываться в один байт.

Теперь рассмотрим основу приема кодировки переменной длины, который является лишь одним из множества приемов сжатия данных, известных в теории информации. Идея этого приема состоит в том, чтобы использовать наибольший значащий бит в каждом байте, чтобы показать, является ли этот байт последним в представлении целого числа или нет. Если бит сброшен, производится переход к следующему байту и восстановление числа продолжается; если бит установлен, чтение последовательности байтов останавливается и выполняется декодирование числа из прочитанной последовательности.

Например, число 13 кодируется как 10001101 - старший бит установлен, поэтому данный байт содержит полное целое число и остальная его часть является простым двоичным представлением числа 13. Далее, число 132 кодируется как 000000001'10000100. В первом байте старший бит сброшен, поэтому остальные семь бит 0000001 сохраняются, в следующем байте старший бит установлен, поэтому оставшиеся семь бит добавляются к предыдущим семи битам и получается значение 10000100, являющееся двоичным представлением числа 132. В этом примере одно число было сохранено в одном байте, а другое - в двух байтах. Сохранение промежутков, полученных на предыдущем шаге, с использованием данного приема позволит сжать исходные данные почти в четыре раза. (Вы можете попробовать поэкспериментировать со случайными числами и подтвердить этот результат.)

Сжатие индексов

Чтобы обеспечить эффективное хранение индексов слов, встречающихся в веб-страницах - что является основой любого поискового механизма - для каждого слова необходимо сохранить номера страниц (или адреса URL), в которых они встречаются, и сжать данные, обеспечив эффективный доступ к ним. В типичных поисковых системах в оперативной памяти хранятся только словари из слов, но не номера страниц.

Сохранение на диске номеров страниц лучше выполнять с применением кодировки переменной длины, с которой мы только что познакомились. Но сохранение самого словаря является гораздо более сложной задачей. В идеале, словарь - это простой массив, содержащий встреченные слова, и смещение в дисковом файле, где хранятся номера страниц, где встречается данное слово. Чтобы повысить эффективность доступа к этим данным, они должны быть отсортированы - это гарантирует время доступа к ним O(log n).

Допустим, что каждая запись в словаре, хранящемся в памяти, является значением следующего типа значения на языке C#, а сам словарь является массивом этих записей:

struct DictionaryEntry
{
    public string Word;
    public ulong DiskOffset;
}

DictionaryEntry[] dictionary = // ...

Массивы типов значений состоят исключительно из экземпляров этих типов. Однако каждый экземпляр содержит ссылку на строку; для n записей эти ссылки, наряду со смещениями в дисковом файле, будут занимать 16n байт в 64-разрядной системе. Мало того, что сам словарь слов будет занимать немалый объем ценной памяти, так еще и каждое слово в словаре будет храниться как отдельная строка, что потребует дополнительно 24 байта (16 байт на заголовок объекта + 4 байта на длину строки + 4 байта для хранения количества символов во внутреннем буфере, выделяемом для строки).

Мы можем значительно уменьшить объем памяти, занимаемой словарем, объединив все слова в одну большую строку и сохранив их смещения в этой строке, как показано на рисунке ниже:

Общая структура словаря в памяти и каталога в строке

Размеры таких объединенных строк редко будет превышать 224 байт = 16 Мбайт, откуда поле индекса может быть выражено 3-байтным целым числом, вместо 8-байтного адреса в памяти:

[StructLayout(LayoutKind.Sequential, Pack = 1, Size = 3)]
struct ThreeByteInteger 
{
    private byte a, b, c;
    public ThreeByteInteger() {}
    public ThreeByteInteger(uint integer) {/*... */}
    
    public static implicit operator int(ThreeByteInteger tbi) 
    {
        // ...
    }
}

struct DictionaryEntry 
{
    public ThreeByteInteger LongStringOffset;
    public ulong DiskOffset;
}

class Dictionary {
    public DictionaryEntry[] Entries = // ...
    public string LongString;
}

В результате мы получаем возможность организации поиска в массиве методом половинного деления - потому что все записи имеют одинаковый размер - а объем занимаемой памяти оказывается намного меньше. Мы сэкономили 24n байт на строковых объектах (так как теперь все слова хранятся в одной большой строке) и еще 5n байт на ссылках на строки, заменив указатели смещениями.

Итак, в этой и предыдущих статьях мы исследовали некоторые положения теоретической информатики, включая анализ сложности алгоритмов, их проектирование и оптимизацию. Как вы могли видеть, оптимизация алгоритмов не является чем-то, доступным только посвященным; в реальной жизни встречается множество ситуаций, когда выбор правильного алгоритма или использование приемов сжатия может существенно повысить производительность. В частности, разделы, описывающие приемы динамического программирования, хранения индексов и алгоритмов аппроксимации, содержат рецепты, которые вы сможете адаптировать для своих приложений.

Пройди тесты
Лучший чат для C# программистов