Мне сложно понять алгоритм LZW. Я изучаю псевдокод, поставляемый на википедии (http://en.wikipedia.org/w/index.php?title=Lempel-Ziv-Welch&oldid=245292660) и есть одна части в коде декомпрессора, что я не понимаю:Алгоритм LZW-декомпрессора
else if (k == currSizeDict)
entry = w + w[0];
Может кто-нибудь объяснить мне ситуацию, когда это произойдет?
Эта проблема объясняется очень хорошо здесь: https://www.cs.duke.edu/csed/curious/compression/lzw.html. Основная идея заключается в том, что поскольку LZW требует только сжатую строку и словарь, содержащий все элементы алфавита (а не словарь, содержащий все закодированные шаблоны), необходимо восстановить все кодировки более сложных шаблонов «на лету» при декодировании. Это приводит к ситуации, когда можно запускать кодировки, которые не входят в словарь. Интересно, что, как указывает вышеприведенная ссылка, это может произойти только тогда, когда закодированная строка начинается и заканчивается одним и тем же символом.