Finden eines Paares nicht überlappender Bitvektoren

17

Ich gebe Ihnen eine Liste von Bitvektoren der Breite . Ihr Ziel ist es, zwei Bitvektoren aus der Liste zurückzugeben, die keine 1 gemeinsam haben, oder zu melden, dass kein solches Paar existiert.nk

Wenn ich Ihnen zum Beispiel ist die einzige Lösung . Alternativ hat die Eingabe keine Lösung. Und jede Liste, die den All-Null-Bitvektor und ein anderes Element hat eine triviale Lösung .[00110,01100,11000]{00110,11000}[111,011,110,101]000...0e{e,000...0}

Hier ist ein etwas schwierigeres Beispiel ohne Lösung (jede Zeile ist ein Bitvektor, die schwarzen Quadrate sind 1s und die weißen Quadrate sind 0s):

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

Wie effizient können zwei nicht überlappende Bitvektoren gefunden werden oder es kann gezeigt werden, dass sie nicht existieren?

Der naive Algorithmus, bei dem Sie einfach jedes mögliche Paar vergleichen, ist . Kann man es besser machen?O(n2k)

Craig Gidney
quelle
Eine mögliche Reduktion: Sie haben einen Graphen mit einem Scheitelpunkt für jeden Vektor und einer Kante zwischen zwei Scheitelpunkten, wenn die beiden entsprechenden Vektoren eine 1 gemeinsam haben. Sie möchten wissen, ob der Diagrammdurchmesser . Aber es scheint schwierig zu sein, schneller zu sein als . G2O(n2k)
François
@ FrançoisGodi Jede verbundene Graphkomponente mit drei Knoten und einer fehlenden Kante hat einen Durchmesser von mindestens zwei. Bei einer Adjazenzlistendarstellung dauert es Zeit, um dies zu überprüfen. O(V)
Craig Gidney
@ Strilanc Sicher, wenn es keine Lösung gibt, ist das Diagramm vollständig (klarer als Durchmesser = 1, Sie haben Recht), aber die Berechnung der Adjazenzlistendarstellung könnte lang sein.
François
Ist kleiner als die Wortbreite Ihrer Maschine? k
Raphael
1
@TomvanderZanden Das hört sich so an, als würde es Invarianten verletzen, auf die sich die Datenstruktur wahrscheinlich stützt. Insbesondere sollte diese Gleichheit transitiv sein. Ich habe bereits darüber nachgedacht, einen Trie zu verwenden, und ich weiß nicht, wie ich jedes Mal, wenn die Abfrage-Bitmaske eine 0 hat, eine Vergrößerung um den Faktor 2 vermeiden kann.
Craig Gidney

Antworten:

10

Aufwärmen: Zufällige Bitvektoren

Zum Aufwärmen können wir mit dem Fall beginnen, in dem jeder Bitvektor gleichmäßig zufällig ausgewählt wird. Dann stellt sich heraus, dass das Problem in der Zeit gelöst werden kann (genauer gesagt, die kann durch ).O(n1.6min(k,lgn))lg 31.6lg3

Wir werden die folgende zweistufige Variante des Problems betrachten:

Bestimmen Sie bei gegebenen Mengen von Bitvektoren, wo es ein nicht überlappendes Paar . s S , t TS,T{0,1}ksS,tT

Die grundlegende Technik, um dies zu lösen, ist das Teilen und Erobern. Hier ist ein -Zeitalgorithmus mit Divide-and-Conquer:O(n1.6k)

  1. Split und auf der Basis der ersten Bit - Position. Mit anderen Worten, Form , , , .T S 0 = { s S : s 0 = 0 } S 1 = { s S : s 0 = 1 } T 0 = { t T : t 0 = 0 }STS0={sS:s0=0}S1={sS:s0=1}T0={tT:t0=0}T1={tT:t0=1}

  2. Suchen Sie nun rekursiv nach einem nicht überlappenden Paar aus , und . Wenn ein rekursiver Aufruf ein nicht überlappendes Paar findet, geben Sie es aus. Anderenfalls wird "Kein überlappendes Paar vorhanden" ausgegeben.S 0 , T 1 T 1 , S 0S0,T0S0,T1T1,S0

Da alle Bitvektoren zufällig ausgewählt werden, können wir erwarten und . Wir haben also drei rekursive Aufrufe und haben das Problem um den Faktor zwei verkleinert (beide Mengen sind um den Faktor zwei verkleinert). Nach der hat eine der beiden Mengen die Größe 1, und das Problem kann in linearer Zeit gelöst werden. Wir erhalten eine Wiederholungsrelation nach , deren Lösung . Wenn wir die Laufzeit genauer in dem Fall mit zwei Mengen berücksichtigen, sehen wir, dass die Laufzeit .| T b | | T | / 2 lg min ( | S | , | T | ) T ( n ) = 3 T ( n / 2 ) + O ( n k ) T ( n ) = O ( n 1,6 k ) O|Sb||S|/2|Tb||T|/2lgmin(|S|,|T|)T(n)=3T(n/2)+O(nk)T(n)=O(n1.6k)O(min(|S|,|T|)0.6max(|S|,|T|)k)

Dies kann weiter verbessert werden, indem bemerkt wird, dass die Wahrscheinlichkeit, dass ein nicht überlappendes Paar existiert, exponentiell klein ist , wenn ist. Insbesondere wenn zwei Zufallsvektoren sind, ist die Wahrscheinlichkeit, dass sie sich nicht überlappen, . Wenn , gibt es solcher Paare, so dass durch eine Vereinigungsgrenze die Wahrscheinlichkeit, dass ein nicht überlappendes Paar existiert, höchstens beträgt . Wenn , ist dies . Also als Vorverarbeitungsschritt, wennx , y ( 3 / 4 ) k | S | = | T | = N n 2 n 2 ( 3 / 4 ) k k 2,5 lg n + 100 1 / 2 100 k 2,5 lg n + 100k2.5lgn+100x,y(3/4)k|S|=|T|=nn2n2(3/4)kk2.5lgn+1001/2100k2.5lgn+100, dann können wir sofort "Kein nicht überlappendes Paar existiert" zurückgeben (die Wahrscheinlichkeit, dass dies falsch ist, ist vernachlässigbar gering), andernfalls führen wir den obigen Algorithmus aus.

Somit erreichen wir eine Laufzeit von (oder für die oben vorgeschlagene Zwei-Mengen-Variante), für den Sonderfall, dass die Bitvektoren gleichmäßig zufällig gewählt werden.O ( min ( | S | , | T | ) 0,6 max ( | S | , | T | ) min ( k , lg n ) )O(n1.6min(k,lgn))O(min(|S|,|T|)0.6max(|S|,|T|)min(k,lgn))

Dies ist natürlich keine Worst-Case-Analyse. Zufällige Bitvektoren sind erheblich einfacher als der schlimmste Fall - aber betrachten wir es als Aufwärmen, um einige Ideen zu erhalten, die wir vielleicht auf den allgemeinen Fall anwenden können.

Lehren aus dem Aufwärmen

Wir können ein paar Lektionen aus dem obigen Aufwärmen lernen. Zunächst scheint das Teilen und Erobern (Aufteilen auf eine Bitposition) hilfreich zu sein. Zweitens wollen Sie auf eine Bit - Position teilen mit so vielen ‚s in dieser Position wie möglich; desto mehr ist da sind, können Sie die weniger Reduktion in Subproblem Größe.010

Drittens legt dies nahe , dass das Problem wird noch schwieriger als die Dichte von ‚s wird kleiner - wenn es nur sehr wenige ist ‘ s unter dem bitvectors (sie sind meist ‚s), das Problem sieht ziemlich hart, da jede Spaltung reduziert die größe der subprobleme ein wenig. Definieren Sie also die Dichte als den Bruchteil der Bits, die (dh von allen Bits), und die Dichte der Bitposition als den Bruchteil der Bitvektoren, die an Position .1 0 Δ 1 n k i 1 i110Δ1nki1i

Handhabung sehr geringer Dichte

Als nächster Schritt könnten wir uns fragen, was passiert, wenn die Dichte extrem klein ist. Es stellt sich heraus, dass, wenn die Dichte an jeder Bitposition kleiner als , wir garantiert sind, dass ein nicht überlappendes Paar existiert: Es gibt ein (nicht konstruktives) Existenzargument, das zeigt, dass sich einige nicht überlappen Paar muss existieren. Das hilft uns nicht, es zu finden, aber zumindest wissen wir, dass es existiert.1/k

Warum ist das so? Angenommen, ein Paar von Bitvektoren wird durch die Bitposition abgedeckt, wenn . Beachten Sie, dass jedes Paar überlappender Bitvektoren durch eine Bitposition abgedeckt sein muss. Wenn wir nun eine bestimmte Bitposition festlegen , beträgt die Anzahl der Paare, die von dieser Bitposition abgedeckt werden können, höchstens . Summiert man über alle der Bitpositionen, so ergibt sich, dass die Gesamtzahl der Paare, die von einer Bitposition abgedeckt werden,i x i = y i = 1 i ( n & Dgr; ( i ) ) 2 < n 2 / k k < n 2x,yixi=yi=1i(nΔ(i))2<n2/kk<n2. Dies bedeutet, dass es ein Paar geben muss, das von keiner Bitposition abgedeckt wird, was bedeutet, dass sich dieses Paar nicht überlappt. Wenn also die Dichte in jeder Bitposition ausreichend niedrig ist, dann existiert mit Sicherheit ein nicht überlappendes Paar.

Ich bin jedoch nicht in der Lage, einen schnellen Algorithmus zu finden, um ein solches nicht überlappendes Paar in diesem Regime zu finden, obwohl garantiert ist, dass eines existiert. Ich sehe nicht sofort irgendwelche Techniken, die eine Laufzeit ergeben würden, die eine subquadratische Abhängigkeit von . Dies ist also ein netter Spezialfall, auf den Sie sich konzentrieren sollten, wenn Sie etwas Zeit zum Nachdenken über dieses Problem verwenden möchten.n

Hin zu einem allgemeinen Algorithmus

Im allgemeinen Fall scheint eine natürliche Heuristik zu sein: die Bit - Position holen mit der größten Anzahl an (mit der höchsten Dichte dh) ‚s und Split auf sich. Mit anderen Worten:1i1

  1. Suchen Sie eine Bitposition , die maximiert .Δ ( i )iΔ(i)

  2. Teile und basierend auf der Bitposition . Mit anderen Worten, Form , , , .T i 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 : t i = 1 }STiS0={sS:si=0}S1={sS:si=1}T0={tT:ti=0}T1={tT:ti=1}

  3. Suchen Sie nun rekursiv nach einem nicht überlappenden Paar aus , und . Wenn ein rekursiver Aufruf ein nicht überlappendes Paar findet, geben Sie es aus. Anderenfalls wird "Kein überlappendes Paar vorhanden" ausgegeben.S 0 , T 1 T 1 , S 0S0,T0S0,T1T1,S0

Die Herausforderung besteht darin, die Leistung im schlimmsten Fall zu analysieren.

Nehmen wir an, dass wir als Vorverarbeitungsschritt zuerst die Dichte jeder Bitposition berechnen. Auch wenn für jedes , wird angenommen, dass der Vorverarbeitungsschritt "Ein überlappendes Paar existiert" ausgibt (ich stelle fest, dass dies kein Beispiel für ein überlappendes Paar darstellt, Aber lassen Sie uns das als separate Herausforderung beiseite stellen. All dies kann in Zeit erledigt werden. Die Dichteinformationen können bei rekursiven Aufrufen effizient verwaltet werden. Es wird nicht der dominierende Beitrag zur Laufzeit sein. iO(nk)Δ(i)<1/kiO(nk)

Wie wird die Laufzeit dieses Verfahrens sein? Ich bin nicht sicher, aber hier sind einige Beobachtungen, die helfen könnten. Jede Rekursionsstufe verringert die Problemgröße um ungefähr Bitvektoren (z. B. von Bitvektoren zu Bitvektoren). Daher kann die Rekursion nur ungefähr Ebenen tief gehen. Ich bin mir jedoch nicht sofort sicher, wie ich die Anzahl der Blätter im Rekursionsbaum zählen soll (es gibt viel weniger als Blätter), daher bin ich mir nicht sicher, zu welcher Laufzeit dies führen soll zu. nn-n/n/knnn/k 3k3k

DW
quelle
Eine geringe Dichte: Dies scheint eine Art Argument für ein Taubenloch zu sein. Vielleicht, wenn wir Ihre allgemeine Idee verwenden (teilen Sie die Spalte mit den meisten), erhalten wir bessere Grenzen, weil der -Fall (auf den wir nicht zurückgreifen) bereits "die meisten" beseitigt? (S1,T1)
Raphael
Die Gesamtanzahl von Einsen kann ein nützlicher Parameter sein. Sie haben bereits eine Untergrenze angezeigt, mit der wir den Baum abschneiden können. können wir auch obere grenzen anzeigen? Wenn es zum Beispiel mehr als gibt, haben wir mindestens Überlappungen. cckc
Raphael
Übrigens, wie schlagen Sie vor, dass wir den ersten Split machen? willkürlich? Warum nicht einfach den gesamten Eingabesatz in eine Spalte aufteilen ? Wir müssen nur im Fall rekursieren (es gibt keine Lösung unter denen, die eine Eins bei teilen ). Dies ergibt erwartungsgemäß über eine Grenze von (wenn fest ist). Für eine allgemeine Schranke haben Sie gezeigt, dass wir (unter der Annahme des von Ihnen vorgeschlagenen unteren Schrankenwerts) bei jeder Aufteilung mindestens Elemente entfernen können, was ein zu implizieren scheint. im schlimmsten Fall gebunden. Oder vermisse ich etwas? ii T ( n ) = T ( n / 2 ) + O ( n k ) O ( n k ) , k n / 0iT(n)=T(n/2)+O(nk)O(nk)k O(nk)n/kO(nk)
Raphael
Ah, das ist natürlich falsch, da es keine 0-1-Fehlpaarungen berücksichtigt. Das ist es, was ich bekomme, wenn ich versuche, vor dem Frühstück nachzudenken.
Raphael
@Raphael, es gibt zwei Probleme: (a) Die Vektoren können größtenteils Nullen sein, Sie können also nicht damit rechnen, eine 50-50-Aufteilung zu erhalten. die Wiederholung wäre eher wie , (b) was noch wichtiger ist, es ist nicht genug, nur auf die 0-Teilmenge zurückzugreifen; Sie müssen auch die Paarungen zwischen einem Vektor aus der 0-Teilmenge und einem Vektor aus der 1-Teilmenge untersuchen, damit ein oder zwei zusätzliche Rekursionen durchgeführt werden können. (Ich denke? Ich hoffe, ich habe das richtig verstanden.)T(n)=T((nn/k)k)+O(nk)
DW
8

Schnellere Lösung bei durch Matrixmultiplikationnk

Angenommen, . Unser Ziel ist es, besser als eine Laufzeit von sein.O ( n 2 k ) = O ( n 3 )n=kO(n2k)=O(n3)

Wir können uns die Bitvektoren und Bitpositionen als Knoten in einem Graphen vorstellen. Es gibt eine Kante zwischen einem Bitvektorknoten und einem Bitpositionsknoten, wenn der Bitvektor an dieser Position eine 1 hat. Der resultierende Graph ist zweigeteilt (mit den Bitvektor-darstellenden Knoten auf der einen Seite und den Bitpositions-darstellenden Knoten auf der anderen Seite) und weist Knoten auf.n+k=2n

Anhand der Adjazenzmatrix eines Graphen können wir feststellen, ob zwischen zwei Scheitelpunkten ein Zwei-Sprung-Pfad besteht, indem wir quadrieren und überprüfen, ob die resultierende Matrix eine "Kante" zwischen diesen beiden Scheitelpunkten aufweist (dh den Eintrag der Kante in der quadratischen Matrix) ist nicht Null). Für unsere Zwecke entspricht ein Null-Eintrag in der quadratischen Adjazenzmatrix einem nicht überlappenden Paar von Bitvektoren (dh einer Lösung). Fehlen Nullen, gibt es keine Lösung.MM M

Das Quadrieren einer nxn-Matrix kann in , wobei bekannt ist , dass unter und angenommen wird, dass es .ω 2.373 2O(nω)ω2.3732

Der Algorithmus lautet also:

  • Wandle die Bitvektoren und Bitpositionen in einen zweigeteilten Graphen mit Knoten und höchstens Kanten um. Dies benötigt Zeit.n k O ( n k )n+knkO(nk)
  • Berechnen Sie die Adjazenzmatrix des Graphen. Dies benötigt Zeit und Raum.O((n+k)2)
  • Quadrieren Sie die Adjazenzmatrix. Dies benötigt Zeit.O((n+k)ω)
  • Durchsuchen Sie den Bitvektorabschnitt der Adjazenzmatrix nach Null-Einträgen. Dies benötigt Zeit.O(n2)

Der teuerste Schritt ist das Quadrieren der Adjazenzmatrix. Wenn dann nimmt der Gesamtalgorithmus die Zeit , was besser ist als die naive Zeit .O ( ( n + k ) ω ) = O ( n ω ) O ( n 3 )n=kO((n+k)ω)=O(nω)O(n3)

Diese Lösung ist auch schneller, wenn nicht zu viel langsamer und nicht zu viel schneller wächst als . Solange und , ist besser als . Für das (asymptotisch). Wenn auf 2 begrenzt ist, erweitern sich die Grenzen in Richtung .n k Ω ( n ω - 2 ) k O ( n 2knkΩ(nω2)(n+k)ωn2kw2,373n0,731kn1,373wnεkn2-εkO(n2ω1)(n+k)ωn2kw2.373n0.731kn1.373wnϵkn2ϵ

Craig Gidney
quelle
1. Dies ist auch besser als die naive Lösung, wenn aber . 2. Wenn , könnte eine Heuristik sein: Wählen Sie eine zufällige Untermenge von Bitpositionen, beschränken Sie sich auf diese Bitpositionen und verwenden Sie die Matrixmultiplikation, um alle Paare aufzulisten, die sich in diesen Bitpositionen nicht überlappen . Prüfen Sie für jedes dieser Paare, ob es das ursprüngliche Problem löst. Wenn es nicht viele Paare gibt, die sich an diesen Bitpositionen nicht überlappen , wird der naive Algorithmus beschleunigt. Allerdings kenne ich keine gute Obergrenze für die Anzahl solcher Paare. k = o ( n 1,457 ) k n n n nk=Ω(n)k=o(n1.457)knnnn
DW
4

Dies ist äquivalent zum Finden eines Bitvektors, der eine Teilmenge des Komplements eines anderen Vektors ist; Das heißt, seine Einsen treten nur dort auf, wo Nullen in der anderen auftreten.

Wenn k (oder die Anzahl der Einsen ) klein ist, können Sie die -Zeit erhalten, indem Sie einfach alle Teilmengen des Komplements jedes Bitvektors generieren und sie in einen Trie setzen (unter Verwendung von Backtracking). Wenn im Trie ein Bitvektor gefunden wird (wir können jeden vor dem Einfügen der Komplement-Teilmenge überprüfen), dann haben wir ein nicht überlappendes Paar.O(n2k)

Wenn die Anzahl der Einsen oder Nullen auf eine noch niedrigere Zahl als k begrenzt ist, kann der Exponent dadurch ersetzt werden. Die Teilmengenindizierung kann entweder für jeden Vektor oder für sein Komplement erfolgen, sofern bei der Prüfung das Gegenteil verwendet wird.

Es gibt auch ein Schema für die Suche nach Supersätzen in einem Trie, bei dem jeder Vektor nur einmal gespeichert wird, aber bei Tests Bit-Skipping ausgeführt wird, wenn ich der Meinung bin, dass es sich um eine ähnliche Gesamtkomplexität handelt. dh es hat Einfügung, aber sucht.o ( 2 k )o(k)o(2k)

KWillets
quelle
Vielen Dank. Die Komplexität Ihrer Lösung ist , wobei die Wahrscheinlichkeit von Einsen im Bitvektor ist. Einige Details zur Implementierung: Dies ist zwar eine leichte Verbesserung, es ist jedoch nicht erforderlich, die Ergänzungen im Test zu berechnen und zu speichern. Es reicht aus, den komplementären Zweigen zu folgen, wenn nach einer nicht überlappenden Übereinstimmung gesucht wird. Und da die Nullen direkt als Platzhalter verwendet werden, ist auch kein spezieller Platzhalter erforderlich. n2(1p)kp
Mauro Lacy
2

Stellen Sie die Bitvektoren als eine Matrix . Nehmen Sie und zwischen 1 und .n×kMijn

(MMT)ij=lMilMjl.

(MMT)ij , das Skalarprodukt des ten und ten Vektors, ist ungleich Null, wenn und nur wenn die Vektoren und eine gemeinsame 1 haben. Berechnen Sie also , um eine Lösung zu finden und geben die Position eines Null-Eintrags zurück, falls ein solcher Eintrag existiert.ijijMMT

Komplexität

Unter Verwendung der naiven Multiplikation erfordert dies -Arithmetikoperationen. Wenn , werden -Operationen unter Verwendung des äußerst unpraktischen Coppersmith-Winograd-Algorithmus oder Verwendung des Strassen-Algorithmus ausgeführt. Wenn , kann das Problem unter Verwendung von Operationen gelöst werden .n = k O ( n 2,37 ) O ( n 2,8 ) k = O ( n 0,302 ) n 2 + o ( 1 )O(n2k)n=kO(n2.37)O(n2.8)k=O(n0.302)n2+o(1)

Ben
quelle
Wie unterscheidet sich das von der Antwort von Strilanc ?
DW
1
@DW Die Verwendung einer by- Matrix anstelle einer -by- -Matrix ist eine Verbesserung. Es wird auch eine Möglichkeit erwähnt, den Faktor von k abzuschneiden, wenn k << n ist, so dass dies nützlich sein könnte. k ( n + k ) ( n + k )nk(n+k)(n+k)
Craig Gidney