Как сжать маленькие строки

Вы рассмотрели использование статического Кодирования методом Хаффмана?

Вы могли использовать существующее тело URL для вычислений кодов Huffmann по всем байтам, происходящим в URL согласно их частоте. Можно затем сохранить тот набор кодов однажды и закодировать все URL с помощью него. Я думаю, что это должно дать достойное сжатие.

Каков формат Ваших URL?

Если какая-либо доля URL один или несколько домен и Вы достаточны приблизительно с 2 миллиардами доменных имен, можно создать пул для доменных имен. И если Вы совместно использовали относительные пути, можно объединить их к.

Для каждого URL в Вашей базе данных, разделение каждый URL в три части. схема и домен, например, http://mydomain.com относительный URL/my/path/и затем остальные mypage.html? id=4 (если у Вас есть параметры строки запроса),

Таким образом, необходимо уменьшить издержки каждого доменного и относительного пути примерно к 8 байтам. Это должно быть лучше, и быстро если Вы хотите части поиска URL.

Примечание: просто сама "http" строка схемы составляет 4 байта, Вы сохраните что-либо кроме того на каждой доменной записи. Если каждый URL запускается с "http://www". Вы сохраните "://www". 7 байтов каждый раз.

Экспериментируйте немного о том, как разделить и структурировать URL, я держу пари, что это, были, Вы найдете свое сжатие. Теперь, остающаяся строка, которая не является общим доменным или относительным путем, что Вы могли сделать с этим?

Сжатие URL

Сжатие общего назначения такие методы получено из арифметического кодирования. Шеннон родительский элемент теории информации написал работу об этом в 60-х. Я работал со сжатием некоторое время и одной вещью, которую я всегда находил, то, что сжатие общего назначения никогда не решает фактическую проблему.

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

Если Вы хотите применить алгоритм сжатия (я думаю, что тема должна быть изменена для отражения сжатия URL, потому что это является зависящим от домена), необходимо будет исследовать энтропию данных. Поскольку это скажет Вам что-то об урожае устройства хранения данных. URL являются символами ASCII, любой символ не в диапазоне ASCII 0x20-0x7E не будет происходить и выбрасывать чувствительность к регистру, Вы всего до 63 отличных состояний.!" # %& '() * +,-./0123456789:; <=>? abcdefghijklmnopqrstuvwxyz {|} ~ включая пробел.

Вы могли создать таблицу частот оставшихся символов и выполнить арифметическое кодирование. Вы знаете о необходимости самое большее в 6 битах что означает для каждого символа в базе данных URL, Вы тратите впустую 2 бита прямо сейчас, и если бы Вы просто сместили вещи в место и использовали справочную таблицу, то Вы получили бы свое 20%-е сжатие. Точно так же, как это ;)

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

Это составляет 97 байтов, или 97 8-разрядных символов ASCII или 97 16-разрядных символов Unicode?

При предположении, что всеми URL являются легальные URL согласно http://www.w3.org/Addressing/URL/url-spec.txt, затем у Вас должны быть только символы ASCII.

Если 97 16-разрядных символов Unicode, просто хранящих младший байт каждого символа, автоматически дадут Вам 50%-е сбережения.

Если 97 8-разрядных символов, заметьте, что Вам только нужны 7 битов. Можно просто передать в 7 битах за один раз в битовый поток и хранилище, которые передают поток битов в базу данных; используйте некоторый более старый 7-разрядный протокол передачи; или придумайте свой собственный специальный способ сохранить биты каждого 8-го символа в высоких битах предыдущих 7 символов.

Краткий обзор:

Типичная проблема крупномасштабных поисковых систем и поисковых роботов состоит в том, как обработать огромное количество URL, с которыми встречаются. Традиционные поисковые системы и поисковые роботы используют жесткий диск для хранения URL без любого сжатия. Это приводит к медленной производительности и большей необходимой площади. Данная статья описывает простой алгоритм сжатия URL, позволяющий эффективное сжатие и распаковку. Алгоритм сжатия основан на схеме кодирования дельты для извлечения URL, совместно использующих общие префиксы и дерево AVL для получения эффективной поисковой скорости. Наши результаты показывают, что 50% сокращения размера достигаются. 1.

- Отдел Kasom Koht-arsa вычислительной техники.

Ресурс

Как Вам используют таблицу URL?

Вы обычно делаете "сканирование диапазона" или поиск уникального идентификатора только?

Если Вы не сделаете чего-то как WHERE url like "/xxxx/question/%". Вы могли использовать хешированный индекс скорее затем индекс B-дерева на varchar () для сокращения количества поиска на диске.

Я пробовал это, используя следующую стратегию. Он использует общий словарь, но работает так, как zlib python не предоставляет вам доступ к самому словарю.

Сначала инициализируйте предварительно обученный компрессор и декомпрессор, пропустив через них кучу обучающих строк. Выбросьте выходные строки.

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

Вот мой код Python (извинения за уродливое тестирование):

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:]

При тестировании я сэкономил более 30% на кучке из 10 000 коротких (50 -> 300 символов) строк Unicode. На их сжатие и распаковку также ушло около 6 секунд (по сравнению с 2 секундами при использовании простого сжатия / распаковки zlib). С другой стороны, простое сжатие zlib сэкономило около 5%, не 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 

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