Let’s do some PLAIN SQL text compression…! (Part II)

OK – It’s time to complete what we started last month...! ...and, of course, it's nice to see you back... :)

First, let's remember the challenge: Let’s do some plain SQL text compression (in CUBRID, of course..)

So you have a table which contains plain, “normal” English text, let’s say the daily employees status report and:

• You don’t have an issue with the database response speed, but you have an issue with the big data(base) size
• The solution you came up with is obviously to compress its content, using some text compression algorithm
• You can’t use stored procedures! (as they are not standard plain SQL)
• You must achieve compression only by using SQL statements and tables and what else a “standard” DMBS is offering!
• You can use as many SQL statements as you want!
• Once gain – you can use only standard SQL statements (including any well-known functions and data manipulation commands)

Just in case you forgot were we arrived in the first part, please make sure you remember...

The last thing we did was to create a “compressor" table, with a row number, an input word and the "compressed" value for the input word, using the following SQL to calculate the “compressed” value:

UPDATE compressor SET output_word = CONCAT(CHR(32 + CAST(SUBSTR(TO_CHAR(id, '0000'), 1,2) AS INT)), CHR(32 + CAST(SUBSTR(TO_CHAR(id, '0000'), 3,2) AS INT)))

Let's continue from there!

3. Next, I created a temporary table – “words” - to hold text-to-be-compressed words and I created the SQL statement to populate the table:

4. Then, I replaced each “known” word from the "words" table with its compressed equivalent:

5. Finally, the compressed text is created from the “words” table, using the GROUP_CONCAT function:

That's all, folks!... …I will leave the “revert”(= "uncompress") algorithm steps to you! :)

Of course, my final question (and challenge for you) is: What is your solution? Have you found a better one…? :)

See you next time – Bye-bye!

/Dee

P.S. I almost forgot to tell you about a much simpler, a no-brainer solution! A solution which works, but it’s quite ugly…

Here it is: You simply execute a chained REPLACE command (using multiple SQLs or just a big-big-big one), using as many times as you want the most common used English words you choose to hard-code.

For example, you could do:

SELECT 'John Doe is the man. He is better, taller and stronger!' INTO :input_txt;

SELECT :input_txt INTO :output_txt;

SELECT REPLACE(:output_txt, '. ', '^0') INTO :output_txt;

SELECT REPLACE(:output_txt, ' of ', '^1') INTO :output_txt;

SELECT REPLACE(:output_txt, ' to ', '^2') INTO :output_txt;

SELECT REPLACE(:output_txt, ' is ', '^3') INTO :output_txt;

… and so on ...

This would obviously ensure (some) compression, and the more words you choose, the better compression you have...
...but yes, it’s far-far-far from looking good or optimal…...but in the end, if you refer strictly to the problem of achieving some level of a text compression, it is probably the simplest solution after all...

Let’s do some PLAIN SQL text compression…! (Part I)

OK – It’s fun time again...! :)

The challenge I got for you now is: Let’s do some plain SQL text compression (in CUBRID, of course..)!

What does this challenge means exactly…? Let’s imagine that:

• You have a table which contains plain, “normal” English text, let’s say the daily employees status report
• You don’t have an issue with the database response speed, but you have an issue with the big data(base) size
• The solution you came up with is obviously to compress its content, using some text compression algorithm
• You can’t use stored procedures! (as they are not standard plain SQL)
• You must achieve compression only by using SQL statements and tables and what else a “standard” DMBS is offering!
• You can use as many SQL statements as you want!
• Once gain – you can use only standard SQL statements (including any well-known functions and data manipulation commands)

(Yes, I know! – The scenario it’s not quite for real – but please remember the fun part… …and that you will improve your SQL skills as well… :D)

Hmm – so what do you say…? Are you up for this challenge…? (And you can use whatever DBMS you want for this - CUBRID is just my obvious choice because this blog is about CUBRID…)

If you are up to the challenge, then take 10 min and think about it… After that, you should read the solution below…

When I start analyzing the problem, here is what it crossed my mind:

• It can’t be a complicated compression algorithm, as we are limited to just some SQL statements and the standard SQL functions
• It must be a lossless compression algorithm

After doing some research, I realized that one way to go is to implement a most “common” English words replacement algorithm, which will work like this:

• Get a list of N most common used English words
• Figure out a way to replace each of the word with some “shorter data” – a number or a string we define or something similar.

As usually there are just some hundreds words we used on a daily basis to communicate – there is no doubt that we can reach a compression here! The “ratio”...? Well, it depends on the text, obviously.

OK – I will spare you the details about the time I spent, searching for all kind of solutions do this in plain SQL…! :)

The big-big problem here is that in plain SQL you can’t ITERATE! There is no FOR, there is no WHILE! You can’t transform characters “one by one”…

After analyzing and analyzing again and so on, I finally found a way to do it – EURIKA! :)

Here is my solution:

1. Store the words I intend to replace in a (dictionary words replace) table.
2. Create a hard-coded “compressed” value for each of the words.
3. Split the text I will compress into words and store the words in a (temporary) table, using the REPLACE function.
4. Perform an UPDATE on the temporary table (which contains our text words), replacing each “known” word with its shorter version.
5. Use the GROUP_CONCAT function to reassemble the new/compressed text.

And here are some details and screenshots:

1. I created a CUBRID table which hold the common-used English words. I used the lists available here.

2. I decided to use a compression algorithm based on the row number of each stored “common” word.

As these words are no more than thousands, I can simply replace each word by an integer 2-byte value, right? :D

Using this compression rule, we can go up to 256 x 256 =65.536 words! This is more than enough to compress any usual English text!

So I added 2 more columns to the “compressor" table: the row number and the compressed value for each word, using the following SQL to calculate the “compressed” value:

UPDATE compressor SET output_word = CONCAT(CHR(32 + CAST(SUBSTR(TO_CHAR(id, '0000'), 1,2) AS INT)), CHR(32 + CAST(SUBSTR(TO_CHAR(id, '0000'), 3,2) AS INT)))

...OK! ...that's enough for now... :)
The 2nd part of this post will be published next month - so you have enough time to come up with your own solution or to finish the one I started to show here...

So see you with the next part soon... Bye-bye!

/Dee