Ағылшыншамен салыстырыңыз: абзацты басыңыз — түпнұсқа терезеде ашылады. Абзац астындағы EN түймесі оны мәтін ішінде көрсетеді.
Мазмұны
Кіріспе
Алға жылжыту (MTF) түрлендіруі – энтропиялық кодтау техникаларының сығымдау тиімділігін арттауға арналған деректерді (көбінесе байттар тізбегін) кодтау әдісі. Тиімді жүзеге асырылған жағдайда, оның пайдасы деректерді сығымдау алгоритміне қосымша қадам ретінде енгізуді қажет етеді. Бұл алгоритм алғаш рет 1980 жылы Борис Рябко "кітап тізімі" деген атпен жариялаған. Кейіннен, 1986 жылы J. K. Bentley және авторлар тобы оны қайта ашты, бұл туралы түсіндірме жазбада айтылған.
The move to front (MTF) transform is an encoding of data (typically a stream of bytes) designed to improve the performance of entropy encoding techniques of compression. When efficiently implemented, it is fast enough that its benefits usually justify including it as an extra step in data compression algorithm. This algorithm was first published by Boris Ryabko under the name of "book stack" in 1980. Subsequently, it was rediscovered by J. K. Bentley et al. in 1986, as attested in the explanatory note.
Іске асыру
Орындау егжей-тегжейлері өнімділік үшін маңызды, әсіресе декодтау үшін. Кодтау үшін байланысты тізімді пайдаланудан ешқандай айқын артықшылық алынбайды, сондықтан тізімді сақтау үшін массивті пайдалану қабылданады, ең нашар жағдайда өнімділік O(nk) болады, мұнда n – кодталатын деректердің ұзындығы, ал k – мәндер саны (әдетте берілген іске асыру үшін тұрақты шама). Көбінесе өнімділік жақсырақ болады, себебі жиі қолданылатын символдар көбінесе алдыңғы жақта орналасып, осылайша тезірек табылса керек. Осы принцип "Алдыға жылжыту" өзін-өзі ұйымдастыратын тізіміне де негізделген. Алайда, декодтау үшін өнімділікті едәуір арттыру үшін арнайы дерек құрылымдарын қолдануға болады.
Details of implementation are important for performance, particularly for decoding. For encoding, no clear advantage is gained by using a linked list, so using an array to store the list is acceptable, with worst case performance O(nk), where n is the length of the data to be encoded and k is the number of values (generally a constant for a given implementation). The typical performance is better because frequently used symbols are more likely to be at the front and will produce earlier hits. This is also the idea behind a Move to front self organizing list. However, for decoding, we can use specialized data structures to greatly improve performance.
Мәліметтерді сығу алгоритмдерінің практикалық қолданылуы
МТФ трансформациясы хабарламаның энтропиясын азайту үшін жиіліктердің жергілікті корреляциясын пайдаланады. Дейін, жақында қолданылған әріптер тізімнің басында қалады; егер әріптерді қолдануда жергілікті байланыс байқалса, нәтижеде шығыста "0" және "1" сияқты көптеген кіші сандар пайда болады. Дегенмен, барлық деректерде осы типтегі жергілікті корреляция кездеспейді, ал кейбір хабарламалар үшін МТФ трансформациясы энтропияны керісінше арттыруы мүмкін. МТФ трансформациясының маңызды қолданылуы – Burrows-Wheeler трансформациясына негізделген сығылу. Burrows-Wheeler трансформациясы мәтін мен басқа да арнайы деректер кластарынан жергілікті жиілік байланысын көрсететін тізбектерді жасауда өте тиімді. Сығылу үдерісінде Burrows-Wheeler трансформациясынан кейін МТФ трансформациясын қолдану, соңғы энтропиялық кодтау кезеңінен бұрын, айтарлықтай пайда береді.
The MTF transform takes advantage of local correlation of frequencies to reduce the entropy of a message. Indeed, recently used letters stay towards the front of the list; if use of letters exhibits local correlations, this will result in a large number of small numbers such as "0"'s and "1"'s in the output. However, not all data exhibits this type of local correlation, and for some messages, the MTF transform may actually increase the entropy. An important use of the MTF transform is in Burrows–Wheeler transform based compression. The Burrows–Wheeler transform is very good at producing a sequence that exhibits local frequency correlation from text and certain other special classes of data. Compression benefits greatly from following up the Burrows–Wheeler transform with an MTF transform before the final entropy encoding step.
Мысал
Мысалы, Гамлеттің "Болу немесе болмау" ("To be, or not to be") монологын қысқымыз келсін. Бұл хабарламаның көлемін 7033 бит деп есептейміз. Керексіздікпен, MTF түрлендіруін тікелей қолдануға тырысамыз. Нәтижесінде 7807 биттен (түпнұсқадан артық) тұратын хабарлама пайда болады. Бұның себебі – ағылшын тіліндегі мәтін әдетте жоғары деңгейдегі жергілікті жиілік байланысын көрсетпейді. Дегенмен, егер алдымен Burrows-Wheeler түрлендіруін, содан кейін MTF түрлендіруін қолдансақ, 6187 биттен тұратын хабарлама аламыз. Burrows-Wheeler түрлендіруі хабарламаның энтропиясын төмендетпейді; ол байттарды MTF түрлендіруін тиімдірек ету үшін ғана қайта реттейді. Негізгі MTF түрлендіруінің бір мәселесі – ол жиілігіне қарамастан, кез келген символ үшін бірдей өзгерістер жасайды, бұл сирек кездесетін символдар жиі кездесетін символдарды жоғары мәндерге ысырып, қысқарудың нашарлауына әкелуі мүмкін. Осы себепті әртүрлі өзгертулер мен баламалар жасалды. Бір әдіс – белгілі бір шектен жоғары символдарды тек белгілі бір деңгейге дейін жылжыту. Тағы бір әдіс – әр символдың жергілікті жиілігін есептейтін және осы мәндерді символдардың кез келген нүктедегі ретін таңдау үшін пайдаланатын алгоритм жасау. Осы түрлендірулердің көпшілігі қайталанатын символдар үшін нөлді сақтап қалады, себебі олар көбінесе Burrows-Wheeler түрлендіруінен кейінгі деректерде жиі кездеседі.
As an example, imagine we wish to compress Hamlet's soliloquy (To be, or not to be ). We can calculate the size of this message to be 7033 bits. Naively, we might try to apply the MTF transform directly. The result is a message with 7807 bits (higher than the original). The reason is that English text does not in general exhibit a high level of local frequency correlation. However, if we first apply the Burrows–Wheeler transform, and then the MTF transform, we get a message with 6187 bits. Note that the Burrows–Wheeler transform does not decrease the entropy of the message; it only reorders the bytes in a way that makes the MTF transform more effective. One problem with the basic MTF transform is that it makes the same changes for any character, regardless of frequency, which can result in diminished compression as characters that occur rarely may push frequent characters to higher values. Various alterations and alternatives have been developed for this reason. One common change is to make it so that characters above a certain point can only be moved to a certain threshold. Another is to make some algorithm that runs a count of each character's local frequency and uses these values to choose the characters' order at any point. Many of these transforms still reserve zero for repeat characters, since these are often the most common in data after the Burrows Wheeler Transform.
Ары қарай жылжыту-байланысты тізім
"Move To Front" (MTF) термині басқаша мағынада да қолданылады, динамикалық байланысты тізімнің бір түрі ретінде. MTF тізімінде әрбір элемент оған жүгінген кезде тізімнің басына жылжытылады. Осылайша, уақыт өте келе жиі қолданылатын элементтерге оңайырақ қол жеткізуге болады.
The term Move To Front (MTF) is also used in a slightly different context, as a type of a dynamic linked list. In an MTF list, each element is moved to the front when it is accessed. This ensures that, over time, the more frequently accessed elements are easier to access.