Login | Register   
LinkedIn
Google+
Twitter
RSS Feed
Download our iPhone app
TODAY'S HEADLINES  |   ARTICLE ARCHIVE  |   FORUMS  |   TIP BANK
Browse DevX
Sign up for e-mail newsletters from DevX


advertisement
 

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.


advertisement
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.
Comment and Contribute

 

 

 

 

 


(Maximum characters: 1200). You have 1200 characters left.

 

 

Sitemap