show/hide this revision's text 2 minor correction; deleted 55 characters in body

This is one of the basic problems that led to the field of information theory. It would take a while to explain all that is known about this, but the following will get you started.

Suppose we assign each book $b$ a binary string $\sigma_b$ such that no two strings are prefixes of each other (like telephone numbers). Then a consumer's purchases can be encoded by concatenating these strings back-to-back (without separating tokens or other marks). The total number of bits used to encode all the customer's purchases is $\sum_b n_b|\sigma_b|$, where $n_b$ is the number of times book $b$ has been purchased. We now have the optimization problem of minimizing this sum subject to the constraint that no two strings are prefixes of each other. This seemingly complex constraint actually boils down to has a simple existence criterion, namely the necessary fact that $\sum_b 2^{-|\sigma_b|} \leq 1$. So the whole thing boils down to finding $$\min \sum_b n_b \ell_b \quad\text{subject to}\quad \sum_b 2^{-\ell_b} \leq 1,$$ where $\ell_b$ is the length of the binary string used to encode the book $b$.

Generalizing a bit, we can think of $p_b = 2^{-\ell_b}$ as a probability associated to the book $b$. Translating the above becomes the problem of finding $$\max \sum_b n_b \log p_b \quad\text{subject to}\quad \sum_b p_b = 1,$$ where $p_b \in [0,1]$ are no longer restricted to being powers of $\frac12$. This continuous optimization problem has solution $p_b = n_b/n$, where $n = \sum_b n_b$ is the total number of books sold. Assuming that this solution happens to be such that the probabilities $p_b$ are all powers of $\frac12$, the total number of bits used is $$n \log_2 n - \sum_b n_b\log_2 n_b.$$ Dividing by $n$ to get the average number of bits used per book sold we get $$\log_2 n - \sum_b \frac{n_b}{n} \log_2 n_b = - \sum_b p_b \log_2 p_b.$$ This is the Shannon entropy of the distribution $p_b = n_b/n$ and this is an absolute lower bound for lossless encoding of this kind of data. Even if the probabilities are not powers of $\frac12$ encodings arbitrarily close to this bound can be achieved through arithmetic coding. In the situation you describe, it seems likely that the distribution $p_b$ is not known in advance, which is the main difficulty with achieving this optimal bound in practice.
show/hide this revision's text 1

This is one of the basic problems that led to the field of information theory. It would take a while to explain all that is known about this, but the following will get you started.

Suppose we assign each book $b$ a binary string $\sigma_b$ such that no two strings are prefixes of each other (like telephone numbers). Then a consumer's purchases can be encoded by concatenating these strings back-to-back (without separating tokens or other marks). The total number of bits used to encode all the customer's purchases is $\sum_b n_b|\sigma_b|$, where $n_b$ is the number of times book $b$ has been purchased. We now have the optimization problem of minimizing this sum subject to the constraint that no two strings are prefixes of each other. This seemingly complex constraint actually boils down to $\sum_b 2^{-|\sigma_b|} \leq 1$. So the whole thing boils down to finding $$\min \sum_b n_b \ell_b \quad\text{subject to}\quad \sum_b 2^{-\ell_b} \leq 1,$$ where $\ell_b$ is the length of the binary string used to encode the book $b$.

Generalizing a bit, we can think of $p_b = 2^{-\ell_b}$ as a probability associated to the book $b$. Translating the above becomes the problem of finding $$\max \sum_b n_b \log p_b \quad\text{subject to}\quad \sum_b p_b = 1,$$ where $p_b \in [0,1]$ are no longer restricted to being powers of $\frac12$. This continuous optimization problem has solution $p_b = n_b/n$, where $n = \sum_b n_b$ is the total number of books sold. Assuming that this solution happens to be such that the probabilities $p_b$ are all powers of $\frac12$, the total number of bits used is $$n \log_2 n - \sum_b n_b\log_2 n_b.$$ Dividing by $n$ to get the average number of bits used per book sold we get $$\log_2 n - \sum_b \frac{n_b}{n} \log_2 n_b = - \sum_b p_b \log_2 p_b.$$ This is the Shannon entropy of the distribution $p_b = n_b/n$ and this is an absolute lower bound for lossless encoding of this kind of data. Even if the probabilities are not powers of $\frac12$ encodings arbitrarily close to this bound can be achieved through arithmetic coding. In the situation you describe, it seems likely that the distribution $p_b$ is not known in advance, which is the main difficulty with achieving this optimal bound in practice.