El algoritmo Knuth-Plass es un algoritmo de salto de línea (Ajuste de línea y ajuste de palabra) diseñado para su uso en el programa de composición tipográfica TeX de Donald Knuth. Integra los problemas de justificación y separación de palabras del texto en un único algoritmo mediante el uso de un método de programación dinámica discreta para minimizar una función de pérdida que intenta describir las cualidades estéticas deseadas en el resultado final.
El algoritmo funciona dividiendo el texto en una secuencia de tres tipos de objetos: "cuadros", que son fragmentos de contenido que no se pueden cambiar de tamaño, "pegamento", que son elementos flexibles y de tamaño variable, y "penalizaciones". , que representan lugares donde la rotura no es deseable (o, si es negativa, deseable).
El algoritmo original de Knuth y Plass no incluye saltos de página, pero puede modificarse para interactuar con un algoritmo de salto de páginas.
== El algoritmo ==
Para el texto de entrada
AAA BB CC DDDDD
con un ancho de línea 6, el algoritmo codicioso produciría:
------ Ancho de línea: 6
AAA BB Espacio restante: 0
CC Espacio restante: 4
DDDDD Espacio restante: 1
La suma del espacio al cuadrado que queda con este método es 0^2 + 4^2 + 1^2 = 17. Sin embargo, la solución óptima logra la suma menor 3^2 + 1^2 + 1^2 = 11:
------ Ancho de línea: 6
AAA Espacio restante: 3
BB CC Espacio restante: 1
DDDDD Espacio restante: 1
La diferencia aquí es que la primera línea está dividida antes de BB en lugar de después, lo que produce un mejor margen derecho y un costo menor 11.
Al utilizar un algoritmo de programación dinámica para elegir las posiciones en las que romper la línea, en lugar de elegir los saltos con avidez, la solución con una irregularidad mínima se puede encontrar en el tiempo O(n^2), donde n es el número de palabras en el texto de entrada. Normalmente, la función de costo de 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 en medio de una línea sin penalización. También es posible aplicar la misma técnica de programación dinámica para minimizar funciones de costos más complejas que combinan otros factores como el número de líneas o los costos de separación de palabras largas. .
[h4] El algoritmo Knuth-Plass es un algoritmo de salto de línea (Ajuste de línea y ajuste de palabra) diseñado para su uso en el programa de composición tipográfica TeX de Donald Knuth. Integra los problemas de justificación y separación de palabras del texto en un único algoritmo mediante el uso de un método de programación dinámica discreta para minimizar una función de pérdida que intenta describir las cualidades estéticas deseadas en el resultado final. El algoritmo funciona dividiendo el texto en una secuencia de tres tipos de objetos: "cuadros", que son fragmentos de contenido que no se pueden [url=viewtopic.php?t=3994]cambiar[/url] de tamaño, "pegamento", que son elementos flexibles y de tamaño variable, y "penalizaciones". , que representan lugares donde la rotura no es deseable (o, si es negativa, deseable).
El algoritmo original de Knuth y Plass no incluye saltos de página, pero puede modificarse para interactuar con un algoritmo de salto de páginas.
== El algoritmo ==
Para el texto de entrada
AAA BB CC DDDDD
con un ancho de línea 6, el algoritmo codicioso produciría:
------ Ancho de línea: 6 AAA BB Espacio restante: 0 CC Espacio restante: 4 DDDDD Espacio restante: 1
La suma del espacio al cuadrado que queda con este método es 0^2 + 4^2 + 1^2 = 17. Sin embargo, la solución óptima logra la suma menor 3^2 + 1^2 + 1^2 = 11:
------ Ancho de línea: 6 AAA Espacio restante: 3 BB CC Espacio restante: 1 DDDDD Espacio restante: 1
La diferencia aquí es que la primera línea está dividida antes de BB en lugar de después, lo que produce un mejor margen derecho y un costo menor 11.
Al utilizar un algoritmo de programación dinámica para elegir las posiciones en las que romper la línea, en lugar de elegir los saltos con avidez, la solución con una irregularidad mínima se puede encontrar en el tiempo O(n^2), donde n es el número de palabras en el texto de entrada. Normalmente, la función de costo de 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 en medio de una línea sin penalización. También es posible aplicar la misma técnica de programación dinámica para minimizar funciones de costos más complejas que combinan otros factores como el número de líneas o los costos de separación de palabras largas. .
* [http://www.eprg.org/G53DOC/pdfs/knuth-plass-breaking.pdf Romper párrafos en líneas], el artículo original de Knuth y Plass
[/h4]
More details: [url]https://en.wikipedia.org/wiki/Knuth-Plass_line-breaking_algorithm[/url]
Grenhopp era un movimiento gimnástico (gimnasia) en las obras de Pehr Henrik Ling.
El saltador salta en la dirección larga de un caballo con arcos, con un toque para...
(7218) Skácel es un asteroide del cinturón principal (cinturón de asteroides interior), descubierto el 19 de septiembre de 1979 por el astrónomo checo Jaroslav Květoň en el Observatorio Kleť (lista...
El '''salto con pértiga masculino''' del '''Campeonato Mundial Juvenil de Atletismo''' se llevó a cabo en el Estadio Olímpico Pascual Guerrero en Cali, Colombia, los días 17 y 19 de julio de 2015....
'''''Line of Battle''''', subtitulado Tactical Capital Ship Combat, 1914-1924 , es un juego de guerra de tablero publicado por Simulators Canada en 1986 que simula el combate naval justo antes,...
Mobile version