<p>Let $(A, \leq)$ be a totally ordered alphabet.</p>

<p>The <em>packing</em> ${\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 <em>crushing</em> every letter of $u$.</p>

<p>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)$. </p>

<p>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$.</p>

<p>Questions are</p>

<ol>
<li>What is the <strong>best algorithm</strong> to compute the packing of a word?</li>
<li>What is the (time and space) <strong>complexity</strong> of this problem assuming $\leq$ is computable in constant space and time?</li>
</ol>

CC BY-SA 3.0
2013-03-01T01:15:34.970Z
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
CC BY-SA 3.0
2013-03-01T01:22:12.547Z
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](https://www.siam.org/proceedings/alenex/2009/alx09_013_belazzouguid.pdf)
Chao Xu
CC BY-SA 3.0
2013-03-01T02:48:07.610Z
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
CC BY-SA 3.0
2013-03-01T05:26:45.383Z
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ε
CC BY-SA 3.0
2013-03-01T09:26:50.230Z
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
<cc.complexity-theory><co.combinatorics>
Complexity of the packing
Samuele Giraudo
# Complexity of the packing

(Asked by: username_0 on 2013-03-01)

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?

**Tags:** cc.complexity-theory, co.combinatorics
> **Comments:**
> **username_1**: 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)$.  
> **username_1**: 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](https://www.siam.org/proceedings/alenex/2009/alx09_013_belazzouguid.pdf)  
> **username_1**: Assume in the general case you can only do comparisons, $\Omega(n \log n)$ time is required because packing can be used for sorting.  
> **username_2**: 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.)  
> **username_0**: 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.  

---

## 0 answers

