Código binário com restrição

7

Suponha que eu tenha um alfabeto de n símbolos. Eu posso codificá-los eficientemente comlog2n-bits strings. Por exemplo, se n = 8:
A: 0 0 0
B: 0 0 1
C: 0 1 0
D: 0 1 1
E: 1 0 0
F: 1 0 1
G: 1 1 0
H: 1 1 1

Agora eu tenho a restrição adicional de que cada coluna deve conter no máximo p bits definidos como 1. Por exemplo, para p = 2 (en = 8), uma solução possível é:
A: 0 0 0 0 0
B: 0 0 0 0 1
C: 0 0 1 0 0
D: 0 0 1 1 0
E: 0 1 0 0 0
F: 0 1 0 1 0
G: 1 0 0 0 0
H: 1 0 0 0 1

Dados nep, existe um algoritmo para encontrar uma codificação ideal (menor comprimento)? (e pode-se provar que calcula uma solução ideal?)

EDITAR

Até agora, foram propostas duas abordagens para estimar um limite mais baixo do número de bits m. O objetivo desta seção é fornecer uma análise e uma comparação das duas respostas, a fim de explicar a escolha da melhor resposta .

A abordagem de Yuval é baseada em entropia e fornece um limite inferior muito bom:lognh(p/n) Onde h(x)=xlogx+(1x)log(x).

A abordagem de Alex é baseada em combinatória. Se desenvolvermos um pouco mais o raciocínio dele, também é possível calcular um limite inferior muito bom:

Dado m o número de bits log2(n), existe um único k de tal modo que

1+(m1)+...+(mk)<n1+(m1)+...+(mk)+(mk+1)
Pode-se convencer que uma solução ideal usará a palavra-código com todos os bits baixos, depois as palavras-código com 1 bit de altura, 2 bits de altura, ..., k bits de altura. Para on1(m1)...(mk) símbolos restantes a serem codificados, não está claro em quais palavras de código é ideal usar, mas, com certeza, os pesos wi de cada coluna será maior do que seria se pudéssemos usar apenas palavras de código com k+1 bits altos e têm |wiwj|1 para todos i,j. Portanto, pode-se diminuir o limitep=max(wi) com
pm=0+1+(m12)+...+(m1k1)+(n1(m1)...(mk))(k+1)m

Agora, dado n e p, tente estimar m. Nós sabemos issopmp então se p<pm, então m<m. Isso fornece o limite inferior param. Primeiro calcule opm então encontre o maior m de tal modo que p<pm

É isso que obtemos se traçarmos, por n=1000, os dois limites inferiores juntos, o limite inferior com base na entropia em verde, o baseado no raciocínio combinatório acima em azul, obtemos:insira a descrição da imagem aqui

Ambos parecem muito semelhantes. No entanto, se traçarmos a diferença entre os dois limites inferiores, ficará claro que o limite inferior baseado no raciocínio combinatório é melhor no geral, especialmente para valores pequenos dep.

insira a descrição da imagem aqui

Eu acredito que o problema vem do fato de que a desigualdade H(X)H(Xi) é mais fraco quando p fica menor, porque as coordenadas individuais se correlacionam com pequenas p. No entanto, este ainda é um limite inferior muito bom quandop=Ω(n).

Aqui está o script (python3) que foi usado para calcular os limites inferiores:

from scipy.misc import comb
from math import log, ceil, floor
from matplotlib.pyplot import plot, show, legend, xlabel, ylabel

# compute p_m 
def lowerp(n, m):
  acc = 1
  k = 0
  while acc + comb(m, k+1) < n:
    acc+=comb(m, k+1)
    k+=1

  pm = 0
  for i in range(k):
    pm += comb(m-1, i)

  return pm + ceil((n-acc)*(k+1)/m)

if __name__ == '__main__':
  n = 100

  # compute lower bound based on combinatorics
  pm = [lowerp(n, m) for m in range(ceil(log(n)/log(2)), n)]
  mp  = []
  p = 1
  i = len(pm) - 1
  while i>= 0:
    while i>=0 and pm[i] <= p: i-=1
    mp.append(i+ceil(log(n)/log(2)))
    p+=1
  plot(range(1, p), mp)

  # compute lower bound based on entropy
  lb = [ceil(log(n)/(p/n*log(n/p)+(n-p)/n*log(n/(n-p)))) for p in range(1,p)]
  plot(range(1, p), lb)

  xlabel('p')
  ylabel('m')
  show()

  # plot diff
  plot(range(1, p), [a-b for a, b in zip(mp, lb)])
  xlabel('p')
  ylabel('m')
  show()
user3017842
fonte
11
@ DW a restrição é exatamente como seus estados. cada coluna deve conter no máximo p bits definidos como 1. ie. os bits 1 em cada posição de todas as teclas selecionadas não excedem p. Mas acho que o primeiro passo ainda está contando a capacidade de cada largura de bit.
Terence Hang
user3017842, suspeito que sua edição mais recente deve ser postada como uma resposta automática. Eu acho que fica sozinho como resposta à sua pergunta. Você concorda? Nesse caso, o lugar certo para isso é na caixa de respostas, e não na pergunta - isso fará muito mais sentido para futuros leitores que se depararem com isso (e também permitirá que a comunidade vote na sua resposta). Compreendo que você esteja compartilhando a análise que fez - obrigado. Convido você a postar esse material como resposta e, em seguida, remova-o da pergunta. O que você acha? Parece que isso faz sentido para você?
DW
@DW A seção EDIT apenas faz uma comparação entre as duas respostas propostas, a fim de explicar a escolha da melhor resposta . Portanto, eu não queria colocá-lo como uma resposta automática. Mas concordo plenamente que falta clareza para futuros usuários; portanto, esclarei o objetivo da seção e forneci links para as respostas correspondentes. Eu acredito que está um pouco mais claro agora.
user3017842

Respostas:

3

Existe um limite inferior adicional que podemos construir, que abordará casos como o que o usuário3030830 mencionou em seu comentário à resposta de Yuval. (Casos em quep é particularmente pequeno.) Suponha que soubéssemos m já: Então nós temos pmtotal de bits alto em todas as palavras de código. Como estamos interessados ​​nos casos em quepé pequeno, vemos esses bits altos como nosso recurso limitador e queremos criar um código com ele (e ver quantas palavras de código podemos extrair). Podemos ter 1 palavra de código com todos os 0s, entãom palavras de código com um único 1; (m2) com dois 1s, etc. Se chamarmos o maior número de bits em uma palavra de código k, então

pm=01+1m+2(m2)+...iki(mi)
Enquanto nosso número de palavras de código n é igualmente limitado por
nik(mi)
Se olharmos para o caso em que pm, então k2já está implícito na primeira desigualdade. (pm=m2=m+2(m2)) Então, o código consistiria no0-palavra, m solteiro-1-words e (p1)m/2 dois-1-palavras. portanto
n1+m+(p1)m/2
ou invertendo
m2(n1)p+1.
Isso produzirá o limite inferior apertado de m5 no exemplo que você fornece, mas, como mencionado anteriormente, provavelmente só será muito útil enquanto pm (ou pn)
Alex Meiburg
fonte
11
Por favor, consulte a seção EDIT do post principal para ver por que sua resposta vence!
user3017842
4

Aqui está um limite inferior e uma construção assintoticamente correspondente, pelo menos para alguns intervalos dos parâmetros. Denotar porm o número de colunas e suponha, por simplicidade, que pn/2.

Começamos com um limite inferior em m. DeixeiXseja a codificação do símbolo escolhido uniformemente aleatoriamente. DeixeiX1,,Xm ser as coordenadas individuais e deixar wip ser o peso do icoluna. Então

logn=H(X)i=1mH(Xi)=i=1mh(wi/n)mh(p/n).
Portanto
mlognh(p/n).
Aqui H é a entropia de uma variável aleatória H(X)=xPr[X=x]logPr[X=x] e h é a função entropia h(x)=xlogx(1x)log(1x). (Você pode usar qualquer base para o logaritmo que desejar.)

A construção assintoticamente correspondente, que deve funcionar para p=Ω(n), escolhe m um pouco maior que esse limite inferior e escolhe um esquema de codificação aleatória, cada bit sendo definido como 1 com alguma probabilidade q/n que é um pouco menor que p/n. Escolhendo os parâmetros corretamente, devemos obter que isso resulte em uma codificação legal (todas as palavras de código são diferentes e todos os pesos de coluna são no máximop) com probabilidade positiva.

Yuval Filmus
fonte
Limite inferior agradável. Por que a construção correspondente deve funcionar parap=Ω(n)? existe alguma maneira fácil de acreditar além de limitar a probabilidade de obter uma codificação inválida quandomé escolhido perto do limite inferior?
Ariel #
A experiência me diz que tem uma grande chance de funcionar, mas você não pode ter certeza sem tentar.
Yuval Filmus
Eu acredito que esse limite inferior é muito bom quando as coordenadas individuais X1,X2,...,Xm são virtualmente independentes (porque a desigualdade H(X)H(Xi)estará perto de ser uma igualdade). É provável que este seja o caso quandop está perto o suficiente para n/2. No entanto, quandoppermanece pequeno, esse não é mais o caso. Considere, por exemplo, o caso extremo em quep=1.
User3017842
11
Quando p=1 é claro que o número de bits é n1(como sugerido na resposta de Alex Meiburg). Contudon1lognh(p/n))n/logn. O limite inferior se torna impreciso quandop permanece pequeno enquanto nestá ficando grande. Além disso, para pequenasp tal como p=1, a construção proposta não funcionará muito bem devido ao conhecido problema de aniversário. Mas, ainda assim, essa é uma abordagem muito boa, especialmente quandop=Ω(n)!
user3017842
Fiz uma comparação com outro limite inferior deduzido do raciocínio combinatório sugerido em outra resposta. Acontece que seu limite inferior é um pouco mais fraco, especialmente quandopfica menor. Por favor, veja os detalhes da comparação na seção EDIT do post principal. No entanto, fiquei muito impressionado com a sua solução! Obrigado !
user3017842
0

Aqui está uma metodologia de pesquisa simples. Começamos a partir de um limite inferior do número de bits e tentamos encontrar uma codificação legal. Especificamente.

Seja m o número atual de bits. Codifique o símbolo i como bi1, bi2, ..., bim.

Restrições: bi xor bj não é 0 - em outras palavras, a codificação de cada símbolo é única

Para todos j: sum_i bij <= p.

Este é um problema de satisfação pseudo-booleano (bem, pode ser facilmente codificado como um problema de satifiabilidade padrão). Portanto, continue aumentando m até encontrar uma que seja satisfatória (ou faça uma pesquisa binária usando os limites inferior e superior para encontrar o mínimo m).

Obviamente, isso não garante que, na prática, você seja capaz de encontrar o m mínimo, a verificação do SAT poderá atingir o tempo limite.

MotiN
fonte