Word Wrap este o problemă de optimizare. În funcție de ceea ce trebuie optimizat, se folosesc diferiți algoritmi.
numărul minim de liniiedit
o modalitate simplă de a face înfășurarea cuvintelor este să folosiți un algoritm lacom care pune cât mai multe cuvinte pe o linie, apoi treceți la linia următoare pentru a face același lucru până când nu mai rămân cuvinte la loc. Această metodă este utilizată de multe procesoare de text moderne, cum ar fi OpenOffice.org scriitor și Microsoft Word., Acest algoritm utilizează întotdeauna numărul minim posibil de linii, dar poate duce la linii de lungimi diferite. Următorul pseudocod implementează acest algoritm:
Unde LineWidth este lățimea de linie, SpaceLeft este restul de lățime de spațiu pe linie pentru a umple, SpaceWidth este lățimea de un singur caracter spațiu, Text este cea de introducere a textului pentru a itera peste si Word este un cuvânt din acest text.,un algoritm diferit, utilizat în TeX, minimizează suma pătratelor lungimilor spațiilor de la capătul liniilor pentru a produce un rezultat mai plăcut din punct de vedere estetic. Următorul exemplu compară această metodă cu algoritmul greedy, care nu minimizează întotdeauna spațiul pătrat.,
Pentru intrare text
AAA BB CC DDDDD
cu lățimea liniei 6, algoritmul greedy va produce:
------ 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
diferența aici este că prima linie este rupt înainte BB în loc de după ea, obținându-se o mai bună marginea din dreapta și un cost mai mic 11.,
folosind un algoritm de programare dinamică pentru a alege de la pozițiile la care să rupă linie, în loc de a alege pauze cu lăcomie, soluția cu minim raggedness poate fi găsit în timp O ( n 2 ) {\displaystyle O(n^{2})} , unde n {\displaystyle n} este numărul de cuvinte din textul de intrare. De obicei, funcția de cost pentru această tehnică ar trebui modificată astfel încât să nu contorizeze spațiul rămas pe linia finală a unui paragraf; această modificare permite unui paragraf să se încheie în mijlocul unei linii fără penalități., De asemenea, este posibil să se aplice aceeași tehnică de programare dinamică pentru a minimiza funcțiile de cost mai complexe care combină alți factori, cum ar fi numărul de linii sau Costurile pentru despărțirea cuvintelor lungi. Algoritmi de timp liniar mai rapide, dar mai complicate bazate pe algoritmul SMAWK sunt, de asemenea, cunoscute pentru problema raggedness minimă, și pentru unele alte funcții de cost care au proprietăți similare.
HistoryEdit
o caracteristică primitivă de rupere a liniei a fost utilizată în 1955 într-o „unitate de control a imprimantei de pagină” dezvoltată de Western Union., Acest sistem a folosit relee mai degrabă decât computere digitale programabile și, prin urmare, a avut nevoie de un algoritm simplu care ar putea fi implementat fără tampoane de date. În sistemul Western Union, fiecare linie a fost ruptă la primul caracter spațial care a apărut după cel de-al 58-lea caracter sau la cel de-al 70-lea caracter dacă nu a fost găsit niciun caracter spațial.
algoritmul greedy pentru linia de rupere precede metoda programării dinamice descrise de Donald Knuth într-un nepublicate 1977 memo descrierea lui TeX culegere de sistem și a publicat mai târziu în detaliu de către Knuth & Plass (1981).