\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
より小さい.
基本的にはこのグラフと頂点$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)$の関数ではなくなる.なので,実は重み付きグラフではない.
0 件のコメント:
コメントを投稿
コメントの追加にはサードパーティーCookieの許可が必要です