diff options
Diffstat (limited to 'devdoc/dw-line-breaking.doc')
| -rw-r--r-- | devdoc/dw-line-breaking.doc | 470 |
1 files changed, 470 insertions, 0 deletions
diff --git a/devdoc/dw-line-breaking.doc b/devdoc/dw-line-breaking.doc new file mode 100644 index 00000000..14ab97c4 --- /dev/null +++ b/devdoc/dw-line-breaking.doc @@ -0,0 +1,470 @@ +/** \page dw-line-breaking Changes in Line-Breaking and Hyphenation + +<div style="border: 2px solid #ffff00; margin-bottom: 0.5em; +padding: 0.5em 1em; background-color: #ffffe0"><b>Info:</b> +Should be incorporated into dw::Textblock.</div> + +Introduction +============ + +For the implementation of hyphenation in dillo, not only a +hyphenation algorithm was implemented, but also, the line breaking was +changed to a simple optimization per line. Aside from the improvement +by this change per se, an important aspect is the introduction of +"penalties". Before this change, dillo put all words into a line which +fitted into it; now, a "badness" is calculated for a possible +breakpoint, and the best breakpoint, i. e. the breakpoint with the +smallest value for "badness", is chosen. This can be simply refined +to define "good" and "bad" breakpoints by assigning a "penalty"; the +best breakpoint is then the one with the smallest value of "badness + +penalty". Details can be found below. + +Example: Normal spaces have a penalty of 0, while hyphenation points +get a penalty of, say, 1, since hyphenation is generally considered as +a bit "ugly" and should rather be avoided. Consider a situation where +the word "dillo" could be hyphenated, with the following badnesses: + +- before "dillo": 0.6; +- between "dil-" and "lo": 0.2; +- after "dillo": 0.5. + +Since the penalty is added, the last value is the best one, so "dillo" +is put at the end of the line, without hyphenation. + +Under other circumstances (e. g. narrower lines), the values +might be different: + +- before "dillo": infinite; +- between "dil-" and "lo": 0.3; +- after "dillo": 1.5. + +In this case, even the addition of the penalty makes hyphenation the +best choice. + + +Literature +========== + +Breaking Paragraphs Into Lines +------------------------------ + +Although dillo does not (yet?) implement the algorithm T<sub>E</sub>X +uses for line breaking, this document shares much of the notation used +by the article *Breaking Paragraphs Into Lines* by Donald E. Knuth and +Michael F. Plass; originally published in: Software -- Practice and +Experience **11** (1981), 1119-1184; reprinted in: *Digital +Typography* by Donalt E. Knuth, CSLI Publications 1999. Anyway an +interesting reading. + +Hyphenation +----------- + +Dillo uses the algorithm by Frank Liang, which is described in his +doctoral dissertation found at http://www.tug.org/docs/liang/. There +is also a description in chapter H ("Hyphenation") of *The +T<sub>E</sub>Xbook* by Donald E. Knuth, Addison-Wesley 1984. + +Pattern files can be found at +http://www.ctan.org/tex-archive/language/hyphenation. + + +Overview of Changes +=================== + +Starting with this change, dw/textblock.cc has been split up; anything +related to line breaking has been moved into +dw/textblock_linebreaking.cc. This will also be done for other aspects +like floats. (Better, however, would be a clean logical split.) + +An important change relates to the way that lines are added: before, +dillo would add a line as soon as a new word for this line was +added. Now, a line is added not before the *last* word of this line is +known. This has two important implications: + +- Some values in dw::Textblock::Line, which represented values + accumulated within the line, could be removed, since now, these + values can be calculated simply in a loop. +- On the other hand, this means that some words may not belong to any + line. For this reason, in some cases (e. g. in + dw::Textblock::sizeRequestImpl) dw::Textblock::showMissingLines is + called, which creates temporary lines, which must, under other + circumstances, be removed again by + dw::Textblock::removeTemporaryLines, since they have been created + based on limited information, and so possibly in a wrong way. (See + below for details.) + +When a word can be hyphenated, an instance of dw::Textblock::Word is +used for each part. Notice that soft hyphens are evaluated +immediately, but automatic hyphenation is done in a lazy way (details +below), so the number of instances may change. There are some new +attributes: only when dw::Textblock::Word::canBeHyphenated is set to +*true*, automatic hyphenation is allowed; it is set to false when soft +hyphens are used for a word, and (of course) by the automatic +hyphenation itself. Furthermore, dw::Textblock::Word::hyphenWidth +(more details in the comment there) has to be included when +calculating line widths. + +Some values should be configurable: dw::Textblock::HYPHEN_BREAK, the +penalty for hyphens. Also dw::Textblock::Word::stretchability, +dw::Textblock::Word::shrinkability, which are both set in +dw::Textblock::addSpace. + + +Criteria for Line-Breaking +========================== + +Before these changes to line breaking, a word (represented by +dw::Textblock::Word) had the following attributes related to +line-breaking: + +- the width of the word itself, represented by + dw::Textblock::Word::size; +- the width of the space following the word, represented by + dw::Textblock::Word::origSpace. + +In a more mathematical notation, the \f$i\f$th word has a width +\f$w_i\f$ and a space \f$s_i\f$. + +A break was possible, when there was a space between the two words, +and the first possible break was chosen. + +With hyphenation, the criteria are refined. Hyphenation should only be +used when otherwise line breaking results in very large spaces. We +define: + +- the badness \f$\beta\f$ of a line, which is greater the more the + spaces between the words differ from the ideal space; +- a penalty \f$p\f$ for any possible break point. + +The goal is to find those break points, where \f$\beta + p\f$ is +minimal. + +Examples for the penalty \f$p\f$: + +- 0 for normal line breaks (between words); +- \f$\infty\f$ to prevent a line break at all costs; +- \f$-\infty\f$ to force a line +- a positive, but finite, value for hyphenation points. + +So we need the following values: + +- \f$w_i\f$ (the width of the word \f$i\f$ itself); +- \f$s_i\f$ (the width of the space following the word \f$i\f$); +- the stretchability \f$y_i\f$, a value denoting how much the space + after word\f$i\f$ can be stretched (typically \f${1\over 2} s_i\f$ + for justified text; otherwise 0, since the spaces are not + stretched); +- the shrinkability \f$y_i\f$, a value denoting how much the space + after word\f$i\f$ can be shrunken (typically \f${1\over 3} s_i\f$ + for justified text; otherwise 0, since the spaces are not shrinked); +- the penalty \f$p_i\f$, if the line is broken after word \f$i\f$; +- a width \f$h_i\f$, which is added, when the line is broken after + word \f$i\f$. + +\f$h_i\f$ is the width of the hyphen, if the word \f$i\f$ is a part of +the hyphenated word (except the last part); otherwise 0. + +Let \f$l\f$ be the (ideal) width (length) of the line, which is +e. at the top given by the browser window width. Furthermore, all words +from \f$a\f$ to \f$b\f$ are added to the line. \f$a\f$ is fixed: we do +not modify the previous lines anymore; but our task is to find a +suitable \f$b\f$. + +We define: + +\f[W_a^b = \sum_{i=a}^{b} w_i + \sum_{i=a}^{b-1} s_i + h_b\f] + +\f[Y_a^b = {Y_0}_a^b + \sum_{i=a}^{b-1} y_i\f] + +\f[Z_a^b = {Z_0}_a^b + \sum_{i=a}^{b-1} z_i\f] + + +\f$W_a^b\f$ is the total width, \f$Y_a^b\f$ the total stretchability, +and \f$Z_a^b\f$ the total shrinkability. \f${Y_0}_a^b\f$ and +\f${Z_0}_a^b\f$ are the stretchability and shrinkability defined per +line, and applied at the borders; they are 0 for justified text, but +\f${Y_0}_a^b\f$ has a positive value otherwise, see below for details. + +Furthermore the *adjustment ratio* \f$r_a^b\f$: + +- in the ideal case that \f$W_a^b = l\f$: \f$r_a^b = 0\f$; +- if \f$W_a^b < l\f$: \f$r_a^b = (l - W_a^b) / Y_a^b\f$ + (\f$r_a^b < 0\f$ in this case); +- if \f$W_a^b > l\f$: \f$r_a^b = (l - W_a^b) / Z_a^b\f$ + (\f$r_a^b < 0\f$ in this case). + +The badness \f$\beta_a^b\f$ is defined as follows: + +- if \f$r_a^b\f$ is undefined or \f$r_a^b < -1\f$: \f$\beta_a^b = \infty\f$; +- otherwise: \f$\beta_a^b = |r_a^b|^3\f$ + +The goal is to find the value of \f$b\f$ where \f$\beta_a^b + p_b\f$ +is minimal. (\f$a\f$ is given, since we do not modify the previous +lines.) + +After a couple of words, it is not predictable whether this minimum +has already been reached. There are two cases where this is possible +for a given \f$b'\f$: + +- \f$\beta_{b'}^a = \infty\f$ (line gets too tight): + \f$a \le b < b'\f$, the minimum has to be searched between these two + values; +- \f$p_{b'} = -\infty\f$ (forced line break): + \f$a \le b \le b'\f$ (there may be another minimum of + \f$\beta_a^b\f$ before; note the \f$\le\f$ instead of \f$<\f$). + +This leads to a problem that the last words of a text block are not +displayed this way, since they do not fulfill these rules for being +added to a line. For this reason, there are "temporary" lines already +described above. + +(Note that the actual calculation differs from this description, since +integer arithmetic is used for performance, which make the actual +code more complicated. See dw::Textblock::BadnessAndPenalty for +details.) + +Ragged Borders +-------------- + +For other than justified text (left-, right-aligned and centered), the +spaces between the words are not shrinked or stretched (so \f$y_i\f$ +and \f$z_i\f$ are 0), but additional space is added to the left or +right border or to both. For this reason, an additional stretchability +\f${Y_0}_a^b\f$ is added (see definition above). Since this space at +the border is 0 in an ideal case (\f$W_a^b = l\f$), it cannot be +shrunken, so \f${Z_0}_a^b\f$ is 0. + +This is not equivalent to the calculation of the total stretchability +as done for justified text, since in this case, the stretchability +depends on the number of words: consider the typical case that all +spaces and stretchabilities are equal (\f$y_a = y_{a + 1} = \ldots = +y_b\f$). With \f$n\f$ words, the total strechability would be \f$n +\cdot y_a\f$, so increase with an increasing number of words +(\f$y_a\f$ is constant). This is correct for justified text, but for +other alignments, where only one space (or two, for centered text) is +changed, this would mean that a line with many narrow words is more +stretchable than a line with few wide words. + +It is obvious that left-aligned text can be handled in the same way as +right-aligned text. [... Centered text? ...] + +The default value for the stretchability is the line height without +the space between the lines (more precisely: the maximum of all word +heights). The exact value not so important when comparing different +possible values for the badness \f$\beta_a^b\f$, when \f${Y_0}_a^b\f$ +is nearly constant for different \f$b\f$ (which is the case for the +actual value), but it is important for the comparison with penalties, +which are constant. To be considered is also that for non-justified +text, hyphenation is differently (less) desirable; this effect can be +achieved by enlarging the stretchability, which will lead to a smaller +badness, and so make hyphenation less likely. The user can configure +the stretchability by changing the preference value +*stretchability_factor* (default: 1.0). + +(Comparison to T<sub>E</sub>X: Knuth and Plass describe a method for +ragged borders, which is effectively the same as described here (Knuth +1999, pp. 93--94). The value for the stretchability of the line +is slightly less, 1 em (ibid., see also p. 72 for the +definition of the units). However, this article suggests a value for +the hyphenation penalty, which is ten times larger than the value for +justified text; this would suggest a larger value for +*stretchability_factor*.) + + +Hyphens +======= + +Words (instances of dw::Textblock::Word), which are actually part of a +hyphenated word, are always drawn as a whole, not seperately. This +way, the underlying platform is able to apply kerning, ligatures, etc. + +Calculating the width of such words causes some problems, since it is +not required that the width of text "AB" is identical to the width of +"A" plus the width of "B", just for the reasons mentioned above. It +gets even a bit more complicated, since it is required that a word +part (instance of dw::Textblock::Word) has always the same length, +independent of whether hyphenation is applied or not. Furthermore, the +hyphen length is fixed for a word; for practical reasons, it is always +the width of a hyphen, in the given font. + +For calculating the widths, consider a word of four syllables: +A-B-C-D. There are 3 hyphenation points, and so 2<sup>3</sup> = 8 +possible ways of hyphenation: ABCD, ABC-D, AB-CD, AB-C-D, A-BCD, +A-BC-D, A-B-CD, A-B-C-D. (Some of them, like the last one, are only +probable for very narrow lines.) + +Let w(A), w(B), w(C), w(D) be the word widths (part of +dw::Textblock::Word::size), which have to be calculated, and l be a +shorthand for dw::core::Platform::textWidth. Without considering +this problem, the calculation would be simple: w(A) = l(A) +etc. However, it gets a bit more complicated. Since all +non-hyphenations are drawn as a whole, the following conditions can be +concluded: + +- from drawing "ABCD" (not hyphenated at all): w(A) + w(B) + w(C) + + w(D) = l(ABCD); +- from drawing "BCD", when hyphenated as "A-BCD" ("A-" is not + considered here): w(B) + w(C) + w(D) = l(BCD); +- likewise, from drawing "CD" (cases "AB-CD" and "A-B-CD"): w(C) + + w(D) = l(CD); +- finally, for the cases "ABC-D", "AB-C-D", "A-BC-D", and "A-B-C-D": + w(D) = l(D). + +So, the calculation is simple: + +- w(D) = l(D) +- w(C) = l(CD) - w(D) +- w(B) = l(BCD) - (w(C) + w(D)) +- w(A) = l(ABCD) - (w(B) + w(C) + w(D)) + +For calculation the hyphen widths, the exact conditions would be +over-determined, even when the possibility for individual hyphen +widths (instead of simply the text width of a hyphen character) would +be used. However, a simple approach of fixed hyphen widths will have +near-perfect results, so this is kept simple. + + +Automatic Hyphenation +===================== + +When soft hyphens are used, words are immediately divided into +different parts, and so different instances of +dw::Textblock::Word. Automatic hyphenation (using Liang's algorithm) +is, however, not applied always, but only when possibly needed, after +calculating a line without hyphenation: + +- When the line is tight, the last word of the line is hyphenated; + possibly this will result in a line with less parts of this word, + and so a less tight line. +- When the line is loose, and there is another word (for the next + line) available, this word is hyphenated; possibly, some parts of + this word are taken into this line, making it less loose. + +After this, the line is re-calculated. + +A problem arrises when the textblock is rewrapped, e. g. when the +user changes the window width. In this case, some new instances of +dw::Textblock::Word must be inserted into the word list, +dw::Textblock::words. This word list is implemented as an array, which +is dynamically increased; a simple approach would involve moving all +of the <i>n</i> elements after position <i>i</i>, so +<i>n</i> - <i>i</i> steps are necessary. This would not be a +problem, since O(n) steps are necessary; however, this will be +necessary again for the next hyphenated word (at the end of a +following line), and so on, so that +(<i>n</i> - <i>i</i><sub>1</sub>) + +(<i>n</i> - <i>i</i><sub>2</sub>) + ..., with +<i>i</i><sub>1</sub> < <i>i</i><sub>2</sub> < ..., +which results in O(n<sup>2</sup>) steps. For this reason, the word +list is managed by the class lout::misc::NotSoSimpleVector, which uses +a trick (a second array) to deal with exactly this problem. See there +for more details. + + +Tests +===== + +There are test HTML files in the <i>test</i> directory. Also, there is +a program testing automatic hyphenation, <i>test/liang</i>, which can +be easily extended. + + +Bugs and Things Needing Improvement +=================================== + +High Priority +------------- + +None. + +Medium Priority +--------------- + +None. + +Low Priority +------------ + +**Mark the end of a paragraph:** Should dw::core::Content::BREAK still +be used? Currently, this is redundant to +dw::Textblock::BadnessAndPenalty. + +Solved (Must Be Documented) +--------------------------- + +These have been solved recently and should be documented above. + +*Bugs in hyphenation:* There seem to be problems when breaking words +containing hyphens already. Example: "Abtei-Stadt", which is divided +into "Abtei-" and "Stadt", resulting possibly in +"Abtei-<span></span>-[new line]Stadt". See also below under +"Medium Priority", on how to deal with hyphens and dashes. + +**Solution:** See next. + +*Break hyphens and dashes:* The following rules seem to be relevant: + +- In English, an em-dash is used with no spaces around. Breaking + before and after the dash should be possible, perhaps with a + penalty > 0. (In German, an en-dash (Halbgeviert) with spaces around + is used instead.) +- After a hyphen, which is part of a compound word, a break should be + possible. As described above ("Abtei-Stadt"), this collides with + hyphenation. + +Where to implement? In the same dynamic, lazy way like hyphenation? As +part of hyphenation? + +Notice that Liang's algorithm may behave different regarding hyphens: +"Abtei-Stadt" is (using the patterns from CTAN) divided into "Abtei-" +and "Stadt", but "Nordrhein-Westfalen" is divided into "Nord", +"rhein-West", "fa", "len": the part containing the hyphen +("rhein-West") is untouched. (Sorry for the German words; if you have +got English examples, send them me.) + +**Solution for both:** This has been implemented in +dw::Textblock::addText, in a similar way to soft hyphens. Liang's +algorithm now only operates on the parts: "Abtei" and "Stadt"; +"Nordrhein" and "Westfalen". + +*Hyphens in adjacent lines:* It should be simple to assign a larger +penalty for hyphens, when the line before is already hyphenated. This +way, hyphens in adjacent lines are penalized further. + +**Solved:** There are always two penalties. Must be documented in +detail. + +*Incorrect calculation of extremes:* The minimal width of a text block +(as part of the width extremes, which are mainly used for tables) is +defined by everything between two possible breaks. A possible break +may also be a hyphenation point; however, hyphenation points are +calculated in a lazy way, when the lines are broken, and not when +extremes are calculated. So, it is a matter of chance whether the +calculation of the minimal width will take the two parts "dil-" and +"lo" into account (when "dillo" has already been hyphenated), or only +one part, "dillo" (when "dillo" has not yet been hyphenated), +resulting possibly in a different value for the minimal width. + +Possible strategies to deal with this problem: + +- Ignore. The implications should be minimal. +- Any solution will make it neccessary to hyphenate at least some + words when calculating extremes. Since the minimal widths of all + words are used to calculate the minimal width of the text block, the + simplest approach will hyphenate all words. This would, of course, + eliminate the performance gains of the current lazy approach. +- The latter approach could be optimized in some ways. Examples: (i) + If a word is already narrower than the current accumulated value for + the minimal width, it makes no sense to hyphenate it. (ii) In other + cases, heuristics may be used to estimate the number of syllables, + the width of the widest of them etc. + +**Solved:** Hyphenated parts of a word are not considered anymore for +width extremes, but only whole words. This is also one reason for the +introduction of the paragraphs list. + +**Also:** + +- Configuration of penalties. + +*/ |