Primeira vez aqui? Seja bem vindo e cheque o FAQ!
x

Como justificar texto usando programação dinâmica?

+1 voto
709 visitas
perguntada Jun 10, 2016 em Ciência da Computação por Marcleiton Morais (21 pontos)  

Considere o problema de justificação de textos (com a restrição de não poder dividir as palavras): onde eu coloco as quebras de linha de forma que o texto fique o mais alinhado possível. Discuta esse problema e implemente uma solução usando programação dinâmica. Compare com a estratégia gananciosa de colocar o máximo de palavras possíveis numa mesma linha. Teste exemplos reais.

Compartilhe

1 Resposta

0 votos
respondida Jun 10, 2016 por Marcleiton Morais (21 pontos)  

Uma forma de resolver o problema de justificação de texto é preencher as linhas gradualmente palavra por palavra. Se a concatenação de uma palavra exceder a largura da linha, a palavra é alocada na próxima linha e segue-se com esse procedimento até a completa disposição do texto. Essa estratégia é caracteristicamente uma estratégia gananciosa. Embora muito intuitiva e de execução rápida, sua aplicação gera muito espaços em branco no final das linhas, o que produz uma deformação na justificação do texto.
A literatura propõe uma forma alternativa para gerenciar os espaços no final das linhas. Estabelece-se uma penalização aos espaços em branco do final da linha, em geral o total de espaços em branco elevado a 3 ou 2. A partir dessa penalização, define-se o custo de se quebrar a linha em uma dada posição penalizando muito mais as lacunas maiores que as menores. Para se chegar a uma configuração de quebras de linha, minimiza-se a soma total de tais sanções, uma estratégia conhecida como "minimum raggedness". Uma linha que excede a largura permitida deve sofrer uma penalidade infinitamente grande; caso contrário, o custo deve seguir uma função que cresce rapidamente, tal como o tamanho da lacuna ao quadrado. O alinhamento de texto por programação dinâmica faz uso desses procedimentos.
Para entender como o algoritmo trabalha, suponha que houvesse uma configuração ideal de linhas. Retirando-se a última linha dessa configuração, deveríamos manter o layout ideal, porque caso contrário, seria possível melhorá-lo e, em conjunto com a linha removida, resultaria em uma configuração ainda melhor, contradizendo o fator que partimos de uma configuração ideal. Operacionalmente, para resolver cada subproblema apenas uma vez, é necessário encontrar e mais tarde reutilizar as linhas que terminam com alguma palavra que menos contribui para o custo total. Como cada uma das n palavras poderia terminar no máximo nas n linhas potenciais, o algoritmo tem complexidade O(n^2).
Um comparativo entre a estratégia gananciosa e a programação dinâmica evidencia suas diferenças. Assim, suponha que queiramos alinhar o texto "a b c d e f g h i j k l m n o p qqqqqqqqq", considerando linhas que possuem largura de 9 espaços. Caso utilizássemos a estratégia gananciosa, teríamos o seguinte resultado:

a b c d e
f g h i j
k l m n o
p
qqqqqqqqq

Enquanto que utilizando programação dinâmica, teríamos:

a  b  c d
e  f  g h
i  j  k l
m  n  o p
qqqqqqqqq

Apresentamos a seguir o algoritmo que gera este último resultado.

import re

def tamanhoItens(l):
    return sum([ len(x) for x in l] )

lead_re = re.compile(r'(^\s+)(.*)$')

def alinhaTexto(texto, larguraLinha, ultimaLinhaParagrafo=0):
    m = lead_re.match(texto)     # detect and save leading whitespace
    if m is None:
        esquerda, direita, largura = '', texto, larguraLinha
    else:
        esquerda, direita, largura = m.group(1), m.group(2), larguraLinha - len(m.group(1))
    itens = direita.split()
    for i in range(len(itens) - 1): # add required space to each words, exclude last item
        itens[i] += ' '
    if not ultimaLinhaParagrafo: # number of spaces to add
        ContaEsquerda = largura - tamanhoItens(itens)
        while ContaEsquerda > 0 and len(itens) > 1:
            for i in range(len(itens) - 1):
                itens[i] += ' '
                ContaEsquerda -= 1
                if ContaEsquerda < 1:  
                    break
    resultado = esquerda + ''.join(itens)
    return resultado

def justificar(texto, larguraLinha):
    palavras = texto.split()
    totalPalavras = len(palavras)
    espacoVazio = [[0] * totalPalavras for i in range(totalPalavras)]
    for i in range(totalPalavras):
        espacoVazio[i][i] = larguraLinha - len(palavras[i])
        for j in range(i + 1, totalPalavras):
            espacoVazio[i][j] = espacoVazio[i][j - 1] - len(palavras[j]) - 1
    minima = [0] + [10 ** 20] * totalPalavras
    quebras = [0] * totalPalavras
    for j in range(totalPalavras):
        i = j
        while i >= 0:
            if espacoVazio[i][j] < 0:
                custo = 10 ** 10
            else:
                custo = minima[i] + espacoVazio[i][j] ** 2
            if minima[j + 1] > custo:
                minima[j + 1] = custo
                quebras[j] = i
            i -= 1
    linhas = []
    j = totalPalavras
    while j > 0:
        i = quebras[j - 1]
        linhas.append(' '.join(palavras[i:j]))
        j = i
    linhas.reverse()
    for linha in linhas:
        print alinhaTexto(linha, larguraLinha, ultimaLinhaParagrafo=0)


texto="a b c d e f g h i j k l m n o p qqqqqqqqq"
#texto = "Considere o problema de justificacao de textos (com a restricao de nao poder dividir as palavras): onde eu coloco as quebras de linha de forma que o texto fique o mais alinhado possivel. Discuta esse problema e implemente uma solucao usando programacao dinamica. Compare com a estrategia gananciosa de colocar o maximo de palavras possiveis numa mesma linha. Teste exemplos reais."
larguraLinha = 9
print justificar(texto,larguraLinha)

D. E. Knuth, M. F. Plass. Breaking Paragraphs into Lines. Software--Practice and Experience 11, 1981.

...