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

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

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

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

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

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

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

E.g.:

// 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();
        }
    }
}

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

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

См. «Алгоритмы приближения упаковки бункера: комбинаторный анализ» Коффмана и др. al.

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

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