Better Lookup Table Compression

§1 Introduction

In the previous post[1] I described the techniques I used to compress a lookup table, namely unaccent.rules[2]. While they were fun to explore and implement, something felt off. I felt like we can do better than ~13 KiB. In a comment under my post on Reddit, u/alex-van-02[3] mentioned that it should be possible to produce a much smaller compressed version, and referenced his work[4] on compressing a lookup table for fast character case conversion. After studying the techniques he used, I came up with a new lookup table compression algorithm that performs much better, both in terms of speed and compression. In the following, we will have a look at the new version.

§2 Excessive Padding

The biggest problem in the previous version was the data structure we used to represent a single entry in the lookup table:

1
2
3
4
5
6
7

#define ENTRY_DATA_LEN 8

typedef struct UnaccentEntry {
  uint8_t symb_len;
  uint8_t repl_len;
  uint8_t data[ENTRY_DATA_LEN];
} UnaccentEntry;

It stores the symbol and replacement together in data, which is a field of fixed size. In reality, not all pairs occupy 8 bytes, so a lot of space is wasted, because we pad all entries to the same size. This can be observed from the following distribution by length:

1
2
3

 length |    2 |    3 |    4 |    5 |    6 |    7 |    8
--------+------+------+------+------+------+------+------
  count |   99 |  394 |  728 | 1033 |  348 |   58 |    2

If we were to just store all pairs right next to each other and without any padding in between, we would need 11967 bytes, which is already less than my previous version, even without any compression techniques applied. This makes it crystal clear that we have to approach storage in memory in such a way that any kind of padding in between entries is avoided.

§3 Data properties

Before jumping into the details of the new design, it is important to look at the data and see what properties it has that we can make use of.

First, when looking at compressed entries, I noticed that the symbol part from data was never affected by dictionary encoding. This is bad, because there are actually a lot of repeating byte pairs in symbols, since many of them are consecutive and therefore have the same prefix. Unfortunately, the modified algorithm for byte pair encoding considers only the byte pairs from the longest entries only. As a result, it can't exploit the redundancy present in symbols. This indicates that maybe we should look into compressing symbols separately.

Second, symbols are very sparse. In total, we have 2662 symbols, but they are spread across the unicode codepoint range 161..127273 (¡ and 🄩) with big gaps in between. On average, there is one symbol for every ~47 codepoints. This might be the place where we apply techniques similar to those in u/alex-van-02's post and get rid of the biggest gaps.

Third, not all replacements are unique. Quite the opposite actually. Out of 2662 replacements, only 453 are unique (~17%). This means that we can deduplicate replacements and store an offset instead of the full replacement, thus saving space on that.

§4 Storing Symbols

My idea was to store symbols using their unicode codepoint instead of the UTF-8 encoding. By doing that, we already reduce the space needed from at most 4 bytes to at most 3 bytes. For example, the maximum symbol 🄩 requires 32 bits (4 bytes) when UTF-8 encoded. On the other hand, its codepoint is 127273, which requires only 17 bits (3 bytes).

Those 17 bits are annoyingly close to 16 bits (2 bytes). It would be great if we could do something to represent a symbol in just 16 bits or less. This is where we exploit the fact that symbols are sparse and that we can get rid of the biggest gaps.

First, let's look at where and how big the gaps are. This small snippet prints all symbol codepoints and the gaps between them:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

codes = [
    ord(symb.decode())
    for symb, repl in entries
]

a = codes[0]
for code in codes:
    gap = code - a
    if gap > 1:
        print(f'------ {gap=}')
    a = code
    print(code)

Here is a sample:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

[...]
1105
------ gap=6319
7424
[...]
9397
------ gap=1232
10629
[...]
13279
------ gap=29521
42800
[...]

To produce a more compact representation for symbols, we could split the range 161..127273 into smaller ranges, so that the value can be stored using less bits, by storing only the offset from the start of the range. Ideally, the smaller ranges must be chosen in such a way that they don't contain any of the big gaps. This script will find these ranges:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10

a = codes[0]
b = a
ranges = []
max_gap = 1000
for code in codes:
    if code - a > max_gap:
        ranges.append((b, a, a-b+1))
        b = code
    a = code
ranges.append((b, a, a-b+1))

The maximum gap was chosen somewhat arbitrarily to be 1000. There is no other meaning behind this number. From the script above we get the following ranges:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10

 # |  start |    end | size
---+--------+--------+------
 0 |    161 |   1105 |  945
 1 |   7424 |   9397 | 1974
 2 |  10629 |  13279 | 2651
 3 |  42800 |  42996 |  197
 4 |  64256 |  65515 | 1260
 5 |  67493 |  67493 |    1
 6 | 119808 | 120770 |  963
 7 | 127232 | 127273 |   42

Using them we can now represent a symbol in just 16 bits. The format will be: tag (3 bits) followed by offset (13 bits). Here, tag is the index of the range the symbol code falls into and offset is how far into the range we have to go to find the code (an offset from the start of the range).

Let's go through an example. Suppose we want to pack symbol ₤. First, we find its codepoint, which in this case is 8356. Second, we find the tag. Codepoint 8356, falls into the range 7424..9397, so tag = 1 (001). Third, we find the offset. This can be done by computing codepoint - start. This gives us offset = 932 (0001110100100). Finally, we concatenate the two and get the packed binary representation: 0010001110100100.

This looks good. Since we have 2662 symbols, it's not possible to pack a symbol into less than two bytes, so we stop here. Next, let's turn our attention to replacements.

§5 Storing Replacements

We can store replacements, as they are, directly in the entry, but then we would have to pad all entries to the same size so that we can perform binary search. We know that there are only 453 unique replacements, so to avoid padding the entries, we instead store all replacements one after another in a single buffer and then keep an offset in the entry that points into that buffer. Since it's just an offset into a memory buffer, it doesn't matter in what order we store the replacements there. Here is the length distribution for replacements:

1
2
3

 length |   0 |   1 |   2 |   3 |   4 |   5
--------+-----+-----+-----+-----+-----+-----
  count |   1 |  94 | 207 | 114 |  35 |   2

Let's see how much space we would need in total. Every replacement needs 1 byte to keep track of its length, followed by that amount of bytes. We get that we need 453 + 0*1 + 1*94 + 2*207 + 3*114 + 4*35 + 5*2 = 1453 bytes. We also have to store 2662 entries. Each entry contains a packed symbol and an offset. Every packed symbol takes 2 bytes and same for the offset. Here, we need 2662 * (2 + 2) = 10648 bytes. In total: 1453 + 10648 = 12101 bytes. This is already an improvement over the 13314 bytes in the previous version. But we can do a bit better.

Many replacements share the same length. We can save a few bytes if we avoid storing the length of each replacement. This is possible if, inside the buffer, we store all replacements in increasing order of their lengths. This makes it so the buffer is partitioned by replacement length. That is, replacement of length 0 is stored between some offsets A and B, all replacements of length 1 between B and C, all replacements of length 2 between C and D and so on. By doing this, we save 453 bytes.

There is one last thing left. Since we stripped off the byte that indicates the length of the replacement, we need to deduce this information from somewhere else. Luckily, we know where the start of each buffer partition starts. To find the length, we find the partition that the offset falls into. To store the partition offsets, we need an additional 2 * 7 = 14 bytes.

§6 More Efficient Packing

Currently, we need 14 + 1001 + 10648 = 11663 bytes to store everything. We can reduce this amount if we make the following observations. First, replacements buffer length is 1001, which means that any offset into the buffer will need at most 10 bits, not all 16 bits allocated to it at the moment.

Second, a packed symbol stores a 3 bit tag and a 13 bit range offset. Maximum range offset that we can ever get is 2651 (range #2), which needs only 12 bits, not 13 bits that are currently allocated to it. Therefore, a packed symbol actually needs 15 bits and together with the buffer offset, they need a total of 15 + 10 = 25 bits. Again, 25 bits (4 bytes) is annoyingly close to 24 bits (3 bytes). If we manage to somehow pack the symbol more efficiently, we could save even more space.

We can do this if we split the ranges into even smaller ranges. This means that their count increases, and therefore, we have to allocate 4 bits instead of 3 bits for tag. We are left with 24 - 4 - 10 = 10 bits for the range offset if we want to fit everything nicely into just 24 bits. As a reminder, these are the ranges that we are currently working with:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10

 # |  start |    end | size
---+--------+--------+------
 0 |    161 |   1105 |  945
 1 |   7424 |   9397 | 1974
 2 |  10629 |  13279 | 2651
 3 |  42800 |  42996 |  197
 4 |  64256 |  65515 | 1260
 5 |  67493 |  67493 |    1
 6 | 119808 | 120770 |  963
 7 | 127232 | 127273 |   42

Having only 10 bits left for the range offset means that the maximum range size should be capped at 1024. Given the table above, it is obvious that ranges #1, #2 and #4 have to be split. After playing around with range endpoints, I settled on the following setup:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

  # |  start |    end | size
----+--------+--------+------
  0 |    161 |   1105 |  945
  1 |   7424 |   8378 |  955
  2 |   8413 |   9397 |  985
  3 |  10629 |  11391 |  763
  4 |  12289 |  12318 |   30
  5 |  13169 |  13279 |  111
  6 |  42800 |  42996 |  197
  7 |  64256 |  64262 |    7
  8 |  65040 |  65515 |  476
  9 |  67493 |  67493 |    1
 10 | 119808 | 120770 |  963
 11 | 127232 | 127273 |   42

All ranges have a size that is less than 1024, which means that we can now fit a packed symbol and a buffer offset into exactly 24 bits (3 bytes). This makes the total space estimate 14 + 1001 + 3*2662 = 9001 bytes.

§7 Conclusion

In the new version we achieved an improvement of ~32% over the previous version. The nice part is that it doesn't need any somewhat fancy compression techniques like before. Everything is pretty simple and also much less code. As a nice side effect, it's also much faster, since entries are not decompressed at every step of binary search:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

---------------------- BEFORE ----------------------
$ time ./indexer pages-all.txt /dev/null > /dev/null

real    0m8.843s
user    0m8.825s
sys     0m0.017s

---------------------- AFTER -----------------------
$ time ./indexer pages-all.txt /dev/null > /dev/null

real    0m0.825s
user    0m0.803s
sys     0m0.022s

I tried applying dictionary compression to replacements like in my previous post, but we save maybe 100 bytes at best, which I considered not worth it really. So I will keep the implementation as is for now.

It does suffer from the same problem as the previous version. The most fragile part is the list of ranges used for symbol packing, since they are currently hand picked. I think it should be possible to automate the process of picking the ranges, but I didn't look into it. Still, every range has some head room left in case new rules are added, and even if a range becomes too big, we have space for 4 more ranges in the list before we need to allocate more bits for the tag. Overall, the current version is actually less sensitive to changes in unaccent.rules than the previous one.

The code for search can be found in Annex A.

§8 References

1. Compressing Lookup Tables
   https://blog.x4204.xyz/posts/compressing-lookup-tables.html
2. PostgreSQL / unaccent.rules
   https://github.com/postgres/postgres/blob/57ee397953985feb95cffa65a06fcaf6a2cd5367/contrib/unaccent/unaccent.rules
3. Comment by u/alex-van-02
   https://www.reddit.com/r/C_Programming/comments/1w3icnl/comment/p72rbhd/
4. Fast Case Conversion
   https://github.com/apankrat/notes/tree/master/fast-case-conversion

§9 Annex A: Search

  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129

#define UNACCENT_ENTRIES_LEN      2662
#define UNACCENT_REPL_OFFSETS_LEN 7
#define UNACCENT_REPL_AREA_LEN    1001
#define UNACCENT_CODE_INVALID     0xffff

uint32_t unaccent_symb_ranges[] = {
  161, 1105,
  7424, 8378,
  8413, 9397,
  10629, 11391,
  12289, 12318,
  13169, 13279,
  42800, 42996,
  64256, 64262,
  65040, 65515,
  67493, 67493,
  119808, 120770,
  127232, 127273,
};
int32_t unaccent_symb_ranges_len =
  sizeof(unaccent_symb_ranges) / sizeof(unaccent_symb_ranges[0]);

typedef struct UnaccentEntry {
  uint8_t data[3];
} UnaccentEntry;

typedef struct UnaccentTable {
  UnaccentEntry entries[UNACCENT_ENTRIES_LEN];
  uint16_t repl_offsets[UNACCENT_REPL_OFFSETS_LEN];
  uint8_t repl_area[UNACCENT_REPL_AREA_LEN];
} UnaccentTable;

uint32_t
unaccent_utf8_code(uint8_t* symb)
{
  uint32_t code = 0;

  if ((symb[0] & 0x80) == 0x00) {
    code = (code | (symb[0] & 0x7f)) << 0;
  } else if ((symb[0] & 0xe0) == 0xc0) {
    code = (code | (symb[0] & 0x1f)) << 6;
    code = (code | (symb[1] & 0x3f)) << 0;
  } else if ((symb[0] & 0xf0) == 0xe0) {
    code = (code | (symb[0] & 0x0f)) << 6;
    code = (code | (symb[1] & 0x3f)) << 6;
    code = (code | (symb[2] & 0x3f)) << 0;
  } else if ((symb[0] & 0xf8) == 0xf0) {
    code = (code | (symb[0] & 0x07)) << 6;
    code = (code | (symb[1] & 0x3f)) << 6;
    code = (code | (symb[2] & 0x3f)) << 6;
    code = (code | (symb[3] & 0x3f)) << 0;
  } else {
    assert(false);
  }

  return code;
}

// NOTE: assumes `symb` points to a valid utf8 encoded symbol
uint16_t
unaccent_symb_code(uint8_t* symb)
{
  uint32_t code = unaccent_utf8_code(symb);

  for (int32_t i = 0; i < unaccent_symb_ranges_len; i += 2) {
    uint32_t a = unaccent_symb_ranges[i + 0];
    uint32_t b = unaccent_symb_ranges[i + 1];
    if (code >= a && code <= b) {
      uint16_t tag = i / 2;
      uint16_t off = code - a;
      return (tag << 12) | (off << 2);
    }
  }

  return UNACCENT_CODE_INVALID;
}

uint16_t
UnaccentEntry_code(UnaccentEntry* entry)
{
  return (entry->data[0] << 8) | (entry->data[1] & 0xfc);
}

uint16_t
UnaccentEntry_offset(UnaccentEntry* entry)
{
  return ((entry->data[1] & 0x03) << 8) | entry->data[2];
}

// NOTE: receives the symbol to find and its length through `repl`
// and `repl_len`. If symbol found in the lookup table, then it
// returns the replacement by overriding `repl` and `repl_len`.
// Otherwise, none of the two parameters are changed
void
UnaccentTable_find(
  UnaccentTable* table,
  uint8_t** repl, int32_t* repl_len
)
{
  uint8_t* symb = *repl;
  uint16_t code = unaccent_symb_code(symb);
  if (code == UNACCENT_CODE_INVALID) return;

  int32_t a = 0;
  int32_t b = UNACCENT_ENTRIES_LEN - 1;

  while (a != b) {
    int32_t m = a + (b - a + 1) / 2;
    UnaccentEntry* entry = &table->entries[m];
    if (code < UnaccentEntry_code(entry)) {
      b = m - 1;
    } else {
      a = m;
    }
  }

  UnaccentEntry* entry = &table->entries[a];
  if (code != UnaccentEntry_code(entry)) return;

  uint16_t entry_offset = UnaccentEntry_offset(entry);
  *repl_len = UNACCENT_REPL_OFFSETS_LEN - 1;
  assert(entry_offset >= 0);
  assert(entry_offset < table->repl_offsets[*repl_len]);

  *repl = &table->repl_area[entry_offset];
  for (; *repl_len >= 0; *repl_len -= 1) {
    if (entry_offset >= table->repl_offsets[*repl_len]) break;
  }
}