\tracingparagraphs

\tracingparagraphsが1以上の時，TeXが行分割をしている状況が出力される．見方はTeXbookにあるのだけど，ちょいとメモ．あっているかは知らない．

とりあえずTeXが行分割位置を決めている方法．黒木さんの記事もある．（原論文もあるのだが，読めていない．）段落に対して，次のような重み付き有向グラフ$(V,E)$を考える．

• $V$は改行可能位置全体のなす集合．特別な元として，行頭$s$と行末$e$を持つ．
• $i,j\in V$で，$j$が$i$よりも後ろにあるときに，デメリット$d = d(i,j)\in\mathbb{Z}$が定義される*1．これは次から算出される．（細かい計算式は略．）大事なのは$b$と$p$．
  • \linepenaltyの値$l$
  • $i$と$j$で行分割した時の，その行の評価値$b$．グルーが伸び縮みされると大きくなる．
  • $j$におけるペナルティ$p$．
  • \adjdemerits，\doublehyphendemerits，\finalhyphendemerts．
  • $j = e$の時はさらに特殊な処理が入る．
• $i,j\in V$にたいして，次を満たすときに$i$から$j$へと矢印を引く．
  • $j$は$i$よりも真に後ろにある．
  • $d(i,j)$が\toleranceより小さい．
  また重みとして$d(i,j)$をこの矢印にのせる．

基本的にはこのグラフと頂点$s,e$に対する最短経路問題を解けばよい．（実際には単純な重み付きグラフではないが．なお，定義からこのグラフは閉路を含まない．）\tracingparagraphsが1以上の時このグラフの情報が出力される．なお，単純に$V$の元を列挙すると膨大な数になるが，（矢印を引くための条件の二つ目により）$s$から到達可能な分割可能位置はほとんどなく，実際に意味のある$V$の元は少ない．ログに出力されるのも意味のある分割位置のみである．

TeXはこれを動的計画法で解く．\tracingparagraphsが1以上の時，ログには次のように出力される．

（ソースファイルにある入力の一部：分割位置を示す）
@ via <直前の分割位置その1> b=<評価値> p=<ペナルティ> d=<デメリット>
…
@ via <直前の分割位置そのn> b=<評価値> p=<ペナルティ> d=<デメリット>
@@<この改行位置の番号> t=<ここまでのデメリットの合計> -> @@<直前改行位置>

TeXbookにある例は

\hsize=2.5in
\tolerance=1000
\tracingparagraphs=1
Mr.~Drofnats---or ``R. J.,'' as he preferred to be called---was happiest when he was at work typesetting beautiful documents.
\bye

で，行分割の情報は（%から始まる部分は自分で加えたもの）こんな感じ．

[]\tenrm Mr. Drofnats---or ``R. J.,'' as he pre-
% preferred内preとferredの間で分割した時の情報．
@\discretionary via @@0 b=0 p=50 d=2600 %d(0,1) = 2600
% この分割位置は1番目なので，この行は@@1から始まる．
@@1: line 1.2- t=2600 -> @@0
ferred to be called---was hap-pi-est when 
@ via @@1 b=131 p=0 d=29881 % d(1,2) = 29881
@@2: line 2.0 t=32481 -> @@1
he 
@ via @@1 b=25 p=0 d=1225 % d(1,3) = 1225
@@3: line 2.3 t=3825 -> @@1
was at work type-set-ting beau-ti-ful doc-
% この分割位置（4番目）は2番目からと3番目からの可能性がある
@\discretionary via @@2 b=1 p=50 d=12621 % d(2,4) = 12621
@\discretionary via @@3 b=291 p=50 d=103101 % d(3,4) = 103101
% 選ばれたのは2番目から（こちらからの方がデメリットの総和が小さい）
@@4: line 3.2- t=45102 -> @@2
u-
@\discretionary via @@3 b=44 p=50 d=15416 % d(3,5) = 15416
@@5: line 3.1- t=19241 -> @@3
ments. 
% 段落終了位置．ここも二カ所からの可能性がある．
@\par via @@4 b=0 p=-10000 d=5100 % d(4,6) = 5100
@\par via @@5 b=0 p=-10000 d=5100 % d(5,6) = 5100
@@6: line 4.2- t=24341 -> @@5

*1

\adjdemeritsなどの存在により，これは$(i,j)$の関数ではなくなる．なので，実は重み付きグラフではない．