O que é um bom algoritmo para compactação de registros em um arquivo bloqueado?

Question

Suponha que você tenha um grande arquivo composto de uma série de blocos de tamanho fixo. Cada um destes blocos contém algumas número de registros de tamanho variável. Cada registro deve caber completamente dentro de um único bloco e, em seguida, tais registros por definição, nunca são maiores do que um bloco completo. Com o tempo, os registros são adicionados e excluídos esses blocos como registros de ir e vir de este "banco de dados".

Em algum ponto, especialmente depois talvez muitos registos são adicionados à base de dados e vários são removidos -. Muitos dos blocos pode acabar apenas parcialmente preenchido

O que é um bom algoritmo para embaralhar os registros em torno deste banco de dados para compactar os blocos desnecessários no final do arquivo, melhor encher os blocos parcialmente cheios?

Requisitos do algoritmo:

• A compactação deve acontecer no lugar do arquivo original sem estender temporariamente o arquivo por mais do que alguns blocos no máximo de seu tamanho começando
• O algoritmo não deve blocos desnecessariamente perturbar essa já estão principalmente completo
• blocos inteiros deve ser lido ou escrito de / para o arquivo de uma só vez e deve assumir a operação de gravação é relativamente caro
• Se os registros são movidos de um bloco para outro eles devem ser adicionados em sua nova localização antes de ser removido de sua posição inicial para que, no caso, a operação é interrompida há registros são perdidos como resultado da compactação "falhou". (Assume-se que esta duplicação temporária de tais registos pode ser detectada em recuperação).
• A memória que pode ser usado para esta operação só pode ser da ordem de talvez vários blocos que é uma porcentagem muito pequena do tamanho total do arquivo
• Suponha que os registros são da ordem de 10 bytes para 1K bytes com um tamanho médio de talvez 100 bytes. Os blocos de tamanho fixo são da ordem de 4K ou 8K e que o arquivo é da ordem de 1000 de blocos.

Answer 1

Isso soa como uma variação do bin packing problema , mas onde você já tem um alocação inferior que você quer melhorar. Então, eu sugiro olhar variações das abordagens que são bem sucedidos para o problema bin embalagem.

Em primeiro lugar, você provavelmente vai querer parametrizar o seu problema, definindo o que você considera "bastante completa" (onde um bloco é suficiente completo que você não quer tocá-lo), e que é "muito vazio" (onde um bloco tem muito espaço vazio que ele tem que ter mais registros adicionados a ele). Depois, você pode classificar todos os blocos como bastante completo, muito vazio ou parcialmente cheio (aqueles que são suficientes nem completa nem muito vazio). Você, então, redefinir o problema de como eliminar todos os blocos demasiado vazios, criando tantos blocos completos suficientes quanto possível, minimizando o número de blocos parcialmente cheios.

Você também vai querer descobrir o que é mais importante:. Obtendo os registros em blocos de menor número possível, ou embalá-los de forma adequada, mas com a menor quantidade de blocos de leitura e escrita

A minha abordagem seria fazer uma passagem inicial sobre todos os blocos, para classificá-los todos em uma das três classes definidas acima. Para cada bloco, você também quer manter o controle do espaço livre disponível na mesma, e para os blocos muito vazio, você vai querer ter uma lista de todos os registros e seus tamanhos. Em seguida, começando com os maiores registos nos blocos demasiado vazios, movê-los para os blocos parcialmente cheios. Se você quiser minimizar leituras e gravações, movê-los para qualquer um dos blocos que você tem atualmente na memória. Se você quiser minimizar o espaço perdido, encontrar o bloco com a menor quantidade de espaço vazio que ainda detêm o recorde, a leitura do bloco em se necessário. Se nenhum bloco irá realizar o registro, criar um novo bloco. Se um bloco na memória atingir o limite "cheio o suficiente", escrevê-lo. Repita até que todos os registros nos blocos parcialmente cheios foram colocados.

Eu tenho pulado mais do que alguns detalhes, mas isso deve dar-lhe alguma idéia. Note-se que o problema de embalagem bin é NP-duro, o que significa que para aplicações práticas, você vai querer decidir o que é mais importante para você, então você pode escolher uma abordagem que lhe dará uma cerca melhor solução em tempo razoável.

Answer 2

Se não houver nenhuma ordenação a esses registros, eu simplesmente preencher os blocos da frente com os registros extraídos do último bloco (s). Isto irá minimizar o movimento dos dados, é bastante simples, e deve fazer um trabalho digno de embalagem de dados firmemente.

por exemplo:.

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

Update: Esqueci de manter a regra de não bloqueia-only-in-memory. Eu atualizei o pseudocódigo para corrigir isso. Também fixa uma falha na minha condição de loop.

Answer 3

A modificação de uma on-line (para desfragmentar em uma passagem) espaço limitado (os requisitos de memória) bin algoritmo embalagem provavelmente poderia trabalhar aqui.

"Bin Packing aproximação Algoritmos: Análise Combinatória" por Coffman et al.

Answer 4

Aqui está um algoritmo que você pode ser capaz de alavancagem, embora seus registros dentro de blocos de tamanho fixo pode exigir um pouco mais de trabalho.

Heap desfragmentação em Bounded Tempo