2
$\begingroup$

I bumped into this problem today, and after a bit of pondering, I think I have a solution in $O(n^3)$, which is better than no solution or an $O(n!)$ solution, but my answer still isn't great. Can you beat my best answer?

The Real-World Impetus

Given a set of data $C$ that consists of nonoverlapping, nonempty, unique sequences $S_1, S_2, S_3, ...$ of atomic values. Each sequence tends to have a lot of repeated values.

For example, in the code where I bumped into the problem, the sequences were initially something like this:

    9, 1, 1, 1, 1, 1;
    5, 5, 5, 3, 2;
    1, 1, 1, 1, 4;
    1, 7, 5, 5;
    4, 4, 4;
    ...

To access the data, there's a secondary table of offsets into the overall data to show where each sequence starts: i.e., sequence $S_1$ starts at 1, and $S_2$ at 7, and $S_3$ at 13, and so on. But this means that the sequences may occur in any order, and they may even overlap.

Given that the data could overlap, it occurred to me that by reordering the sequences, I could reduce the storage required. For example, in the above data, I can reduce the size of the required storage by reordering the sequences as $S_1, S_3, S_5; S_4, S_2$:

    9, 1, 1, 1, 1, 1, 4, 4, 4;
    1, 7, 5, 5, 5, 3, 2;
    ...

By overlapping the prefixes and suffixes, we can store 16 values instead of the original 23, a considerable savings.

The Problem Statement

Generalizing this, the problem, then, is to find an algorithm for ordering an arbitrary set of sequences, so that the resulting ordering will have the maximum overall overlap of those sequences' prefixes and suffixes.

(And for what it's worth, I don't actually have to solve this for the code I was working on: This is purely a question of academic interest at this point.)

My Best Answer

It's easy to "see" an optimal answer for trivial examples like the one above, but in the general case of a large number of sequences of arbitrary values, it gets hard quickly. A greedy algorithm could likely at least give an acceptable answer in polynomial time, but that wouldn't be the true minimal answer. And obviously, you can simply try every possible ordering, but $O(n!)$ is not a very nice solution either.

It occurred to me a possible solution might exist as a variation on a longest-path-through-a-weighted-graph problem. You consider each sequence $S_1, S_2, S_3, ...$ as a node in a graph, and construct a directed edge anywhere $S_n$ has a prefix that matches a suffix of $S_m$ for all $n$ and $m$, weighted by the match length. This results in a two-step solution:

  • Calculate all the edge weights. The edge weights can be calculated trivially in $O(n^2)$, or maybe even in $O(n)$ using a trie constructed via dynamic programming.

  • Then for each vertex, use Dijkstra's shortest-path algorithm (or similar), inverted, to find the longest path for that vertex. Of all the possible longest paths, then take the overall longest. This is $O(n^3)$, or maybe $O(n^2\ log\ n)$ using priority queues.

I think this might work, with an overall time of $O(n^3)$ or maybe $O(n^2\ log\ n)$, but I haven't attempted to prove it for real (or implement it). There might also be a better technique than Dijkstra's algorithm for "longest path in the graph when you don't care what node it starts or ends on."

Can you do better?

Here's the problem statement again:

Find an algorithm that can efficiently order a set of sequences $S_1, S_2, S_3, ...$ such that there is maximal global overlap of their prefixes and suffixes.

Good luck; I'm curious to see if you can solve it better than I could!

$\endgroup$
  • 1
    $\begingroup$ "At least $O(n)$" might be confusing. Just say "$O(n)$", which is concise and clear. $\endgroup$ – Apass.Jack Jun 10 at 22:58
  • $\begingroup$ @Apass.Jack Valid point; edited. $\endgroup$ – Sean Werkema Jun 11 at 0:15
1
$\begingroup$

This problem is known as "Shortest Common Superstring" (or sometimes just "Shortest Superstring"). It is an NP-complete problem in general, though good approximations are known (e.g.: via approximations of weighted set cover, as outlined in the linked Wikipedia article).

$\endgroup$
  • $\begingroup$ Interesting: Reading Räihä and Ukkonen's paper (linked from the Wikipedia article), it's clear the general problem is indeed NP-complete. In my case, every $S_n$ was short, so it looked like a simpler solution was possible (as Räihä and Ukkonen noted, although they didn't mention the algorithm I proposed). But I had suspected at first glance that the problem was NP-complete, so I guess I should have stuck with my gut instinct on it. $\endgroup$ – Sean Werkema Jun 11 at 0:25
  • $\begingroup$ I haven't looked through your proposed solution in detail but one pitfall is apparent: you can't simply invert Dijkstra's to obtain a poly time algorithm for longest path. In fact, the longest path problem itself is also NP-complete (see Hamiltonian Path). $\endgroup$ – mhum Jun 11 at 0:34
  • $\begingroup$ What I meant by "invert" was to flip the math upside-down: Assign the weights by the counts of non-matching symbols in $S_n$ and $S_m$; so small weights become the most desirable, and for that, Dijkstra's algorithm should still work. In my original sample data, the lengths of each $S_i$ were the same for all $i$, so the "inverted" weight could be easily calculated with subtraction during the shortest-path search. That said, I can see my algorithm doesn't solve the full SCS problem either, but rather a much simpler variant: A proper SCS solution would be a far better answer. $\endgroup$ – Sean Werkema Jun 11 at 0:58
  • $\begingroup$ If Dijkstra's algorithm could be inverted like that, then we would have a polynomial-time algorithm for the NP-complete Longest Path problem. $\endgroup$ – mhum Jun 11 at 1:04

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.