Ағылшыншамен салыстырыңыз: абзацты басыңыз — түпнұсқа терезеде ашылады. Абзац астындағы EN түймесі оны мәтін ішінде көрсетеді.
Мазмұны
Кіріспе
Жоғалмайтын деректерді сығыстыру алгоритмі. Грамматикалық кодтар немесе грамматикалық сығыстыру – қысылатын жол үшін контекстсіз грамматика (CFG) құру идеясына негізделген сығыстыру алгоритмдері. Мысалға, универсалды жоғалмайтын деректерді сығыстыру алгоритмдерін келтіруге болады. Деректер жолын сығыстыру үшін грамматикалық код оны контекстсіз грамматикаға түрлендіреді. Кіріс жолы үшін ең кіші грамматиканы табу мәселесі (ең кіші грамматика мәселесі) NP-толық екені белгілі, сондықтан теориялық және практикалық тұрғыдан көптеген грамматикалық түрлендіру алгоритмдері ұсынылған. Әдетте, алынған грамматика арифметикалық кодтау сияқты статистикалық кодтаушылармен қосымша сығыстырылады.
Lossless data compression algorithm
Grammar based codes or Grammar based compression are compression algorithms based on the idea of constructing a context free grammar (CFG) for the string to be compressed. Examples include universal lossless data compression algorithms. To compress a data sequence , a grammar based code transforms into a context free grammar The problem of finding a smallest grammar for an input sequence (smallest grammar problem) is known to be NP hard, so many grammar transform algorithms are proposed from theoretical and practical viewpoints. Generally, the produced grammar is further compressed by statistical encoders like arithmetic coding.
Мысалдар мен сипаттамалары
Грамматикалық кодтар класы өте кең. Оған блок кодтары, көп деңгейлі үлгіні тану (MPM) алгоритмі, Lempel Ziv кодының инкременттік талдауының түрлері және көптеген басқа жаңа әмбебап жоғалтусыз сығылу алгоритмдері кіреді. Грамматикалық кодтар әмбебап болып табылады, себебі олар шекті әліпбиі бар кез келген тұрақты, эргодикалық дереккөздің энтропиялық жылдамдығына асимптотикалық түрде жете алады.
The class of grammar based codes is very broad. It includes block codes, the multilevel pattern matching (MPM) algorithm, variations of the incremental parsing Lempel Ziv code, and many other new universal lossless compression algorithms. Grammar based codes are universal in the sense that they can achieve asymptotically the entropy rate of any stationary, ergodic source with a finite alphabet.
Қолданбалы алгоритмдер
Төмендегі компрессия бағдарламаларын сыртқы сілтемелер арқылы алуға болады. Sequitur – кіріс мәтінін тікелей CFG-ге аударатын классикалық грамматикалық қысу алгоритмі, содан кейін жасалған CFG арифметикалық кодтаушымен кодталады. Re-Pair – ең көп кездесетін элементтерді бірінші кезекте алмастыру стратегиясын қолданатын ашкөз алгоритм. Оның қысу өнімділігі жоғары, бірақ негізгі жадқа қажетті орын өте көп. GLZA – қайталанатын грамматика құрастырады, яғни ішінде қайталаулар болады, мұнда қайталауларды "ашудың" энтропиялық кодтау құны, оларды анықтап, кодтау үшін ереже жасау құнынан төмен. (Жалпы алғанда, қысу бойынша оптималды SLG азайтылмайды, ал ең кіші грамматика мәселесі нақты SLG қысу мәселесінен өзгеше.)
The compression programs of the following are available from external links. Sequitur is a classical grammar compression algorithm that sequentially translates an input text into a CFG, and then the produced CFG is encoded by an arithmetic coder. Re Pair is a greedy algorithm using the strategy of most frequent first substitution. The compressive performance is powerful, although the main memory space requirement is very large. GLZA, which constructs a grammar that may be reducible, i. e., contain repeats, where the entropy coding cost of "spelling out" the repeats is less than the cost creating and entropy coding a rule to capture them. (In general, the compression optimal SLG is not irreducible, and the Smallest Grammar Problem is different from the actual SLG compression problem.)