In the world of data compression, Huffman coding is a classic algorithm. However, it is notoriously fragile: a single bit error during transmission can lead to "synchronization loss," causing the decoder to misinterpret the entire remaining sequence.
In this problem, you are tasked with recovering a message from a corrupted Huffman-encoded bitstream.
The Setup:
1.Dictionary: You are given a cell array of binary strings (e.g., {'0', '10', '11'} ). The i-th element corresponds to the i-th letter of the alphabet (1->'A', 2-> 'B', etc.).
2.Bitstream: A string of '0's and '1's. This stream contains exactly one flipped bit (an error where a 0 became a 1 or vice versa).
3.ValidWords: A cell array of possible original strings (e.g.,{'ABC', 'BBA'}).
The Rules:
- The original (pre-corruption) bitstream, when decoded, results in one of the strings listed in ValidWords.
- A decoded string is only valid if the bitstream can be completely partitioned into codewords from the dictionary with no bits left over.
- You must identify the single erroneous bit, flip it back, and return the corrected decoded string.
Input:
- Dictionary: 1 x N cell array of bit strings.
- Bitstream: A string of '0's and '1's.
- ValidWords: A cell array of strings.
Output:
- decodedWords: The corrected string (must be an element of ValidWords).
Example:
- Dictionary = {'0', '10', '11'} (A = '0', B = '10', C = '11')
- ValidWords = {'ABC', 'BBA', 'ACC'}
- Bitstream = '00011'
Analysis:
- If we flip the 1st bit: '10011' -> 'B' + '0' + '11' = 'BAC' (Not in ValidWords)
- If we flip the 2nd bit: '01011' -> '0' + '10' + '11' = 'ABC' ( Matches ValidWords! )
- Result: 'ABC'
Solution Stats
Problem Comments
2 Comments
Solution Comments
Show comments
Loading...
Problem Recent Solvers3
Suggested Problems
More from this Author19
Problem Tags
Community Treasure Hunt
Find the treasures in MATLAB Central and discover how the community can help you!
Start Hunting!
Test case 3 has two valid solutions.
Testcase has been updated Xd