Заокруживање речи
У представљању текста, преламање линије текста заправо представља надовезивање нове линије на крај претходне, када је она испуњена до краја, тако да свака линија одговара ширини прозора у којем читамо дати текст (омогућено је само померање, скроловање, текста вертикално, не и хоризонтално).
Заокруживање речи је додатна карактеристика већине уређивача текста (енгл. Text editor), процесора који обрађују речи (енгл. Word processor) и веб претраживача (Web browser). Заокруживање речи прекида линију текста између речи, а не у оквиру саме речи. Изузетак јесте случај када је сама реч дужа од максималне дужине линије текста и сама реч тада мора бити преломљена.
Меко преламање (енгл. Soft return) представља паузу, тачније празан простор који се појави у линији текста као последица заокруживања речи или преламања линије текста, док тврдо преламање (енгл. Hard return) представља намерно прављење празног простора у текст едиторима како би се обележио нови пасус. Другачије речено, тврдо преламање убацује линије прекида на местима заокруживања текста, док меко преламање раставља текст на местима прекида не убацујући намерне линије прекида између два дела преломљеног текста.
Меко преламање омогућава да се линије текста преломе тако да се оне аутоматски подешавају по ширини прозора у којем читамо текст или по ширини унапред подешених маргина неког текст едитора, процесора који обрађује речи или имејл клијента.
Границе речи, растављање цртицом и тврдо растављање цртицом
[уреди | уреди извор]Празни простори меког преламања се појављују или на крају завршене речи или након интерпункције која следи након завршене речи. Међутим, прелом се може јавити и унутар саме речи у виду цртице која прелама реч на два дела остављајући прву половину речи у претходној а другу половину у новој линији текста. У случајевима када не желимо такво растављање речи можемо користити опцију непрекидајуће цртице (енгл. non-breaking hyphen) која не дозвољава растављање речи цртицом или тврдо растављање цртицом (енгл. hard hyphen), када не желимо класично раздвајање цртицом.
Речи без цртице могу бити растављене и методом меког растављања цртицом. Када реч не излази ван оквира линије текста (није преломљена у оквиру линије текста), мека цртица није видљива. Уколико се деси да реч излази ван оквира линије текста, реч можемо поделити меком цртицом након чега је приказана као видљива цртица на горњем реду где је подељена реч. У ретким случајевима када се реч мора преломити на крају линије, тако да она другом половином ствара нову линију текста, уместо цртице може се појавити само празан простор нулте ширине. Тада се цртица не приказује.
У случајевима када је прелом непожељан између суседних речи можемо користити опцију тврдог размака (енгл. hard space) или непрекидајућег размака уместо регуларних размака.
Растављање речи у тексту који садржи јапанске, кинеске или корејанске карактере (CJK)
[уреди | уреди извор]У кинеском, јапанском или корејанском писму се сваки Хан-карактер (кинески карактер) сматра једном речју, па се растављање линија текста обично појављује пре или после Хан-карактера.
У неким случајевима, растављање није пожељно. На пример,
- преламање речи се углавном не жели код личних имена
- преламање сложених речи се углавном не жели (када је текст поравнат лево, само у неким стиловима)
Већина процесора и софтвера за писање и уређивање текста не подржавају ни један од горенаведених случајева.
CJK (кинески, јапански, и корејски) карактери могу или не морају поштовати горе поменута правила. Све зависи од правила прекида линија Источно азијских земаља.
Међутим, постоји специјални случај преламања линија текста за CJK карактере: преламање линија никада не сме да се деси унутар CJK цртица или елипса. Иако сваки од ових знакова интерпункције мора бити представљен са два лика, због ограничења свих постојећих кодирања знакова, сваки од њих је суштински један знак интерпункције ширине 2 ем-а а не два знака који имају ширину по један ем.
Алгоритам
[уреди | уреди извор]Преламање речи је проблем оптимизације. У зависности од тога за шта треба да буде оптимизован, користе се различити алгоритми.
Минимална дужина
[уреди | уреди извор]Једноставан начин на који можемо урадити растављање или заокруживање речи јесте похлепни алгоритам (greedy algorithm), који у линију текста поставља колико год је могуће речи, затим прелази на нову линију и врши исти процес све док има речи које треба сместити у текст. Ову методу користе многи модерни процесори као што су Apache OpenOffice Writer и [[Мајкрософт ворд]. Овај алгоритам увек користи најмањи могућ број линија али може довести до тога да су све линије различитих ширина што текст може учинити несређеним. Следећи псеудокод представља имплементацију овог алгоритма.
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 представља ширину линије, SpaceLeft је преостала ширина линије која треба да се попуни (празан простор), SpaceWidth је ширина појединачног размака, Text је текст који се уноси и Word представља појединачну реч из текста.
Минимална величина и снага
[уреди | уреди извор]Другачији алгоритам, коришћен у TeX-у смањује квадрат простора на крају линије и тиме производи естетски лепши резултат. Наредни пример пореди овај метод са похлепним алгоритмом, који не мора увек да минимизује квадрат простора.
За текст који се уноси
- aaa bb cc ddddd и ширину линије 6, похлепни алгоритам би урадио следеће:
------ Ширина линије: 6 aaa bb Преостало простора: 0 cc Преостало простора: 4 ddddd Преостало простора: 1
Збир преосталих квадрата овом методом је 02 + 42 + 12 = 17. Међутим, оптимално решење постиже мању суму 32 + 12 + 12 = 11:
------ Ширина линије: 6 aaa Преостало простора: 3 bb cc Преостало простора: 1 ddddd Преостало простора: 1
Разлика је у томе што је прва линија прекинута пре bb уместо после, што даје бољу десну маргину и мању суму 11.
Користећи алгоритам динамичког програмирања да изаберемо позицију на којој ће доћи до прелома линије текста, уместо да изаберемо прелом похлепног алгоритма, решење може бити пронађено за време O(n2), где је n број речи у тексту. Функције за овај метод би требало да буду модификоване тако да не рачунају преостали простор на крајњој линији пасуса. Ова модификација дозвољава пасусу да се заврши на средини линије без грешке. Такође, могуће је да применимо исту технику динамичког програмирања да минимизујемо комплексније функције које користе и друге факторе као што су број линија или цену дугачких речи које су раздвојене цртицом.[1] Бржи али компликованији алгоритми линеарне сложености су такође познати по проблему минималне величине и снаге и по другачијим функцијама са сличним опцијама.[2][3]
Историјат
[уреди | уреди извор]Примитивна карактеристика разбијања линија коришћена је још 1955. године од стране Western Union за "page printer control unit" (штампач). Овај сисетм користи релеје уместо програмибилних дигиталних рачунара, стога му је потребан једноставан алгоритам који не користи бафере података (data buffers). У Western Union систему свака линија текста је раздвајана при појави првог размака (space character) након 58. карактера или након 70. карактера ако тај размак није пронађен.[4]
Похлепни алгоритам за раздвајање линија текста претходи методи динамичког програмирања коју је осмислио Доналд Кнут, у необјављеном 1977 допису описује свој систем припрема TeX-у[5], а касније је објављен са више детаља од стране Кнут и Плас (Knuth & Plass 1981).
Референце
[уреди | уреди извор]- ^ 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. (јануар 1956), „Keyboard standardization”, Western Union Technical Review, 10 (1): 37—42, Архивирано из оригинала 03. 08. 2015. г., Приступљено 01. 06. 2013
- ^ Knuth, Donald (1977), TEXDR.AFT, Архивирано из оригинала 4. 3. 2016. г., Приступљено 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