Мардан сапарбаев
жүктеу/скачать 290,41 Kb.
|
АКТ каз УМКД
- Бұл бет үшін навигация:
- KWE тобының алгоритмдері
| RLE алгоритмі
Қайталанатын деректердің реттілігін анықтаса және деректер коды көрсетілсе, онда қарапайым құрылымы мен қайталану факторы бар, оларды ауыстыру идеясына RLE алгоритмі негізделген. Мысалы, қысуға жататын деректер тізбегі берілген: 1 1 1 1 2 2 3 4 4 4 Біріншісі- деректер коды, ал екінші - қайталау фактор 1 4 2 2 3 1 4 3, нөмірлердің әрбір жұптың алғашқы саны: RLE алгоритмі оның орнына мынадай құрылымды ұсынады. Сіз 1 байт болса шығыс тізбегі (сығылған нұсқасы) кіріс ретпен әр деректер элементін сақтау үшін жадыдан 8 байт алады, ал бүкіл тізбегі, жадының 10 байтқа дейін қысу дәрежесін сипаттайды. KWE тобының алгоритмдері Тіркелген ұзындықтағы байт топтарының лексикалық бірлік кодтау қағидасы кілт сөздер бойынша қысу алгоритмімен негізделген. Лексикалық элемент мысалы ортақ сөз болуы мүмкін. Іс жүзінде, таңдалған лексикалық бірлік қайталанатын символ тізбегінің аз ұзындықтағы таңбалар жолында (коды) кодталған. Бұл алгоритімнің көптеген түрлері бар, олардың ішіндегі ең тараған Lempel-Zіva (LZ алгоритмі) болып табылады, және оның модификациясы Lempel-Zіva-Уэлч (LZW алгоритмі). Сөз тіркестерінің ықтималдығы шексіз тізім - алгоритімінің сөздігі. Алгоритм жұмысты бос сөздіктің бір ғана кодталған NULL-желісі деп аталатын жолынан бастайды. Келесі деректер тізбегінің символының кірісін оқу кезінде, ол ағымдағы желісіне қосылады. Процесс ретінде ұзақ ағымдағы желісі сөздікте кез келген жазбаға сәйкес келу ретінде жалғастырады. Бірақ ерте ме, кеш пе, ағымдағы желісі кез келген сөздігінің фразасына сәйкес келмесе орындауы тоқтатылады. Ағымдағы қатар соңғы қатар қазыр ғана оқып шыққан соңғы сөздікпен сәйкес келсе кодер қатардың сәйкес келуін бұзған сәйкестік индексіннен тұратын кодты береді. Содан кейін индекс және келесіге сәйкес келетін жаңа фраза сөздікке қосылады. Фраза хабарламада пайда болса, онда ол неғұрлым ұзақ сөз тіркестерін құру үшін пайдалануға болатынын қөрсетеді. LZW алгоритімі тұрақты ұзындығының кодтарында таңба жолдарынан қысылған хабарламаларды ауыстырады, ол кесте фразалар (лексика) айналасында салынды. Кесте келесі қасиетке ие, яғни сөздіктің әр сөзіне , кез келген W фразасынан және К символы кірді. Сөздіктің барлық бөліктері толығымен толтырылған болса, онда ол (кодтау сөздікте қолданыстағы сөз тіркестерінің негізінде орын алады) адаптивті кодтау болуы тоқталады. Осы топтағы алгоритмдерді сығу үлкен көлемдегі мәтінді деректер үшін ең тиімді болып табылады, бірақ шағын файл өлшемдері үшін тиімсіз болып табылады(сөздігін сақтап қалу қажеттігіне байланысты). жүктеу/скачать 290,41 Kb. Достарыңызбен бөлісу:
|