Влияние върху производителността
Постъпателни алгоритми – синтез на кодове Huffman
Изтегляне 1.47 Mb.
|
Свързани:
saap conspect
Постъпателни алгоритми – синтез на кодове HuffmanНормално ASCII има 100 печатащи се символа log100 =7 бита + 1 бит контрол по четност.Т.е. за С символа са нужни logC бита за кодиране. Нека във файл имаме само символи a,e,I,s,t , blank, NL. Нека след статистика знаем че във файла има 10 –a; 15 e; 12 I; 3 s; 4 t; 13 blanks; 1 ML. Нужни са 174 бита за съхраняване на поредицата Ще представим стратегия постигаща за нормален файл 25%пестене и 60%за дълги файлове.Варираме с дължината на кода за разл символи. Най-честите с най-къс код.При едн. честота – няма значение кой.Ето дърво, даващо н-н за кодировка на азбука от 7 символа: Данни има само в листата.Кодировката е еднозначна Ако символ c i е в дълбочина d i и се среща f i пъти, то общ.цена на кодираната инф. е ∑d I * f i.Едно подобре-ние става при свиване дълбочината за възли с 1 листо: Общата цена става 173, което изобщо не е подобрение. Винаги работим с пълно дърво. При символи само в листата, всяка последователност от 0 и 1 е еднозначна и мд се декодира.Това е т.нар.префиксно кодиране. Проблемът се сведе до: намиране на full binary tree с мин. цена, в което символи има само по листата. Ето оптималното за примера (цена 146): Алгоритъм на Huffman Имаме С символа.Правим набор дървета.Тегло за дър-во се получава от сума на честотите в листата му. С-1 пъти избираме 2 дървета Т1 и Т2 с мин. тегла и ги обединяваме. В нач. имаме С дървета с по 1 възел. В края на алг. имаме 1 дърво и това е оптимал. кодово дърво. Ето за нашия пример Начало: първо обединение ( няма значение кое е ляво, така че реализиращата процедура няма да прави връщания назад). Теглото на новополученото д-во е сума: Реализацията в прог. е лесна: правим нов възел,устано-вяваме 2 указателя и изчисл. тегло.продължаваме: краят ( след обединението) беше вече показан Накратко за доказателството, че Хофмановия алгоритъм води до оптимален код: полученото д-во е пълно, така че не може да се подобрява с местене възли нагоре. 2 букви “а, б” с мин. честота са най-долу. Доказваме с използване на обратно твърдение: ако това не е така , (поне едното от а и б не е в най-дълбоко листо), то има някакво г (дървото е пълно) което е там. Но щом а е по-рядко срещано от г, то най-лесно ще подобрим общата цена като разменим а и г . Очевидно, 2 символа във възли с еднаква дълбочина могат да се разместват без променяне на оптималния избор. Отчитаме, че може да сливаме символ – дърво с слято вече. Тогава очевидно азбуката ни се е проме-нила (напр. е,Т4,Т3). Но крайните символи изгражда-щи напр Т3 са по-дълбоко,но и по-рядко срещани от е. Алг.е greedy,защото на всеки етап правим сливане без оглед на глобал.оптимиз., а само в локален оптимум. **Разбира се кодиращата инф.следва да се изпрати в началото на файла при трансмисия за да е възможно декодиране.За малки файлове това е лошо(много добавена инф.). ***Алгоритъмът е двупасов – първо се събират данни за честотата, после се кодира. За големи файлове това не е добре – има подходи за обединяване задачите. Изтегляне 1.47 Mb. Сподели с приятели:
|