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?
  • 1
    $\begingroup$ 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)$. $\endgroup$ – Chao Xu Mar 1 '13 at 1:15
  • 1
    $\begingroup$ 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 $\endgroup$ – Chao Xu Mar 1 '13 at 1:22
  • 2
    $\begingroup$ Assume in the general case you can only do comparisons, $\Omega(n \log n)$ time is required because packing can be used for sorting. $\endgroup$ – Chao Xu Mar 1 '13 at 2:48
  • 2
    $\begingroup$ 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.) $\endgroup$ – Jeffε Mar 1 '13 at 5:26
  • 1
    $\begingroup$ 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. $\endgroup$ – Samuele Giraudo Mar 1 '13 at 9:26

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.