Como construo um código de afixo ideal?

Um código de afixo é um código que é simultaneamente um código de prefixo e sufixo. Ou seja, nenhuma palavra de código não é nem o prefixo nem o sufixo de qualquer outra palavra de código. Os códigos de afixação podem ser decodificados instantaneamente nas duas direções (para frente e para trás).

Quero criar um que comprima de maneira ideal uma determinada distribuição de símbolos de entrada, considerando um conjunto de símbolos de saída.

O algoritmo de Huffman (que cria códigos de prefixo) se aproxima mais, mas devido à sua estratégia gananciosa, parece inadequado para modificações com esse objetivo.

Como encontrar códigos de afixação ideais?

coding-theory prefix-free-code Anko
fonte

Respostas:

Realmente não acho que exista um algoritmo conhecido como ideal. De fato, há uma grande conjectura sobre a eficácia de um conjunto de palavras de código, consulte: http://arxiv.org/abs/0709.2598 (o nome que eu conhecia para código de afixação é código sem correção). Se um algoritmo se mostrou ótimo, provavelmente também resolveria (ou refutaria) essa conjectura.

domotorp
fonte

Essas respostas parecem sugerir que o algoritmo de Huffman produz códigos ótimos sob condições razoáveis.

Anko #

Não vejo como essas respostas estão relacionadas ao seu problema. Se você apenas usar um algoritmo, poderá usar o huffman e depois estender algumas palavrões.

domotorp

Estou apenas afirmando que alguns códigos podem ser ótimos. Estender as palavras de código de um código Huffman provavelmente o tornaria não ideal, uma vez que toda extensão faz com que se aproxime de uma codificação de bloco. Este pode ser um ponto de partida!

Anko

Mas huffman não possui prefixos, para os quais conhecemos a desigualdade Kraft ( en.wikipedia.org/wiki/Kraft%27s_inequality ). Se temos provas de otimalidade, segue-se a desigualdade do tipo kraft. Mas para códigos sem correção, o resp. desigualdade é conjectura, então não pode haver prova.

Domotorp

Na página 8, na parte inferior, vários códigos livres de correção para o inglês são descritos e é mencionado que nenhum dos algoritmos usados para construí-los provou ser o ideal. Portanto, presumivelmente, nenhum algoritmo eficiente é conhecido.

Yuval Filmus

FWIW, parece-me provável que exista um PTAS para o problema, seguindo a idéia básica deste artigo . (Isso não responde exatamente à sua pergunta, mas ainda descreverei o PTAS aqui na seção de respostas, pois é muito longo para caber em um comentário.)

$\epsilon>0$ $p$ $[n]$

$K$ $K$

$K=\lceil 1/\epsilon^2\rceil$ $K$ $p$ $n$ $S$ $K$ $K$ $C(S)$ $|S|$ $p$ $S$ $n-|S|$ $K$ $S$ $n-|S|$ $n-|S|$ $S$ $C(S)$ $C_0$ $S$ $C_0$ $K$ $p$ .

$C_0$ $p$ $K$

$C_0$ $(1+O(\epsilon))$

$C_0$ $K' = \lceil 1/\epsilon \rceil$ $(1+\epsilon)$ $K$ $K$ $C_0$ $K$ $K'$ $K'$ $1+O(\epsilon)$ $C_1$

$C_1$ $(1+O(\epsilon))$ $C_0$ $C_0$ $C_1$ $(1+O(\epsilon))$

Neal Young
fonte