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