符号 - alphaomega @ ウィキ

https://ja.wikipedia.org/wiki/%E7%AC%A6%E5%8F%B7
シンボルの集合S, Xがあるとき、Sに含まれるシンボルのあらゆる系列から、Xに含まれるシンボルの系列への写像、または、Sに含まれるシンボルに対してその写像を適用した結果得られるXのシンボルの系列(符号語)の集合のことである。
Sを情報源アルファベット、Xを符号アルファベットという。
すなわち符号とは、情報の断片（例えば、文字、語、句、ジェスチャーなど）を別の形態や表現へ（ある記号から別の記号へ）変換する規則であり、変換先は必ずしも同種のものとは限らない。

つまりある表現を別の表現に変換すること。
シンボルとは表現の種類のことで。文章なら文字(アルファベット、数字等)、コンピュータのデータならバイナリ({0,1})、手旗信号なら個々のジェスチャーがシンボルに当たる。
シンボルとは「情報の表現」のことで、アルファベット(文章)であるならa,b,c...、バイナリなら0,1、手旗信号なら個々のジェスチャーがシンボルに当たる。
シンボルの系列や列とはシンボルを複数個つなげたもの。シンボルが'A','B','C'...など(アルファベット)ならその列は"BLACK"や"TOOL"のようになり、'0'と'1'(バイナリ)なら"101011"のようになる。

例えばASCIIという符号では、アルファベットなどの文字からバイナリへの変換を行う。
'A'というアルファベットのシンボルには"1000001"というバイナリの列を割り当て、'X'には"1011000"というバイナリの列を割り当てる。
同じようにして、"BLACK"というシンボルの列にはそれぞれのシンボルをASCIIで符号化し、"1000010 1001100 1000001 1000011 1001011"というバイナリの列を割り当てる。(見やすいように空白が入っているが実際は入らない)
このように一つの変換前のシンボルが複数個の変換後のシンボル(符号語)に変換される。

変換前のシンボルの集合Sを「情報源アルファベット」、返還後のシンボルの集合Xを「符号アルファベット」という。
符号を用いてシンボルを変換することを「符号化(エンコード)」といい、変換されたシンボルをもとのシンボルに戻すことを「復号(デコード)」という。
SのシンボルをXのシンボルの列へ符号化したものを「符号語」という。
Sのシンボルの列をXのシンボルの列へ符号化したもの(符号語の列)を「符号文字列」という。
SとXが同じこともある。(バイナリからバイナリへの符号など)
SとXが同じでも符号語の長さは一定とは限らない。
異なるシンボルを符号化した結果同じ符号語になることもある。

写像
C={a->0,b->01,c->011}
は符号を表しており、情報源アルファベットは集合{a,b,c}であり、符号アルファベットは集合{0,1}である。この符号を使って 0011001011 という符号文字列が得られたとする。これを符号語に分割すると 0–011–0–01–011 となり、復号すれば acabc というシンボル列が得られる。

つまり数学的にはある集合S,Xについて、SからX*への写像、C:S->X*もしくは、SからX*への写像、C:S*->X*のことを符号という。(*はシンボルの集合からシンボルの列の集合への写像)
C:S*->X*は「Sに含まれるシンボルのあらゆる系列から、Xに含まれるシンボルの系列への写像」に当たる。
C:S->X*の値域は「Sに含まれるシンボルに対してその写像を適用した結果得られるXのシンボルの系列(符号語)の集合」に当たる。

拡張
C:S->X*をC:S*->X*へと拡張すること。
つまり'a','b','c'といった個々のシンボルに対する符号を、"acbd"のようなシンボルの列に対する符号へと拡張する。

可変長符号
情報源の記号に対して割り当てる符号を可変長とする符号である。
符号語の長さが一定でない符号。
符号C={a->0,b->01,c->011}は符号語の長さが一定でないので可変長符号。
ASCIIは1文字を7bitのバイナリで符号化する(符号語の長さが一定)ので可変長符号でない。

非特異符号
情報源の各シンボルが異なる符号語に写像される場合、すなわち、情報源シンボルから符号語への写像が単射である場合、符号が非特異(non-singular)であるという。
例えば、写像M1={a->0,b->0,c->1}は、'a'と'b'の両方が同じビット列"0"に写像されるため、非特異ではない（特異(singular)である）。この写像を拡張すると、非可逆符号になる。これは復号できない。
写像M2={a->1,b->011,c->01110,d->1110,e->10011,f->0}は非特異である。この写像を拡張すると、可逆符号になる。これは復号できる。ただし一意に復号できるとは限らない。

一意復号可能な符号
符号語の復号が一通りしかない場合(符号の拡張が非特異である場合)、その符号は一意復号可能(uniquely decodable)であるという。
一意復号可能なら非特異である。
写像M3={a->0,b->01,c->011}は一意復号可能である。これは、0が符号語の先頭にしか現れないので、符号文字列中に0が現れたら、それが符号語の区切りであることが明白だからである。
M2は非特異だが一意復号可能でない。符号文字列 011101110011 は、符号語 01110-1110-011 の列として解釈できるほか、符号語 011-1-110 の列としても解釈できるからである。よって、この符号文字列は cdb と babe の2通りに復号しうる。

接頭符号
語頭属性 (prefix property) を満たす符号である。
接頭符号ではそれぞれの符号語が決して他の符号語の接頭部にならない。
M3は接頭符号でない。aの符号語0がb,cの符号語の接頭部となっているため。

シャノン符号化
let str=`
In the field of data compression, Shannon coding, named after its creator, Claude Shannon, is a lossless data compression technique for constructing a prefix code based on a set of symbols and their probabilities (estimated or measured). It is suboptimal in the sense that it does not achieve the lowest possible expected code word length like Huffman coding does, and never better but sometimes equal to the Shannon–Fano coding.
`.trim().split("");
let freq=new Map();
str.map(c=> freq.set(c,freq.has(c)?freq.get(c)+1:1) );
freq=Array.from(freq).sort((a,b)=>b[1]-a[1]);
freq.map(s=>s[2]=s[1]/str.length);
freq.map(s=>s[3]=s[1]);
freq.reduce((a,c)=>c[3]=c[3]+a,0);
freq.map(s=>s[3]=s[3]-s[1]);
freq.map(s=>s[3]=s[3]/str.length);
freq.map(s=>s[3]=s[3].toString(2).slice(2).padEnd(53,"0"));
freq.map(s=>s[3]=s[3].slice(0,Math.ceil(-Math.log2(s[2]))));
freq;

シャノン・ファノ符号化
let str=`
In the field of data compression, Shannon coding, named after its creator, Claude Shannon, is a lossless data compression technique for constructing a prefix code based on a set of symbols and their probabilities (estimated or measured). It is suboptimal in the sense that it does not achieve the lowest possible expected code word length like Huffman coding does, and never better but sometimes equal to the Shannon–Fano coding.
`.trim().split("");
let freq=new Map();
str.map(c=> freq.set(c,freq.has(c)?freq.get(c)+1:1) );
freq=Array.from(freq).sort((a,b)=>b[1]-a[1]);
freq.map(s=>s[2]=s[1]/str.length);
freq.map(s=>s[3]="");
function T(subfreq,subtree=[]){

if(subfreq.length<2)return;
subtree[0]={subfreq:[],subtree:[],count:0};
subtree[1]={subfreq:[],subtree:[],count:0};
while(subfreq.length){
	if(subtree[0].count<=subtree[1].count){
		let s=subfreq.shift();
		subtree[0].subfreq.push   (s);
		subtree[0].count+=s[1];
		s[3]+="0";
	}else{
		let s=subfreq.pop  ();
		subtree[1].subfreq.unshift(s);
		subtree[1].count+=s[1];
		s[3]+="1";
	}
}
T(subtree[0].subfreq,subtree[0].subtree);
T(subtree[1].subfreq,subtree[1].subtree);

}
T(Array.from(freq));
freq;