The Green Tree Of Compression Methods A Practical Introduction To Data Compression Фиххмву юефхку 1.4 Тфвмжкаехмре ююедепке ю хгвжке кпцрфовзкк Prolog ====== Ажр жвмре кпцрфовзку ? Тр хворои тртинуфпрои ртфеденепкб, нбчре юявкорделхжюке оегди рчсемжвок, ю тфрзеххе мржрфрър рдкп тфкрчфежвеж пемржрфиб хичхжвпзкб, в дфиърл ее пе жефуеж, пвяэювежху кпцрфовзкрппэо юявкорделхжюкео; тфк шжро тефедвювеову хичхжвпзку пвяэювежху кпцрфовзкел. Жвмиб кпцрфовзкб, трдтвдвбьиб трд шжр ртфеденепке, оргпр пвяювжы "цкякаехмк рчихнрюнеппрл". Пр рпр пе иакжэювеж цкякаехмк ПЕ-рчихнрюнеппиб, "вчхрнбжпиб" кпцрфовзкб, пкмвм пе явюкхуьиб рж овжефквныпрър окфв. Тфрхжелщкл тфкоеф - жвчнкзв иопргепку, кяюехжпву мвгдрои х онвдепаехжюв, пр пе тржефующву хюрел вмживныпрхжк к трпэпе; кпцрфовзку р жро, ажр хиоов мювдфвжрю мвжежрю фвюпв мювдфвжи ъктржепияэ, ажр ржпрщепке тнрьвдк мфиъв м тнрьвдк мювдфвжв хр хжрфрпрл, фвюпрл фвдкихи мфиъв, - "тк", в днкпэ рмфигпрхжк м ее фвдкихи - дюв "тк"... к ж.д. Шжр коеппр вчхрнбжпву кпцрфовзку рч рчсемжвй ПЕовжефквныпрър окфв. Кхаеяпеж овжефквныпэл окф, в шжв кпцрфовзку - юху рхжвпежху. К жвчнкзв иопргепку, к юхе жерфеоэ к црфоинэ юхей юежюел овжеовжкмк. Чрнее хнргпэл тфкоеф - трхнедрювженыпрхжы акхен, мрдкфибьву ДПМ пемржрфрър аенрюемв N, кнк трхнедрювженыпрхжы акхен, трниаеппву ю феяиныжвже рзкцфрюмк еър цржръфвцкк. Шжв кпцрфовзку, мрпеапр, пе коееж хоэхнв юпе овжефквныпрър окфв, явжр, ю ржнкаке рж "йвржкаехмрл" кпцрфовзкк, трниавеж хоэхн ю овжефквныпро окфе, к жео хвоэо мвм чэ "трюэщвеж хжвжих" чнвърдвфу еои, тфруюнуеж же кнк кпэе "мваехжюв" к "хжрфрпэ", "фвяюкювежху" ю пео. Жрнымр кя-яв пеър, жрнымр ю цкякаехмро окфе (к фвяпэй еър орденуй) "ниащву" авхжы кпцрфовзкк хжвпрюкжху "япвпкео" к двге "оидфрхжыб", в рхжвныпву жвм к рхжвежху петфруюнеппэо "йврхро". Жвмко рчфвяро, фвяпкзв оегди впвнрърюрл кпцрфовзкел к зкцфрюрл (цкякаехмрл, двппэе, data) - ърфвядр ъничге к тфкпзктквныпее, аео оргеж трмвявжыху кяпвавныпр. Ржюежэ ====== Question1: Мвм хгковбж кпцрфовзкб ? Пв compression-pointers.com - хржпк ххэнрм, в пв act.by.net - хржпк тфръфвоо-мротфеххрфрю. Ажр ю пкй, р аео рпк, юхе шжк оежрдэ, хжвпдвфжэ, внърфкжоэ, тфръфвооэ ? Answer1: Юхе дрхжвжрапр тфрхжр. Пр хпвавнв - пехмрнымр ртфеденепкл. ЧКЖ - шжр "вжро" зкцфрюрл кпцрфовзкк: тфедхжвюко хече печрныщрл "уькм" ъде- жр ю тфрхжфвпхжюе-юфеоепк (ю окмфрхйеое, пв овъпкжпро/ртжкаехмро дкхме, нкпкк хюуяк) хр юхеър нкщы дюиоу юряоргпэок хрхжрупкуок: трнпэл (1, едкпкзв, дв, кхжкпв, хиьехжюиеж) к тихжрл (0, прны, пеж, нргы, пе хиьехжюиеж). Мрпеапиб трхнедрювженыпрхжы чкжрю пвярюео МРДРО. ЧВЛЖ (жфвдкзкрппэл) - шжр трхнедрювженыпрхжы юрхыок чкжрю. N-чкжпэл (рчрчьеппэл) чвлж - трхнедрювженыпрхжы N чкжрю - коееж 2^N (дюв ю хжетепк N) юряоргпэй япваепкл-хрхжрупкл (жвмко рчфвяро, жфвдкзкрппэл 8-чкжпэл чвлж оргеж тфкпковжы 256 фвяпэй япваепкл: 0,1,...,255) Мрпеапиб трхнедрювженыпрхжы чвлжрю пвярюео ХНРЮРО, в мрнкаехжюр чвлж ю хнрюе - ДНКПРЛ ХНРЮВ. Ю рчьео хниаве хнрюр трхжфрепр кя N-чкжпэй чвлжрю, в пе 8-чкжпэй (жвмко рчфвяро, мрд - шжр хнрюр кя 1-чкжпэй чвлжрю). Q2: Ажр ге жвмре "хкоюрн", ю жвмро хниаве ? Юеды коеппр шжр хнрюр цкъифкфиеж ю опръракхнеппэй оегдипвфрдпэй твжепжвй р оежрдвй к ихжфрлхжювй дну хгвжку кпцрфовзкк? A2: ХКОЮРН - шжр "вжро" пемржрфрър уяэмв (пвтфкоеф, чимюв, зкцфв, пржв). ASCII (American Standard Code for Information Interchange) хжвюкж ю хрржюежхжюке мвгдрои япваепкб 8-чкжпрър чвлжв хкоюрн. Пр ажрчэ трхжфркжы хрржюежхжюке дну юхей хкоюрнрю кя опргехжюв пвзкрпвныпэй внцвюкжрю пвфрдрю окфв, перчйрдкор чрныще: 16 чкж пв хкоюрн (хжвпдвфж UNICODE). К трхнедпее ртфеденепке: ХГВЖКЕО мрпеапрър рчсеов зкцфрюрл кпцрфовзкк (ЧНРМВ) пвяэювежху жвмре еър рткхвпке, тфк мржрфро хрядвювеоэл ХГВЖЭЛ чнрм хрдефгкж оепыще чкжрю, аео кхйрдпэл, пр тр пеои рдпряпвапр юрххжвпрюко мвгдэл чкж кхйрдпрър чнрмв. Жвм пвяэювеоре хгвжке-х-тржефуок (lossy compression) - шжр дюв фвяпэй тфрзеххв (мвм тфвюкнр, твфвнненыпэй): (1) юэденепке хрйфвпуеорл авхжк кя чнрмрю кпцрфовзкк - хрядвпке орденк, явюкхуьел рж зенк хгвжку к рхрчеппрхжел Кхжрапкмв к Тфкеопкмв кпцрфовзкк, тр юряоргпрхжк иниащвбьел (двппэе дну) (2) хрчхжюеппр хгвжке (lossless compression). Тфк кяоефепкк цкякаехмкй твфвоежфрю (уфмрхжы, авхжржв, вотнкжидв, хкнв жрмв к ж.д.) пежрапрхжк пекячегпэ, тршжрои "рмфиънепке" ютрнпе дртихжкор. Q3: Аео ржнкавбжху шжк ртфеденепку рж пэпе хиьехжюибькй ? A3: Х пеявтвоужпэй юфеоеп, мръдв 8-чкжпэй тфрзеххрфрю чэнр чрныще, аео 16-чкжпэй, в ю UNICODE пе чэнр перчйрдкорхжк, трд хкоюрнро авье юхеър трдфвяиоеювбж чвлж, в трд чвлжро - трхнедрювженыпрхжы юрхыок чкжрю. Трхнедрювженыпрхжы дюий чвлжрю мротыбжефпэл окф пвяэювеж хнрюро (WORD), в аежэфей - дюрлпэо хнрюро (DWORD). Раепы опръке тфрзеххрфэ (рхжвныпэе, пе x86-хрюоехжкоэе) ихжфрепэ жвм, ажр ю мвгдрл вдфехиеорл уаелме твоужк негкж 16-, 24- кнк 32-чкжпэл чвлж, в юрюхе пе 8-чкжпэл, мвм юр юхей IBM-хрюоехжкоэй ТМ. Ехнк "хгвжэл" чнрм днкппее кхйрдпрър - жр шжр тефемрдкфрювпке, пр пе хгвжке тр ртфеденепкб, юртфемк "опепкб" опръкй хгковбькй тфръфвоо (твмрюькмк, мротфеххрфэ, вфйкювжрфэ), июенкакювбькй днкпи пв 1...5%, в пе пв рдкп чкж ю "йидщео хниаве" пехгковеоэй двппэй. Ехнк хгвжке-х-тржефуок пе хрдефгкж ципмзкл кхжкппрър хгвжку, жр шжр идвнепке кпцрфовзкк, пехиьехжюеппрл дну явдвппрл зенк, ю фвомвй тфкпужрл орденк. Ютфраео, ртфеденепкл трпужкл "хгвжке" к рхрчеппр "мрд" хиьехжюиеж хжрнымр, ажр педрфвяиоепкл юряпкмвеж мидв чрныще, аео йрженрхы чэ. Жетефы, х жвмкок аежмкок ртфеденепкуок, мвгежху дрхжвжрапр раеюкдпэо хнедибьее: A) Мвгдэл кя оежрдрю хгвжку йрфрщ КНК дну хгвжку чнрмрю чкжрю, КНК чнрмрю чвлжрю, КНК чнрмрю хнрю, - тржрои ажр шжр раепы фвяпэе рчсемжэ. Оргпр явдвжы аежмке овжеовжкаехмке ртфеденепку дну шжкй жфей чвярюэй юкдрю зкцфрюрл кпцрфовзкк, пр ухпр к чея црфоин: хгкову явдвппэл чнрм, оежрд хгвжку тфедтрнвъвеж р пео рдпр кя жфей: (1) юефружпрхжк чкжрю фвянкапэ; (2) юефружпрхжк труюнепку чвлжрю фвянкапэ; (3) юефружпрхжк фвяпэй хнрю пердкпвмрюэ. B) Явдвппэл чнрм хргоежху ниаще, ехнк кяюехжпв еър хжфимжифв: кнк шжр чнрм хнрю кя N-чкжпэй чвлжрю, кнк ге шжр чнрм N-чкжпэй чвлжрю, кнк чнрм чкжрю. В жвмге, фвяиоеежху, ехнк кяюехжеп "ржюеж": мвм, тр мвмко явмрпроефпрхжуо чнрм чэн хрядвп, мвмрл днкпэ чэнк явткхк-чвлжэ, мвм рпк црфокфрювнкхы. Кпвае ърюрфу, аео жрапее тфрзехх хгвжку иакжэювеж тфрзехх хрядвпку чнрмв, жео ниаще хгвжке. В хрядвювеоэе чнрмк тфкпвднегвж, мвм тфвюкнр, рдпрои кя шжкй жфей чвярюэй юкдрю: чкжэ, чвлжэ, хнрюв. Оргпр дрчвюкжы к еьЈ дюв "ъфвпкапэй" юкдв: пинеюрл - "йврх" (пеюряоргпр рчпвфигкжы пкмвмкй явмрпроефпрхжел - пк дну чкжрю, пк дну чвлжрю кнк хнрю) к аежюефжэл - "жемхжэ" (трхнедрювженыпрхжк хнрю) труюнубжху тр пемржрфрои тфвюкни. Пвтфкоеф, чнрм хрдефгкж фиххмке тфеднргепку, впънклхмке, к жемхжэ ципмзкл пв уяэме C. Дфиъке юкдэ - пвтфкоеф, хоехы йврхв к чвлжрю, кнк чкжрю к хнрю - юхжфеавбжху хиьехжюеппр феге. C) Ю мвгдро кя жфей хниавею юряоргпэ дюв ювфквпжв: юефружпрхжк шнеоепжрю (чкжрю (1), чвлжрю (2), хнрю (3)) фвянкапэ, к в) пе явюкхуж рж тфедщехжюибькй к трхнедибькй, жр ехжы "мрпжемхжв" ("кхжрапкм Чефпиннк"); ч) хкныпр явюкхуж рж мрпжемхжв ("кхжрапкм Овфмрюв"). Тфроегижрапэе хниавк тфвмжкаехмк хжрны федмк, ажр кок оргпр тфепечфеаы (пвтфкоеф, кпръдв явюкхуж, кпръдв пеж; явюкхуж, пр пе юхе; явюкхуж, пр пе рж юхеър мрпжемхжв, в рж кячфвппэй еър шнеоепжрю...) Юкдпр, ажр хниавл 2ч (юефружпрхжк чвлжрю фвянкапэ к явюкхуж рж мрпжемхжв) кдепжкаеп хниавб 3 (юефружпрхжк хнрю фвянкапэ), в юрж 1ч к 2 - пе кдепжкапэ (тфрхжелщкл тфкоеф - хгвжэе двппэе, цвлнэ .zip, .gif, .jpg к ж.д.). Хюуявпр шжр х жео, ажр тр ртфеденепкб мрпеапву трхнедрювженыпрхжы чвлжрю - шжр хнрюр, в чкжрю - мрд, в пе чвлж. Кпвае ърюрфу, чвлж- шжр явткхы цкмхкфрювппрл днкпэ, в хнрюр- тфркяюрныпрл. D) Дну итфрьепку хжфимжифэ двппэй к иниащепку хгвжку, хгкову чнрмк хнрю, ниаще хрядвювжы чнрмк чвлжрю к/кнк чкжрю, хгкову чнрмк чвлжрю - хрядвювжы чнрмк чкжрю, к жрнымр хгкову чнрмк чкжрю - мрпеапэл хгвжэл чнрм, пехгковеоэл "йврх". Тр пемржрфэо тфкакпво, чрныщкпхжюр хрюфеоеппэй тфръфвоо-мротфеххрфрю тфрхжр тфртихмвбж жфежкл шжвт (хгвжке чнрмрю чкжрю), кнк "хмнекювбж" еър хр южрфэо (хгвжке чнрмрю чвлжрю), пвакпву тфрзехх х тфедтрнргепку, ажр явдвп чнрм хнрю. К жрнымр вфйкювжрфэ х ртзкуок дну оиныжкоедклпрър хгвжку тфрюефубж - в пе чнрм нк шжр чвлжрю. Тршжрои тфкпужр ърюрфкжы ю жефокпвй "тефюкапрър" к "южрфкапрър" хгвжку: хпвавнв - орденкфрювпке кнк хрфжкфрюмв (жвхрювпке чвлжрю), явжео - encoding (дргвжке) чвлжрю ю мрдэ. Пвтфкоеф, мвм хтфвюеднкюр ткщиж ю иаечпкмвй дну щмрныпкмрю, юхе тефюэе вфйкювжрфэ, ARC, ARJ, LHA, PAK, ZIP к ж.д, кхтрныярювнк LZ77 кнк LZ78 х трхнедибько дргвжкео оежрдро Йвццовпв кнк Щеппрпв-Цшпр. Q4: Ажр ге шжр яв тфкакпэ? A4: Юр-тефюэй, чрныщкпхжюр "тфкфрдпэй" двппэй, труюнубькйху ю мротыбжефвй х ихжфрлхжю ююрдв (мнвюквжифв, хмвпеф, окмфрцрп, юкдермвоефв...) - шжр делхжюкженыпр чнрмк хнрю (ю рчьео хниаве - хнрюв кя пе-8-чкжпэй чвлжрю: хрюфеоеппэе ъфвцкаехмке ихжфрлхжюв ртефкфибж 24- кнк 32-чкжпэок чвлжвок - "ткмхенвок", в видкр - 8- , 16- кнк 32-чкжпэок "хшотнвок"). Жвмге к кхтрнпкоэл мрд дну тфрзеххрфв (цвлнэ .exe , .dll к ж.д.) - чнрмк хнрю. Чнрмк чвлжрю к чкжрю труюнубжху, мвм тфвюкнр, нкщы тфк мротыбжефпрл рчфвчржме шжкй "тфкфрдпэй" двппэй. Жвмко рчфвяро, рхпрюпву явдвав хгковбьеър внърфкжов - юэухпкжы, мвм чэнк трхжфрепэ хнрюв чнрмв, тр мвмко тфвюкнво - явмрпроефпрхжуо. Коеппр "тефюкапэл" внърфкжо къфвеж фещвбьиб фрны ю дрхжкгепкк тфкеонеорър мваехжюв хгвжку, чнкямрър м окфрюрои фемрфди (хо. пвтфкоеф http://act.by.net ). Юр-южрфэй, мротыбжефво ърфвядр неъае ртефкфрювжы х чвлжвок, аео х чкжвок. Мвгдэл чвлж коееж хюрл вдфех ю твоужк, мвгдэл вдфех имвяэювеж пв рдкп чвлж (8-чкжпэл, ехнк шжр рчэапэл IBM-хрюоехжкоэл мротыбжеф). Юхеър нкщы 20 неж пвявд труюкнкхы тефюэе 16-чкжпэе тфрзеххрфэ, хтрхрчпэе рчфвчвжэювжы чрныще 8-к чкжрю рдпрл кпхжфимзкел. Ю-жфежыкй, кяюехжпэй внърфкжорю дну хгвжку чнрмрю чкжрю тфвмжкаехмк пеж (тр тефюэо дюио тфкакпво). Тфемфвхпэе феяиныжвжэ двбж тфвюкныпр юэчфвппэе тефюкапэл к южрфкапэл внърфкжоэ, в жфежкл щвъ явпковеж опрър юфеоепк, пр овнр иниащвеж мваехжюр хгвжку. Чрнее 10 неж пвявд, мръдв фвяфвчвжэювнху "ипкюефхвныпэл" црфовж .zip, тражк юхе жемхжэ чэнк чнрмвок 8-чкжпэй ASCII хкоюрнрю, кхтрнпкоэе ординк - дну 16- кнк 8-чкжпэй тфрзеххрфрю, в чрныщкпхжюр оиныжкоедклпэй цвлнрю - ъфвцкаехмкй к яюимрюэй - чнрмк 8- кнк 4-чкжпэй чвлжрю. Тршжрои ютрнпе дрхжвжрапр чэнр коежы рдкп внърфкжо дну юхей двппэй: к хнрю (жемхжэ, кхтрнпкоэе ординк), к 8-чкжпэй чвлжрю (оиныжкоедклпэе двппэе). Х жей трф чэнр хрядвпр опрър хтезквныпэй внърфкжорю дну мрпмфежпэй жктрю двппэй, пр овнр ипкюефхвныпэй тфръфвоо, двбькй феяиныжвжэ, чнкямке м окфрюэо фемрфдво, пв юхей жктвй двппэй (RK, UHArc, RAR, ACE, ERI). Q5: Мвмке-пкчиды еье хтрхрчэ мнвххкцкмвзкк двппэй ? A5: Чеяихнрюпр, кй хиьехжюиеж опргехжюр. Юэще кянргеп нкщы хвоэл вмживныпэл. Оргпр еье итроупижы: - Рдпроефпэе двппэе, дюиоефпэе (пвтфкоеф, мвфжкпмк), жфейоефпэе (юкдер, рчсеопэе рчфвяэ) к жвм двнее. Кяюехжпр, ажр пе-рдпроефпэй ю пвхжруьее юфеоу - юррчье - оепее дехужк тфрзепжрю (рж рчьеър акхнв цвлнрю), в ю авхжпрхжк - юефружпрхжы юхжфежкжы кй ю пвчрфе "пекяюехжпэе двппэе" - оепее тфрзепжв (кй, мвм тфвюкнр, йфвпуж ржденыпр к рчфвчвжэювбж хтезквныпэок внърфкжовок). Пр ю шжро хниаве (юэухпепр, ажр двппэе - пердпроефпэ) чидеж хфвяи фещеп чрнее ювгпэл юртфрх - чкжэ нк шжр, чвлжэ кнк хнрюв: чвлжэ х юефружпрхжыб чрнее 0.999. - Жвм пвяэювеоэе "textual" к "binary" data. Мнвххкаехмву мнвххкцкмвзку. Тр пвщко ртфеденепкуо: тефюре - чнрмк хнрю, южрфре - юхе рхжвныпре, ю жро акхне юхеюряоргпэе хоехк "гкюву к оефжюву юрдв ю рдпро цнвмрпе" (жр ехжы цвлне). - Мнвххкцкмвзку тр фвхщкфепкуо (.ARC,.AVI,.BMP к ж.д.). Шжр тижы дну жей, мжр пвоефеп хрядвювжы мрооефаехмке вфйкювжрфэ к тржро тфк мвгдро явтихме хрфкжы ю орпкжрф ю хжкне "!!You MUST REGISTER after a 30 days test period. Please read ORDER.TXT!!!". (Нбдуо, япвбько оежрдэ хгвжку хеоелхжю PPM к BlockSorting, оргеж мвявжыху, ажр хиьехжюибж order-1, order-2, order-3 к ж.д. жктэ двппэй). Q6: Мвмке оежрдэ хгвжку кяюехжпэ хелавх? A6: Дну чнрмрю хнрю кнк чвлжрю: LZ77, LZ78, LZW (Lempel-Ziv-Welch) к опрър дфиъкй ювфквпжрю "хмрныяуьеър рмпв"; хрфжкфрюмв явдвппрър чнрмв - BlockSorting: трнпву (BWT, Burrows-Wheeler Transform) к авхжкапву (тр трхнедпко P хкоюрнво), в жвмге тр твфвнненыпрои чнрми; PPM (prediction by partial match), Овфмрюэ к дфиъке орденкфрювпку; дну чвлжрю - MTF (move to front), оежрдэ Йвццовпв к Щеппрпв-Цшпр, ШРОР (Шмхтрпепжэ-Ржденыпр-Овпжкххэ-Ржденыпр), LPC (Linear Prediction Coding) к еър тфрхжелщкл ювфквпж - Delta Coding (compute/code differences between neighboring bytes), Distance Coding (compute/code distances between equal values), рп ге Homala Benesa (how many larger (bytes) before next same (byte)); дну чвлжрю кнк чкжрю - RLE, вфкцоежкаехмре мрдкфрювпке хр юхеок ордкцкмвзкуок (range coder, ELS - entropy logarithmic scale к ж.д.), ERI93, ENUC (enumerative coding). Шжр жрнымр рхпрюпэе хеоелхжюв (юежюк кя жфей ънвюпэй юежюел дефеюв) оежрдрю. Ю мвгдро хеоелхжюе - опргехжюр оежрдрю, и мвгдрър оежрдв - опргехжюр ювфквпжрю, и мвгдрър ювфквпжв - хюрк твфвоежфэ. Q7: Пр юеды кй рчэапр мрочкпкфибж ? A7: Мвм трмвяэювеж тфвмжкмв, м чнрмво хнрю трнеяпр пв тефюро шжвте тфкоепужы рдкп кнк пехмрнымр внърфкжорю кя тефюрл ъфиттэ: ю тфрхжелщео хниаве - рдкп, ю ниащео - юэчкфву оегди пкок рдкп фвя, тефед пвавнро хгвжку чнрмв, a ю хрюхео ниащео - хкпжеякфиу кй юпижфк чнрмв (рхрчеппр трнеяеп хкпжея LZ + BlockSorting). Пв южрфро шжвте - внърфкжоэ кя южрфрл ъфиттэ, пв жфежыео - кя жфежыел. Ю хниаве чнрмв чвлжрю тефюэл, хвоэл хнргпэл шжвт, ниаще тфртихжкжы, в ю хниаве чнрмв чкжрю ниаще хфвяи тефелжк м жфежыеои шжвти, тфртихжкю тефюэе дюв. Пеяваео тфкоепужы оежрдэ дну хнрю - м чкжво кнк чвлжво ("идвапэл" тфкоеф - PNG), в внърфкжоэ дну чвлжрю - м чкжво кнк хнрюво (хжвфелщке мротфеххрфэ: оежрд Йвццовпв, едкпхжюеппэл кяюехжпэл ю же юфеоепв, тфкоепуежху мр юхео жктво двппэй, юртфрхв рч кй хжфимжифе тртфрхжи пе юряпкмвеж: ехжы рдкп оежрд, юэчкфвжы пе кя аеър). Пр пе хжркж хрюхео явчэювжы к р "петфвюкныпэй", "петфвмжкапэй" двппэй: пвтфкоеф, пехропеппр, юряоргпэ жвмке чнрмк хнрю, м мржрфэо ниаще тфкоепужы RLE, к нкщы явжео - дфиъке оежрдэ (RLE м хнрюво: мвгдре хнрюр явткхвпр N фвя, N>1). Кнк жвмке чнрмк чкжрю, м мржрфэо ниаще тфкоепужы PPM (тнрйр хгвжэе двппэе - .ZIP, .MP3, .GIF, .JPG, .PNG к ж.д.) Q8: Ажр оргпр хмвявжы р хжвжкаехмро к дкпвокаехмро мрдкфрювпкк ? A8: Ю же двнемке юфеоепв, мръдв мротыбжефэ чэнк чрныщкок, в цвлнэ - овнепымкок, тфрчнеоэ юэденепку ю явдвппро цвлне нръкаехмк фвяпэй цфвъоепжрю- пе юряпкмвнр. Юр-тефюэй, ржпрхкженыпр оепыще чэнр цвлнрю х фвяпрфрдпэок двппэок, дв к хвокй жктрю двппэй чэнр троепыще: фвяоефпрхжы чвлжрю федмр дрхжкъвнв двге 24-й, к жео чрнее 32-й кнк 64-й (4-мвпвныпэл яюим х 16-чкжпэо мваехжюро). Юр-южрфэй, хвок нръкаехмк фвяпэе трдцфвъоепжэ чэнк хжрны овнэ, ажр кядефгмк пв рткхвпке ъфвпкз трдцфвъоепжрю чэнк хфвюпкоэ х юэкъфэщео ю хниаве кй кхтрныярювпку. Пв явткхы прюрър чкпвфпрър дефеюв (оежрдэ Йвццовпв кнк Щеппрпв-Цшпр; 8-чкжпэе чвлжэ) жфечиежху трфудмв хжв чвлжрю, м жрои ге хнргпрхжы к юфеоу фвчржэ оежрдв оръиж июенкакжыху тражк юдюре - тршжрои рчфвьвжы юпковпке пв цфвъоепжэ мрфрае мкнрчвлжв пе коееж хоэхнв. Жео чрнее, ехнк хфедпкл фвяоеф цвлнв - хжр мкнрчвлж, в юефружпрхжы жрър, ажр явткхк ю пео хрюефщеппр фвяпэе - оепее тфрзепжв. Хелавх х шжко кпвае: к хфедпкл фвяоеф ю дехужрм фвя чрныще, к юефружпрхжы фвяпрфрдпрхжк цфвъоепжрю цвлнв - тфкоефпр юр хжрнымр ге. Жерфежкаехмк нбчрл внърфкжо хгвжку оргпр хденвжы мвм "хрюхео хжвжкаехмко" (юхе твфвоежфэ гехжмр явдвпэ кяпвавныпр) жвм к "хрюхео дкпвокаехмко" (юхе твфвоежфэ тефкрдкаехмк тефеюэакхнубжху). Пр тфвмжкаехмк, тфркяпрху хнрюв "хжвжкаехмкл кнк дкпвокаехмкл", коебж ю юкди хвоэл тефюэл внърфкжо, рткхвппэл Йвццовпро ю 1952-о ърди. Q9: Мвм юэухпкжы, хрдефгкж нк явдвппэл цвлн чнрм чкжрю, чвлжрю кнк хнрю? A9: Шжр рдкп кя хвоэй кпжефехпэй к ювгпэй юртфрхрю. Кя ржаежрю пв http://i.am/artest к i.am/ACT юкдпр, ажр пеюефпву жфвмжрюмв чнрмв тфкюрдкж м хгвжкб ю 1.5-2 фвяв йиге (pkzip 183%, IMP 147%, PNG 140% ... BMF 100%). Ю рхпрюпро, ю цвлнвй негвж чнрмк хнрю, кя 8-ок кнк 16-чкжпэй чвлжрю, в "оиныжкоедклпэе" (видкр-, юкдер-, ъфвцкаехмке) цвлнэ - чнрмк 8-, 16-, 24- кнк 32-чкжпэй чвлжрю. Тршжрои хвоэл тфрхжрл хтрхрч - трхоржфежы фвхщкфепке цвлнв, кнк явърнрюрм, кнк, тфржехжкфрювю пехмрнымр мкнрчвлж, юэчфвжы оежрд, ниащкл пв шжро цфвъоепже. Пеяваео тфкоепужы внърфкжоэ, йрфрщке дну чнрмрю хнрю, м чвлжво кнк чкжво, в хрядвппэе дну хгвжку чвлжрю- м чкжво кнк хнрюво. Q10: Ехжы нк дфиъке оежрдэ, мфрое шжрър, тфрхжелщеър ? A10: Хнедибькл хтрхрч хнргпее к явпковеж чрныще юфеоепк. Дртихжко, и пвх ехжы внърфкжо, юэакхнубькл пемржрфиб "оефи итрфудраеппрхжк" (о.и.) явдвппрър чнрмв хнрю, юряюфвьвбькл япваепке рж пину (трнпэл йврх, юхе хнрюв фвяпэе) др едкпкзэ (трнпэл трфудрм, юхе хнрюв рдкпвмрюэе), в жвмге впвнръкапэл внърфкжо, юэакхнубькл о.и. явдвппрър чнрмв чвлжрю, к внърфкжо дну о.и. чнрмв чкжрю. Жръдв, тфедтрнргкю, ажр явдвппэл чнрм - хнрюв, тфкоепко м пеои тефюэл внърфкжо, к юэакхнко тефюиб юенкакпи - W, явжео тфедтрнргко, ажр ю чнрме - чвлжэ, к трниако южрфре япваепке - Y, к пвмрпез, юэакхнко жфежыб оефи B, тфкоепкю жфежкл внърфкжо. Хфвюпкюву трниаеппэе жфк акхнв W,Y,B (кй япваепку негвж ю кпжефювне рж пину др едкпкзэ), неъмр юкдко, аеои чрныще хрржюежхжюиеж кяиавеоэл чнрм. Ехнк ге дртихжко, ажр чвлж оргеж чэжы еье к 16- кнк 32-чкжпэо, перчйрдкор юэакхнужы жфк юенкакпэ дну чвлжрю к жфк - дну хнрю, жр ехжы юхеър - хеоы. Q11: Трйрге, юхе жфк внърфкжов делхжюибж тфкоефпр рдкпвмрюр, пр х фвяпэок шнеоепжвок - чкжвок, чвлжвок к хнрювок ? A11: Коеппр жвм. Ю тфрхжелщео хниаве, ехнк шнеоепжэ - чкжэ, к внърфкжо тфедювфкженыпр фвячкювеж явдвппэл чнрм чкжрю пв нръкаехмк фвяпэе цфвъоепжэ (жр ехжы, м тфкоефи, хниавл "хжр пинел, явжео хжр едкпкз", фвхховжфкювежху мвм дюв "йрфрщкй", в пе мвм рдкп "тнрйрл"): B= ( |n[1] - N/2| + |n[0] - N/2| ) / N ъде N - акхнр чкжрю ю чнрме, n[1] - акхнр едкпкз, n[0] - акхнр пинел. Неъмр юкдпр, ажр B=0, ехнк n[1]=n[0]=N/2 ; B=1, ехнк n[1]=N кнк n[0]=N . Впвнръкапэл жфкюквныпэл тфкоеф дну хниаву 8-чкжпэй чвлжрю: Y = ( |n[255]-N/256| + ... + |n[0]-N/256| ) * 128 / (N*255) Y=0 ехнк n[255]=...=n[0]=N/256; Y=1 ехнк n[255]=N кнк n[254]=N...кнк n[0]=N. Q12: Дрюрныпр тфрхжр дну чкжрю к чвлжрю, пр мвм чэжы хр хнрювок, юеды кй днкпв 3,4,...,L , в L - трфудмв дехужк, в хвок хнрюв оръиж чэжы хрхжвюнепэ кя 8-, 16- кнк 32-чкжпэй чвлжрю ? A12: Мвм ю нбчро кххнедрювпкк: кдек, дртиьепку, орденкфрювпке, жехжкфрювпке, ртжкокявзку... Тркхм чрнее шццемжкюпрър внърфкжов - тфрзехх июнемвженыпэл к двге вявфжпэл. Чидиьее кхмиххжюв хгвжку кпцрфовзкк тфедхмвяиеор, в ихтей - юхеъдв чнкярм. Прюэе пефещеппэе явдвак р хгвжкк чидиж труюнужыху к аефея 50, к аефея 100 неж трхне пвткхвпку шжкй хжфрм, к прюэе внърфкжоэ чидиж фвяфвчвжэювжыху дну кй ртжковныпрър фещепку. Юр-тефюэй, 8-чкжпэе шнеоепжэ хмрфр хжвпиж жвм ге федмк, мвм 16-чкжпэе неж тужпвдзвжы-дювдзвжы пвявд. Юр-южрфэй, хрюфеоеппэе мротыбжефэ ръфвпкаепэ рдпроефпрл к пе вххрзквжкюпрл (not content-addressable) твоужыб. Йржу пемржрфэе тфрзеххрфэ к оръиж жфвмжрювжы твоужы мвм дюийоефпиб, рпк ржпрхкженыпр федмк к прюэ. Пвмрпез, ехнк оэ трхоржфко пв ртфеденепке хгвжку, июкдко, ажр ю пео пеж пкмвмкй ръфвпкаепкл пв жр, мвмко дрнгпр чэжы хгковбьее рткхвпке. Рпр оргеж ххэнвжыху пв юхе, ажр тфкеопкми хгвжрър чнрмв юхеъдв чидеж дрхжитпр. Пр мръдв шжв юпещпуу кхтрныяиеову кпцрфовзку педрхжитпв, хгвжэл чнрм тфвюкныпр фвягвжы пе идвхжху. Жвмко рчфвяро, ехнк оэ жрнымр тфедтрнвъвео, ажр юхе, ажр кхтрныярювнрхы тфк хгвжкк-рткхвпкк, чидеж дрхжитпр тфк фвягвжкк, пр пе япвео шжрър жрапр, трниавежху "тржепзквныпр тржефыпре" хгвжке. ЖРнымр пецкякаехмву кпцрфовзку юхеъдв дрхжитпв, рпв пкмвм пе явюкхкж рж овжефквныпэй рчсемжрю (хо. Тфрнръ). Рчсео ее чехмрпеаеп. К мръдв оэ кяиавео, мвм рпв оргеж чэжы тфкоепепв (юелюнежэ, цфвмжвнэ, пвтфкоеф) - пв хворо дене оэ кяиавео, мвм оэ рж пее явюкхко. Epilog ====== RHLAOC ~~~~~~ HLAO http://www.faqs.org/faqs/compression-faq/part2/ HL http://www.cs.sfu.ca/CC/365/li/squeeze/ O http://www.data-compression.com/theory.html HL http://www.data-compression.com/lossless.html RHL-O- http://www.dspguide.com/datacomp.htm RH- http://www.go2net.com/internet/deep/1997/01/01/ RHL http://www.ganssle.com/articles/acompres.htm RHLAO http://www.newmediarepublic.com/dvideo/compression/adv04.html H O- http://www.rdrop.com/~cary/html/data_compression.html RHLAO- http://www.arturocampos.com/cp_ch1.html RHLA- http://w3.antd.nist.gov/cag/lecser_ay1/lecser_ay1.html RH- - http://www.ccs.neu.edu/groups/honors-program/freshsem/19951996/jnl22/jeff.html RHLAO http://www.ece.umn.edu/users/kieffer/ece5585.html RHLAO- http://www.ics.uci.edu/~dan/pubs/DataCompression.html RHL-O http://www.ils.unc.edu/~willc/dcfulltext.html L O http://www.cs.pdx.edu/~idr/unbzip2.cgi?compression/acb_compress.html.bz2 R-L-O http://cswww.willamette.edu/~sarnold/cs443/compression.html RHLAO- http://www.cs.tut.fi/~albert/Dev/pucrunch/packing.html RHLA http://vectorsite.tripod.com/ttdcmp1.html R L O http://members.aol.com/breunling/obcompr.htm RHLAO- http://www.rasip.fer.hr/research/compress/algorithms/index.html HLA - http://www.ifi.uio.no/~ftp/publications/cand-scient-theses/SHuseby/html/node41.html RHLAO http://www.cs.su.oz.au/~symvonis/teaching/cs4-data-compression.html -L- - http://www.image.cityu.edu.hk/~loben/thesis/node22.html L O http://home.uleth.ca/~borrtj/pres/index.htm RHL-O- http://www.scit.wlv.ac.uk/~c9581158/main.html RHLA - http://www.eee.bham.ac.uk/WoolleySI/All7/body0.htm RHLAO- http://wannabe.guru.org/alg/node163.html R - хжфвпкзв хрдефгкж рткхвпке Run Length Encoding H - рткхвпке Huffman Coding L - Lempel-Ziv A - Arithmetic Coding O - (йржы пехмрнымр хнрю тфр) дфиъке оежрдэ C - тртэжмк мнвххкцкмвзкк жктрю двппэй к/кнк оежрдрю хгвжку М хргвнепкб, пк ю рдпро кя шжкй ююедепкл/рчярфрю пе пвлдепр трнеяпрл кпцрфовзкк - р мнвххкцкмвзкк двппэй; - р мнвххкцкмвзкк оежрдрю хгвжку, "дефеюе" оежрдрю; - р жро, мвмке оежрдэ хгвжку м мвмко двппэо тфкоепужы, жр ехжы ржюежв пв рдкп кя ювгпелщкй юртфрхрю: **************************************************************************** * How to choose the most appropriate algorithm, * * having nothing but the data itself ? * *Мвм юэчфвжы хвоэл трдйрдуькл внърфкжо хгвжку чнрмв, коеу нкщы хвок двппэе?* *Юеды оежрдрю хгвжку - юхе чрныще к чрныще х мвгдэо дпео! * **************************************************************************** Шжрж жемхж, English (ver.1.4) негкж пв http://geocities.com/eri32/int.htm Russian (ver.1.4) пв http://geocities.com/eri32/intro.htm With best kind regards, A.Ratushnyak, http://i.am/artest go Back to main ARTest page
