1
$\begingroup$

Let $\Sigma$ be a finite set. Let $\Sigma^*$ be a set of finite strings in $\Sigma$.

Is there a map $f:\Sigma\to \{0, 1\}^*$ such that the concatenated map $f^*:\Sigma^*\to \{0, 1\}^*$ has the property that for all $\sigma\in\Sigma, s\in \Sigma^*$ the number of times $\sigma$ occurs in $s$ is equal to the number of times $f^*(\sigma)=f(\sigma)$ occurs in $f^*(s)$ as a contiguous substring?

Improve this question
$\endgroup$
2
  • 3
    $\begingroup$ There's an easy one: number the elements of $\Sigma$ injectively by some $h: \Sigma \mapsto [1, n]$, and let $f(\sigma) = 10^{h(n)}1$. The 1s act as delimiters; the number of 0s between any pair of 1s tells you which $\sigma$ it comes from (and we restrict $h(n) \geq 1$ in order to tell the difference between a left and right delimiter). This is extremely inefficient (along the lines of unary coding), but can be made more efficient by longer delimiters. $\endgroup$
    – user44191
    Commented Jul 23, 2021 at 19:32
  • $\begingroup$ I'm pretty sure that you can get arbitrarily efficient (as measured by $\frac{\log |\Sigma|}{\max |f(\sigma)|}<1$, i.e. the number of informative bits transferred divided by the number of total bits transferred) by using arbitrarily long delimiters that are otherwise "avoided". $\endgroup$
    – user44191
    Commented Jul 23, 2021 at 21:26

1 Answer 1

Reset to default
2
$\begingroup$

To encode an integer $X \geq 1:$

Let $N = \lfloor \log_2 X\rfloor$. Note that $N$ is the highest power of $2$ in $X$ hence $$2^N \leq X < 2^{N+1}$$

Let $L = \lfloor \log_2 N +1 \rfloor$ which implies $$2 ^L \leq N+1 <2^{L+1}$$

Encode $\sigma:=X$, i.e., define $f(\sigma)$ by $L$ zeros, followed by the $L+1$ bit binary representation of $N+1,$ followed by the last $N$ bits of $X.$

This is Elias $\delta$ coding and its efficiency is $$ \frac{ \lfloor \log_2 n \rfloor } {\lfloor \log_2 n \rfloor +2 \lfloor \log_2( \lfloor \log_2 n \rfloor+1) \rfloor+1} $$ which approaches $1$ from below as $n\rightarrow \infty.$

Improve this answer
$\endgroup$
2
  • 1
    $\begingroup$ I don't think this quite works; the coding of $2$ is $0100$, while the coding of $8$ is $00100000$, which includes the coding for $2$. $\endgroup$
    – user44191
    Commented Jul 24, 2021 at 13:20
  • 1
    $\begingroup$ More generally, any coding that allows arbitrary-length arbitrary binary representations can't work. $\endgroup$
    – user44191
    Commented Jul 24, 2021 at 13:20

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .