prefixes.md

Simple algorithm for encoding a set of prefixes

Motivation

There are situations in which it might be useful to send a set of prefixes to other nodes in order to verify that they have the same set as we do (inter-group synchronization). When there are large number of prefixes, it will be beneficial to encode them in some way instead of just putting them in full in the message.

The algorithm

The encoding of a set of prefixes will consist of two parts: the starting prefix and the proper encoding (an empty prefix can be assumed in the absence of a starting prefix).

The proper encoding will be a sequence of bits that allow for the reconstruction of the whole set in the following way:

1. Start with an empty resulting list and a queue containing only the starting prefix.
2. Pop a bit b from the start of the sequence and a prefix P from the queue
3. If b is 1, push P0 and P1 to the queue; otherwise insert P into the resulting list.
4. Repeat point 2 and 3 until the bit sequence is empty. If there are any prefixes left in the queue, add them to the resulting list.

Examples (all starting with the empty prefix):

• 0 encodes just the empty prefix
• 1 (or 10, or 100) encodes prefixes 0 and 1
• 11 (or 110) encodes prefixes 00, 01, 1
• 101 encodes 0, 10, 11
• 111 encodes 00, 01, 10, 11
• 10101 encodes 0, 10, 110, 111

Notes

The trailing zeros don't change anything, which leads to non-uniqueness of the encoding and suggests that there might exist a more efficient way of compressing the prefixes.