Compressing Lookup Tables

Aug 31, 2026

§0 Table of Contents

§1 Introduction
§2 Why Remove Diacritics?
§3 Storing the Replacement Rules
§4 Dictionary Encoding
§5 Mixed Radix Numeral System Encoding
§6 Frame of Reference Encoding
§7 Building the Code Dictionary
§8 Conclusion
§9 References
§10 Annex A: Encoding/Decoding

§1 Introduction

In my free time I am implementing a small search engine I call sg^[1] as a way to get a deeper understanding and hands-on experience with search engine internals. It is written in C and compiled to WASM. The idea is to have a static search engine that can be used on the client-side without the need to make requests to a backend service for search, which is very useful for statically generated websites such as blogs and documentation.

In a search engine, query terms typically go through a few preprocessing steps before they are indexed or used for search. These steps include things like removing diacritics, case normalisation and stemming. In this post I will be looking at how diacritics are removed in sg and which techniques I use to compress the lookup table of replacement rules.

§2 Why Remove Diacritics?

In this preprocessing step, symbols such as accented letters are replaced with their closest ASCII match. A few example replacements are:

ü -> u (German)
ă -> a (Romanian)
‟ -> " (punctuation)
© -> (C) (symbols)

The reason I wanted to apply this preprocessing step is so that most of the text can represented using plain ASCII. This makes the search a bit more fuzzy, but on the other hand, it can also be an advantage.

A good example, where this step might be useful, is searching texts written in the Romanian language. Romanian speakers will often skip diacritics entirely in informal text, since it's relatively easy to figure out the correct word from context. This means that the collection of documents might have a mix of texts with and without diacritics. If someone searches for mămăligă^[2] and this preprocessing step is skipped, then the search engine will match only documents that contain the word with diacritics. The documents that contain mamaliga (without diacritics) will be skipped, because it's technically a different term. In most cases, this is not a desirable behaviour.

§3 Storing the Replacement Rules

There are many diacritics replacement lists out there, but I decided to use the one from PostgreSQL's unaccent.rules^[3]. The file contains 2662 replacement rules and represents the dataset that we want to compress. Each rule is a separate line in the file and contains the symbol to be replaced and its replacement, separated by a tab.

Since the replacement rules are nothing more than a key-value map, I initially considered using a simple hash table to store it. A hash table, however, doesn't work well for me for multiple reasons.

I want the data structure to be as compact as possible and waste the least amount of space on disk, ideally none, even before I apply any kind of compression. No matter what collision resolution techniques hash tables employ, be it open addressing or chaining, they are known to use more space than actually needed. This is so that the amount of collisions is kept low.

To avoid any wasted space, a hash table could use a minimal perfect hash function. Such a hash function maps N inputs to N slots without any collisions. After some experimetation with gperf^[4] it became clear that I can't make it build a minimal perfect hash function for the replacement rules.

There are other ways to create perfect hash tables, but the simplest ones typically require an intermediary table, which takes additional space and would need to be compressed separately. This made me reject the idea of using hash tables to store the replacement rules.

My next option, and the one I settled on, was to store the replacement rules in sorted order by key and then use binary search for lookup. The big advantage here is that it does not use extra space, unlike hash tables, and the implementation is super simple. An entry and the corresponding table can be represented this way:

#define ENTRY_DATA_LEN 8

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

typedef struct UnaccentTable {
  int32_t len;
  UnaccentEntry items[];
} UnaccentTable;

Here, symb_len is the length in bytes of the symbol to be replaced, repl_len is the length in bytes of the replacement and data stores the symbol and its replacement concatenated together. Maximum symbol length is 4 bytes and maximum replacement length is 5 bytes, but concatenated, their maximum length is 8 bytes. As a result, an UnaccentEntry takes 10 bytes and the entire table takes 26624 bytes. This will be our baseline.

Looking up a symbol in the table is then a simple binary search. Other data structures might also work as a lookup table (e.g. prefix trees), but I didn't experiment with them and don't know how well they can be compressed.

§4 Dictionary Encoding

When compressing, we want to reduce the amount of space needed to represent a sequence of bytes. Dictionary encoding^[5] is one efficient and simple to implement technique that achieves that. The idea is very simple: keep a dictionary of substitution rules A -> B, where A is the code and B is the sequence of symbols being substituted. While encoding, check if the subsequence exists in the dictionary. If there is a match, emit the corresponding code; otherwise, emit the symbol as is and go to next symbol. Decoding is the opposite operation: if a code is encountered, emit the corresponding sequence from the dictionary; otherwise, emit the symbol.

Our dictionary encoding algorithm will be based on byte-pair encoding^[6]. There, the most frequent pair of symbols in the string is found. A rule is added to the dictionary, then all occurrences in the string are substituted with the new code. This is repeated until the dictionary size reaches a threshold or there are no more pairs in the string with a frequency greater than 1. Here is the pseudocode:

str = "..."
dict = {}
while true:
  counts = count frequency of every pair in str
  pair, count = find top pair in counts
  if count == 1: break
  code = find next code
  dict[code] = pair
  replace pair in str

We need to make a couple adjustments to the algorithm to adapt it to our usecase. In the regular byte-pair encoding algorithm, it is the most frequent pair that is being substituted at every step. That's fine if we are working with only one string, but in our case there are 2662 byte strings. Our goal is not just reduce the length of a subset of strings, it's to reduce the maximum length ENTRY_DATA_LEN. To do that, we consider only the pairs found in the longest strings. Here is the pseudocode:

entries = [...]
dict = {}
while true:
  max_entries = find entries of max length
  candidates = set of all pairs in all entries from max_entries
  counts = count frequency of every candidate pair in all entries
  pair, count = find top pair in counts
  if count == 1: break
  code = find next code
  dict[code] = pair
  replace pair in all entries

Second adjustment is related to how a code is chosen for the next rule. Normally, finding the next code is just code = 1 + (max code in dict). This, however, will not work well for the following reason. Since we're processing UTF-8 strings, all codes below 256 will be allocated for use in actual symbols. This means that codes can only take values that are greater than or equal to 256. Otherwise, in a sequence of bytes, it won't be clear which byte represents a code and which one a symbol. As a result, every symbol and code has to be represented as a 16-bit integer, which is wasteful.

We can do better by exploiting the characteristics of the data we are working with. Not all values in the range 0..255 are taken. We can reuse these values for our codes and since they never appear in the data, there won't be any ambiguity in whether the value represents a code or a symbol. By doing this, we manage to keep everything in 8-bit. Here is the pseudocode to find the unused values:

available_codes = set of all values in interval 0..255
for entry in entries:
  for byte in entry:
    discard byte from available_codes

This gives us the following list of values we can choose codes from:

available_codes = [
    0,   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,

                                    127,

           192, 193,

  210, 211, 212, 213, 214, 215, 216, 217, 218, 219,
  220, 221, 222, 223, 224,                228, 229,
  230, 231, 232, 233,      235, 236, 237, 238,

       241, 242, 243, 244, 245, 246, 247, 248, 249,
  250, 251, 252, 253, 254, 255
]

Note the gaps where values are missing. These are the bytes that appear in the dataset and can't be repurposed. The most promising values we could use for dictionary codes are the ones from the range 127..238. The exact reason for this will become clearer in the section on frame of reference encoding. In short, all values found in our dataset fit in the range 32..240. Ideally, we don't want to widen this range by assigning values from outside it to dictionary codes, and 127..238 is promising, because it fits entirely inside 32..240.

We now have everything needed to build the substitution dictionary. After some experimentation, I ended up with the following one. Details on how exactly it was built will be given in a later section.

7f: [28,32]     c0: [2f,33]     c1: [f0,9d]     d2: [e3,8f]
d3: [f0,9f]     d4: [ef,b8]     d5: [86,43]     d6: [20,35]
d7: [82,61]     d8: [e2,91]     d9: [2f,38]     da: [e2,a9]
db: [2f,35]     dc: [e2,85]     dd: [d3,84]     de: [e2,82]
df: [20,31]     e0: [e3,8e]     e4: [63,61]     e5: [72,61]
e6: [e2,80]     e7: [e2,86]     e8: [49,49]     e9: [28,31]
eb: [20,33]     ec: [e2,92]     ed: [2e,6d]     ee: [df,2f]
f1: [ef,ac]     f2: [69,69]     f3: [e3,8d]     f4: [e2,84]
f5: [2f,73]

In total, there are 33 substitution rules. In the dictionary above, all values are in hexadecimal. Every rule represents a substitution of one byte with two other bytes. For example, the pair [28,32] will be substituted with 7f when encoding and viceversa when decoding. By using just this small dictionary of only 33 rules, it was possible to reduce the maximum length ENTRY_DATA_LEN from 8 to 5 bytes.

Note that, unfortunately, we were not able to entirely avoid widening the range 32..240, since there are only 28 available values within 127..238. The range was widened by five more values, namely 241..245 (i.e. codes f1..f5). Without these 5 additional codes, dictionary encoding would have reduced the maximum length to 6 instead of 5 bytes.

Overall, size of an UnaccentEntry is now 7 bytes instead of the 10 bytes we started with. This saves us 7986 bytes across the entire lookup table. Not bad for just 33 substitution rules, but we can compress it a bit more.

§5 Mixed Radix Numeral System Encoding

A mixed radix numeral system^[7] (MRNS) is a numeral system where the radix varies from position to position. This is not a special concept. In fact, it's pretty simple and there are plenty of every day examples where such a system is in use. Time is expressed in hour (radix 24), minute (radix 60) and seconds (radix 60). Rotation is expressed in degrees (radix 360), minutes (radix 60) and seconds (radix 60). Length in imperial units is expressed in miles (radix 1760), yards (radix 3) and feet (radix 12). This is unlike other numeral system like base 2, where the base is the same in every position.

We will now follow an example with time. According to the paragraph above, the base for time is (24, 60, 60). Therefore, 15:49:31 represents 56971 seconds. This is how we encode:

hours, minutes, seconds = 15, 49, 31
encoded = 0
encoded = encoded * 24 + hours    # -> 15
encoded = encoded * 60 + minutes  # -> 949
encoded = encoded * 60 + seconds  # -> 56971

And this is how we decode:

seconds = encoded % 60    # -> 31
encoded = encoded // 60   # -> 949

minutes = encoded % 60    # -> 49
encoded = encoded // 60   # -> 15

hours = encoded % 24      # -> 15
encoded = encoded // 24   # -> 0

The values 15:49:31 and 56971 are equivalent. They are the same thing really, just represented in different ways. What makes a difference, however, is the way we store this information in memory, the amount of space it takes and the way each time component is accessed. Let's say that we use a byte to represent each time component (i.e. hour, minute, second). We get that we need 3 * 8 = 24 bits to store the time. Now let's see how many bits are needed if we represent it as a plain integer. In total, we need ceil(log2(24 * 60 * 60)) = 17 bits, which is 7 bits less. An MRNS gives us the opportunity to save space by packing a sequence of values in a much more compact way.

We could interpret an UnaccentEntry as a sequence of values that we then encode using an MRNS. In this case we are dealing with a sequence of 7 bytes (i.e. symbol length, replacement length and 5 bytes of dictionary encoded data). To find the base for MRNS, we need to find the maximum value for every byte in the sequence. After running a small script, these are the max values we get:

1
2
3

     | symb_len | repl_len | data[0] | data[1] | data[2] | data[3] | data[4]
-----+----------+----------+---------+---------+---------+---------+--------
 max |        5 |        6 |     244 |     215 |     242 |     245 |     245

This forms the MRNS base (5, 6, 244, 215, 242, 245, 245) that we can then use to encode an UnaccentEntry into a single integer. The current space requirement for storing an entry is 7 * 8 = 56 bits. If, however, we encode it as an integer, then the space requirement drops to ceil(log2(5 * 6 * 244 * 215 * 242 * 245 * 245)) = 45 bits, which is just over 40 bits (5 bytes). These 5 extra bits are keeping us from achieving a 5 byte encoding, but thankfully there is one more technique we can apply.

§6 Frame of Reference Encoding

Note that when encoding, say data[0], using an MRNS, we use the interval 0..244. Remember from the dictionary encoding section that we chose the dictionary codes carefully, such that we do not widen the range too much. The reason we did that is so we can apply frame of reference coding and shift the range by the biggest offset possible. In essense, data[0] has range 0..244 at the moment, but there are no values below 193 in that position in any of the entries, so its range is effectively 193..244. Frame of reference encoding shifts these endpoints, so we can work with smaller values, and as a result use less bits. We now find the minimum value of each byte and shift the corresponding ranges:

     | symb_len | repl_len | data[0] | data[1] | data[2] | data[3] | data[4]
-----+----------+----------+---------+---------+---------+---------+--------
 max |        5 |        6 |     244 |     215 |     242 |     245 |     245
 min |        2 |        0 |     193 |     128 |      32 |      33 |      33
diff |        3 |        6 |      52 |      88 |     211 |     213 |     213

Space requirement is now ceil(log2(3 * 6 * 52 * 88 * 211 * 213 * 213)) = 40 bits, which fits exactly into 5 bytes. The entire unaccent table takes only half of the original space (13314 bytes) and can still be used to lookup symbols without having to decompress the entire table! The entire implementation of entry encoding and decoding is presented in Annex A.

§7 Building the Code Dictionary

Searching for a good code dictionary happens in two stages and requires a bit of bruteforcing. We first need to find how many rules are needed to achieve a final entry encoding of roughly 40 bits. We try dictionaries of different lengths and use them to encode all entries, then look at how many bits each entry takes after the rest of the compression techniques are applied. If the amount of bits is close to 40, then we found a candidate dictionary, so we keep it; otherwise we discard it.

available_codes = [...]
candidate_dicts = []
for k in 1..40:
  use_codes = (
    choose k consecutive values from available_codes
    such that range 127..238 is widened the least
  )
  dict, entry_bits = build dict with use_codes
  if abs(entry_bits - 40) < 3:
    append dict to candidate_dicts

Now that we have a short list of candidates, we can proceed with the second stage. The order in which we replace pairs in strings matters, because this affects the ranges for each byte. One replacement order can give slightly better compression than another after other techniques are applied. We want to find the permutation of rules that will result in at most 40 bit final encoding. By permutation I mean assigning a different code to each pair. Every candidate dictionary from above has at least 30 rules. It's unfeasible to try all permutations, so we try 1000 random permutations and hope to find a good one. Here's the pseudocode:

good_dicts = []
for dict in candidate_dicts:
  for k in 1..1000:
    dict_perm = randomly permute dict rules
    entry_bits = encode entries
    if entry_bits <= 40:
      append dict_perm to good_dicts

The only thing left now is to choose whichever dictionary you like most from good_dicts. I chose the one with the least amount of substitution rules.

§8 Conclusion

In this post I described the techniques I applied to compress a symbol lookup table. I'm pretty happy with how it turned out. We were able to reduce the storage requirements in half, while preserving fairly fast lookup and not requiring a full table decompression before lookup.

It does have a few caveats, though. This approach is specifically finetuned for unaccent.rules in the state it exists at that specific commit. If anything in the file changes, then the chances are high that the compression algorithm will break completelly or become less efficient and encode entries into more bytes than what it currently does. On top of that, during lookup it fully decompresses up to O(log n) entries since it's doing binary search. This, however, is not a problem for our usecase, because at runtime diacritics are removed only from query strings. These are typically only a handful of words, and modern CPUs are really fast, so it doesn't really have a considerable impact on the runtime of the algorithm. This is an acceptable tradeoff given the amount of compression we get.

As an improvement to what was mentioned, perhaps the entry decoding can be performed incrementally, so that instead of decoding it fully, we only decode as much as we need for binary search to take place and not a byte more. Another potential improvement is to perform string comparisons directly on dictionary encoded strings and skip the dictionary decoding step during entry decompression. Both of these should improve the runtime a bit, but again, given the usecase, it's not really worth it since this preprocessing step is not a bottleneck.

§9 References

sg
https://gitlab.com/x4204/sg
Mămăligă
https://en.wikipedia.org/wiki/M%C4%83m%C4%83lig%C4%83
PostgreSQL / unaccent.rules
https://github.com/postgres/postgres/blob/57ee397953985feb95cffa65a06fcaf6a2cd5367/contrib/unaccent/unaccent.rules
GNU / gperf
https://www.gnu.org/software/gperf/
Dictionary coder
https://en.wikipedia.org/wiki/Dictionary_coder
Byte-pair encoding
https://en.wikipedia.org/wiki/Byte-pair_encoding
Mixed radix
https://en.wikipedia.org/wiki/Mixed_radix

§10 Annex A: Encoding/Decoding

#define UNACCENT_ENTRY_DEC_DATA_MAX 8
#define UNACCENT_ENTRY_ENC_DATA_MAX 5
#define UNACCENT_CODES_MAX 33

typedef struct UnaccentEntryDec {
  uint8_t symb_len;
  uint8_t data_len;
  uint8_t data[UNACCENT_ENTRY_DEC_DATA_MAX];
} UnaccentEntryDec;

typedef struct UnaccentEntryEnc {
  uint8_t data[UNACCENT_ENTRY_ENC_DATA_MAX];
} UnaccentEntryEnc;

typedef struct UnaccentTable {
  int32_t len;
  UnaccentEntryEnc items[];
} UnaccentTable;

typedef struct UnaccentCode {
  uint8_t rule;
  uint8_t pair0;
  uint8_t pair1;
} UnaccentCode;

UnaccentCode unaccent_codes[UNACCENT_CODES_MAX] = {
  { .rule = 0x7f, .pair0 = 0x28, .pair1 = 0x32 },
  { .rule = 0xc0, .pair0 = 0x2f, .pair1 = 0x33 },
  { .rule = 0xc1, .pair0 = 0xf0, .pair1 = 0x9d },
  { .rule = 0xd2, .pair0 = 0xe3, .pair1 = 0x8f },
  { .rule = 0xd3, .pair0 = 0xf0, .pair1 = 0x9f },
  { .rule = 0xd4, .pair0 = 0xef, .pair1 = 0xb8 },
  { .rule = 0xd5, .pair0 = 0x86, .pair1 = 0x43 },
  { .rule = 0xd6, .pair0 = 0x20, .pair1 = 0x35 },
  { .rule = 0xd7, .pair0 = 0x82, .pair1 = 0x61 },
  { .rule = 0xd8, .pair0 = 0xe2, .pair1 = 0x91 },
  { .rule = 0xd9, .pair0 = 0x2f, .pair1 = 0x38 },
  { .rule = 0xda, .pair0 = 0xe2, .pair1 = 0xa9 },
  { .rule = 0xdb, .pair0 = 0x2f, .pair1 = 0x35 },
  { .rule = 0xdc, .pair0 = 0xe2, .pair1 = 0x85 },
  { .rule = 0xdd, .pair0 = 0xd3, .pair1 = 0x84 },
  { .rule = 0xde, .pair0 = 0xe2, .pair1 = 0x82 },
  { .rule = 0xdf, .pair0 = 0x20, .pair1 = 0x31 },
  { .rule = 0xe0, .pair0 = 0xe3, .pair1 = 0x8e },
  { .rule = 0xe4, .pair0 = 0x63, .pair1 = 0x61 },
  { .rule = 0xe5, .pair0 = 0x72, .pair1 = 0x61 },
  { .rule = 0xe6, .pair0 = 0xe2, .pair1 = 0x80 },
  { .rule = 0xe7, .pair0 = 0xe2, .pair1 = 0x86 },
  { .rule = 0xe8, .pair0 = 0x49, .pair1 = 0x49 },
  { .rule = 0xe9, .pair0 = 0x28, .pair1 = 0x31 },
  { .rule = 0xeb, .pair0 = 0x20, .pair1 = 0x33 },
  { .rule = 0xec, .pair0 = 0xe2, .pair1 = 0x92 },
  { .rule = 0xed, .pair0 = 0x2e, .pair1 = 0x6d },
  { .rule = 0xee, .pair0 = 0xdf, .pair1 = 0x2f },
  { .rule = 0xf1, .pair0 = 0xef, .pair1 = 0xac },
  { .rule = 0xf2, .pair0 = 0x69, .pair1 = 0x69 },
  { .rule = 0xf3, .pair0 = 0xe3, .pair1 = 0x8d },
  { .rule = 0xf4, .pair0 = 0xe2, .pair1 = 0x84 },
  { .rule = 0xf5, .pair0 = 0x2f, .pair1 = 0x73 },
};

uint8_t unaccent_offs[] = {0, 2, 193, 128, 32, 33, 33};
#define unaccent_offs_len \
  (sizeof(unaccent_offs) / sizeof(unaccent_offs[0]))

uint8_t unaccent_mrns_base[] = {6, 3, 52, 88, 211, 213, 213};
#define unaccent_mrns_base_len \
  (sizeof(unaccent_mrns_base) / sizeof(unaccent_mrns_base[0]))

int32_t
bit_size(uint64_t n)
{
  return n == 0 ? 0 : 64 - __builtin_clzll(n);
}

// NOTE: can do binary search here since the list is sorted by
// `.rule`, but I'm too lazy to implement it and it probably
// isn't that much faster than a simple linear search
int32_t
unaccent_code_find(uint8_t rule)
{
  for (int32_t i = 0; i < UNACCENT_CODES_MAX; i += 1) {
    if (unaccent_codes[i].rule == rule) return i;
  }
  return -1;
}

void
unaccent_code_expand(UnaccentEntryDec* dec, uint8_t rule)
{
  int32_t ci = unaccent_code_find(rule);
  if (ci < 0) {
    dec->data[dec->data_len] = rule;
    dec->data_len += 1;
  } else {
    unaccent_code_expand(dec, unaccent_codes[ci].pair0);
    unaccent_code_expand(dec, unaccent_codes[ci].pair1);
  }
}

void
unaccent_encode(UnaccentEntryEnc* enc, UnaccentEntryDec* dec)
{
  // dictionary encoding
  uint8_t tmp[UNACCENT_ENTRY_DEC_DATA_MAX] = {0};
  uint8_t tmp_len = dec->data_len;
  memcpy(tmp, dec->data, tmp_len);
  for (int32_t ci = 0; ci < UNACCENT_CODES_MAX; ci += 1) {
    UnaccentCode* code = &unaccent_codes[ci];
    int32_t len = 0;
    for (int32_t i = 0; i < tmp_len; i += 1, len += 1) {
      if (
        i + 1 < tmp_len
        && tmp[i + 0] == code->pair0
        && tmp[i + 1] == code->pair1
      ) {
        tmp[len] = code->rule;
        i += 1;
      } else {
        tmp[len] = tmp[i];
      }
    }
    tmp_len = len;
  }
  memset(&tmp[tmp_len], 0, UNACCENT_ENTRY_DEC_DATA_MAX - tmp_len);
  assert(tmp_len <= UNACCENT_ENTRY_ENC_DATA_MAX);

  // prepare buffer
  uint8_t buf[] = {
    tmp_len, dec->symb_len,
    tmp[0], tmp[1], tmp[2], tmp[3], tmp[4],
  };
  int32_t buf_len = sizeof(buf) / sizeof(buf[0]);
  assert(buf_len == unaccent_offs_len);
  assert(buf_len == unaccent_mrns_base_len);

  // frame of reference encoding
  for (int32_t i = 0; i < 2 + tmp_len; i += 1) {
    buf[i] -= unaccent_offs[i];
  }

  // mixed radix numeral system encoding
  uint64_t pacc = 1;
  uint64_t sacc = 0;
  for (int32_t i = 0; i < buf_len; i += 1) {
    sacc += pacc * buf[i];
    pacc *= (uint64_t)unaccent_mrns_base[i];
  }
  assert(bit_size(sacc) <= 40);

  enc->data[0] = (sacc >> (4 * 8)) & 0xff;
  enc->data[1] = (sacc >> (3 * 8)) & 0xff;
  enc->data[2] = (sacc >> (2 * 8)) & 0xff;
  enc->data[3] = (sacc >> (1 * 8)) & 0xff;
  enc->data[4] = (sacc >> (0 * 8)) & 0xff;
}

void
unaccent_decode(UnaccentEntryDec* dec, UnaccentEntryEnc* enc)
{
  // prepare buffer
  uint8_t buf[7] = {0};
  int32_t buf_len = sizeof(buf) / sizeof(buf[0]);
  assert(buf_len == unaccent_offs_len);
  assert(buf_len == unaccent_mrns_base_len);

  // mixed radix numeral system decoding
  uint64_t sacc = (0lu
    | (uint64_t)enc->data[0] << (4 * 8)
    | (uint64_t)enc->data[1] << (3 * 8)
    | (uint64_t)enc->data[2] << (2 * 8)
    | (uint64_t)enc->data[3] << (1 * 8)
    | (uint64_t)enc->data[4] << (0 * 8)
  );
  for (int32_t i = 0; i < buf_len; i += 1) {
    buf[i] = sacc % unaccent_mrns_base[i];
    sacc /= unaccent_mrns_base[i];
  }

  // frame of reference decoding
  for (int32_t i = 0; i < 2 + buf[0]; i += 1) {
    buf[i] += unaccent_offs[i];
  }

  // dictionary decoding
  int32_t data_len = buf[0];
  for (int32_t i = 0; i < data_len; i += 1) {
    unaccent_code_expand(dec, buf[2 + i]);
  }
  dec->symb_len = buf[1];
}

bool
UnaccentTable_find(
  UnaccentEntryDec* entry_dec,
  UnaccentTable* table, uint8_t* key, int32_t key_len
)
{
  int32_t a = 0;
  int32_t b = table->len - 1;

  while (a != b) {
    int32_t m = a + (b - a + 1) / 2;

    UnaccentEntryEnc* entry_enc = &table->items[m];
    memset(entry_dec, 0, sizeof(*entry_dec));
    unaccent_decode(entry_dec, entry_enc);

    if (Buffer_cmp(key, key_len, entry_dec->data, entry_dec->symb_len) < 0) {
      b = m - 1;
    } else {
      a = m;
    }
  }

  UnaccentEntryEnc* entry_enc = &table->items[a];
  memset(entry_dec, 0, sizeof(*entry_dec));
  unaccent_decode(entry_dec, entry_enc);

  return Buffer_cmp(key, key_len, entry_dec->data, entry_dec->symb_len) == 0;
}

int32_t
Buffer_cmp(uint8_t* a, int32_t a_len, uint8_t* b, int32_t b_len)
{
  int32_t len = min(a_len, b_len);
  for (int32_t i = 0; i < len; i += 1) {
    if (a[i] < b[i]) return -1;
    if (a[i] > b[i]) return +1;
  }
  return a_len - b_len;
}