encontrar definições de token ótimas para compactação

5

Eu tenho uma coleção de strings que tem muitas substrings comuns, e estou tentando encontrar uma boa maneira de definir tokens para compactá-los.

Por exemplo, se minhas strings forem:

s1 = "String"
s2 = "Bool"
s3 = "String -> Bool"
s4 = "String -> String"
s5 = "(String -> String) -> String -> [Bool]"

posso querer usar os tokens:

$1 = "String"
$2 = "Bool"
$3 = "$1 -> $1"

para que as sequências possam ser definidas como:

s1 = "$1"
s2 = "$2"
s3 = "$1 -> $2"
s4 = "$3"
s5 = "($3) -> $1 -> [$2]"

(Na verdade, agora está claro que a definição $4 = " -> " pode ser boa para adicionar).

Estou procurando uma boa (talvez a melhor?) maneira de escolher o definições de token. Estou interessado em minimizar o comprimento total das definições de token + as definições de string resultantes.

Alguma idéia?

Atualizar

É meio relacionado a essa pergunta SO: codificação Huffman com símbolos de tamanho variável

    
por ErikR 26.05.2016 / 16:39
fonte

2 respostas

2

O termo genérico para o que você está tentando fazer é compactação baseada em gramática . Em particular, você parece estar tentando resolver o menor problema gramatical .

Ver, por exemplo, Charikar, Lehman, Lehman, Liu, Panigrahy, Prabhakaran, Sahai, Shelat (2005). O menor problema de gramática . Transações do IEEE na Teoria da Informação 51 (7): 2554–2576

    
por 02.08.2016 / 10:16
fonte
0

Lempel-Ziv estilo compactação faz o tipo de coisa que você procurando por.

Para o seu aplicativo, parece que você deseja um "dicionário de cadeias" fixo (representação interna do LZ das suas definições de token), em vez do dinâmico usado pelos programas de compactação padrão como gzip ou compress . O esquema geral de Lempel-Ziv é prontamente adaptável a esse tipo de coisa.

Se nada mais, esteja ciente de que as técnicas no estilo Lempel-Ziv podem naturalmente ajudar a compactar os próprios dados de definição de tokens.

    
por 03.06.2016 / 01:13
fonte