Can a static pre-shared database reduce communication size?

Question

Is the problem of communication with a pre-shared database studied? If yes, what field studies it, or which researchers work on it?

Let there be two parties that want to share multiple yet-to-be-defined messages. These parties want to compress future communication as much as possible. For that, they first define some pre-shared knowledge: some database that will be used as a reference for constructing the messages. The size of the database is much bigger than the size of each specific message. Does the database help to compress or reduce the size of sent messages?

Here's an example: aliens from our nearest star, Proxima Centauri, come to visit Earth. They stay here for a while, which provides an opportunity to understand each other's language, define algorithms and construct a common database of some form. The time they stay here isn't sufficient to share all our knowledge, and we want to ease the future knowledge exchange (or even one-sided sharing) when they are back at Proxima Centauri.

While they are here, it's easy to share communication, and construct a big pre-shared database. However, Proxima Centauri is about 4.2 light years away from Earth, so sending a message from us to them takes about 4.2 years to reach the destination. We have lots of data to share, and we want to reduce the size of the sent messages. We can compress the sent messages with any available methods, but the question is, can this database help? For example, instead of writing a full message of size $n$, find the first $n/k$ bits in the database, and if they are there, call the address of the first bit $A$, do the same for the rest and call the address $B$. With that, instead of sending the whole message, send just the addresses of $A$ and $B$, and the length of the message (or, send more than two addresses, if the message can't be split into two addresses because there are no such strings in the database).

Is this question studied in any way? Can such a database help, or sending the addresses of $A$ and $B$ won't be shorter than the message itself? Various models come to mind: the database can be just a long array of random bits, pre-structured, or calculated (e.g.: take $k$ bits starting from the $m$-th digit of $\pi$). It can be static, or grow over time according to some algorithm or even by using the exchanged messages. For a database of size $O(n)$, the messages can be of size $O(log(n))$ or $O(sqrt(n))$ or some other function of $n$ that is significantly smaller than $n$. The allowed messages can include any string or only strings of some form. The number of sent messages can be infinite or be defined as some function of n. The message exchange algorithm can use only the database addresses or any combination of database data with message unique data.

The main idea is to check if some formatted (even if randomized) pre-shared database can reduce the messaging size (even if probabilistically): per message, or cumulatively for multiple or all messages.

Thanks in advance.

Answer 1

I will assume you are looking for an information-theoretic view, where the goal is to come up with an encoding/compression scheme to minimize the length of the encoded data, without worrying about computational issues (how efficiently the data can be encoded or decoded). I'll also assume that you want lossless compression. In that case, this should be covered by standard information-theoretic notions.

The answer depends on the nature of the process that generates the data you want to transmit. If this process is independent of the database, then the database won't help. More precisely, let $X$ denote the message that you are sending. In information theory, we model $X$ as a random variable. If $X$ is independent of the database (i.e., the process that generates $X$ is independent, in terms of probability theory, from the process that generates the database), then the database doesn't help. The best you can do is to use the best code for $X$ in isolation. Shannon's source coding theorem states that you need approximately $H(X)$ bits to send $X$ in encoded form, where $H(X)$ is the Shannon entropy of $X$.

In the general case, where the two aren't necessarily independent, then the database can help. Let the r.v. $X$ model the (process for generating the) message you want to send and $D$ model the (process for generating the) database. Then the number of bits needed is approximately $H(X|D)$. In other words, in this case we need to use the conditional entropy.

How much does the database help? It reduces the number of bits needed from $H(X)$ to $H(X|D)$. Thus, it helps by saving us $H(X)-H(X|D)$ bits per message. This value is so important it has a name: it is called the mutual information, and is denoted by $I(X;D)$.

The information-theoretic view has some limitations. It assumes that the probability distributions that generate $X$ and $D$ are known, perfectly, to both the sender and the receiver. It also ignores the computational costs of encoding and decoding. Both of these might be issues in practice. Nonetheless, it is helpful for understanding limits on what is achievable.