Кодирование длины пробега подстрок произвольной длины

Что такое эффективная (с точки зрения временной сложности) алгоритм run length encoding для произвольной, но конечной длины входного потока. Алгоритм подстрок длины 1 может быть реализован в C, как:Кодирование длины пробега подстрок произвольной длины

void encoding(char *bytes) 
{ 
    int c = 0; 
    char *s = bytes, ch; 

    while(*s) { 
     c=1; 
     ch=*s; 

     while(*s && *s== *(s+1)) { 
      c++; 
      s++; 
     } 
     printf("%d%c", c, ch); 
     s++; 
    } 
}

Однако я ищу лучший алгоритм, который может кодировать подстроки любой длины. Например, для ввода "abbabb" приведенный выше код напечатает: "1a2b1a2b". Но лучший алгоритм может кодировать его как "2abb".

Язык реализации (C/Python - мой выбор) не является проблемой, так как алгоритм - это все, что я ищу.

источник

2015-05-16 P.P.

Без ограничений алгоритм «лучше» всегда будет искать по крайней мере ровно половину строки плюс один, а в худшем случае - всю длину строки. (... В этот момент он просто * может * в итоге получить 50% -ную степень сжатия, что совсем неплохо.) – usr2564301

Ah! Это предлагает алгоритм грубой силы «самый жадный»: учитывая входную длину * n *, сравните * n/2 * с тем, что следует, затем сравните * n/3 * и т. Д., Пока не достигнете длины сравнения 1 – usr2564301

Я не уверен, что это так просто (сравнения n/2, n/3 и т. Д.). Потому что вспомогательная строка может начинаться и заканчиваться где угодно. Например, 'abcdabcdaaaa' может быть закодирован как' 2abcd4a', и проблема в том, как я могу выбрать 'abcd' в качестве подстроки, не просматривая вход несколько раз. –

Любой алгоритм, который может найти повторяющуюся подстроку определенной длины, может быть использован для реализации сжатия Lempel-Ziv с помощью скользящего окна этой длины.

Так что я бы посмотрел в кодеры Лемпеля-Зива и использовал это. Или еще лучше: отбросить кодировку длины выполнения и реализовать Lempel-Ziv - она может обеспечить лучшее сжатие.

источник

2015-05-16 12:24:18 orlp

Никогда не слышал о [Lempel-Ziv] (http://en.wikipedia.org/wiki/Lempel%E2%80%93Ziv%E2%80%93Welch) раньше. Я посмотрю. Благодарю. –

@Jongware Мой главный ответ заключается в том, что вы можете посмотреть часть поиска подпоследовательности Lempel-Ziv, чтобы решить проблему в его вопросе. Предложение о прямом использовании LZ - это лишь запоздалая мысль. – orlp

К сожалению: P Вы имеете в виду что-то, как в http://www.wikipedia.org/wiki/LZ77#LZ77? Здесь есть хороший пример. – usr2564301

Кодирование длины пробега подстрок произвольной длины

ответ

Смежные вопросы