SMAWK アルゴリズムによる行分割法

Knuth 大先生が TeX に利用した行分割アルゴリズムを思い出してみましょう。 まず、 行に分割したい記号列をグルーとボックス (hbox) を交互に並べたリストへと変換します。 続いて、 分割候補となるグルーごとに、 そこで行分割するデメリットを計算します。 そして、 デメリットの積算が最小になる分割位置を探し出します。 この探索は無循環有向グラフの最小経路問題なのですが、 TeX は手堅く古典的な動的計画法で解いています。

TeX は 1970 年代後半の作で、 それから 10 年経た 1980 年後半にこの手の問題の一般化がおこなわれて SMAWK アルゴリズムが発見されました。 SMAWK の名は発見者の A. Aggarwal、 M. M. Klawe、 S. Moran、 P. W. Shor、 R. E. Wilber の頭文字に由来しています。 なお、 基づいている数学を調べるには monge および monotone matrix で検索すれば見つかります。

http://www.egr.unlv.edu/~larmore/Courses/CSC477/monge.pdf

SMAWK アルゴリズムによる行分割の例を探すと、 既に Python のコードがありました。

http://xxyxyz.org/line-breaking/

それを Ruby に翻訳してみます。 行分割したい段落の文字列を str に束縛して、 折り返したいカラム幅と一緒に split_line メソッドを呼ぶと、 入れ子の配列を返します。 単語の配列が一行で、 行の配列を返します。

class LineBreaking
#@<split_line@>
#@<cost>
#@<smawk>

  class Series
    def initialize(a0, a1, d) @first, @second, @step = a0, a1, d end
    def [](i) @first + i * @step end
    def size() (@second - @first + @step - 1) / @step end
    def interace() Series.new(@first + @step, @second, @step * 2) end
  end
end

LineBreaking.new.split_line(str, 72).each {|line| puts line.join(' ') }

split_line メソッドは、 段落の文字列を単語の列に分割します。 今回は 1 文字を 1 カラムとして、 カラム単位で行分割をおこないます。 まず、 段落の先頭からの単語先頭までのカラム数を offsets 配列へ求めておきます。 準備ができたら、 タプル (n、 i、 offset) を更新しつつ、 offsets に対応している単語先頭でのデメリットを minima 配列へ、 行分割箇所の一方向リンク・リストを link_breaks 配列へ作っていきます。 その際、 求めたい配列の先頭から 2 のべき乗ずつ適応範囲を伸ばしながら、 SMAWK アルゴリズムを適応していきます。

#@<split_line@>=
  def split_line(text, width)
    words = text.split
    @offsets = [0]
    words.each_with_index do |w, i|
      @offsets[i + 1] = @offsets[i] + w.size
    end
    @width = width

    @minima = [0] + [10 ** 20] * words.size
    @link_breaks = [0] + [0] * words.size
    n, i, offset = words.size + 1, 0, 0
    while true
      r = [n, 2 ** (i + 1)].min
      edge = 2 ** i + offset
      smawk(Series.new(offset, edge, 1), Series.new(edge, r + offset, 1))
      #smawk((offset ... edge).to_a, (edge ... r + offset).to_a)
      d = @minima[r - 1 + offset]
      k = (2 ** i ... r - 1).find {|j| cost(j + offset, r - 1 + offset) <= d }
      if not k.nil?
        n, i, offset = n - k, 0, offset + k
      elsif r == n
        break
      else
        i = i + 1
      end
    end

    lines = []
    j = words.size
    while j > 0
      i = @link_breaks[j]
      lines.unshift words[i ... j]
      j = i
    end
    lines
  end

デメリットの計算法は Python のコード例そのままにしています。 TeX と異なり、 行中の空白を伸ばさない場合を計算してあり、 右側に残す空白数の二乗をデメリットにしています。

#@<cost>=
  def cost(i, j)
    w = @offsets[j] - @offsets[i] + j - i - 1
    if w > @width
      (10 ** 10) * (w - @width)
    else
      @minima[i] + (@width - w) ** 2
    end
  end

SMAWK アルゴリズムは、 カラム位置と行内位置の配列を受け取り、 まずデメリットが小さくなる可能性の高い行頭の候補になりうるカラム位置を抜き出します。 続いて偶数番目の行内位置 (ruby の配列は添字がゼロから始まるので、 添字が奇数の要素) を抜き出して、 smawk メソッドを再帰呼び出しします。 それが終わったら、 極小のデメリットのある位置を探して行分割位置を記録します。

#@<smawk>=
  def smawk(columns, rows)
    possible = []
    j = 0
    while j < columns.size
      if possible.empty?
        possible << columns[j]
      else
        i = possible.size - 1
        if cost(columns[j], rows[i]) <= cost(possible.last, rows[i])
          possible.pop
          j -= 1
        elsif i + 1 < rows.size
          possible << columns[j]
        end
      end
      j += 1
    end
    if rows.size > 1
      smawk(possible, rows.interace)
      #rows_skiped = [].tap{|r| rows.each_with_index{|x, i| i.odd? and r << x } }
      #smawk(possible, rows_skiped)
    end
    i = j = 0
    while j < rows.size
      col_end = j + 1 < rows.size ? @link_breaks[rows[j + 1]] : possible.last
      demerit = cost(possible[i], rows[j])
      if demerit < @minima[rows[j]]
        @minima[rows[j]] = demerit
        @link_breaks[rows[j]] = possible[i]
      end
      if possible[i] < col_end
        i += 1
      else
        j += 2
      end
    end
  end