algorithm - 换行算法 : The greedy approach

Question

我需要一个简单的换行算法，所以我求助于维基百科:

http://en.wikipedia.org/wiki/Line_wrap_and_word_wrap#Minimum_number_of_lines

贪心算法:

1. |  SpaceLeft := LineWidth2. |  for each Word in Text3. |      if (Width(Word) + SpaceWidth) > SpaceLeft4. |         insert line break before Word in Text5. |         SpaceLeft := LineWidth - Width(Word)6. |      else7. |         SpaceLeft := SpaceLeft - (Width(Word) + SpaceWidth)

On line #5, when we start a new line and subtract the word width from the available width, shouldn't we also subtract the space width?

5. |         SpaceLeft := LineWidth - (Width(Word) + SpaceWidth)

Why is the space width not accounted for on line #5?

-- UPDATE --

Some simple testing.

In each of the images, the first paragraph is created by JavaScript using the above wrapping algorithm (orange outline), and the second paragraph is native-rendered by the browser (blue outline).

Interestingly, this extremely bare-bones algorithm, indeed produces the exact same results as the browser rendering, for text with NO edge cases.

This first image shows that when we use

SpaceLeft := LineWidth - Width(Word)

JS渲染和浏览器渲染完全一样。

但是下面的图片(不同的线宽)显示了我们使用时JS和浏览器渲染的细微差别:

SpaceLeft := LineWidth - (Width(Word) + SpaceWidth)

代码

// function getWidth() uses canvas to calculate the widths// http://stackoverflow.com/questions/118241/calculate-text-width-with-javascriptvar wrap = function(container, text, lineWidth) {        var words = text.split(' ');        var w, x, i, l;        var spaceWidth = getWidth(' ');        var spaceLeft = lineWidth;        var arr = [], line = [];        arr.push(line);        for ( i = 0, l = words.length; i < l; i++ ) {            w = words[i];            x = getWidth(w) + spaceWidth;            if ( x > spaceLeft ) {                line = [];                arr.push(line);                line.push(w);                // this is the case for Wikipedia algorithm                // spaceLeft = lineWidth - getWidth(w);                spaceLeft = lineWidth - x;            }            else {                spaceLeft = spaceLeft - x;                line.push(w);            }        }        for ( i = 0, l = arr.length; i < l; i++ ) {            container.append(                $('<span>').text(arr[i].join(' '))            );        }    };

Answer 1

如果第 5 行是，算法可能会“更”正确

5. |         SpaceLeft := LineWidth - (Width(Word) + SpaceWidth)

按照你的建议。

无论如何，这个问题有点哲学性，因为该算法对于任何具体实现来说都过于简单，考虑到真正的实现需要注意文本可能已经包含新行的事实，即单词是不一定由空格(例如连字符)和/或多个空格分隔。

使用现有的实现可能是最好的解决方案，例如对于 Java:Wrap the string after a number of characters word-wise in Java