Zaokruživanje reči

U predstavljanju teksta, prelamanje linije teksta zapravo predstavlja nadovezivanje nove linije na kraj prethodne, kada je ona ispunjena do kraja, tako da svaka linija odgovara širini prozora u kojem čitamo dati tekst (omogućeno je samo pomeranje, skrolovanje, teksta vertikalno, ne i horizontalno).

Zaokruživanje reči je dodatna karakteristika većine uređivača teksta (engl. Text editor), procesora koji obrađuju reči (engl. Word processor) i veb pretraživača (Web browser). Zaokruživanje reči prekida liniju teksta između reči, a ne u okviru same reči. Izuzetak jeste slučaj kada je sama reč duža od maksimalne dužine linije teksta i sama reč tada mora biti prelomljena.

Meko prelamanje (engl. Soft return) predstavlja pauzu, tačnije prazan prostor koji se pojavi u liniji teksta kao posledica zaokruživanja reči ili prelamanja linije teksta, dok tvrdo prelamanje (engl. Hard return) predstavlja namerno pravljenje praznog prostora u tekst editorima kako bi se obeležio novi pasus. Drugačije rečeno, tvrdo prelamanje ubacuje linije prekida na mestima zaokruživanja teksta, dok meko prelamanje rastavlja tekst na mestima prekida ne ubacujući namerne linije prekida između dva dela prelomljenog teksta.

Meko prelamanje omogućava da se linije teksta prelome tako da se one automatski podešavaju po širini prozora u kojem čitamo tekst ili po širini unapred podešenih margina nekog tekst editora, procesora koji obrađuje reči ili imejl klijenta.

Granice reči, rastavljanje crticom i tvrdo rastavljanje crticom

Prazni prostori mekog prelamanja se pojavljuju ili na kraju završene reči ili nakon interpunkcije koja sledi nakon završene reči. Međutim, prelom se može javiti i unutar same reči u vidu crtice koja prelama reč na dva dela ostavljajući prvu polovinu reči u prethodnoj a drugu polovinu u novoj liniji teksta. U slučajevima kada ne želimo takvo rastavljanje reči možemo koristiti opciju neprekidajuće crtice (engl. non-breaking hyphen) koja ne dozvoljava rastavljanje reči crticom ili tvrdo rastavljanje crticom (engl. hard hyphen), kada ne želimo klasično razdvajanje crticom.

Reči bez crtice mogu biti rastavljene i metodom mekog rastavljanja crticom. Kada reč ne izlazi van okvira linije teksta (nije prelomljena u okviru linije teksta), meka crtica nije vidljiva. Ukoliko se desi da reč izlazi van okvira linije teksta, reč možemo podeliti mekom crticom nakon čega je prikazana kao vidljiva crtica na gornjem redu gde je podeljena reč. U retkim slučajevima kada se reč mora prelomiti na kraju linije, tako da ona drugom polovinom stvara novu liniju teksta, umesto crtice može se pojaviti samo prazan prostor nulte širine. Tada se crtica ne prikazuje.

U slučajevima kada je prelom nepoželjan između susednih reči možemo koristiti opciju tvrdog razmaka (engl. hard space) ili neprekidajućeg razmaka umesto regularnih razmaka.

Rastavljanje reči u tekstu koji sadrži japanske, kineske ili korejanske karaktere (CJK)

U kineskom, japanskom ili korejanskom pismu se svaki Han-karakter (kineski karakter) smatra jednom rečju, pa se rastavljanje linija teksta obično pojavljuje pre ili posle Han-karaktera.

U nekim slučajevima, rastavljanje nije poželjno. Na primer,

prelamanje reči se uglavnom ne želi kod ličnih imena
prelamanje složenih reči se uglavnom ne želi (kada je tekst poravnat levo, samo u nekim stilovima)

Većina procesora i softvera za pisanje i uređivanje teksta ne podržavaju ni jedan od gorenavedenih slučajeva.

CJK (kineski, japanski, i korejski) karakteri mogu ili ne moraju poštovati gore pomenuta pravila. Sve zavisi od pravila prekida linija Istočno azijskih zemalja.

Međutim, postoji specijalni slučaj prelamanja linija teksta za CJK karaktere: prelamanje linija nikada ne sme da se desi unutar CJK crtica ili elipsa. Iako svaki od ovih znakova interpunkcije mora biti predstavljen sa dva lika, zbog ograničenja svih postojećih kodiranja znakova, svaki od njih je suštinski jedan znak interpunkcije širine 2 em-a a ne dva znaka koji imaju širinu po jedan em.

Algoritam

Prelamanje reči je problem optimizacije. U zavisnosti od toga za šta treba da bude optimizovan, koriste se različiti algoritmi.

Minimalna dužina

Jednostavan način na koji možemo uraditi rastavljanje ili zaokruživanje reči jeste pohlepni algoritam (greedy algorithm), koji u liniju teksta postavlja koliko god je moguće reči, zatim prelazi na novu liniju i vrši isti proces sve dok ima reči koje treba smestiti u tekst. Ovu metodu koriste mnogi moderni procesori kao što su Apache OpenOffice Writer i [[Majkrosoft vord]. Ovaj algoritam uvek koristi najmanji moguć broj linija ali može dovesti do toga da su sve linije različitih širina što tekst može učiniti nesređenim. Sledeći pseudokod predstavlja implementaciju ovog algoritma.

SpaceLeft := LineWidth
for each Word in Text
    if (Width(Word) + SpaceWidth) > SpaceLeft
        insert line break before Word in Text
        SpaceLeft := LineWidth - Width(Word)
    else
        SpaceLeft := SpaceLeft - (Width(Word) + SpaceWidth)

LineWidth predstavlja širinu linije, SpaceLeft je preostala širina linije koja treba da se popuni (prazan prostor), SpaceWidth je širina pojedinačnog razmaka, Text je tekst koji se unosi i Word predstavlja pojedinačnu reč iz teksta.

Minimalna veličina i snaga

Drugačiji algoritam, korišćen u TeX-u smanjuje kvadrat prostora na kraju linije i time proizvodi estetski lepši rezultat. Naredni primer poredi ovaj metod sa pohlepnim algoritmom, koji ne mora uvek da minimizuje kvadrat prostora.

Za tekst koji se unosi

aaa bb cc ddddd i širinu linije 6, pohlepni algoritam bi uradio sledeće:

------    Ширина линије: 6
aaa bb    Преостало простора: 0
cc        Преостало простора: 4
ddddd     Преостало простора: 1

Zbir preostalih kvadrata ovom metodom je 0² + 4² + 1² = 17. Međutim, optimalno rešenje postiže manju sumu 3² + 1² + 1² = 11:

------    Ширина линије: 6
aaa       Преостало простора: 3
bb cc     Преостало простора: 1
ddddd     Преостало простора: 1

Razlika je u tome što je prva linija prekinuta pre bb umesto posle, što daje bolju desnu marginu i manju sumu 11.

Koristeći algoritam dinamičkog programiranja da izaberemo poziciju na kojoj će doći do preloma linije teksta, umesto da izaberemo prelom pohlepnog algoritma, rešenje može biti pronađeno za vreme O(n²), gde je n broj reči u tekstu. Funkcije za ovaj metod bi trebalo da budu modifikovane tako da ne računaju preostali prostor na krajnjoj liniji pasusa. Ova modifikacija dozvoljava pasusu da se završi na sredini linije bez greške. Takođe, moguće je da primenimo istu tehniku dinamičkog programiranja da minimizujemo kompleksnije funkcije koje koriste i druge faktore kao što su broj linija ili cenu dugačkih reči koje su razdvojene crticom.^[1] Brži ali komplikovaniji algoritmi linearne složenosti su takođe poznati po problemu minimalne veličine i snage i po drugačijim funkcijama sa sličnim opcijama.^[2]^[3]

Istorijat

Primitivna karakteristika razbijanja linija korišćena je još 1955. godine od strane Western Union za "page printer control unit" (štampač). Ovaj sisetm koristi releje umesto programibilnih digitalnih računara, stoga mu je potreban jednostavan algoritam koji ne koristi bafere podataka (data buffers). U Western Union sistemu svaka linija teksta je razdvajana pri pojavi prvog razmaka (space character) nakon 58. karaktera ili nakon 70. karaktera ako taj razmak nije pronađen.^[4]

Pohlepni algoritam za razdvajanje linija teksta prethodi metodi dinamičkog programiranja koju je osmislio Donald Knut, u neobjavljenom 1977 dopisu opisuje svoj sistem priprema TeX-u^[5], a kasnije je objavljen sa više detalja od strane Knut i Plas (Knuth & Plass 1981).

Reference

^ Knuth, Donald E.; Plass, Michael F. (1981), „Breaking paragraphs into lines”, Software: Practice and Experience, 11 (11): 1119—1184, doi:10.1002/spe.4380111102
^ Wilber, Robert (1988), „The concave least-weight subsequence problem revisited”, Journal of Algorithms, 9 (3): 418—425, MR 955150, doi:10.1016/0196-6774(88)90032-6
^ Galil, Zvi; Park, Kunsoo (1990), „A linear-time algorithm for concave one-dimensional dynamic programming”, Information Processing Letters, 33 (6): 309—311, MR 1045521, doi:10.1016/0020-0190(90)90215-J
^ Harris, Robert W. (januar 1956), „Keyboard standardization”, Western Union Technical Review, 10 (1): 37—42, Arhivirano iz originala 03. 08. 2015. g., Pristupljeno 01. 06. 2013
^ Knuth, Donald (1977), TEXDR.AFT, Arhivirano iz originala 4. 3. 2016. g., Pristupljeno 7. 4. 2013 . Reprinted in Knuth, Donald (1999), Digital Typography, CSLI Lecture Notes, 78, Stanford, California: Center for the Study of Language and Information, ISBN 978-1-57586-010-7

Vidi još

[knuth-plass-1] Knuth, Donald E.; Plass, Michael F. (1981), „Breaking paragraphs into lines”, Software: Practice and Experience, 11 (11): 1119—1184, doi:10.1002/spe.4380111102

[2] Wilber, Robert (1988), „The concave least-weight subsequence problem revisited”, Journal of Algorithms, 9 (3): 418—425, MR 955150, doi:10.1016/0196-6774(88)90032-6

[3] Galil, Zvi; Park, Kunsoo (1990), „A linear-time algorithm for concave one-dimensional dynamic programming”, Information Processing Letters, 33 (6): 309—311, MR 1045521, doi:10.1016/0020-0190(90)90215-J

[4] Harris, Robert W. (januar 1956), „Keyboard standardization”, Western Union Technical Review, 10 (1): 37—42, Arhivirano iz originala 03. 08. 2015. g., Pristupljeno 01. 06. 2013

[5] Knuth, Donald (1977), TEXDR.AFT, Arhivirano iz originala 4. 3. 2016. g., Pristupljeno 7. 4. 2013 . Reprinted in Knuth, Donald (1999), Digital Typography, CSLI Lecture Notes, 78, Stanford, California: Center for the Study of Language and Information, ISBN 978-1-57586-010-7

[1]

[2]

[3]

[4]

[5]