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)?

Improve this question
$\endgroup$
9
  • 1
    $\begingroup$ What kinds of rearrangements do you permit? Arbitrary permutations? $\endgroup$
    – Dave Clarke
    Commented Oct 5, 2011 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
    Commented Oct 5, 2011 at 15:31
  • 3
    $\begingroup$ Do you have an application in mind? $\endgroup$
    – Raphael
    Commented Oct 5, 2011 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
    Commented Oct 5, 2011 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
    Commented Oct 6, 2011 at 23:39

2 Answers 2

Reset to default
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.

Improve this answer
$\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?

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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