I am searching for an algorithm to decompose a word with the following constraints:

Decompose the word $w$ such that the following value is minimized: $\sum_{i=1}^{k} | w_i| + \sum_{i=1}^{k} \log(n_i)$ where $w=w_{i_1}w_{i_2}\ldots w_{i_l}$ is decomposed in words $w_{i_j} \in \{w_1,\ldots,w_k\}$ of length $|w_{i_j}|$ and $n_{i_j}$ is the number of occurrences of the word $w_{i_j}$ in the word $w$. Or alternatively decompose $w$ such that the value $\sum_{i=1}^{k} | w_i| + \sum_{i=1}^{k} n_i$ is minimized.

Does somebody know of any algorithm on how to do this?

Applications of this decomposition would be a compression of the word $w$. After decomposing, one would sort the $w_i$ lexicographically and store the corresponding permutation plus one would store the $w_i$ and the $n_i$.

Example of the compression with one decomposition (possibly not optimal in the above sense):

$w = bc|a|bc|a|bc|a$

The permutation is given by $\sigma=(1,3,5,0,2,4)$. The Lehmer-Number (For a definition see "Factorial Number System" in Wikipedia) of the permutation is $l(\sigma)=187$ One would then store: $187;a:3;bc:3$ To decompress, one would compute the permutation from the Lehmer-Number $187$ and apply its inverse to $(a,a,a,bc,bc,bc)$.


Your Answer

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