Quick encoding of balanced vectors
Let's consider $n$-bit strings $x$. Definitions:


$f(x,i)$ = bit string $x$ with last $i$ bits complemented.
$b(x)$ = "imbalance" of $x$: number of 1s in $x$ $-$ number of 0s in $x$.


Now fix a string $x$. Consider the function $g(i) = b(f(x,i))$. Observations:


$g(0) = b(x)$.
$g(n) = -g(0)$.
$|g(i) - g(i+1)| = 2$ for all $i$. We either remove one 0 and add one 1 or vice versa.


Now it follows that there exists an $i$ such that $-1 \le g(i) \le +1$.

Hence we can construct an $(n+O(\log n))$-bit string $y$ as follows: concatenate $f(x,i)$ and the binary encoding of the index $i$. The absolute value of the imbalance of $y$ is $O(\log n)$. Moreover, we can recover $x$ given $y$; the mapping is bijection.

Finally, you can add $O(\log n)$ dummy bits that reduce the imbalance of $y$ from $O(\log n)$ to $0$.