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

При разработке приложений, связанных с отображением текста, часто возникает задача расстановки переносов в словах.Столкнулись с такой задачей и мы.

Для её решения первым делом подключили готовую js-библиотеку, которая хоть и расставляла переносы хорошо, но ужасно тормозила - между загрузкой страницы и отрисовкой на ней текста с расставленными переносами проходило примерно 1-2 секунды. После разочарования принялись пытаться перенести этот алгоритм на сторону сервера, но так и не нашли готовых библиотек на C#, зато нашли описание алгоритма и код на Си.

Описание

Немного объясню, как это все работает - фактически нам надо определить в словах все места в которых возможна установка знака переноса, после чего отобразить перенос только в нужном месте, для этого существует символ "мягкого переноса" (в HTML обозначается мнемоникой ­). С помощью этого символа в словах помечаются места возможного переноса, после чего, при отображении текста, браузер (или другой рендер) при необходимости разрывает слово ставя уже полноценный символ переноса, в других местах, где перенос возможен, но не нужен не отображается ничего.

Сейчас почти стандартным алгоритмом для расстановки мягких переносов является Алгоритм Ляна-Кнута, который используется в таких системах, как TeX или OpenOffice.

Этот алгоритм предложенный в 1983 Франклином Ляном (Franklin Mark Liang) - учеником того самого Кнута, не зависит от языка текста и работает на заранее заданных паттернах. Когда-то паттерны были извлечены из заранее размеченного набора слов, но как оказалось, что с их помощью алгоритм может "угадывать" правильные места переносов в тех словах, которых не было в обучающей выборке, кроме того, они постоянно улучшаются и пополняются. Набор паттернов для каждого языка, естественно, свой. Более подробно о алгоритме можно почитать на хабре, там же есть реализация на Си.

Отмечу, что правил для русского языка около 8К, что не очень хорошо сказывается на потреблении памяти. На сервере это незаметно, но если вы делаете приложение для телефонов – это может играть роль и тогда советую обратить внимание на алгоритм П.Христова в модификации Дымченко и Варсанофьева. Он чуть похуже и подходит, вроде-как только для русского, но работать должен быстрее, кушать поменьше памяти, да и реализуется на паре-тройке регексов.

Библиотека

После нескольких часов вспоминания особенностей Cи и портирования на C# найденных исходников, появилась небольшая библиотека которая теперь доступна на github. Для тех, кто хочет поизучать код – добро пожаловать в репозиторий, а всем остальным в – нугет. Сейчас в ней доступны только два языка – английский (в британской и американской версии) и русский. При необходимости можно скачать исходный код и подложить паттерны для нужного языка, все инструкции и ссылка на репозиторий с паттернами TeX присутствуют в комментариях к исходному коду.

Для того чтобы использовать ее в вашем проекте достаточно написать

Hyphenator hyphenator= new Hyphenator(HyphenatePatternsLanguage.EnglishUs, "-");
var result = hyphenator.HyphenateText(text);

здесь мы расставляем переносы в тексте из переменной text используя паттерны для американского английского. В реальной жизни вы скорее всего вместо черточки ("-") будете использовать ­ для мягкого переноса.

Также в конструкторе Hypenator можно указать минимальное количество символов в слове, для которого включается расстановка переносов и минимальное количество символов, которое остается на строке при переносе, по умолчанию эти значения равны 5 и 3 символам соотвественно. Ещё один параметр отвечает за то, надо ли переносить последнее слово вообще, по умолчанию он установлен в false.


comments powered by HyperComments
Яндекс.Метрика