ajuste es un problema de optimización. Dependiendo de lo que necesita ser optimizado para, se utilizan diferentes algoritmos.
número mínimo de lineseditar
una forma sencilla de hacer el ajuste de palabras es usar un algoritmo codicioso que pone tantas palabras en una línea como sea posible, luego pasar a la siguiente línea para hacer lo mismo hasta que no queden más palabras para colocar. Este método es utilizado por muchos procesadores de texto modernos, tales como OpenOffice.org escritor y Microsoft Word., Este algoritmo siempre utiliza el número mínimo posible de líneas, pero puede dar lugar a líneas de longitud muy variable. El siguiente pseudocódigo implementa este algoritmo:
Donde LineWidth es el ancho de una línea, SpaceLeft es el resto del ancho de espacio en la línea de relleno, SpaceWidth es el ancho de un carácter de espacio único, Text es el texto de entrada para recorrer y Word es una palabra en este texto.,
raggednesseditar
un algoritmo diferente, utilizado en TeX, minimiza la suma de los cuadrados de las longitudes de los espacios al final de las líneas para producir un resultado más estéticamente agradable. El siguiente ejemplo compara este método con el algoritmo greedy, que no siempre minimiza el espacio cuadrado.,
para el texto de entrada
AAA BB CC DDDDD
con el ancho de línea 6, el algoritmo codicioso produciría:
------ Line width: 6AAA BB Remaining space: 0CC Remaining space: 4DDDDD Remaining space: 1
------ Line width: 6AAA Remaining space: 3BB CC Remaining space: 1DDDDD Remaining space: 1
la diferencia aquí es que la primera línea está rota antes de BB en lugar de después de él, produciendo un mejor margen derecho y un menor costo 11.,
mediante el uso de un algoritmo de programación dinámica para elegir las posiciones en las que romper la línea, en lugar de elegir rupturas con avidez, la solución con un mínimo de irregularidad se puede encontrar en el tiempo O ( n 2 ) {\displaystyle O(n^{2})} , donde n {\displaystyle n} es el número de palabras en el texto de entrada. Típicamente, la función de costo para esta técnica debe modificarse para que no cuente el espacio dejado en la línea final de un párrafo; esta modificación permite que un párrafo termine en el 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 para dividir palabras largas. Los Algoritmos de tiempo lineal más rápidos pero más complicados basados en el algoritmo SMAWK también son conocidos por el problema de irregularidad mínima, y por algunas otras funciones de costo que tienen propiedades similares.
HistoryEdit
una característica primitiva de ruptura de línea fue utilizada en 1955 en una «unidad de control de impresora de páginas» desarrollada por Western Union., Este sistema usaba Relés en lugar de computadoras digitales programables, y por lo tanto necesitaba un algoritmo simple que pudiera implementarse sin búferes de datos. En el sistema de Western Union, cada línea se rompía en el primer carácter de espacio que aparecía después del carácter 58, o en el carácter 70 si no se encontraba ningún carácter de espacio.
el algoritmo codicioso para el salto de línea es anterior al método de programación dinámica descrito por Donald Knuth en un memo inédito de 1977 que describe su sistema de composición tipográfica TeX y más tarde publicado con más detalle por Knuth & Plass (1981).