Image Processing

Пе­ре­но­сы в сло­вах нуж­ны для то­го, что­бы текст вы­гля­дел бо­лее при­вле­ка­тель­но. При вы­рав­ни­ва­нии по обе­им сто­ро­нам раз­ме­ры про­бе­лов уве­ли­чи­ва­ют­ся не так за­мет­но, как в тек­сте без пе­ре­но­сов, а при вы­рав­ни­ва­нии по ле­во­му краю пра­вая гра­ни­ца бу­дет бо­лее ров­ной. Это вы­зва­но тем, что в тек­сте с пе­ре­но­са­ми име­ет­ся боль­ше мест для раз­би­е­ния строки́.

Для ав­то­ма­ти­че­ской рас­ста­нов­ки пе­ре­но­сов в рус­ско­языч­ных текстах я реа­ли­зо­вал на PHP быст­рый и ка­че­ствен­ный ал­го­ритм, ко­то­рый иден­ти­чен то­му, что ис­поль­зу­ет­ся в си­сте­ме TeX. Ав­то­ры ал­го­рит­ма — До­нальд Кнут и Франк Лянг.

Здесь вы мо­же­те ска­чать дис­сер­та­цию Фран­ка Лян­га по рас­ста­нов­ке пе­ре­но­сов: http://www.​tug.​org/​docs/​liang/.

Не­смот­ря на то, что ал­го­ритм был раз­ра­бо­тан 25 лет на­зад, он до сих пор ак­туа­лен, и его не уда­лось пре­взой­ти. Впро­чем, это ка­са­ет­ся все­го, к че­му при­ло­жил ру­ку До­нальд Кнут.

Я снаб­дил ал­го­ритм при­мер­но 5000 пра­ви­ла­ми пе­ре­но­сов, со­бран­ных из раз­лич­ных дис­три­бу­ти­вов LaTeX и из про­сто­ров Ин­тер­не­та. Про­ти­во­ре­чи­вые пра­ви­ла бы­ли про­ве­ре­ны вруч­ную. Спе­ци­аль­ные ст­рук­ту­ры дан­ных, ис­поль­зуе­мые в ал­го­рит­ме, поз­во­ля­ют до­стичь быст­ро­дей­ствия, не за­ви­ся­ще­го от ко­ли­че­ства при­ме­няе­мых пра­вил пе­ре­но­са.

Про­ве­рим ал­го­ритм на сле­дую­щем тек­сте:

Алисе наскучило сидеть с сестрой без дела на берегу реки; разок-другой она заглянула в книжку, которую читала сестра, но там не было ни картинок, ни разговоров.

— Что толку в книжке, — подумала Алиса, — если в ней нет ни картинок, ни разговоров?

Она сидела и размышляла, не встать ли ей и не нарвать ли цветов для венка; мысли ее текли медленно и несвязно — от жары ее клонило в сон. Конечно, сплести венок было бы очень приятно, но стоит ли ради этого подыматься?

Вдруг мимо пробежал белый кролик с красными глазами.

Конечно, ничего удивительного в этом не было. Правда, Кролик на бегу говорил:
— Ах, боже мой, боже мой! Я опаздываю.

Но и это не показалось Алисе особенно странным. (Вспоминая об этом позже, она подумала, что ей следовало бы удивиться, однако в тот миг все казалось ей вполне естественным.) Но, когда Кролик вдруг вынул часы из жилетного кармана и, взглянув на них, помчался дальше, Алиса вскочила на ноги. Ее тут осенило: ведь никогда раньше она не видела кролика с часами, да еще с жилетным карманом в придачу! Сгорая от любопытства, она побежала за ним по полю и только-только успела заметить, что он юркнул в нору под изгородью.

В тот же миг Алиса юркнула за ним следом, не думая о том, как же она будет выбираться обратно.

Вот ре­зуль­тат. Ал­го­ритм об­ра­ба­ты­ва­ет все сло­ва длин­нее трёх букв; та­кие сло­ва по­ме­че­ны жир­ным шриф­том. Воз­мож­ные ме­ста пе­ре­но­сов по­ка­за­ны сме­ной цве­та с бар­до­во­го на зе­лё­ный и об­рат­но. Под­ра­зу­ме­ва­ет­ся, что каж­дое сло­во бу­дет пе­ре­не­се­но не бо­лее чем в од­ном ме­сте:

Алисе наскучило сидеть с сестрой без дела на берегу реки; разок-другой она заглянула в книжку, которую читала сестра, но там не было ни картинок, ни разговоров.

— Что толку в книжке, — подумала Алиса, — если в ней нет ни картинок, ни разговоров?

Она сидела и размышляла, не встать ли ей и не нарвать ли цветов для венка; мысли ее текли медленно и несвязно — от жары ее клонило в сон. Конечно, сплести венок было бы очень приятно, но стоит ли ради этого подыматься?

Вдруг мимо пробежал белый кролик с красными глазами.

Конечно, ничего удивительного в этом не было. Правда, Кролик на бегу говорил:
— Ах, боже мой, боже мой! Я опаздываю.

Но и это не показалось Алисе особенно странным. (Вспоминая об этом позже, она подумала, что ей следовало бы удивиться, однако в тот миг все казалось ей вполне естественным.) Но, когда Кролик вдруг вынул часы из жилетного кармана и, взглянув на них, помчался дальше, Алиса вскочила на ноги. Ее тут осенило: ведь никогда раньше она не видела кролика с часами, да еще с жилетным карманом в придачу! Сгорая от любопытства, она побежала за ним по полю и только-только успела заметить, что он юркнул в нору под изгородью.

В тот же миг Алиса юркнула за ним следом, не думая о том, как же она будет выбираться обратно.

На­по­ми­наю, что ме­ста воз­мож­ной рас­ста­нов­ки пе­ре­но­сов в рус­ском язы­ке не все­гда сов­па­да­ют с гра­ни­ца­ми сло­гов.

Ал­го­ритм до­ста­точ­но мощ­ный, что­бы об­ра­бо­тать са­мые слож­ные сло­ва (кое-где не­до­ста­ёт воз­мож­ных пе­ре­но­сов, я знаю):

Бодр-ство-вать Мудр-ство-вать
Быст-ро-вы-зы-вае-мый
Адъ-юнкт-ство Бур-го-мистр-ство
Контр-стра-те-гия
Пред-праздн-ство Рот-мистр-ство
Сверх-встре-во-жен-ный
Взблеск Вспласт Всплеск Вспрыск
Фельдъ-егерь
Те-ле-грам-ма-ап-па-рат
Ме-ток-си-хлор-ди-этилами-но-ме-тил-бу-тилами-ноак-ри-дин
Че-ты-рёх-сот-вось-ми-де-ся-ти-че-ты-рёх-мил-ли-грам-мо-вый
Рент-ге-но-элек-тро-кар-дио-гра-фи-че-ско-го
Пре-вы-со-ко-мно-го-рас-смот-ри-тель-ствую-щий
Част-но-пред-при-ни-матель-ский
Са-мо-но-со-ро-го-по-доб-ность
Зря-че-ню-хо-слы-ша-щий
Ра-зум По-душ-ка

Про­ве­рить ал­го­ритм рас­ста­нов­ки пе­ре­но­сов на сво­ём тек­сте вы мо­же­те здесь.

О пра­ви­лах пе­ре­но­са в рус­ском язы­ке мож­но по­чи­тать здесь: http://www.​rusyaz.​ru/​pr/​opp.html

P.S.

За­ме­чу, что эта раз­ра­бот­ка — не пер­вая в Ин­тер­не­те.

Ре­ко­мен­дую по­се­тить сайт Иго­ря Ба­то­ва, по­свя­щё­ный, в ос­нов­ном, ав­то­ма­ти­че­ской рас­ста­нов­ке пе­ре­но­сов. Там же мож­но про­те­сти­ро­вать его ал­го­рит­мы и ал­го­рит­мы кон­ку­рен­тов.

Боль­шин­ство осталь­ных под­хо­дов ос­но­ва­ны на ис­поль­зо­ва­нии не­сколь­ких про­стых пра­вил, что вы­гля­дит смеш­но для «Ве­ли­ко­го и Мо­гу­че­го», на­при­мер: http://xpoint.ru/know-how/VebAlgoritmyi/RabotaSTekstami/RasstanovkaPerenosov.

Вот ин­те­рес­ный под­ход, ос­но­ван­ный на ис­поль­зо­ва­нии рас­ста­нов­щи­ка пе­ре­но­сов на сто­ро­не кли­ен­та (JavaScript): http://snusmumrik.org.ru/ru/hyph/