[{"@context":"http:\/\/schema.org\/","@type":"BlogPosting","@id":"https:\/\/wiki.edu.vn\/en\/wiki24\/tunstall-coding-wikipedia\/#BlogPosting","mainEntityOfPage":"https:\/\/wiki.edu.vn\/en\/wiki24\/tunstall-coding-wikipedia\/","headline":"Tunstall coding – Wikipedia","name":"Tunstall coding – Wikipedia","description":"From Wikipedia, the free encyclopedia In computer science and information theory, Tunstall coding is a form of entropy coding used","datePublished":"2016-08-19","dateModified":"2016-08-19","author":{"@type":"Person","@id":"https:\/\/wiki.edu.vn\/en\/wiki24\/author\/lordneo\/#Person","name":"lordneo","url":"https:\/\/wiki.edu.vn\/en\/wiki24\/author\/lordneo\/","image":{"@type":"ImageObject","@id":"https:\/\/secure.gravatar.com\/avatar\/c9645c498c9701c88b89b8537773dd7c?s=96&d=mm&r=g","url":"https:\/\/secure.gravatar.com\/avatar\/c9645c498c9701c88b89b8537773dd7c?s=96&d=mm&r=g","height":96,"width":96}},"publisher":{"@type":"Organization","name":"Enzyklop\u00e4die","logo":{"@type":"ImageObject","@id":"https:\/\/wiki.edu.vn\/wiki4\/wp-content\/uploads\/2023\/08\/download.jpg","url":"https:\/\/wiki.edu.vn\/wiki4\/wp-content\/uploads\/2023\/08\/download.jpg","width":600,"height":60}},"image":{"@type":"ImageObject","@id":"https:\/\/wikimedia.org\/api\/rest_v1\/media\/math\/render\/svg\/c1ba2895d1e423f0d6850a388eba7f3f191556d4","url":"https:\/\/wikimedia.org\/api\/rest_v1\/media\/math\/render\/svg\/c1ba2895d1e423f0d6850a388eba7f3f191556d4","height":"","width":""},"url":"https:\/\/wiki.edu.vn\/en\/wiki24\/tunstall-coding-wikipedia\/","wordCount":2736,"articleBody":"From Wikipedia, the free encyclopediaIn computer science and information theory, Tunstall coding is a form of entropy coding used for lossless data compression.Table of ContentsHistory[edit]Properties[edit]Algorithm[edit]Example[edit]Limitations[edit]References[edit]History[edit]Tunstall coding was the subject of Brian Parker Tunstall’s PhD thesis in 1967, while at Georgia Institute of Technology. The subject of that thesis was “Synthesis of noiseless compression codes” [1]Its design is a precursor to Lempel\u2013Ziv.Properties[edit]Unlike variable-length codes, which include Huffman and Lempel\u2013Ziv coding,Tunstall coding is a code which maps source symbols to a fixed number of bits.[2]Both Tunstall codes and Lempel\u2013Ziv codes represent variable-length words by fixed-length codes.[3]Unlike typical set encoding, Tunstall coding parses a stochastic source with codewords of variable length.It can be shown[4]that, for a large enough dictionary, the number of bits per source letter can be arbitrarily close to H(U){displaystyle H(U)}, the entropy of the source.Algorithm[edit]The algorithm requires as input an input alphabet U{displaystyle {mathcal {U}}}, along with a distribution of probabilities for each word input.It also requires an arbitrary constant C{displaystyle C}, which is an upper bound to the size of the dictionary that it will compute.The dictionary in question, D{displaystyle D}, is constructed as a tree of probabilities, in which each edge is associated to a letter from the input alphabet.The algorithm goes like this:D\u00a0:= tree of |U|{displaystyle |{mathcal {U}}|} leaves, one for each letter in U{displaystyle {mathcal {U}}}.While |D|(9)\u2309=4{displaystyle lceil log _{2}(9)rceil =4} bits.We then take the leaf of highest probability (here, w1{displaystyle w_{1}}), and convert it to yet another tree of |U|=9{displaystyle |{mathcal {U}}|=9} leaves, one for each character.We re-compute the probabilities of those leaves. For instance, the sequence of two letters L happens once.Given that there are three occurrences of letters followed by an L, the resulting probability is 13\u22c5312=112{displaystyle {1 over 3}cdot {3 over 12}={1 over 12}}.We obtain 17 words, which can each be encoded into a fixed-sized output of \u2308log2\u2061(17)\u2309=5{displaystyle lceil log _{2}(17)rceil =5} bits.Note that we could iterate further, increasing the number of words by |U|\u22121=8{displaystyle |{mathcal {U}}|-1=8} every time.Limitations[edit]Tunstall coding requires the algorithm to know, prior to the parsing operation, what the distribution of probabilities for each letter of the alphabet is.This issue is shared with Huffman coding.Its requiring a fixed-length block output makes it lesser than Lempel\u2013Ziv, which has a similar dictionary-based design, but with a variable-sized block output.[clarification needed]References[edit]  "},{"@context":"http:\/\/schema.org\/","@type":"BreadcrumbList","itemListElement":[{"@type":"ListItem","position":1,"item":{"@id":"https:\/\/wiki.edu.vn\/en\/wiki24\/#breadcrumbitem","name":"Enzyklop\u00e4die"}},{"@type":"ListItem","position":2,"item":{"@id":"https:\/\/wiki.edu.vn\/en\/wiki24\/tunstall-coding-wikipedia\/#breadcrumbitem","name":"Tunstall coding – Wikipedia"}}]}]