Il word wrapping è un problema di ottimizzazione. A seconda di cosa deve essere ottimizzato per, vengono utilizzati diversi algoritmi.

Numero minimo di linesEdit

Un modo semplice per eseguire il wrapping delle parole è utilizzare un algoritmo avido che mette quante più parole su una riga possibile, quindi passare alla riga successiva per fare lo stesso fino a quando non ci sono più parole da posizionare. Questo metodo è utilizzato da molti moderni word processor, come ad esempio OpenOffice.org Writer e Microsoft Word., Questo algoritmo utilizza sempre il numero minimo possibile di linee, ma può portare a linee di lunghezze molto diverse. Il seguente pseudocodice, implementa l’algoritmo:

Dove LineWidth è la larghezza di una riga SpaceLeft è la parte rimanente di spazio sulla linea di riempimento SpaceWidth è la larghezza di un singolo carattere di spazio, Text è l’input di testo per scorrere e Word è una parola nel testo.,

Minimum raggednessEdit

Un algoritmo diverso, utilizzato in TeX, minimizza la somma dei quadrati delle lunghezze degli spazi alla fine delle linee per produrre un risultato esteticamente più gradevole. L’esempio seguente confronta questo metodo con l’algoritmo greedy, che non sempre minimizza lo spazio quadrato.,

Per il testo di input

AAA BB CC DDDDD

con la larghezza della linea 6, l’algoritmo greedy avrebbe prodotto:

------ 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 differenza qui è che la prima linea è interrotta prima di BB invece che dopo, producendo un migliore margine destro e un costo inferiore 11.,

utilizzando un algoritmo di programmazione dinamica per scegliere le posizioni in cui si desidera interrompere la linea, invece di scegliere pause avidamente, la soluzione con il minimo raggedness può essere trovato in tempo O ( n 2 ) {\displaystyle O(n^{2})} , dove n {\displaystyle n} è il numero di parole nel testo di input. In genere, la funzione di costo per questa tecnica dovrebbe essere modificata in modo che non conti lo spazio lasciato sulla riga finale di un paragrafo; questa modifica consente a un paragrafo di terminare nel mezzo di una riga senza penalità., È anche possibile applicare la stessa tecnica di programmazione dinamica per ridurre al minimo le funzioni di costo più complesse che combinano altri fattori come il numero di righe o costi per sillabare parole lunghe. Algoritmi di tempo lineare più veloci ma più complicati basati sull’algoritmo SMAWK sono noti anche per il problema del minimo raggedness e per alcune altre funzioni di costo che hanno proprietà simili.

HistoryEdit

Una caratteristica primitiva di rottura della linea è stata utilizzata nel 1955 in una “page printer control unit” sviluppata da Western Union., Questo sistema utilizzava relè piuttosto che computer digitali programmabili, e quindi necessitava di un semplice algoritmo che potesse essere implementato senza buffer di dati. Nel sistema Western Union, ogni riga è stata interrotta al primo carattere di spazio che appare dopo il 58 ° carattere, o al 70 ° carattere se non è stato trovato alcun carattere di spazio.

L’algoritmo greedy per la line-breaking precede il metodo di programmazione dinamica delineato da Donald Knuth in un memo inedito del 1977 che descrive il suo sistema di composizione TEX e successivamente pubblicato in modo più dettagliato da Knuth& Plass (1981).