中缀法,前缀法,后缀法 中缀记法: 前缀记法(波兰记法) 后缀记法道波兰记法) e 9 C 《合论与图论》第21讲
《集合论与图论》第21讲 11 中缀法,前缀法,后缀法 中缀记法: 前缀记法(波兰记法): 后缀记法(逆波兰记法): ÷ ÷ ∗ ∗ ∗ - + + a + b c d e f g h i j
中缀法,前缀法,后缀法(例) d中缀:(a*(b+c)*d-e)÷(什+g):(h*(+) 前缀(波兰)÷÷*+bCde+yhi C 后缀(逆波兰)abC*d*ey+:hj+ 《集合论与图论》第21讲
《集合论与图论》第21讲 12 中缀法,前缀法,后缀法(例) 中缀: ((a∗(b+c))∗d-e)÷(f+g)÷(h∗(i+j)) 前缀(波兰): ÷÷-∗∗a+bcde+fg∗h+ij 后缀(逆波兰): abc+∗d∗e-fg+÷hij+∗÷ ÷ ÷ ∗ ∗ ∗ - + + a + b c d e f g h i j
通讯编码 Shannon Hamming Sudan 有噪声信道的可靠通信:编码 信息就是不确定性的消除:熵( entropy 比特(it: binary information unit 例:{0,1,2…7,og98=3,编码为 00001010,,111 秦00011101010译为0725 《集合论与图论》第21讲 13
《集合论与图论》第21讲 13 通讯编码 Shannon, Hamming, Sudan 有噪声信道的可靠通信: 编码 信息就是不确定性的消除: 熵(entropy) 比特(bit): binary information unit 例: {0,1,2,…,7}, log28=3, 编码为 000,001,010,…,111 000111010101译为0725
不等长编码 眷若{0,1,2,…,7}出现频率不一样,则出现频 率高的用短码字 秦例:频率递减:0,1,2,3,4,5,67,编码为 0,1,00,01,10,11000,001 若收到000111能唯一解码 651,235,075等 原因:码字互为前缀,如00是001的前缀 《集合论与图论》第21讲
《集合论与图论》第21讲 14 不等长编码 若{0,1,2,…,7}出现频率不一样,则出现频 率高的用短码字 例: 频率递减: 0,1,2,3,4,5,6,7, 编码为 0,1,00,01,10,11,000,001. 若收到000111, 不能唯一解码: 651, 235, 075,…等. 原因: 码字互为前缀,如00是001的前缀
前缀码 prefix code 前缀码:码字互相不为前缀的不等长编码 前缀码与二叉树对应 例:0,23码为{0001.0111 秦收到000111为023 00 010011 《集合论与图论》第21讲 15
《集合论与图论》第21讲 15 前缀码(prefix code) 前缀码: 码字互相不为前缀的不等长编码 前缀码与二叉树对应 例:{0,1,2,3}编码为 {00,010,011,1} 收到000111,译为 023 0 0 0 1 1 1 00 010 011 1