Автоматический расчет ширины столбцов

Задача


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

После некоторых раздумий, решено было воспользоваться FOP для генерации PDF. Загвоздка в том, что Apache FOP не поддерживает table-layout:auto, то есть при построении таблицы необходимо вручную задать ширину столбцов (хорошо еще, что можно задать относительную ширину в процентах). Если же сделать все столбцы одинаковой ширины, таблица будет выглядеть несколько неэлегантно. Выходит, рассчитывать ширину придется вручную.

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


Решение


Я решал задачу на С++ с использованием фреймворка Qt, поэтому некоторые отсылки к языку и Qt определенно будут, но в общем-то, я постараюсь избежать кода и описать основную идею решения.

Подготовка данных

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

Кроме того, необходимо знать ширину бумаги, причем выраженную в тех же единицах, что и длина слов.

Я использовал QFontMetrics::width для определения длины слов. Таким образом, длина слов получалась в пикселах. Тогда для того, чтобы определить ширину бумаги в пикселах, достаточно перемножить ее ширину в дюймах на DPI экрана, которое можно получить, воспользовавшись функцией QPaintDevice::logicalDpiX.


Может оказаться, что ширина бумаги недостаточна для того, чтобы вместить таблицу, даже если сжать столбцы настолько, что в каждой строке будет умещаться всего по одному слову.

Вероятность такого варианта развития событий мала (если Вы не немец и не тестировщик, конечно), поэтому я не стал разрабатывать сколько-нибудь сложный алгоритм обработки такого рода случаев. Просто проверим, что минимальная ширина таблицы, которая определяется как сумма максимальных длин слов в столбцах, меньше размера бумаги.

минимальная
ширина
таблицы
определяется
суммой
длин
самых
длинных
слов
в столбцах

Если таблица не влезает, придется обрезать длинные слова. Поскольку, раз уж слово решили обрезать, то обрезать его можно в любом месте, будем считать эффективную длину таких обрезанных слов равной нулю.

Итак, будем обрезать самое длинное слово в таблице до тех пор, пока таблица не станет вмещаться на бумагу.

На этом подготовку данных можно считать законченной, и можно перейти к алгоритму расчета ширины столбцов.

Расчет

В начале статьи я определил основную идею решения. Теперь настало время выразить ее более формально. Фактически, необходимо отобразить таблицу на бумаге таким образом, чтобы как можно сильнее сократить площадь таблицы.
Площадь, занимаемую таблицей, можно определить как сумму площадей ее столбцов:

Здесь и – высота и ширина столбца соответственно.

Конечно, это не совсем верно, но такая модель на практике дает вполне удовлетворительный результат.

Распишем, чему равна высота столбца:

где m – число строк таблицы, lh – высота строки текста, p – некоторый коэффициент, описывающий высоту отступов, wc – число переносов строк.

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

А вот количество переносов строк напрямую зависит от ширины столбца. Таким образом, высоту столбца можно переписать в виде:


А задача сводится к минимизации функции


Да-да, я не ошибся, А и B не будут зависеть от k, поскольку B определяется высотой строки, а A, в добавок, размерами отступов и числом строк.

S можно переписать в виде:


Сейчас я сделаю большую грубость. это идеальная площадь таблицы, когда переносов вообще нет. Но поскольку нас не интересует оптимизация по ширине таблицы, (в итоге все равно растянем таблицу на всю страницу), то заменим , то есть на постоянную. Теперь все просто: для задачи минимизации коэффициенты G и B никакой роли не играют, поэтому их можно благополучно выкинуть и находить минимум функции


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

Вы сказали производная?

На самом деле, функция числа переносов в зависимости от ширины столба не отличается особой гладкостью. Это ступенчатая функция, которая терпит разрывы в точках изменения числа переносов. Выглядит это как-то так:

У такой функции явные проблемы с производными, но мы поступим просто: будем рассматривать не саму функцию, а некоторую монотонно-убывающую функцию, которая в точках изменения числа переносов совпадает с правым пределом изначальной функции.

В качестве начальной точки возьмем точку с наименьшими возможными ширинами столбцов.

Алгоритм

Для каждого столбца:
  • Построим массивы точек, в которых число переносов в данном столбце изменяется – mk.
  • Массивы значений гладкой функции числа переносов в этих точках (гладкую функцию я определил в предыдущем пункте) – wck.

Для того, чтобы сформировать эти массивы, используем подготовленные на первом этапе данные о длине слов в каждой ячейке таблицы.

Дополним массивы (их получилось столько же, сколько и столбцов) начальными точками.

В итоге, для столбца
минимальная
ширина
таблицы

получим следующую структуру данных:
m0
wc0
11
2
13 («ширина» и «таблицы» — на одной строке)
1
24
0

Аналогичные структуры получим и для остальных столбцов.

Теперь запустим итерационный процесс:
Пока сумма ширин столбцов меньше чем ширина страницы:
  • Вычислим изменение функции площади (U) при движении по каждой координате по формуле

    (Это хорошо всем известная формула взятия дифференциала произведения: d(AB) = B dA + A dB)
  • Если в каком-то массиве остался всего один элемент, значит в данном столбце уже нет переносов строк (wck[0] == 0). Такой столбец мы не берем в рассмотрение.
  • Если ни один массив не попал в рассмотрение, во всех столбцах уже отсутствуют переносы строк, заканчиваем вычисления.
  • Увеличиваем ширину k-го столбца, в котором величина dk — наибольшая. Удаляем первые элементы массивов wck и mk для этого столбца.

В заключение, пересчитаем полученные ширины столбцов из абсолютных единиц в проценты. Тем самым, отвяжемся от той метрики шрифта, которую использовали.

Итог


В итоге таблица получается именно такой, какой бы я ее сделал при ручном форматировании.

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

Ну. И что?
Реклама
Комментарии 18
    0
    Если интересно, то в модуле CSS3 Tables предпринята попытка описать алгоритм автоматической раскладки table-layout: auto. Это только набросок черновика, так что он может быть неполным, неточным и т. д., но всё же что-то.
      0
      Прочитал. Честно говоря, я не понял, как предлагается распределять ширину между столбцами с атрибутом width:auto. Написано, вроде бы, только как вычислить минимальную и максимальную ширину.

      К тому же, утверждение
      If possible, widen all spanned columns by approximately the same amount.
      мне кажется подозрительным, потому что в одном столбце может быть много текста, а в другом — мало. Увеличивать их на примерно одну величну нерационально.
      0
      Эх, а я с первых строк понадеялся, что кто-то наконец допишет кусок FOP для таблиц…
        0
        Хм. В свободное время (еще б найти его) можно будет попробовать. Я правда Java не знаю. А вообще есть коммерческие процессоры же. Они вроде бы поддерживают.
        0
        А вы не смотрели алгоритмы верстки таблиц в LaTeX'е, в качестве образца? Там наверняка есть много поучительного, и идеи для верстки в ТеХе исходно стоят на хорошем алгоритмическом/математическом фундаменте.
          0
          Не смотрел. Спасибо за наводку. Сейчас нашел документ, описывающий разметку таблиц text. Как минимум, отличие в том, что там предлагают минимизировать a height(table) + width(table). Но вообще я рассматриваю более частный случай, когда таблица растянута по всей ширине страницы, отсутсвуют объединенные ячейки.
            0
            Сейчас прочитать статью по вашей ссылке не успел, только общую идею с первой страницы. Думаю, это частичные решения, потому что кроме расположения ячеек нужно еще учитывать «плохость» (термин не мой, а Кнута) текста внутри ячеек. Плохость в ТеХе определяется как функция отклонений межсловных интервалов от нормальных (эти значения берут из данных кернинга шрифта), штрафов за переносы и ряд характерных типографических событий типа «нельзя однобуквенный заглавный предлог оставлять в конце строки». Без оптимизации набора внутри ячеек получается то, что вы видите в поликлиниках на стенах, то есть — никуда не годится.
          0
          Мне тут подсказали: а вы не рассматривали простой перебор по всем возможным ширинам столбцов? Если таблица на лист формата А4 или около того, там вариантов то всего ничего, кажется.
            0
            Отчет большой. Таблица может быть и на 50 листов А4.
              0
              Ну если не 50 листов в ширину, а в длину (т.е. таблица шириной А4), то это не сильно увеличивает количество вариантов для перебора. Какая-нибудь стандартная таблица из 5 столбцов. 11 шрифтом у меня сейчас в вордпаде влезает 11 слов «привет» в строчку. Есть слова длиннее, есть короче. Для первого столбца есть около 7 вариантов длин (11 — 4). Для второго тоже, для третьего и четвертого тоже. Ширина пятого столбца и так понятна, если заданы все другие. Итого 7^4 = 2401 вариантов. Если шрифт мелкий и слова мелкие, то все равно это будет, пусть даже 20^4 вариантов. Если больше столбцов, то это увеличивает показатель степени, но уменьшает число, которое возводим. Плюс можно исключать варианты типа: первые два столбца шириной 7 т.к. это будет уже шире, чем лист, а нужно еще минимум 3 слова впихнуть. Это существенно сократит перебор, на случай, если таблицы нужно строить с 60 фпс :-) Конечно, каждую новую итерацию придется вычислять количество переносов в каждом столбце, но т.к. для каждого столбца есть только несколько вариантов, то и это самое количество переносов можно посчитать один раз вначале всего алгоритма и занести в массив, отдельный для каждого столбца (типа «кэшировать»).
                0
                Хотя, наверное, туплю :-) Надо еще подумать над перебором
                  +1
                  В разных строках же разный текст, поэтому в общем случае получается, что для каждой ячейки могут быть свои градации. Не забывайте еще, что в примере я считал размер буквы равным единице, а в реальной жизни размер слова высчитывается с использованием метрики шрифта.
                    0
                    Да, да согласен!
              0
              Все гораздо проще на самом деле.

              Таблицы используют механизм сходный с flex layout
              В той статье приведена моя имплеменация т.н. spring engine (Физическая инерпретация процесса — связанная системы пружин с ограничителями. )
              www.terrainformatica.com/w3/flex-layout/spring-engine.h

              Там два основных метода

              spring::engine::add(int valmin, int valmax, int weight)
              и
              spring::engine::calc(int total_space)

              Для каждого столбца таблицы зовем add c
              valmin — минимальная ширина колонки без overflow.
              valmax — или MAXINT или max-width если устанвленно.
              weight — для флексов — flex units value, для таблиц либо процент если есть, либо привденный к процентам max-content width.

              (max-content width это минимальная ширина блока в которм все параграфы в одну строку)

              после вызова calc() с требуемой шириной таблицы получаем расситанные ширины столбцов.
              Алгоритм финитный с хорошей сходимостью — макс. количество итераций N*N (где N это количество столбцов), но на практике просто N или 2N.
                0
                Можно делать и так. Собственно, с чего-то похожего я и начинал.

                Основная проблема в том, чтобы правильно вычислить «жесткость пружинки». Если, как вы предлагаете, использовать в качестве жесткости максимальную ширину столбца, то у Вас размерность не сходится. столбец, состоящий в среднем из 2х коротких слов, но в одной строке содержащий 10 длинных, будет растянут гораздо больше, чем следовало.

                Я пробовал вычислить коэффициент жесткости на основе функции числа переносов, но она все-таки обладает сильной нелинейностью и при линеаризации точность заметно теряется. Возможно, можно придумать метод вычисления коэффициента, который даст хороший результат, но его ведь еще нужно обосновать. Я решил, что проще не линеаризовывать.

                Кстати, алгоритм не такой уж и сложный. Реализация занимает у меня строк 200-300 кода.
                  0
                  Я не слышал ни разу что использование числа переносов в качестве метрики кем-то используется вообще. Перенос в тексте это настолько language specific feature что закладываться на нея в алгоритмах таблиц это путь в никуда.

                  Данный spring::engine используется для рассчета HTML таблиц в моих движках HTMLayout и Sciter. Он воспроизводит auto layout HTML таблиц достаточно точно насколько это вообще возможно ибо у всех browsing движков (trident, gecko и webkit) несколько разные базовые алгоритмы).

                  Извиняюсь, но я не понял фразу «столбец, состоящий в среднем из 2х коротких слов, но в одной строке содержащий 10 длинных, будет растянут гораздо больше, чем следовало.» «10 длинных» чего?

                  Во всяком случае все HTML движки согласны что вот эти две колонки имеют ширины 2:1

                  <table width="100%" border=1> <tr> <td>123456789012345 6789</td> <td>12345 1234</td> </tr> </table>
                    0
                    Возможно браузеры и используют такой алгоритм, но на тех данных, про которые я говорил выше, они косячат. Вот пример

                    P.S. Куда постить html, чтобы было видно сразу и код и результат? Точно что-то было, но сейчас не могу найти.
                      0
                      Я не слышал ни разу что использование числа переносов в качестве метрики кем-то используется вообще


                      Возможно, вы имели ввиду верстку только таблиц, но в ТеХе именно число переносов (взвешенное, суммированное со штрафами за другие типографические события) является метрикой, которую оптимизируют во время верстки текста. Не возьмусь утверждать, что в ТеХе таблицы расчитываются ровно так же (давно не заглядывал в TeXbook).

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

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