Кіріспе
Деректерді сығуда қолданылатын энтропиялық кодтаманың түрі. Арифметикалық кодтау (АК) – жоғалтусыз деректерді сығуда қолданылатын энтропиялық кодтаманың бір түрі. Көбінесе, символдар тізбегі ASCII кодысындағыдай, әрбір символы үшін белгілі бір саны біттермен көрсетіледі. Тізбек арифметикалық кодтауға айналғанда, жиі қолданылатын символдар аз біттермен, ал сирек кездесетін символдар көп біттермен сақталады, нәтижесінде жалпы біттер саны азаяды. Арифметикалық кодтау, мысалы, Хаффман кодтау сияқты энтропиялық кодтаманың басқа түрлерінен өзгешелігі, кіріс деректі компоненттік символдарға бөліп, әрқайсысын кодпен алмастырудың орнына, бүкіл хабарламаны бір санға – кез келген дәлдіктегі бөлшек санға (0,0 ≤ q < 1,0) кодтайды. Ол ағымдағы ақпаратты екі санмен белгіленген диапазон ретінде көрсетеді. Ағымдағы ақпаратты білдіретін бір табиғи санмен тікелей жұмыс істеуге мүмкіндік беретін, асимметриялық сандық жүйелер деп аталатын энтропиялық кодтаушылардың жаңа тобы, осы арқылы жылдам жұмыс істеуге жағдай жасайды.
Arithmetic coding (AC) is a form of entropy encoding used in lossless data compression. Normally, a string of characters is represented using a fixed number of bits per character, as in the ASCII code. When a string is converted to arithmetic encoding, frequently used characters will be stored with fewer bits and not so frequently occurring characters will be stored with more bits, resulting in fewer bits used in total. Arithmetic coding differs from other forms of entropy encoding, such as Huffman coding, in that rather than separating the input into component symbols and replacing each with a code, arithmetic coding encodes the entire message into a single number, an arbitrary precision fraction q, where 0.0 ≤ q < 1.0. It represents the current information as a range, defined by two numbers. A recent family of entropy coders called asymmetric numeral systems allows for faster implementations thanks to directly operating on a single natural number representing the current information.
Тең ықтималдықтар
Ең қарапайым жағдайда, әрбір символдың пайда болу ықтималдығы тең болады. Мысалы, үш символдан тұратын жиынтықты қарастырайық: А, В және С, олардың әрқайсысының пайда болуы бірдей ықтимал. Символдарды бірінен соң бірін кодтау үшін әрбір символға 2 бит қажет, бұл тиімсіз: бит комбинацияларының бірі ешқашан қолданылмайды. Яғни, А, В және С символдары сәйкесінше 00, 01 және 10 ретінде кодталуы мүмкін, ал 11 қолданылмайды. Көбірек тиімді шешім – осы үш символдың тізбегін 3-тік санау жүйесіндегі рационал сан ретінде көрсету, мұнда әрбір цифр символды білдіреді. Мысалы, "ABBCAB" тізбегі 0.0112013 болып келуі мүмкін, арифметикалық кодтауда [0, 1) аралығындағы мән ретінде. Келесі қадам – бұл үштік санды жеткілікті дәлдігі бар қабатты екілік санға түрлендіру арқылы кодтау, оны қалпына келтіруге болады, мысалы, 0.00101100012 – бұл тек 10 бит; қарапайым блоктық кодтаумен салыстырғанда 2 бит үнемделеді. Бұл ұзақ тізбектер үшін мүмкін, себебі кез келген дәлдіктегі сандардың санау жүйесін өзгертуге арналған тиімді, орынды алгоритмдер бар. Мәнді декодтау үшін бастапқы тізбектің ұзындығы 6 екенін білген адам жай ғана 3-тік санау жүйесіне қайтара алады, 6 цифрге дейін дөңгелектеп, тізбекті қалпына келтіре алады.
Адаптациялық арифметикалық кодтау
Арифметикалық кодтаудың басқа ұқсас деректерді сығу әдістерінен артықшылығы – бейімделудің қолайлылығы. Бейімделу – деректерді өңдеу барысында жиілік (немесе ықтималдық) кестелерін өзгерту. Егер декодтау кезінде жиілік кестесі кодтау кезіндегідей бірдей тәсілмен және бірдей қадаммен жаңартылса, декодталған дерек бастапқы деректермен сәйкес келеді. Синхрондау көбінесе кодтау және декодтау процесінде кездесетін символдардың комбинациясына негізделген.
Асимптотикалық тең бөлу
Біз мұны интуитивті түрде түсінеміз. Егер бастапқы дерек ергодикалық болса, онда оның асимптотикалық тең бөліну қасиеті (АЭП) болады. АЭП бойынша, ұзақ символдар ағынынан кейін, интервал дерлік бірдей өлшемдегі интервалдарға бөлінеді. Техникалық тұрғыдан алғанда, кез келген кішкентай ε үшін, жеткілікті үлкен N-ге, әрбір тізбектің дерлік бірдей ықтималдығы p болады, және олардың жалпы ықтималдығы 1-ге тең. Кез келген мұндай тізбек үшін, ол ұзындығы N болатын екілік тізбекпен арифметикалық түрде кодталады, мұндағы N – интервалдағы түріндегі бөлшек болатын ең кіші бүтін сан. интервалының өлшемі болғандықтан, болғанда оның аралығында түріндегі бір бөлшек болуын күтуге болады. Осылайша, жоғары ықтималдықпен, ұзындығы N болатын екілік тізбекпен арифметикалық түрде кодталады.
For any such string, it is arithmetically encoded by a binary string of length , where is the smallest such that there exists a fraction of form in the interval for Since the interval for has size , we should expect it to contain one fraction of form when
Thus, with high probability, can be arithmetically encoded with a binary string of length .
Хаффман коды
Арифметикалық кодтау бір мезгілде бір деректі сығымдамайтындықтан, IID тізбектерін сығымдағанда энтропияға кез келген дәлдікпен жақындаса алады. Керісінше, Хаффман кодтаудың кеңейтілген нұсқасын (тізбектерге) қолданғанда, алфавит символдарының барлық ықтималдықтары екінің дәрежесі болмаса, энтропияға жете алмайды. Мұндай жағдайда, Хаффман және арифметикалық кодтаулар энтропияға жетеді. Бинарлық тізбектерді қарапайым түрде Хаффман кодтау кезінде, энтропия төмен болса да, қысылу мүмкін емес (мысалы, {0, 1} тізбегі үшін ықтималдықтар {0.95, 0.05} болса). Хаффман кодтау әр мәнге 1 бит тағайындайды, нәтижесінде кіріспен бірдей ұзындықта код пайда болады. Ал арифметикалық кодтау биттерді жақсы қысып, ең жақсы қысу қатынасына жақымдасады.
Хаффман кодтаудың тиімсіздігін шешудің бір қарапайым жолы – символдарды біріктіру ("блоктау") арқылы жаңа әліпби құру. Бұл жаңа әліпбиде әрбір жаңа символ бастапқы әліпбиден алынған символдар тізбегін көрсетеді – бұл жағдайда биттер. Жоғарыдағы мысалда, үш символдан тұратын тізбектерді топтастыру нәтижесінде мынадай жиіліктері бар жаңа "суперсимволдар" пайда болады:
: 85.7%
, , : әрқайсысы 4.5%
, , : әрқайсысы 0.24%
: 0.0125%
: 85.7%
, , : 4.5% each
, , : 0.24% each
: 0.0125%
Осы топтастыру арқылы Хаффман кодтау үш символға 1.3 биттен орташа есептейді, яғни әрбір символға 0.433 бит, ал бастапқы кодтауда бір символға 1 бит жұмсалатын еді, яғни қысылу жүзеге асты. Кез келген үлкен тізбектерге рұқсат ету энтропияға кез келген дәлдікпен жақындасады – арифметикалық кодтау сияқты, бірақ мұны істеу үшін үлкен кодтар қажет, сондықтан бұл мақсат үшін арифметикалық кодтаудан кем практикалық. Балама ретінде, Хаффман негізіндегі Голомб-Райс кодтары арқылы тізбектерді кодтауға болады. Бұл тәсіл арифметикалық кодтаудан немесе тіпті Хаффман кодтаудан қарапайым және жылдам кодтау/декодтауға мүмкіндік береді, өйткені соңғысына кестелік іздеу қажет. {0.95, 0.05} мысалында, төрт биттік қалдықпен Голомб-Райс коды үш биттік блоктарды пайдаланудан гөрі жақсы қысу қатынасына жетеді. Алайда, Голомб-Райс кодтары тек Бернуллилік кірістерге ғана қолданылады, мысалы, осы мысалдағыдай, сондықтан ол барлық жағдайларда блоктаудың орнына қолданылмайды.
Салыстырмалы көрсеткіштер және басқа да техникалық сипаттамалар
Арифметикалық кодтаудың әрбір бағдарламалық іске асырылуы әртүрлі сығылу қатынасымен және өнімділікпен сипатталады. Сығылу қатынастары көбінесе шамалы өзгереді (әдетте 1% төмен), бірақ кодты орындау уақыты 10 есеге дейін айырмашылықты құрауы мүмкін. Қолжетімді кодтаушылардың тізімінен дұрыс кодтаушыны таңдау қиын, себебі өнімділік және сығылу қатынасы дерек түріне, әсіресе әліпби мөлшеріне (әр түрлі символдар санына) байланысты. Кейбір кодтаушылар кішкентай әліпбилер үшін жақсы өнімділік көрсетеді, ал басқалары үлкен әліпбилер үшін тиімдірек болады. Көптеген кодтаушылар әліпби мөлшеріне шектеу қояды, сондай-ақ олардың көпшілігі нақты екі символдан (0 және 1) тұратын әліпбилер үшін арнайы жасалған.