Login | Register   
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 4

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
Sub-Messages Decomposition
As previously mentioned, any sub-message (portion) that has more than one zero at the end can be interpreted as a set, where each element consists of a binary number n, substituting n 1's, and a sequence of 0's. For example, the first portion in binPath 100000,100,111100,11 (id = 8) can be interpreted as follows:

10000,0 – substitution for sixteen 1's and one zero; 1000,00 - substitution for eight 1's and two 0's; 100,000 - substitution for four 1's and three 0's; 10,0000 – no substitution (one 1 and five 0's); 1,00000 – no substitution (one 1 and five 0's)

In fact, the last two cases (10,0000 and 1,00000) are the same. Binary number 102 cannot be considered a substitution for two 1's because such a replacement wouldn't shorten the original message. Therefore, splitting sub-messages with zeros at the end, you can exclude one of two combinations (1,0…0 or 10,0…0) from the final result. For instance, binPath 100000,100,111100,11 (id = 8) can produce the following combinations:



10000,0,100,111100,11 1000,00,100,111100,11 100,000,100,111100,11 10,0000,100,111100,11 1,00000,100,111100,11

The last two combinations are identical. One of them can be deleted.

One more situation that should be addressed as a special case is when a sub-message is equal to 11 (as in the last portion of binPath 100000,100,111100,11). Indeed, 11 can be interpreted as two 1's in the original message, in which case the replacement isn't necessary; or as a substitution of three 1's in the original message by binary number 11 (310).

To process all these situations and further split the sub-messages, I created two stored procedures: spu_processSplitPath (see Listing 4) and spu_processBinForest (see Listing 5).

Compiling both procedures and executing spu_processBinForest produces the following result:

id binPath result ----------- -------------------------- --------------------------- 1 10000010011110011 10000010011110011 2 100000100111100,11 10000010011110,0,2 3 100000100111100,11 10000010011110,0,3 4 100000100111100,11 1000001001111,00,2 5 100000100111100,11 1000001001111,00,3 6 100000100,11110011 10000010,0,11110011 7 100000100,11110011 1000001,00,11110011 8 100000100,111100,11 10000010,0,11110,0,2 9 100000100,111100,11 10000010,0,1111,00,2 10 100000100,111100,11 1000001,00,11110,0,2 11 100000100,111100,11 1000001,00,1111,00,2 12 100000100,111100,11 10000010,0,11110,0,3 13 100000100,111100,11 10000010,0,1111,00,3 14 100000100,111100,11 1000001,00,11110,0,3 15 100000100,111100,11 1000001,00,1111,00,3 16 100000,10011110011 10000,0,10011110011 17 100000,10011110011 1000,00,10011110011 18 100000,10011110011 100,000,10011110011 19 100000,10011110011 1,00000,10011110011 20 100000,100111100,11 10000,0,10011110,0,2 21 100000,100111100,11 1000,00,10011110,0,2 22 100000,100111100,11 100,000,10011110,0,2 23 100000,100111100,11 1,00000,10011110,0,2 24 100000,100111100,11 10000,0,1001111,00,2 25 100000,100111100,11 1000,00,1001111,00,2 26 100000,100111100,11 100,000,1001111,00,2 27 100000,100111100,11 1,00000,1001111,00,2 28 100000,100111100,11 10000,0,10011110,0,3 29 100000,100111100,11 1000,00,10011110,0,3 30 100000,100111100,11 100,000,10011110,0,3 31 100000,100111100,11 1,00000,10011110,0,3 32 100000,100111100,11 10000,0,1001111,00,3 33 100000,100111100,11 1000,00,1001111,00,3 34 100000,100111100,11 100,000,1001111,00,3 35 100000,100111100,11 1,00000,1001111,00,3 36 100000,100,11110011 10000,0,1,00,11110011 37 100000,100,11110011 1000,00,1,00,11110011 38 100000,100,11110011 100,000,1,00,11110011 39 100000,100,11110011 1,00000,1,00,11110011 40 100000,100,111100,11 10000,0,1,00,11110,0,2 41 100000,100,111100,11 1000,00,1,00,11110,0,2 42 100000,100,111100,11 100,000,1,00,11110,0,2 43 100000,100,111100,11 1,00000,1,00,11110,0,2 44 100000,100,111100,11 10000,0,1,00,1111,00,2 45 100000,100,111100,11 1000,00,1,00,1111,00,2 46 100000,100,111100,11 100,000,1,00,1111,00,2 47 100000,100,111100,11 1,00000,1,00,1111,00,2 48 100000,100,111100,11 10000,0,1,00,11110,0,3 49 100000,100,111100,11 1000,00,1,00,11110,0,3 50 100000,100,111100,11 100,000,1,00,11110,0,3 51 100000,100,111100,11 1,00000,1,00,11110,0,3 52 100000,100,111100,11 10000,0,1,00,1111,00,3 53 100000,100,111100,11 1000,00,1,00,1111,00,3 54 100000,100,111100,11 100,000,1,00,1111,00,3 55 100000,100,111100,11 1,00000,1,00,1111,00,3 (55 row(s) affected)



Comment and Contribute

 

 

 

 

 


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

 

 

Sitemap