buy - sqlite website

Cómo comprimir pequeñas cadenas

Question

Tengo una base de datos sqlite llena de una gran cantidad de URL y está tomando una gran cantidad de espacio de disco, y acceder a ella provoca muchas búsquedas de disco y es lento. La longitud promedio de la ruta URL es de 97 bytes (los nombres de los hosts se repiten mucho, así que los moví a una tabla con clave foránea). ¿Hay alguna buena forma de comprimirlos? La mayoría de los algoritmos de compresión funcionan bien con documentos grandes, no con "documentos" de menos de 100 bytes en promedio, pero incluso una reducción del 20% sería muy útil. Algún algoritmo de compresión que funcionaría? No tiene que ser nada estándar.

Answer 1

¿Cuál es el formato de tus URL?

Si alguna URL comparte uno o más dominios y usted es suficiente con aproximadamente 2 mil millones de nombres de dominio, puede crear un grupo de nombres de dominio. Y si ha compartido rutas relativas puede agruparlas.

Para cada URL en su base de datos, divida cada URL en tres partes. el esquema y el dominio, por ejemplo, http://midominio.com el URL real / mi / ruta / y luego el resto mypage.html? id = 4 (si tiene parámetros de cadena de consulta)

De esta forma, debe reducir la sobrecarga de cada dominio y ruta relativa a solo alrededor de 8 bytes. Eso debería ser mejor, y rápido si quiere buscar partes de las URL.

Nota: solo la cadena de esquema "http" en sí tiene 4 bytes, guardará cualquier cosa más allá en cada entrada de dominio. Si cada URL comienza con " http: // www ." guardará ": // www." 7 bytes cada vez.

Experimente un poco sobre cómo dividir y estructurar las URL, apuesto a que esto es donde encontrará su compresión. Ahora, la cadena restante que no es un dominio común o una ruta relativa, ¿qué podrías hacer con eso?

Compresión de URL

Compresión de uso general tales métodos se derivan de la codificación aritmética. Shannon, el padre de la teoría de la información, escribió un artículo sobre esto en los años 60. He estado trabajando con compresión por un tiempo y la única cosa que siempre he encontrado es que la compresión de uso general nunca resuelve el problema real.

Estás de suerte, porque las URL tienen estructura y esa estructura que debes utilizar para almacenar mejor tus URL.

Si desea aplicar un algoritmo de compresión (creo que el tema debe modificarse para reflejar la compresión de URL porque es un dominio específico), tendrá que examinar la entropía de sus datos. Porque le dirá algo sobre el rendimiento del almacenamiento. Las URL son caracteres ASCII, cualquier carácter que no esté dentro del rango ASCII 0x20-0x7E no se producirá y descartando la distinción entre mayúsculas y minúsculas, se reduce a solo 63 estados distintos. ! "#% & ''() * +, -. / 0123456789:; <=>? @ Abcdefghijklmnopqrstuvwxyz {|} ~ incluido el espacio en blanco.

Puede crear una tabla de frecuencias de los caracteres restantes y realizar la codificación aritmética. Sabes que necesitarás como máximo 6 bits, lo que significa que por cada personaje de tu base de datos de URL estás desperdiciando 2 bits en este momento, y si simplemente cambiaras de lugar y usaras una tabla de búsqueda, obtendrías tu 20% de compresión. Solo así;)

Debido a que los datos son tan específicos, realmente no es una buena idea simplemente comprimir con métodos de propósito general. Es mejor estructurar la información y dividirla en partes de datos que pueda almacenar de manera más eficiente. Usted sabe mucho sobre el dominio, use ese conocimiento para comprimir sus datos.

Answer 2

¿Cómo se usa la tabla de URL?

¿Usualmente hace un "escaneo de rango" o una búsqueda de identificación única solamente?

Si no va a hacer algo como WHERE url like "/xxxx/question/%" . Puede usar un índice hash en lugar de un índice b-tree en varchar () para reducir el número de búsquedas de disco.

Answer 3

¿Es eso 97 bytes, o 97 caracteres ASCII de 8 bits, o 97 caracteres Unicode de 16 bits?

Suponiendo que todas sus URL son URL legales según http://www.w3.org/Addressing/URL/url-spec.txt , entonces debe tener solo caracteres ASCII.

Si 97 caracteres Unicode de 16 bits que simplemente almacenan el byte inferior de cada personaje automáticamente le darán un 50% de ahorro.

Si tiene 97 caracteres de 8 bits, observe que solo necesita 7 bits. Simplemente puede pasar 7 bits a la vez en su flujo de bits y almacenar ese flujo de bits en su base de datos; utilice algún protocolo de transmisión de 7 bits anterior; o crea tu propia forma adhoc de almacenar los bits de cada 8vo personaje en los bits altos de los 7 caracteres anteriores.

Answer 4

¿Has considerado utilizar la codificación estática de Huffman ?

Podría utilizar su cuerpo existente de URL para calcular los códigos de Huffmann sobre todos los bytes que aparecen en las URL de acuerdo con su frecuencia. A continuación, puede almacenar ese conjunto de códigos una vez y codificar todas las URL que lo utilizan. Creo que debería dar una compresión decente.

Answer 5

Use el algoritmo de compresión pero use un diccionario compartido.

He hecho algo como esto antes, donde usé el algoritmo LZC / LZW, tal como lo usa el comando de compresión Unix.

El truco para obtener una buena compresión con cadenas cortas es usar un diccionario compuesto por una muestra estándar de las URL que está comprimiendo.

Deberías obtener fácilmente el 20%.

Editar: LZC es una variante de LZW. Solo necesita LZW ya que solo necesita un diccionario estático. LZC agrega soporte para reiniciar el diccionario / tabla cuando se llena.

Answer 6

Abstracto:

Un problema común de los motores de búsqueda a gran escala y arañas web es cómo manejar una gran cantidad de URL encontradas. Los motores de búsqueda tradicionales y las arañas web usan el disco duro para almacenar las URL sin ninguna compresión. Esto resulta en un rendimiento lento y más necesidad de espacio. Este artículo describe un algoritmo simple de compresión de URL que permite una compresión y descompresión eficiente. El algoritmo de compresión se basa en un esquema de codificación delta para extraer URL que comparten prefijos comunes y un árbol AVL para obtener una velocidad de búsqueda eficiente. Nuestros resultados muestran que se logra el 50% de reducción de tamaño. 1.

- Departamento de Ingeniería Informática Kasom Koht-arsa.

Recurso

Answer 7

Lo he intentado usando la siguiente estrategia. Está utilizando un diccionario compartido, pero está trabajando en la forma en que zlib de python no le da acceso al diccionario en sí.

Primero, inicialice un compresor precompuesto y un descompresor ejecutando un conjunto de cadenas de entrenamiento a través de ellos. Bote las cadenas de salida.

Luego, use copias del compresor entrenado para comprimir cada cuerda pequeña y use copias del descompresor para descomprimirlas.

Aquí está el código de Python (disculpas por las feas pruebas):

import zlib
class Trained_short_string_compressor(object):
    def __init__(self,
                 training_set, 
                 bits = -zlib.MAX_WBITS,
                 compression = zlib.Z_DEFAULT_COMPRESSION,
                 scheme = zlib.DEFLATED):
        # Use a negative number of bits, so the checksum is not included.
        compressor = zlib.compressobj(compression,scheme,bits)
        decompressor = zlib.decompressobj(bits)
        junk_offset = 0
        for line in training_set:
            junk_offset += len(line)
            # run the training line through the compressor and decompressor
            junk_offset -= len(decompressor.decompress(compressor.compress(line)))

        # use Z_SYNC_FLUSH. A full flush seems to detrain the compressor, and 
        # not flushing wastes space.
        junk_offset -= len(decompressor.decompress(compressor.flush(zlib.Z_SYNC_FLUSH)))

        self.junk_offset = junk_offset
        self.compressor = compressor
        self.decompressor = decompressor

    def compress(self,s):
        compressor = self.compressor.copy()
        return compressor.compress(s)+compressor.flush()

    def decompress(self,s):
        decompressor = self.decompressor.copy()
        return (decompressor.decompress(s)+decompressor.flush())[self.junk_offset:]

Al probarlo, guardé más del 30% en un grupo de 10.000 cadenas de caracteres unicode shortish (50 -> 300 caracteres). También les llevó unos 6 segundos comprimirlos y descomprimirlos (en comparación con aproximadamente 2 segundos con compresión / descompresión simple de zlib). Por otro lado, la compresión zlib simple ahorró aproximadamente un 5%, no un 30%.

def test_compress_small_strings():
    lines =[l for l in gzip.open(fname)]
    compressor=Trained_short_string_compressor(lines[:500])

    import time
    t = time.time()
    s = 0.0
    sc = 0.
    for i in range(10000):
        line = lines[1000+i] # use an offset, so you don''t cheat and compress the training set
        cl = compressor.compress(line)
        ucl = compressor.decompress(cl)
        s += len(line)
        sc+=len(cl)
        assert line == ucl

    print ''compressed'',i,''small strings in'',time.time()-t,''with a ratio of'',s0/s
    print ''now, compare it ot a naive compression ''
    t = time.time()
    for i in range(10000):
        line = lines[1000+i]
        cr = zlib.compressobj(zlib.Z_DEFAULT_COMPRESSION,zlib.DEFLATED,-zlib.MAX_WBITS)
        cl=cr.compress(line)+cr.flush()
        ucl = zlib.decompress(cl,-zlib.MAX_WBITS)
        sc += len(cl)
        assert line == ucl


    print ''naive zlib compressed'',i,''small strings in'',time.time()-t, ''with a ratio of '',sc/s 

Tenga en cuenta que no es persistente si lo elimina. Si quisieras persistencia, tendrías que recordar el conjunto de entrenamiento.