# Complexity of the packing

Let $(A, \leq)$ be a totally ordered alphabet.

The packing ${\tt pack(u)}$ of a word $u \in A^*$ is the word of $\lbrace 1, \dots, k \rbrace^*$, where $k$ is the number of different letters of $u$, obtained by crushing every letter of $u$.

Formally, let $f_u:A\to \lbrace 1, \dots, k \rbrace$ such that $f_u(x)\leq f_u(y) \Leftrightarrow x\leq y$. Then, if $u=u_1 \dots u_n$, ${\tt pack(u)}$ is the sequence $f_u(u_1) \dots f_u(u_n)$.

For instance, let $A$ be the alphabet $\lbrace a_i : i \in \mathbb{N} \rbrace$ where $a_i \leq a_j$ if and only if $i \leq j$ and $u := a_6 a_2 a_2 a_5 a_1 a_9 a_1$. Then, we have ${\tt pack(u)} = 4223151$.

Questions are

1. What is the best algorithm to compute the packing of a word?
2. What is the (time and space) complexity of this problem assuming $\leq$ is computable in constant space and time?
• If your alphabets is $\{1,\ldots,N\}$, then insert all alphabets in the string to a Y-fast trie in $O(n \log \log N)$ time. Compute the rank of all alphabets by running a sequence of predecessor queries. After that, each look up is just another $O(\log \log N)$ time. The space complexity is $O(n)$. – Chao Xu Mar 1 '13 at 1:15
• A more advanced treatment for the integer alphabet case are the recent progresses on monotone minimal perfect hashing. See Theory and Practise of Monotone Minimal Perfect Hashing – Chao Xu Mar 1 '13 at 1:22
• Assume in the general case you can only do comparisons, $\Omega(n \log n)$ time is required because packing can be used for sorting. – Chao Xu Mar 1 '13 at 2:48
• Voting to close. This is not a research-level question; please see the faq for more information. (Like your previous problem, this is obviously equivalent to sorting.) – Jeffε Mar 1 '13 at 5:26
• In my previous problem, it was unclear that it was equivalent to a stable sorting because standardization makes a little less work than a sorting. For this problem, I am aware that it is maybe not a top research question, but it is basically a reference request on this algorithm. – Samuele Giraudo Mar 1 '13 at 9:26