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.