Algoritmo de salto de línea de Knuth-Plass

El algoritmo Knuth-Plass es un algoritmo de salto de línea diseñado para su uso en el programa de composición tipográfica TeX de Donald Knuth . Integra los problemas de justificación de texto y división de palabras en un único algoritmo mediante un método de programación dinámica discreta para minimizar una función de pérdida que intenta cuantificar las cualidades estéticas deseadas en el resultado final. ^{[ 1 ] [ 2 ] [ 3 ]}

El algoritmo funciona dividiendo el texto en un flujo de tres tipos de objetos: cajas , que son fragmentos de contenido no redimensionables; pegamento , que son elementos flexibles y redimensionables; y penalizaciones , que representan lugares donde la división es indeseable (o, si es negativa, deseable). ^{[ 2 ]} La función de pérdida, conocida como "mala calidad", se define en términos de la deformación de los elementos de pegamento y cualquier penalización adicional incurrida por la división de líneas. ^{[ 1 ]}

La toma de decisiones sobre la división de palabras se deriva naturalmente del algoritmo, pero la elección de los posibles puntos de división dentro de las palabras, y opcionalmente su ponderación de preferencia, debe realizarse primero, e insertarse esa información en el flujo de texto con antelación. El algoritmo original de Knuth y Plass no incluye saltos de página, pero puede modificarse para interactuar con un algoritmo de paginación , como el diseñado por Plass en su tesis doctoral. ^{[ 3 ] [ 4 ]}

Por lo general, la función de costo para esta técnica debe modificarse para que no cuente el espacio que queda en la última línea de un párrafo; esta modificación permite que un párrafo termine a mitad de una línea sin penalización. La misma técnica también puede extenderse para tener en cuenta otros factores, como el número de líneas o los costos de la división de palabras largas con guiones. ^{[ 2 ]}

Una búsqueda exhaustiva e ingenua de fuerza bruta para encontrar la mínima maldad probando cada combinación posible de puntos de ruptura tomaría un tiempo poco práctico. ${\displaystyle O(2^{n})}$tiempo. El enfoque clásico de programación dinámica de Knuth-Plass para resolver el problema de minimización es un caso en el peor de los casos.${\displaystyle O(n^{2})}$algoritmo pero suele ejecutarse mucho más rápido, en un tiempo casi lineal. ^{[ 5 ]}

Se puede demostrar que resolver el óptimo de Knuth-Plass es un caso especial del problema de subsecuencia de peso mínimo convexo , que se puede resolver en${\displaystyle O(n)}$tiempo. ^{[ 6 ]} Los métodos para hacer esto incluyen el algoritmo SMAWK . ^{[ 7 ] [ 8 ]}

Para el texto de entrada

AAA BB CC DDDDD

Con un ancho de línea de 6, un algoritmo voraz que coloca tantas palabras como sea posible en una línea, preservando el orden antes de pasar a la siguiente, produciría:

------ Ancho de línea: 6 AAA BB Espacio restante: 0 Espacio restante CC: 4 Espacio restante: 1

La suma del espacio cuadrado restante por este método es${\displaystyle 0^{2}+4^{2}+1^{2}=17}$Sin embargo, la solución óptima logra la suma más pequeña.${\displaystyle 3^{2}+1^{2}+1^{2}=11}$:

------ Ancho de línea: 6 AAA Espacio restante: 3 BB CC Espacio restante: 1 Espacio restante: 1

La diferencia aquí es que la primera línea se divide antes BBen lugar de después, lo que produce un mejor margen derecho y un menor costo 11.

• Dividir párrafos en líneas , el artículo original de Knuth y Plass.