Encontre o substring prefixo que dá melhor compactação

Question

Problema:

Dada uma lista de cordas, encontrar o substring que, se subtraído do início de todas as cadeias onde partidas substituído por um byte de escape, dá o menor comprimento total.

Exemplo:

"foo", "fool", "bar"

O resultado é: "foo" como cadeia de base com o "\0" cordas, "\0l", "bar" e um comprimento total de 9 bytes. "\0" é o byte de escape. A soma do comprimento das cordas originais é 10, portanto, neste caso, só salvou um byte.

Um algoritmo ingênuo seria parecido com:

for string in list
  for i = 1, i < length of string
      calculate total length based on prefix of string[0..i]
      if better than last best, save it
return the best prefix

Isso nos dará a resposta, mas é algo como O ((n * m) ^ 2), que é muito caro.

Answer 1

Use uma floresta de árvores de prefixo (trie) ...

  f_2    b_1
 /       |
 o_2     a_1
 |       |
 o_2     r_1
 |
 l_1

então, podemos encontrar o melhor resultado, e garantir que, através da maximização (depth * frequency) que será substituído com o caractere de escape. Você pode otimizar a busca fazendo um ramo e profundidade ligada primeiro procurar o máximo.

Na complexidade: O (C), conforme mencionado no comentário, para construí-lo, e para encontrar o ideal, isso depende. Se encomendar a primeira frequência elementos (O (A) --where A é o tamanho do alfabeto idiomas), então você vai ser capaz de cortar mais ramos, e têm uma boa chance de conseguir tempo sub-linear.

Eu acho que isso é claro, não estou indo para escrevê-la --o que é esta uma tarefa de casa? ;)

Answer 2

Gostaria de tentar começar por classificar a lista. Então você simplesmente ir de corda para corda comparando o primeiro personagem a primeiro caractere do próximo string. Uma vez que você tem um jogo que você iria olhar para o próximo caractere. Você precisará encontrar uma maneira de rastrear o melhor resultado até agora.

Answer 3

Bem, o primeiro passo seria a de ordenar a lista. Em seguida, uma passagem através da lista, comparando cada elemento com a anterior, mantendo o controle da maior dois caracteres, três caracteres, 4-carácter etc funcionamentos. Em seguida, figura é os 20 prefixos de 3 caracteres melhor do que os 15 prefixos de 4 caracteres.