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

StackOverflow https://stackoverflow.com//questions/9653793

Вопрос

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

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

Все длины равны, каждая составляет 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К струн, которые все разные и все одинаковы одновременно.

Наша задача сжимает целую кучу строк как можно лучше.

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

Это было полезно?

Решение

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

agctgtgcgagagagagcgggtgggg ...

ggctgtgcgagcgagagcggtggg ...

cgctgtgagaggagagcgggtggg ...

ngctgtgcgagagagagcggtggg ...

ggctgtgcgagtgagagcggtggg ...

... ...

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

  1. Huffman Coding: Ref.Википедия самостоятельно

  2. Stontology: Ref. http://books.google.com.hk/books/about/Jwels_of_stringoling.html?id=9ndohjxtiyyc

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

Другие советы

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

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

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

Лицензировано под: CC-BY-SA с атрибуция
Не связан с StackOverflow
scroll top