Реттік кодтау – 1979 ж. құрастырылған, ақпаратты тиімді түрде жиып, тарату әдісі. Арифметикалық кодтауға ұқсас, бірақ жылдам әрі патенттік шектеулерден бос.
Ағылшыншамен салыстырыңыз: абзацты басыңыз — түпнұсқа терезеде ашылады. Абзац астындағы EN түймесі оны мәтін ішінде көрсетеді.
Мазмұны
Кіріспе
Диапазондық кодтау (немесе диапазондық енкодирование) – 1979 жылы G. Nigel N. Martin-нің 1979 жылғы мақаласында сипатталған энтропиялық кодтау әдісі, ол Ричард Кларк Паско 1976 жылы алғаш енгізген FIFO арифметикалық кодын қайта ашты. Символдар тізбегі мен олардың ықтималдықтары берілген жағдайда, диапазондық кодтаушы осы символдарды ұсыну үшін ғарышты тиімді түрде сақтайтын биттер ағынын жасайды, ал ағын мен ықтималдықтарды пайдаланып, диапазондық декодер осы процесті кері қайтарады. Диапазондық кодтау арифметикалық кодтауға өте ұқсас, бірақ кодтау биттермен емес, кез келген негіздегі сандармен жүзеге асырылады, сондықтан үлкен негіздерді (мысалы, байтты) қолданғанда сығылу тиімділігінің азаюымен бірге жылдамдық артады. Алғашқы (1978) арифметикалық кодтау патентының мерзімі біткеннен кейін, диапазондық кодтау патенттік шектеулерден бос болып көрінді. Бұл, әсіресе, ашық кодты қауымдастықта осы техникаға қызығушылықты арттырды. Одан бері әртүрлі танымал арифметикалық кодтау техникаларына да патенттердің мерзімі бітті.
Range coding (or range encoding) is an entropy coding method defined by G. Nigel N. Martin in a 1979 paper, which effectively rediscovered the FIFO arithmetic code first introduced by Richard Clark Pasco in 1976. Given a stream of symbols and their probabilities, a range coder produces a space efficient stream of bits to represent these symbols and, given the stream and the probabilities, a range decoder reverses the process. Range coding is very similar to arithmetic coding, except that coding is done with digits in any base, instead of with bits, and so it is faster when using larger bases (e. g. a byte) at small cost in compression efficiency. After the expiration of the first (1978) arithmetic coding patent, range coding appeared to clearly be free of patent encumbrances. This particularly drove interest in the technique in the open source community. Since that time, patents on various well known arithmetic coding techniques have also expired.
Қашықтық кодтамасының жұмыс істеу тәсілі
Диапазондық кодтау хабардың барлық символдарын бір санға кодтайды, Хаффман кодтауынан өзгеше, ол әрбір символға бит үлгісін тағайындап, барлық бит үлгілерін тізбектей біріктіреді. Осылайша, диапазондық кодтау Хаффман кодтауындағы символ үшін бір биттен кем емес төменгі шекке қарағанда жоғары сығылу коэффициенттерін қол жеткізе алады және Хаффманның екінің дәрежесі емес ықтималдықтармен жұмыс істегенде туындайтын тиімсіздіктерге ұшырамайды. Диапазондық кодтаудың негізгі идеясы мынада: жеткілікті үлкен бүтін сандар диапазоны және символдардың ықтималдығын бағалау болғанда, бастапқы диапазонды олардың мөлшері олар көрсететін символдың ықтималдығына пропорционалды кіші диапазонға бөлуге болады. Содан кейін хабардың әрбір символы келесі кодталатын символға сәйкес келетін сол кіші диапазонға ағымдағы диапазонды қысқарту арқылы өз кезегінде кодталады. Декодер кодтаушы қолданған ықтималдық бағалауын дәл білуі керек, ол алдын ала жіберілуі, бұрын жіберілген деректерден шығарылуы немесе компрессор мен декомпрессордың құрамына кіруі мүмкін. Барлық символдар кодталғаннан кейін, жалпы хабарды жеткізу үшін тек кіші диапазонды анықтау жеткілікті (әрине, декодер барлық хабарды алған кезде хабарланады деп есептесек). Кіші диапазонды анықтау үшін бір бүтін сан жеткілікті, тіпті бүтін санды толығымен жіберудің қажеті де болмауы мүмкін; егер цифрлардың тізбегі болса, онда осы префикстің басталатын әрбір саны кіші диапазонға кірсе, онда кіші диапазонды анықтау үшін және осылайша хабарды жіберу үшін тек префикс қана жеткілікті.
Range coding conceptually encodes all the symbols of the message into one number, unlike Huffman coding which assigns each symbol a bit pattern and concatenates all the bit patterns together. Thus range coding can achieve greater compression ratios than the one bit per symbol lower bound on Huffman coding and it does not suffer the inefficiencies that Huffman does when dealing with probabilities that are not an exact power of two. The central concept behind range coding is this: given a large enough range of integers, and a probability estimation for the symbols, the initial range can easily be divided into sub ranges whose sizes are proportional to the probability of the symbol they represent. Each symbol of the message can then be encoded in turn, by reducing the current range down to just that sub range which corresponds to the next symbol to be encoded. The decoder must have the same probability estimation the encoder used, which can either be sent in advance, derived from already transferred data or be part of the compressor and decompressor. When all symbols have been encoded, merely identifying the sub range is enough to communicate the entire message (presuming of course that the decoder is somehow notified when it has extracted the entire message). A single integer is actually sufficient to identify the sub range, and it may not even be necessary to transmit the entire integer; if there is a sequence of digits such that every integer beginning with that prefix falls within the sub range, then the prefix alone is all that's needed to identify the sub range and thus transmit the message.
Арифметикалық кодтаумен байланыс
Арифметикалық кодтау аралық кодтаумен бірдей, бірақ бүтін сандар бөлшектердің алымы ретінде қарастырылады. Бұл бөлшектердің ортақ белгісі бар, сондықтан барлық бөлшектер [0,1) аралығына түседі. Сәйкесінше, алынған арифметикалық кодтың басы имплицитті түрде "0" деп түсіндіріледі. Бұл екі кодтау әдісінің әртүрлі интерпретациясы болғандықтан және нәтижедегі арифметикалық және аралық кодтар бірдей болғандықтан, әр арифметикалық кодтаушы – сәйкес аралық кодтаушы, және керісінше. Яғни, арифметикалық кодтау мен аралық кодтау – бір нәрсені түсінудің екі, сәл ғана ерекшеленетін тәсілі. Бірақ практикада, аралық кодтаушылар деп аталатындар көбінесе Мартиннің мақаласында сипатталғандай іске асырылады, ал арифметикалық кодтаушылар көбінесе аралық кодтаушылар деп аталмайды. Мұндай аралық кодтаушылардың жиі аталатын ерекшелігі – бір уақытта бір бит емес, бір уақытта бір байтты нормалауға бейімділік (әдеттегідей). Басқаша айтқанда, аралық кодтаушылар биттердің орнына байттарды кодтау цифрлары ретінде пайдаланады. Бұл қол жеткізілетін сығылу мөлшерін өте аз ғана төмендетсе де, әр бит үшін нормалау орындауға қарағанда жылдам.
Arithmetic coding is the same as range coding, but with the integers taken as being the numerators of fractions. These fractions have an implicit, common denominator, such that all the fractions fall in the range [0,1). Accordingly, the resulting arithmetic code is interpreted as beginning with an implicit "0". As these are just different interpretations of the same coding methods, and as the resulting arithmetic and range codes are identical, each arithmetic coder is its corresponding range encoder, and vice versa. In other words, arithmetic coding and range coding are just two, slightly different ways of understanding the same thing. In practice, though, so called range encoders tend to be implemented pretty much as described in Martin's paper, while arithmetic coders more generally tend not to be called range encoders. An often noted feature of such range encoders is the tendency to perform renormalization a byte at a time, rather than one bit at a time (as is usually the case). In other words, range encoders tend to use bytes as coding digits, rather than bits. While this does reduce the amount of compression that can be achieved by a very small amount, it is faster than when performing renormalization for each bit.