<p>The problem I'm wondering about was tackled long ago (1977) by Douglas Comer and Ravi Sethi, in a paper entitled <a href="http://dl.acm.org/citation.cfm?id=322023" rel="nofollow">"The Complexity of Trie Index Construction"</a>. They show that the decision version of the above problem, as well as three other variants, are NP-complete.</p>

CC BY-SA 3.0
2012-01-02T10:20:24.413Z
2012-01-02T10:20:24.413Z
Anthony Labarre
<p>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.</p>

<p>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?</p>

CC BY-SA 3.0
2011-10-07T08:14:29.160Z
2011-10-07T08:14:29.160Z
zotachidil
<p>I'm currently thinking about the following problem.</p>

<h2>Problem</h2>

<p><strong>Input:</strong> a set $W$ of strings over an alphabet $\Sigma$.</p>

<p><strong>Goal:</strong> permute the characters in each string so that the <a href="http://en.wikipedia.org/wiki/Trie">trie</a> that will contain the rearranged strings has as few edges as possible.</p>

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

<h2>Example</h2>

<p>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:</p>

<pre><code>0-A-B-R-A-C-A-D-R-A-B-A (S')
                 \
                  U     (T')
</code></pre>

<p>(where 0 denotes the root, and $S&#39;$ (resp. $T'$) is the rearranged $S$ (resp. $T$)).</p>

<h2>Question(s)</h2>

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

CC BY-SA 3.0
2011-10-05T14:12:14.467Z
What kinds of rearrangements do you permit? Arbitrary permutations?
Dave Clarke
CC BY-SA 3.0
2011-10-05T14:17:35.883Z
@DaveClarke: Yes, sorry if that was unclear.
Anthony Labarre
CC BY-SA 3.0
2011-10-05T15:31:17.667Z
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?
Tsuyoshi Ito
CC BY-SA 3.0
2011-10-05T17:45:35.697Z
Do you have an application in mind?
Raphael
CC BY-SA 3.0
2011-10-05T21:11:28.793Z
@TsuyoshiIto: done! Raphael: assume you have to mine frequent patterns in a graph (i.e. extract subgraphs that occur at least $t$ times). Each extracted match is a set of edges, and the order of edges within a match does not matter. Matches must be stored and reported, and both the graph to mine and the set of extracted patterns can be quite large; this is one possible way of saving space.
Anthony Labarre
CC BY-SA 3.0
2011-10-05T21:56:28.817Z
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...
Jukka Suomela
CC BY-SA 3.0
2011-10-06T23:39:03.917Z
Is alphabet Σ fixed or specified as part of the input?  (Your comment suggests that it is part of the input.)
Tsuyoshi Ito
CC BY-SA 3.0
2011-10-07T08:03:50.423Z
It is indeed part of the input.
Anthony Labarre
CC BY-SA 3.0
2011-10-07T12:08:27.723Z
Questions about the question usually imply that the question is not written clearly.  Please try to improve your question rather than just answering in comments.
Tsuyoshi Ito
<ds.algorithms><ds.data-structures>
Rearranging strings to minimise storage in a trie
Anthony Labarre
# Rearranging strings to minimise storage in a trie

(Asked by: username_0 on 2011-10-05)

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

**Tags:** ds.algorithms, ds.data-structures
> **Comments:**
> **username_1**: What kinds of rearrangements do you permit? Arbitrary permutations?  
> **username_0**: @DaveClarke: Yes, sorry if that was unclear.  
> **username_2**: 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?  
> **username_3**: Do you have an application in mind?  
> **username_0**: @TsuyoshiIto: done! Raphael: assume you have to mine frequent patterns in a graph (i.e. extract subgraphs that occur at least $t$ times). Each extracted match is a set of edges, and the order of edges within a match does not matter. Matches must be stored and reported, and both the graph to mine and the set of extracted patterns can be quite large; this is one possible way of saving space.  
> **username_4**: 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...  
> **username_2**: Is alphabet Σ fixed or specified as part of the input?  (Your comment suggests that it is part of the input.)  
> **username_0**: It is indeed part of the input.  
> **username_2**: Questions about the question usually imply that the question is not written clearly.  Please try to improve your question rather than just answering in comments.  

---

## 2 answers

### Answer by username_0 on 2012-01-02. Score: 4 | Accepted answer

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"](http://dl.acm.org/citation.cfm?id=322023). They show that the decision version of the above problem, as well as three other variants, are NP-complete.


---

### Answer by username_5 on 2011-10-07. Score: 1

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?


---

