Что такое хороший алгоритм для сжатия записей в заблокированном файле?

Question

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

В какой-то момент, особенно после того, как, возможно, многие записи добавлены в базу данных, а некоторые удалены - многие блоки могут закончиться только частично.

Каков хороший алгоритм для перетасовки записей в этой базе данных, чтобы сжать ненужные блоки в конце файла, лучше заполняя частично заполненные блоки?

Требования к алгоритму:

• Сжатие должно происходить вместо исходного файла без временного расширения файла не более чем на несколько блоков от его начального размера
• Алгоритм не должен излишне мешать блокам, которые уже в основном заполнены
• Целые блоки должны быть прочитаны или записаны из / в файл одновременно, и следует предположить, что операция записи является относительно дорогой
• Если записи перемещаются из одного блока в другой, они должны быть добавлены в новом месте перед удалением из исходного положения, чтобы в случае прерывания операции записи не терялись в результате «неудачного» сжатия. (Предположим, что это временное дублирование таких записей может быть обнаружено при восстановлении).
• Память, которая может быть использована для этой операции, может быть порядка нескольких блоков, что составляет очень маленький процент от общего размера файла
• Предположим, что записи имеют порядок от 10 байт до 1 Кбайт со средним размером, возможно, 100 байт. Блоки фиксированного размера имеют порядок 4K или 8K, а размер файла - порядка 1000 блоков.

Answer 1

Модификация алгоритма упаковки ограниченного пространства в режиме онлайн (для дефрагментации за один проход) (требования к памяти), вероятно, могла бы работать здесь.

См. "Алгоритмы аппроксимации бункерной упаковки: комбинаторный анализ" , автор Коффман и др.

Answer 2

Это звучит как вариант проблемы упаковки бина , но там, где у вас уже есть низкое распределение, которое вы хотите улучшить. Поэтому я предлагаю рассмотреть варианты подходов, которые являются успешными для решения проблемы упаковки бина.

Прежде всего, вы, вероятно, захотите параметризовать свою проблему, определив, что вы считаете «достаточно полным» (где блок достаточно полон, чтобы вы не хотели его касаться), и что «слишком пусто» (где блок имеет так много пустого пространства, что к нему нужно добавить больше записей). Затем вы можете классифицировать все блоки как достаточно полные, слишком пустые или частично полные (те, которые не являются ни полными, ни слишком пустыми). Затем вы переопределяете проблему так, как устранить все слишком пустые блоки, создав как можно больше заполненных блоков при минимальном количестве частично заполненных блоков.

Вы также захотите решить, что важнее: собрать записи в наименьшее количество возможных блоков или упаковать их соответствующим образом, но с наименьшим количеством прочитанных и записанных блоков.

Мой подход состоял бы в том, чтобы сделать начальный проход по всем блокам, чтобы классифицировать их все в один из трех классов, определенных выше. Для каждого блока вы также хотите отслеживать доступное в нем свободное пространство, а для слишком пустых блоков вам нужен список всех записей и их размеров. Затем, начиная с самых больших записей в слишком пустых блоках, переместите их в частично заполненные блоки. Если вы хотите минимизировать чтение и запись, переместите их в любой из блоков, которые у вас есть в памяти. Если вы хотите минимизировать потерянное пространство, найдите блок с наименьшим количеством пустого пространства, в котором все еще будет храниться запись, считывая блок при необходимости. Если ни один блок не будет содержать запись, создайте новый блок. Если блок в памяти достигает «достаточно полного» порога, запишите его. Повторяйте, пока все записи в частично заполненных блоках не будут размещены.

Я пропустил более нескольких деталей, но это должно дать вам некоторое представление. Обратите внимание, что проблема упаковки бункера составляет NP-hard , что означает, что для практических применений вы захотите решить, что для вас наиболее важно, поэтому вы можете выбрать подход, который даст вам примерно лучшее решение в разумные сроки.

Answer 3

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

например:.

// records should be sorted by size in memory (probably in a balanced BST)
records = read last N blocks on disk;

foreach (block in blocks) // read from disk into memory
{
    if (block.hasBeenReadFrom())
    {
        // we read from this into records already
        // all remaining records are already in memory

        writeAllToNewBlocks(records);

        // this will leave some empty blocks on the disk that can either
        // be eliminated programmatically or left alone and filled during
        // normal operation

        foreach (record in records)
        {
            record.eraseFromOriginalLocation();
        }

        break;
    }

    while(!block.full())
    {
        moveRecords = new Array; // list of records we've moved

        size = block.availableSpace();
        record = records.extractBestFit(size);
        if (record == null)
        {
            break;
        }

        moveRecords.add(record);
        block.add(record);

        if (records.gettingLow())
        {
            records.readMoreFromDisk();
        }
    }

    if(moveRecords.size() > 0)
    {
        block.writeBackToDisk();
        foreach (record in moveRecords)
        {
            record.eraseFromOriginalLocation();
        }
    }
}

Обновление: я забыл сохранить правило "нет блоков только в памяти". Я обновил псевдокод, чтобы исправить это. Также исправлен глюк в моем состоянии цикла.

Answer 4

Вот алгоритм, который вы можете использовать, хотя ваши записи внутри блоков фиксированного размера могут потребовать немного больше работы.

Дефрагментация кучи в ограниченное время