Problem 185. Data decompression

Created byTomasz

Like (5)

Solve Later

{"relationships":[{"relationshipType":"http://schemas.mathworks.com/matlab/code/2013/relationships/document","targetMode":"","relationshipId":"rId1","target":"/matlab/document.xml"},{"relationshipType":"http://schemas.mathworks.com/matlab/code/2013/relationships/output","targetMode":"","relationshipId":"rId2","target":"/matlab/output.xml"}],"parts":[{"partUri":"/matlab/document.xml","relationship":[],"contentType":"application/vnd.mathworks.matlab.code.document+xml","content":"<?xml version=\"1.0\" encoding=\"UTF-8\"?>\n<w:document xmlns:w=\"http://schemas.openxmlformats.org/wordprocessingml/2006/main\"><w:body><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:t>A chunk of data is to be 'decompressed'.</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:t>Input:</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"ListParagraph\"/><w:numPr><w:numId w:val=\"1\"/></w:numPr></w:pPr><w:r><w:t>compressed: a row vector of uint8 values. This is the compressed data.</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"ListParagraph\"/><w:numPr><w:numId w:val=\"1\"/></w:numPr></w:pPr><w:r><w:t>table: a cell-array of strings. Each string contains only '1's and '0's and represents a binary code.</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"ListParagraph\"/><w:numPr><w:numId w:val=\"1\"/></w:numPr></w:pPr><w:r><w:t>alphabet: a string containing all possible symbols that may occur in the decompressed data. The symbol at alphabet(x) is encoded with the code at table{x}.</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:t>Output:</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"ListParagraph\"/><w:numPr><w:numId w:val=\"1\"/></w:numPr></w:pPr><w:r><w:t>decompressed: a string with the decoded message.</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:t>Example:</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"code\"/></w:pPr><w:r><w:t><![CDATA[compressed=[93,85,127]\ntable={'1','010'}\nalphabet='al'\n==> decompressed = 'laaalalalaaaaaaa']]></w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:t>because:</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"code\"/></w:pPr><w:r><w:t><![CDATA[[93,85,127] = '01011101 01010101 01111111' in binary\ndecoded from left to right:\n'010 1 1 1 010 1 010 1 010 1 1 1 1 1 1 1'\n= l a a a l a l a l a a a a a a a]]></w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:t>Remarks: The message is such that always exactly all bits of</w:t></w:r><w:r><w:t> </w:t></w:r><w:r><w:rPr><w:rFonts w:cs=\"monospace\"/></w:rPr><w:t>compressed</w:t></w:r><w:r><w:t> are used. The solution is unique (see</w:t></w:r><w:r><w:t> </w:t></w:r><w:hyperlink w:docLocation=\"http://en.wikipedia.org/wiki/Prefix_code\"><w:r><w:t>prefix-free code</w:t></w:r></w:hyperlink><w:r><w:t>).</w:t></w:r></w:p></w:body></w:document>"},{"partUri":"/matlab/output.xml","contentType":"text/xml","content":"<?xml version=\"1.0\" encoding=\"UTF-8\" standalone=\"no\" ?><embeddedOutputs><metaData><evaluationState>manual</evaluationState><layoutState>code</layoutState><outputStatus>ready</outputStatus></metaData><outputArray type=\"array\"/><regionArray type=\"array\"/></embeddedOutputs>"}]}

A chunk of data is to be 'decompressed'.Input:<ul><li>compressed: a row vector of uint8 values. This is the compressed data.</li><li>table: a cell-array of strings. Each string contains only '1's and '0's and represents a binary code.</li><li>alphabet: a string containing all possible symbols that may occur in the decompressed data. The symbol at alphabet(x) is encoded with the code at table{x}.</li></ul>Output:<ul><li>decompressed: a string with the decoded message.</li></ul>Example:<pre class="language-matlab">compressed=[93,85,127] table={'1','010'} alphabet='al' ==> decompressed = 'laaalalalaaaaaaa' </pre>because:<pre class="language-matlab">[93,85,127] = '01011101 01010101 01111111' in binary decoded from left to right: '010 1 1 1 010 1 010 1 010 1 1 1 1 1 1 1' = l a a a l a l a l a a a a a a a </pre>Remarks: The message is such that always exactly all bits of <tt>compressed</tt> are used. The solution is unique (see <a href="http://en.wikipedia.org/wiki/Prefix_code">prefix-free code</a>).

Solve

Solution Stats

361 Solutions
68 Solvers

LastSolutionsubmitted on Jun 07, 2022

Last 200 Solutions

Problem Comments

2 Comments

2 Comments

Tomaszon 1 Feb 2012

Update: two randomized tests added to the suite.

Nikolaos Nikolaouon 28 Oct 2020

i donnot understand the uint8 twist :/

Problem Recent Solvers68

Problem Tags

社区Treasure Hunt

Find the treasures in MATLAB Central and discover how the community can help you!

Start Hunting!

Problem 185. Data decompression

Solution Stats

Last 200 Solutions

Problem Comments

Problem Recent Solvers68

Suggested Problems

More from this Author7

Problem Tags

社区Treasure Hunt

Problem 185. Data decompression

Solution Stats

Last 200 Solutions

Problem Comments

Problem Recent Solvers68

Suggested Problems

More from this Author7

Problem Tags

社区Treasure Hunt

Players