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

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

Алгоритм основан на сравнении исходного слова с набором правил (шаблонов). Чем больше правил и чем качественнее они составлены, тем лучше будут расставляться переносы. В пакете TeX можно найти готовые бесплатные наборы правил для многих языков, нужно только внимательно смотреть на условия использования и распространения.

Пример правил:

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

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

Основные этапы работы алгоритма:

  1. Выбрать все правила, подходящие к выбранному слову и для каждой позиции в слове получить набор уровней (сколько правил пришлось на одну позицию, столько и уровней получим).
  2. В каждой позиции выбрать максимальный уровень. Если он четный – здесь переносить нельзя, если нечетный – допустимое место переноса.
  3. Отсечь очевидно недопустимые переносы (например, одна буква в начале или в конце).

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

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

Сопоставим слово со всеми правилами и выберем наибольшие уровни:

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

Реализация

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

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

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

void sort_pattern_list(pattern_list_t* pattern_list)
{
    if (!pattern_list) return;
    std::sort(pattern_list->list.begin(), pattern_list->list.end(), pattern_compare);
}

Теперь непосредственно алгоритм нахождения переносов:
std::vector<unsigned char> levels;
levels.assign(word_string.size(), 0);

for (size_t i = 0; i < word_string.size()-2; ++i)
{
    std::vector<pattern_t*>::const_iterator pattern_iter = pattern_list->list.begin();
    for (size_t count = 1; count <= word_string.size()-i; ++count)
    {
        pattern_t pattern_from_word;
        pattern_from_word.str = word_string.substr(i, count);
        if (pattern_compare(&pattern_from_word, *pattern_iter))
            continue;
        pattern_iter = std::lower_bound(pattern_iter, pattern_list->list.end(), &pattern_from_word, pattern_compare);
        if (pattern_iter == pattern_list->list.end())
            break;
        if (!pattern_compare(&pattern_from_word, *pattern_iter)) 
        {
            for (size_t level_i = 0; level_i < (*pattern_iter)->levels.size(); ++level_i)
            {
                unsigned char l = (*pattern_iter)->levels[level_i];
                if (l > levels[i+level_i]) 
                levels[i+level_i] = l;
            }
        }
    }
}

В строку word_string мы помещаем исходное слово, с добавленными символами '.' по краям, чтобы автоматически подбирались правила, содержащие указания о своей позиции в слове. Теперь в исходном слове для каждого символа с i=0 до N перебираем все подстроки начинающиеся с i и длиной от 1 до N-i. Ищем каждую подстроку в векторе правил стандартным алгоритмом std::lower_bound. Исходим из того, что правила отсортированы нужным нам образом и нет необходимости на каждом шаге перебирать все заново. Когда находим совпадение, берем вектор уровней и применяем его к текущему результату, т.е. если уровень для текущей позиции в правиле выше, запоминаем его вместо старого.

В векторе levels скапливаются максимальные значения уровней для каждой позиции. Осталось проверить его на нечетные значения.
mask_size = levels.size()-2;
mask = new unsigned char[mask_size];
for (size_t i = 0; i < mask_size; ++i)
{
    if (levels[i+1] % 2 && i) 
        mask[i] = 1;
    else 
        mask[i] = 0;
}

Примеры работы алгоритма для набора правил из TeX:
про-грам-мист
ки-бер-не-ти-ка
вопль
ин-ту-и-ци-я
до-сто-при-ме-ча-тель-ность
при-вет


Готовый код на С++ вместе с приведенными примерами можно скачать здесь. Тестовый пример в файле main.c (кодировка Windows-1251), правила в файле patterns.h.
Поделиться публикацией
Комментарии 15
    0
    >нужно учитывать особенности каждого языка, чтобы решить, в каком месте разорвать слово
    В примерах указан только русский язык. А как это будет выглядеть для английского, немецкого и китайского языков?
      +1
      Не знаю, как насчет китайского, словарь не попадался, а для английского и немецкого достаточно взять соответствующий набор правил. Вот например для английского (по шаблонам из TeX):
      hel-lo
      ap-pli-ca-tion
      descrip-tion
    • НЛО прилетело и опубликовало эту надпись здесь
        0
        Действительно! Спасибо, я этого не знал
          +3
          Не знаю что там знают дворники, но в японском, в отличие от китайского, помимо иероглифов есть еще и кана, которая имеет правила переноса. Например, нельзя переносить «маленькую» кану на новую строчку:


          ップロード < — будет неверно

          а также еще куча разных спец. значков: удлинения звука в катакане ー, скобок 『 (full-width) и проч. (вкратце, можно почитать тут).

          Ну и плюс ко всему есть стилистическое разбиение, например, если строка заканчивается на です, переносить лучше её всю целиком, а не отдельно で и す.
          0
          То ли я недопонял этот алгоритм, то ли он нерабочий…
          Нельзя ли пояснить, как сформлировать в его терминах правило «в каждой из частей перенесённого слова должен быть хотя бы один гласный» (то, что называлось «перенос по слогам» когда я вшколе учился)?
            +2
            Формулируется не одним правилом, а их набором и приоритетами между ними. Алгоритм не дает 100% гарантии правильности переносов, но качество напрямую зависит от набора шаблонов и их согласованности. Вы можете наделать правил, в которых будет хотя бы одна гласная и разрешить перенос или запретить, можно сделать комбинации для всех возможных гласных и согласных. Пример: правило «1п0р0и1» — запрещает разбивать «при» на куски, но разрешает отделять «при» от остального слова. Разумеется надо следить, чтобы другие правила не ломали предыдущие если у них уровни выше.
              0
              всё равно не понял. Как мне гарантировать то, что всегда в обеих частях будет по гласной?
              Предположим, у меня есть правило
              по1
              , которое гарантирует возможность переноса в правильном месте слов
              поход
              полёт
              покос
              понос
              И попалось мне слово полк.
              Это правило радостно сообщит мне что да, после приставки «по» надо переносить.
              Предлагается рисовать правило
              2лк
              я верно понял? Но тогда правил таких нужны полчища, и мы в них очень быстро запутаемся.
                +2
                Да, все верно, правил нужно достаточно много, чтобы охватить самые распространенные сочетания. Поэтому 100% результата никто и не обещает, слишком много правил это медленно и трудоемко для составления. Но однако алгоритм все равно дает неплохие результаты на словаре из TeX, в котором почти 5000 шаблонов.
              0
              1. разбиение на слоги и правила переноса несколько разные вещи.
              например: а-па-ти-я
              2. слогоделение — морфо-фонетическое явление, специфичное для каждого языка.
              а чуваки изобрели универсальный алгоритм.
              +4
              Если лень возится с Ляна-Кнутом, и требуется только русский язык, то можно воспользоваться алгоритмом П.Хpистова в модификации Дымченко и Ваpсанофьева.

              Всего шесть правил:

              «Х-»
              «Г-Г»
              «ГС-СГ»
              «СГ-СГ»
              «ГС-ССГ»
              «ГСС-ССГ»


              Где: Г — гласная, С — согласная, Х — буква из набора «ьъй».

              Элементарно реализуется на регекспах.
              Утверждается, что покрывает немалую часть правил русского языка.
                +2
                Ух ты, оказывается 2 года назад я «изобрёл» алгоритм П.Христова :) А ведь искал перед этим в сети, но не нашёл. Честно сказать, набор шаблонов очень небольшой и алгоритм довольно простой. Не проверял на «Войне и мире», конечно, но нареканий по работе не было.
                  +1
                  А можно так без регэкспов: sites.google.com/site/foliantapp/project-updates/hyphenation
                  +2
                  Такой алгоритм подходит только для частных случаев, увы. Анализ с учетом морфологии слов (то есть правил русского языка) куда надежней будет.
                    0
                    И как быстро работает на девайсе? Сколько времени надо на обработку страницы среднего шрифта на iPad?

                    Только полноправные пользователи могут оставлять комментарии. Войдите, пожалуйста.

                    Самое читаемое