शैनन फानो एलगोरिदम

शैनन-फ़ानो एल्गोरिथ्म पहले संपीड़न एल्गोरिदम में से एक है जो पहली बार अमेरिकी वैज्ञानिकों शैनन और फ़ानो द्वारा तैयार किया गया था, और यह हफ़मैन एल्गोरिदम के लिए एक मजबूत समानता है। एल्गोरिथ्म पुनरावृत्ति दर पर आधारित है। तो, अक्सर होने वाला चरित्र छोटी लंबाई के कोड के साथ एन्कोड किया जाता है, और एक दुर्लभ एक लंबी लंबाई के कोड के साथ एन्कोड किया जाता है।
बदले में, एन्कोडिंग द्वारा प्राप्त कोड उपसर्ग हैं। यह आपको विशिष्ट रूप से कोड शब्दों के किसी भी अनुक्रम को डिकोड करने की अनुमति देता है। लेकिन यह सब एक शुरूआत है।

काम करने के लिए, दोनों एल्गोरिदम में वर्णमाला के तत्वों की आवृत्तियों की एक तालिका होनी चाहिए।

तो, हफमैन एल्गोरिथ्म निम्नानुसार काम करता है:

1. इनपुट गैर-बढ़ती आवृत्तियों के क्रम में आता है ।
2. वर्णमाला के दो सबसे कम-आवृत्ति वाले अक्षर चुने जाते हैं, और एक माता-पिता बनाया जाता है (इन "पत्तियों" की दो आवृत्तियों का योग)।
3. वंशज हटा दिए जाते हैं और माता-पिता को उनके स्थान पर लिखा जाता है, माता-पिता की "शाखाओं" को गिना जाता है: बाईं शाखा को "1", दाईं ओर "0" सौंपा गया है।
4. चरण दो को मुख्य माता-पिता तक दोहराया जाता है, "मूल", पाया जाता है।

शैनन-फ़ानो एल्गोरिथम निम्नानुसार काम करता है:

1. इनपुट गैर-बढ़ती आवृत्तियों के क्रम में आता है।
2. एक मध्य है जो वर्णमाला को लगभग दो भागों में विभाजित करता है। ये भाग (वर्णमाला आवृत्तियों के योग) लगभग बराबर हैं। "1" को बाईं ओर, "0" को दाईं ओर के लिए सौंपा गया है, इसलिए हमें पेड़ के पत्ते मिलते हैं
3. चरण 2 को दोहराया जाता है जब तक कि हमें अनुक्रम का एक तत्व नहीं मिलता है, अर्थात्। चादर

इस प्रकार, यह देखा जा सकता है कि हफ़मैन एल्गोरिथ्म पत्तियों से जड़ की ओर जाता है, और शैनन-फ़ानो एल्गोरिथम विभाजन का उपयोग करते हुए, जड़ से पत्तियों की ओर बढ़ता है।

खैर, जानकारी को जल्दी से समझने के लिए, आप पास्कल में शैनन-फ़ानो एल्गोरिथ्म कोड लिख सकते हैं। उन्होंने इस पर लिखने को कहा। इसलिए, मैं टिप्पणियों के साथ एक सूची दूंगा।

 program ShennonFano; uses crt; const a :array[1..6] of char = ('a','b','c','d','e','f'); {  } af:array[1..6] of integer = (10, 8, 6, 5, 4, 3); {   } {       } procedure SearchTree(branch:char; full_branch:string; start_pos:integer; end_pos:integer); var dS:real; {    } i, m, S:integer; { m -     , S -  ,   } c_branch:string; {      } begin {         } if (a<>' ') then c_branch := full_branch + branch else c_branch := ''; {  :    ,    } if (start_pos = end_pos) then begin WriteLn(a[start_pos], ' = ', c_branch); exit; end; {       } dS := 0; for i:=start_pos to end_pos do dS:= dS + af[i]; dS := dS/2; {      for, while, repeat   } S := 0; i := start_pos; m := i; while ((S+af[i]<dS) and (i<end_pos)) do begin S := S + af[i]; inc(i); inc(m); end; {     } SearchTree('1', c_branch, start_pos, m); {    } SearchTree('0', c_branch, m+1, end_pos); end; begin WriteLn('Press <enter> to show'); ReadLn; ClrScr; {   ,       } SearchTree(' ',' ', 1, 6); ReadLn; end; 
 

program ShennonFano; uses crt; const a :array[1..6] of char = ('a','b','c','d','e','f'); { } af:array[1..6] of integer = (10, 8, 6, 5, 4, 3); { } { } procedure SearchTree(branch:char; full_branch:string; start_pos:integer; end_pos:integer); var dS:real; { } i, m, S:integer; { m - , S - , } c_branch:string; { } begin { } if (a<>' ') then c_branch := full_branch + branch else c_branch := ''; { : , } if (start_pos = end_pos) then begin WriteLn(a[start_pos], ' = ', c_branch); exit; end; { } dS := 0; for i:=start_pos to end_pos do dS:= dS + af[i]; dS := dS/2; { for, while, repeat } S := 0; i := start_pos; m := i; while ((S+af[i]<dS) and (i<end_pos)) do begin S := S + af[i]; inc(i); inc(m); end; { } SearchTree('1', c_branch, start_pos, m); { } SearchTree('0', c_branch, m+1, end_pos); end; begin WriteLn('Press <enter> to show'); ReadLn; ClrScr; { , } SearchTree(' ',' ', 1, 6); ReadLn; end;

खैर, यह वास्तव में मैं बात करना चाहता था। सारी जानकारी विकिपीडिया से ली जा सकती है। आंकड़े ऊपर की आवृत्तियों को दर्शाते हैं।

आपका ध्यान के लिए धन्यवाद!