徽标
联盟百科
通讯
下载应用,请到 Google Play
新! 在您的Android™设备上下载联盟百科!
自由
比浏览器更快的访问!
 

香农-范诺编码

指数 香农-范诺编码

在数据压缩的领域里,香农-范诺编码(Shannon–Fano coding)是一种基于一组符号集及其出現的或然率(估量或测量所得),从而构建前缀码的技术。其名稱來自於以克劳德·香农和羅伯特·法諾。在理想意义上,它与哈夫曼编码一样,并未实现码词(code word)长度的最低预期;然而,与哈夫曼编码不同的是,它确保了所有的码词长度在一个理想的理论范围 P(x)之内。这项技术是香农于1948年,在他介绍信息理论的文章“通信数学理论”中被提出的。这个方法归功于范诺,他在不久以后以技术报告发布了它。 香农-范诺编码不应该与香农编码混淆,后者的编码方法用于证明Shannon's noiseless coding theorem,或与Shannon–Fano–Elias coding(又被称作Elias coding)一起,被看做算术编码的先驱。 香农-范诺编码,符号从最大可能到最少可能排序,将排列好的信源符号分化为两大组,使两组的概率和近于相同,并各赋予一个二元码符号“0”和“1”。只要有符号剩余,以同样的过程重复这些集合以此确定这些代码的连续编码数字。依次下去,直至每一组的只剩下一个信源符号为止。当一组已经降低到一个符号,显然,这意味着符号的代码是完整的,不会形成任何其他符号的代码前缀。 这是一个行之有效的算法,它会产生相当有效的可变长度编码;当两个较小的集生产分区其实是相等的概率,一位用于区分它们的信息是最有效的使用。不幸的是,香农 - 法诺并不总是产生最优的前缀码:概率是一个将分配非优化代码的Shannon-Fano的编码的一个例子。 出于这个原因,香农 - 范诺几乎从不使用; 哈夫曼编码几乎是计算简单,生产总是达到预期最低的码字长度的制约下,每个符号是由一个整数组成一个代码代表的前缀码。这往往是不必要的,因为代码将装在首尾相连的长序列的里。如果我们认为一次的代码组,象征符号的哈夫曼编码是唯一的最佳符号的概率统计独立|独立和一些半功率,即,为\textstyle \frac。在大多数情况下,可以产生比哈夫曼或的香农-范诺更大的整体压缩,因为它可以在小数位编码,这更接近实际的符号信息内容。然而,算术编码并没有取代像霍夫曼取代的香农-范诺一样取代哈夫曼,一方面是因为算术编码的计算成本的方式,因为它是由多个专利覆盖。香农:范诺编码被用在爆聚压缩方法.

7 关系: 克劳德·香农前置碼算术编码羅伯特·法諾霍夫曼编码概率数据压缩

克劳德·香农

克劳德·艾尔伍德·香农(Claude Elwood Shannon,),美国数学家、电子工程师和密码学家,被誉为信息论的创始人。 香农是密西根大學學士,麻省理工學院博士。 1948年,香农发表了划时代的论文——通信的数学原理,奠定了现代信息论的基础。不仅如此,香农还被认为是数字计算机理论和数字电路设计理论的创始人。1937年,21岁的香农是麻省理工學院的硕士研究生,他在其硕士论文中提出,将布尔代数应用于电子领域,能够构建并解决任何逻辑和数值关系,被誉为有史以来最具水平的硕士论文之一。二战期间,香农为军事领域的密码分析——密码破译和保密通信——做出了很大贡献。.

新!!: 香农-范诺编码和克劳德·香农 · 查看更多 »

前置碼

前置碼(Prefix code),又譯前綴碼,是一種編碼系統。這種編碼系統通常是可變長度碼,在其中的每個碼字,都具備「前置性質」(prefix property),也就是說,在編碼中的每個碼字,都不能被其他碼字當成前置部位。舉例而言,編碼字 具備了前置性質,但編碼字就不具備,因為其中的"5",是"59"及"55"的前置字。這也被稱為無首碼的代碼(prefix-free codes,PFC,無前綴碼)。 Category:编码理论 Category:前綴 Category:数据压缩 Category:无损压缩算法.

新!!: 香农-范诺编码和前置碼 · 查看更多 »

算术编码

算术编码是一种无损数据压缩方法,也是一种熵编码的方法。和其它熵编码方法不同的地方在于,其他的熵编码方法通常是把输入的消息分割为符号,然后对每个符号进行编码,而算术编码是直接把整个输入的消息编码为一个数,一个满足(0.0 ≤ n.

新!!: 香农-范诺编码和算术编码 · 查看更多 »

羅伯特·法諾

羅伯特·馬利歐·法諾(Robert Mario Fano,),本名羅貝托·馬利歐·法諾(Roberto Mario Fano),生於義大利都靈,義裔美籍計算機科學家,為麻省理工學院電機工程與計算機科學榮譽教授。專長於資訊理論,曾與克劳德·香农共同開發出香农-范诺编码,並曾提出。.

新!!: 香农-范诺编码和羅伯特·法諾 · 查看更多 »

霍夫曼编码

霍夫曼編碼(Huffman Coding),又譯為哈夫曼编码、赫夫曼编码,是一種用於无损数据压缩的熵編碼(權編碼)演算法。由美國計算機科學家大衛·霍夫曼(David Albert Huffman)在1952年發明。.

新!!: 香农-范诺编码和霍夫曼编码 · 查看更多 »

概率

--率,舊稱--率,又称或然率、機會率或--、可能性,是数学概率论的基本概念,是一个在0到1之间的实数,是对随机事件发生之可能性的度量。 概率常用來量化對於某些不確定命題的想法"Kendall's Advanced Theory of Statistics, Volume 1: Distribution Theory", Alan Stuart and Keith Ord, 6th Ed, (2009), ISBN 978-0-534-24312-8,命題一般會是以下的形式:「某個特定事件會發生嗎?」,對應的想法則是:「我們可以多確定這個事件會發生?」。確定的程度可以用0到1之間的數值來表示,這個數值就是機率William Feller, "An Introduction to Probability Theory and Its Applications", (Vol 1), 3rd Ed, (1968),Wiley,ISBN 978-0-471-25708-0。因此若事件發生的機率越高,表示我們越認為這個事件可能發生。像丟銅板就是一個簡單的例子,正面朝上及背面朝上的兩種結果看來機率相同,每個的機率都是1/2,也就是正面朝上及背面朝上的機率各有50%。 這些概念可以形成機率論中的數學公理(參考概率公理),在像數學、統計學、金融、博弈論、科學(特別是物理)、人工智慧/機器學習、電腦科學及哲學等學科中都會用到。機率論也可以描述複雜系統中的內在機制及規律性。.

新!!: 香农-范诺编码和概率 · 查看更多 »

数据压缩

在计算机科学和信息论中,数据压缩或者源编码是按照特定的编码机制用比未经编码少的数据位元(或者其它信息相关的单位)表示信息的过程。例如,如果我们将「compression」编码为「comp」那么这篇文章可以用较少的数据位表示。常見的例子是ZIP文件格式,此格式不仅仅提供压缩功能,还可作为归档工具(Archiver),能够将许多文件存储到同一个文件中。.

新!!: 香农-范诺编码和数据压缩 · 查看更多 »

传出传入
嘿!我们在Facebook上吧! »