 |
I. Блок индивидуальных заданий.
|
|
|
|
ПОСТРОЕНИЕ ОПТИМАЛЬНЫХ КОДОВ. АЛГОРИТМЫ СЖАТИЯ ДАННЫХ
I. Блок индивидуальных заданий.
2.1. Кодирование методом Хаффмана.
(30 баллов)
Цель: научиться генерировать коды Хаффмана и пользуясь ими (кодировать/ раскодировать) заданный текст.
Задание: а) перед вами список символов, из которых состоит закодированный текст и вероятность каждого символа в тексте. Пользуясь этой информацией, сгенерируйте коды Хаффмана и расшифруйте закодированный в соседней колонке текст. Подсчитайте коэффициент сжатия. Определите, каким бы мог быть максимальный коэффициент сжатия, пользуясь теоремой Шеннона (предполагая, что мы выделяем –log2(p) бит на каждый символ, где p – вероятность этого символа.
б) выберите самостоятельно текст для кодирования (не менее 10 символов). Определите статистику символов и их вероятности. Сгенерируйте коды Хаффмана. Закодируйте текст с помощью этих кодов. Определите коэффициент сжатия. Определите, каким бы мог быть максимальный коэффициент сжатия и сравните его с полученным.
| Вариант | Символы и их вероятности | Закодированное слово |
| «т»-0.15; «а»-0.15; «л»-0.15; «о»-0.15; «м»-0.08; «е»-0.08; «п»-0.08; «р»-0.08; «к» - 0.08. | ||
| «о»-0.36; «д»-0.09; «б»-0.09; «р»-0.09; «в»-0.09; «л»-0.09; «ь»-0.09; «н»-0.09; | ||
| «а»-0.25; «о»-0.17; «р»-0.17; «л»-0.08; «б»-0.08; «т»-0.08; «н»-0.08; «я»-0.08; | ||
| «и»-0.23; «о»-0.15; «я»-0.15; «р»-0.08; «г»-0.08; «з»-0.08; «л»-0.08; «д»-0.08; «ц»-0.08; | ||
| «о»-0.31; «д»-0.08; «р»-0.08; «г»-0.08; «с»-0.08; «т»-0.08; «я»-0.08; «щ»-0.08; «и»-0.08; «й»-0.08; | ||
| «е»-0.15; «л»-0.15; «т»-0.15; «и»-0.15; «р»-0.08; «б»-0.08; «с»-0.08; «к»-0.08; «а»-0.08; | ||
| «а»-0.18; «о»-0.18; «р»-0.18; «л»-0.09; «б»-0.09; «т»-0.09; «и»-0.09; «я»-0.09; | ||
| «с»-0.23; «н»-0.15; «к»-0.08; «у»-0.08; «т»-0.08; «в»-0.08; «е»-0.08; «и»-0.08; «ы»-0.08; «й»-0.08; | ||
| «и»-0.23; «е»-0.15; «р»-0.08; «п»-0.08; «о»-0.08; «д»-0.08; «ч»-0.08; «с»-0.08; «к»-0.08; «й»-0.08; | ||
| «р»-0.14; «а»-0.14; «и»-0.14; «н»-0.14; «о»-0.07; «ц»-0.07; «л»-0.07; «ь»-0.07; «ы»-0.07; «й»-0.07; | ||
| «и»-0.33; «м»-0.08; «с»-0.08; «т»-0.08; «ф»-0.08; «к»-0.08; «а»-0.08; «ц»-0.08; «я»-0.08; | ||
| «а»-0.17; «н»-0.17; «ц»-0.08; «и»-0.08; «о»-0.08; «р»-0.08; «л»-0.08; «ь»-0.08; «ы»-0.08; «й»-0.08; | ||
| «с»-0.25; «и»-0.25; «е»-0.12; «п»-0.06; «м»-0.06; «т»-0.06; «ч»-0.06; «к»-0.06; «й»-0.06; | ||
| «о»-0.27; «р»-0.09; «п»-0.09; «в»-0.09; «л»-0.09; «ч»-0.09; «н»-0.09; «ы»-0.09; «й»-0.09; | ||
| «а»-0.25; «з»-0.08; «м»-0.08; «р»-0.08; «и»-0.08; «н»-0.08; «о»-0.08; «в»-0.08; «т»-0.08; «ь»-0.08; | ||
| «и»-0.27; «с»-0.18; «м»-0.09; «т»-0.09; «ч»-0.09; «е»-0.09; «к»-0.09; «й»-0.09; | ||
| «р»-0.18; «и»-0.18; «г»-0.09; «е»-0.09; «с»-0.09; «т»-0.09; «а»-0.09; «ц»-0.09; «я»-0.09; | ||
| «и»-0.27; «е»-0.09; «р»-0.09; «в»-0.09; «ф»-0.09; «к»-0.09; «а»-0.09; «ц»-0.09; «я»-0.09; | ||
| «е»-0.18; «р»-0.18; «п»-0.09; «с»-0.09; «т»-0.09; «о»-0.09; «й»-0.09; «к»-0.09; «а»-0.09; | ||
| «е»-0.18; «о»-0.18; «в»-0.18; «л»-0.09; «м»-0.09; «з»-0.09; «с»-0.09; «т»-0.09; | ||
| «е»-0.25; «р»-0.17; «т»-0.17; «с»-0.08; «м»-0.08; «о»-0.08; «п»-0.08; «ь»-0.08; | ||
| «е»-0.33; «н»-0.17; «р»-0.08; «в»-0.08; «д»-0.08; «п»-0.08; «ы»-0.08; «й»-0.08; | ||
| «о»-0.27; «р»-0.18; «у»-0.09; «б»-0.09; «т»-0.09; «п»-0.09; «в»-0.09; «д»-0.09; | ||
| «б»-0.18; «о»-0.18; «с»-0.09; «п»-0.09; «е»-0.09; «д»-0.09; «н»-0.09; «ы»-0.09; «й»-0.09; | ||
| «а»-0.36; «р»-0.18; «т»-0.09; «б»-0.09; «щ»-0.09; «и»-0.09; «н»-0.09; | ||
| «а»-0.27; «т»-0.27; «р»-0.09; «с»-0.09; «н»-0.09; «е»-0.09; «ц»-0.09; | ||
| «о»-0.27; «н»-0.18; «с»-0.09; «т»-0.09; «р»-0.09; «п»-0.09; «и»-0.09; «й»-0.09; | ||
| «е»-0.18; «р»-0.18; «о»-0.18; «г»-0.09; «п»-0.09; «д»-0.09; «к»-0.09; «а»-0.09; | ||
| «п»-0.18; «о»-0.18; «е»-0.18; «р»-0.09; «д»-0.09; «б»-0.09; «н»-0.09; «ы»-0.09; «й»-0.09; | ||
| «е»-0.27; «р»-0.18; «п»-0.09; «в»-0.09; «н»-0.09; «у»-0.09; «т»-0.09; «ь»-0.09; |
|
|
|
2.2 Арифметическое кодирование.
(30 баллов)
Цель: закрепить понимание арифметического кодирования, научиться кодировать и раскодировать данные с помощью этого алгоритма.
Задание: а) перед вами список символов, из которых состоит закодированный текст и вероятность каждого символа в тексте. О закодированном тексте известно количество символов в нем и число – результат арифметического кодирования. Пользуясь этой информацией, сформируйте диапазоны для заданных символов и расшифруйте текст. Переведите кодовое число в двоичный формат и подсчитайте коэффициент сжатия. Определите, каким бы мог быть максимальный коэффициент сжатия, пользуясь теоремой Шеннона (предполагая, что мы выделяем –log2(p) бит на каждый символ, где p – вероятность этого символа.
б) выберите самостоятельно текст для кодирования (около 10 символов). Определите статистику символов и их вероятности. Закодируйте текст с помощью арифметического кодирования. Определите коэффициент сжатия. Определите, каким бы мог быть максимальный коэффициент сжатия и сравните его с полученным.
|
|
|
| Вариант | Символы и их вероятности | Кол-во символов | Кодовое число |
| "е" - 0,2; "р" - 0,2; "п" - 0,1; "к" - 0,1; "у" - 0,1; "и" - 0,1; "т" - 0,1; "ь" - 0,1; | 0,404450863599777 | ||
| "о" - 0,2; "р" - 0,1; "п" - 0,1; "в" - 0,1; "к" - 0,1; "а" - 0,1; "ц" - 0,1; "и" - 0,1; "я" - 0,1; | 0,320822715759277 | ||
| "е" - 0,4; "р" - 0,2; "т" - 0,2; "п" - 0,1; "ь" - 0,1; | 0,818038463592529 | ||
| "а" - 0,3; "р" - 0,1; "с" - 0,1; "п" - 0,1; "ш" - 0,1; "о" - 0,1; "н" - 0,1; "к" - 0,1; | 0,313561102375388 | ||
| "е" - 0,3; "р" - 0,2; "п" - 0,1; "з" - 0,1; "а" - 0,1; "т" - 0,1; "ь" - 0,1; | 0,509613327682018 | ||
| "е" - 0,3; "н" - 0,2; "р" - 0,1; "м" - 0,1; "б" - 0,1; "ы" - 0,1; "й" - 0,1; | 0,715550690889359 | ||
| "е" - 0,3; "р" - 0,2; "п" - 0,1; "м" - 0,1; "я" - 0,1; "т" - 0,1; "ь" - 0,1; | 0,510104730725288 | ||
| "е" - 0,2; "р" - 0,2; "а" - 0,2; "м" - 0,1; "п" - 0,1; "т" - 0,1; "ь" - 0,1; | 0,704517051577568 | ||
| "е" - 0,3; "н" - 0,2; "р" - 0,1; "м" - 0,1; "п" - 0,1; "ы" - 0,1; "й" - 0,1; | 0,715550690889359 | ||
| "о" - 0,4; "д" - 0,2; "в" - 0,2; "п" - 0,1; "р" - 0,1; | 0,637712478637695 | ||
| а" - 0,4; "м" - 0,1; "д" - 0,1; "г" - 0,1; "с" - 0,1; "к" - 0,1; "р" - 0,1; | 0,421010166406631 | ||
| "е" - 0,3; "т" - 0,2; "л" - 0,1; "м" - 0,1; "р" - 0,1; "и" - 0,1; "я" - 0,1; | 0,331104725599289 | ||
| "е" - 0,3; "п" - 0,1; "р" - 0,1; "м" - 0,1; "ш" - 0,1; "а" - 0,1; "т" - 0,1; "ь" - 0,1; | 0,312468331307173 | ||
| "о" - 0,3; "н" - 0,2; "в" - 0,1; "м" - 0,1; "д" - 0,1; "ы" - 0,1; "й" - 0,1; | 0,331120386719704 | ||
| "о" - 0,3; "д" - 0,1; "б" - 0,1; "р" - 0,1; "в" - 0,1; "л" - 0,1; "е" - 0,1; "ц" - 0,1; | 0,313556130975485 | ||
| "е" - 0,2; "н" - 0,2; "р" - 0,1; "п" - 0,1; "о" - 0,1; "с" - 0,1; "ы" - 0,1; "й" - 0,1; | 0,50813390314579 | ||
| "е" - 0,2; "п" - 0,1; "р" - 0,1; "в" - 0,1; "о" - 0,1; "д" - 0,1; "ч" - 0,1; "и" - 0,1; "к" - 0,1; | 0,206182715948671 | ||
| "а" - 0,2; "т" - 0,2; "р" - 0,1; "ш" - 0,1; "ю" - 0,1; "п" - 0,1; "и" - 0,1; "с" - 0,1; | 0,708225514739752 | ||
| "а" - 0,4; "к" - 0,2; "р" - 0,1; "т" - 0,1; "и" - 0,1; "ц" - 0,1; | 0,449482083320618 | ||
| "е" - 0,2; "п" - 0,2; "л" - 0,1; "ь" - 0,1; "н" - 0,1; "и" - 0,1; "ц" - 0,1; "а" - 0,1; | 0,208730863407254 | ||
| "е" - 0,2; "б" - 0,1; "л" - 0,1; "о" - 0,1; "с" - 0,1; "н" - 0,1; "ж" - 0,1; "к" - 0,1; "а" - 0,1; | 0,20691231591627 | ||
| "о" - 0,2; "п" - 0,1; "р" - 0,1; "д" - 0,1; "и" - 0,1; "с" - 0,1; "т" - 0,1; "ы" - 0,1; "й" - 0,1; | 0,206182715948671 | ||
| "е" - 0,2; "н" - 0,2; "р" - 0,1; "в" - 0,1; "я" - 0,1; "д" - 0,1; "ы" - 0,1; "й" - 0,1; | 0,708225103095174 | ||
| "н" - 0,2; "т" - 0,1; "е" - 0,1; "к" - 0,1; "л" - 0,1; "я" - 0,1; "с" - 0,1; "ы" - 0,1; "й" - 0,1; | 0,723456035833806 | ||
| "н" - 0,2; "т" - 0,2; "к" - 0,1; "ц" - 0,1; "е" - 0,1; "о" - 0,1; "р" - 0,1; "а" - 0,1; | 0,471121514216065 | ||
| "о" - 0,2; "в" - 0,1; "р" - 0,1; "б" - 0,1; "ь" - 0,1; "и" - 0,1; "н" - 0,1; "ы" - 0,1; "й" - 0,1; | 0,206182715948671 | ||
| "о" - 0,3; "р" - 0,2; "л" - 0,2; "м" - 0,1; "т" - 0,1; "е" - 0,1; | 0,724304437637329 | ||
| "д" - 0,2; "а" - 0,2; "е" - 0,1; "н" - 0,1; "в" - 0,1; "ц" - 0,1; "т" - 0,1; "ь" - 0,1; | 0,129045903682709 | ||
| "е" - 0,2; "б" - 0,1; "с" - 0,1; "ц" - 0,1; "в" - 0,1; "т" - 0,1; "н" - 0,1; "ы" - 0,1; "й" - 0,1; | 0,206902715843171 | ||
| "т" - 0,2; "а" - 0,2; "и" - 0,1; "н" - 0,1; "р" - 0,1; "д" - 0,1; "ц" - 0,1; "ь" - 0,1; | 0,129071295261383 |
|
|
|
|
|
|
2.3. Словарный алгоритм LZ77.
(20 баллов)
Цель: закрепить понимание работы словарного алгоритма LZ77, научиться кодировать и раскодировать данные с помощью этого алгоритма.
Задание: а) перед вами текст, закодированный с помощью алгоритма LZ77. Раскодируйте его, самостоятельно определите каким должен быть размер словаря (минимальный) и длина совпадения. Пользуясь полученной информацией определите коэффициент сжатия.
б) выберите самостоятельно текст для кодирования (не менее 30 символов) и параметры словаря. Закодируйте текст с алгоритма LZ77. Определите коэффициент сжатия.
| Вариант | Закодированный текст |
| <0,0,"О"> <0,0,"т"> <0,0,"_"> <2,1,"я"> <0,0,"ж"> <0,0,"е"> <0,0,"л"> <0,0,"о"> <0,0,"й"> <0,0,"_"> <0,0,"р"> <0,0,"а"> <0,0,"б"> <6,1,"т"> <0,0,"ы"> <7,1,"е"> <0,0,"щ"> <2,1,"_"> <0,0,"н"> <0,0,"и"> <0,0,"к"> <0,0,"т"> <0,0,"о"> <6,2,"е"> <3,1,"у"> <0,0,"м"> <0,0,"и"> <0,0,"р"> <0,0,"а"> <0,0,"л"> <0,0,","> <0,0,"_"> <0,0,"э"> <0,0,"т"> <0,0,"о"> <4,1,"в"> <0,0,"е"> <0,0,"р"> <0,0,"н"> <6,1,","> <7,1,"н"> <4,1,"_"> <0,0,"з"> <0,0,"а"> <0,0,"ч"> <0,0,"е"> <0,0,"м"> <6,1,"р"> <0,0,"и"> <0,0,"с"> <0,0,"к"> <0,0,"о"> <0,0,"в"> <0,0,"а"> <0,0,"т"> <0,0,"ь"> <0,0,"."> <0,0,"_"> <0,0,"Р"> <3,1,"Р"> <0,0,"е"> <0,0,"й"> <0,0,"г"> <0,0,"а"> <0,0,"н"> | |
| <0,0,"Е"> <0,0,"с"> <0,0,"л"> <0,0,"и"> <0,0,"_"> <0,0,"в"> <0,0,"ы"> <3,1,"ж"> <0,0,"е"> <8,1,"а"> <3,1,"т"> <5,1,","> <12,1,"ч"> <5,1,"о"> <0,0,"б"> <15,2,"Б"> <5,1,"г"> <22,1,"р"> <17,1,"с"> <29,1,"м"> <23,1,"я"> <24,1,"с"> <3,1,","> <12,2,"а"> <12,2,"к"> <16,1,"ж"> <0,0,"и"> <29,1,"е"> <27,1,"е"> <20,1,"у"> <31,1,"о"> <29,1,"в"> <29,1,"ш"> <13,1,"х"> <23,1,"п"> <29,1,"а"> <0,0,"н"> <26,1,"х"> <0,0,"."> <31,1,"В"> <3,1,"А"> <10,1,"л"> <27,1,"н"> <0,0,"."> | |
| <0,0,"З"> <0,0,"д"> <0,0,"р"> <0,0,"а"> <0,0,"в"> <0,0,"ы"> <0,0,"й"> <0,0,"_"> <0,0,"с"> <0,0,"м"> <5,1,"с"> <0,0,"л"> <6,1,"е"> <7,1,"т"> <0,0,"ь"> <11,2,"у"> <12,1,"м"> <0,0,"а"> <11,1,"п"> <0,0,"р"> <13,1,"д"> <3,1,"а"> <12,1,"с"> <13,1,"д"> <0,0,"к"> <0,0,"о"> <0,0,"в"> <14,1,"с"> <3,1,"о"> <15,1,"г"> <8,1,"_"> <9,1,"р"> <6,1,"м"> <8,1,"н"> <0,0,"и"> <0,0,"."> <9,1,"Ф"> <3,1,"Г"> <10,1,"г"> <12,1,"л"> <0,0,"ь"> <10,1,"л"> | |
| <0,0,"Х"> <0,0,"о"> <0,0,"р"> <2,1,"ш"> <0,0,"и"> <0,0,"й"> <0,0,"_"> <0,0,"д"> <4,1,"п"> <0,0,"л"> <11,1,"м"> <0,0,"а"> <0,0,"т"> <9,1,"в"> <0,0,"с"> <0,0,"е"> <0,0,"г"> <13,1,"а"> <7,1,"п"> <13,2,"н"> <0,0,"и"> <14,1,","> <15,1,"ч"> <4,1,"о"> <12,1,"о"> <10,1,"_"> <0,0,"д"> <15,1,"л"> <0,0,"ж"> <0,0,"е"> <7,2,"з"> <0,0,"а"> <0,0,"б"> <0,0,"ы"> <0,0,"т"> <0,0,"ь"> <0,0,"."> <15,1,"Г"> <3,1,"М"> <10,1,"к"> <0,0,"м"> <0,0,"и"> <0,0,"л"> <1,1,"а"> <0,0,"н"> <3,1,"А"> | |
| <0,0,"У"> <0,0,"д"> <0,0,"а"> <0,0,"ч"> <0,0,"н"> <0,0,"о"> <0,0,"_"> <0,0,"в"> <0,0,"ы"> <0,0,"с"> <0,0,"м"> <0,0,"е"> <0,0,"и"> <6,1,"а"> <4,1,"ш"> <0,0,"ь"> <12,1,"л"> <8,1,"ш"> <5,2,"т"> <14,1,"_"> <0,0,"н"> <13,1,"д"> <0,0,"о"> <0,0,"с"> <8,1,"а"> <10,1,"к"> <0,0,"и"> <0,0,","> <15,1,"к"> <10,1,"т"> <12,1,"р"> <0,0,"ы"> <0,0,"е"> <8,1,"е"> <0,0,"с"> <15,1,"ь"> <13,1,"у"> <15,1,"т"> <10,1,"б"> <0,0,"я"> <12,1,"с"> <0,0,"а"> <0,0,"м"> <0,0,"о"> <0,0,"г"> <2,1,"."> <15,1,"А"> <3,1,"Д"> <8,1,"д"> <0,0,"е"> <2,1,"х"> | |
| <0,0,"Л"> <0,0,"ю"> <0,0,"б"> <0,0,"о"> <0,0,"в"> <0,0,"ь"> <0,0,"_"> <0,0,"-"> <2,1,"э"> <0,0,"т"> <8,1,"_"> <3,2,","> <10,1,"ч"> <8,2,"_"> <0,0,"с"> <0,0,"л"> <0,0,"у"> <7,1,"а"> <0,0,"е"> <14,1,"с"> <0,0,"я"> <10,2,"_"> <0,0,"м"> <11,1,"ж"> <12,1,"и"> <0,0,"н"> <14,1,"м"> <4,1,"_"> <2,2,"ж"> <0,0,"е"> <9,1,"щ"> <12,2,"а"> <12,2,","> <13,1,"к"> <0,0,"о"> <0,0,"т"> <2,1,"р"> <0,0,"ы"> <0,0,"е"> <8,1,"н"> <3,2,"з"> <4,1,"а"> <0,0,"ю"> <13,1,"_"> <0,0,"д"> <14,1,"у"> <0,0,"г"> <5,2,"р"> <5,2,"а"> <0,0,"."> <12,1,"С"> <3,1,"М"> <0,0,"о"> <0,0,"э"> <0,0,"м"> <0,0,"л"> | |
| <0,0,"Н"> <0,0,"е"> <0,0,"_"> <0,0,"з"> <0,0,"н"> <0,0,"а"> <0,0,"ю"> <0,0,","> <6,2,"а"> <9,1,"ч"> <0,0,"т"> <0,0,"о"> <13,1,"р"> <0,0,"у"> <0,0,"г"> <14,2,"т"> <14,1,"п"> <8,1,"а"> <0,0,"в"> <0,0,"и"> <15,1,"е"> <0,0,"л"> <0,0,"ь"> <0,0,"с"> <12,1,"в"> <0,0,"о"> <0,0,"?"> <15,1,"О"> <0,0,"н"> <5,1,"_"> <0,0,"ж"> <14,1,"_"> <6,1,"и"> <0,0,"ч"> <5,1,"г"> <10,2,"н"> <10,2,"д"> <13,1,"л"> <0,0,"а"> <11,1,"т"> <0,0,"."> <11,1,"Б"> <3,1,"Х"> <0,0,"о"> <0,0,"у"> <0,0,"п"> <0,0,"г"> | |
| <0,0,"Н"> <0,0,"е"> <0,0,"_"> <0,0,"п"> <3,1,"ч"> <0,0,"а"> <0,0,"л"> <0,0,"ь"> <0,0,"с"> <0,0,"я"> <0,0,","> <10,1,"ч"> <0,0,"т"> <0,0,"о"> <14,1,"л"> <0,0,"ю"> <0,0,"д"> <0,0,"и"> <19,1,"н"> <22,2,"з"> <4,1,"а"> <10,1,"т"> <28,1,"т"> <31,1,"б"> <24,2,"_"> <15,1,"о"> <27,1,"п"> <18,1,"ч"> <16,1,"л"> <0,0,"ь"> <0,0,"с"> <13,2,"_"> <8,1,"т"> <14,2,"т"> <0,0,"ы"> <20,2,"е"> <29,1,"з"> <24,1,"а"> <31,1,"ш"> <20,1,"_"> <23,1,"ю"> <0,0,"д"> <29,1,"й"> <0,0,"."> <24,1,"К"> <23,1,"н"> <0,0,"ф"> <0,0,"у"> <0,0,"ц"> <0,0,"и"> <10,1,"”> | |
| <0,0,"Ж"> <0,0,"е"> <0,0,"н"> <0,0,"щ"> <0,0,"и"> <3,1,"а"> <0,0,"_"> <0,0,"в"> <0,0,"д"> <0,0,"о"> <0,0,"х"> <10,1,"о"> <6,1,"л"> <0,0,"я"> <0,0,"е"> <0,0,"т"> <12,1,"м"> <0,0,"у"> <0,0,"ж"> <0,0,"ч"> <0,0,"и"> <13,1,"у"> <8,1,"н"> <0,0,"а"> <11,1,"в"> <15,1,"л"> <10,1,"к"> <12,1,"е"> <11,1,"д"> <8,2,"а"> <13,1,"и"> <15,1,"м"> <15,1,"ш"> <7,1,"е"> <0,0,"т"> <14,1,"е"> <8,1,"у"> <13,1,"с"> <0,0,"о"> <0,0,"в"> <13,1,"р"> <14,2,"т"> <0,0,"ь"> <14,1,"и"> <0,0,"х"> <0,0,"."> <14,1,"А"> <3,1,"Д"> <0,0,"ю"> <0,0,"м"> <13,1,""> | |
| <0,0,"Д"> <0,0,"е"> <0,0,"л"> <0,0,"а"> <0,0,"й"> <0,0,","> <0,0,"_"> <0,0,"ч"> <0,0,"т"> <0,0,"о"> <4,1,"м"> <3,1,"ж"> <13,1,"ш"> <0,0,"ь"> <12,2,"с"> <14,1,"т"> <8,1,"м"> <7,2,"ч"> <6,1,"о"> <11,1,"и"> <8,1,"е"> <11,1,"ш"> <0,0,"ь"> <12,2,"т"> <0,0,"а"> <9,1,","> <13,1,"г"> <0,0,"д"> <13,1,"_"> <9,1,"ы"> <12,1,"е"> <0,0,"с"> <14,1,"ь"> <0,0,"."> <13,1,"Т"> <3,1,"Р"> <0,0,"у"> <0,0,"з"> <0,0,"в"> <12,1,"л"> <11,1,"т"> | |
| <0,0,"Н"> <0,0,"р"> <0,0,"а"> <0,0,"в"> <0,0,"с"> <0,0,"т"> <3,1,"е"> <0,0,"н"> <1,1,"о"> <7,2,"ь"> <0,0,"_"> <0,0,"у"> <0,0,"ч"> <0,0,"и"> <13,1,"_"> <12,1,"е"> <8,1,"т"> <14,1,"м"> <11,1,","> <14,1,"к"> <28,1,"к"> <18,1,"с"> <29,1,"а"> <24,2,"_"> <28,1,"ч"> <11,1,"с"> <31,1,"л"> <28,1,"в"> <0,0,"ы"> <23,1,","> <31,1,"а"> <24,2,"а"> <24,2,"с"> <24,2,"т"> <24,2,"д"> <0,0,"о"> <23,2,"о"> <0,0,"й"> <0,0,"н"> <23,2,"_"> <31,1,"ч"> <24,1,"с"> <17,2,"я"> <0,0,"."> <31,1,"И"> <3,1,"К"> <31,1,"н"> <29,1,""> | |
| <0,0,"С"> <0,0,"а"> <0,0,"м"> <0,0,"о"> <0,0,"е"> <0,0,"_"> <0,0,"н"> <6,1,"д"> <5,1,"ж"> <5,1,"о"> <9,2,"л"> <12,1,"к"> <11,1,"р"> <0,0,"с"> <0,0,"т"> <0,0,"в"> <11,1,"_"> <13,1,"т"> <13,1,"и"> <14,1,"л"> <0,0,"ю"> <0,0,"з"> <5,1,"й"> <11,1,"-"> <13,1,"в"> <7,1,"г"> <12,1,"я"> <0,0,"д"> <7,2,"_"> <15,1,"е"> <0,0,"р"> <0,0,"к"> <0,0,"а"> <11,1,"о"> <0,0,"."> <11,1,"О"> <3,1,"Х"> <8,1,"к"> <0,0,"с"> <10,1,"и"> | |
| <0,0,"М"> <0,0,"у"> <0,0,"ж"> <0,0,"ч"> <0,0,"и"> <0,0,"н"> <0,0,"а"> <0,0,","> <0,0,"_"> <0,0,"е"> <0,0,"с"> <0,0,"л"> <0,0,"и"> <5,1,"б"> <0,0,"ы"> <3,1,"с"> <0,0,"м"> <0,0,"о"> <0,0,"г"> <5,1,"п"> <4,1,"н"> <0,0,"я"> <0,0,"т"> <0,0,"ь"> <0,0,","> <0,0,"_"> <0,0,"ч"> <5,1,"о"> <4,1,"д"> <0,0,"у"> <0,0,"м"> <0,0,"а"> <0,0,"е"> <0,0,"т"> <7,1,"ж"> <4,1,"н"> <0,0,"щ"> <0,0,"и"> <3,1,"а"> <0,0,","> <0,0,"_"> <0,0,"в"> <0,0,"с"> <0,0,"е"> <4,1,"р"> <0,0,"а"> <6,1,"н"> <0,0,"о"> <6,1,"н"> <0,0,"е"> <3,1,"п"> <6,1,"в"> <5,1,"р"> <0,0,"и"> <0,0,"л"> <0,0,"_"> <0,0,"б"> <0,0,"ы"> <0,0,"."> <4,1,"Д"> <3,1,"П"> <0,0,"а"> <0,0,"р"> <0,0,"к"> <0,0,"е"> <3,1,""> | |
| <0,0,"У"> <0,0,"с"> <0,0,"п"> <0,0,"е"> <0,0,"х"> <0,0,"_"> <0,0,"-"> <2,1,"д"> <6,1,"л"> <0,0,"о"> <7,1,"ч"> <0,0,"и"> <14,1,"т"> <6,1,"г"> <8,2,"с"> <12,1,"у"> <11,1,"а"> <0,0,"я"> <0,0,"."> <8,1,"Э"> <14,2,"_"> <0,0,"в"> <9,1,"м"> <8,1,"с"> <0,0,"к"> <14,1,"ж"> <0,0,"е"> <12,1,"_"> <0,0,"л"> <0,0,"ю"> <0,0,"б"> <0,0,"о"> <0,0,"й"> <13,1,"н"> <10,1,"у"> <0,0,"д"> <15,1,"ч"> <6,1,"и"> <0,0,"к"> <0,0,"."> <11,1,"Э"> <3,1,"У"> <7,1,"л"> <0,0,"с"> <0,0,"о"> <12,1,"”> | |
| <0,0,"С"> <0,0,"в"> <0,0,"о"> <0,0,"б"> <2,1,"д"> <0,0,"а"> <0,0,"_"> <0,0,"н"> <0,0,"и"> <0,0,"ч"> <0,0,"е"> <0,0,"г"> <11,1,"_"> <7,1,"е"> <10,1,"с"> <0,0,"т"> <7,1,"и"> <3,1,","> <10,1,"е"> <8,1,"л"> <7,1,"_"> <10,1,"н"> <0,0,"а"> <9,1,"н"> <10,1,"_"> <0,0,"в"> <0,0,"к"> <12,1,"ю"> <0,0,"ч"> <10,1,"е"> <0,0,"т"> <9,2,"_"> <0,0,"с"> <14,1,"б"> <0,0,"я"> <5,2,"в"> <0,0,"о"> <6,1,"о"> <0,0,"д"> <0,0,"у"> <15,1,"о"> <0,0,"ш"> <0,0,"и"> <14,1,"а"> <0,0,"т"> <0,0,"ь"> <15,1,"я"> <0,0,"."> <11,1,"М"> <3,1,"Г"> <10,1,"н"> <0,0,"д"> <15,1,"”> | |
| <0,0,"Н"> <0,0,"а"> <0,0,"у"> <0,0,"к"> <0,0,"и"> <0,0,"_"> <0,0,"д"> <0,0,"е"> <0,0,"л"> <0,0,"я"> <0,0,"т"> <0,0,"с"> <3,1,"_"> <0,0,"н"> <14,1,"_"> <10,1,"с"> <9,1,"е"> <3,2,"в"> <17,1,"н"> <12,1,"ы"> <21,1,","> <17,2,"е"> <16,8,"н"> <16,3,"_"> <0,0,"и"> <31,1,"п"> <0,0,"р"> <0,0,"о"> <29,1,"и"> <30,1,"о"> <22,8,"н"> <22,3,"."> <23,1,"Л"> <3,1,"Л"> <0,0,"а"> <31,1,"д"> <3,1,"у"> | |
| <0,0,"Ф"> <0,0,"и"> <0,0,"л"> <0,0,"о"> <0,0,"с"> <2,1,"ф"> <0,0,"ы"> <0,0,"_"> <0,0,"-"> <2,1,"э"> <0,0,"т"> <10,1,"_"> <13,1,"ю"> <0,0,"д"> <0,0,"и"> <0,0,","> <12,1,"к"> <9,1,"т"> <11,1,"р"> <0,0,"ы"> <0,0,"е"> <8,2,"_"> <10,1,"л"> <0,0,"ю"> <0,0,"ч"> <0,0,"а"> <0,0,"м"> <9,1,"п"> <15,1,"д"> <0,0,"б"> <0,0,"и"> <0,0,"р"> <9,1,"ю"> <0,0,"т"> <10,1,"з"> <14,2,"к"> <10,1,"."> <7,1,"С"> <3,1,"Л"> <0,0,"е"> <9,1,"."> | |
| <0,0,"Н"> <0,0,"е"> <0,0,"б"> <0,0,"о"> <0,0,"л"> <0,0,"ь"> <0,0,"ш"> <0,0,"а"> <0,0,"я"> <0,0,"_"> <0,0,"и"> <0,0,"н"> <0,0,"ф"> <9,1,"я"> <0,0,"ц"> <6,1,"я"> <9,1,"-"> <11,1,"в"> <0,0,"с"> <22,1,"_"> <0,0,"р"> <19,1,"в"> <17,1,"о"> <0,0,","> <22,1,"ч"> <0,0,"т"> <31,1,"_"> <25,1,"е"> <0,0,"б"> <10,1,"л"> <0,0,"ь"> <0,0,"ш"> <17,1,"я"> <27,1,"б"> <24,1,"р"> <26,1,"м"> <28,1,"н"> <25,2,"с"> <23,1,"ь"> <0,0,"."> <28,1,"Ф"> <3,1,"Р"> <0,0,"у"> <0,0,"з"> <0,0,"в"> <29,1,"л"> <27,1,"т"> | |
| <0,0,"Н"> <0,0,"и"> <0,0,"к"> <0,0,"о"> <0,0,"г"> <0,0,"д"> <0,0,"а"> <0,0,"_"> <0,0,"с"> <0,0,"т"> <7,1,"л"> <0,0,"ь"> <11,2,"_"> <0,0,"н"> <0,0,"е"> <11,1,"л"> <16,1,"у"> <13,1,","> <17,1,"к"> <20,1,"к"> <21,1,"в"> <16,2,"в"> <0,0,"р"> <17,1,"м"> <0,0,"я"> <9,2,"о"> <0,0,"й"> <25,1,"ы"> <20,2,"п"> <16,1,"с"> <29,1,"е"> <26,1,"о"> <0,0,"х"> <23,1,"т"> <13,1,"_"> <0,0,"и"> <30,1,"д"> <30,2,"в"> <21,1,"б"> <26,1,"р"> <28,1,"в"> <0,0,"."> <26,1,"О"> <3,1,"Б"> <17,1,"с"> <0,0,"м"> <0,0,"а"> <12,1,"к"> | |
| <0,0,"О"> <0,0,"д"> <0,0,"н"> <0,0,"и"> <0,0,"_"> <0,0,"к"> <0,0,"о"> <0,0,"п"> <0,0,"я"> <0,0,"т"> <0,0,","> <7,1,"с"> <0,0,"л"> <8,1,"в"> <14,1,"о"> <14,1,"д"> <14,1,"л"> <0,0,"ж"> <21,1,"ы"> <21,1,"ж"> <24,1,"т"> <0,0,"ь"> <26,1,"в"> <0,0,"е"> <0,0,"ч"> <18,2,","> <19,2,"р"> <0,0,"у"> <0,0,"г"> <15,1,"е"> <26,1,"т"> <7,1,"а"> <20,1,"я"> <22,1,","> <27,1,"с"> <0,0,"л"> <20,1,"в"> <23,2,"_"> <15,1,"о"> <17,1,"ч"> <17,1,"с"> <29,1,"у"> <0,0,"м"> <30,2,"т"> <0,0,"."> <29,1,"А"> <29,1,"и"> <24,1,"т"> <18,2,"е"> <28,1,"ь"> | |
| <0,0,"Е"> <0,0,"с"> <0,0,"л"> <0,0,"и"> <0,0,"_"> <0,0,"н"> <0,0,"а"> <0,0,"ч"> <2,1,"л"> <0,0,"ь"> <10,1,"т"> <0,0,"в"> <0,0,"о"> <11,2,"е"> <14,1,"д"> <3,1,"л"> <16,1,"е"> <12,1,"_"> <21,2,"м"> <25,1,"з"> <29,1,"о"> <0,0,","> <30,1,"т"> <22,2,"э"> <4,2,"_"> <0,0,"у"> <0,0,"ж"> <27,2,"н"> <30,1,"м"> <27,1,"л"> <19,1,"е"> <28,1,"б"> <24,1,"а"> <0,0,"г"> <26,1,"."> <31,1,"П"> <3,1,"Б"> <28,1,"м"> <17,1,"р"> <0,0,"ш"> <25,1,"”> | |
| <0,0,"Д"> <0,0,"и"> <0,0,"р"> <0,0,"е"> <0,0,"к"> <0,0,"т"> <0,0,"о"> <5,1,"_"> <0,0,"-"> <2,1,"т"> <0,0,"а"> <9,1,"о"> <0,0,"й"> <8,1,"ж"> <15,1,"_"> <0,0,"ч"> <18,1,"л"> <17,1,"в"> <22,2,","> <20,1,"к"> <18,2,"_"> <0,0,"и"> <26,1,"в"> <0,0,"с"> <19,2,"о"> <4,1,"т"> <30,1,"л"> <0,0,"ь"> <0,0,"н"> <0,0,"ы"> <29,1,","> <30,1,"т"> <28,1,"л"> <9,1,"к"> <16,1,"_"> <18,1,"н"> <21,2,"б"> <30,1,"э"> <14,2,"м"> <29,1,"н"> <22,1,"_"> <0,0,"з"> <27,1,"а"> <27,1,"т"> <0,0,"."> <28,1,"Г"> <3,1,"Ч"> <8,1,"н"> <0,0,"д"> <0,0,"л"> <16,1,"р"> | |
| <0,0,"В"> <0,0,"е"> <0,0,"д"> <0,0,"и"> <0,0,"_"> <0,0,"с"> <5,1,"б"> <0,0,"я"> <5,1,"т"> <0,0,"а"> <0,0,"к"> <0,0,","> <10,1,"б"> <0,0,"у"> <15,1,"т"> <0,0,"о"> <11,2,"ы"> <19,1,"у"> <0,0,"ж"> <25,1,"_"> <23,1,"ч"> <19,1,"с"> <22,1,"л"> <31,1,"в"> <23,2,"и"> <30,2,"ы"> <28,1,"д"> <18,1,"й"> <15,2,"в"> <15,1,"т"> <25,1,"л"> <0,0,"ь"> <0,0,"н"> <0,0,"о"> <29,2,"т"> <29,1,"е"> <0,0,"ш"> <9,1,"_"> <18,1,"ч"> <7,1,"с"> <28,1,"л"> <21,1,"в"> <28,1,"е"> <0,0,"."> <19,1,"Д"> <3,1,"К"> <20,1,"р"> <27,1,"е"> <0,0,"г"> <14,1,"”> | |
| <0,0,"К"> <0,0,"а"> <0,0,"ж"> <0,0,"д"> <3,1,"я"> <0,0,"_"> <0,0,"н"> <7,1,"ц"> <0,0,"и"> <6,2,"и"> <0,0,"з"> <0,0,"в"> <0,0,"е"> <0,0,"с"> <0,0,"т"> <12,2,"_"> <7,1,"_"> <0,0,"м"> <15,1,"р"> <11,1,"_"> <0,0,"г"> <0,0,"л"> <11,1,"в"> <14,1,"ы"> <11,1,"_"> <0,0,"о"> <0,0,"б"> <13,1,"а"> <0,0,"з"> <5,1,"м"> <8,1,"с"> <14,1,"о"> <0,0,"и"> <14,1,"и"> <15,1,"п"> <11,1,"р"> <13,1,"к"> <0,0,"а"> <9,2,"."> <10,1,"Д"> <0,0,"ж"> <4,1,"К"> <13,1,"н"> <14,1,"а"> <0,0,"д"> | |
| <0,0,"Н"> <0,0,"и"> <0,0,"_"> <0,0,"о"> <0,0,"д"> <0,0,"н"> <3,1,"_"> <0,0,"к"> <0,0,"р"> <0,0,"у"> <0,0,"п"> <7,2,"е"> <13,1,"с"> <14,1,"с"> <0,0,"т"> <14,1,"я"> <10,1,"и"> <10,2,"ч"> <13,1,"с"> <10,1,"н"> <0,0,"ы"> <0,0,"м"> <8,1,"п"> <0,0,"у"> <7,1,"е"> <6,2,"н"> <0,0,"и"> <9,1,"р"> <0,0,"а"> <0,0,"з"> <11,1,"_"> <8,1,"а"> <0,0,"ж"> <10,1,"т"> <0,0,"о"> <15,2,"е"> <15,1,"б"> <0,0,"ы"> <0,0,"л"> <8,1,"."> <9,1,"Р"> <12,1,"к"> <0,0,"ф"> <12,1,"л"> <10,1,"е"> <0,0,"р"> | |
| <0,0,"С"> <0,0,"л"> <0,0,"о"> <0,0,"н"> <0,0,"_"> <0,0,"-"> <2,1,"э"> <0,0,"т"> <7,1,"_"> <0,0,"м"> <0,0,"ы"> <0,0,"ш"> <0,0,"ь"> <0,0,","> <12,1,"и"> <0,0,"з"> <0,0,"г"> <18,1,"т"> <20,1,"в"> <23,1,"е"> <23,1,"н"> <0,0,"а"> <0,0,"я"> <26,1,"п"> <23,2,"п"> <0,0,"р"> <8,1,"в"> <21,1,"т"> <15,1,"л"> <28,1,"с"> <23,1,"в"> <21,2,"н"> <29,1,"м"> <0,0,"у"> <22,1,"з"> <26,1,"к"> <28,1,"з"> <7,1,"."> <30,1,"Р"> <3,1,"Х"> <28,1,"й"> <19,1,"л"> <4,2,"н"> | |
| <0,0,"Е"> <0,0,"с"> <0,0,"л"> <0,0,"и"> <0,0,"_"> <0,0,"б"> <0,0,"ы"> <3,1,"я"> <5,1,"н"> <0,0,"а"> <8,1,"о"> <0,0,"д"> <12,1,"н"> <13,1,"д"> <0,0,"е"> <10,1,"ь"> <18,1,"с"> <0,0,"т"> <14,1,"л"> <23,1,"к"> <16,1,"р"> <18,1,"л"> <14,1,"м"> <0,0,","> <29,2,"_"> <0,0,"п"> <27,2,"о"> <0,0,"ж"> <30,1,"а"> <20,2,"б"> <0,0,"ы"> <28,2,"_"> <23,1,"е"> <0,0,"ф"> <27,2,"м"> <14,1,"м"> <0,0,"и"> <26,1,"д"> <24,1,"_"> <0,0,"з"> <22,1,"в"> <0,0,"т"> <17,1,"а"> <0,0,"."> <26,1,"П"> <3,1,"У"> <26,1,"т"> <18,1,"н"> <25,1,"в"> | |
| <0,0,"В"> <0,0,"с"> <0,0,"я"> <0,0,"к"> <0,0,"а"> <3,1,"_"> <0,0,"и"> <7,1,"т"> <3,1,"н"> <8,1,"_"> <0,0,"р"> <0,0,"о"> <0,0,"ж"> <0,0,"д"> <14,1,"е"> <11,1,"с"> <17,2,"к"> <21,1,"к"> <21,1,"е"> <15,1,"е"> <30,1,"ь"> <27,2,"_"> <0,0,"у"> <0,0,"м"> <31,1,"р"> <22,2,"т"> <20,2,"а"> <20,2,"п"> <20,2,"д"> <13,2,"с"> <24,1,"у"> <6,1,"о"> <15,1,"."> <28,1,"Т"> <3,1,"Г"> <24,1,"к"> <13,1,"л"> <31,1,"”> | |
| <0,0,"Е"> <0,0,"д"> <0,0,"и"> <0,0,"н"> <0,0,"с"> <0,0,"т"> <0,0,"в"> <0,0,"е"> <5,1,"н"> <0,0,"ы"> <0,0,"й"> <0,0,"_"> <9,1,"п"> <0,0,"о"> <12,1,"о"> <0,0,"б"> <7,1,"о"> <7,1,"р"> <16,1,"д"> <18,1,"л"> <25,1,"т"> <0,0,"ь"> <18,1,"г"> <10,1,"а"> <31,1,"и"> <0,0,"ц"> <27,1,"_"> <0,0,"в"> <25,1,"з"> <0,0,"м"> <28,1,"ж"> <11,1,"о"> <16,1,"о"> <30,1,"-"> <13,2,"ы"> <0,0,"й"> <27,1,"и"> <27,1,"з"> <26,1,"_"> <0,0,"э"> <7,2,"_"> <18,1,"р"> <8,1,"н"> <13,1,"ц"> <18,1,"."> <24,1,"А"> <3,1,"К"> <0,0,"л"> <19,1,"р"> <0,0,"к"> | |
| <0,0,"О"> <0,0,"б"> <0,0,"_"> <0,0,"у"> <0,0,"м"> <0,0,"е"> <4,1,"п"> <0,0,"р"> <0,0,"а"> <0,0,"в"> <0,0,"и"> <0,0,"т"> <8,1,"л"> <0,0,"я"> <14,1,"с"> <15,1,"д"> <5,1,"т"> <16,2,"о"> <23,1,"т"> <3,1,"м"> <26,1,","> <29,1,"к"> <24,1,"к"> <24,1,"х"> <31,1,"л"> <0,0,"ю"> <21,1,"е"> <0,0,"й"> <27,1,"о"> <0,0,"н"> <15,2,"_"> <0,0,"с"> <9,1,"б"> <11,1,"_"> <31,1,"р"> <21,1,"б"> <20,1,"и"> <0,0,"ж"> <28,1,"е"> <0,0,"т"> <0,0,"."> <28,1,"Н"> <3,1,"М"> <8,1,"к"> <15,1,"а"> <0,0,"в"> <24,1,"л"> <18,2,"”> |
|
|
|
2.4. Словарный алгоритм LZSS.
(20 баллов)
Цель: закрепить понимание работы словарного алгоритма LZSS, научиться кодировать и раскодировать данные с помощью этого алгоритма.
Задание: а) перед вами текст, закодированный с помощью алгоритма LZSS. Раскодируйте его, самостоятельно определите каким должен быть размер словаря (минимальный) и длина совпадения. Пользуясь полученной информацией определите коэффициент сжатия.
б) выберите самостоятельно текст для кодирования (не менее 30 символов) и параметры словаря. Закодируйте текст с алгоритма LZSS. Определите коэффициент сжатия.
| Вариант | Закодированный текст | ||||
| <0("Д")> <0("л")> <0("я")> <0("_")> <0("б")> <0("о")> <1(5,1)> <0("ь")> <0("ш")> <0("и")> <0("н")> <0("с")> <0("т")> <0("в")> <0("а")> <1(12,1)> <1(15,1)> <0("ю")> <0("д")> <0("е")> <0("й")> <1(18,1)> <1(13,1)> <1(12,1)> <0("п")> <0("р")> <1(12,1)> <1(14,1)> <1(19,1)> <1(17,1)> <1(23,1)> <1(20,1)> <1(30,1)> <0(",")> <1(31,1)> <0("з")> <1(26,1)> <1(23,1)> <0("ч")> <1(11,2)> <1(26,1)> <1(18,1)> <0("о")> <0("м")> <1(26,1)> <1(10,1)> <1(15,1)> <1(19,2)> <1(29,1)> <1(28,1)> <1(25,1)> <1(10,1)> <1(32,1)> <1(21,1)> <1(20,1)> <1(12,1)> <0("д")> <1(16,1)> <1(29,1)> <1(32,1)> <1(25,1)> <1(23,1)> <0("к")> <1(26,1)> <0(".")> <1(26,1)> <0("В")> <1(26,1)> <0("л")> <1(22,1)> <1(32,1)> <1(28,1)> <0("р")> | |||||
<0("В")> <0("с")> <0("е")> <0("г")> <0("о")> <0("_")> <1(5,1)> <0("п")> <0("р")> <0("а")> <0("в")> <1(9,1)> <0("д")> <0("л")> <0("и")> <1(5,2)> <1(15,1)> <1(13,1)> <0("н")> <1(11,1)> <1(16,2)> <1(13,2)> <0("т")> <1(9,2)> <0("б")> <0("ы")> <1(17,1)> <1(26,1)> <1(24,2)> <0("з")> <1(23,1)> <1(25
Воспользуйтесь поиском по сайту:  ©2015 - 2024 megalektsii.ru Все авторские права принадлежат авторам лекционных материалов. Обратная связь с нами...
|