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

Question

У меня есть база данных sqlite, заполненная огромным количеством URL-адресов, и она занимает огромное количество дискового пространства, и доступ к ней вызывает много операций поиска на диске и медленный. Средняя длина пути URL составляет 97 байт (имена хостов повторяются, поэтому я переместил их в таблицу с внешним ключом). Есть ли хороший способ сжать их? Большинство алгоритмов сжатия хорошо работают с большими документами, а не с «документами» размером менее 100 байт, но даже сокращение на 20% было бы очень полезно. Любые алгоритмы сжатия, которые будут работать? Не должно быть ничего стандартного.

Answer 1

Используйте алгоритм сжатия, но используйте общий словарь.

Я делал что-то подобное раньше, где использовал алгоритм LZC / LZW, используемый командой сжатия Unix.

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

Вы должны легко получить 20%.

Редактировать: LZC - это вариант LZW. Вам нужен только LZW, так как вам нужен только статический словарь. LZC добавляет поддержку для сброса словаря / таблицы, когда она заполняется.

Answer 2

Я пробовал это, используя следующую стратегию. Он использует общий словарь, но работает так, как 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 символов) строк юникода. Для их сжатия и распаковки также потребовалось около 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 

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

Answer 3

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

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

Answer 4

Какой у вас формат 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%. Просто так;)

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

Answer 5

Аннотация:

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

- Касом Кохт-Арса Кафедра вычислительной техники.

Ресурс

Answer 6

Как вы используете таблицу URL?

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

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

Answer 7

Это 97 байтов, или 97 8-битных символов ASCII, или 97 16-битных символов Юникода?

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

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

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