Нахождение пары непересекающихся битовых векторов

17

Я даю вам список из n битвекторов шириной k . Ваша цель - вернуть два битовых вектора из списка, у которых нет общих единиц, или сообщить, что такой пары не существует.

Например, если я дам вам [00110,01100,11000] то единственным решением будет {00110,11000} . В качестве альтернативы, вход [111,011,110,101] не имеет решения. И любой список, который содержит нулевой битовый вектор 000...0 и другой элемент e имеет тривиальное решение {e,000...0} .

Вот немного более сложный пример без решения (каждая строка является битовым вектором, черные квадраты равны 1 с, а белые квадраты равны 0):

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

Насколько эффективно можно найти два непересекающихся битовых вектора или показать, что они не существуют?

Наивным алгоритмом, где вы просто сравниваете каждую возможную пару, является O(n2k) . Можно ли сделать лучше?

Крейг Гидни
источник
Возможное сокращение: у вас есть граф G с одной вершиной для каждого вектора и ребром между двумя вершинами, если два соответствующих вектора имеют общую 1. Вы хотите знать, если диаметр графика 2 . Но, кажется, трудно идти быстрее, чем O(n2k) .
Франсуа
@ FrançoisGodi Любой связанный компонент графа с тремя узлами и отсутствующим ребром имеет диаметр не менее двух. С представлением списка смежности требуется O(V) время, чтобы проверить это.
Крейг Гидни
@Strilanc Конечно, если решения не существует, график полон (более понятен, чем диаметр = 1, вы правы), но вычисление представления списка смежности может занять много времени.
Франсуа
Является ли k меньше ширины слова вашей машины?
Рафаэль
1
@TomvanderZanden Похоже, это нарушит инварианты, на которые, вероятно, опирается структура данных. В частности, это равенство должно быть переходным. Я уже думал об использовании trie и не вижу, как избежать увеличения коэффициента 2 каждый раз, когда битовая маска запроса имеет 0.
Крейг Гидни

Ответы:

10

Разминка: случайные битовые векторы

В качестве разминки мы можем начать со случая, когда каждый битовый вектор выбирается равномерно случайным образом. Тогда оказывается, что проблема может быть решена за O(n1.6min(k,lgn)) времени (точнее, 1.6 можно заменить на lg3 ).

Мы рассмотрим следующий двунаправленный вариант задачи:

С учетом множества из битвекторов, определить , где существует неперекрывающийся пары сек S , T T .S,T{0,1}ksS,tT

Основной метод решения этой проблемы - разделяй и властвуй. Вот алгоритм времени , использующий принцип «разделяй и властвуй»:O(n1.6k)

  1. Разделите и 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 : tSTS0={sS:s0=0}S1={sS:s0=1}T0={tT:t0=0} .T1={tT:t0=1}

  2. Теперь рекурсивно ищем неперекрывающуюся пару из , из S 0 , T 1 и из T 1 , S 0 . Если какой-либо рекурсивный вызов найдет неперекрывающуюся пару, выведите его, в противном случае выведите «Перекрывающаяся пара не существует».S0,T0S0,T1T1,S0

Поскольку все битовые векторы выбираются случайным образом, мы можем ожидать и | Т б | | T | / 2 . Таким образом, у нас есть три рекурсивных вызова, и мы уменьшили размер задачи в два раза (оба набора уменьшились в размере в два раза). После разбиения lg min ( | S | , | T | ) один из двух наборов уменьшается до размера 1, и проблема может быть решена за линейное время. Мы получаем рекуррентное соотношение в соответствии с|Sb||S|/2|Tb||T|/2lgmin(|S|,|T|) , чье решение T ( n ) = O ( n 1.6 k ) . Учет времени работы более точно в случае с двумя наборами, мы видим, что время работы составляет O ( мин ( | S | , | T | ) 0,6 макс ( | S | , | TT(n)=3T(n/2)+O(nk)T(n)=O(n1.6k) .O(min(|S|,|T|)0.6max(|S|,|T|)k)

Это можно еще улучшить, отметив, что если , то вероятность того, что непересекающаяся пара существует, экспоненциально мала. В частности, если х , у двух случайных векторов, вероятность того, что они не перекрывающиеся является ( 3 / 4 ) K . Если | S | = | T | = n , существует n 2 таких пар, так что по границе объединения вероятность того, что неперекрывающаяся пара существует, не превышает n 2 ( 3k2.5lgn+100x,y(3/4)k|S|=|T|=nn2 . Когда к 2,5 Л.Г. п + 100 , это1 / 2 100 . Таким образом, в качестве шага предварительной обработки, если k 2,5 lg n + 100 , мы можем сразу же вернуть «Не существует непересекающейся пары» (вероятность того, что это неверно, пренебрежимо мала), в противном случае мы запускаем описанный выше алгоритм.n2(3/4)kk2.5lgn+1001/2100k2.5lgn+100

Таким образом, мы достигаем время работы (или O ( мин ( | S | , | T | ) 0,6 макс ( | S | , | T | ) min ( k , lg n) ) ) для предложенного выше варианта с двумя наборами), для частного случая, когда битовые векторы выбираются случайным образом равномерно.O(n1.6min(k,lgn))O(min(|S|,|T|)0.6max(|S|,|T|)min(k,lgn))

Конечно, это не худший анализ. Случайные битовые векторы значительно проще, чем в худшем случае, но давайте рассмотрим это как разминку, чтобы получить некоторые идеи, которые, возможно, мы сможем применить к общему случаю.

Уроки разминки

Мы можем выучить несколько уроков из разминки выше. Во-первых, «разделяй и властвуй» (разделяя на битовую позицию) кажется полезным. Во- вторых, вы хотите разделить на позицию бита с таким количеством «S в таком положении , как это возможно; чем больше 0 , тем меньше уменьшение размера подзадачи.10

В- третьих, это говорит о том, что эта проблема становится все труднее , как плотность «S становится все меньше - если есть очень мало 1 » S среди битвекторов (они в основном 0 «s), проблема выглядит довольно сложно, так как каждый раскол уменьшает размер подзадач немного. Итак, определите плотность Δ, чтобы быть долей битов, которые равны 1 (то есть из всех n k битов), и плотность позиции бита i, чтобы быть долей векторов битов, которые равны 1 в позиции i .110Δ1nki1i

Обработка очень низкой плотности

В качестве следующего шага мы могли бы задаться вопросом, что произойдет, если плотность чрезвычайно мала. Оказывается, что если плотность в каждой позиции бита меньше , мы гарантируем, что существует неперекрывающаяся пара: существует (неконструктивный) аргумент существования, показывающий, что некоторая непересекающаяся пара должна существовать. Это не помогает нам найти его, но, по крайней мере, мы знаем, что оно существует.1/k

Почему это так? Скажем , что пара битвекторов будет покрыта на битовой позиции я , если х я = у я = 1 . Обратите внимание, что каждая пара перекрывающихся битовых векторов должна быть покрыта некоторой битовой позицией. Теперь, если мы фиксируем конкретную битовую позицию i , количество пар, которые могут быть покрыты этой битовой позицией, составляет самое большее ( n Δ ( i ) ) 2 < n 2 / k . Суммирование по всем kx,yixi=yi=1i(nΔ(i))2<n2/kkиз битовых позиций мы находим, что общее количество пар, которые покрыты некоторой битовой позицией, составляет . Это означает, что должна существовать некоторая пара, которая не покрыта какой-либо битовой позицией, что означает, что эта пара не перекрывается. Таким образом, если плотность достаточно низкая в каждой позиции бита, то непересекающаяся пара наверняка существует.<n2

Однако я затрудняюсь определить быстрый алгоритм для нахождения такой неперекрывающейся пары в этих режимах, хотя гарантированно существует такая. Я не сразу вижу какие-либо методы, которые дали бы время выполнения, которое имеет субквадратичную зависимость от . Итак, это хороший особый случай, на котором стоит сосредоточиться, если вы хотите потратить некоторое время на обдумывание этой проблемы.n

На пути к общему алгоритму

В общем случае естественная эвристика выглядит так: выберите битовую позицию с наибольшим числом 1 (т. Е. С наибольшей плотностью) и разделите ее. Другими словами:i1

  1. Найдите положение бита которое максимизирует Δ ( i ) .iΔ(i)

  2. Разделить и 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 :STiS0={sS:si=0}S1={sS:si=1}T0={tT:ti=0} .T1={tT:ti=1}

  3. Теперь рекурсивно ищем неперекрывающуюся пару из , из S 0 , T 1 и из T 1 , S 0 . Если какой-либо рекурсивный вызов найдет неперекрывающуюся пару, выведите его, в противном случае выведите «Перекрывающаяся пара не существует».S0,T0S0,T1T1,S0

Задача состоит в том, чтобы проанализировать его производительность в худшем случае.

Давайте предположим, что в качестве шага предварительной обработки мы сначала вычислим плотность каждой позиции бита. Также, если для каждогоi, предположим, что на этапе предварительной обработки выводится «перекрывающаяся пара» (я понимаю, что это не демонстрирует пример перекрывающейся пары, но давайте отложим это как отдельную задачу). Все это можно сделать заO(nk)раз. Информация о плотности может поддерживаться эффективно, поскольку мы делаем рекурсивные вызовы; это не будет доминирующим фактором времени выполнения.Δ(i)<1/kiO(nk)

Какой будет продолжительность этой процедуры? Я не уверен, но вот несколько замечаний, которые могут помочь. Каждый уровень рекурсии уменьшает размер проблемы примерно на битовых векторов (например, отnбитовых векторов доn-n/n/kn битвекторов). Поэтому рекурсия может идти только оnn/k уровней глубоко. Тем не менее, я не сразу уверен, как посчитать количество листьев в дереве рекурсии (их намного меньше, чем3k уходит), поэтому я не уверен, к какому времени это должно привести.3k

DW
источник
с низкой плотностью: похоже, это некий аргумент. Может быть, если мы воспользуемся вашей общей идеей (разбить столбец на наибольшее число), мы получим более точные оценки, потому что -кател (мы не повторяем) уже избавляется от «большинства»? (S1,T1)
Рафаэль
Общее количество единиц может быть полезным параметром. Вы уже показали нижнюю границу, которую мы можем использовать для обрезки дерева; мы можем показать верхние границы тоже? Например, если их больше, чем , мы имеем как минимум c перекрытий. ckc
Рафаэль
Кстати, как вы предлагаете сделать первый сплит; произвольно? Почему бы просто не разбить весь входной набор по некоторому столбцу ? Нам нужно только выполнить рекурсию в 0- кейсе (среди тех, кто разделяет единицу в i, решения нет ). В ожидании это дает через T ( n ) = T ( n / 2 ) + O ( n k ) границу O ( n k ) (если k фиксировано). Для общей границы вы показали, что мы можем (при условии, что предложенная вами нижняя граница отсечения) избавиться, по крайней мере, отi0iT(n)=T(n/2)+O(nk)O(nk)kn/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
@ Рафаэль, есть две проблемы: (a) векторы могут быть в основном нулями, поэтому вы не можете рассчитывать на 50-50; повторение будет что-то вроде , (b) что более важно, недостаточно просто рекурсировать на 0-подмножестве; вам также нужно изучить пары между вектором из 0-го подмножества и вектором из 1-подмножества, так что есть еще одна или две рекурсии. (Я думаю? Надеюсь, я понял это правильно.)T(n)=T((nn/k)k)+O(nk)
DW
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
источник
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

This is equivalent to finding a bit vector which is a subset of the complement of another vector; ie its 1's occur only where 0's occur in the other.

If k (or the number of 1's) is small, you can get O(n2k) time by simply generating all the subsets of the complement of each bitvector and putting them in a trie (using backtracking). If a bitvector is found in the trie (we can check each before complement-subset insertion) then we have a non-overlapping pair.

If the number of 1's or 0's is bounded to an even lower number than k, then the exponent can be replaced by that. The subset-indexing can be on either each vector or its complement, so long as probing uses the opposite.

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
источник
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
источник
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