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

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

Шаб­ло­ны («пат­тер­ны») пе­ре­но­сов пред­став­ля­ют со­бой бук­во­со­че­та­ния, в на­ча­ле, в кон­це и меж­ду бук­ва­ми ко­то­рых рас­по­ло­же­ны чис­ла  уров­ни (англ. 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
Добавить комментарий
Заполните форму, чтобы отправить свой комментарий. E-mail заполнять не обязательно, но имеет смысл, если Вы рассчитываете на ответ по почте. В любом случае, Ваш e-mail не будет опубликован.