7
$\begingroup$

I'm currently thinking about the following problem.

Problem

Input: a set $W$ of strings over an alphabet $\Sigma$.

Goal: permute the characters in each string so that the trie that will contain the rearranged strings has as few edges as possible.

(by "permuting" and "rearranging", I mean that any permutation of the characters is valid).

Example

Given strings $S=$"ABRACADABRA" and $T=$"BARRACUDA", storing them without rearrangement would require a trie of size 20, since they share no common prefix; however, if we are allowed to rearrange them, we can obtain the following optimal solution of size 12:

0-A-B-R-A-C-A-D-R-A-B-A (S')
                 \
                  U     (T')

(where 0 denotes the root, and $S'$ (resp. $T'$) is the rearranged $S$ (resp. $T$)).

Question(s)

Has this problem been studied before, and can you give me references? What is its complexity (for $|W|\geq 3$; the problem is easy otherwise)?

$\endgroup$
  • 1
    $\begingroup$ What kinds of rearrangements do you permit? Arbitrary permutations? $\endgroup$ – Dave Clarke Oct 5 '11 at 14:12
  • 1
    $\begingroup$ I had the same question as Dave. Can you edit the question so that people do not have to read the comments to understand what you are asking? $\endgroup$ – Tsuyoshi Ito Oct 5 '11 at 15:31
  • 3
    $\begingroup$ Do you have an application in mind? $\endgroup$ – Raphael Oct 5 '11 at 17:45
  • 1
    $\begingroup$ In the graph example, you are storing sets of edges, while your question seems to suggest that you are storing multisets (i.e., your strings may contain the same character more than once). The case of sets sounds easier to me... $\endgroup$ – Jukka Suomela Oct 5 '11 at 21:56
  • 1
    $\begingroup$ Is alphabet Σ fixed or specified as part of the input? (Your comment suggests that it is part of the input.) $\endgroup$ – Tsuyoshi Ito Oct 6 '11 at 23:39
4
$\begingroup$

The problem I'm wondering about was tackled long ago (1977) by Douglas Comer and Ravi Sethi, in a paper entitled "The Complexity of Trie Index Construction". They show that the decision version of the above problem, as well as three other variants, are NP-complete.

$\endgroup$
1
$\begingroup$

Hmm, minimizing the size of the trie seems hard. However, when you change your objective function to maximizing the saved space you can easily get a 2-approximation.

For every pair of strings, count the number of characters they have in common. Then do a max cost matching weighted by the values computed before, and for each matched pair permute their characters so that their common prefix is as long as possible. The analysis is simple, right?

$\endgroup$

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.