Musala Soft Logo Конкурс по програмиране на Musala Soft и PC Magazine Bulgaria PC Magazine Bulgaria Logo
  Състезателна система
Сезон 2010 - 2011
Сезон 2009 - 2010
Сезон 2008 - 2009
Сезон 2007 - 2008
Сезон 2006 - 2007
Сезон 2005 - 2006
Сезон 2004 - 2005
Сезон 2003 - 2004
Сезон 2002 - 2003
Правила
Задача 1
Задача 2
Задача 3
Задача 4
Задача 5
Задача 6
Класиране
Финален кръг
Сезон 2001 - 2002
Сезон 2000 - 2001

Задача 1 - КОМПРЕСИЯ - Анализ


Едно съвсем “наивно” решение на поставената задача е входният файл да се опише в компресирания с последователност от числа. Входният файл се разгледа като редица от нули и единици (все едно редовете се “долепят”) и всяка последователност от еднакви символи се описва с двойка (вид символ, брой срещания). Така 00001110001100001... ще се опише с двойките (0,4), (1,3), (0,3), (1,2), (0,4) и т.н. Забелязваме, че последователните двойки кодират различен символ (0 или 1) т.е. достатъчно е да запомним символа само в първата двойка, а за всяка следваща двойка той ще е алтернативният. Така, за горния пример ще получим 0,4,3,3,2,4... Този подход не взема под внимание две много важни особености на задачата. Първата е, че числото е изписано с един шрифт и еднаквите му цифри ще имат еднакви изображения. Понеже числото може да е до 1000 цифри, а различните цифри са само 10, то помненето на растерното изображение на всяка цифра само веднъж ще намали компресирания файл близо 100 пъти. Втората особеност е, че растерните изображения съдържат не какво да е, а цифри и всяка цифра има свое специфично изобразяване. Използването на тези специфични особености може да помогне за по-доброто компресиране на числата. И ако върху кодиран по този начин файл се направи някоя стандартна компресия, то би се получило добро решение.

Най-добре представилите се участници Николай Николов (победителят в този кръг) и Петър Митров постъпват по друг начин. Ето накратко техните обяснения (пълните текстове на идеите им за решение можете да намерите чрез линковете по-долу)

Николай Николов: “Нека имаме някакъв текст, които искаме да компресираме (т.е. да кодираме с минимален брой битове). Нека допуснем, че знаем каква е вероятността за срещане на всеки символ в текста. Тогава възниква въпросът: какъв е минималният брой битове, с които трябва да кодираме всеки символ, така че резултатът да е най-кратък (и все пак да можем от него да възстановим оригинала). Отговорът е: за да кодираме символ, който се среща с вероятност p (p е между нула и едно) ще са ни необходими точно -log2(p) бита.

Кодирането на Хъфман е може би най-известният алгоритъм за вероятностно кодиране. Има го обяснен навсякъде и няма да се впускам в подробности, но той дава кодиране с цяло число битове за символ, т.е. най-доброто приближение на -log2(p) до цяло число. Когато възможните символи са много, хъфмановото кодиране се справя не лошо и се предпочита, заради това че се реализира лесно и работи бързо Когато символите са 2 (нула и единица) алгоритъмът на Хъфман кодира и двата символа с по 1 бит, каквито и да са вероятностите им, и следователно e безполезен за нашите цели. Ето защо моята програма използва аритметично кодиране.”

Аритметичното кодиране също е класически алгоритъм за компресия. Подробности за тази техника може да се намерят в различни книги (вж. например Mark Nelson, Jean-Loup Gailly, The Data Compression Book, Hungry Minds, Inc; 2nd Edition, November 1995). Аритметичното кодиране дава важно преимущество при решаване на конкурсната задача. За разлика от хъфмановото, то реализира докрай възможностите на вероятностния подход, като осъществява невъзможното на пръв поглед кодиране на всеки символ с не цяло число битове

В добавка към аритметичното кодиране Николай прилага още няколко техники. Първо, той заменя оригиналното изображение с т.н. “контурно”, като само маркира с 1 местата на смените на 0 с 1 и обратно. По този начин силно променя съотношението на двете вероятности (единицата се среща много по-рядко в контурното изображение) и постига максимален ефект от вероятностния подход. Втората идея е позната от стандарта за компресиране на факсове, известен като CCITT (версия T.6 или по-ранни версии). Идеята се състои в използване на факта, че позициите на смяна на 0 с 1 и обратно в два последователни реда на растера са много близки или даже съвпадат. Николай, както и други участници, кодира само по един път всяка от цифрите, които се срещат в числото, а за да може да го възстанови, го включва в компресирания текст, като го компресира, прилагайки аритметично кодиране и в този случай. За финал, той се опитва да използва и симетричността на изображенията на цифрите 0, 1, 3 и 8 в някои шрифтове.

Петър Митров също е реализирал идеята за запомняне на числото и кодиране еднократно на всяка срещана в него цифра. Кодирането на цифрите става със споменатата вече техника CCITT, версия Т.6 (вж. http://www.rasip.fer.hr/research/compress/algorithms/adv/fakscomp/index.html), а за кодиране на числото използва популярното речниково кодиране LZSS (вж. http://www.rasip.fer.hr/research/compress/algorithms/fund/lz/lzss.html).


Анализи на решения изпратени от участници:


За въпроси можете да ни пишете на адрес: konkurs@musala.com.

Supported by Musala Soft Ltd.

Copyright 2000-2010 by Musala Soft Ltd. All rights reserved.