Member Avatar for ffishy

hi all, I need some help w.r.t. arrays and it's representation. My assignment was to think of an idea(s) to redesign a 2-dimensional array that is a compressed form of binary patterns.

e.g. {3,9,4,2} is compressed form and it's decompressed form is 111000000000111100. Then same for next few rows.

I did some reading up and found out that it is called run-length encoding. The question requires me to redesign the array such that through a decompression method, it will give the same binary pattern.

I was thinking that every number is significant in it's representation and hence, the number of entries should remain the same.

Does anyone have any idea how a smaller array can be implemented to show the same data after decompression?

  • 3 Contributors
  • 5 Replies
  • 125 Views
  • 16 Hours Discussion Span
  • Latest Post Latest Post by griswolf

Dani AI

Generated

A couple of practical, lossless ideas that complement the thread:

First, if many rows repeat or are drawn from a small set, store a dictionary of unique rows and keep one small index per original row. This is simple, fast to decode, and often wins when the number of distinct row patterns is much smaller than the number of rows (addresses the small-data problem mentioned). Use a compact index (fixed-wide or varint) and bit‑pack the dictionary entries.

Second, treat each run-length row as a choice of boundary positions rather than as raw counts. A row that has m runs across a fixed width N can be represented by choosing m-1 boundary positions from N-1 slots; there are C(N-1, m-1) possibilities. Encode the chosen combination as its lexicographic rank (the combinatorial number system) and store that integer instead of a list of counts. For many small N and small m this is often denser than storing m raw integers. Group rows by run-count m to avoid storing m per row.

A minimal example of ranking a sorted list of boundary indices (Python-ish):

from math import comb

def comb_rank(boundaries, N):
    # boundaries: sorted list of k positions in 1..N-1
    rank = 0
    k = len(boundaries)
    prev = 0
    for i, b in enumerate(boundaries):
        for x in range(prev+1, b):
            rank += comb(N - x - 1, k - i - 1)
        prev = b
    return rank

Practical notes: pack the resulting integers tight (bit-fields or varints), group rows with the same m, and deduplicate identical encoded values. If random access or very fast queries are required, consider compressed bitmap libraries (for example Roaring bitmaps) instead of heavy entropy coding. Also watch numeric ranges—combinatorial ranks can grow large and may need big-integer support for big N. This approach complements earlier replies from and while avoiding the per-row header blowup they warned about; it trades a slightly heavier encode/decode step for lower storage when N and m are modest.

References: combinatorial number system (https://en.wikipedia.org/wiki/Combinatorial_number_system), Roaring bitmaps (https://roaringbitmap.org/).

Recommended Answers

All 5 Replies

Member Avatar for Momerath

I was thinking that every number is significant in it's representation and hence, the number of entries should remain the same.

Does anyone have any idea how a smaller array can be implemented to show the same data after decompression?

If the number of entries are the same, then it can't be smaller.

Given that, do some entries end in zeros, that is, {9,3,2,0}? If so, you can look at jagged arrays (Yes, it's a C# page, but it has a good description of jagged arrays).

Member Avatar for griswolf

Do you need to deal with the possibility that the data can start with zero(s)? Generally, RLE has to deal with more than two tokens, so it uses a dictionary header, and outputs both the dictionary index and the repetition for each run of "same token". So, your example would look like "{[0,1]1:3,0:9,1:4,0:2}" or some such. In your case you could just have a 'first digit is' convention so it looks like "{1:3,9,4,2}" or with 5 leading zeros: "{0:5,3,9,4,2}"

You can make it even shorter (if lucky) by finding repeating sequences rather than repeating digits. For instance to encode '1001001001001100100100100100' you might output"{[100,1]0:4,1:1,0:5}". This is a gamble: If you start out using this idea, you may not find enough repetition to 'pay off' the size of the header. Note that for binary data, there are only 4 possible pairs of digits (A:00,B:01,C:10,D:11). You could encode your 11,10,00,00,00,00,11,11,00 as "{D1C1A4D2A1}". One common variation is that a single repetition requires no number, so reduce all the counts by one: "{DCA3D1A}". The same idea applies to triples, quads and (using upper and lower case) 5-bit groups.
Note: no header needed if your convention is ABCD representing 00,01,10,11 respectively.
Note: that by using letters as indices, we can lose the commas.
Note: If you are actually putting this data on the wire, you don't want to spend 7 or 8 bits for every index, every digit of the count and every separator (if any), so this is all more for fun than actual use.

Edited by griswolf because: n/a
Member Avatar for ffishy

The entries do not have zeroes. Thanks for your help though. I've submitted my assignment but I'm still curious.
I wrote something along the lines of using differencing to obtain a smaller array. But explained that there might be data loss and decompression is not complete.

:)

Member Avatar for ffishy

Do you need to deal with the possibility that the data can start with zero(s)? Generally, RLE has to deal with more than two tokens, so it uses a dictionary header, and outputs both the dictionary index and the repetition for each run of "same token". So, your example would look like "{[0,1]1:3,0:9,1:4,0:2}" or some such. In your case you could just have a 'first digit is' convention so it looks like "{1:3,9,4,2}" or with 5 leading zeros: "{0:5,3,9,4,2}"

You can make it even shorter (if lucky) by finding repeating sequences rather than repeating digits. For instance to encode '1001001001001100100100100100' you might output"{[100,1]0:4,1:1,0:5}". This is a gamble: If you start out using this idea, you may not find enough repetition to 'pay off' the size of the header. Note that for binary data, there are only 4 possible pairs of digits (A:00,B:01,C:10,D:11). You could encode your 11,10,00,00,00,00,11,11,00 as "{D1C1A4D2A1}". One common variation is that a single repetition requires no number, so reduce all the counts by one: "{DCA3D1A}". The same idea applies to triples, quads and (using upper and lower case) 5-bit groups. Note that by using letters as indices, we can lose the commas.

Hello there. The array in my assignment had 5 values in every row, some rows having even lesser values. Just to make an observation, do correct me if I'm wrong;
The smaller the amount of data, the harder it is to find a repetitive pattern to compress.

Thanks for your reply, it was insightful.

Member Avatar for griswolf

So: "The smaller the amount of data, the harder it is to find a repetitive pattern to compress.?"
As a general rule, yes.
If every datum is one of a small set of choices, then the compression is possible by stepping up one level. For example, when sending colors, you might just say "'chartreuse' is 0, 'vermilion' is 1, and 'turquoise' is 2. Anything else is spelled out." Every message might have only one color in it, so the message would not seem to be subject to compression, but if you know it always has a color in it, you can compress the color part by using your knowledge of the system.

Be a part of the DaniWeb community

We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.