Семейство алгоритмов LZ78.

Maxime, 15.10.95

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

Самым известным алгоритмом этого класса (частенько ошибочно называемый методом Лемпеля-Зива) является алгоритм Тэри Уэлча (Terry Welch), описанный им в 1984 г. для применения в высокопроизводительных контроллерах диска. Однако, наиболее широкое применение он нашел в скоростных модемах и вошел составной частью в протокол связи v.42bis. (Метод обозначается LZW).

Метод LZW в своей работе пользуется словарем, содержащим 4096 элементов. Элементы с номерами 0 - 255 указывают на отдельные символы. эти элементы словаря постоянны, т.е. не изменяются в процессе работы алгоритма. остальные элементы с номерами 256 - 4095 изначально имеют пустые ссылки, а в процессе работы указывают на фразы, составленные по следующему правилу: новая фраза образуется добавлением текущего символа к концу текущей фразы. Схема LZW алгоритма сжатия выглядит следующим образом:

        w = NIL                                                               
        loop                                                                  
                read a character K                                            
                if wK exists in the dictiontary                               
                        w = wK                                                
                else                                                          
                        output the code for w                                 
                        add wK to the dictionary                              
                        w = K                                                 
        endloop                                                               

Когда словарь переполняется, алгоритм Уэлча приписывает нулевые ссылки элементам словаря с номерами 256 - 4095, т.е. как бы начинает свою работу сначала. Уже существуют модификации этого алгоритма, сбрасывающие при переполнении не весь словарь, а только какую-то его часть, например, первую половину.

Алгоритм распаковки несколько сложнее:

        input oldcode                                                         
        output dictionary[oldcode]                                            
        loop                                                                  
                input code                                                    
                w = dictionary[oldcode]                                       
                if dictionary[code] <> NIL                                    
                        output dictionary[code]                               
                        K = first character of dictionary[code]               
                else                                                          
                        K = first character of w                              
                endif                                                         
                add wK to the dictionary                                      
                oldcode = code                                                
        endloop                                                               

Все алгоритмы данного семейства можно легко классифицировать по способу образования новых фраз словаря и по способу преодоления переполнения этого словаря.

Метод LZW с некоторыми специфичными изменениями также входит в состав формата записи компьютерных изображения GIF.


Изменена 19.03.2011 06:45 MSK Яндекс цитирования Рейтинг@Mail.ru  Развод документы