Блог пользователя amanmittal

Grid Compression
Автор amanmittal, 10 лет назад, По-английски

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

  • Проголосовать: нравится
  • +1
  • Проголосовать: не нравится

»
10 лет назад, # |
← Rev. 6   Проголосовать: нравится 0 Проголосовать: не нравится 
`- ....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

→ Ответить
»
4 года назад, # |
← Rev. 2   Проголосовать: нравится -18 Проголосовать: не нравится 

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.
→ Ответить