Huffman කේත: උදාහරණ අයදුම්

ඒ මොහොතේ දී, පුද්ගලයන් අතලොස්සකගේ කාරනය ගැන හිතන්න ගොනුව සම්පීඩන කරන්නේ කොහොමද. පෞද්ගලික පරිගණකය වන අතර මීට පෙර භාවිතා සමඟ සසඳන වඩාත් පහසු වී ඇත. හා ගොනු පද්ධතිය සමඟ වැඩ පුද්ගලයා සෑම ගොනු භාවිතා කරයි. නමුත් සුළු පිරිසක් ඔවුන් වැඩ කරන ආකාරය ගැන සහ ගොනු සම්පීඩන දේ පදනම මත කියලා. මෙම ක්රියාවලිය කරන පළමු අනුවාදය Huffman කේත වූ අතර, ඔවුන් අද ජනප්රිය archivers වල යොදා ඇත. බොහෝ පරිශීලකයන් පවා ගොනු සම්පීඩන සිදු ආකාරය පහසු හිතන්නේ නැහැ එය යෝජනා ක්රමය මත වැඩ කර ඇත. මෙම ලිපියෙන් අපි සම්පීඩන කිරීමෙන් වේගවත් සියුම් දේ ආකාරය දෙස බලා කේතන ක්රම ක්රියාවලිය සරල මෙන්ම, ගස් කේතීකරණ මූලධර්මය දේ බලන්න.

ඉතිහාසය ඇල්ගොරිතමය

ඉලෙක්ට්රොනික තොරතුරු කාර්යක්ෂම පොදු කේතීකරණ කරන පළමු ඇල්ගොරිතමය Huffman එනම් 1952 දී, ලෙස මුල් විසිවන සියවසේ මැද ලෙස යෝජනා කේත බවට පත් වී තිබේ. එය මේ මොහොතේ එම තොරතුරු සංකෝචනය නිර්මාණය වැඩසටහන් බහුතරයක් පදනම අංගයක් වන ඔහු විය. මේ මොහොත වන විට, මෙම කේතය භාවිතා කරමින් වඩාත් ජනප්රිය ආරංචි මාර්ග වලින් එකක් ලේඛනාගාරය ZIP, ARJ, RAR හා තවත් බොහෝ අය වේ. එසේම, Huffman ඇල්ගොරිතමය සඳහා භාවිතා JPEG-රූප සංකෝචනය සහ වෙනත් රූප. හොඳයි, සියලු ෆැක්ස් නවීන කේතනය, 1952 දී නිර්මාණය භාවිතා කර ඇත. කේතය මැවූ තැන් පටන් මේ දවස එය නව පටල සහ උපකරණ පැරණි සහ නූතන වර්ග වල යොදා ඇත ඒ තරම් කාලයක් ගත විය යන කාරනය තිබිය.

කාර්යක්ෂම කේතීකරණ මූලධර්මය

මෙම Huffman ඇල්ගොරිතමය පදනම බොහෝ විට සංකේත ඇතිවීම, ඔබ වඩාත්ම විශ්වාස වෙනුවට ඉඩ සලසා දෙන ක්රමය ඇතුළත් ද්විමය කේතනය පද්ධතිය. සහ අඩු පොදු සිටින අය, තවදුරටත් කේත වෙනුවට. දිගු Huffman කේත යන්නේ පද්ධතිය සියලු අවම අගයන් භාවිතා වූ පසු පමණක් සිදුවේ. මෙම තාක්ෂණය ඔබ සමස්තයක් ලෙස මුල් පණිවිඩය එක් එක් සංකේතය සඳහා කේතය දිග අවම කිරීමට ඉඩ දෙයි. මෙම වැදගත් කරුණ, මෙම ලිපි සිදුවී පොදු කේතීකරණ සම්භාවිතාව ආරම්භයේ දී මේ වන විටත් දන්නා කළ යුතු බව ය. එය සකස් කරන අතර, අවසාන පණිවිඩය ඔවුන් සිට ඇත. මෙම දත්ත මත පදනම් වූ, එය පිටතට Huffman කේතය ගස ඉදිකිරීම, සංරක්ෂණයේ ක්රියාවලිය සංකේතවත් ලිපි පැවැත්වෙන පදනම මත සිදු.

Huffman කේතය, උදාහරණයක්

මෙම ඇල්ගොරිතමය නිදර්ශනය කිරීමට, මෙම කේතය ගසක් ඉදිකිරීම් චිත්රක ප්රභේද්යයක් සලකා බලන්න. ඵලදායී බවට මෙම ක්රමය භාවිතා කිරීම සඳහා, එය එම ක්රියාවලිය පිළිබඳ සංකල්පය සඳහා අවශ්ය සමහර අගයන් අර්ථ දැක්වීම පැහැදිලි කිරීම සඳහා අවශ්ය වේ. node එකක් මතම ඊට අදාල සිට node එකක් මතම ඊට අදාල යොමු කරන ගැටිති හා arcs ඇති බහුවිධ කුලකයකි, ප්රස්තාරය හමුවිය. ගස ම විශේෂිත ගුණ මාලාවක් සමඟ ප්රස්ථාරයක් වේ:

• සෑම node එකක් මතම ඊට අදාල දී arcs එක් වඩා වැඩි ඇතුළත් විය හැකිය;
• මෙම ගැටිති එක ඒ කියන්නේ, ඒ සියල්ල දී චාප කොටසක් විය යුතු නැහැ, ගස මූල විය යුතුය;
• කඳ මෙම arcs ඔස්සේ ආරම්භ නම්, මෙම ක්රියාවලිය ගැටිති ඕනෑම සම්පූර්ණයෙන්ම ලබා ගැනීමට ඉඩ දෙන්න ඕනෑ.

එහි ගසක කොළ ලෙස Huffman කේත කොටසක්, එවැනි දෙයක් ද ඇත. එය ඕනෑම චාප යන්න යුතු සිට node එකක් මතම ඊට අදාල වේ. මංසල දෙකක් චාප සම්බන්ධ කරනු ලැබේ නම්, ඔවුන්ගෙන් එක් කෙනෙක් චාප යනවා node එකක් මතම ඊට අදාල, සහ ඇතුලත් වන්නේ කුමක් කුමන මත පදනම්ව, අනෙක් දරුවා මව් වේ. මංසල දෙකක් එකම මව් node එකක් මතම ඊට අදාල තිබේ නම්, ඔවුන් සහෝදර වෙබ් අඩවි ලෙස හැඳින්වේ. නම්, කොළ, arcs කිහිපයක් ගැටිති සිට පිටත්, පසුව එය ද්විමය ගසක් ලෙස හැඳින්වේ. යන්තම් ඒ නිසා Huffman වෘක්ෂයකි. ඒකක ඉදිකිරීම සැලැස්ම එක් එක් මව් බර එහි සියලු දරුවන් පුරුක් බර එකතුව සමාන වන බවයි.

ගස Huffman ඉදිකිරීම සඳහා ඇල්ගොරිතමයක්

මෙම Huffman කේතය ඉදිකිරීම හෝඩියේ අකුරු ආදානය කර ඇත. අනාගත කේතය ගසක නිදහස් අඩවි ලැයිස්තුවක් ජනනය. ලැයිස්තුවේ එක් එක් node එකක් මතම ඊට අදාල බර ලිපි තනතුරු මෙම node එකක් මතම ඊට අදාල අනුරූප වන සිදුවීමෙ සම්භාවිතාවය සමාන විය යුතුය. මේ අවස්ථාවේ දී, අවම වශයෙන් බර වූ එක් අනාගත ගසක් නොමිලේ වෙබ් අඩවි කිහිපයක් අතරින් තෝරා ගනු ලැබේ. මේ අවස්ථාවේ දී, අවම ගාස්තු කිහිපයක් අඩවි නිරීක්ෂණය කරන්නේ නම්, ඔබ නිදහසේ යුගල ඕනෑම තෝරා ගත හැකිය. එවිට පුරුක් මේ දෙදෙනා වන බර එකතුව තරම් බර යුතු මව් node එකක් මතම ඊට අදාල, නිර්මාණය වෙයි. ඊට පසු, දෙමාපියන් නිදහස් වැසිකිළි ලැයිස්තුව යැවීම, සහ දරුවන් ඉවත් වේ. මෙම චාප සුදුසු දර්ශක, අය හා බිංදු වේ. මෙම ක්රියාවලිය පමණක් තනි node එකක් මතම ඊට අදාල තබා ගැනීමට අවශ්ය තරම් පුනරාවර්තනය වී ඇත. එවිට එහි මුදුනේ සිට පතුල දක්වා ද්විමය ඉලක්කම් ලියන්න.

සම්පීඩන කාර්යක්ෂමතාව වැඩි දියුණු කිරීම

සම්පීඩන කාර්යක්ෂමතාව වැඩි කිරීම සඳහා, එය ගසක් අනුයුක්ත, යම් ගොනුවේ අක්ෂර සිදුවීමෙ සම්භාවිතාවය මත ඇති සියලුම දත්ත භාවිතා කිරීමට, ඔවුන් පෙළ ලේඛන විශාල සංඛ්යාවක් පුරා විසිරී සිටින බව ඉඩ ගසක් ගොඩනැගිල්ල කේතය තුළ අවශ්ය වේ. මෙම ගොනුව හරහා පෙර ඇවිදින්න නම්, ඔබ වහාම සම්පීඩන පහසුකම විෂය ලිපි එහි කොපමණ බොහෝ විට ඇති සංඛ්යා ලේඛන ගණනය කළ හැක.

සම්පීඩන ක්රියාවලිය වේගවත්

මෙම ඇල්ගොරිතමය වේගවත් කිරීම සඳහා, ලිපි පිළිබඳ අර්ථ දැක්වීම යම් ලිපිය සිදුවීමෙ සම්භාවිතාවය, සහ එහි ඇති වීමේ සංඛ්යාතය අනුව නොවේ සිදු කළ යුතු වෙනවා. මෙම ඇල්ගොරිතමය සමග පහසු බවට පත් වෙයි, බොහෝ වේගවත් ඔවුන් සමග කටයුතු කිරීම. එය ද ඉපිලුම් ලක්ෂ්ය අංශය හා සම්බන්ධ මෙහෙයුම් බලයි. මීට අමතරව, මෙම ක්රමය, ගතික Huffman කේතය හෝ, ඒ වෙනුවට මෙම ඇල්ගොරිතමය ම වැඩ කරන ඕනෑම වෙනස් යටත් නොවේ. මෙම ප්රධාන වශයෙන් බඹලොව සංඛ්යාත සමානුපාතික වන බව සත්යයකි. එය ගොනු අවසන් බර, හෝ ඊනියා මූල node එකක් මතම ඊට අදාල ප්රතිකාර කළ යුතු වස්තුවක් අක්ෂර සංඛ්යාව එකතුව සමාන බව ඇත්ත අවධානය යොමු වටී.

නිගමනය

Huffman කේත - බොහෝ ප්රසිද්ධ වැඩසටහන් හා සමාගම් විසින් තවමත් භාවිතා කරන සරල සහ දිගු කාලීනව තහවුරු ඇල්ගොරිතමය. එහි සරල හා පැහැදිලි බව ඵලදායී ප්රතිඵල ඕනෑම පරිමාව ගොනු සංකෝචනය හා සැලකිය යුතු තැටි ගබඩා ඇති ඉඩ ප්රමාණය අඩු ලබා ගත හැකි වනු ඇත. වෙනත් වචන වලින් කිවහොත්, Huffman ඇල්ගොරිතමය - දිගු පරීක්ෂණ කර ඇති අතර, හදිසි මේ දවස අඩු නොකරන ලද වැඩ සටහන. හා, ගොනු විශාලත්වය අඩු, ජාලය හරහා ඔවුන් මාරු මගින් හෝ වෙනත් කිරීමේ හැකියාව එය, වඩාත් සරල වේගවත් සහ පහසු වේ. මෙම ඇල්ගොරිතමය සමග වැඩ කරන, ඔබ යම් තොරතුරු සම්පූර්ණයෙන්ම එහි ව්යුහය හා ගුණාත්මක භාවයට හානියක් නොමැතිව, නමුත් උපරිම ක්රියාත්මක වන පරිදි බර ගොනුව අඩු කිරීමට සංකෝචනය හැක. වෙනත් වචන වලින් කිවහොත්, Huffman කේත පොදු කේතීකරණ වී සහ ගොනු විශාලත්වය සම්පීඩනය වඩාත් ජනප්රිය හා අදාළ ක්රමය තවමත් ඇත.