Как сжать небольшие струны

Ответ 1

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

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

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

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

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

Ответ 2

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

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

Ответ 3

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

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

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

Здесь мой код 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 char) строк юникода. Также потребовалось около 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 

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

Ответ 4

Каков формат ваших URL-адресов?

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

Для каждого URL в вашей базе данных разделите каждый URL на три части. схема и домен, например. http://mydomain.com realtive 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% сжатие. Просто так:)

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

Ответ 5

Аннотация:

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

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

Ресурс

Ответ 6

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

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

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

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

Ответ 7

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

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

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