Красивый перенос строк

Этот абзац набран вашим браузером, и набран жадно: браузер кладёт в строку слова, пока они помещаются, а следующее слово переносит, не думая о том, что будет дальше. Так быстро, но правый край выходит рваным: одна строка доходит почти до края, другая обрывается на середине, потому что длинное слово в неё не влезло. TeX, программа Дональда Кнута для набора книг, поступает иначе: смотрит на абзац целиком и выбирает места переноса так, чтобы все строки были примерно одинаковой длины. Ниже этот самый абзац набран обоими способами в колонку, ширину которой можно менять.

Слева у некоторых строк справа видна глубокая пустота; справа пустоты мельче, но их больше. Сумма квадратов недобора — мерка ровности края — справа всегда не больше, а самая короткая строка обычно заметно длиннее, чем слева. В режиме «по ширине» пустоту приходится раздавать пробелам, и в узкой колонке они растягиваются в четыре-пять раз при любом способе. Перебор по всему абзацу с ценой, растущей как куб растяжения, — так считает TeX — убирает самые страшные строки: у нас в колонке 400 пикселей самый растянутый пробел стал в 3,7 раза шире обычного вместо 5,3; в вашем браузере числа могут немного отличаться. Совсем без дыр узкую колонку по ширине не набрать — нужны переносы внутри слов.

На всех 119 вводных абзацах этого каталога в колонке из 35 знаков — примерно столько помещается в строку на телефоне — жадный набор и лучший расходятся в 107 абзацах. Сумма квадратов недобора падает с 35 615 до 30 107, а самая короткая строка во всех абзацах становится короче края не на 29 знаков, а на 15. В колонке из 70 знаков расходятся 65 абзацев, и выигрыш меньше: чем шире колонка, тем больше слов в строке и тем легче жадности.

Идея

Перенос — это выбор мест разрыва между словами. Жадный перенос решает за каждую строку отдельно и не пересматривает решений. Перенос «по всему абзацу» назначает каждой строке цену — чем больше недобор, тем дороже — и ищет набор разрывов с наименьшей суммарной ценой. Места разрыва — вершины графа, возможные строки — рёбра, и лучший набор — кратчайший путь от начала абзаца к концу. Граф ациклический, поэтому путь находится одним проходом слева направо.

Цену берут квадратом недобора, а не самим недобором, и это не прихоть. Если число строк задано, сумма недоборов всех строк, кроме последней, зависит только от длины последней строки: остальное определяют ширина колонки, число строк и длина текста. Такая цена ничего не говорит о ровности. Квадрат наказывает одну пустоту в двенадцать знаков сильнее, чем две по шесть: 144 против 72.

Что умеет жадный перенос

У жадного переноса есть честное достоинство, и его можно доказать.

Это рассуждение «жадный не отстаёт» — тот же приём, что в статье о жадных алгоритмах. А вот о ровности края оно ничего не говорит: жадный набор берёт в каждую строку как можно больше и оставляет всю пустоту там, где следующее слово не влезло.

Граф мест разрыва

Возьмём фразу из вводного абзаца статьи о задержках и колонку в 19 знаков. Места между словами пронумерованы, дуга из i в j — строка из слов между ними, если она помещается.

Жадный перенос идёт по самым длинным дугам: «Сложение двух чисел» заполняет строку целиком, и на «— треть» остаётся недобор 12, цена 144. Лучший путь платит дважды по 36: «Сложение двух / чисел — треть / наносекунды.» — сумма 72. Заодно он не начинает строку с тире: в русском наборе это считается ошибкой, и TeX в таких местах ставит штраф за разрыв.

Пусть cost[j] — наименьшая цена набора первых j слов, если после слова j строка кончается. Тогда

cost[j] = min по i < j из cost[i] + (W − длина строки из слов i + 1..j)²,

где минимум берётся по строкам, которые помещаются в колонку шириной W, а для последней строки квадрат не прибавляется.

Перебирать все i не нужно. Начнём с i = j − 1 и будем двигать начало строки влево: строка только удлиняется, и, как только она перестала помещаться, дальше влево смотреть бессмысленно. На каждое j уходит не больше L шагов, где L — сколько слов помещается в строку. В листинге на 9100 словах каталога в колонке из 35 знаков это 48 399 шагов — около пяти на слово.

Код

Листинг набирает все вводные абзацы каталога жадно и по всему абзацу в колонки из 35 и 70 знаков, сравнивает суммы квадратов и самые короткие строки, а в конце печатает один абзац обоими способами, отмечая недобор каждой строки точками.

Как это сделано в TeX

Дональд Кнут и Майкл Пласс описали алгоритм разбиения абзаца на строки в 1981 году. Он богаче нашей модели в четырёх местах.

• Пробелы тянутся. TeX набирает по ширине, и у каждого пробела есть нормальная ширина, запас растяжения и запас сжатия. Строку можно сжать, а не только растянуть, и ценой служит не недобор, а то, насколько пробелы отклонились от нормы. «Плохость» строки растёт как куб этого отклонения: 100·r³, где r — доля использованного запаса.
• Штрафы. Разрыв можно запретить или удорожить: внутри слова на месте переноса, перед тире, после короткого предлога. Добавляются штрафы за два переноса подряд и за соседство очень плотной строки с очень разреженной.
• Переносы внутри слов. Места переноса в словах дают отдельный алгоритм Фрэнка Лианга 1983 года на образцах; для графа это просто новые вершины со штрафом.
• Отсечение. Строки, которые пришлось бы растянуть или сжать сверх допустимого, вообще не рассматриваются, а из мест разрыва в работе держатся только «активные» — те, от которых ещё можно дотянуться до текущего слова. Поэтому алгоритм на практике работает почти за линейное время.

Неразрывный пробел в этой модели — пробел без вершины: строку в этом месте рвать нельзя. Им склеены, например, разряды числа 1 515 185 802 420 673 в абзаце из листинга. А абзацы этого сайта браузер ещё и переносит по слогам — у текста стоит hyphens: auto, — так что в настоящем наборе вершин больше, чем в нашей модели.

Что умеют браузеры

Обычный перенос в браузерах жадный: страница должна появиться быстро, а набор пересчитывается при каждом изменении ширины окна. Но в 2023 году появились два свойства CSS. text-wrap: balance выравнивает короткие блоки вроде заголовков: по описанию разработчиков Chrome, браузер двоичным поиском ищет самую узкую колонку, при которой строк не становится больше, — это вторая задача статьи. text-wrap: pretty просит набрать абзац получше. Chromium при этом пересматривает только последние четыре строки, чтобы не оставлять в конце одинокое слово, а WebKit в 2025 году начал применять его ко всему абзацу. Вот как это выглядит в вашем браузере:

Сколько это стоит

Жадный перенос — O(n): одно сложение и одно сравнение на слово. Перенос по всему абзацу — O(n·L) времени и O(n) памяти; при L в пределах десятка-двух слов это в несколько раз дороже жадного, но для абзаца в сотню слов — доли миллисекунды. Дорого становится, когда пересчитывать нужно постоянно: при каждом изменении ширины окна, в каждом абзаце длинной страницы. Поэтому браузеры долго ограничивались жадным переносом, а TeX, который набирает книгу один раз, мог позволить себе перебирать.

Если цена строки — выпуклая функция недобора, как квадрат, есть способы быстрее O(n·L): задача сводится к поиску минимумов в матрице с монотонной структурой, и для неё известны линейные алгоритмы. На практике хватает простого перебора с обрывом цикла.

Где работает

Набор книг и статей. TeX и LaTeX разбивают абзацы на строки по Кнуту и Плассу.

Веб. Заголовки с text-wrap: balance и абзацы с text-wrap: pretty — там, где браузер это поддерживает. На этом сайте так набран курс математики: у заголовков карточек balance, у вводных абзацев pretty. Текст этого каталога переносится обычным, жадным способом.

Терминалы, редакторы кода, почтовые программы. Жадный перенос: в моноширинном шрифте и рваном крае выигрыш от перебора невелик, а простота важнее.

История

Кнут начал писать TeX в 1977 году, недовольный тем, как набран второй том его «Искусства программирования». Алгоритм, который смотрит на абзац целиком, он и его аспирант Майкл Пласс описали в 1981 году в статье «Breaking paragraphs into lines». Алгоритм переноса слов по слогам на образцах Фрэнк Лианг, тоже ученик Кнута, описал в диссертации 1983 года. Свойства text-wrap: balance и pretty появились в браузерах в 2023 году.

Задачи

Первая — наименьшая сумма квадратов недобора: тот самый кратчайший путь по местам разрыва. Вторая — что делает браузер с text-wrap: balance: самая узкая колонка, в которой строк не больше.