Codificación rápida de vectores balanceados

Es fácil ver que para cualquier existe un mapeo 1-1 de {0,1} a {0,1} tal que para cualquier el vector está "equilibrado", es decir, tiene el mismo número de 1s y 0s. ¿Es posible definir tal para que dada podamos calcular eficiente? $n$ $F$ $^n$ $^{n+O(\log n)}$ $x$ $F(x)$ $F$ $x$ $F(x)$

Gracias.

ds.algorithms ds.data-structures encoding Piotr
fuente

Supongo que por 'eficiente' te refieres a O (n) o por ahí, descartando el argumento de "ensayos aleatorios repetidos".

Suresh Venkat

@Suresh, ¿sería capaz de esbozar el argumento de "ensayos aleatorios repetidos"?

Emil

Una forma de demostrar que el mapeo existe es mediante el método probabilístico: seleccione F al azar, y luego el mapeo funciona con cierta probabilidad. a eso me refería.

Suresh Venkat

La pregunta está perfectamente bien definida pero, en mi opinión, el título es engañoso. No llamaría a un mapeo F que satisfaga la condición establecida una "codificación de vectores balanceados" a menos que F sea biyectivo. Es más como una codificación de una cadena de n bits por un vector equilibrado.

Tsuyoshi Ito

"Perfectamente bien definido" hasta interpretaciones posiblemente diferentes de "eficientemente", quiero decir. Pero este no es el punto de mi comentario anterior.

Tsuyoshi Ito

Respuestas:

Consideremos las cadenas de bits . Definiciones: $n$ $x$

$f(x,i)$ = cadena de bits con los últimos bits complementados. $x$ $i$
$b(x)$ = "desequilibrio" de : número de 1s en número de 0s en . $x$ $x$ $-$ $x$

Ahora arregla una cadena . Considere la función . Observaciones: $x$ $g(i) = b(f(x,i))$

$g(0) = b(x)$ .
$g(n) = -g(0)$ .
$|g(i) - g(i+1)| = 2$ para todo . Eliminamos un 0 y agregamos un 1 o viceversa. $i$

Ahora se deduce que existe un tal que . $i$ $-1 \le g(i) \le +1$

Por lo tanto, podemos construir una cadena de bits siguiente manera: concatenar y la codificación binaria del índice . El valor absoluto del desequilibrio de es . Además, podemos recuperar dado ; El mapeo es biyección. $(n+O(\log n))$ $y$ $f(x,i)$ $i$ $y$ $O(\log n)$ $x$ $y$

Finalmente, puede agregar bits ficticios que reducen el desequilibrio de de a . $O(\log n)$ $y$ $O(\log n)$ $0$

Jukka Suomela
fuente

b (x) en la tercera línea debe ser b (y).

Emil

Creo que posiblemente deba agregar otro bit a la cadena x para asegurarse de que tenga una longitud uniforme (de modo que pueda estar seguro de que g (i) es cero para algunos i).

Emil

@Emil: No afirmo que sea cero para algunos ; es suficiente que el valor absoluto de sea "bastante pequeño" para algunos (como mucho logarítmico sería suficiente, pero es fácil demostrar que será como máximo para algunos ).

g (i)

$g(i)$

i

$i$

g (i)

$g(i)$

i

$i$

1

$1$

i

$i$

Jukka Suomela

@ Jukka: Ah, sí, ya veo.

Emil

Pero sí, tiene razón, hay muchas variantes del mismo enfoque básico. Por ejemplo, como sugirió, primero puede usar un bit de relleno para asegurarse de que

sea igual a cero para algunos

; entonces puede codificar

utilizando los pares de bits

, es decir,

bits adicionales; entonces el resultado de la concatenación está estrictamente equilibrado y no necesita agregar nada más.

g (i)

$g(i)$

i

$i$

i

$i$

01

$01$

10

$10$

2 \log (n)

$2\log(n)$

Jukka Suomela

Use el mapeo que preserva el orden lexicográfico. Para encontrar el -ésimo vector equilibrado de longitud con 1's, hágalo recursivamente: si $k$ $n$ $n/2$ , luego establezca el primer bit 0 y luego encuentre el-ésimovector delongitudcon1 para completar losbitsrestantes. De lo contrario, establezca el primer bit 1 y encuentre el-th length-con1's. $k\leq{n-1\choose n/2}$ $k$ $(n-1)$ $n/2$ $n-1$ $k-{n-1\choose n/2}$ $(n-1)$ $n/2-1$

Zeyu
fuente

Y si reutiliza el valor de un coeficiente binomial para calcular el siguiente coeficiente binomial requerido, todo el algoritmo se ejecuta en tiempo O (n).

Tsuyoshi Ito

¡Gracias! Esto tiene sentido. Supongo que el tiempo de ejecución dependerá del modelo computacional. Si puede realizar operaciones con números de n bits en unidad de tiempo, la implementación de Tsuyoshi Ito se ejecutará en tiempo O (n). Por otro lado, si cuenta las operaciones de bit, creo que el tiempo será O (n ^ 2).

Piotr