Алгоритм разрыва строки Кнута-Пласса ⇐ Васина Википедия

[wiki_en]

Алгоритм Кнута-Пласса представляет собой перенос строк и слов|алгоритм разрыва строк, разработанный для использования в наборной программе TeX Дональда Кнута. Он объединяет проблемы выравнивания текста и расстановки переносов в единый алгоритм, используя метод дискретного динамического программирования для минимизации функции потерь, которая пытается описать эстетические качества, желаемые в конечном результате.
Алгоритм работает путем разделения текста на поток трех типов объектов: «коробки», представляющие собой фрагменты контента без изменения размера, «клей», представляющий собой гибкие элементы с изменяемым размером, и «штрафы». , обозначающие места, где взлом нежелателен (или, если отрицательный результат, желателен).

Оригинальный алгоритм Кнута и Пласса не включает разрыв страниц, но может быть изменен для взаимодействия с алгоритмом разрыва страниц.

== Алгоритм ==

Для ввода текста

ААА ББ СС ДДДДД

при ширине линии 6 жадный алгоритм выдаст:

------ Ширина линии: 6
AAA BB Осталось места: 0
CC Осталось места: 4
DDDDD Осталось места: 1

Сумма квадратов пространства, оставшегося в результате этого метода, равна 0^2 + 4^2 + 1^2 = 17. Однако оптимальное решение дает меньшую сумму 3^2 + 1^2 + 1^2 = 11:

------ Ширина линии: 6
AAA Осталось места: 3
BB CC Осталось места: 1
DDDDD Осталось места: 1

Разница здесь в том, что первая строка разрывается перед BB, а не после нее, что дает лучшее правое поле и меньшую стоимость 11.

Используя алгоритм динамического программирования для выбора позиций разрыва строки, вместо жадного выбора разрывов, решение с минимальной неровностью может быть найдено за время O(n^2), где n — количество слов во входном тексте. Обычно функцию стоимости для этого метода следует изменить так, чтобы она не учитывала пространство, оставшееся в последней строке абзаца; эта модификация позволяет абзацу заканчиваться в середине строки без каких-либо штрафов. Также можно применить ту же технику динамического программирования для минимизации более сложных функций стоимости, которые сочетают в себе другие факторы, такие как количество строк или затраты на расстановку переносов в длинных словах. .

* [http://www.eprg.org/G53DOC/pdfs/knuth-p ... eaking.pdf Разбиение абзацев на строки], оригинальная статья Кнута и Пласса