3
$\begingroup$

Consider $N$ sets $S_1,S_2,....,S_{N}$ of binary strings with don't-cares ($X$) with $|S_i| = n$ and the length of all strings is $m$.
In my application, $N=1000$, $n=100$ and $m=500$.

I have to find atleast one binary string with all set bits (either $1$ or $0$) that is compatible with at least one string of each set. Two strings are compatible if they are bit-wise similar. As we know $X$ bits are similar to both $0$ or $1$. For example, consider string $A=10XX0$ and string $B=X011X$. Here string $A$ and $B$ are compatible with each other.

As we can see, due to the size of each string ($m=500$), it's impossible to find a solution with brute force (i.e. create all possible strings of length $m$ and compare each with all strings of all sets). So, I am looking for a reasonable heuristic to find the solution.

Improve this question
$\endgroup$
5
  • 1
    $\begingroup$ Can you estimate number of X? I think (but obviously have to check) that finding them all in linear time meassured in decompressed strings is possible. $\endgroup$ Commented Aug 24, 2016 at 18:02
  • $\begingroup$ Yes 50% to 60% will be don't care bits. $\endgroup$ Commented Aug 24, 2016 at 18:06
  • $\begingroup$ What about divide and conquer? Chop 500 bits into 50 pieces and try to match each piece at a time and then put all matches together. $\endgroup$ Commented Aug 24, 2016 at 19:22
  • $\begingroup$ "So, I am looking for a reasonable heuristic to find the solution" -- 1) That's a non-sequitur. There may be exact algorithms that don't use brute force. If you doubt that, consider sorting or finding shortest paths. 2) What is "reasonable" for you? How many result strings do you need? Do you allow for some returned strings to be wrong? $\endgroup$ Commented Aug 24, 2016 at 20:35
  • $\begingroup$ By reasonable I meant other than brute force in this case. I need to find at least one string with all set bits (either 1 or 0) that is compatible with at least one string of each set. $\endgroup$ Commented Aug 24, 2016 at 21:01

2 Answers 2

Reset to default
3
$\begingroup$

Your problem is NP-hard. It's basically a variant of SAT. You shouldn't expect any algorithm that is provably efficient. Instead, I recommend you use an off-the-shelf SAT solver; since your problem is basically SAT, that's probably about as good as you can do, without a lot of effort tuning for your particular scenario.

NP-hardness: In particular, if every element of every set $S_i$ has exactly $m-1$ don't-cares (has only a single bit set to 0 or 1), then your problem becomes exactly $n$-CNF-SAT with $m$ variables and $N$ clauses. We know that $n$-CNF-SAT is NP-hard; it follows that this special case of your problem is NP-hard, and thus your problem in general is NP-hard.

Using a SAT solver: Introduce variables $x_1,\dots,x_m$ representing the string you're trying to find. Then we obtain a formula of the form

$$\Psi(x_1,\dots,x_m) = \bigwedge_{i=1}^N \bigvee_{j=1}^n \phi_{i,j}(x_1,\dots,x_m),$$

where each $\phi_{i,j}$ is a conjunction of literals. The goal is to find an assignment $x_1,\dots,x_m$ that makes $\Psi(x_1,\dots,x_m)$ true.

You can formulate this as a SAT instance by applying the Tseitin transform. In other words, introduce variables $y_{i,j}$, then add CNF clauses enforcing that $y_{i,j} = \phi_{i,j}(x_1,\dots,x_m)$ as well as CNF clauses $(y_{i,1} \lor \dots \lor y_{i,n})$ for all $i$. The Tseitin transform tells you how to add the former clauses. In particular, you add the clause $(\neg y_{i,j} \lor \neg x_k)$ if the $j$th element of $S_i$ has a 0 in its $k$th bit; add the clause $(\neg y_{i,j} \lor x_l)$ if the $j$th element of $S_i$ has a 1 in its $l$th bit; and add the clause $(y_{ij} \lor x_k \lor \neg x_l \lor \dots)$ if the $j$th element of $S_i$ has a 0 in its $k$ bit and a 1 in its $l$th bit and so on. Or, use a SAT front-end that will let you input arbitrary formulas and will do the Tseitin transform for you -- for instance, STP is a nice tool for that purpose.

Then, let the off-the-shelf SAT solver look for a satisfying assignment for you.

Improve this answer
$\endgroup$
2
$\begingroup$

Let $S = \bigcup_{i=1}^N S_i$ the set of all strings.

Here is a sketch of an algorithm. The idea is to start with a trie of all strings and eliminate one $X$ after the other, copying the membership information from $X$-subtries to its siblings.

  1. Create a (ternary) trie of all strings in $S$; label each leaf for $w \in S$ with all indices $i$ for which $w \in S_i$, for instance with a bit vector $\chi_w$ (each).

  2. For each node $v$ reached via an $X$-edge do:

    1. For each leaf $w$ under $v$ and matching leaves $w'$ under the $0$- and $1$-sibling of $v$, set

      $\qquad \chi_{w'} = \chi_{w} \lor \chi_{w'}$.

      If matching $w'$ do not exist, create them.

    2. Remove $v$.

  3. Any leaf $w$ with $\chi_w = (1, \dots, 1)$ is a solution.

Since step 2.1 may double the number of nodes in the subtree rooted in the parent of $v$ we do not get a polynomial bound on the running time. In fact, we will eventually create the binary trie of all strings that are compatible to any string in $S$ -- who may be legion.

Here are some ideas on how to speed up the algorithm, sometimes.

  • Keep track of which leaves correspond to binary strings. As soon as you get one labelled with the one-vector, terminate.
  • In step 2, prefer nodes on paths with as few $X$ as possible. (You can label leaves with this information during step 1.)
  • In step 2, prefer nodes that cover more $S_i$. (You can label nodes with this information during step 1, just like leaves.)
Improve this answer
$\endgroup$

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.