Word Hy-phen-a-tion by Com-put-er
quittance.ru
документы
прочее

Алгоритм Ляна-Кнута для расстановки мягких переносов

Применение алгоритма Ляна-Кнута для качественной расстановки переносов

Алго­ритм Ляна-Кну­та для ав­то­ма­ти­че­ской рас­ста­нов­ки пе­ре­но­сов раз­ра­бо­тан в 1983 го­ду. Автор ал­го­рит­ма: Фран­клин Марк Лян (англ. Franklin Mark Liang), сту­дент про­фес­со­ра Дональ­да Эрви­на Кну­та (англ. Donald Ervin Knuth). Впер­вые ал­го­ритм был при­ме­нен в из­да­тель­ской си­сте­ме TeX, ав­то­ром ко­то­рой яв­ля­ет­ся проф. Дональд Кнут.

Алго­ритм ра­бо­та­ет в два эта­па.* На пер­вом эта­пе по сло­ва­рю пе­ре­но­сов стро­ит­ся от­но­си­тель­но ком­пакт­ный (в срав­не­нии с ис­ход­ным сло­ва­рем) на­бор пра­вил, поз­во­ля­ю­щий вос­ста­но­вить все ме­ста мяг­ких пе­ре­но­сов во всех сло­вах ис­ход­но­го сло­варя.

*) Как спра­вед­ли­во за­ме­ча­ет И. В. Батов, су­ще­ству­ет еще один не ме­нее важ­ный «нуле­вой» этап  под­го­тов­ка ис­ход­но­го сло­ва­ря пе­ре­но­сов.

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

Каче­ство рас­ста­нов­ки пе­ре­но­сов на­пря­мую за­ви­сит от ка­че­ства на­бо­ра пра­вил, ко­то­рое, в свою оче­редь, за­ви­сит от пол­но­ты и ка­че­ства ис­ход­но­го сло­ва­ря пе­ре­но­сов.

Пер­вый этап ал­го­рит­ма  из­го­тов­ле­ние на­бо­ра пра­вил, так на­зы­ва­е­мых «пат­тер­нов»  ре­а­ли­зу­ет­ся клас­си­че­ской про­грам­мой patgen, ко­то­рая, од­на­ко, тре­бу­ет осо­бо­го ис­кус­ства в об­ра­ще­нии.

Здесь бу­дем го­во­рить по­чти ис­клю­чи­тель­но о вто­ром эта­пе ал­го­рит­ма Ляна-Кну­та  рас­ста­нов­ке мяг­ких пе­ре­но­сов с ис­поль­зо­ва­ни­ем го­то­во­го на­бо­ра пра­вил. Вопро­сы пер­во­го эта­па, не го­во­ря уже о «нуле­вом», на­хо­дят­ся да­ле­ко за пре­де­ла­ми ком­пе­тен­ции ав­то­ра. Инте­ре­су­ю­щи­е­ся мо­гут по­чи­тать учеб­ник по patgen'у и дис­сер­та­цию Фран­кли­на Ляна: Word Hy-phen-a-tion by Com-put-er.

Алго­ритм Ляна-Кну­та ре­а­ли­зо­ван в веб-ори­ен­ти­ро­ван­ной си­сте­ме рас­ста­нов­ки мяг­ких пе­ре­но­сов phpHypher. Её ис­ход­ный код, рас­про­стра­ня­е­мый под сво­бод­ной ли­цен­зи­ей LGPL, до­сту­пен в под­раз­де­ле «ре­а­ли­за­ция рас­ста­нов­ки пе­ре­но­сов на php». Каче­ство ра­бо­ты мож­но оце­нить в раз­де­ле «Рас­ста­нов­ка пе­ре­но­сов».

комментировать 01/06/2010

Принцип работы алгоритма Ляна-Кнута при расстановке переносов

Шаб­ло­ны («пат­тер­ны») пе­ре­но­сов пред­став­ля­ют со­бой бук­во­со­че­та­ния, в на­ча­ле, в кон­це и меж­ду бук­ва­ми ко­то­рых рас­по­ло­же­ны чис­ла  уров­ни (англ. levels). Напри­мер:
.бе2з1у2
1бе
й1
ж1н
1зу
3ны
р1ж
р2жн
у1де
Если циф­ра в ка­кой-то по­зи­ции пат­тер­на от­сут­ству­ет, то счи­та­ет­ся, что там сто­ит 0. Послед­ний шаб­лон из вы­ше­при­ве­ден­но­го при­ме­ра в раз­вер­ну­том ви­де мож­но за­пи­сать сле­ду­ю­щим об­ра­зом: 0у1д0е0

Точ­ка в на­ча­ле или в кон­це пат­тер­на озна­ча­ет, что этот шаб­лон при­ме­ним толь­ко к на­ча­лу или к кон­цу сло­ва со­от­вет­ственно.

Нечет­ные уров­ни раз­ре­ша­ют пе­ре­нос в дан­ном ме­сте, чет­ные уров­ни, вклю­чая 0  за­пре­ща­ют. Боль­шее чис­ло име­ет при­о­ри­тет пе­ред мень­шим.

Про­ще го­во­ря, нечет­ный уро­вень в со­от­вет­ству­ю­щем сло­ву шаб­лоне ре­ко­мен­ду­ет пе­ре­нос сло­ва в опре­де­лен­ном ме­сте, но толь­ко ес­ли не най­дет­ся дру­го­го со­от­вет­ству­ю­ще­го сло­ву шаб­ло­на, в ко­то­ром на этом ме­сте сто­ит бо­лее вы­со­кий чет­ный уро­вень.

В про­цес­се рас­ста­нов­ки пе­ре­но­сов сло­во со­по­став­ля­ет­ся с бук­ва­ми каж­до­го шаб­ло­на, как по­ка­за­но ни­же (ну­ли опу­ще­ны для удо­бо­чи­та­е­мо­сти).
. б е з у д е р ж н ы й .
. б е2з1у2
1б е
1з у
у1д е
р1ж
р2ж н
ж1н
3н ы
й1
-------------------------
.1б е2з1у2д е р2ж3н ы й1.
^ ^
б е з|у д е р ж|н ы й => без-удерж-ный
В ме­стах, где раз­ные пат­тер­ны пред­ла­га­ют раз­ные уров­ни, при­ни­ма­ет­ся наи­боль­ший из них. В вы­ше­при­ве­ден­ном при­ме­ре шаб­лон p1ж раз­ре­ша­ет пе­ре­нос меж­ду бук­ва­ми «р» и «ж» на уровне 1, а шаб­лон p2жн за­пре­ща­ет этот пе­ре­нос бо­лее вы­со­ким уров­нем 2.

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

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

комментировать 31/05/2010

О ручном исправлении и дополнении набора правил переносов

К со­жа­ле­нию, иде­аль­но­го на­бо­ра пра­вил пе­ре­но­сов не су­ще­ству­ет. В ра­бо­те все они об­на­ру­жи­ва­ют ка­кие-ни­будь неточ­но­сти, а ино­гда да­же от­кро­вен­ные ошибки.

Неред­ко воз­ни­ка­ет же­ла­ние вруч­ную ис­пра­вить неко­то­рые шаб­ло­ны или до­пол­нить су­ще­ству­ю­щий на­бор пра­вил сво­и­ми пат­тер­нами.

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

Изго­тов­лен­ные вруч­ную пра­ви­ла от­но­си­тель­но без­опас­но при­ме­нять для за­пре­та оши­боч­ных или неже­ла­тель­ных пе­ре­но­сов, ис­поль­зуя ис­клю­чи­тель­но чет­ные уров­ни в шаб­ло­нах. Даже ес­ли за­пре­ти­тель­ное пра­ви­ло за­тронет дру­гие сло­ва и вос­пре­пят­ству­ет их пе­ре­но­су в за­кон­ных ме­стах, осо­бо­го вре­да от это­го не бу­дет.

Но по­рою при­хо­дит­ся вруч­ную го­то­вить и раз­ре­ши­тель­ные шаб­ло­ны, со­дер­жа­щие нечет­ные уров­ни. В та­ком слу­чае су­ще­ству­ет риск спро­во­ци­ро­вать оши­боч­ные пе­ре­но­сы в дру­гих сло­вах. Чтобы све­сти к ми­ни­му­му ве­ро­ят­ность ошиб­ки, мож­но ре­ко­мен­до­вать два оче­вид­ных пра­вила.

Пер­вое пра­ви­ло: ис­поль­зуй­те ми­ни­маль­ный уро­вень, при­во­дя­щий к тре­бу­е­мо­му ре­зуль­та­ту. Не сто­ит ста­вить уро­вень 5, ес­ли до­ста­точ­но еди­ни­цы. Чем мень­ше уро­вень, тем мень­ше ве­ро­ят­ность оши­боч­но­го пе­ре­но­са в дру­гих сло­вах, по­па­да­ю­щих под дей­ствие дан­но­го шаб­лона.

Вто­рое пра­ви­ло: не эко­номь­те на длине шаб­ло­на. Ста­рай­тесь сде­лать шаб­лон с нечет­ны­ми уров­ня­ми на­столь­ко длин­ным, на­сколь­ко воз­мож­но, при усло­вии охва­та им всех необ­хо­ди­мых сло­во­форм. Чем длин­нее шаб­лон, тем мень­ше «лиш­них» слов по­па­дет под его дей­ствие и тем ни­же бу­дет ве­ро­ят­ность оши­бок.

комментировать 31/05/2010
Copyright 2008–2010 Sergey Kurakin