8000 swift-algorithm-club/Huffman Coding at master · rreballos/swift-algorithm-club · GitHub
[go: up one dir, main page]
Skip to content
{"payload":{"allShortcutsEnabled":false,"path":"Huffman Coding","repo":{"id":245351143,"defaultBranch":"master","name":"swift-algorithm-club","ownerLogin":"rreballos","currentUserCanPush":false,"isFork":true,"isEmpty":false,"createdAt":"2020-03-06T06:59:16.000Z","ownerAvatar":"https://avatars.githubusercontent.com/u/1049202?v=4","public":true,"private":false,"isOrgOwned":false},"currentUser":null,"refInfo":{"name":"master","listCacheKey":"v0:1615943933.75875","canEdit":false,"refType":"branch","currentOid":"c22182f0d0b7708380a152640401fe873a705c20"},"tree":{"items":[{"name":"Huffman.playground","path":"Huffman Coding/Huffman.playground","contentType":"directory"},{"name":"Images","path":"Huffman Coding/Images","contentType":"directory"},{"name":"Huffman.swift","path":"Huffman Coding/Huffman.swift","contentType":"file"},{"name":"NSData+Bits.swift","path":"Huffman Coding/NSData+Bits.swift","contentType":"file"},{"name":"README.markdown","path":"Huffman Coding/README.markdown","contentType":"file"}],"templateDirectorySuggestionUrl":null,"readme":{"displayName":"README.markdown","richText":"\u003carticle class=\"markdown-body entry-content container-lg\" itemprop=\"text\"\u003e\u003cdiv class=\"markdown-heading\" dir=\"auto\"\u003e\u003ch1 tabindex=\"-1\" class=\"heading-element\" dir=\"auto\"\u003eHuffman Coding\u003c/h1\u003e\u003ca id=\"user-content-huffman-coding\" class=\"anchor\" aria-label=\"Permalink: Huffman Coding\" href=\"#huffman-coding\"\u003e\u003csvg class=\"octicon octicon-link\" viewBox=\"0 0 16 16\" version=\"1.1\" width=\"16\" height=\"16\" aria-hidden=\"true\"\u003e\u003cpath d=\"m7.775 3.275 1.25-1.25a3.5 3.5 0 1 1 4.95 4.95l-2.5 2.5a3.5 3.5 0 0 1-4.95 0 .751.751 0 0 1 .018-1.042.751.751 0 0 1 1.042-.018 1.998 1.998 0 0 0 2.83 0l2.5-2.5a2.002 2.002 0 0 0-2.83-2.83l-1.25 1.25a.751.751 0 0 1-1.042-.018.751.751 0 0 1-.018-1.042Zm-4.69 9.64a1.998 1.998 0 0 0 2.83 0l1.25-1.25a.751.751 0 0 1 1.042.018.751.751 0 0 1 .018 1.042l-1.25 1.25a3.5 3.5 0 1 1-4.95-4.95l2.5-2.5a3.5 3.5 0 0 1 4.95 0 .751.751 0 0 1-.018 1.042.751.751 0 0 1-1.042.018 1.998 1.998 0 0 0-2.83 0l-2.5 2.5a1.998 1.998 0 0 0 0 2.83Z\"\u003e\u003c/path\u003e\u003c/svg\u003e\u003c/a\u003e\u003c/div\u003e\n\u003cp dir=\"auto\"\u003eThe idea: To encode objects that occur often with a smaller number of bits than objects that occur less frequently.\u003c/p\u003e\n\u003cp dir=\"auto\"\u003eAlthough any type of objects can be encoded with this scheme, it is common to compress a stream of bytes. Suppose you have the following text, where each character is one byte:\u003c/p\u003e\n\u003cdiv class=\"snippet-clipboard-content notranslate position-relative overflow-auto\" data-snippet-clipboard-copy-content=\"so much words wow many compression\"\u003e\u003cpre class=\"notranslate\"\u003e\u003ccode\u003eso much words wow many compression\n\u003c/code\u003e\u003c/pre\u003e\u003c/div\u003e\n\u003cp dir=\"auto\"\u003eIf you count how often each byte appears, you can see some bytes occur more than others:\u003c/p\u003e\n\u003cdiv class=\"snippet-clipboard-content notranslate position-relative overflow-auto\" data-snippet-clipboard-copy-content=\"space: 5 u: 1\n o: 5 h: 1\n s: 4 d: 1\n m: 3 a: 1\n w: 3 y: 1\n c: 2 p: 1\n r: 2 e: 1\n n: 2 i: 1\"\u003e\u003cpre class=\"notranslate\"\u003e\u003ccode\u003espace: 5 u: 1\n o: 5 h: 1\n s: 4 d: 1\n m: 3 a: 1\n w: 3 y: 1\n c: 2 p: 1\n r: 2 e: 1\n n: 2 i: 1\n\u003c/code\u003e\u003c/pre\u003e\u003c/div\u003e\n\u003cp dir=\"auto\"\u003eWe can assign bit strings to each of these bytes. The more common a byte is, the fewer bits we assign to it. We might get something like this:\u003c/p\u003e\n\u003cdiv class=\"snippet-clipboard-content notranslate position-relative overflow-auto\" data-snippet-clipboard-copy-content=\"space: 5 010 u: 1 11001\n o: 5 000\t h: 1 10001\n s: 4 101\t d: 1 11010\n m: 3 111\t a: 1 11011\n w: 3 0010 y: 1 01111\n c: 2 0011 p: 1 11000\n r: 2 1001 e: 1 01110\n n: 2 0110 i: 1 10000\"\u003e\u003cpre class=\"notranslate\"\u003e\u003ccode\u003espace: 5 010 u: 1 11001\n o: 5 000\t h: 1 10001\n s: 4 101\t d: 1 11010\n m: 3 111\t a: 1 11011\n w: 3 0010 y: 1 01111\n c: 2 0011 p: 1 11000\n r: 2 1001 e: 1 01110\n n: 2 0110 i: 1 10000\n\u003c/code\u003e\u003c/pre\u003e\u003c/div\u003e\n\u003cp dir=\"auto\"\u003eNow if we replace the original bytes with these bit strings, the compressed output becomes:\u003c/p\u003e\n\u003cdiv class=\"snippet-clipboard-content notranslate position-relative overflow-auto\" data-snippet-clipboard-copy-content=\"101 000 010 111 11001 0011 10001 010 0010 000 1001 11010 101\ns o _ m u c h _ w o r d s\n\n010 0010 000 0010 010 111 11011 0110 01111 010 0011 000 111\n_ w o w _ m a n y _ c o m\n\n11000 1001 01110 101 101 10000 000 0110 0\np r e s s i o n\"\u003e\u003cpre class=\"notranslate\"\u003e\u003ccode\u003e101 000 010 111 11001 0011 10001 010 0010 000 1001 11010 101\ns o _ m u c h _ w o r d s\n\n010 0010 000 0010 010 111 11011 0110 01111 010 0011 000 111\n_ w o w _ m a n y _ c o m\n\n11000 1001 01110 101 101 10000 000 0110 0\np r e s s i o n\n\u003c/code\u003e\u003c/pre\u003e\u003c/div\u003e\n\u003cp dir=\"auto\"\u003eThe extra 0-bit at the end is there to make a full number of bytes. We were able to compress the original 34 bytes into merely 16 bytes, a space savings of over 50%!\u003c/p\u003e\n\u003cp dir=\"auto\"\u003eTo be able to decode these bits, we need to have the original frequency table. That table needs to be transmitted or saved along with the compressed data. Otherwise, the decoder does not know how to interpret the bits. Because of the overhead of this frequency table (about 1 kilobyte), it is not beneficial to use Huffman encoding on small inputs.\u003c/p\u003e\n\u003cdiv class=\"markdown-heading\" dir=\"auto\"\u003e\u003ch2 tabindex=\"-1\" class=\"heading-element\" dir=\"auto\"\u003eHow it works\u003c/h2\u003e\u003ca id=\"user-content-how-it-works\" class=\"anchor\" aria-label=\"Permalink: How it works\" href=\"#how-it-works\"\u003e\u003csvg class=\"octicon octicon-link\" viewBox=\"0 0 16 16\" version=\"1.1\" width=\"16\" height=\"16\" aria-hidden=\"true\"\u003e\u003cpath d=\"m7.775 3.275 1.25-1.25a3.5 3.5 0 1 1 4.95 4.95l-2.5 2.5a3.5 3.5 0 0 1-4.95 0 .751.751 0 0 1 .018-1.042.751.751 0 0 1 1.042-.018 1.998 1.998 0 0 0 2.83 0l2.5-2.5a2.002 2.002 0 0 0-2.83-2.83l-1.25 1.25a.751.751 0 0 1-1.042-.018.751.751 0 0 1-.018-1.042Zm-4.69 9.64a1.998 1.998 0 0 0 2.83 0l1.25-1.25a.751.751 0 0 1 1.042.018.751.751 0 0 1 .018 1.042l-1.25 1.25a3.5 3.5 0 1 1-4.95-4.95l2.5-2.5a3.5 3.5 0 0 1 4.95 0 .751.751 0 0 1-.018 1.042.751.751 0 0 1-1.042.018 1.998 1.998 0 0 0-2.83 0l-2.5 2.5a1.998 1.998 0 0 0 0 2.83Z\"\u003e\u003c/path\u003e\u003c/svg\u003e\u003c/a\u003e\u003c/div\u003e\n\u003cp dir=\"auto\"\u003eWhen compressing a stream of bytes, the algorithm first creates a frequency table that counts how often each byte occurs. Based on this table, the algorithm creates a binary tree that describes the bit strings for each of the input bytes.\u003c/p\u003e\n\u003cp dir=\"auto\"\u003eFor our example, the tree looks like this:\u003c/p\u003e\n\u003cp dir=\"auto\"\u003e\u003ca target=\"_blank\" rel=\"noopener noreferrer\" href=\"/rreballos/swift-algorithm-club/blob/master/Huffman%20Coding/Images/Tree.png\"\u003e\u003cimg src=\"/rreballos/swift-algorithm-club/raw/master/Huffman%20Coding/Images/Tree.png\" alt=\"The compression tree\" style=\"max-width: 100%;\"\u003e\u003c/a\u003e\u003c/p\u003e\n\u003cp dir=\"auto\"\u003eNote that the tree has 16 leaf nodes (the grey ones), one for each byte value from the input. Each leaf node also shows the count of how often it occurs. The other nodes are \"intermediate\" nodes. The number shown in these nodes is the sum of the counts of their child nodes. The count of the root node is therefore the total number of bytes in the input.\u003c/p\u003e\n\u003cp dir=\"auto\"\u003eThe edges between the nodes are either \"1\" or \"0\". These correspond to the bit-encodings of the leaf nodes. Notice how each left branch is always 1 and each right branch is always 0.\u003c/p\u003e\n\u003cp dir=\"auto\"\u003eCompression is then a matter of looping through the input bytes and for each byte traversing the tree from the root node to that byte's leaf node. Every time we take a left branch, we emit a 1-bit. When we take a right branch, we emit a 0-bit.\u003c/p\u003e\n\u003cp dir=\"auto\"\u003eFor example, to go from the root node to \u003ccode\u003ec\u003c/code\u003e, we go right (\u003ccode\u003e0\u003c/code\u003e), right again (\u003ccode\u003e0\u003c/code\u003e), left (\u003ccode\u003e1\u003c/code\u003e), and left again (\u003ccode\u003e1\u003c/code\u003e). This gives the Huffman code as \u003ccode\u003e0011\u003c/code\u003e for \u003ccode\u003ec\u003c/code\u003e.\u003c/p\u003e\n\u003cp dir=\"auto\"\u003eDecompression works in exactly the opposite way. It reads the compressed bits one-by-one and traverses the tree until it reaches to a leaf node. The value of that leaf node is the uncompressed byte. For example, if the bits are \u003ccode\u003e11010\u003c/code\u003e, we start at the root and go left, left again, right, left, and a final right to end up at \u003ccode\u003ed\u003c/code\u003e.\u003c/p\u003e\n\u003cdiv class=\"markdown-heading\" dir=\"auto\"\u003e\u003ch2 tabindex=\"-1\" class=\"heading-element\" dir=\"auto\"\u003eThe code\u003c/h2\u003e\u003ca id=\"user-content-the-code\" class=\"anchor\" aria-label=\"Permalink: The code\" href=\"#the-code\"\u003e\u003csvg class=\"octicon octicon-link\" viewBox=\"0 0 16 16\" version=\"1.1\" width=\"16\" height=\"16\" aria-hidden=\"true\"\u003e\u003cpath d=\"m7.775 3.275 1.25-1.25a3.5 3.5 0 1 1 4.95 4.95l-2.5 2.5a3.5 3.5 0 0 1-4.95 0 .751.751 0 0 1 .018-1.042.751.751 0 0 1 1.042-.018 1.998 1.998 0 0 0 2.83 0l2.5-2.5a2.002 2.002 0 0 0-2.83-2.83l-1.25 1.25a.751.751 0 0 1-1.042-.018.751.751 0 0 1-.018-1.042Zm-4.69 9.64a1.998 1.998 0 0 0 2.83 0l1.25-1.25a.751.751 0 0 1 1.042.018.751.751 0 0 1 .018 1.042l-1.25 1.25a3.5 3.5 0 1 1-4.95-4.95l2.5-2.5a3.5 3.5 0 0 1 4.95 0 .751.751 0 0 1-.018 1.042.751.751 0 0 1-1.042.018 1.998 1.998 0 0 0-2.83 0l-2.5 2.5a1.998 1.998 0 0 0 0 2.83Z\"\u003e\u003c/path\u003e\u003c/svg\u003e\u003c/a\u003e\u003c/div\u003e\n\u003cp dir=\"auto\"\u003eBefore we get to the actual Huffman coding scheme, it is useful to have some helper code that can write individual bits to an \u003ccode\u003eNSData\u003c/code\u003e object. The smallest piece of data that \u003ccode\u003eNSData\u003c/code\u003e understands is the byte, but we are dealing in bits, so we need to translate between the two.\u003c/p\u003e\n\u003cdiv class=\"highlight highlight-source-swift notranslate position-relative overflow-auto\" dir=\"auto\" data-snippet-clipboard-copy-content=\"public class BitWriter {\n public var data = NSMutableData()\n var outByte: UInt8 = 0\n var outCount = 0\n\n public func writeBit(bit: Bool) {\n if outCount == 8 {\n data.append(\u0026amp;outByte, length: 1)\n outCount = 0\n }\n outByte = (outByte \u0026lt;\u0026lt; 1) | (bit ? 1 : 0)\n outCount += 1\n }\n\n public func flush() {\n if outCount \u0026gt; 0 {\n if outCount \u0026lt; 8 {\n let diff = UInt8(8 - outCount)\n outByte \u0026lt;\u0026lt;= diff\n }\n data.append(\u0026amp;outByte, length: 1)\n }\n }\n}\"\u003e\u003cpre\u003e\u003cspan class=\"pl-k\"\u003epublic\u003c/span\u003e \u003cspan class=\"pl-k\"\u003eclass\u003c/span\u003e \u003cspan class=\"pl-smi\"\u003eBitWriter\u003c/span\u003e \u003cspan class=\"pl-kos\"\u003e{\u003c/span\u003e\n \u003cspan class=\"pl-k\"\u003epublic\u003c/span\u003e \u003cspan class=\"pl-k\"\u003evar\u003c/span\u003e \u003cspan class=\"pl-s1\"\u003e\u003cspan class=\"pl-c1\"\u003edata\u003c/span\u003e\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003e=\u003c/span\u003e \u003cspan class=\"pl-en\"\u003eNSMutableData\u003c/span\u003e\u003cspan class=\"pl-kos\"\u003e(\u003c/span\u003e\u003cspan class=\"pl-kos\"\u003e)\u003c/span\u003e\n \u003cspan class=\"pl-k\"\u003evar\u003c/span\u003e \u003cspan class=\"pl-s1\"\u003e\u003cspan class=\"pl-c1\"\u003eoutByte\u003c/span\u003e\u003c/span\u003e\u003cspan class=\"pl-kos\"\u003e:\u003c/span\u003e \u003cspan class=\"pl-smi\"\u003eUInt8\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003e=\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003e0\u003c/span\u003e\n \u003cspan class=\"pl-k\"\u003evar\u003c/span\u003e \u003cspan class=\"pl-s1\"\u003e\u003cspan class=\"pl-c1\"\u003eoutCount\u003c/span\u003e\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003e=\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003e0\u003c/span\u003e\n\n \u003cspan class=\"pl-k\"\u003epublic\u003c/span\u003e \u003cspan class=\"pl-en\"\u003efunc\u003c/span\u003e writeBit\u003cspan class=\"pl-kos\"\u003e(\u003c/span\u003ebit\u003cspan class=\"pl-kos\"\u003e:\u003c/span\u003e \u003cspan class=\"pl-smi\"\u003eBool\u003c/span\u003e\u003cspan class=\"pl-kos\"\u003e)\u003c/span\u003e \u003cspan class=\"pl-kos\"\u003e{\u003c/span\u003e\n \u003cspan class=\"pl-k\"\u003eif\u003c/span\u003e outCount \u003cspan class=\"pl-c1\"\u003e==\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003e8\u003c/span\u003e \u003cspan class=\"pl-kos\"\u003e{\u003c/span\u003e\n data\u003cspan class=\"pl-kos\"\u003e.\u003c/span\u003e\u003cspan class=\"pl-en\"\u003eappend\u003c/span\u003e\u003cspan class=\"pl-kos\"\u003e(\u003c/span\u003e\u003cspan class=\"pl-c1\"\u003e\u0026amp;\u003c/span\u003eoutByte\u003cspan class=\"pl-kos\"\u003e,\u003c/span\u003e length\u003cspan class=\"pl-kos\"\u003e:\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003e1\u003c/span\u003e\u003cspan class=\"pl-kos\"\u003e)\u003c/span\u003e\n outCount \u003cspan class=\"pl-c1\"\u003e=\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003e0\u003c/span\u003e\n \u003cspan class=\"pl-kos\"\u003e}\u003c/span\u003e\n outByte \u003cspan class=\"pl-c1\"\u003e=\u003c/span\u003e \u003cspan class=\"pl-kos\"\u003e(\u003c/span\u003eoutByte \u0026lt;\u0026lt; \u003cspan class=\"pl-c1\"\u003e1\u003c/span\u003e\u003cspan class=\"pl-kos\"\u003e)\u003c/span\u003e | \u003cspan class=\"pl-kos\"\u003e(\u003c/span\u003ebit \u003cspan class=\"pl-c1\"\u003e?\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003e1\u003c/span\u003e \u003cspan class=\"pl-k\"\u003e:\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003e0\u003c/span\u003e\u003cspan class=\"pl-kos\"\u003e)\u003c/span\u003e\n outCount \u003cspan class=\"pl-c1\"\u003e+=\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003e1\u003c/span\u003e\n \u003cspan class=\"pl-kos\"\u003e}\u003c/span\u003e\n\n \u003cspan class=\"pl-k\"\u003epublic\u003c/span\u003e \u003cspan class=\"pl-en\"\u003efunc\u003c/span\u003e flush\u003cspan class=\"pl-kos\"\u003e(\u003c/span\u003e\u003cspan class=\"pl-kos\"\u003e)\u003c/span\u003e \u003cspan class=\"pl-kos\"\u003e{\u003c/span\u003e\n \u003cspan class=\"pl-k\"\u003eif\u003c/span\u003e outCount \u003cspan class=\"pl-c1\"\u003e\u0026gt;\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003e0\u003c/span\u003e \u003cspan class=\"pl-kos\"\u003e{\u003c/span\u003e\n \u003cspan class=\"pl-k\"\u003eif\u003c/span\u003e outCount \u003cspan class=\"pl-c1\"\u003e\u0026lt;\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003e8\u003c/span\u003e \u003cspan class=\"pl-kos\"\u003e{\u003c/span\u003e\n \u003cspan class=\"pl-k\"\u003elet\u003c/span\u003e \u003cspan class=\"pl-s1\"\u003ediff\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003e=\u003c/span\u003e \u003cspan class=\"pl-en\"\u003eUInt8\u003c/span\u003e\u003cspan class=\"pl-kos\"\u003e(\u003c/span\u003e\u003cspan class=\"pl-c1\"\u003e8\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003e-\u003c/span\u003e outCount\u003cspan class=\"pl-kos\"\u003e)\u003c/span\u003e\n outByte \u003cspan class=\"pl-c1\"\u003e\u0026lt;\u0026lt;=\u003c/span\u003e diff\n \u003cspan class=\"pl-kos\"\u003e}\u003c/span\u003e\n data\u003cspan class=\"pl-kos\"\u003e.\u003c/span\u003e\u003cspan class=\"pl-en\"\u003eappend\u003c/span\u003e\u003cspan class=\"pl-kos\"\u003e(\u003c/span\u003e\u003cspan class=\"pl-c1\"\u003e\u0026amp;\u003c/span\u003eoutByte\u003cspan class=\"pl-kos\"\u003e,\u003c/span\u003e length\u003cspan class=\"pl-kos\"\u003e:\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003e1\u003c/span\u003e\u003cspan class=\"pl-kos\"\u003e)\u003c/span\u003e\n \u003cspan class=\"pl-kos\"\u003e}\u003c/span\u003e\n \u003cspan class=\"pl-kos\"\u003e}\u003c/span\u003e\n\u003cspan class=\"pl-kos\"\u003e}\u003c/span\u003e\u003c/pre\u003e\u003c/div\u003e\n\u003cp dir=\"auto\"\u003eTo add a bit to the \u003ccode\u003eNSData\u003c/code\u003e, you can call \u003ccode\u003ewriteBit()\u003c/code\u003e. This helper object stuffs each new bit into the \u003ccode\u003eoutByte\u003c/code\u003e variable. Once you have written 8 bits, \u003ccode\u003eoutByte\u003c/code\u003e gets added to the \u003ccode\u003eNSData\u003c/code\u003e object for real.\u003c/p\u003e\n\u003cp dir=\"auto\"\u003eThe \u003ccode\u003eflush()\u003c/code\u003e method is used for outputting the very last byte. There is no guarantee that the number of compressed bits is a nice round multiple of 8, in which case there may be some spare bits at the end. If so, \u003ccode\u003eflush()\u003c/code\u003e adds a few 0-bits to make sure that we write a full byte.\u003c/p\u003e\n\u003cp dir=\"auto\"\u003eHere is a similar helper object for reading individual bits from \u003ccode\u003eNSData\u003c/code\u003e:\u003c/p\u003e\n\u003cdiv class=\"highlight highlight-source-swift notranslate position-relative overflow-auto\" dir=\"auto\" data-snippet-clipboard-copy-content=\"public class BitReader {\n var ptr: UnsafePointer\u0026lt;UInt8\u0026gt;\n var inByte: UInt8 = 0\n var inCount = 8\n\n public init(data: NSData) {\n ptr = data.bytes.assumingMemoryBound(to: UInt8.self)\n }\n\n public func readBit() -\u0026gt; Bool {\n if inCount == 8 {\n inByte = ptr.pointee // load the next byte\n inCount = 0\n ptr = ptr.successor()\n }\n let bit = inByte \u0026amp; 0x80 // read the next bit\n inByte \u0026lt;\u0026lt;= 1\n inCount += 1\n return bit == 0 ? false : true\n }\n}\"\u003e\u003cpre\u003e\u003cspan class=\"pl-k\"\u003epublic\u003c/span\u003e \u003cspan class=\"pl-k\"\u003eclass\u003c/span\u003e \u003cspan class=\"pl-smi\"\u003eBitReader\u003c/span\u003e \u003cspan class=\"pl-kos\"\u003e{\u003c/span\u003e\n \u003cspan class=\"pl-k\"\u003evar\u003c/span\u003e \u003cspan class=\"pl-s1\"\u003e\u003cspan class=\"pl-c1\"\u003eptr\u003c/span\u003e\u003c/span\u003e\u003cspan class=\"pl-kos\"\u003e:\u003c/span\u003e \u003cspan class=\"pl-smi\"\u003eUnsafePointer\u003c/span\u003e\u003cspan class=\"pl-c1\"\u003e\u0026lt;\u003c/span\u003e\u003cspan class=\"pl-smi\"\u003eUInt8\u003c/span\u003e\u003cspan class=\"pl-c1\"\u003e\u0026gt;\u003c/span\u003e\n \u003cspan class=\"pl-k\"\u003evar\u003c/span\u003e \u003cspan class=\"pl-s1\"\u003e\u003cspan class=\"pl-c1\"\u003einByte\u003c/span\u003e\u003c/span\u003e\u003cspan class=\"pl-kos\"\u003e:\u003c/span\u003e \u003cspan class=\"pl-smi\"\u003eUInt8\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003e=\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003e0\u003c/span\u003e\n \u003cspan class=\"pl-k\"\u003evar\u003c/span\u003e \u003cspan class=\"pl-s1\"\u003e\u003cspan class=\"pl-c1\"\u003einCount\u003c/span\u003e\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003e=\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003e8\u003c/span\u003e\n\n \u003cspan class=\"pl-k\"\u003epublic\u003c/span\u003e \u003cspan class=\"pl-v\"\u003einit\u003c/span\u003e\u003cspan class=\"pl-kos\"\u003e(\u003c/span\u003edata\u003cspan class=\"pl-kos\"\u003e:\u003c/span\u003e \u003cspan class=\"pl-smi\"\u003eNSData\u003c/span\u003e\u003cspan class=\"pl-kos\"\u003e)\u003c/span\u003e \u003cspan class=\"pl-kos\"\u003e{\u003c/span\u003e\n ptr \u003cspan class=\"pl-c1\"\u003e=\u003c/span\u003e data\u003cspan class=\"pl-kos\"\u003e.\u003c/span\u003ebytes\u003cspan class=\"pl-kos\"\u003e.\u003c/span\u003e\u003cspan class=\"pl-en\"\u003eassumingMemoryBound\u003c/span\u003e\u003cspan class=\"pl-kos\"\u003e(\u003c/span\u003eto\u003cspan class=\"pl-kos\"\u003e:\u003c/span\u003e \u003cspan class=\"pl-smi\"\u003eUInt8\u003c/span\u003e\u003cspan class=\"pl-kos\"\u003e.\u003c/span\u003eself\u003cspan class=\"pl-kos\"\u003e)\u003c/span\u003e\n \u003cspan class=\"pl-kos\"\u003e}\u003c/span\u003e\n\n \u003cspan class=\"pl-k\"\u003epublic\u003c/span\u003e \u003cspan class=\"pl-en\"\u003efunc\u003c/span\u003e readBit\u003cspan class=\"pl-kos\"\u003e(\u003c/span\u003e\u003cspan class=\"pl-kos\"\u003e)\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003e-\u0026gt;\u003c/span\u003e \u003cspan class=\"pl-smi\"\u003eBool\u003c/span\u003e \u003cspan class=\"pl-kos\"\u003e{\u003c/span\u003e\n \u003cspan class=\"pl-k\"\u003eif\u003c/span\u003e inCount \u003cspan class=\"pl-c1\"\u003e==\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003e8\u003c/span\u003e \u003cspan class=\"pl-kos\"\u003e{\u003c/span\u003e\n inByte \u003cspan class=\"pl-c1\"\u003e=\u003c/span\u003e ptr\u003cspan class=\"pl-kos\"\u003e.\u003c/span\u003epointee // load the next byte\n inCount \u003cspan class=\"pl-c1\"\u003e=\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003e0\u003c/span\u003e\n ptr \u003cspan class=\"pl-c1\"\u003e=\u003c/span\u003e ptr\u003cspan class=\"pl-kos\"\u003e.\u003c/span\u003e\u003cspan class=\"pl-en\"\u003esuccessor\u003c/span\u003e\u003cspan class=\"pl-kos\"\u003e(\u003c/span\u003e\u003cspan class=\"pl-kos\"\u003e)\u003c/span\u003e\n \u003cspan class=\"pl-kos\"\u003e}\u003c/span\u003e\n \u003cspan class=\"pl-k\"\u003elet\u003c/span\u003e \u003cspan class=\"pl-s1\"\u003ebit\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003e=\u003c/span\u003e inByte \u003cspan class=\"pl-c1\"\u003e\u0026amp;\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003e0x80\u003c/span\u003e // read the next bit\n inByte \u003cspan class=\"pl-c1\"\u003e\u0026lt;\u0026lt;=\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003e1\u003c/span\u003e\n inCount \u003cspan class=\"pl-c1\"\u003e+=\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003e1\u003c/span\u003e\n \u003cspan class=\"pl-k\"\u003ereturn\u003c/span\u003e bit \u003cspan class=\"pl-c1\"\u003e==\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003e0\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003e?\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003efalse\u003c/span\u003e \u003cspan class=\"pl-k\"\u003e:\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003etrue\u003c/span\u003e\n \u003cspan class=\"pl-kos\"\u003e}\u003c/span\u003e\n\u003cspan class=\"pl-kos\"\u003e}\u003c/span\u003e\u003c/pre\u003e\u003c/div\u003e\n\u003cp dir=\"auto\"\u003eBy using this helper object, we can read one whole byte from the \u003ccode\u003eNSData\u003c/code\u003e object and put it in \u003ccode\u003einByte\u003c/code\u003e. Then, \u003ccode\u003ereadBit()\u003c/code\u003e returns the individual bits from that byte. Once \u003ccode\u003ereadBit()\u003c/code\u003e has been called 8 times, we read the next byte from the \u003ccode\u003eNSData\u003c/code\u003e.\u003c/p\u003e\n\u003cblockquote\u003e\n\u003cp dir=\"auto\"\u003e\u003cstrong\u003eNote:\u003c/strong\u003e If you are unfamiliar with this type of bit manipulation, just know that these two helper objects make it simple for us to write and read bits.\u003c/p\u003e\n\u003c/blockquote\u003e\n\u003cdiv class=\"markdown-heading\" dir=\"auto\"\u003e\u003ch2 tabindex=\"-1\" class=\"heading-element\" dir=\"auto\"\u003eThe frequency table\u003c/h2\u003e\u003ca id=\"user-content-the-frequency-table\" class=\"anchor\" aria-label=\"Permalink: The frequency table\" href=\"#the-frequency-table\"\u003e\u003csvg class=\"octicon octicon-link\" viewBox=\"0 0 16 16\" version=\"1.1\" width=\"16\" height=\"16\" aria-hidden=\"true\"\u003e\u003cpath d=\"m7.775 3.275 1.25-1.25a3.5 3.5 0 1 1 4.95 4.95l-2.5 2.5a3.5 3.5 0 0 1-4.95 0 .751.751 0 0 1 .018-1.042.751.751 0 0 1 1.042-.018 1.998 1.998 0 0 0 2.83 0l2.5-2.5a2.002 2.002 0 0 0-2.83-2.83l-1.25 1.25a.751.751 0 0 1-1.042-.018.751.751 0 0 1-.018-1.042Zm-4.69 9.64a1.998 1.998 0 0 0 2.83 0l1.25-1.25a.751.751 0 0 1 1.042.018.751.751 0 0 1 .018 1.042l-1.25 1.25a3.5 3.5 0 1 1-4.95-4.95l2.5-2.5a3.5 3.5 0 0 1 4.95 0 .751.751 0 0 1-.018 1.042.751.751 0 0 1-1.042.018 1.998 1.998 0 0 0-2.83 0l-2.5 2.5a1.998 1.998 0 0 0 0 2.83Z\"\u003e\u003c/path\u003e\u003c/svg\u003e\u003c/a\u003e\u003c/div\u003e\n\u003cp dir=\"auto\"\u003eThe first step in the Huffman compression is to read the entire input stream and build a frequency table. This table contains a list of all 256 possible byte values and shows how often each of these bytes occurs in the input data.\u003c/p\u003e\n\u003cp dir=\"auto\"\u003eWe could store this frequency information in a dictionary or an array, but since we need to build a tree, we might store the frequency table as the leaves of the tree.\u003c/p\u003e\n\u003cp dir=\"auto\"\u003eHere are the definitions we need:\u003c/p\u003e\n\u003cdiv class=\"highlight highlight-source-swift notranslate position-relative overflow-auto\" dir=\"auto\" data-snippet-clipboard-copy-content=\"class Huffman {\n typealias NodeIndex = Int\n\n struct Node {\n var count = 0\n var index: NodeIndex = -1\n var parent: NodeIndex = -1\n var left: NodeIndex = -1\n var right: NodeIndex = -1\n }\n\n var tree = [Node](repeating: Node(), count: 256)\n\n var root: NodeIndex = -1\n}\"\u003e\u003cpre\u003e\u003cspan class=\"pl-k\"\u003eclass\u003c/span\u003e \u003cspan class=\"pl-smi\"\u003eHuffman\u003c/span\u003e \u003cspan class=\"pl-kos\"\u003e{\u003c/span\u003e\n \u003cspan class=\"pl-k\"\u003etypealias\u003c/span\u003e \u003cspan class=\"pl-smi\"\u003eNodeIndex\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003e=\u003c/span\u003e \u003cspan class=\"pl-smi\"\u003eInt\u003c/span\u003e\n\n \u003cspan class=\"pl-k\"\u003estruct\u003c/span\u003e \u003cspan class=\"pl-smi\"\u003eNode\u003c/span\u003e \u003cspan class=\"pl-kos\"\u003e{\u003c/span\u003e\n \u003cspan class=\"pl-k\"\u003evar\u003c/span\u003e \u003cspan class=\"pl-s1\"\u003e\u003cspan class=\"pl-c1\"\u003ecount\u003c/span\u003e\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003e=\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003e0\u003c/span\u003e\n \u003cspan class=\"pl-k\"\u003evar\u003c/span\u003e \u003cspan class=\"pl-s1\"\u003e\u003cspan class=\"pl-c1\"\u003eindex\u003c/span\u003e\u003c/span\u003e\u003cspan class=\"pl-kos\"\u003e:\u003c/span\u003e \u003cspan class=\"pl-smi\"\u003eNodeIndex\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003e=\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003e-\u003c/span\u003e\u003cspan class=\"pl-c1\"\u003e1\u003c/span\u003e\n \u003cspan class=\"pl-k\"\u003evar\u003c/span\u003e \u003cspan class=\"pl-s1\"\u003e\u003cspan class=\"pl-c1\"\u003eparent\u003c/span\u003e\u003c/span\u003e\u003cspan class=\"pl-kos\"\u003e:\u003c/span\u003e \u003cspan class=\"pl-smi\"\u003eNodeIndex\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003e=\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003e-\u003c/span\u003e\u003cspan class=\"pl-c1\"\u003e1\u003c/span\u003e\n \u003cspan class=\"pl-k\"\u003evar\u003c/span\u003e \u003cspan class=\"pl-s1\"\u003e\u003cspan class=\"pl-c1\"\u003eleft\u003c/span\u003e\u003c/span\u003e\u003cspan class=\"pl-kos\"\u003e:\u003c/span\u003e \u003cspan class=\"pl-smi\"\u003eNodeIndex\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003e=\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003e-\u003c/span\u003e\u003cspan class=\"pl-c1\"\u003e1\u003c/span\u003e\n \u003cspan class=\"pl-k\"\u003evar\u003c/span\u003e \u003cspan class=\"pl-s1\"\u003e\u003cspan class=\"pl-c1\"\u003eright\u003c/span\u003e\u003c/span\u003e\u003cspan class=\"pl-kos\"\u003e:\u003c/span\u003e \u003cspan class=\"pl-smi\"\u003eNodeIndex\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003e=\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003e-\u003c/span\u003e\u003cspan class=\"pl-c1\"\u003e1\u003c/span\u003e\n \u003cspan class=\"pl-kos\"\u003e}\u003c/span\u003e\n\n \u003cspan class=\"pl-k\"\u003evar\u003c/span\u003e \u003cspan class=\"pl-s1\"\u003e\u003cspan class=\"pl-c1\"\u003etree\u003c/span\u003e\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003e=\u003c/span\u003e \u003cspan class=\"pl-kos\"\u003e[\u003c/span\u003eNode\u003cspan class=\"pl-kos\"\u003e]\u003c/span\u003e\u003cspan class=\"pl-kos\"\u003e(\u003c/span\u003erepeating\u003cspan class=\"pl-kos\"\u003e:\u003c/span\u003e \u003cspan class=\"pl-en\"\u003eNode\u003c/span\u003e\u003cspan class=\"pl-kos\"\u003e(\u003c/span\u003e\u003cspan class=\"pl-kos\"\u003e)\u003c/span\u003e\u003cspan class=\"pl-kos\"\u003e,\u003c/span\u003e count\u003cspan class=\"pl-kos\"\u003e:\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003e256\u003c/span\u003e\u003cspan class=\"pl-kos\"\u003e)\u003c/span\u003e\n\n \u003cspan class=\"pl-k\"\u003evar\u003c/span\u003e \u003cspan class=\"pl-s1\"\u003e\u003cspan class=\"pl-c1\"\u003eroot\u003c/span\u003e\u003c/span\u003e\u003cspan class=\"pl-kos\"\u003e:\u003c/span\u003e \u003cspan class=\"pl-smi\"\u003eNodeIndex\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003e=\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003e-\u003c/span\u003e\u003cspan class=\"pl-c1\"\u003e1\u003c/span\u003e\n\u003cspan class=\"pl-kos\"\u003e}\u003c/span\u003e\u003c/pre\u003e\u003c/div\u003e\n\u003cp dir=\"auto\"\u003eThe tree structure is stored in the \u003ccode\u003etree\u003c/code\u003e array and will be made up of \u003ccode\u003eNode\u003c/code\u003e objects. Since this is a \u003ca href=\"/rreballos/swift-algorithm-club/blob/master/Binary%20Tree\"\u003ebinary tree\u003c/a\u003e, each node needs two children, \u003ccode\u003eleft\u003c/code\u003e and \u003ccode\u003eright\u003c/code\u003e, and a reference back to its \u003ccode\u003eparent\u003c/code\u003e node. Unlike a typical binary tree, these nodes do not use pointers to refer to each other but use simple integer indices in the \u003ccode\u003etree\u003c/code\u003e array. (We also store the array \u003ccode\u003eindex\u003c/code\u003e of the node itself; the reason for this will become clear later.)\u003c/p\u003e\n\u003cp dir=\"auto\"\u003eNote that the \u003ccode\u003etree\u003c/code\u003e currently has room for 256 entries. These are for the leaf nodes because there are 256 possible byte values. Of course, not all of those may end up being used, depending on the input data. Later, we will add more nodes as we build up the actual tree. For the moment, there is not a tree yet. It includes 256 separate leaf nodes with no connections between them. All the node counts are 0.\u003c/p\u003e\n\u003cp dir=\"auto\"\u003eWe use the following method to count how often each byte occurs in the input data:\u003c/p\u003e\n\u003cdiv class=\"highlight highlight-source-swift notranslate position-relative overflow-auto\" dir=\"auto\" data-snippet-clipboard-copy-content=\" fileprivate func countByteFrequency(inData data: NSData) {\n var ptr = data.bytes.assumingMemoryBound(to: UInt8.self)\n for _ in 0..\u0026lt;data.length {\n let i = Int(ptr.pointee)\n tree[i].count += 1\n tree[i].index = i\n ptr = ptr.successor()\n }\n }\"\u003e\u003cpre\u003e \u003cspan class=\"pl-k\"\u003efileprivate\u003c/span\u003e \u003cspan class=\"pl-en\"\u003efunc\u003c/span\u003e countByteFrequency\u003cspan class=\"pl-kos\"\u003e(\u003c/span\u003einData data\u003cspan class=\"pl-kos\"\u003e:\u003c/span\u003e \u003cspan class=\"pl-smi\"\u003eNSData\u003c/span\u003e\u003cspan class=\"pl-kos\"\u003e)\u003c/span\u003e \u003cspan class=\"pl-kos\"\u003e{\u003c/span\u003e\n \u003cspan class=\"pl-k\"\u003evar\u003c/span\u003e \u003cspan class=\"pl-s1\"\u003eptr\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003e=\u003c/span\u003e data\u003cspan class=\"pl-kos\"\u003e.\u003c/span\u003ebytes\u003cspan class=\"pl-kos\"\u003e.\u003c/span\u003 8000 e\u003cspan class=\"pl-en\"\u003eassumingMemoryBound\u003c/span\u003e\u003cspan class=\"pl-kos\"\u003e(\u003c/span\u003eto\u003cspan class=\"pl-kos\"\u003e:\u003c/span\u003e \u003cspan class=\"pl-smi\"\u003eUInt8\u003c/span\u003e\u003cspan class=\"pl-kos\"\u003e.\u003c/span\u003eself\u003cspan class=\"pl-kos\"\u003e)\u003c/span\u003e\n \u003cspan class=\"pl-k\"\u003efor\u003c/span\u003e \u003cspan class=\"pl-s1\"\u003e_\u003c/span\u003e \u003cspan class=\"pl-k\"\u003ein\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003e0\u003c/span\u003e\u003cspan class=\"pl-c1\"\u003e..\u0026lt;\u003c/span\u003edata\u003cspan class=\"pl-kos\"\u003e.\u003c/span\u003elength \u003cspan class=\"pl-kos\"\u003e{\u003c/span\u003e\n \u003cspan class=\"pl-k\"\u003elet\u003c/span\u003e \u003cspan class=\"pl-s1\"\u003ei\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003e=\u003c/span\u003e \u003cspan class=\"pl-en\"\u003eInt\u003c/span\u003e\u003cspan class=\"pl-kos\"\u003e(\u003c/span\u003eptr\u003cspan class=\"pl-kos\"\u003e.\u003c/span\u003epointee\u003cspan class=\"pl-kos\"\u003e)\u003c/span\u003e\n \u003cspan class=\"pl-en\"\u003etree\u003c/span\u003e\u003cspan class=\"pl-kos\"\u003e[\u003c/span\u003ei\u003cspan class=\"pl-kos\"\u003e]\u003c/span\u003e\u003cspan class=\"pl-kos\"\u003e.\u003c/span\u003ecount \u003cspan class=\"pl-c1\"\u003e+=\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003e1\u003c/span\u003e\n \u003cspan class=\"pl-en\"\u003etree\u003c/span\u003e\u003cspan class=\"pl-kos\"\u003e[\u003c/span\u003ei\u003cspan class=\"pl-kos\"\u003e]\u003c/span\u003e\u003cspan class=\"pl-kos\"\u003e.\u003c/span\u003eindex \u003cspan class=\"pl-c1\"\u003e=\u003c/span\u003e i\n ptr \u003cspan class=\"pl-c1\"\u003e=\u003c/span\u003e ptr\u003cspan class=\"pl-kos\"\u003e.\u003c/span\u003e\u003cspan class=\"pl-en\"\u003esuccessor\u003c/span\u003e\u003cspan class=\"pl-kos\"\u003e(\u003c/span\u003e\u003cspan class=\"pl-kos\"\u003e)\u003c/span\u003e\n \u003cspan class=\"pl-kos\"\u003e}\u003c/span\u003e\n \u003cspan class=\"pl-kos\"\u003e}\u003c/span\u003e\u003c/pre\u003e\u003c/div\u003e\n\u003cp dir=\"auto\"\u003eThis steps through the \u003ccode\u003eNSData\u003c/code\u003e object from beginning to end and for each byte increments the \u003ccode\u003ecount\u003c/code\u003e of the corresponding leaf node. After \u003ccode\u003ecountByteFrequency()\u003c/code\u003e completes, the first 256 \u003ccode\u003eNode\u003c/code\u003e objects in the \u003ccode\u003etree\u003c/code\u003e array represent the frequency table.\u003c/p\u003e\n\u003cp dir=\"auto\"\u003eTo decompress a Huffman-encoded block of data, we need to have the original frequency table. If we were writing the compressed data to a file, then somewhere in the file we should include the frequency table.\u003c/p\u003e\n\u003cp dir=\"auto\"\u003eWe could dump the first 256 elements from the \u003ccode\u003etree\u003c/code\u003e array, but that is not efficient. Not all of these 256 elements will be used, and we do not need to serialize the \u003ccode\u003eparent\u003c/code\u003e, \u003ccode\u003eright\u003c/code\u003e, and \u003ccode\u003eleft\u003c/code\u003e pointers. All we need is the frequency information and not the entire tree.\u003c/p\u003e\n\u003cp dir=\"auto\"\u003eInstead, we will add a method to export the frequency table without all the pieces we do not need:\u003c/p\u003e\n\u003cdiv class=\"highlight highlight-source-swift notranslate position-relative overflow-auto\" dir=\"auto\" data-snippet-clipboard-copy-content=\" struct Freq {\n var byte: UInt8 = 0\n var count = 0\n }\n\n func frequencyTable() -\u0026gt; [Freq] {\n var a = [Freq]()\n for i in 0..\u0026lt;256 where tree[i].count \u0026gt; 0 {\n a.append(Freq(byte: UInt8(i), count: tree[i].count))\n }\n return a\n }\"\u003e\u003cpre\u003e \u003cspan class=\"pl-k\"\u003estruct\u003c/span\u003e \u003cspan class=\"pl-smi\"\u003eFreq\u003c/span\u003e \u003cspan class=\"pl-kos\"\u003e{\u003c/span\u003e\n \u003cspan class=\"pl-k\"\u003evar\u003c/span\u003e \u003cspan class=\"pl-s1\"\u003e\u003cspan class=\"pl-c1\"\u003ebyte\u003c/span\u003e\u003c/span\u003e\u003cspan class=\"pl-kos\"\u003e:\u003c/span\u003e \u003cspan class=\"pl-smi\"\u003eUInt8\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003e=\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003e0\u003c/span\u003e\n \u003cspan class=\"pl-k\"\u003evar\u003c/span\u003e \u003cspan class=\"pl-s1\"\u003e\u003cspan class=\"pl-c1\"\u003ecount\u003c/span\u003e\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003e=\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003e0\u003c/span\u003e\n \u003cspan class=\"pl-kos\"\u003e}\u003c/span\u003e\n\n \u003cspan class=\"pl-en\"\u003efunc\u003c/span\u003e frequencyTable\u003cspan class=\"pl-kos\"\u003e(\u003c/span\u003e\u003cspan class=\"pl-kos\"\u003e)\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003e-\u0026gt;\u003c/span\u003e \u003cspan class=\"pl-kos\"\u003e[\u003c/span\u003e\u003cspan class=\"pl-smi\"\u003eFreq\u003c/span\u003e\u003cspan class=\"pl-kos\"\u003e]\u003c/span\u003e \u003cspan class=\"pl-kos\"\u003e{\u003c/span\u003e\n \u003cspan class=\"pl-k\"\u003evar\u003c/span\u003e \u003cspan class=\"pl-s1\"\u003ea\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003e=\u003c/span\u003e \u003cspan class=\"pl-kos\"\u003e[\u003c/span\u003eFreq\u003cspan class=\"pl-kos\"\u003e]\u003c/span\u003e\u003cspan class=\"pl-kos\"\u003e(\u003c/span\u003e\u003cspan class=\"pl-kos\"\u003e)\u003c/span\u003e\n \u003cspan class=\"pl-k\"\u003efor\u003c/span\u003e \u003cspan class=\"pl-s1\"\u003ei\u003c/span\u003e \u003cspan class=\"pl-k\"\u003ein\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003e0\u003c/span\u003e\u003cspan class=\"pl-c1\"\u003e..\u0026lt;\u003c/span\u003e\u003cspan class=\"pl-c1\"\u003e256\u003c/span\u003e \u003cspan class=\"pl-k\"\u003ewhere\u003c/span\u003e \u003cspan class=\"pl-en\"\u003etree\u003c/span\u003e\u003cspan class=\"pl-kos\"\u003e[\u003c/span\u003ei\u003cspan class=\"pl-kos\"\u003e]\u003c/span\u003e\u003cspan class=\"pl-kos\"\u003e.\u003c/span\u003ecount \u003cspan class=\"pl-c1\"\u003e\u0026gt;\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003e0\u003c/span\u003e \u003cspan class=\"pl-kos\"\u003e{\u003c/span\u003e\n a\u003cspan class=\"pl-kos\"\u003e.\u003c/span\u003e\u003cspan class=\"pl-en\"\u003eappend\u003c/span\u003e\u003cspan class=\"pl-kos\"\u003e(\u003c/span\u003e\u003cspan class=\"pl-en\"\u003eFreq\u003c/span\u003e\u003cspan class=\"pl-kos\"\u003e(\u003c/span\u003ebyte\u003cspan class=\"pl-kos\"\u003e:\u003c/span\u003e \u003cspan class=\"pl-en\"\u003eUInt8\u003c/span\u003e\u003cspan class=\"pl-kos\"\u003e(\u003c/span\u003ei\u003cspan class=\"pl-kos\"\u003e)\u003c/span\u003e\u003cspan class=\"pl-kos\"\u003e,\u003c/span\u003e count\u003cspan class=\"pl-kos\"\u003e:\u003c/span\u003e \u003cspan class=\"pl-en\"\u003etree\u003c/span\u003e\u003cspan class=\"pl-kos\"\u003e[\u003c/span\u003ei\u003cspan class=\"pl-kos\"\u003e]\u003c/span\u003e\u003cspan class=\"pl-kos\"\u003e.\u003c/span\u003ecount\u003cspan class=\"pl-kos\"\u003e)\u003c/span\u003e\u003cspan class=\"pl-kos\"\u003e)\u003c/span\u003e\n \u003cspan class=\"pl-kos\"\u003e}\u003c/span\u003e\n \u003cspan class=\"pl-k\"\u003ereturn\u003c/span\u003e a\n \u003cspan class=\"pl-kos\"\u003e}\u003c/span\u003e\u003c/pre\u003e\u003c/div\u003e\n\u003cp dir=\"auto\"\u003eThe \u003ccode\u003efrequencyTable()\u003c/code\u003e method looks at those first 256 nodes from the tree but keeps only those that are used, without the \u003ccode\u003eparent\u003c/code\u003e, \u003ccode\u003eleft\u003c/code\u003e, and \u003ccode\u003eright\u003c/code\u003e pointers. It returns an array of \u003ccode\u003eFreq\u003c/code\u003e objects. You have to serialize this array along with the compressed data, so that it can be properly decompressed later.\u003c/p\u003e\n\u003cdiv class=\"markdown-heading\" dir=\"auto\"\u003e\u003ch2 tabindex=\"-1\" class=\"heading-element\" dir=\"auto\"\u003eThe tree\u003c/h2\u003e\u003ca id=\"user-content-the-tree\" class=\"anchor\" aria-label=\"Permalink: The tree\" href=\"#the-tree\"\u003e\u003csvg class=\"octicon octicon-link\" viewBox=\"0 0 16 16\" version=\"1.1\" width=\"16\" height=\"16\" aria-hidden=\"true\"\u003e\u003cpath d=\"m7.775 3.275 1.25-1.25a3.5 3.5 0 1 1 4.95 4.95l-2.5 2.5a3.5 3.5 0 0 1-4.95 0 .751.751 0 0 1 .018-1.042.751.751 0 0 1 1.042-.018 1.998 1.998 0 0 0 2.83 0l2.5-2.5a2.002 2.002 0 0 0-2.83-2.83l-1.25 1.25a.751.751 0 0 1-1.042-.018.751.751 0 0 1-.018-1.042Zm-4.69 9.64a1.998 1.998 0 0 0 2.83 0l1.25-1.25a.751.751 0 0 1 1.042.018.751.751 0 0 1 .018 1.042l-1.25 1.25a3.5 3.5 0 1 1-4.95-4.95l2.5-2.5a3.5 3.5 0 0 1 4.95 0 .751.751 0 0 1-.018 1.042.751.751 0 0 1-1.042.018 1.998 1.998 0 0 0-2.83 0l-2.5 2.5a1.998 1.998 0 0 0 0 2.83Z\"\u003e\u003c/path\u003e\u003c/svg\u003e\u003c/a\u003e\u003c/div\u003e\n\u003cp dir=\"auto\"\u003eAs a reminder, there is the compression tree for the example:\u003c/p\u003e\n\u003cp dir=\"auto\"\u003e\u003ca target=\"_blank\" rel=\"noopener noreferrer\" href=\"/rreballos/swift-algorithm-club/blob/master/Huffman%20Coding/Images/Tree.png\"\u003e\u003cimg src=\"/rreballos/swift-algorithm-club/raw/master/Huffman%20Coding/Images/Tree.png\" alt=\"The compression tree\" style=\"max-width: 100%;\"\u003e\u003c/a\u003e\u003c/p\u003e\n\u003cp dir=\"auto\"\u003eThe leaf nodes represent the actual bytes that are present in the input data. The intermediary nodes connect the leaves in such a way that the path from the root to a frequently-used byte value is shorter than the path to a less common byte value. As you can see, \u003ccode\u003em\u003c/code\u003e, \u003ccode\u003es\u003c/code\u003e, space, and \u003ccode\u003eo\u003c/code\u003e are the most common letters in our input data and the highest up in the tree.\u003c/p\u003e\n\u003cp dir=\"auto\"\u003eTo build the tree, we do the following:\u003c/p\u003e\n\u003col dir=\"auto\"\u003e\n\u003cli\u003eFind the two nodes with the smallest counts that do not have a parent node yet.\u003c/li\u003e\n\u003cli\u003eCreate a new parent node that links these two nodes together.\u003c/li\u003e\n\u003cli\u003eThis repeats over and over until only one node with no parent remains. This becomes the root node of the tree.\u003c/li\u003e\n\u003c/ol\u003e\n\u003cp dir=\"auto\"\u003eThis is an ideal place to use a \u003ca href=\"/rreballos/swift-algorithm-club/blob/master/Priority%20Queue\"\u003epriority queue\u003c/a\u003e. A priority queue is a data structure that is optimized, so that finding the minimum value is always fast. Here, we repeatedly need to find the node with the smallest count.\u003c/p\u003e\n\u003cp dir=\"auto\"\u003eThe function \u003ccode\u003ebuildTree()\u003c/code\u003e then becomes:\u003c/p\u003e\n\u003cdiv class=\"highlight highlight-source-swift notranslate position-relative overflow-auto\" dir=\"auto\" data-snippet-clipboard-copy-content=\" fileprivate func buildTree() {\n var queue = PriorityQueue\u0026lt;Node\u0026gt;(sort: { $0.count \u0026lt; $1.count })\n for node in tree where node.count \u0026gt; 0 {\n queue.enqueue(node) // 1\n }\n\n while queue.count \u0026gt; 1 {\n let node1 = queue.dequeue()! // 2\n let node2 = queue.dequeue()!\n\n var parentNode = Node() // 3\n parentNode.count = node1.count + node2.count\n parentNode.left = node1.index\n parentNode.right = node2.index\n parentNode.index = tree.count\n tree.append(parentNode)\n\n tree[node1.index].parent = parentNode.index // 4\n tree[node2.index].parent = parentNode.index\n\n queue.enqueue(parentNode) // 5\n }\n\n let rootNode = queue.dequeue()! // 6\n root = rootNode.index\n }\"\u003e\u003cpre\u003e \u003cspan class=\"pl-k\"\u003efileprivate\u003c/span\u003e \u003cspan class=\"pl-en\"\u003efunc\u003c/span\u003e buildTree\u003cspan class=\"pl-kos\"\u003e(\u003c/span\u003e\u003cspan class=\"pl-kos\"\u003e)\u003c/span\u003e \u003cspan class=\"pl-kos\"\u003e{\u003c/span\u003e\n \u003cspan class=\"pl-k\"\u003evar\u003c/span\u003e \u003cspan class=\"pl-s1\"\u003equeue\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003e=\u003c/span\u003e \u003cspan class=\"pl-smi\"\u003ePriorityQueue\u003c/span\u003e\u003cspan class=\"pl-c1\"\u003e\u0026lt;\u003c/span\u003e\u003cspan class=\"pl-smi\"\u003eNode\u003c/span\u003e\u003cspan class=\"pl-c1\"\u003e\u0026gt;\u003c/span\u003e\u003cspan class=\"pl-kos\"\u003e(\u003c/span\u003esort\u003cspan class=\"pl-kos\"\u003e:\u003c/span\u003e \u003cspan class=\"pl-kos\"\u003e{\u003c/span\u003e $0\u003cspan class=\"pl-kos\"\u003e.\u003c/span\u003ecount \u003cspan class=\"pl-c1\"\u003e\u0026lt;\u003c/span\u003e $1\u003cspan class=\"pl-kos\"\u003e.\u003c/span\u003ecount \u003cspan class=\"pl-kos\"\u003e}\u003c/span\u003e\u003cspan class=\"pl-kos\"\u003e)\u003c/span\u003e\n \u003cspan class=\"pl-k\"\u003efor\u003c/span\u003e \u003cspan class=\"pl-s1\"\u003enode\u003c/span\u003e \u003cspan class=\"pl-k\"\u003ein\u003c/span\u003e tree \u003cspan class=\"pl-k\"\u003ewhere\u003c/span\u003e node\u003cspan class=\"pl-kos\"\u003e.\u003c/span\u003ecount \u003cspan class=\"pl-c1\"\u003e\u0026gt;\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003e0\u003c/span\u003e \u003cspan class=\"pl-kos\"\u003e{\u003c/span\u003e\n queue\u003cspan class=\"pl-kos\"\u003e.\u003c/span\u003e\u003cspan class=\"pl-en\"\u003eenqueue\u003c/span\u003e\u003cspan class=\"pl-kos\"\u003e(\u003c/span\u003enode\u003cspan class=\"pl-kos\"\u003e)\u003c/span\u003e // 1\n \u003cspan class=\"pl-kos\"\u003e}\u003c/span\u003e\n\n \u003cspan class=\"pl-k\"\u003ewhile\u003c/span\u003e queue\u003cspan class=\"pl-kos\"\u003e.\u003c/span\u003ecount \u003cspan class=\"pl-c1\"\u003e\u0026gt;\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003e1\u003c/span\u003e \u003cspan class=\"pl-kos\"\u003e{\u003c/span\u003e\n \u003cspan class=\"pl-k\"\u003elet\u003c/span\u003e \u003cspan class=\"pl-s1\"\u003enode1\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003e=\u003c/span\u003e queue\u003cspan class=\"pl-kos\"\u003e.\u003c/span\u003e\u003cspan class=\"pl-en\"\u003edequeue\u003c/span\u003e\u003cspan class=\"pl-kos\"\u003e(\u003c/span\u003e\u003cspan class=\"pl-kos\"\u003e)\u003c/span\u003e! // 2\n \u003cspan class=\"pl-k\"\u003elet\u003c/span\u003e \u003cspan class=\"pl-s1\"\u003enode2\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003e=\u003c/span\u003e queue\u003cspan class=\"pl-kos\"\u003e.\u003c/span\u003e\u003cspan class=\"pl-en\"\u003edequeue\u003c/span\u003e\u003cspan class=\"pl-kos\"\u003e(\u003c/span\u003e\u003cspan class=\"pl-kos\"\u003e)\u003c/span\u003e!\n\n \u003cspan class=\"pl-k\"\u003evar\u003c/span\u003e \u003cspan class=\"pl-s1\"\u003eparentNode\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003e=\u003c/span\u003e \u003cspan class=\"pl-en\"\u003eNode\u003c/span\u003e\u003cspan class=\"pl-kos\"\u003e(\u003c/span\u003e\u003cspan class=\"pl-kos\"\u003e)\u003c/span\u003e // 3\n parentNode\u003cspan class=\"pl-kos\"\u003e.\u003c/span\u003ecount \u003cspan class=\"pl-c1\"\u003e=\u003c/span\u003e node1\u003cspan class=\"pl-kos\"\u003e.\u003c/span\u003ecount \u003cspan class=\"pl-c1\"\u003e+\u003c/span\u003e node2\u003cspan class=\"pl-kos\"\u003e.\u003c/span\u003ecount\n parentNode\u003cspan class=\"pl-kos\"\u003e.\u003c/span\u003eleft \u003cspan class=\"pl-c1\"\u003e=\u003c/span\u003e node1\u003cspan class=\"pl-kos\"\u003e.\u003c/span\u003eindex\n parentNode\u003cspan class=\"pl-kos\"\u003e.\u003c/span\u003eright \u003cspan class=\"pl-c1\"\u003e=\u003c/span\u003e node2\u003cspan class=\"pl-kos\"\u003e.\u003c/span\u003eindex\n parentNode\u003cspan class=\"pl-kos\"\u003e.\u003c/span\u003eindex \u003cspan class=\"pl-c1\"\u003e=\u003c/span\u003e tree\u003cspan class=\"pl-kos\"\u003e.\u003c/span\u003ecount\n tree\u003cspan class=\"pl-kos\"\u003e.\u003c/span\u003e\u003cspan class=\"pl-en\"\u003eappend\u003c/span\u003e\u003cspan class=\"pl-kos\"\u003e(\u003c/span\u003eparentNode\u003cspan class=\"pl-kos\"\u003e)\u003c/span\u003e\n\n \u003cspan class=\"pl-en\"\u003etree\u003c/span\u003e\u003cspan class=\"pl-kos\"\u003e[\u003c/span\u003enode1\u003cspan class=\"pl-kos\"\u003e.\u003c/span\u003eindex\u003cspan class=\"pl-kos\"\u003e]\u003c/span\u003e\u003cspan class=\"pl-kos\"\u003e.\u003c/span\u003eparent \u003cspan class=\"pl-c1\"\u003e=\u003c/span\u003e parentNode\u003cspan class=\"pl-kos\"\u003e.\u003c/span\u003eindex // 4\n \u003cspan class=\"pl-en\"\u003etree\u003c/span\u003e\u003cspan class=\"pl-kos\"\u003e[\u003c/span\u003enode2\u003cspan class=\"pl-kos\"\u003e.\u003c/span\u003eindex\u003cspan class=\"pl-kos\"\u003e]\u003c/span\u003e\u003cspan class=\"pl-kos\"\u003e.\u003c/span\u003eparent \u003cspan class=\"pl-c1\"\u003e=\u003c/span\u003e parentNode\u003cspan class=\"pl-kos\"\u003e.\u003c/span\u003eindex\n\n queue\u003cspan class=\"pl-kos\"\u003e.\u003c/span\u003e\u003cspan class=\"pl-en\"\u003eenqueue\u003c/span\u003e\u003cspan class=\"pl-kos\"\u003e(\u003c/span\u003eparentNode\u003cspan class=\"pl-kos\"\u003e)\u003c/span\u003e // 5\n \u003cspan class=\"pl-kos\"\u003e}\u003c/span\u003e\n\n \u003cspan class=\"pl-k\"\u003elet\u003c/span\u003e \u003cspan class=\"pl-s1\"\u003erootNode\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003e=\u003c/span\u003e queue\u003cspan class=\"pl-kos\"\u003e.\u003c/span\u003e\u003cspan class=\"pl-en\"\u003edequeue\u003c/span\u003e\u003cspan class=\"pl-kos\"\u003e(\u003c/span\u003e\u003cspan class=\"pl-kos\"\u003e)\u003c/span\u003e! // 6\n root \u003cspan class=\"pl-c1\"\u003e=\u003c/span\u003e rootNode\u003cspan class=\"pl-kos\"\u003e.\u003c/span\u003eindex\n \u003cspan class=\"pl-kos\"\u003e}\u003c/span\u003e\u003c/pre\u003e\u003c/div\u003e\n\u003cp dir=\"auto\"\u003eHere is how it works step-by-step:\u003c/p\u003e\n\u003col dir=\"auto\"\u003e\n\u003cli\u003e\n\u003cp dir=\"auto\"\u003eCreate a priority queue and enqueue all the leaf nodes that have at least a count of 1. (If the count is 0, then this byte value did not appear in the input data.) The \u003ccode\u003ePriorityQueue\u003c/code\u003e object sorts the nodes by their count, so that the node with the lowest count is always the first one that gets dequeued.\u003c/p\u003e\n\u003c/li\u003e\n\u003cli\u003e\n\u003cp dir=\"auto\"\u003eWhile there are at least two nodes left in the queue, remove the two nodes that are at the front of the queue. Since this is a min-priority queue, this gives us the two nodes with the smallest counts that do not have a parent node yet.\u003c/p\u003e\n\u003c/li\u003e\n\u003cli\u003e\n\u003cp dir=\"auto\"\u003eCreate a new intermediate node that connects \u003ccode\u003enode1\u003c/code\u003e and \u003ccode\u003enode2\u003c/code\u003e. The count of this new node is the sum of the counts of \u003ccode\u003enode1\u003c/code\u003e and \u003ccode\u003enode2\u003c/code\u003e. Because the nodes are connected using array indices instead of real pointers, we use \u003ccode\u003enode1.index\u003c/code\u003e and \u003ccode\u003enode2.index\u003c/code\u003e to find these nodes in the \u003ccode\u003etree\u003c/code\u003e array. (This is why a \u003ccode\u003eNode\u003c/code\u003e needs to know its own index.)\u003c/p\u003e\n\u003c/li\u003e\n\u003cli\u003e\n\u003cp dir=\"auto\"\u003eLink the two nodes into their new parent node. Now this new intermediate node has become part of the tree.\u003c/p\u003e\n\u003c/li\u003e\n\u003cli\u003e\n\u003cp dir=\"auto\"\u003ePut the new intermediate node back into the queue. At this point we are done with \u003ccode\u003enode1\u003c/code\u003e and \u003ccode\u003enode2\u003c/code\u003e, but the \u003ccode\u003eparentNode\u003c/code\u003e still needs to be connected to other nodes in the tree.\u003c/p\u003e\n\u003c/li\u003e\n\u003cli\u003e\n\u003cp dir=\"auto\"\u003eRepeat steps 2-5 until there is only one node left in the queue. This becomes the root node of the tree, and we are done.\u003c/p\u003e\n\u003c/li\u003e\n\u003c/ol\u003e\n\u003cp dir=\"auto\"\u003eThe animation shows what the process looks like:\u003c/p\u003e\n\u003cp dir=\"auto\"\u003e\u003ca target=\"_blank\" rel=\"noopener noreferrer\" href=\"/rreballos/swift-algorithm-club/blob/master/Huffman%20Coding/Images/BuildTree.gif\"\u003e\u003cimg src=\"/rreballos/swift-algorithm-club/raw/master/Huffman%20Coding/Images/BuildTree.gif\" alt=\"Building the tree\" data-animated-image=\"\" style=\"max-width: 100%;\"\u003e\u003c/a\u003e\u003c/p\u003e\n\u003cblockquote\u003e\n\u003cp dir=\"auto\"\u003e\u003cstrong\u003eNote:\u003c/strong\u003e Instead of using a priority queue, you can repeatedly iterate through the \u003ccode\u003etree\u003c/code\u003e array to find the next two smallest nodes, but that makes the compressor slow as \u003cstrong\u003eO(n^2)\u003c/strong\u003e. Using the priority queue, the running time is only \u003cstrong\u003eO(n log n)\u003c/strong\u003e where \u003cstrong\u003en\u003c/strong\u003e is the number of nodes.\u003c/p\u003e\n\u003c/blockquote\u003e\n\u003cblockquote\u003e\n\u003cp dir=\"auto\"\u003e\u003cstrong\u003eFun fact:\u003c/strong\u003e Due to the nature of binary trees, if we have \u003cem\u003ex\u003c/em\u003e leaf nodes we can at most add \u003cem\u003ex - 1\u003c/em\u003e additional nodes to the tree. Given that at most there will be 256 leaf nodes, the tree will never contain more than 511 nodes total.\u003c/p\u003e\n\u003c/blockquote\u003e\n\u003cdiv class=\"markdown-heading\" dir=\"auto\"\u003e\u003ch2 tabindex=\"-1\" class=\"heading-element\" dir=\"auto\"\u003eCompression\u003c/h2\u003e\u003ca id=\"user-content-compression\" class=\"anchor\" aria-label=\"Permalink: Compression\" href=\"#compression\"\u003e\u003csvg class=\"octicon octicon-link\" viewBox=\"0 0 16 16\" version=\"1.1\" width=\"16\" height=\"16\" aria-hidden=\"true\"\u003e\u003cpath d=\"m7.775 3.275 1.25-1.25a3.5 3.5 0 1 1 4.95 4.95l-2.5 2.5a3.5 3.5 0 0 1-4.95 0 .751.751 0 0 1 .018-1.042.751.751 0 0 1 1.042-.018 1.998 1.998 0 0 0 2.83 0l2.5-2.5a2.002 2.002 0 0 0-2.83-2.83l-1.25 1.25a.751.751 0 0 1-1.042-.018.751.751 0 0 1-.018-1.042Zm-4.69 9.64a1.998 1.998 0 0 0 2.83 0l1.25-1.25a.751.751 0 0 1 1.042.018.751.751 0 0 1 .018 1.042l-1.25 1.25a3.5 3.5 0 1 1-4.95-4.95l2.5-2.5a3.5 3.5 0 0 1 4.95 0 .751.751 0 0 1-.018 1.042.751.751 0 0 1-1.042.018 1.998 1.998 0 0 0-2.83 0l-2.5 2.5a1.998 1.998 0 0 0 0 2.83Z\"\u003e\u003c/path\u003e\u003c/svg\u003e\u003c/a\u003e\u003c/div\u003e\n\u003cp dir=\"auto\"\u003eNow that we know how to build the compression tree from the frequency table, we can use it to compress the contents of an \u003ccode\u003eNSData\u003c/code\u003e object. Here is the code:\u003c/p\u003e\n\u003cdiv class=\"highlight highlight-source-swift notranslate position-relative overflow-auto\" dir=\"auto\" data-snippet-clipboard-copy-content=\" public func compressData(data: NSData) -\u0026gt; NSData {\n countByteFrequency(inData: data)\n buildTree()\n\n let writer = BitWriter()\n var ptr = data.bytes.assumingMemoryBound(to: UInt8.self)\n for _ in 0..\u0026lt;data.length {\n let c = ptr.pointee\n let i = Int(c)\n traverseTree(writer: writer, nodeIndex: i, childIndex: -1)\n ptr = ptr.successor()\n }\n writer.flush()\n return writer.data\n }\"\u003e\u003cpre\u003e \u003cspan class=\"pl-k\"\u003epublic\u003c/span\u003e \u003cspan class=\"pl-en\"\u003efunc\u003c/span\u003e compressData\u003cspan class=\"pl-kos\"\u003e(\u003c/span\u003edata\u003cspan class=\"pl-kos\"\u003e:\u003c/span\u003e \u003cspan class=\"pl-smi\"\u003eNSData\u003c/span\u003e\u003cspan class=\"pl-kos\"\u003e)\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003e-\u0026gt;\u003c/span\u003e \u003cspan class=\"pl-smi\"\u003eNSData\u003c/span\u003e \u003cspan class=\"pl-kos\"\u003e{\u003c/span\u003e\n \u003cspan class=\"pl-en\"\u003ecountByteFrequency\u003c/span\u003e\u003cspan class=\"pl-kos\"\u003e(\u003c/span\u003einData\u003cspan class=\"pl-kos\"\u003e:\u003c/span\u003e data\u003cspan class=\"pl-kos\"\u003e)\u003c/span\u003e\n \u003cspan class=\"pl-en\"\u003ebuildTree\u003c/span\u003e\u003cspan class=\"pl-kos\"\u003e(\u003c/span\u003e\u003cspan class=\"pl-kos\"\u003e)\u003c/span\u003e\n\n \u003cspan class=\"pl-k\"\u003elet\u003c/span\u003e \u003cspan class=\"pl-s1\"\u003ewriter\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003e=\u003c/span\u003e \u003cspan class=\"pl-en\"\u003eBitWriter\u003c/span\u003e\u003cspan class=\"pl-kos\"\u003e(\u003c/span\u003e\u003cspan class=\"pl-kos\"\u003e)\u003c/span\u003e\n \u003cspan class=\"pl-k\"\u003evar\u003c/span\u003e \u003cspan class=\"pl-s1\"\u003eptr\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003e=\u003c/span\u003e data\u003cspan class=\"pl-kos\"\u003e.\u003c/span\u003ebytes\u003cspan class=\"pl-kos\"\u003e.\u003c/span\u003e\u003cspan class=\"pl-en\"\u003eassumingMemoryBound\u003c/span\u003e\u003cspan class=\"pl-kos\"\u003e(\u003c/span\u003eto\u003cspan class=\"pl-kos\"\u003e:\u003c/span\u003e \u003cspan class=\"pl-smi\"\u003eUInt8\u003c/span\u003e\u003cspan class=\"pl-kos\"\u003e.\u003c/span\u003eself\u003cspan class=\"pl-kos\"\u003e)\u003c/span\u003e\n \u003cspan class=\"pl-k\"\u003efor\u003c/span\u003e \u003cspan class=\"pl-s1\"\u003e_\u003c/span\u003e \u003cspan class=\"pl-k\"\u003ein\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003e0\u003c/span\u003e\u003cspan class=\"pl-c1\"\u003e..\u0026lt;\u003c/span\u003edata\u003cspan class=\"pl-kos\"\u003e.\u003c/span\u003elength \u003cspan class=\"pl-kos\"\u003e{\u003c/span\u003e\n \u003cspan class=\"pl-k\"\u003elet\u003c/span\u003e \u003cspan class=\"pl-s1\"\u003ec\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003e=\u003c/span\u003e ptr\u003cspan class=\"pl-kos\"\u003e.\u003c/span\u003epointee\n \u003cspan class=\"pl-k\"\u003elet\u003c/span\u003e \u003cspan class=\"pl-s1\"\u003ei\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003e=\u003c/span\u003e \u003cspan class=\"pl-en\"\u003eInt\u003c/span\u003e\u003cspan class=\"pl-kos\"\u003e(\u003c/span\u003ec\u003cspan class=\"pl-kos\"\u003e)\u003c/span\u003e\n \u003cspan class=\"pl-en\"\u003etraverseTree\u003c/span\u003e\u003cspan class=\"pl-kos\"\u003e(\u003c/span\u003ewriter\u003cspan class=\"pl-kos\"\u003e:\u003c/span\u003e writer\u003cspan class=\"pl-kos\"\u003e,\u003c/span\u003e nodeIndex\u003cspan class=\"pl-kos\"\u003e:\u003c/span\u003e i\u003cspan class=\"pl-kos\"\u003e,\u003c/span\u003e childIndex\u003cspan class=\"pl-kos\"\u003e:\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003e-\u003c/span\u003e\u003cspan class=\"pl-c1\"\u003e1\u003c/span\u003e\u003cspan class=\"pl-kos\"\u003e)\u003c/span\u003e\n ptr \u003cspan class=\"pl-c1\"\u003e=\u003c/span\u003e ptr\u003cspan class=\"pl-kos\"\u003e.\u003c/span\u003e\u003cspan class=\"pl-en\"\u003esuccessor\u003c/span\u003e\u003cspan class=\"pl-kos\"\u003e(\u003c/span\u003e\u003cspan class=\"pl-kos\"\u003e)\u003c/span\u003e\n \u003cspan class=\"pl-kos\"\u003e}\u003c/span\u003e\n writer\u003cspan class=\"pl-kos\"\u003e.\u003c/span\u003e\u003cspan class=\"pl-en\"\u003eflush\u003c/span\u003e\u003cspan class=\"pl-kos\"\u003e(\u003c/span\u003e\u003cspan class=\"pl-kos\"\u003e)\u003c/span\u003e\n \u003cspan class=\"pl-k\"\u003ereturn\u003c/span\u003e writer\u003cspan class=\"pl-kos\"\u003e.\u003c/span\u003edata\n \u003cspan class=\"pl-kos\"\u003e}\u003c/span\u003e\u003c/pre\u003e\u003c/div\u003e\n\u003cp dir=\"auto\"\u003eThis first calls \u003ccode\u003ecountByteFrequency()\u003c/code\u003e to build the frequency table and then calls \u003ccode\u003ebuildTree()\u003c/code\u003e to put together the compression tree. It also creates a \u003ccode\u003eBitWriter\u003c/code\u003e object for writing individual bits.\u003c/p\u003e\n\u003cp dir=\"auto\"\u003eThen, it loops through the entire input and calls \u003ccode\u003etraverseTree()\u003c/code\u003efor each byte. This method will step through the tree nodes and for each node write a 1 or 0 bit. Finally, we return the \u003ccode\u003eBitWriter\u003c/code\u003e's data object.\u003c/p\u003e\n\u003cblockquote\u003e\n\u003cp dir=\"auto\"\u003e\u003cstrong\u003eNote:\u003c/strong\u003e Compression always requires two passes through the entire input data: first to build the frequency table, and second to convert the bytes to their compressed bit sequences.\u003c/p\u003e\n\u003c/blockquote\u003e\n\u003cp dir=\"auto\"\u003eThe interesting stuff happens in \u003ccode\u003etraverseTree()\u003c/code\u003e. This is a recursive method:\u003c/p\u003e\n\u003cdiv class=\"highlight highlight-source-swift notranslate position-relative overflow-auto\" dir=\"auto\" data-snippet-clipboard-copy-content=\" private func traverseTree(writer: BitWriter, nodeIndex h: Int, childIndex child: Int) {\n if tree[h].parent != -1 {\n traverseTree(writer: writer, nodeIndex: tree[h].parent, childIndex: h)\n }\n if child != -1 {\n if child == tree[h].left {\n writer.writeBit(bit: true)\n } else if child == tree[h].right {\n writer.writeBit(bit: false)\n }\n }\n }\"\u003e\u003cpre\u003e \u003cspan class=\"pl-k\"\u003eprivate\u003c/span\u003e \u003cspan class=\"pl-en\"\u003efunc\u003c/span\u003e traverseTree\u003cspan class=\"pl-kos\"\u003e(\u003c/span\u003ewriter\u003cspan class=\"pl-kos\"\u003e:\u003c/span\u003e \u003cspan class=\"pl-smi\"\u003eBitWriter\u003c/span\u003e\u003cspan class=\"pl-kos\"\u003e,\u003c/span\u003e nodeIndex h\u003cspan class=\"pl-kos\"\u003e:\u003c/span\u003e \u003cspan class=\"pl-smi\"\u003eInt\u003c/span\u003e\u003cspan class=\"pl-kos\"\u003e,\u003c/span\u003e childIndex child\u003cspan class=\"pl-kos\"\u003e:\u003c/span\u003e \u003cspan class=\"pl-smi\"\u003eInt\u003c/span\u003e\u003cspan class=\"pl-kos\"\u003e)\u003c/span\u003e \u003cspan class=\"pl-kos\"\u003e{\u003c/span\u003e\n \u003cspan class=\"pl-k\"\u003eif\u003c/span\u003e \u003cspan class=\"pl-en\"\u003etree\u003c/span\u003e\u003cspan class=\"pl-kos\"\u003e[\u003c/span\u003eh\u003cspan class=\"pl-kos\"\u003e]\u003c/span\u003e\u003cspan class=\"pl-kos\"\u003e.\u003c/span\u003eparent \u003cspan class=\"pl-c1\"\u003e!=\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003e-\u003c/span\u003e\u003cspan class=\"pl-c1\"\u003e1\u003c/span\u003e \u003cspan class=\"pl-kos\"\u003e{\u003c/span\u003e\n \u003cspan class=\"pl-en\"\u003etraverseTree\u003c/span\u003e\u003cspan class=\"pl-kos\"\u003e(\u003c/span\u003ewriter\u003cspan class=\"pl-kos\"\u003e:\u003c/span\u003e writer\u003cspan class=\"pl-kos\"\u003e,\u003c/span\u003e nodeIndex\u003cspan class=\"pl-kos\"\u003e:\u003c/span\u003e \u003cspan class=\"pl-en\"\u003etree\u003c/span\u003e\u003cspan class=\"pl-kos\"\u003e[\u003c/span\u003eh\u003cspan class=\"pl-kos\"\u003e]\u003c/span\u003e\u003cspan class=\"pl-kos\"\u003e.\u003c/span\u003eparent\u003cspan class=\"pl-kos\"\u003e,\u003c/span\u003e childIndex\u003cspan class=\"pl-kos\"\u003e:\u003c/span\u003e h\u003cspan class=\"pl-kos\"\u003e)\u003c/span\u003e\n \u003cspan class=\"pl-kos\"\u003e}\u003c/span\u003e\n \u003cspan class=\"pl-k\"\u003eif\u003c/span\u003e child \u003cspan class=\"pl-c1\"\u003e!=\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003e-\u003c/span\u003e\u003cspan class=\"pl-c1\"\u003e1\u003c/span\u003e \u003cspan class=\"pl-kos\"\u003e{\u003c/span\u003e\n \u003cspan class=\"pl-k\"\u003eif\u003c/span\u003e child \u003cspan class=\"pl-c1\"\u003e==\u003c/span\u003e \u003cspan class=\"pl-en\"\u003etree\u003c/span\u003e\u003cspan class=\"pl-kos\"\u003e[\u003c/span\u003eh\u003cspan class=\"pl-kos\"\u003e]\u003c/span\u003e\u003cspan class=\"pl-kos\"\u003e.\u003c/span\u003eleft \u003cspan class=\"pl-kos\"\u003e{\u003c/span\u003e\n writer\u003cspan class=\"pl-kos\"\u003e.\u003c/span\u003e\u003cspan class=\"pl-en\"\u003ewriteBit\u003c/span\u003e\u003cspan class=\"pl-kos\"\u003e(\u003c/span\u003ebit\u003cspan class=\"pl-kos\"\u003e:\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003etrue\u003c/span\u003e\u003cspan class=\"pl-kos\"\u003e)\u003c/span\u003e\n \u003cspan class=\"pl-kos\"\u003e}\u003c/span\u003e \u003cspan class=\"pl-k\"\u003eelse\u003c/span\u003e \u003cspan class=\"pl-k\"\u003eif\u003c/span\u003e child \u003cspan class=\"pl-c1\"\u003e==\u003c/span\u003e \u003cspan class=\"pl-en\"\u003etree\u003c/span\u003e\u003cspan class=\"pl-kos\"\u003e[\u003c/span\u003eh\u003cspan class=\"pl-kos\"\u003e]\u003c/span\u003e\u003cspan class=\"pl-kos\"\u003e.\u003c/span\u003eright \u003cspan class=\"pl-kos\"\u003e{\u003c/span\u003e\n writer\u003cspan class=\"pl-kos\"\u003e.\u003 8000 c/span\u003e\u003cspan class=\"pl-en\"\u003ewriteBit\u003c/span\u003e\u003cspan class=\"pl-kos\"\u003e(\u003c/span\u003ebit\u003cspan class=\"pl-kos\"\u003e:\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003efalse\u003c/span\u003e\u003cspan class=\"pl-kos\"\u003e)\u003c/span\u003e\n \u003cspan class=\"pl-kos\"\u003e}\u003c/span\u003e\n \u003cspan class=\"pl-kos\"\u003e}\u003c/span\u003e\n \u003cspan class=\"pl-kos\"\u003e}\u003c/span\u003e\u003c/pre\u003e\u003c/div\u003e\n\u003cp dir=\"auto\"\u003eWhen we call this method from \u003ccode\u003ecompressData()\u003c/code\u003e, the \u003ccode\u003enodeIndex\u003c/code\u003e parameter is the array index of the leaf node for the byte that we need to encode. This method recursively walks the tree from a leaf node up to the root and then back again.\u003c/p\u003e\n\u003cp dir=\"auto\"\u003eAs we are going back from the root to the leaf node, we write a 1 bit or a 0 bit for every node we encounter. If a child is the left node, we emit a 1; if it is the right node, we emit a 0.\u003c/p\u003e\n\u003cp dir=\"auto\"\u003eIn a picture:\u003c/p\u003e\n\u003cp dir=\"auto\"\u003e\u003ca target=\"_blank\" rel=\"noopener noreferrer\" href=\"/rreballos/swift-algorithm-club/blob/master/Huffman%20Coding/Images/Compression.png\"\u003e\u003cimg src=\"/rreballos/swift-algorithm-club/raw/master/Huffman%20Coding/Images/Compression.png\" alt=\"How compression works\" style=\"max-width: 100%;\"\u003e\u003c/a\u003e\u003c/p\u003e\n\u003cp dir=\"auto\"\u003eEven though the illustration of the tree shows a 0 or 1 for each edge between the nodes, the bit values 0 and 1 are not actually stored in the tree! The rule is that we write a 1 bit if we take the left branch and a 0 bit if we take the right branch, so just knowing the direction we are going in is enough to determine what bit value to write.\u003c/p\u003e\n\u003cp dir=\"auto\"\u003eYou use the \u003ccode\u003ecompressData()\u003c/code\u003e method as follows:\u003c/p\u003e\n\u003cdiv class=\"highlight highlight-source-swift notranslate position-relative overflow-auto\" dir=\"auto\" data-snippet-clipboard-copy-content=\"let s1 = \u0026quot;so much words wow many compression\u0026quot;\nif let originalData = s1.dataUsingEncoding(NSUTF8StringEncoding) {\n let huffman1 = Huffman()\n let compressedData = huffman1.compressData(originalData)\n print(compressedData.length)\n}\"\u003e\u003cpre\u003e\u003cspan class=\"pl-k\"\u003elet\u003c/span\u003e \u003cspan class=\"pl-s1\"\u003es1\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003e=\u003c/span\u003e \u003cspan class=\"pl-s\"\u003e\"\u003c/span\u003e\u003cspan class=\"pl-s\"\u003eso much words wow many compression\u003c/span\u003e\u003cspan class=\"pl-s\"\u003e\"\u003c/span\u003e\n\u003cspan class=\"pl-k\"\u003eif\u003c/span\u003e \u003cspan class=\"pl-k\"\u003elet\u003c/span\u003e originalData \u003cspan class=\"pl-c1\"\u003e=\u003c/span\u003e s1\u003cspan class=\"pl-kos\"\u003e.\u003c/span\u003e\u003cspan class=\"pl-en\"\u003edataUsingEncoding\u003c/span\u003e\u003cspan class=\"pl-kos\"\u003e(\u003c/span\u003eNSUTF8StringEncoding\u003cspan class=\"pl-kos\"\u003e)\u003c/span\u003e \u003cspan class=\"pl-kos\"\u003e{\u003c/span\u003e\n \u003cspan class=\"pl-k\"\u003elet\u003c/span\u003e \u003cspan class=\"pl-s1\"\u003ehuffman1\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003e=\u003c/span\u003e \u003cspan class=\"pl-en\"\u003eHuffman\u003c/span\u003e\u003cspan class=\"pl-kos\"\u003e(\u003c/span\u003e\u003cspan class=\"pl-kos\"\u003e)\u003c/span\u003e\n \u003cspan class=\"pl-k\"\u003elet\u003c/span\u003e \u003cspan class=\"pl-s1\"\u003ecompressedData\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003e=\u003c/span\u003e huffman1\u003cspan class=\"pl-kos\"\u003e.\u003c/span\u003e\u003cspan class=\"pl-en\"\u003ecompressData\u003c/span\u003e\u003cspan class=\"pl-kos\"\u003e(\u003c/span\u003eoriginalData\u003cspan class=\"pl-kos\"\u003e)\u003c/span\u003e\n \u003cspan class=\"pl-en\"\u003eprint\u003c/span\u003e\u003cspan class=\"pl-kos\"\u003e(\u003c/span\u003ecompressedData\u003cspan class=\"pl-kos\"\u003e.\u003c/span\u003elength\u003cspan class=\"pl-kos\"\u003e)\u003c/span\u003e\n\u003cspan class=\"pl-kos\"\u003e}\u003c/span\u003e\u003c/pre\u003e\u003c/div\u003e\n\u003cdiv class=\"markdown-heading\" dir=\"auto\"\u003e\u003ch2 tabindex=\"-1\" class=\"heading-element\" dir=\"auto\"\u003eDecompression\u003c/h2\u003e\u003ca id=\"user-content-decompression\" class=\"anchor\" aria-label=\"Permalink: Decompression\" href=\"#decompression\"\u003e\u003csvg class=\"octicon octicon-link\" viewBox=\"0 0 16 16\" version=\"1.1\" width=\"16\" height=\"16\" aria-hidden=\"true\"\u003e\u003cpath d=\"m7.775 3.275 1.25-1.25a3.5 3.5 0 1 1 4.95 4.95l-2.5 2.5a3.5 3.5 0 0 1-4.95 0 .751.751 0 0 1 .018-1.042.751.751 0 0 1 1.042-.018 1.998 1.998 0 0 0 2.83 0l2.5-2.5a2.002 2.002 0 0 0-2.83-2.83l-1.25 1.25a.751.751 0 0 1-1.042-.018.751.751 0 0 1-.018-1.042Zm-4.69 9.64a1.998 1.998 0 0 0 2.83 0l1.25-1.25a.751.751 0 0 1 1.042.018.751.751 0 0 1 .018 1.042l-1.25 1.25a3.5 3.5 0 1 1-4.95-4.95l2.5-2.5a3.5 3.5 0 0 1 4.95 0 .751.751 0 0 1-.018 1.042.751.751 0 0 1-1.042.018 1.998 1.998 0 0 0-2.83 0l-2.5 2.5a1.998 1.998 0 0 0 0 2.83Z\"\u003e\u003c/path\u003e\u003c/svg\u003e\u003c/a\u003e\u003c/div\u003e\n\u003cp dir=\"auto\"\u003eDecompression is the compression in reverse. However, the compressed bits are useless without the frequency table. As mentioned, the \u003ccode\u003efrequencyTable()\u003c/code\u003e method returns an array of \u003ccode\u003eFreq\u003c/code\u003e objects. If we were saving the compressed data into a file or sending it across the network, we'd also save that \u003ccode\u003e[Freq]\u003c/code\u003e array along with it.\u003c/p\u003e\n\u003cp dir=\"auto\"\u003eWe first need some way to turn the \u003ccode\u003e[Freq]\u003c/code\u003e array back into a compression tree:\u003c/p\u003e\n\u003cdiv class=\"highlight highlight-source-swift notranslate position-relative overflow-auto\" dir=\"auto\" data-snippet-clipboard-copy-content=\" fileprivate func restoreTree(fromTable frequencyTable: [Freq]) {\n for freq in frequencyTable {\n let i = Int(freq.byte)\n tree[i].count = freq.count\n tree[i].index = i\n }\n buildTree()\n }\"\u003e\u003cpre\u003e \u003cspan class=\"pl-k\"\u003efileprivate\u003c/span\u003e \u003cspan class=\"pl-en\"\u003efunc\u003c/span\u003e restoreTree\u003cspan class=\"pl-kos\"\u003e(\u003c/span\u003efromTable frequencyTable\u003cspan class=\"pl-kos\"\u003e:\u003c/span\u003e \u003cspan class=\"pl-kos\"\u003e[\u003c/span\u003e\u003cspan class=\"pl-smi\"\u003eFreq\u003c/span\u003e\u003cspan class=\"pl-kos\"\u003e]\u003c/span\u003e\u003cspan class=\"pl-kos\"\u003e)\u003c/span\u003e \u003cspan class=\"pl-kos\"\u003e{\u003c/span\u003e\n \u003cspan class=\"pl-k\"\u003efor\u003c/span\u003e \u003cspan class=\"pl-s1\"\u003efreq\u003c/span\u003e \u003cspan class=\"pl-k\"\u003ein\u003c/span\u003e frequencyTable \u003cspan class=\"pl-kos\"\u003e{\u003c/span\u003e\n \u003cspan class=\"pl-k\"\u003elet\u003c/span\u003e \u003cspan class=\"pl-s1\"\u003ei\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003e=\u003c/span\u003e \u003cspan class=\"pl-en\"\u003eInt\u003c/span\u003e\u003cspan class=\"pl-kos\"\u003e(\u003c/span\u003efreq\u003cspan class=\"pl-kos\"\u003e.\u003c/span\u003ebyte\u003cspan class=\"pl-kos\"\u003e)\u003c/span\u003e\n \u003cspan class=\"pl-en\"\u003etree\u003c/span\u003e\u003cspan class=\"pl-kos\"\u003e[\u003c/span\u003ei\u003cspan class=\"pl-kos\"\u003e]\u003c/span\u003e\u003cspan class=\"pl-kos\"\u003e.\u003c/span\u003ecount \u003cspan class=\"pl-c1\"\u003e=\u003c/span\u003e freq\u003cspan class=\"pl-kos\"\u003e.\u003c/span\u003ecount\n \u003cspan class=\"pl-en\"\u003etree\u003c/span\u003e\u003cspan class=\"pl-kos\"\u003e[\u003c/span\u003ei\u003cspan class=\"pl-kos\"\u003e]\u003c/span\u003e\u003cspan class=\"pl-kos\"\u003e.\u003c/span\u003eindex \u003cspan class=\"pl-c1\"\u003e=\u003c/span\u003e i\n \u003cspan class=\"pl-kos\"\u003e}\u003c/span\u003e\n \u003cspan class=\"pl-en\"\u003ebuildTree\u003c/span\u003e\u003cspan class=\"pl-kos\"\u003e(\u003c/span\u003e\u003cspan class=\"pl-kos\"\u003e)\u003c/span\u003e\n \u003cspan class=\"pl-kos\"\u003e}\u003c/span\u003e\u003c/pre\u003e\u003c/div\u003e\n\u003cp dir=\"auto\"\u003eWe convert the \u003ccode\u003eFreq\u003c/code\u003e objects into leaf nodes and then call \u003ccode\u003ebuildTree()\u003c/code\u003e to do the rest.\u003c/p\u003e\n\u003cp dir=\"auto\"\u003eHere is the code for \u003ccode\u003edecompressData()\u003c/code\u003e, which takes an \u003ccode\u003eNSData\u003c/code\u003e object with Huffman-encoded bits and a frequency table, and it returns the original data:\u003c/p\u003e\n\u003cdiv class=\"highlight highlight-source-swift notranslate position-relative overflow-auto\" dir=\"auto\" data-snippet-clipboard-copy-content=\" func decompressData(data: NSData, frequencyTable: [Freq]) -\u0026gt; NSData {\n restoreTree(fromTable: frequencyTable)\n\n let reader = BitReader(data: data)\n let outData = NSMutableData()\n let byteCount = tree[root].count\n\n var i = 0\n while i \u0026lt; byteCount {\n var b = findLeafNode(reader: reader, nodeIndex: root)\n outData.append(\u0026amp;b, length: 1)\n i += 1\n }\n return outData\n }\"\u003e\u003cpre\u003e \u003cspan class=\"pl-en\"\u003efunc\u003c/span\u003e decompressData\u003cspan class=\"pl-kos\"\u003e(\u003c/span\u003edata\u003cspan class=\"pl-kos\"\u003e:\u003c/span\u003e \u003cspan class=\"pl-smi\"\u003eNSData\u003c/span\u003e\u003cspan class=\"pl-kos\"\u003e,\u003c/span\u003e frequencyTable\u003cspan class=\"pl-kos\"\u003e:\u003c/span\u003e \u003cspan class=\"pl-kos\"\u003e[\u003c/span\u003e\u003cspan class=\"pl-smi\"\u003eFreq\u003c/span\u003e\u003cspan class=\"pl-kos\"\u003e]\u003c/span\u003e\u003cspan class=\"pl-kos\"\u003e)\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003e-\u0026gt;\u003c/span\u003e \u003cspan class=\"pl-smi\"\u003eNSData\u003c/span\u003e \u003cspan class=\"pl-kos\"\u003e{\u003c/span\u003e\n \u003cspan class=\"pl-en\"\u003erestoreTree\u003c/span\u003e\u003cspan class=\"pl-kos\"\u003e(\u003c/span\u003efromTable\u003cspan class=\"pl-kos\"\u003e:\u003c/span\u003e frequencyTable\u003cspan class=\"pl-kos\"\u003e)\u003c/span\u003e\n\n \u003cspan class=\"pl-k\"\u003elet\u003c/span\u003e \u003cspan class=\"pl-s1\"\u003ereader\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003e=\u003c/span\u003e \u003cspan class=\"pl-en\"\u003eBitReader\u003c/span\u003e\u003cspan class=\"pl-kos\"\u003e(\u003c/span\u003edata\u003cspan class=\"pl-kos\"\u003e:\u003c/span\u003e data\u003cspan class=\"pl-kos\"\u003e)\u003c/span\u003e\n \u003cspan class=\"pl-k\"\u003elet\u003c/span\u003e \u003cspan class=\"pl-s1\"\u003eoutData\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003e=\u003c/span\u003e \u003cspan class=\"pl-en\"\u003eNSMutableData\u003c/span\u003e\u003cspan class=\"pl-kos\"\u003e(\u003c/span\u003e\u003cspan class=\"pl-kos\"\u003e)\u003c/span\u003e\n \u003cspan class=\"pl-k\"\u003elet\u003c/span\u003e \u003cspan class=\"pl-s1\"\u003ebyteCount\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003e=\u003c/span\u003e \u003cspan class=\"pl-en\"\u003etree\u003c/span\u003e\u003cspan class=\"pl-kos\"\u003e[\u003c/span\u003eroot\u003cspan class=\"pl-kos\"\u003e]\u003c/span\u003e\u003cspan class=\"pl-kos\"\u003e.\u003c/span\u003ecount\n\n \u003cspan class=\"pl-k\"\u003evar\u003c/span\u003e \u003cspan class=\"pl-s1\"\u003ei\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003e=\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003e0\u003c/span\u003e\n \u003cspan class=\"pl-k\"\u003ewhile\u003c/span\u003e i \u003cspan class=\"pl-c1\"\u003e\u0026lt;\u003c/span\u003e byteCount \u003cspan class=\"pl-kos\"\u003e{\u003c/span\u003e\n \u003cspan class=\"pl-k\"\u003evar\u003c/span\u003e \u003cspan class=\"pl-s1\"\u003eb\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003e=\u003c/span\u003e \u003cspan class=\"pl-en\"\u003efindLeafNode\u003c/span\u003e\u003cspan class=\"pl-kos\"\u003e(\u003c/span\u003ereader\u003cspan class=\"pl-kos\"\u003e:\u003c/span\u003e reader\u003cspan class=\"pl-kos\"\u003e,\u003c/span\u003e nodeIndex\u003cspan class=\"pl-kos\"\u003e:\u003c/span\u003e root\u003cspan class=\"pl-kos\"\u003e)\u003c/span\u003e\n outData\u003cspan class=\"pl-kos\"\u003e.\u003c/span\u003e\u003cspan class=\"pl-en\"\u003eappend\u003c/span\u003e\u003cspan class=\"pl-kos\"\u003e(\u003c/span\u003e\u003cspan class=\"pl-c1\"\u003e\u0026amp;\u003c/span\u003eb\u003cspan class=\"pl-kos\"\u003e,\u003c/span\u003e length\u003cspan class=\"pl-kos\"\u003e:\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003e1\u003c/span\u003e\u003cspan class=\"pl-kos\"\u003e)\u003c/span\u003e\n i \u003cspan class=\"pl-c1\"\u003e+=\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003e1\u003c/span\u003e\n \u003cspan class=\"pl-kos\"\u003e}\u003c/span\u003e\n \u003cspan class=\"pl-k\"\u003ereturn\u003c/span\u003e outData\n \u003cspan class=\"pl-kos\"\u003e}\u003c/span\u003e\u003c/pre\u003e\u003c/div\u003e\n\u003cp dir=\"auto\"\u003eThis also uses a helper method to traverse the tree:\u003c/p\u003e\n\u003cdiv class=\"highlight highlight-source-swift notranslate position-relative overflow-auto\" dir=\"auto\" data-snippet-clipboard-copy-content=\" private func findLeafNode(reader reader: BitReader, nodeIndex: Int) -\u0026gt; UInt8 {\n var h = nodeIndex\n while tree[h].right != -1 {\n if reader.readBit() {\n h = tree[h].left\n } else {\n h = tree[h].right\n }\n }\n return UInt8(h)\n }\"\u003e\u003cpre\u003e \u003cspan class=\"pl-k\"\u003eprivate\u003c/span\u003e \u003cspan class=\"pl-en\"\u003efunc\u003c/span\u003e findLeafNode\u003cspan class=\"pl-kos\"\u003e(\u003c/span\u003ereader reader\u003cspan class=\"pl-kos\"\u003e:\u003c/span\u003e \u003cspan class=\"pl-smi\"\u003eBitReader\u003c/span\u003e\u003cspan class=\"pl-kos\"\u003e,\u003c/span\u003e nodeIndex\u003cspan class=\"pl-kos\"\u003e:\u003c/span\u003e \u003cspan class=\"pl-smi\"\u003eInt\u003c/span\u003e\u003cspan class=\"pl-kos\"\u003e)\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003e-\u0026gt;\u003c/span\u003e \u003cspan class=\"pl-smi\"\u003eUInt8\u003c/span\u003e \u003cspan class=\"pl-kos\"\u003e{\u003c/span\u003e\n \u003cspan class=\"pl-k\"\u003evar\u003c/span\u003e \u003cspan class=\"pl-s1\"\u003eh\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003e=\u003c/span\u003e nodeIndex\n \u003cspan class=\"pl-k\"\u003ewhile\u003c/span\u003e \u003cspan class=\"pl-en\"\u003etree\u003c/span\u003e\u003cspan class=\"pl-kos\"\u003e[\u003c/span\u003eh\u003cspan class=\"pl-kos\"\u003e]\u003c/span\u003e\u003cspan class=\"pl-kos\"\u003e.\u003c/span\u003eright \u003cspan class=\"pl-c1\"\u003e!=\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003e-\u003c/span\u003e\u003cspan class=\"pl-c1\"\u003e1\u003c/span\u003e \u003cspan class=\"pl-kos\"\u003e{\u003c/span\u003e\n \u003cspan class=\"pl-k\"\u003eif\u003c/span\u003e reader\u003cspan class=\"pl-kos\"\u003e.\u003c/span\u003e\u003cspan class=\"pl-en\"\u003ereadBit\u003c/span\u003e\u003cspan class=\"pl-kos\"\u003e(\u003c/span\u003e\u003cspan class=\"pl-kos\"\u003e)\u003c/span\u003e \u003cspan class=\"pl-kos\"\u003e{\u003c/span\u003e\n h \u003cspan class=\"pl-c1\"\u003e=\u003c/span\u003e \u003cspan class=\"pl-en\"\u003etree\u003c/span\u003e\u003cspan class=\"pl-kos\"\u003e[\u003c/span\u003eh\u003cspan class=\"pl-kos\"\u003e]\u003c/span\u003e\u003cspan class=\"pl-kos\"\u003e.\u003c/span\u003eleft\n \u003cspan class=\"pl-kos\"\u003e}\u003c/span\u003e \u003cspan class=\"pl-k\"\u003eelse\u003c/span\u003e \u003cspan class=\"pl-kos\"\u003e{\u003c/span\u003e\n h \u003cspan class=\"pl-c1\"\u003e=\u003c/span\u003e \u003cspan class=\"pl-en\"\u003etree\u003c/span\u003e\u003cspan class=\"pl-kos\"\u003e[\u003c/span\u003eh\u003cspan class=\"pl-kos\"\u003e]\u003c/span\u003e\u003cspan class=\"pl-kos\"\u003e.\u003c/span\u003eright\n \u003cspan class=\"pl-kos\"\u003e}\u003c/span\u003e\n \u003cspan class=\"pl-kos\"\u003e}\u003c/span\u003e\n \u003cspan class=\"pl-k\"\u003ereturn\u003c/span\u003e \u003cspan class=\"pl-en\"\u003eUInt8\u003c/span\u003e\u003cspan class=\"pl-kos\"\u003e(\u003c/span\u003eh\u003cspan class=\"pl-kos\"\u003e)\u003c/span\u003e\n \u003cspan class=\"pl-kos\"\u003e}\u003c/span\u003e\u003c/pre\u003e\u003c/div\u003e\n\u003cp dir=\"auto\"\u003e\u003ccode\u003efindLeafNode()\u003c/code\u003e walks the tree from the root down to the leaf node given by \u003ccode\u003enodeIndex\u003c/code\u003e. At each intermediate node, we read a new bit and then step to the left (bit is 1) or the right (bit is 0). When we get to the leaf node, we simply return its index, which is equal to the original byte value.\u003c/p\u003e\n\u003cp dir=\"auto\"\u003eIn a picture:\u003c/p\u003e\n\u003cp dir=\"auto\"\u003e\u003ca target=\"_blank\" rel=\"noopener noreferrer\" href=\"/rreballos/swift-algorithm-club/blob/master/Huffman%20Coding/Images/Decompression.png\"\u003e\u003cimg src=\"/rreballos/swift-algorithm-club/raw/master/Huffman%20Coding/Images/Decompression.png\" alt=\"How decompression works\" style=\"max-width: 100%;\"\u003e\u003c/a\u003e\u003c/p\u003e\n\u003cp dir=\"auto\"\u003eHere is how we use the decompression method:\u003c/p\u003e\n\u003cdiv class=\"highlight highlight-source-swift notranslate position-relative overflow-auto\" dir=\"auto\" data-snippet-clipboard-copy-content=\" let frequencyTable = huffman1.frequencyTable()\n\n let huffman2 = Huffman()\n let decompressedData = huffman2.decompressData(compressedData, frequencyTable: frequencyTable)\n\n let s2 = String(data: decompressedData, encoding: NSUTF8StringEncoding)!\"\u003e\u003cpre\u003e \u003cspan class=\"pl-k\"\u003elet\u003c/span\u003e \u003cspan class=\"pl-s1\"\u003efrequencyTable\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003e=\u003c/span\u003e huffman1\u003cspan class=\"pl-kos\"\u003e.\u003c/span\u003e\u003cspan class=\"pl-en\"\u003efrequencyTable\u003c/span\u003e\u003cspan class=\"pl-kos\"\u003e(\u003c/span\u003e\u003cspan class=\"pl-kos\"\u003e)\u003c/span\u003e\n\n \u003cspan class=\"pl-k\"\u003elet\u003c/span\u003e \u003cspan class=\"pl-s1\"\u003ehuffman2\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003e=\u003c/span\u003e \u003cspan class=\"pl-en\"\u003eHuffman\u003c/span\u003e\u003cspan class=\"pl-kos\"\u003e(\u003c/span\u003e\u003cspan class=\"pl-kos\"\u003e)\u003c/span\u003e\n \u003cspan class=\"pl-k\"\u003elet\u003c/span\u003e \u003cspan class=\"pl-s1\"\u003edecompressedData\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003e=\u003c/span\u003e huffman2\u003cspan class=\"pl-kos\"\u003e.\u003c/span\u003e\u003cspan class=\"pl-en\"\u003edecompressData\u003c/span\u003e\u003cspan class=\"pl-kos\"\u003e(\u003c/span\u003ecompressedData\u003cspan class=\"pl-kos\"\u003e,\u003c/span\u003e frequencyTable\u003cspan class=\"pl-kos\"\u003e:\u003c/span\u003e frequencyTable\u003cspan class=\"pl-kos\"\u003e)\u003c/span\u003e\n\n \u003cspan class=\"pl-k\"\u003elet\u003c/span\u003e \u003cspan class=\"pl-s1\"\u003es2\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003e=\u003c/span\u003e \u003cspan class=\"pl-en\"\u003eString\u003c/span\u003e\u003cspan class=\"pl-kos\"\u003e(\u003c/span\u003edata\u003cspan class=\"pl-kos\"\u003e:\u003c/span\u003e decompressedData\u003cspan class=\"pl-kos\"\u003e,\u003c/span\u003e encoding\u003cspan class=\"pl-kos\"\u003e:\u003c/span\u003e NSUTF8StringEncoding\u003cspan class=\"pl-kos\"\u003e)\u003c/span\u003e!\u003c/pre\u003e\u003c/div\u003e\n\u003cp dir=\"auto\"\u003eFirst we get the frequency table from somewhere (in this case the \u003ccode\u003eHuffman\u003c/code\u003e object we used to encode the data) and then call \u003ccode\u003edecompressData()\u003c/code\u003e. The string that results should be equal to the one we compressed in the first place.\u003c/p\u003e\n\u003cp dir=\"auto\"\u003ewe can see how this works in more detail in the Playground.\u003c/p\u003e\n\u003cdiv class=\"markdown-heading\" dir=\"auto\"\u003e\u003ch2 tabindex=\"-1\" class=\"heading-element\" dir=\"auto\"\u003eSee also\u003c/h2\u003e\u003ca id=\"user-content-see-also\" class=\"anchor\" aria-label=\"Permalink: See also\" href=\"#see-also\"\u003e\u003csvg class=\"octicon octicon-link\" viewBox=\"0 0 16 16\" version=\"1.1\" width=\"16\" height=\"16\" aria-hidden=\"true\"\u003e\u003cpath d=\"m7.775 3.275 1.25-1.25a3.5 3.5 0 1 1 4.95 4.95l-2.5 2.5a3.5 3.5 0 0 1-4.95 0 .751.751 0 0 1 .018-1.042.751.751 0 0 1 1.042-.018 1.998 1.998 0 0 0 2.83 0l2.5-2.5a2.002 2.002 0 0 0-2.83-2.83l-1.25 1.25a.751.751 0 0 1-1.042-.018.751.751 0 0 1-.018-1.042Zm-4.69 9.64a1.998 1.998 0 0 0 2.83 0l1.25-1.25a.751.751 0 0 1 1.042.018.751.751 0 0 1 .018 1.042l-1.25 1.25a3.5 3.5 0 1 1-4.95-4.95l2.5-2.5a3.5 3.5 0 0 1 4.95 0 .751.751 0 0 1-.018 1.042.751.751 0 0 1-1.042.018 1.998 1.998 0 0 0-2.83 0l-2.5 2.5a1.998 1.998 0 0 0 0 2.83Z\"\u003e\u003c/path\u003e\u003c/svg\u003e\u003c/a\u003e\u003c/div\u003e\n\u003cp dir=\"auto\"\u003e\u003ca href=\"https://en.wikipedia.org/wiki/Huffman_coding\" rel=\"nofollow\"\u003eHuffman coding at Wikipedia\u003c/a\u003e\u003c/p\u003e\n\u003cp dir=\"auto\"\u003eThe code is loosely based on Al Stevens' C Programming column from Dr.Dobb's Magazine, February 1991 and October 1992.\u003c/p\u003e\n\u003cp dir=\"auto\"\u003e\u003cem\u003eWritten for Swift Algorithm Club by Matthijs Hollemans\u003c/em\u003e\u003c/p\u003e\n\u003c/article\u003e","errorMessage":null,"headerInfo":{"toc":[{"level":1,"text":"Huffman Coding","anchor":"huffman-coding","htmlText":"Huffman Coding"},{"level":2,"text":"How it works","anchor":"how-it-works","htmlText":"How it works"},{"level":2,"text":"The code","anchor":"the-code","htmlText":"The code"},{"level":2,"text":"The frequency table","anchor":"the-frequency-table","htmlText":"The frequency table"},{"level":2,"text":"The tree","anchor":"the-tree","htmlText":"The tree"},{"level":2,"text":"Compression","anchor":"compression","htmlText":"Compression"},{"level":2,"text":"Decompression","anchor":"decompression","htmlText":"Decompression"},{"level":2,"text":"See also","anchor":"see-also","htmlText":"See also"}],"siteNavLoginPath":"/login?return_to=https%3A%2F%2Fgithub.com%2Frreballos%2Fswift-algorithm-club%2Ftree%2Fmaster%2FHuffman%2520Coding"}},"totalCount":5,"showBranchInfobar":true},"fileTree":{"":{"items":[{"name":".github","path":".github","contentType":"directory"},{"name":"3Sum and 4Sum","path":"3Sum and 4Sum","contentType":"directory"},{"name":"AVL Tree","path":"AVL Tree","contentType":"directory"},{"name":"All-Pairs Shortest Paths","path":"All-Pairs Shortest Paths","contentType":"directory"},{"name":"Array2D","path":"Array2D","contentType":"directory"},{"name":"B-Tree","path":"B-Tree","contentType":"directory"},{"name":"Binary Search Tree","path":"Binary Search Tree","contentType":"directory"},{"name":"Binary Search","path":"Binary Search","contentType":"directory"},{"name":"Binary Tree","path":"Binary Tree","contentType":"directory"},{"name":"Bit Set","path":"Bit Set","contentType":"directory"},{"name":"Bloom Filter","path":"Bloom Filter","contentType":"directory"},{"name":"Bounded Priority Queue","path":"Bounded Priority Queue","contentType":"directory"},{"name":"Boyer-Moore-Horspool","path":"Boyer-Moore-Horspool","contentType":"directory"},{"name":"Breadth-First Search","path":"Breadth-First Search","contentType":"directory"},{"name":"Brute-Force String Search","path":"Brute-Force String Search","contentType":"directory"},{"name":"Bubble Sort","path":"Bubble Sort","contentType":"directory"},{"name":"Bucket Sort","path":"Bucket Sort","contentType":"directory"},{"name":"Closest Pair","path":"Closest Pair","contentType":"directory"},{"name":"Comb Sort","path":"Comb Sort","contentType":"directory"},{"name":"Combinatorics","path":"Combinatorics","contentType":"directory"},{"name":"Convex Hull","path":"Convex Hull","contentType":"directory"},{"name":"Count Occurrences","path":"Count Occurrences","contentType":"directory"},{"name":"Counting Sort","path":"Counting Sort","contentType":"directory"},{"name":"Depth-First Search","path":"Depth-First Search","contentType":"directory"},{"name":"Deque","path":"Deque","contentType":"directory"},{"name":"Dijkstra Algorithm","path":"Dijkstra Algorithm","contentType":"directory"},{"name":"DiningPhilosophers","path":"DiningPhilosophers","contentType":"directory"},{"name":"Egg Drop Problem","path":"Egg Drop Problem","contentType":"directory"},{"name":"Encode and Decode Tree","path":"Encode and Decode Tree","contentType":"directory"},{"name":"Fixed Size Array","path":"Fixed Size Array","contentType":"directory"},{"name":"Fizz Buzz","path":"Fizz Buzz","contentType":"directory"},{"name":"GCD","path":"GCD","contentType":"directory"},{"name":"Genetic","path":"Genetic","contentType":"directory"},{"name":"Graph","path":"Graph","contentType":"directory"},{"name":"Hash Set","path":"Hash Set","contentType":"directory"},{"name":"Hash Table","path":"Hash Table","contentType":"directory"},{"name":"Hashed Heap","path":"Hashed Heap","contentType":"directory"},{"name":"HaversineDistance","path":"HaversineDistance","contentType":"directory"},{"name":"Heap Sort","path":"Heap Sort","contentType":"directory"},{"name":"Heap","path":"Heap","contentType":"directory"},{"name":"Huffman Coding","path":"Huffman Coding","contentType":"directory"},{"name":"Images","path":"Images","contentType":"directory"},{"name":"Insertion Sort","path":"Insertion Sort","contentType":"directory"},{"name":"Introsort","path":"Introsort","contentType":"directory"},{"name":"K-Means","path":"K-Means","contentType":"directory"},{"name":"Karatsuba Multiplication","path":"Karatsuba Multiplication","contentType":"directory"},{"name":"Knuth-Morris-Pratt","path":"Knuth-Morris-Pratt","contentType":"directory"},{"name":"Kth Largest Element","path":"Kth Largest Element","contentType":"directory"},{"name":"LRU Cache","path":"LRU Cache","contentType":"directory"},{"name":"Linear Regression","path":"Linear Regression","contentType":"directory"},{"name":"Linear Search","path":"Linear Search","contentType":"directory"},{"name":"Linked List","path":"Linked List","contentType":"directory"},{"name":"Longest Common Subsequence","path":"Longest Common Subsequence","contentType":"directory"},{"name":"Merge Sort","path":"Merge Sort","contentType":"directory"},{"name":"Miller-Rabin Primality Test","path":"Miller-Rabin Primality Test","contentType":"directory"},{"name":"Minimum Edit Distance","path":"Minimum Edit Distance","contentType":"directory"},{"name":"Minimum Spanning Tree (Unweighted)","path":"Minimum Spanning Tree (Unweighted)","contentType":"directory"},{"name":"Minimum Spanning Tree","path":"Minimum Spanning Tree","contentType":"directory"},{"name":"MinimumCoinChange","path":"MinimumCoinChange","contentType":"directory"},{"name":"Monty Hall Problem","path":"Monty Hall Problem","contentType":"directory"},{"name":"Multiset","path":"Multiset","contentType":"directory"},{"name":"Myers Difference Algorithm","path":"Myers Difference Algorithm","contentType":"directory"},{"name":"Naive Bayes Classifier","path":"Naive Bayes Classifier","contentType":"directory"},{"name":"Octree","path":"Octree","contentType":"directory"},{"name":"Ordered Array","path":"Ordered Array","contentType":"directory"},{"name":"Ordered Set","path":"Ordered Set","contentType":"directory"},{"name":"Palindromes","path":"Palindromes","contentType":"directory"},{"name":"Points Lines Planes","path":"Points Lines Planes","contentType":"directory"},{"name":"Priority Queue","path":"Priority Queue","contentType":"directory"},{"name":"QuadTree","path":"QuadTree","contentType":"directory"},{"name":"Queue","path":"Queue","contentType":"directory"},{"name":"Quicksort","path":"Quicksort","contentType":"directory"},{"name":"Rabin-Karp","path":"Rabin-Karp","contentType":"directory"},{"name":"Radix Sort","path":"Radix Sort","contentType":"directory"},{"name":"Radix Tree","path":"Radix Tree","contentType":"directory"},{"name":"Red-Black Tree","path":"Red-Black Tree","contentType":"directory"},{"name":"Ring Buffer","path":"Ring Buffer","contentType":"directory"},{"name":"Rootish Array Stack","path":"Rootish Array Stack","contentType":"directory"},{"name":"Run-Length Encoding","path":"Run-Length Encoding","contentType":"directory"},{"name":"Segment Tree","path":"Segment Tree","contentType":"directory"},{"name":"Select Minimum Maximum","path":"Select Minimum Maximum","contentType":"directory"},{"name":"Selection Sampling","path":"Selection Sampling","contentType":"directory"},{"name":"Selection Sort","path":"Selection Sort","contentType":"directory"},{"name":"Set Cover (Unweighted)","path":"Set Cover (Unweighted)","contentType":"directory"},{"name":"Shell Sort","path":"Shell Sort","contentType":"directory"},{"name":"Shortest Path (Unweighted)","path":"Shortest Path (Unweighted)","contentType":"directory"},{"name":"Shuffle","path":"Shuffle","contentType":"directory"},{"name":"Shunting Yard","path":"Shunting Yard","contentType":"directory"},{"name":"Simulated annealing","path":"Simulated annealing","contentType":"directory"},{"name":"Single-Source Shortest Paths (Weighted)","path":"Single-Source Shortest Paths (Weighted)","contentType":"directory"},{"name":"Singly Linked List","path":"Singly Linked List","contentType":"directory"},{"name":"Skip-List","path":"Skip-List","contentType":"directory"},{"name":"Slow Sort","path":"Slow Sort","contentType":"directory"},{"name":"Sorted Set","path":"Sorted Set","contentType":"directory"},{"name":"Sparse Table","path":"Sparse Table","contentType":"directory"},{"name":"Splay Tree","path":"Splay Tree","contentType":"directory"},{"name":"Stack","path":"Stack","contentType":"directory"},{"name":"Strassen Matrix Multiplication","path":"Strassen Matrix Multiplication","contentType":"directory"},{"name":"Ternary Search Tree","path":"Ternary Search Tree","contentType":"directory"},{"name":"Threaded Binary Tree","path":"Threaded Binary Tree","contentType":"directory"},{"name":"Topological Sort","path":"Topological Sort","contentType":"directory"},{"name":"Treap","path":"Treap","contentType":"directory"},{"name":"Tree","path":"Tree","contentType":"directory"},{"name":"Trie","path":"Trie","contentType":"directory"},{"name":"Two-Sum Problem","path":"Two-Sum Problem","contentType":"directory"},{"name":"Union-Find","path":"Union-Find","contentType":"directory"},{"name":"Z-Algorithm","path":"Z-Algorithm","contentType":"directory"},{"name":".gitignore","path":".gitignore","contentType":"file"},{"name":".swiftlint.yml","path":".swiftlint.yml","contentType":"file"},{"name":"Algorithm Design.markdown","path":"Algorithm Design.markdown","contentType":"file"},{"name":"Big-O Notation.markdown","path":"Big-O Notation.markdown","contentType":"file"},{"name":"LICENSE.txt","path":"LICENSE.txt","contentType":"file"},{"name":"README.markdown","path":"README.markdown","contentType":"file"},{"name":"Under Construction.markdown","path":"Under Construction.markdown","contentType":"file"},{"name":"What are Algorithms.markdown","path":"What are Algorithms.markdown","contentType":"file"},{"name":"Why Algorithms.markdown","path":"Why Algorithms.markdown","contentType":"file"},{"name":"gfm-render.sh","path":"gfm-render.sh","contentType":"file"},{"name":"install_swiftlint.sh","path":"install_swiftlint.sh","contentType":"file"}],"totalCount":118}},"fileTreeProcessingTime":3.8676909999999998,"foldersToFetch":[],"treeExpanded":true,"symbolsExpanded":false,"csrf_tokens":{"/rreballos/swift-algorithm-club/branches":{"post":"et2ktxEZgNLXp86P8X7nAvQpXmP4FURjdIDnKYkoRhWw1F9nxSS1dbru7qJ9kiFYchUOZawyY6Nm1hmsT_jZdA"},"/rreballos/swift-algorithm-club/branches/fetch_and_merge/master":{"post":"blW5mPgR7e4ZdMSsC6baMIkkVtUf8me36KuRUc9pOx9DAMXgjKJRUqc1uPTEmB6sITrd6A4pQeGw8qytWWx6jQ"},"/rreballos/swift-algorithm-club/branches/fetch_and_merge/master?discard_changes=true":{"post":"ZAyVTWbh0_l8Hu3QmUhuRiWFkuvzDvlVONYwmWAj8B5JWek1ElJvRcJfkYhWdqrajZsZ1uLV3wNgjw1l9iaxjA"}}},"title":"swift-algorithm-club/Huffman Coding at master · rreballos/swift-algorithm-club","appPayload":{"helpUrl":"https://docs.github.com","findFileWorkerPath":"/assets-cdn/worker/find-file-worker-263cab1760dd.js","findInFileWorkerPath":"/assets-cdn/worker/find-in-file-worker-1b17b3e7786a.js","githubDevUrl":null,"enabled_features":{"code_nav_ui_events":false,"react_blob_overlay":false,"accessible_code_button":true}}}
0