Data Compression - Run Length Encoding

මතකනේ මීට කලින් අපි දත්ත සම්පීඩනය හා අසම්පීඩනය පිළිබදව සරලව කතාකලා. ඒ වගේම Data compression මූලික වර්ගීකරණය හා ක්‍රමවේදයන් පිළිබඳවත් සුළු සඳහන් කිරීමක් කලා. ඒ ලිපි කීපයට ලැබුණු ප්‍රතිචාර නිසාම අපි තීරණය කලා මේ ක්‍ෂේත්‍රය ගැන විස්තර පළකිරීම කීපදෙනෙකුට හෝ ප්‍රයෝජනවත් වේවි කියලා.

මෙම ලිපියෙහි අරමුණවන්නේ Data compression සඳහා යොදාගන්නා සරලතම ඇල්ගොරිතමයක් වන RLE(Run length encoding) පිළිබඳ උදාහරණ ඇසුරෙන් සාකච්ඡාකිරීමයි.

නමින් හැඟවෙන පරිදිම "ගොනුවක(file එකක) දත්තයන්, රටාවන් ලෙස කෙතරම් දුරකට දිවයන්නේද යන්න නිරූපණය කිරීමෙන් ගොනුවේ එකිනෙක ආසන්නයේ නැවත නැවත යෙදෙන රටාවන් සම්පීඩනය කිරීම" මෙම ඇල්ගොරිතමෙහි අරමුණයි.


1. උදාහරණය aaaaaaaaAAAA යන දත්ත ගොනුවේ යෙදී ඇති රටාව නිරීක්ෂණය කරන්න. එහි එකිනෙක ළඟින් පිහිටි “a” අක්ෂර 8කුත් “A” අක්ෂර 4කුත් දැකිය හැක. ඒ අනුව එය අක්ෂර 12ක විශාලත්වයෙන් යුතු ගොනුවකි. Runlength සම්පීඩනයට අනුව මෙම රටාව සංක්ෂිප්ත කොට a8A4 යනුවෙන් අක්ෂර 4කින් නිරූපණය කළහැක. මෙම සම්පීඩිත ගොනුව අසම්පීඩනය කිරීමෙන් නැවත මුල් ගොනුව ප්‍රතිනිර්මාණය කරගතහැක.

තවත් උදාහරණයක් සලකා බලමු.


2. aaabaaaaAAAA
මෙම දත්ත ගොනුවේදී එකම අක්ෂරය ළඟ ළඟ යෙදෙන රටාවට “b” අකුරකින් බාධා වී ඇති බව නිරීක්ෂණය කරන්න.

සරල runlength නිරූපණය = a3b1a4A4
තනි "b" අක්‍ෂරය නිරූපණය කිරීමට අක්ෂර දෙකකුත් "a" අක්‍ෂර පන්ති දෙකක් ඇති බැවින් ඒ වෙනුවෙන් අක්ෂර 4කුත් යොදාගැනීමට සිදුවී ඇත. පෙර උදාහරණය හා සසඳන විට දැකිය හැක්කේ එක් අක්‍ෂරයක වෙනසක් පමණක් වුවත් එමගින් දත්ත රටාවේ ගලායාමට ඇතිවූ බාධාවේ ප්‍රතිඵලයක් ලෙස පෙර උදාහරණයට සාපේක්‍ෂව සම්පීඩිත ගොනුව තරමක් විශාලවී ඇත.


3. උදා: aAaAaAaAaA
මෙම ගොනුව තුළද එකළඟින් යෙදෙන රටාවක් දැකිය හැක. නමුත් කලින්මෙන් එක් අක්ෂරය බැගින් සලකා runlength නිරූපණය කළහොත් ලැබෙනුයේ අක්ෂර 20කින් සමන්විත ගොනුවකි;

a1A1a1A1a1A1a1A1a1A1

එය මුල්ගොනුව මෙන් දෙගුණයක් විශාලය. එබැවින් මෙම නිරූපණය දත්ත සම්පීඩනයට උචිත නොවේ.

නමුත් මෙම ගොනුව සඳහා අක්ෂර 2 බැගින් සලකා runlength නිරූපණය කිරීමෙන්;

aA5

අක්ෂර 3ක ගොනුවක් නිර්මාණය කරගැනීමට හැකි බව පෙනේ.

දෝෂ නිරාකරණය

සරල බව හේතුවෙන්ම encoding(කේතාංකණ) ක්‍රියාවලිය හා decoding(විකේතන) ක්‍රියාවලිය මුහුණපෑ හැකි විශේෂ අවස්ථා කීපයක් සලකාබලමු.

4. උදා: මුල් ගොනුව තුල අනුයාතව "7" ඉලක්කම් 10කුත් "1" ඉලක්කම් 11කුත් සහිත උදාහරණයක් සලකමු.

File= 7777777777111111111111
කේතාංකණය මගින්

encoded file= 710111

ලෙස කුඩා ගොනුවක් නිර්මාණයකරගත හැකිවුවත් එම නිරූපණය වැරදි ලෙස විකේතනය වියහැක.
decoded file= 701


5. උදා: අක්‍ෂර දෙක බැගින් සලකා කරන ලද කේතාංකණයක් තනි අක්ෂරය බැගින් විකේතනය කිරීමේදී

file= 55555566

අක්ෂර දෙක බැගින් සැලකූවිට
encoded file= 553661

අක්ෂර 1 බැගින් යයි සලකා අසම්පීඩනය කළහොත්
decoded file= 555553333336

මෙවැනි පැටලැවීම් මඟහරවා ගැනීමට encoded ගොනුව නියමිත ආකෘතියකට ගොඩනැගිය යුතුය.
දත්ත රටාව  සඳහා අක්‍ෂර ස්ථාන කීයක් වෙන්කල යුතුද, යෙදී ඇති වාර ගණන දැක්වීමට ස්ථාන කීයක් වෙන්කල යුතුද යන්න එමගින් තීරණය කල යුතුය. 4 උදාහරණයේදී නම් රටාව සඳහා එක් අකුරක්ද වාර ගණන(සංඛ්‍යාතය) සඳහා ස්ථාන දෙකක්ද වෙන්වන බව ඩිකෝඩරය දැනසිටියේ නම් ගැටලුවක් නොවේ. එසේත් නැතිනම් එන්කෝඩරය මගින් රටාවට එක් ස්ථානයක්ද සංඛ්‍යාතයටද එක් ස්ථානයක්ද බැගින් වෙන්කලේනම්;
encoded file=79711912
එවිටද ගැටලුවක් නොවනු ඇත.

නිගමනය

• දත්ත සම්පීඩනය සඳහා යොදාගත හැකි සරලතම ක්‍රමවේදයක් ලෙස Run Length encoding ඇල්ගොරිතම දැක්විය හැක.
• දත්ත ගොනුව තුළ දැකිය හැකි රටාවන් වඩාත් හොඳින් සම්පීඩන වන පරිදි runlength යෙදිය හැකි ආකාර සලකා බැලිය හැක. එක් අක්ෂතරය බැගින් (bit 8 බැගින්), bit 16 බැගින්, bit 4 බැගින්
• එන්කෝඩරය මගින් ගොඩනගනුලබන ගොනුව ඩිකෝඩරයට පැහැදිලිව තේරුම්ගත හැකි පරිදි ආකෘතිගත කල යුතුය.

බිටු 4 බැගින් සලකා RL Encoded උදාහරණයක්
(ද්විමය පාදයෙන් දක්වා ඇත)

• දත්ත ගොනුව තුළ ළඟළඟ යෙදෙන රටාවන් සැලකිය යුතු ප්‍රමාණයක් නොවන විට run length encoding භාවිතයෙන් සම්පීඩනයක් ඇතිකරගත නොහැක.

  එමනිසා බොහෝ අවස්ථාවන්හිදී run length උචිත නොවේ. ප්‍රායෝගික භාවිතයේදී මූලික සම්පීඩන ක්‍රමවේදයකට වඩා වෙනත් ඇල්ගොරිතම ශක්තිමත් කරන උපාංගයක් ලෙස runlength ඇල්ගොරිතම භාවිතයට ගැනේ.

අමතර සටහන

පැහැදිලි කිරීමේ සහ අවබෝධ කරගැනීමේ පහසුව සඳහා "අක්‍ෂර", "අංක" ලෙස සඳහන් කර ඇත. ප්‍රායෝගිකව ඒවා සංඛ්‍යාත්කම(numeric/ හෝ ASCII) බව සලකන්න. 

ගැටලු/අදහස් තියෙනවනම් Comment කරන්ඩ අමතකකරන්ඩ එපා.

වළාකුළු: Compression, Concepts