RSS Feed
Download our iPhone app
Browse DevX
Sign up for e-mail newsletters from DevX


Decompress Binary Messages Using Directed Graphs : Page 5

When you're faced with a number of possible solutions to a problem, determining the optimal one is a critical task. Follow a practical example for optimization tasks using stored procedures and graphs.

Final Result
As you can see, 55 combinations exist for the sample input 10000010011110011. Before evaluating them, let's create a table that will store 218 = 262144 binary numbers (see Listing 6).

(You need to create and load this table only once and then you just use it.)

Then you need to compile and execute the stored procedure spu_getFinalAnswer (see Listing 7) as follows, where 32 is the length of the original message and 26 is the number of 1's in the original message:

EXEC spu_getFinalAnswer @L = 32, @N = 26

The final result will be:

numID       originBinPath              finalResult 
----------- -------------------------- ----------------------------------
1           100000,100,111100,11       1000,00,1,00,1111,00,2

This answer is correct for the sample input 10000010011110011. There is only one combination. The value of the column finalResult is divided into the portions (sub-messages). Each portion is a binary number that substitutes the corresponding amount of 1's in the original message. Thus, 1000,00,1,00,1111,00,2 means (1000 + 1 + 1111) 2 + 210 = 8 + 1 + 15 + 2 = 26 ones and six zeros.

To test two other sample inputs, you need to run all the procedures in the following sequence:

DECLARE @comprMsg varchar(40), @L int, @N int;
SELECT @comprMsg = '1010101', @L = 9, @N = 7;

EXEC spu_splitComprMsg @comprMsg
EXEC spu_generateAllCombinations
EXEC spu_convertCombinationsToBinary @comprMsg
-- stored procedure spu_processSplitPath should be created once
EXEC spu_processBinForest
-- table binFinal should be created once
EXEC spu_getFinalAnswer @L, @N; 

For the sample input, the correct answer would be:

numID       originBinPath      finalResult
----------- ------------------ --------------
1           1010,10,1          101,0,1,0,1
2           10,1010,1          1,0,101,0,1
3           10,10,101          1,0,1,0,101 

You can validate a third sample using the same procedures and the following parameters:

@comprMsg = '111111', @L = 14, @N = 14;

Be careful, however, when you try to run the procedures for the maximal or near-maximal number of portions. It may take you a few hours to get the answer for the compressed message '1010101010101010101010101010101010101010'.

Alex Kozak is a senior DBA/analyst working for SAP Canada. He has more than 15 years of database and programming experience. Microsoft has included some of his articles in the MSDN Library.
Email AuthorEmail Author
Close Icon
Thanks for your registration, follow us on our social networks to keep up-to-date