Алгоритмы / [Из песочницы] Алгоритм Ляна-Кнута для расстановки мягких переносов

При работе с текстом часто возникает потребность корректно расставить переносы. Задача на первый взгляд не такая уж очевидная, нужно учитывать особенности каждого языка, чтобы решить, в каком месте разорвать слово. Как правильно формализовать такие требования, и как потом применить их в алгоритме? Одно из самых распространенных на сей день решений предложил Франклин Марк Лян, студент известного профессора Дональда Кнута. Алгоритм так и называется – «Алгоритм Ляна-Кнута», он применяется в издательской системе TeX, автор которой опять же Д. Кнут.
Алгоритм основан на сравнении исходного слова с набором правил (шаблонов). Чем больше правил и чем качественнее они составлены, тем лучше будут расставляться переносы. В пакете TeX можно найти готовые бесплатные наборы правил для многих языков, нужно только внимательно смотреть на условия использования и распространения.
Пример правил:

при1
при3в
2и1ве
.по3ж2

Каждое правило состоит из букв и цифр между ними, а также цифр в начале и в конце. Цифру 0 обычно опускают. Например, первое правило должно пониматься как 0п0р0и1. Последовательность букв – это часть слова, для которой определяется перенос, т.е. эта последовательность должна присутствовать в слове. Цифры называют «уровнем», они задают приоритет между правилами и возможность переноса в соответствующей позиции. Четные цифры, включая 0, запрещают перенос. Нечетные – разрешают. Точка в начале правила означает, что правило применяется, только если последовательность находится в начале слова. Аналогично с точкой в конце – слово должно заканчиваться этой последовательностью. Если точка есть и в начале и в конце, то правило содержит слово целиком.
Основные этапы работы алгоритма:
Выбрать все правила, подходящие к выбранному слову и для каждой позиции в слове получить набор уровней (сколько правил пришлось на одну позицию, столько и уровней получим).

В каждой позиции выбрать максимальный уровень. Если он четный – здесь переносить нельзя, если нечетный – допустимое место переноса.

Отсечь очевидно недопустимые переносы (например, одна буква в начале или в конце).

Посмотрим работу алгоритма на примере:

Исходное слово: алгоритм
Набор правил (взяты из TeX):
лго1
1г
о1ри
и1т
и2тм
тм2

Сопоставим слово со всеми правилами и выберем наибольшие уровни:
В позициях с уровнем 1 можно смело ставить перенос. Получаем результат «ал-го-ритм».
Реализация

Теперь реализуем этот алгоритм на языке С++. Мне нужен был рабочий алгоритм для использования в iOS, поэтому я сделал все в виде Си-шного интерфейса. Модуль написан без привязки к какой-либо локали или платформе, можно использовать где угодно.
Правило будем хранить так:
struct pattern_t
{
std::basic_string str;
std::vector levels;
};

Будем преобразовывать каждое правило в вид «чистая последовательность символов» + «набор уровней», чтобы удобно было применять в дальнейшем.
Набор правил:
struct pattern_list_t
{
std::vector list;
};

Код для выдергивания уровней из правил простой, его можно посмотреть в полных исходниках по ссылке в конце статьи.
После того как мы заполним список правил, его нужно отсортировать, чтобы обеспечить правильную и эффективную работу алгоритма. Напишем свою функцию less и применим стандартный алгоритм сортировки:
bool pattern_compare(const pattern_t* a, const pattern_t* b)
{
bool first = a->str.size() str.size();
size_t min_size = first ? a->str.size() : b->str.size();
for (size_t i = 0; i str[i] str[i])
return true;
else if (a->str[i] > b->str[i])
return false;
}
return first;
}