Azərbaycanca
Беларускі
Dansk
Deutsch
Española
Français
Indonesia
Italiana
日本語
Қазақ
Lietuvos
Nederlands
Português
Русский
සිංහල
แบบไทย
Türkçe
Українська
中國人
United State
Afrikaans
Кодування довжин серій (англ. Run-length encoding, RLE) або Кодування повторів — простий алгоритм стиснення даних, який оперує серіями даних, тобто послідовностями, в яких один і той же символ зустрічається кілька разів поспіль. При кодуванні рядок однакових символів, що становлять серію, замінюється рядком, який містить сам повторюваний символ і кількість його повторів.
Приклад використання
Розглянемо зображення, що містить простий чорний текст на суцільному білому фоні. Тут буде багато серій білих пікселів в порожніх місцях, і багато коротких серій чорних пікселів в тексті. Нехай, наприклад, дано довільний рядок чорно-білого зображення. Тут B (англ. Black) позначає чорний піксель, а W (англ. White) - білий:
WWWWWWWWWWWWBWWWWWWWWWWWWBBBWWWWWWWWWWWWWWWWWWWWWWWWBWWWWWWWWWWWWWW
Якщо ми застосуємо просте кодування довжин серій до цього рядка, то отримаємо таке:
12W1B12W3B24W1B14W
Останній запис інтерпретується як «дванадцять W», «одна B», «дванадцять W», «три B» і т. д. Таким чином, код подає вихідні 67 символів у вигляді всього лише 18.
Однак, у випадку, якщо рядок містить велику кількість неповторюваних символів, його обсяг може зрости.
ABCABCABCDDDFFFFFF1A1B1C1A1B1C1A1B1C3D6F
Проблема вирішується досить просто. Алфавіт, в якому записані довжини серій, розділяється на дві (зазвичай рівні) частини. Алфавіт цілих чисел можна, наприклад, розділити на дві частини: додатні і від'ємні. Додатні використовують для запису кількості повторюваних однакових символів, а від'ємні — для запису кількості неоднакових.
-9ABCABCABC3D6F
Оскільки чисельні типи даних на комп'ютері завжди мають певну межу, виникає ще одна проблема. Припустимо, ми використовуємо тип signed char для запису довжин серій. Тоді ми не можемо записати серію, довшу ніж 127 символів, однією парою «довжина-символ». Якщо поспіль записано 256 символів A, їх розділяють на мінімальну кількість груп:
127A127A2A
Реалізація на конкретній мові програмування алгоритму RLE з урахуванням цих обмежень може бути нетривіальною.
Звичайно, кодування, яке використовується для зберігання зображень, оперує з двійковими даними, а не з символами ASCII, як у розглянутому прикладі, однак принцип залишається таким самим.
Застосування
Вочевидь, що таке кодування ефективно для даних, що містять велику кількість серій, наприклад, для простих графічних зображень, таких як іконки та графічні малюнки. Однак це кодування погано підходить для зображень з плавним переходом тонів, таких як фотографії.
Поширені формати для упаковки даних за допомогою RLE включають в себе , PCX і ILBM.
Методом кодування довжин серій можуть бути стиснуті довільні файли з двійковими даними, оскільки специфікації на формати файлів часто включають в себе повторювані байти в області вирівнювання даних. Проте, сучасні системи стиснення (наприклад, DEFLATE) частіше використовують алгоритми на основі LZ77, які є узагальненням методу кодування довжин серій і оперують з послідовностями символів виду «BWWBWWBWWBWW».
Звукові дані, які мають довгі послідовні серії байт (такі як низькоякісні звукові семпли) можуть бути стиснуті за допомогою RLE після того, як до них буде застосовано Дельта-кодування.
Реалізація алгоритму мовою C/
#include <stdio.h> #include <string.h> int main() { int cnt; char smb; char *code = new char [80]; char *encode = new char [80]; char *str = new char [80]; scanf("%s", code); strcpy(encode, ""); smb = code[0]; cnt = 0; for (int i = 0; i <= strlen(code); i++) { if (code[i]==smb) { cnt++; } else { sprintf(str, "%d", cnt); strcat(encode, str); sprintf(str, "%c", smb); strcat(encode, str); smb = code[i]; cnt = 1; } } printf("%s\n", encode); return 0; } Реалізація алгоритму мовою PHP
<?php $code = 'fafaaaaaaaaaaaaa'; $encode = ''; for ($i = 0; $i < strlen($code);$i++){ $smb = $code[$i] ; $count = 1 ; for ($b = $i; $b < strlen($code);$b++){ if ($code[$b + 1] != $smb) break ; $count++ ; $i++ ; } $encode .= $count . $smb ; } print 'Рядок: ' . $code . ' вдалося стиснути до ' . $encode . '.<br /> і ми заощадили ' . (strlen($code) - strlen($encode)) . ' байтів.' ?> Реалізації алгоритму мовою Delphi/Pascal
function encode(s:string):string; var i,k:integer; c:char; begin Result:=''; if s='' then exit; c:=s[1]; k:=1; for i:=2 to length(s)+1 do if s[i]=c then inc(k) else begin if k>1 then Result:=Result+IntToStr(k); Result:=Result+c; c:=s[i]; k:=1; end; end; function decode(s:string):string; var i,j,c:integer; newS:string; begin i:=1; while i <= length(s) do begin j:=i; while s[j] in ['0'..'9'] do inc(j); if j-i > 0 then begin for c:=1 to strtoint(copy(s,i,j-i)) do newS := newS + s[j]; delete(s,i,j-i+1); end else begin newS := newS + s[i]; inc(i); end; end; result:= newS; end; Реалізації алгоритму на Visual Basic 6
Public Function Encode(ByVal SrcString As String) As String Dim I As Long, N As Long, sResult As String N = 1 For I = 1 To Len(SrcString) If Not Mid(SrcString, I, 1) = Mid(SrcString, I + 1, 1) Then sResult = sResult & IIf(I - N + 1 > 1, CStr(I - N + 1), CStr("")) & Mid(SrcString, I, 1) N = I + 1 End If Next Encode = sResult End Function Див. також
| Ця стаття не містить . (травень 2014) |
 | Це незавершена стаття про алгоритми. Ви можете проєкту, виправивши або дописавши її. |
Вікіпедія, Українська, Україна, книга, книги, бібліотека, стаття, читати, завантажити, безкоштовно, безкоштовно завантажити, mp3, відео, mp4, 3gp, jpg, jpeg, gif, png, малюнок, музика, пісня, фільм, книга, гра, ігри, мобільний, телефон, android, ios, apple, мобільний телефон, samsung, iphone, xiomi, xiaomi, redmi, honor, oppo, nokia, sonya, mi, ПК, web, Інтернет
Koduvannya dovzhin serij angl Run length encoding RLE abo Koduvannya povtoriv prostij algoritm stisnennya danih yakij operuye seriyami danih tobto poslidovnostyami v yakih odin i toj zhe simvol zustrichayetsya kilka raziv pospil Pri koduvanni ryadok odnakovih simvoliv sho stanovlyat seriyu zaminyuyetsya ryadkom yakij mistit sam povtoryuvanij simvol i kilkist jogo povtoriv Priklad vikoristannyaRozglyanemo zobrazhennya sho mistit prostij chornij tekst na sucilnomu bilomu foni Tut bude bagato serij bilih pikseliv v porozhnih miscyah i bagato korotkih serij chornih pikseliv v teksti Nehaj napriklad dano dovilnij ryadok chorno bilogo zobrazhennya Tut B angl Black poznachaye chornij piksel a W angl White bilij WWWWWWWWWWWWBWWWWWWWWWWWWBBBWWWWWWWWWWWWWWWWWWWWWWWWBWWWWWWWWWWWWWW Yaksho mi zastosuyemo proste koduvannya dovzhin serij do cogo ryadka to otrimayemo take 12W1B12W3B24W1B14W Ostannij zapis interpretuyetsya yak dvanadcyat W odna B dvanadcyat W tri B i t d Takim chinom kod podaye vihidni 67 simvoliv u viglyadi vsogo lishe 18 Odnak u vipadku yaksho ryadok mistit veliku kilkist nepovtoryuvanih simvoliv jogo obsyag mozhe zrosti ABCABCABCDDDFFFFFF 1A1B1C1A1B1C1A1B1C3D6F Problema virishuyetsya dosit prosto Alfavit v yakomu zapisani dovzhini serij rozdilyayetsya na dvi zazvichaj rivni chastini Alfavit cilih chisel mozhna napriklad rozdiliti na dvi chastini dodatni i vid yemni Dodatni vikoristovuyut dlya zapisu kilkosti povtoryuvanih odnakovih simvoliv a vid yemni dlya zapisu kilkosti neodnakovih 9ABCABCABC3D6F Oskilki chiselni tipi danih na komp yuteri zavzhdi mayut pevnu mezhu vinikaye she odna problema Pripustimo mi vikoristovuyemo tip signed char dlya zapisu dovzhin serij Todi mi ne mozhemo zapisati seriyu dovshu nizh 127 simvoliv odniyeyu paroyu dovzhina simvol Yaksho pospil zapisano 256 simvoliv A yih rozdilyayut na minimalnu kilkist grup 127A127A2A Realizaciya na konkretnij movi programuvannya algoritmu RLE z urahuvannyam cih obmezhen mozhe buti netrivialnoyu Zvichajno koduvannya yake vikoristovuyetsya dlya zberigannya zobrazhen operuye z dvijkovimi danimi a ne z simvolami ASCII yak u rozglyanutomu prikladi odnak princip zalishayetsya takim samim ZastosuvannyaVochevid sho take koduvannya efektivno dlya danih sho mistyat veliku kilkist serij napriklad dlya prostih grafichnih zobrazhen takih yak ikonki ta grafichni malyunki Odnak ce koduvannya pogano pidhodit dlya zobrazhen z plavnim perehodom toniv takih yak fotografiyi Poshireni formati dlya upakovki danih za dopomogoyu RLE vklyuchayut v sebe PCX i ILBM Metodom koduvannya dovzhin serij mozhut buti stisnuti dovilni fajli z dvijkovimi danimi oskilki specifikaciyi na formati fajliv chasto vklyuchayut v sebe povtoryuvani bajti v oblasti virivnyuvannya danih Prote suchasni sistemi stisnennya napriklad DEFLATE chastishe vikoristovuyut algoritmi na osnovi LZ77 yaki ye uzagalnennyam metodu koduvannya dovzhin serij i operuyut z poslidovnostyami simvoliv vidu BWWBWWBWWBWW Zvukovi dani yaki mayut dovgi poslidovni seriyi bajt taki yak nizkoyakisni zvukovi sempli mozhut buti stisnuti za dopomogoyu RLE pislya togo yak do nih bude zastosovano Delta koduvannya Realizaciya algoritmu movoyu C C include lt stdio h gt include lt string h gt int main int cnt char smb char code new char 80 char encode new char 80 char str new char 80 scanf s code strcpy encode smb code 0 cnt 0 for int i 0 i lt strlen code i if code i smb cnt else sprintf str d cnt strcat encode str sprintf str c smb strcat encode str smb code i cnt 1 printf s n encode return 0 Realizaciya algoritmu movoyu PHP lt php code fafaaaaaaaaaaaaa encode for i 0 i lt strlen code i smb code i count 1 for b i b lt strlen code b if code b 1 smb break count i encode count smb print Ryadok code vdalosya stisnuti do encode lt br gt i mi zaoshadili strlen code strlen encode bajtiv gt Realizaciyi algoritmu movoyu Delphi Pascalfunction encode s string string var i k integer c char begin Result if s then exit c s 1 k 1 for i 2 to length s 1 do if s i c then inc k else begin if k gt 1 then Result Result IntToStr k Result Result c c s i k 1 end end function decode s string string var i j c integer newS string begin i 1 while i lt length s do begin j i while s j in 0 9 do inc j if j i gt 0 then begin for c 1 to strtoint copy s i j i do newS newS s j delete s i j i 1 end else begin newS newS s i inc i end end result newS end Realizaciyi algoritmu na Visual Basic 6Public Function Encode ByVal SrcString As String As String Dim I As Long N As Long sResult As String N 1 For I 1 To Len SrcString If Not Mid SrcString I 1 Mid SrcString I 1 1 Then sResult sResult amp IIf I N 1 gt 1 CStr I N 1 CStr amp Mid SrcString I 1 N I 1 End If Next Encode sResult End FunctionDiv takozhLZ77 Deflate Delta koduvannya Cya stattya ne mistit posilan na dzherela Vi mozhete dopomogti polipshiti cyu stattyu dodavshi posilannya na nadijni avtoritetni dzherela Material bez dzherel mozhe buti piddano sumnivu ta vilucheno traven 2014 Ce nezavershena stattya pro algoritmi Vi mozhete dopomogti proyektu vipravivshi abo dopisavshi yiyi