sexta-feira, 9 de outubro de 2009

Problema 2.17

Qual a Distância de Hamming entre duas cadeias de caracteres, isto é, em quantas posições divergem? Se as cadeias tiveram o mesmo comprimento é fáciul:


def hamming_b(cad1,cad2): # Começar com esta solução...
"""
Determina a distância de Hamming entre duas cadeias.
Para o mesmo tamanho!!!
"""
conta = 0
for i in range(len(cad1)):
if cad1[i] != cad2[i]: # erro corrigido!
conta = conta + 1
return conta

Limitamo-nos a usar o padrão acumulador, percorrendo as cadeias posição a posição e testando a igualdade (linha 8). Mas, e se tiverem comprimento diferente? Bom ,só é preciso um pequeno ajuste.


def hamming_a(cad1,cad2):
"""
Determina a distância de Hamming entre duas cadeias.
"""
conta = 0
comp_min = min(len(cad1),len(cad2))
comp_max = max(len(cad1),len(cad2))
for i in range(comp_min):
if cad1[i] != cad2[i]:
conta = conta + 1
conta = conta + (comp_max - comp_min)
return conta


Testamos as sub-cadeias de igual comprimento, como anteriormente, e depois consideramos que os caracteres em excesso devem todos ser contabilizados para a distância de Hamming.

9 comentários:

  1. Também fiz como o professor na segunda vez:

    def hamming(str1,str2):
    acum = 0
    for i in range(min(len(str1),len(str2))):
    if str1[i] != str2[i]:
    acum = acum + 1
    acum = acum + (max(len(str1),len(str2))-min(len(str1),len(str2)))
    return acum

    PS: Só dizer que na 1ª vez enganou se na condição, tem lá "if cad1[i] == cad2[i]:" e deveria ser "if cad1[i] != cad2[i]:" (penso eu).

    ResponderEliminar
  2. A versão simples tinha um bug sim senhor. Confesso que apenas escrevi o programa e não o testei, pois fiz logo a versão complicada. Aprende-se muito com o erros, incluindo os dos outros :-)!

    ResponderEliminar
  3. No meu último comentário na resolução do problema 2.16 digo que podemos simplificar se conhecermos melhor a linguagem.

    Pois neste fiz o contrário.
    def d217(a,b):
    i=0
    t=0
    if len(a) <= len(b):
    c = len(a)
    d = len(b) - len(a)
    else:
    c = len(b)
    d = len(a) - len(b)
    for i in range(c):
    if a[i] != b[i]:
    t = t + 1
    return t + d

    ResponderEliminar
  4. Eu estou a ver que dou sempre a Volta ao Mundo™:

    def hamming(x,y):
    a=x[:]
    b=y[:]
    Q=len(a)-len(b)
    if Q>0:
    b+=" "*Q
    elif Q<0:
    a+=" "*(-Q)
    distancia=0
    for i in range(len(a)):
    if a[i]!=b[i]:
    distancia+=1
    print distancia

    ResponderEliminar
  5. Rui Gonçalves: não complique! Porque tenta normalizar as duas sequências? O que está em jogo é a contagem. Como pode ver na solução que apresento acima não é preciso fazer essa "normalização". Mesmo aceitando a sua solução, uma vez mais não complique. Faça antes:
    ...
    Q = abs(len(a)-len(b))
    ...
    Assim evita um código muito específico e que funciona porque acrescenta "nada" à cadeia mais pequena!


    Outra coisa: você insiste nas suas soluções em colocar print em vez de return. Habitue-se a usar por defeito o return a menos que no enunciado lhe seja pedido a impressão do resultado!!

    ResponderEliminar
  6. Pessoal estou a tentar encontrar uma implementação simples da codificação e descodificação do hamming(7,4) mais não encontro,como sou iniciante em python fiz uma codificação mais não consigo descodificar. Será que alguém poderia dar-me uma ajudinha?

    ResponderEliminar
  7. Roger, Não entendo o seu comentário. A distância de Hamming não é um processo de codificação / descodificação, mas apenas um modo de calcular a distância entre objectos, neste caso de cadeias de caracteres. Quer tornar a dúvida mais precisa?

    ResponderEliminar
  8. É isso ai,pretendo codificar um sinal com 4 bits de dados e 3 de paridade.Mais o meu problema agora é outro que é o seguinte:
    Tendo um arrayBits=[1,0,1,1,1,1,0,1] como é que eu converto cada bit do array por um inteiro de base dois? tentei fazer sinalInteiros=[]
    for e in range(len(arrayBits)):
    sinalInteiros.append(int(arrayBits[e],2)) mais retorna uma exception dizendo: int() can't convert non-string with explicit base. Existe alguma forma de contornar isto?

    ResponderEliminar
  9. Roger. Não entendo o que pretende. Repare que 0 e 1 têm a mesma representação, logo o seu vector é um inteiro na base dois. A mensagem de erro que obtém é porque o construtor int espera uma cadeia de caracteres quando se indica a base.

    ResponderEliminar