Дәріс №1 Кіріспе. Жиындар теориясының негізгі ұғымдары. Жиындарға амалдар қолдану

Мысал.

Төмендегі алфавиттер берілсін делік:

0. 
   = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9} В = {0, 1}.
   

Онда кодтау кестесі орналастыру түрінде бола алады:

Алфавиттік кодтак схемасы префиксті деп аталады, егер бір әріптің элементар коды басқа әріптің элементар кодының префиксі болып табылмаса.

Алфавиттік кодтау схемасы бөлінгішті деп аталады, егер кез-келген элементар кодтардан құралған сөз элементар кодтарға жалғыз әдіспен жіктелетін болса.

Алфавиттік кодтау схемасы бөлінгішті болуы үшін элементар кодтардың ұзындығы Макмиллан теңсіздігі деп аталатын қатынасты қанағаттандыруы керек.

бөлінгішті болса, онда

теңсіздігі орындалады.

Берілген схема префиксті болып табылмайды, себебіа әрпінің элементар коды b әрпінің элементар кодының префиксі болып табылады.

1. 
   Кодтау дегеніміз не?
   
2. 
   Декодтау қалай жүзеге асырылады?
   
3. 
   Бөлінгіштік дегеніміз не?Префиксті код деген қандай код?
   
4. 
   Макмиллан теңсіздігі.
   

0. 
   Мәліметтерді сығу
   
1. 
   Қайталамалы серияларды кодтау
   
2. 
   Лемпель –Зив алгоритмі
   

1.Мәліметтерді сығу

Кез-келген сығу негізінде мәліметтердің шығу тегінің моделі тұрады. Басқаша айтқанда қандай типті мәлімет сығылуы қажеттігін білу керек. Сығылатын материал туралы мәліметіңіз болмай тұрып, оның көлемін азайту үшін ешқандай әрекет ете алмайсыз.

Барлық сығу алгоритмдері екі негізгі класқа бөлінеді:

Шығынсыз сығу; Шығынмен сығу.

Шығынсыз сығуды қолданғанда мәліметтерді толығымен қалпына келтіруге болады, ал шығынмен сығуды қолданғанда мәліметтер елеусіз ақаулықтармен қалпына келтіріледі. Мәліметтерді шығынсыз сығу мәтіндік құжаттарды, компьютерлік программаларды, сирек жағдайда аудио-бейне мәліметтердің, цифрлық бейнелердің көлемін азайту мақсатында, яғни мәлімет ақаулықсыз қалпына келтірілу қажет болғанда қолданылады. Шығынмен сығу әдетте аудио-бейне файлдардың, цифрлық бейнелердің көлемін азайту үшін, яғни бастапқы мәлімет пен қалпына келтірілген мәліметтің толық сәйкестігі талап етілмеген жағдайда қолданылады.

0. 
   Қайталамалы серияларды кодтау
   

Мәліметтерді сығудың ең танымал қарапайым шешімі және ақпаратты қайтымды жолмен сығу – бұл қайталамалы серияларды кодтау (Run Length Encoding - RLE). Бұл әдістің мәні қайталамалы байттар сериясын немесе шынжырларды немесе олардың тізбегін бәір кодтаушы байтпен және қайталану санының есептегішіне алмастыру болып табылады.

Мысалы:

44 44 44 11 11 11 11 11 01 33 FF 22 22 – бастапқы берілген тізбек , 03 44 04 11 00 03 01 03 FF 02 22 сығылған тізбек. Бірінші байт келесі байтты неше рет қайталау керектігін көрсетеді. Егер бірінші байт 00-ге тең болса, онда оның артынан қанша қайталанбайтын мәлімет бар екендігін көрсететін есептегіш тұрады. Бұл әдістер растрлы графикалық бейнелерді (BMP, PCX, TIF, GIF) сығуға өте тиімді болып келеді, себебі олар қайталанатын ұзын сериялы байттар тізбегінен тұрады. RLE әдісінің кемшілігі сығу дәрежесінің төмендігі болып табылады.


3. Лемпель –Зив алгоритмі

1977 жылы Абрахам Лемпель және Якоб Зив кейін LZ77 аталған мәліметтерді сығу алгоритмін ұсынды. Бұл алгоритм мәтінді сығу compress,

lha, pkzip және arj программаларында қолданылады.LZ78өзгертілгеналгоритмі екілік мәліметтерді сығу үшін қолданылады. Бұл өзгертілген алгоритмдер АҚШ патентімен қорғалған. Алгоритм биттер тізбегін фразаларға бөлу арқылы кодтап, кейін осы фразаларды кодтауды ұсынады. Алгоритмнің мәні келесіден болады:

Егер мәтінде қайталанатын символдар жолы кездесетін болса, онда олар сол жолға сілтемелермен алмастырылады. Сілтеме форматы <префикс, арақашықтығы, ұзындығы>түрінде болады. Префикс бұл жағдайда 1-ге тең. Арақашықтық өрісі жолдар сөздігіндегі сөзді идентификациялайды.Егер жолсөздікте болмаса, онда <префикс, символ> түріндегі символ коды генерацияланады, мұндағы префикс өрісі=0, ал символ өрісі бастапқы мәтіннің ағымдық символына сәйкес келеді. Осыдан префикстің көрсеткіштер кодын символдар кодынан бөліп тұратынын көруге болады. <Символ> кодтарын кірістіру сөздікті тиімді етуге және сығу тиімділігін арттыруға мүмкіндік береді. Мұндағы негізгі алгоритмдік мәселе тиімді жолды таңдауда болып тұр, себебі мұнда біршама артық алынуы мүмкін.

Мысал қарастырайық. U = 0010001101 бастапқы берілген тізбек.

P[n] —n нөмірлі фраза; C — сығу нәтижесі.

Бастапқы берілген биттер тізбегін фраза түрінде жазу 1-кестеде көрсетілген.

P[0] — бос жол. "." (нүкте) символымен біріктіру операциясы белгіленеді (конкатенация).

Әрқайсысы(A.B) түрінде болатын жолдар жұбын қалыптастырайық. Әрбір жұп жаңа фразаны құрады және осы фразаға қосылатын алдыңғы фразаның идентификаторы мен биттен тұрады. Барлық осы жұптарды біріктіру С соңғы нәтижесін береді. P[1]=P[0].0 (00.0)-ді береді, P[2] = P[1].0 (01.0)-ді береді және т.с.с. түрлендіру схемасы 2-кестеде көрсетілген.

Құрамында P[0] бар барлық формулалар сығуды бермейді. Көріп тұрғанымыздай С U-ға қарағанда ұзынырақ, бірақ бұл бастапқы берілгені қысқа тізбек үшін. Мәлімет үлкен көлемді болғанда бастапқы берілгенді сығу өте жақсы жүзеге асады. Келтірілген мысалдан сығу амалдарының барлығы мәліметтердің көлемін қысқартпайтынын көруге болады.