Каков наилучший способ сжать список похожих, но не идентичных строк? - PullRequest
Новая
       45

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

4 голосов
/ 11 марта 2012

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

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

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

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

ОБНОВЛЕНИЕ ( формат данных ):

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

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

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

и т. Д.

Весь словарный запас этого языка не превышает размер английского алфавита.

Строка описывает всю картину: «U12C6P1L74D74R74U74P0 ....».

Представьте теперь класс из десяти тысяч детей, которым было сказано нарисовать какой-то очень специфический образ с помощью этого языка: например, флаг своей страны. Мы получим 10 тыс. Строк, которые все разные и одинаковые одновременно.

Наша задача - сжать всю цепочку как можно лучше.

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

Ответы [ 3 ]

1 голос
/ 11 марта 2012

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

AGCTGTGCGAGAGAGAGCGGTGGG ...

GGCTGTGCGAGCGAGAGCGGTGGG ...

CGCTGTGAGAGNGAGAGCGGTTGGG ...

* GGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGG К КсGGCTGTGCGAGTGAGAGCGGTGGG ...

... ...

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

  1. Кодирование Хаффмана: исх.Википедия самостоятельно

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

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

0 голосов
/ 14 марта 2012

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

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

0 голосов
/ 11 марта 2012

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

...