Znajdowanie pary nie nakładających się wektorów bitowych

17

Daję ci listę wektorów bitowych o szerokości . Twoim celem jest zwrócenie dwóch wektorów bitowych z listy, które nie mają wspólnych 1, lub zgłoszenie, że taka para nie istnieje.n nkk

Na przykład, jeśli dam ci wówczas jedynym rozwiązaniem jest . Alternatywnie, wejście nie ma rozwiązania. Każda lista zawierająca całkowicie zerowy bitvector i inny element ma trywialne rozwiązanie .[ 00110 , 01100 , 11000 ] [00110,01100,11000]{ 00110 , 11000 } {00110,11000}[ 111 , 011 , 110 , 101 ] [111,011,110,101]000 ... 0 000...0e e{ e , 000 ... 0 }{e,000...0}

Oto nieco trudniejszy przykład, bez rozwiązania (każdy wiersz jest nieco wektorem, czarne kwadraty to 1s, a białe kwadraty to 0s):

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

Jak skutecznie można znaleźć dwa nienakładające się wektory bitowe lub pokazać, że nie istnieją?

Naiwnym algorytmem, w którym po prostu porównujesz każdą możliwą parę, jest . Czy można to zrobić lepiej?O ( n 2 k )O(n2k)

Craig Gidney
źródło
Możliwa redukcja: masz wykres z jednym wierzchołkiem dla każdego wektora i krawędzią między dwoma wierzchołkami, jeśli dwa odpowiadające wektory mają wspólną wartość 1. Chcesz wiedzieć, czy średnica wykresu wynosi . Wydaje się jednak, że trudno jest jechać szybciej niż . G G2 2O ( n 2 k )O(n2k)
François
@ FrançoisGodi Dowolny podłączony komponent wykresu z trzema węzłami i brakującą krawędzią ma średnicę co najmniej dwóch. W przypadku reprezentacji listy przyległości sprawdzenie tego zajmuje . O ( V )O(V)
Craig Gidney
@ Trilanc Pewnie, jeśli nie ma rozwiązania, wykres jest kompletny (bardziej przejrzysty niż średnica = 1, masz rację), ale obliczenie reprezentacji listy sąsiadów może być długie.
François
Czy mniejszy niż szerokość słowa twojej maszyny? kk
Raphael
1
@TomvanderZanden To brzmi, jakby naruszałoby niezmienniki, na których prawdopodobnie opiera się struktura danych. W szczególności równość ta powinna być przechodnia. Myślałem już o użyciu wersji próbnej i nie wiem, jak uniknąć
powiększenia

Odpowiedzi:

10

Rozgrzewanie: losowe wektory bitowe

Jako rozgrzewkę możemy zacząć od przypadku, w którym każdy bitvector jest wybierany losowo równomiernie. Potem okazuje się, że problem można rozwiązać w czasie (a dokładniej można zastąpić ).O ( N : 1,6 min ( k , lg n ) ) 1,6 lg 3O(n1.6min(k,lgn))1.6lg3

Rozważymy następujący dwuczęściowy wariant problemu:

Podane zestawy z bitvectors określić, gdzie istnieje nienakładające się para .S , T { 0 , 1 } k s S , t TS,T{0,1}ksS,tT

Podstawową techniką rozwiązania tego jest dzielenie i podbijanie. Oto algorytm czasowy przy użyciu funkcji dziel i zwycięż:O ( n 1,6 k )O(n1.6k)

  1. Podziel i podstawie pierwszej pozycji bitu. Innymi słowy, formularz , , , .S T S 0 = { s S : s 0 = 0 } S 1 = { s S : s 0 = 1 } T 0 = { t T : t 0 = 0 } T 1 = { t T : t 0 = 1 }STS0={sS:s0=0}S1={sS:s0=1}T0={tT:t0=0}T1={tT:t0=1}

  2. Teraz rekurencyjnie szukaj pary nienakładającej się z , z oraz z . Jeśli jakieś wywołanie rekurencyjne znajdzie parę, która się nie nakłada, wyślij ją, w przeciwnym razie wyślij „Nie ma pary nakładających się”.S 0 , T 0 S 0 , T 1 T 1 , S 0S0,T0S0,T1T1,S0

Ponieważ wszystkie wektory bitowe są wybierane losowo, możemy spodziewać się i . Mamy więc trzy rekurencyjne wywołania i zmniejszyliśmy rozmiar problemu dwa razy (oba zestawy są zmniejszone dwa razy). Po jeden z dwóch zestawów ma rozmiar 1, a problem można rozwiązać w czasie liniowym. Otrzymujemy relację powtarzalności wzdłuż linii , których rozwiązaniem jest . Uwzględniając czas wykonywania dokładniej w przypadku dwóch zestawów, widzimy, że czas działania wynosi .| S b | | S | / 2 | 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) ( min ( | S | , | T | ) 0,6 maks. ( | S | , | T | ) k )O(min(|S|,|T|)0.6max(|S|,|T|)k)

Można to jeszcze poprawić, zauważając, że jeśli , prawdopodobieństwo istnienia pary, która się nie pokrywa, jest wykładniczo małe. W szczególności, jeśli są dwoma losowymi wektorami, prawdopodobieństwo, że się nie pokrywają, wynosi . Jeśli , istnieje takich par, więc przez związanie, prawdopodobieństwo istnienia pary, która się nie nakłada, wynosi najwyżej . Kiedy , to . Tak więc, jako etap wstępnego przetwarzania, jeślik 2,5 lg n + 100 x , r ( 3 / 4 ), k | S | = | T | = N n 2 n 2 ( 3 / 4 ) k k 2,5 lg n + 100k2.5lgn+100x,y(3/4)k|S|=|T|=nn2n2(3/4)kk2.5lgn+1001 / 2 100 K 2,5 lg n + 1001/2100k2.5lgn+100, wówczas możemy natychmiast zwrócić „Nie ma pary nienakładającej się” (prawdopodobieństwo, że jest to niepoprawne, jest pomijalnie małe), w przeciwnym razie uruchomimy powyższy algorytm.

W ten sposób osiągamy czas działania (lub dla wariantu dwóch zestawów zaproponowanego powyżej), dla specjalnego przypadku, w którym bitwektory są wybierane równomiernie losowo.O ( n 1,6 min ( k , lg n ) ) O ( min ( | S | , | T | ) 0,6 maks. ( | S | , | T | ) min ( k , lg n ) )O(n1.6min(k,lgn))O(min(|S|,|T|)0.6max(|S|,|T|)min(k,lgn))

Oczywiście nie jest to najgorsza analiza. Losowe wektory bitowe są znacznie łatwiejsze niż najgorszy przypadek - ale traktujmy to jako rozgrzewkę, aby uzyskać kilka pomysłów, które być może moglibyśmy zastosować w przypadku ogólnym.

Lekcje z rozgrzewki

Możemy nauczyć się kilku lekcji z powyższej rozgrzewki. Po pierwsze, pomocna jest funkcja dziel i zwyciężaj (dzielenie na pozycję bitową). Po drugie, chcesz podzielić się na pozycji bitowej z jak największą liczbą w tej pozycji; im więcej , tym mniejsze zmniejszenie wielkości podproblemu.1 010

Po trzecie, sugeruje to, że problem staje się trudniejszy, gdy gęstość jest mniejsza - jeśli wśród bitvektorów jest bardzo niewiele (są to w większości ), problem wygląda dość trudny, ponieważ każdy podział zmniejsza się wielkość podproblemów trochę. Zdefiniuj więc gęstość jako ułamek bitów, które są (tj. Spośród wszystkich bitów ), a gęstość pozycji bitu aby była ułamkiem wektorów bitowych, które są w pozycji .1 1 0 Δ 1 n k i 1 i110Δ1nki1i

Obsługa bardzo niskiej gęstości

W kolejnym kroku możemy zastanawiać się, co się stanie, jeśli gęstość będzie wyjątkowo mała. Okazuje się, że jeśli gęstość w każdej pozycji bitowej jest mniejsza niż , gwarantujemy, że istnieje para nie nakładająca się: istnieje (niekonstruktywny) argument istnienia wskazujący, że niektóre nie nakładające się para musi istnieć. To nie pomaga nam go znaleźć, ale przynajmniej wiemy, że istnieje.1 / k1/k

Dlaczego tak jest? Powiedzmy, że para wektorów bitowych jest objęta pozycją bitu jeśli . Zauważ, że każda para nakładających się wektorów bitowych musi być zakryta przez jakąś pozycję bitu. Teraz, jeśli naprawimy określoną pozycję bitu , liczba par, które mogą być objęte tą pozycją bitu, wynosi co najwyżej . Podsumowując wszystkie pozycji bitów, stwierdzamy, że łączna liczba par objętych pewną pozycją bitową wynosix , y i x I = Y i = 1 i ( n Δ ( I ) )x,yixi=yi=1i 2 < n 2 / k k < n 2(nΔ(i))2<n2/kk<n2. Oznacza to, że musi istnieć para, która nie jest objęta żadną pozycją bitową, co oznacza, że ​​ta para się nie nakłada. Jeśli więc gęstość jest wystarczająco niska w każdej pozycji bitowej, z pewnością istnieje para, która się nie nakłada.

Jednak nie mogę zidentyfikować szybkiego algorytmu, aby znaleźć taką nie nakładającą się parę w tych reżimach, nawet jeśli jedna z nich istnieje. Nie widzę od razu żadnych technik, które zapewniłyby czas działania zależny od kwadratury od . Jest to więc miły szczególny przypadek, na którym można się skoncentrować, jeśli chcesz poświęcić trochę czasu na przemyślenie tego problemu.nn

W kierunku algorytmu ogólnego przypadku

W ogólnym przypadku naturalna heurystyka wydaje się być: wybierz pozycję bitu z największą liczbą (tj. O największej gęstości) i podziel na nią. Innymi słowy:i 1i1

  1. Znajdź pozycję bitową która maksymalizuje .i Δ ( i )iΔ(i)

  2. Podział i podstawie pozycji bitu . Innymi słowy, formularz , , , .S 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. Teraz rekurencyjnie szukaj pary nienakładającej się z , z oraz z . Jeśli jakieś wywołanie rekurencyjne znajdzie parę, która się nie nakłada, wyślij ją, w przeciwnym razie wyślij „Nie ma pary nakładających się”.S 0 , T 0 S 0 , T 1 T 1 , S 0S0,T0S0,T1T1,S0

Wyzwanie polega na analizie jego wydajności w najgorszym przypadku.

Załóżmy, że jako krok przetwarzania wstępnego najpierw obliczamy gęstość każdej pozycji bitu. Ponadto, jeśli dla każdego , przyjmijmy, że krok wstępnego przetwarzania daje wynik „Istnieje nakładająca się para” (zdaję sobie sprawę, że nie pokazuje to przykładu nakładającej się pary, ale odłóżmy to na bok jako osobne wyzwanie). Wszystko to można zrobić w czasie . Informacje o zagęszczeniu mogą być skutecznie utrzymywane, gdy wykonujemy połączenia rekurencyjne; nie będzie dominującym czynnikiem wpływającym na czas działania.Δ ( i ) < 1 / k iO(nk)Δ(i)<1/kiO(nk)

Jaki będzie czas trwania tej procedury? Nie jestem pewien, ale oto kilka spostrzeżeń, które mogą pomóc. Każdy poziom rekurencji zmniejsza rozmiar problemu o około bitvectors (np. Od bitvectors do bitvectors). Dlatego rekurencja może wchodzić tylko na głębokości około . Jednak nie jestem od razu pewny, jak policzyć liczbę liści w drzewie rekurencyjnym (jest dużo mniej niż liści), więc nie jestem pewien, jaki czas powinien to prowadzić do.n / kn/k n n - n / nknn/kk 3kk3k

DW
źródło
i niska gęstość: wydaje się to rodzajem kłótni o szufladkę. Może jeśli użyjemy twojego ogólnego pomysłu (podziel na kolumnę z większością), uzyskamy lepsze granice, ponieważ obudowa (S_1 (do której się nie powracamy) już pozbywa się „większości”? ( S 1 , T 1 )(S1,T1)
Raphael
Łączna liczba z nich może być użytecznym parametrem. Pokazałeś już dolną granicę, której możemy użyć do odcięcia drzewa; czy możemy też pokazać górne granice? Na przykład, jeśli jest ich więcej niż , mamy co najmniej nakładania się. c k cckc
Raphael
Nawiasem mówiąc, jak proponujesz zrobić pierwszy podział; dowolnie? Dlaczego nie podzielić całego zestawu danych wejściowych na kolumnę ? Musimy tylko powtarzać w przypadku (nie ma rozwiązania wśród tych, którzy korzystają z jednego w ). W oczekiwaniu daje to przez granicę (jeśli ustalona). Jeśli chodzi o ogólne ograniczenie, wykazałeś, że możemy (zakładając, że zaproponujesz niższy limit graniczny), że pozbywamy się co najmniej elementów przy każdym podziale, co wydaje się sugerować w najgorszym przypadku. A może coś mi brakuje? i 0 i T ( n ) = T ( n / 2 ) + O ( n k ) O ( n k ) k n / i0iT(n)=T(n/2)+O(nk)O(nk)kk O(nk)n/kO(nk)
Raphael
Ach, to oczywiście nie tak, ponieważ nie uwzględnia niezgodności 0-1. Chyba tak myślę przed próbą śniadania.
Raphael
@ Rafael, istnieją dwa problemy: (a) wektory mogą być głównie zerami, więc nie możesz liczyć na uzyskanie podziału 50-50; powtórzenie byłoby czymś bardziej podobnym do , (b) co ważniejsze, nie wystarczy po prostu powtórzyć na podzbiorze 0; musisz także zbadać pary między wektorem z podzbioru 0 i wektorem z podzbioru 1, więc jest dodatkowa rekurencja lub dwie do zrobienia. (Chyba? Mam nadzieję, że mi się to udało.)T(n)=T((nn/k)k)+O(nk)T(n)=T((nn/k)k)+O(nk)
DW
8

Szybsze rozwiązanie, gdy , przy użyciu mnożenia macierzynknk

Załóżmy, że . Naszym celem jest osiągnięcie lepszych wyników niż czas działania .n=kn=kO(n2k)=O(n3)O(n2k)=O(n3)

Możemy myśleć o wektorach bitowych i pozycjach bitowych jak o węzłach na wykresie. Pomiędzy węzłem bitvector a węzłem pozycji bitowej występuje krawędź, gdy bitvector ma 1 w tej pozycji. Powstały wykres jest dwustronny (z węzłami reprezentującymi bitvector z jednej strony i węzłami reprezentującymi położenie bitowe z drugiej) i ma węzłów.n+k=2nn+k=2n

Biorąc pod uwagę macierz przylegania wykresu, możemy stwierdzić, czy istnieje ścieżka dwóch przeskoków między dwoma wierzchołkami, poprzez podniesienie kwadratu i sprawdzenie, czy otrzymana macierz ma „krawędź” między tymi dwoma wierzchołkami (tj. Wejście krawędzi w macierz kwadratową jest niezerowa). Dla naszych celów zero wpisu w kwadratowej macierzy przylegania odpowiada nie nakładającej się parze wektorów bitowych (tzn. Rozwiązanie). Brak zer oznacza, że ​​nie ma rozwiązania.MM MM

Kwadratowanie macierzy nxn można wykonać w czasie , gdzie wiadomo , że ma mniej niż a przypuszcza się, że wynosi .O(nω)O(nω)ωω2.3732.37322

Algorytm jest następujący:

  • Konwertuj bitwektory i pozycje bitów na dwuczęściowy wykres z węzłów i co najwyżej krawędzi . To zajmuje czas .n+kn+knknkO(nk)O(nk)
  • Oblicz macierz przyległości wykresu. To zajmuje czas i przestrzeń.O((n+k)2)O((n+k)2)
  • Wyprostuj macierz przylegania. Zajmuje to czas .O((n+k)ω)O((n+k)ω)
  • Przeszukaj sekcję bitvector macierzy przyległości pod kątem zerowych wpisów. Zajmuje to czas .O(n2)O(n2)

Najdroższym krokiem jest podniesienie kwadratu macierzy sąsiedztwa. Jeśli to ogólny algorytm zajmuje czas , co jest lepsze niż naiwny czas .n=kn=kO((n+k)ω)=O(nω)O((n+k)ω)=O(nω)O(n3)O(n3)

To rozwiązanie jest również szybsze, gdy rośnie niezbyt dużo wolniej i nie zbyt szybko niż . O ile i , to jest lepsze niż . Dla co przekłada się na (asymptotycznie). Jeśli ogranicza się do 2, wówczas granice rozszerzają się w kierunku .kknnkΩ(nω2)kΩ(nω2)kO(n2ω1)kO(n2ω1)(n+k)ω(n+k)ωn2kn2kw2.373w2.373n0.731kn1.373n0.731kn1.373wwnϵkn2ϵnϵkn2ϵ

Craig Gidney
źródło
1. Jest to również lepsze niż naiwne rozwiązanie, jeśli ale . 2. Jeśli , heurystyka może być: wybierz losowy podzbiór pozycji bitów, ogranicz się do tych pozycji bitów i użyj mnożenia macierzy, aby wyliczyć wszystkie pary, które nie pokrywają się w tych pozycjach bitów; dla każdej takiej pary sprawdź, czy to rozwiązuje pierwotny problem. Jeśli nie ma wielu par, które nie pokrywają się w tych pozycjach bitów, zapewnia to przyspieszenie w stosunku do naiwnego algorytmu. Nie znam jednak dobrej górnej granicy liczby takich par. k = Ω ( n ) k = o ( n 1,457 ) k n n n nk=Ω(n)k=o(n1.457)knnnn
DW
4

Jest to równoważne ze znalezieniem wektora bitowego, który jest podzbiorem dopełniacza innego wektora; tzn. jego 1 występuje tylko wtedy, gdy 0 występuje w drugim.

Jeśli k (lub liczba 1) jest mała, możesz uzyskać czas , po prostu generując wszystkie podzbiory dopełniacza każdego bitvectora i umieszczając je w trie (używając cofania). Jeśli w trie zostanie znaleziony bitvector (możemy sprawdzić każdy przed wstawieniem podzbioru dopełniacza), mamy parę, która się nie nakłada.O ( n 2 k )O(n2k)

Jeśli liczba 1 lub 0 jest ograniczona do jeszcze niższej liczby niż k, wykładnik można zastąpić tym. Indeksowanie podzbiorów może dotyczyć każdego wektora lub jego dopełniacza, o ile w sondowaniu stosuje się coś przeciwnego.

Istnieje również schemat wyszukiwania supersetów w trie, który przechowuje każdy wektor tylko raz, ale przeskakuje bity podczas sond, dla których, moim zdaniem, jest podobna złożoność złożona; tzn. ma wstawienie ale wyszukiwania .o ( k ) o ( 2 k )o(k)o(2k)

KWillets
źródło
dzięki. Złożoność twojego rozwiązania wynosi , gdzie jest prawdopodobieństwem 1 w bitvektorze. Kilka szczegółów implementacji: choć jest to niewielka poprawa, nie ma potrzeby obliczania i przechowywania dodatków w trie. Wystarczy śledzić komplementarne gałęzie, sprawdzając, czy dopasowanie nie pokrywa się. A biorąc zero bezpośrednio za symbole wieloznaczne, nie jest również potrzebna specjalna karta wieloznaczna. n 2 ( 1 - p ) k pn2(1p)kp
Mauro Lacy,
2

Reprezentują wektory wiertła, z n x k macierzy M . Take I i J pomiędzy 1 i n .n×kMijn

( M M T ) i j = l M i l M j l .

(MMT)ij=lMilMjl.

( M M T ) i j , iloczyn iloczynu i- tego i j- tego wektora, jest niezerowy, jeśli i tylko wtedy, gdy wektory i i j mają wspólną 1. Więc, aby znaleźć rozwiązanie, oblicz M M T i zwraca pozycję zerowego wpisu, jeśli taki wpis istnieje.(MMT)ijijijMMT

Złożoność

Korzystanie z naiwnego mnożenia wymaga operacji arytmetycznych O ( n 2 k ) . Jeśli n = k , wymaga operacji O ( n 2.37 ) przy użyciu całkowicie niepraktycznego algorytmu Coppersmith-Winograd lub O ( n 2.8 ) przy użyciu algorytmu Strassena. Jeśli k = O ( n 0,302 ) , problem można rozwiązać za pomocą operacji n 2 + o ( 1 ) .O(n2k)n=kO(n2.37)O(n2.8)k=O(n0.302)n2+o(1)

Ben
źródło
Czym różni się to od odpowiedzi Strilanc ?
DW
1
@DW Użycie matrycy n - by- k zamiast macierzy ( n + k ) -by- ( n + k ) jest ulepszeniem. Wspomina także o sposobie odcięcia współczynnika k, gdy k << n, więc może to być przydatne.
Craig Gidney