Как лучше всего сжать список похожих, но не идентичных строк?

Скажем, у меня есть ряд строк, которые очень похожи, но не абсолютно идентичны.

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

Все длины равны, каждая составляет 256 байт. Общее число строк меньше 2^16.

Каков был бы наилучший метод сжатия для такого случая?

Обновление (формат данных):

Я не могу поделиться данными, но я могу описать это довольно близко к реальности:

Представьте себе нотация (как и язык логотипа), представляющая собой последовательность команд для некоторого устройства для перемещения и рисования на плоскости. Например: 

U12 - move up 12 steps
D64 - move down 64 steps
C78 - change drawing color to 78
P1  - pen down (start drawing)

И так далее.

Весь словарный запас этого языка не превышает размера английского алфавита. Затем строка описывает целую картину: "U12C6P1L74D74R74U74P0....". Представьте себе теперь класс из десяти тысяч детей, которым было сказано нарисовать с помощью этого языка какой-то очень специфический образ: например, флаг своей страны. Мы получим 10K строк, которые все разные и все одинаковые одновременно. Наша задача-сжать всю связку струн как можно лучше.

Мое подозрение здесь заключается в том, что есть способ использовать это сходство и общую длину строк, в то время как Хаффман, например, не использует его явно.

3 4
compression data-structures data-compression decompression

3 ответа:

Не могли бы вы рассказать нам, что это за данные ? Может быть, как последовательность ДНК ? Как

AGCTGTGCGAGAGAGAGCGGTGGG...

GGCTGTGCGAGCGAGCGGTGGG...

CGCTGTGAGAGNGAGCGGTGGG...

NGCTGTGCGAGAGAGAGCGGTGGG...

GGCTGTGCGAGTGAGCGGTGGG...

... ...

? Может быть, и нет. Во всяком случае, вот два уровня или два способа мышления:

  1. Кодировка Хаффмана: ref. Википедия по себя

  2. Стрингология: исх. http://books.google.com.hk/books/about/Jewels_of_stringology.html?id=9NdohJXtIyYC

Я думаю, что легко решить вашу проблему, но трудно выбрать лучший способ. Вы можете разработать несколько методов для сравнения, используя http://en.wikipedia.org/wiki/Data_compression и другие инструменты .
1

Поскольку у вас есть фиксированная ширина 256 байт, и это степень 2, я бы попробовал преобразование burrow-wheeler или алгоритм перемещения вперед с таким размером или, возможно, удвоением этого размера. Тогда вы можете попробовать код Хаффмана. Может быть, вы можете попробовать кривую Гильберта на 256 байтах, а затем bwt и mft?

0

" общее число строк меньше 2^16."Это маленькое, ограниченное число, которое делает вашу работу очень простой: почему бы вам не сохранить таблицу поиска (хэш-таблицу) всех строк, ранее виденных. Затем вы можете преобразовать каждую строку из 256 байт в двухбайтовый индекс в этой таблице подстановки.

Тогда у вас есть последовательность 16-битных целых чисел. Эти целые числа будут содержать шаблоны, такие как "после того, как перо опустилось, есть 90% шанс, что следующая команда начнет рисовать". Если данные содержит паттерны, подобные этому, PPM - это ваш выбор. 7-zip имеет высококачественную PPM-реализацию. Вы можете выбрать его с помощью графического интерфейса пользователя или командной строки.

0