algorithm - texto - ¿Qué es un buen algoritmo para compactar registros en un archivo bloqueado?

tipos de algoritmos de compresion

Question

Supongamos que tiene un archivo grande formado por un grupo de bloques de tamaño fijo. Cada uno de estos bloques contiene cierta cantidad de registros de tamaño variable. Cada registro debe caber completamente dentro de un solo bloque y, por definición, dichos registros nunca son más grandes que un bloque completo. Con el tiempo, los registros se agregan y eliminan de estos bloques a medida que los registros van y vienen de esta "base de datos".

En algún momento, especialmente después de que tal vez se agreguen muchos registros a la base de datos y se eliminen varios, muchos de los bloques pueden terminar llenos solo parcialmente.

¿Qué es un buen algoritmo para mezclar los registros en esta base de datos para compactar bloques innecesarios al final del archivo al rellenar mejor los bloques parcialmente llenos?

Requisitos del algoritmo:

• La compactación debe ocurrir en lugar del archivo original sin extender temporalmente el archivo en más de unos pocos bloques como máximo desde su tamaño de inicio
• El algoritmo no debería molestar innecesariamente bloques que ya están principalmente llenos
• Se deben leer o escribir bloques enteros desde / hacia el archivo a la vez y se debe suponer que la operación de escritura es relativamente costosa.
• Si los registros se mueven de un bloque a otro, deben agregarse en su nueva ubicación antes de ser eliminados de su posición inicial, de modo que en caso de que la operación se interrumpa, no se perderán registros como resultado de la compactación "fallida". (Supongamos que esta duplicación temporal de tales registros se puede detectar en la recuperación).
• La memoria que se puede usar para esta operación solo puede estar en el orden de tal vez varios bloques, que es un porcentaje muy pequeño del tamaño total del archivo
• Supongamos que los registros están en el orden de 10 bytes a 1K bytes con un tamaño promedio de quizás 100 bytes. Los bloques de tamaño fijo son del orden de 4K o 8K y el archivo está en el orden de 1000 de bloques.

Answer 1

Aquí hay un algoritmo que podría aprovechar, aunque sus registros dentro de bloques de tamaño fijo podrían requerir un poco más de trabajo.

Desfragmentación de montón en tiempo limitado

Answer 2

Esto suena como una variación del problema del empaquetamiento de los contenedores , pero donde ya tiene una asignación inferior que desea mejorar. Por lo tanto, sugiero observar las variaciones de los enfoques que son exitosos para el problema del empaque en el contenedor.

En primer lugar, es probable que desee parametrizar su problema definiendo lo que considera "lo suficientemente completo" (donde un bloque está lo suficientemente lleno para que no desee tocarlo), y lo que está "demasiado vacío" (donde un bloque tiene tanto espacio vacío que tiene que tener más registros agregados). Luego, puede clasificar todos los bloques como suficientemente llenos, demasiado vacíos o parcialmente llenos (los que no están suficientemente llenos ni demasiado vacíos). A continuación, redefine el problema de cómo eliminar todos los bloques demasiado vacíos creando tantos bloques lo más completos posible como minimizando la cantidad de bloques parcialmente llenos.

También querrá saber qué es más importante: obtener los registros en el menor número posible de bloques, o empaquetarlos adecuadamente, pero con la menor cantidad de bloques leídos y escritos.

Mi enfoque sería hacer un pase inicial sobre todos los bloques, para clasificarlos a todos en una de las tres clases definidas anteriormente. Para cada bloque, también desea realizar un seguimiento del espacio libre disponible en él, y para los bloques demasiado vacíos, querrá tener una lista de todos los registros y sus tamaños. Luego, comenzando con los registros más grandes en los bloques demasiado vacíos, muévalos a los bloques parcialmente llenos. Si desea minimizar las lecturas y escrituras, muévalas a cualquiera de los bloques que tiene actualmente en la memoria. Si desea minimizar el espacio perdido, busque el bloque con la menor cantidad de espacio vacío que aún contenga el registro, leyendo el bloque si es necesario. Si ningún bloque retendrá el registro, crea un nuevo bloque. Si un bloque en la memoria alcanza el umbral "suficientemente lleno", escríbalo. Repita hasta que se hayan colocado todos los registros en los bloques parcialmente llenos.

Me salté más de unos pocos detalles, pero esto debería darte una idea. Tenga en cuenta que el problema del empaque de contenedores es NP-hard , lo que significa que para aplicaciones prácticas, deberá decidir qué es lo más importante para usted, de modo que pueda elegir un enfoque que le proporcione la mejor solución en un tiempo razonable.

Answer 3

Podría funcionar aquí una modificación de un algoritmo de empaquetado de contenedores en línea (para desfragmentar en un paso) el espacio delimitado (los requisitos de memoria).

Ver "Algoritmos de aproximación de empaquetamiento de bandejas: Análisis combinatorio" por Coffman et al.

Answer 4

Si no hay ordenamiento para estos registros, simplemente llenaría los bloques desde el frente con los registros extraídos del último bloque (s). Esto minimizará el movimiento de los datos, es bastante simple y debe hacer un trabajo decente para empaquetar los datos de forma ajustada.

P.ej:

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

Actualización: olvidé mantener la regla de no-blocks-only-in-memory. He actualizado el pseudocódigo para solucionar esto. También solucionó un problema en mi condición de bucle.