1
$\begingroup$

You have to arrays of single digit numbers. (0 - 9).

A = [....1 billion elements....];
B = [3,5,8,1,2,5,8,3,4,9,1,0,2];

I want to find combo of as few as possible subsets that of array B in A.

So whole Array B could be in Array A by coincidence since it's very large and that would be the largest match as whole sequence is there. Or you could have subset of array B, [8,3,4,9], at index ex: i = 3800443...

Now my goal is to convert Array B to references based on Array A.

So If I give you object like this:

{
  block1: {i: 48938, len: 388},
  block2: {i: 2828, len: 3},
  ...
}

you'd be able to reconstruct array B if you had array A.

One mistake would be to go and find biggest subset only. Then the solution would have biggest subset, but not minimum amount of subsets possible.

Example:

a = [1,3,4,4,3,0,8,3,5,5,2,8,3,1,0,9];
    |^||^||^||^||^||      ^     ||^|

Although this has longest subset, but It ended up with 6 blocks. Whereas,

b = [1,3,4,4,3,0,8,3,5,5,2,8,3,1,0,9];
    |    ^    ||     ^    ||    ^   |

here each subset might not be the longest but there are fewer subsets to cover whole array.

$\endgroup$
  • 1
    $\begingroup$ You might want to look into creating a suffix tree of B, then use the tree as basically an automata when scanning through A. Keep track of the longest sequences for each suffix of B in A. This will be $O(|B|)$ sequences total, then determine how they can minimally cover all of B. Also consider the case when no character of B are in A. $\endgroup$ – ryan Nov 5 '17 at 22:59
  • $\begingroup$ there will be all characters in A, characters are only 0 to 9, and since A is long it's likely all of them are there. assume, i put first 10 characeters in A as, [0,1,2,3,4,5,6,7,8,9, .... ] $\endgroup$ – Muhammad Umer Nov 5 '17 at 23:05
4
$\begingroup$

Assuming all characters of $B$ are wholly contained in $A$, then this method should give you an optimal results.

Algorithm

  1. Compute the longest substring $P_i$ in $A$ that is a prefix of the suffix of $B$ from $B_{i \ldots n}$. This is essentially equivalent to finding the longest common substrings between $A$ and $B$ starting at index $i$ of $B$. There are many methods of doing this, some listed below:
    1. Compute a suffix tree $T$ for the array $B$. Making sure to leave in the suffix links (these are important for back tracking and essentially make the tree like an Aho-Corasick state machine). Traverse $A$ using $T$ as a state machine. Keep track of deepest non-root node reached in $T$ for each path from root to leaf. This will take $\Theta(|B|) + \Theta(|B| + |A|) = \Theta(|B| + |A|)$.
    2. Solve this by inserting both strings $A$ and $B$ into a generalized suffix tree. Keep track of deepest common ancestor between a suffix leaf of $B$ with any other suffix leaf in $A$. This will take $\Theta(|B| + |A|)$.
    3. Least optimal, use dynamic programming, but reverse the formula so you compute longest prefix for a suffix, rather than longest suffix for a given prefix. This will take $\Theta(|B|\cdot |A|)$. (Would not recommend)
  2. Sort $P$ by the index of the starting character of the prefix (i.e. in the original suffix order).
  3. Let $i = 0$
  4. While $i < |B|$:
    1. Let $j$ be the last index of substring $P_i$.
    2. Add substring $P_i$ to a set $S$.
    3. Let $i = j+1$
  5. Return $S$ as it is the set of sequences in $A$ that minimally but completely cover $B$.

Running Time

Let $n = |B|$ and $m = |A|$:

  1. Will take $O(n + m)$ because branching factor is constant (only 10 values) and if you keep it compressed and refer to indices instead of values.
  2. Will take $O(n \log n)$ or $O(1)$ depending on how you structure $T$.
  3. Will take $O(n)$.

Total time will be $O(m + n)$ which will be $O(m)$ for $m \gg n$.

Example

Let $$B = [0, 1, 3, 1, 2, 0]$$ $$A = [2, 1, 3, 0, 5, 1, 2, 4, 0, 1, 3, 0, 3, 1]$$

Step 1 would compute the following tree:

suffixtree

Step 2 should generate the following longest prefixes $P$ for suffix $S$:

$$\begin{array}{|c||r|r|} \hline B \text{ indices} & S & P \\ \hline [0\ldots 5] & 0,1,3,1,2,0 & 0,1,3 \\ \hline [1\ldots 5] & 1,3,1,2,0 & 1,3 \\ \hline [2\ldots 5] & 3,1,2,0 & 3,1 \\ \hline [3\ldots 5] & 1,2,0 & 1,2 \\ \hline [4\ldots 5] & 2,0 & 2 \\ \hline [5\ldots 5] & 0 & 0 \\ \hline \end{array}$$

We then follow steps 5, 6, and 7 to get that our set to be returned is contained of: $$P_0 = [0, 1, 3], P_3 = [1, 2], \text{ and } P_5 = [0]$$

It's also easy to think of this as the maximum number of disjoint subsequences of $B$ contained in $A$. The maximum here is 3 because there are at most 3 subsequences that have no overlapping pieces:

timeslots

Maybe this visualization will help. Then we should keep track of indices along the way in $A$ (this is relatively trivial with proper manipulation), but we see $B$ can be represented by:

$$A[6 \ldots 8] \; A[4 \ldots 5] \; A[3 \ldots 3]$$ $$0,1,3 : 1,2 : 0$$

$\endgroup$
  • $\begingroup$ wow amazing, not sure i got it yet but i think it's right. at least i know it's possible..maybe if i need to read this couple of times more $\endgroup$ – Muhammad Umer Nov 6 '17 at 8:50
  • 1
    $\begingroup$ @Muhammad Umer, yeah reading through it a few times will help. Also, because traversal time will be the most expensive, I would look into the Aho-Corasick DFA that I mentioned above. It's not too difficult to implement, but a bit tricky to wrap your head around. It's basically going to be the same as the suffix tree, except now you have failure functions as well (similar to KMP) so you don't have to backtrack. $\endgroup$ – ryan Nov 6 '17 at 18:14

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.