Encontrar un par de vectores de bits no superpuestos

17

Te doy una lista de n vectores de bits de ancho k . Su objetivo es devolver dos vectores de bits de la lista que no tienen 1 en común, o bien informar que no existe dicho par.

Por ejemplo, si le doy [00110,01100,11000] entonces la única solución es {00110,11000} . Alternativamente, la entrada [111,011,110,101] no tiene solución. Y cualquier lista que contenga el vector de bits todo cero 000...0 y otro elemento e tiene una solución trivial {e,000...0} .

Aquí hay un ejemplo un poco más difícil, sin solución (cada fila es un vector de bits, los cuadrados negros son 1s y los cuadrados blancos son 0s):

■ ■ ■ ■ □ □ □ □ □ □ □ □ □
■ □ □ □ ■ ■ ■ □ □ □ □ □ □ 
■ □ □ □ □ □ □ ■ ■ ■ □ □ □
■ □ □ □ □ □ □ □ □ □ ■ ■ ■
□ ■ □ □ □ ■ □ □ □ ■ ■ □ □
□ ■ □ □ ■ □ □ □ ■ □ □ □ ■
□ ■ □ □ □ □ ■ ■ □ □ □ ■ □ <-- All row pairs share a black square
□ □ ■ □ □ □ ■ □ ■ □ ■ □ □
□ □ ■ □ □ ■ □ ■ □ □ □ □ ■
□ □ ■ □ ■ □ □ □ □ ■ □ ■ □
□ □ □ ■ ■ □ □ ■ □ □ ■ □ □
□ □ □ ■ □ □ ■ □ □ ■ □ □ ■
□ □ □ ■ □ ■ □ □ ■ □ □ ■ □

¿Cuán eficientemente se pueden encontrar dos vectores de bits no superpuestos o demostrar que no existen?

El algoritmo ingenuo, donde solo compara cada par posible, es O(n2k) . ¿Es posible hacerlo mejor?

Craig Gidney
fuente
Una posible reducción: tiene un gráfico con un vértice para cada vector y un borde entre dos vértices si los dos vectores correspondientes tienen un 1 en común. Desea saber si el diámetro del gráfico es 2 . Pero parece difícil ir más rápido que O ( n 2 k ) . G2O(n2k)
François
@ FrançoisGodi Cualquier componente gráfico conectado con tres nodos y un borde faltante tiene un diámetro de al menos dos. Con una representación de lista de adyacencia, lleva tiempo comprobar eso. O(V)
Craig Gidney
@Strilanc Claro, si no hay una solución, el gráfico está completo (más claro que diámetro = 1, tiene razón), pero calcular la representación de la lista de adyacencia podría ser largo.
François
¿Es más pequeño que el ancho de palabra de su máquina? k
Raphael
1
@TomvanderZanden Parece que violaría invariantes en los que probablemente se basa la estructura de datos. En particular, esa igualdad debe ser transitiva. He estado pensando en usar un trie ya y no veo cómo evitar una explosión de factor de 2 cada vez que la máscara de bits de consulta tiene un 0.
Craig Gidney

Respuestas:

10

Calentamiento: vectores de bits aleatorios

Como calentamiento, podemos comenzar con el caso en el que cada bitvector se elige de manera uniforme al azar. Entonces resulta que el problema se puede resolver en (más precisamente, el 1.6 se puede reemplazar con lg 3 ).O(n1.6min(k,lgn))1.6lg3

Consideraremos la siguiente variante de dos conjuntos del problema:

Dados los conjuntos de vectores de bits, determine dónde existe un par no superpuestoS,T{0,1}k .sS,tT

La técnica básica para resolver esto es dividir y conquistar. Aquí hay un algoritmo de tiempo ( n 1.6 k ) que usa divide y vencerás:O(n1.6k)

  1. Dividir y T según la posición del primer bit. En otras palabras, forma S 0 = { s S : s 0 = 0 } , S 1 = { s S : s 0 = 1 } , T 0 = { t T : t 0 = 0 } , TSTS0={sS:s0=0}S1={sS:s0=1}T0={tT:t0=0} .T1={tT:t0=1}

  2. Ahora busque recursivamente un par no superpuesto de , de S 0 , T 1 y de TS0,T0S0,T1 . Si alguna llamada recursiva encuentra un par no superpuesto, envíelo, de lo contrario, saldrá "No existe par superpuesto".T1,S0

Como todos los vectores de bits se eligen al azar, podemos esperar y | T b | | T | / 2 . Por lo tanto, tenemos tres llamadas recursivas y hemos reducido el tamaño del problema en un factor de dos (ambos conjuntos se reducen en tamaño en un factor de dos). Después de que lg min ( | S | , | T | ) se divide, uno de los dos conjuntos se reduce al tamaño 1, y el problema se puede resolver en tiempo lineal. Obtenemos una relación de recurrencia a lo largo de las líneas de|Sb||S|/2|Tb||T|/2lgmin(|S|,|T|) , cuya solución es T ( n ) = O ( n 1.6 k ) . Teniendo en cuenta el tiempo de ejecución con mayor precisión en el caso de dos conjuntos, vemos que el tiempo de ejecución es O ( min ( | S | , | T | ) 0.6 max ( | S | , | TT(n)=3T(n/2)+O(nk)T(n)=O(n1.6k) .O(min(|S|,|T|)0.6max(|S|,|T|)k)

Esto se puede mejorar aún más, observando que si , entonces la probabilidad de que exista un par no superpuesto es exponencialmente pequeña. En particular, si x , y son dos vectores al azar, la probabilidad de que es que son no superpuestas ( 3 / 4 ) k . Si | S | = | T | = n , hay n 2 de estos pares, por lo que por un enlace de unión, la probabilidad de que exista un par no superpuesto es como máximo n 2 ( 3k2.5lgn+100x,y(3/4)k|S|=|T|=nn2 . Cuando k 2.5 lg n +n2(3/4)k , esto es1 / 2 100 . Entonces, como un paso de preprocesamiento, si k 2.5 lg n + 100 , entonces podemos devolver inmediatamente "No existe un par no superpuesto" (la probabilidad de que esto sea incorrecto es insignificantemente pequeño), de lo contrario, ejecutamos el algoritmo anterior.k2.5lgn+1001/2100k2.5lgn+100

Por lo tanto, alcanzamos un tiempo de ejecución de (u O ( min ( | S | , | T | ) 0.6 max ( | S | , | T | ) min ( k , lg n ) ) para la variante de dos conjuntos propuesta anteriormente), para el caso especial donde los vectores de bits se eligen uniformemente al azar.O(n1.6min(k,lgn))O(min(|S|,|T|)0.6max(|S|,|T|)min(k,lgn))

Por supuesto, este no es un análisis del peor de los casos. Los vectores de bits aleatorios son considerablemente más fáciles que el peor de los casos, pero tratémoslo como un calentamiento, para obtener algunas ideas que quizás podamos aplicar al caso general.

Lecciones del calentamiento

Podemos aprender algunas lecciones del calentamiento anterior. Primero, dividir y conquistar (dividir en una posición de bit) parece útil. En segundo lugar, desea dividir en una posición de bit con tantos en esa posición como sea posible; cuanto más 0 's hay, menos reducción en el tamaño subproblema se obtiene.10

En tercer lugar, esto sugiere que el problema se vuelve más difícil a medida que la densidad de hace más pequeña: si hay muy pocos 1 entre los vectores de bits (en su mayoría son 0 ), el problema parece bastante difícil, ya que cada división se reduce el tamaño de los subproblemas un poco. Por lo tanto, defina la densidad Δ como la fracción de bits que son 1 (es decir, de todos los n k bits), y la densidad de la posición de bit i como la fracción de los vectores de bits que son 1110Δ1nki1 en la posición .i

Manejo de muy baja densidad

Como siguiente paso, podríamos preguntarnos qué sucede si la densidad es extremadamente pequeña. Resulta que si la densidad en cada posición de bit es menor que , estamos garantizados de que existe un par no superpuesto: existe un argumento de existencia (no constructivo) que muestra que debe existir algún par no superpuesto. Esto no nos ayuda a encontrarlo, pero al menos sabemos que existe.1/k

¿Por qué es este el caso? Digamos que un par de bitvectors está cubierto por la posición de bit i si x i = y i = 1 . Tenga en cuenta que cada par de vectores de bits superpuestos debe estar cubierto por alguna posición de bits. Ahora, si fijamos una posición de bit particular i , el número de pares que puede cubrir esa posición de bit es como máximo ( n Δ ( i ) ) 2 < n 2 / k . Resumiendo todo kx,yixi=yi=1i(nΔ(i))2<n2/kk de las posiciones de bit, encontramos que el número total de pares que están cubiertos por alguna posición de bit es . Esto significa que debe existir algún par que no esté cubierto por ninguna posición de bit, lo que implica que este par no se superpone. Entonces, si la densidad es suficientemente baja en cada posición de bit, entonces seguramente existe un par no superpuesto.<n2

Sin embargo, no puedo identificar un algoritmo rápido para encontrar un par que no se superponga, en este régimen, aunque se garantiza que existe uno. No veo de inmediato ninguna técnica que produzca un tiempo de ejecución que tenga una dependencia subcuadrática de . Entonces, este es un buen caso especial para enfocarse, si desea pasar un tiempo pensando en este problema.n

Hacia un algoritmo de caso general

En el caso general, una heurística natural parece ser: elija la posición de bit con el mayor número de 1 (es decir, con la densidad más alta) y divídala. En otras palabras:i1

  1. Encuentre una posición de bit que maximice Δ ( i ) .iΔ(i)

  2. Dividir y T según la posición del bit i . En otras palabras, forma S 0 = { s S : s i = 0 } , S 1 = { s S : s i = 1 } , T 0 = { t T : t i = 0 } , T 1 = { t T :STiS0={sS:si=0}S1={sS:si=1}T0={tT:ti=0}T1={tT:ti=1} .

  3. Ahora busque recursivamente un par no superpuesto de , de S 0 , T 1 y de T 1 , S 0 . Si alguna llamada recursiva encuentra un par no superpuesto, envíelo, de lo contrario, saldrá "No existe par superpuesto".S0,T0S0,T1T1,S0

El desafío es analizar su desempeño en el peor de los casos.

Supongamos que, como paso previo al procesamiento, primero calculamos la densidad de cada posición de bit. Además, si para cadai, suponga que el paso de preprocesamiento genera "Existe un par superpuesto" (me doy cuenta de que esto no muestra un ejemplo de un par superpuesto, pero dejemos eso a un lado como un desafío separado). Todo esto se puede hacer enO(nk)Δ(i)<1/kiO(nk) time. The density information can be maintained efficiently as we do recursive calls; it won't be the dominant contributor to running time.

What will the running time of this procedure be? I'm not sure, but here are a few observations that might help. Each level of recursion reduces the problem size by about n/k bitvectors (e.g., from n bitvectors to nn/k bitvectors). Therefore, the recursion can only go about k levels deep. However, I'm not immediately sure how to count the number of leaves in the recursion tree (there are a lot less than 3k leaves), so I'm not sure what running time this should lead to.

D.W.
fuente
ad low density: this seems to be some kind of pigeon-hole argument. Maybe if we use your general idea (split w.r.t. the column with the most ones), we get better bounds because the (S1,T1)-case (we don't recurse to) already gets rid of "most" ones?
Raphael
The total number of ones may be a useful parameter. You have already shown a lower bound we can use for cutting off the tree; can we show upper bounds, too? For example, if there are more than ck ones, we have at least c overlaps.
Raphael
By the way, how do you propose we do the first split; arbitrarily? Why not just split the whole input set w.r.t. some column i? We only need to recurse in the 0-case (there is no solution among those that share a one at i). In expectation, that gives via T(n)=T(n/2)+O(nk) a bound of O(nk) (if k fixed). For a general bound, you have shown that we can (assuming the lower-bound-cutoff you propose) that we get rid of at least n/k elements with every split, which seems to imply an O(nk) worst-case bound. Or am I missing something?
Raphael
Ah, that's wrong, of course, since it does not consider 0-1-mismatches. That's what I get for trying to think before breakfast, I guess.
Raphael
@Raphael, there are two issues: (a) the vectors might be mostly zeros, so you can't count on getting a 50-50 split; the recurrence would be something more like T(n)=T((nn/k)k)+O(nk), (b) more importantly, it's not enough to just recurse on the 0-subset; you also need to examine pairings between a vector from the 0-subset and a vector from the 1-subset, so there's an additional recursion or two to do. (I think? I hope I got that right.)
D.W.
8

Faster solution when nk, using matrix multiplication

Suppose that n=k. Our goal is to do better than an O(n2k)=O(n3) running time.

We can think of the bitvectors and bit positions as nodes in a graph. There is an edge between a bitvector node and a bit position node when the bitvector has a 1 in that position. The resulting graph is bipartite (with the bitvector-representing nodes on one side and the bitposition-representing nodes on the other), and has n+k=2n nodes.

Given the adjacency matrix M of a graph, we can tell if there is a two-hop path between two vertices by squaring M and checking if the resulting matrix has an "edge" between those two vertices (i.e. the edge's entry in the squared matrix is non-zero). For our purposes, a zero entry in the squared adjacency matrix corresponds to a non-overlapping pair of bitvectors (i.e. a solution). A lack of any zeroes means there's no solution.

Squaring an n x n matrix can be done in O(nω) time, where ω is known to be under 2.373 and conjectured to be 2.

So the algorithm is:

  • Convert the bitvectors and bit positions into a bipartite graph with n+k nodes and at most nk edges. This takes O(nk) time.
  • Compute the adjacency matrix of the graph. This takes O((n+k)2) time and space.
  • Square the adjacency matrix. This takes O((n+k)ω) time.
  • Search the bitvector section of the adjacency matrix for zero entries. This takes O(n2) time.

The most expensive step is squaring the adjacency matrix. If n=k then the overall algorithm takes O((n+k)ω)=O(nω) time, which is better than the naive O(n3) time.

This solution is also faster when k grows not-too-much-slower and not-too-much-faster than n. As long as kΩ(nω2) and kO(n2ω1), then (n+k)ω is better than n2k. For w2.373 that translates to n0.731kn1.373 (asymptotically). If w limits to 2, then the bounds widen towards nϵkn2ϵ.

Craig Gidney
fuente
1. This is also better than the naive solution if k=Ω(n) but k=o(n1.457). 2. If kn, a heuristic could be: pick a random subset of n bit positions, restrict to those bit positions and use matrix multiplication to enumerate all pairs that don't overlap in those n bit positions; for each such pair, check if it solves the original problem. If there aren't many pairs that don't overlap in those n bit positions, this provides a speedup over the naive algorithm. However I don't know a good upper bound on the number of such pairs.
D.W.
4

Esto es equivalente a encontrar un vector de bits que es un subconjunto del complemento de otro vector; es decir, sus 1 ocurren solo donde 0 ocurren en el otro.

Si k (o el número de 1) es pequeño, puede obtener O(norte2k)tiempo simplemente generando todos los subconjuntos del complemento de cada bitvector y colocándolos en un trie (usando el seguimiento). Si se encuentra un vector de bits en el trie (podemos verificar cada uno antes de la inserción del complemento-subconjunto), entonces tenemos un par no superpuesto.

Si el número de 1 o 0 está limitado a un número aún menor que k, entonces el exponente puede ser reemplazado por eso. La indexación de subconjuntos puede estar en cada vector o en su complemento, siempre que el sondeo utilice lo contrario.

There's also a scheme for superset-finding in a trie that only stores each vector only once, but does bit-skipping during probes for what I believe is similar aggregate complexity; ie it has o(k) insertion but o(2k) searches.

KWillets
fuente
thanks. The complexity of your solution is n2(1p)k, where p is the probability of 1's in the bitvector. A couple of implementation details: though this is a slight improvement, there's no need to compute and store the complements in the trie. Just following the complementary branches when checking for a non-overlapping match is enough. And, taking the 0's directly as wildcards, no special wildcard is needed, either.
Mauro Lacy
2

Represent the bit vectors as an n×k matrix M. Take i and j between 1 and n.

(MMT)ij=lMilMjl.

(MMT)ij, the dot product of the ith and jth vector, is non-zero if, and only if, vectors i and j share a common 1. So, to find a solution, compute MMT and return the position of a zero entry, if such an entry exists.

Complexity

Using naive multiplication, this requires O(n2k) arithmetic operations. If n=k, it takes O(n2.37) operations using the utterly impractical Coppersmith-Winograd algorithm, or O(n2.8) using the Strassen algorithm. If k=O(n0.302), then the problem may be solved using n2+o(1) operations.

Ben
fuente
How is this different from Strilanc's answer?
D.W.
1
@D.W. Using an n-by-k matrix instead of an (n+k)-by-(n+k) matrix is an improvement. Also it mentions a way to cut off the factor of k when k << n, so that might be useful.
Craig Gidney