amanmittal's blog

Grid Compression
By amanmittal, 10 years ago, In English

I have read grid compression from this Quora link. But I didn't get the technique by which a grid can be compressed. I know the implementation of 1-D coordinate compression by using binary search technique, but I am not getting how a 2D grid can be compressed.

Here is the problem that I am trying to solve

  • Vote: I like it
  • +1
  • Vote: I do not like it

»
10 years ago, # |
← Rev. 6   Vote: I like it 0 Vote: I do not like it 
`- ....x...    .x. (1)`
`- ....xxxx  C .xx (1)`
`- ....x... -->.x. (1)`
`- ........    ... (2)`
`- ........   (413)`

where each row/column have they own weight — the number of such equal lines so you can compress the table in 150c from 10^9x10^9 to ~10^3x10^3

→ Reply
»
4 years ago, # |
← Rev. 2   Vote: I like it -18 Vote: I do not like it 

In 1d (line) compression, you find for empty coordinates on the x axis and remove the unnecessary one.

Similarly for 2d (grid), you find first those horizontal lines which are empty and try the compress the grid vertically and after that try to compress the grid horizontally by finding the empty vertical lines.
NOTE : '#' means an element is present, '.' means empty space.
 Eg : 1D

 #....#...## -> ####

Eg : 2D

 ###         ### 
 ...   ->    #.# 
 #.#             

vertical compression by removing the 2nd horizontal line

 #..          #..
 .#.    ->    .#.
 ..#          ..#


No compression in this case as no vertical and horizontal lines are empty.
→ Reply