Clever Geek Handbook

シャノンファーノアルゴリズム

Shannon-Fanoアルゴリズムは、アメリカの科学者ShannonとFanoによって最初に策定された最初の圧縮アルゴリズムの1つであり、Huffmanアルゴリズムと非常によく似ています。 このアルゴリズムは、繰り返し率に基づいています。 そのため、頻繁に発生する文字は短いコードでエンコードされ、まれな文字は長いコードでエンコードされます。

また、エンコードによって取得されるコードはプレフィックスです。 これにより、コードワードのシーケンスを一意にデコードできます。 しかし、これはすべて紹介です。



動作するには、両方のアルゴリズムにアルファベットの要素の頻度の表が必要です。



したがって、ハフマンアルゴリズムは次のように機能します。

  1. 入力は、増加しない周波数の順になります 。
  2. アルファベットの最も頻度の低い2つの文字が選択され、親が作成されます（これらの「葉」の2つの頻度の合計）。
  3. 子孫は削除され、親はその場所に書き込まれ、親の「ブランチ」には番号が付けられます。左のブランチには「1」、右の「0」が割り当てられます。
  4. メインの親である「ルート」が見つかるまで、ステップ2が繰り返されます。




画像






Shannon-Fanoアルゴリズムは次のように機能します。

  1. 入力は、増加しない周波数の順になります。
  2. アルファベットを約2つの部分に分割する中央があります。 これらの部分（アルファベットの頻度の合計）はほぼ等しいです。 「1」が左側に、「0」が右側に割り当てられているため、ツリーの葉が得られます
  3. 手順2は、シーケンスの単一の要素、つまり リーフレット




画像






したがって、ハフマンアルゴリズムは葉から根に移動し、除算を使用したシャノンファノアルゴリズムは根から葉に移動することがわかります。



さて、情報をすばやく理解して、PascalでShannon-Fanoアルゴリズムコードを記述できます。 彼らはそれを書くように頼んだ。 したがって、コメントとともにリストを提供します。 



 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;











まあ、実際に私が話したかったのはそれだけです。 すべての情報はウィキペディアから取得できます。 図は上記の周波数を示しています。



ご清聴ありがとうございました！


More articles:


All Articles