Ruby を使って grapheme cluster 単位で文字列を切り詰めたい

tl;dr

• 最近の Ruby を使えば、実装自体は難しくないと思われる
• 実行時間上の性能問題を抱えた実装しか思いつかない…

はじめに

Active Support には、文字列を切り詰めるメソッドとして String#truncate があります。似たようなメソッドとして、切り詰める際の長さをバイト数で指定する String#truncate_bytes もあります(master ブランチ)。

String#truncate_bytes は、切り詰める際に grapheme cluster を分解しない様に処理してくれますが、 String#truncate はコードポイント単位で処理するため grapheme cluster が含まれる場合に期待した結果を得られない可能性があります。

$ ruby -v
ruby 2.6.1p33 (2019-01-30 revision 66950) [x86_64-linux]

# frozen_string_literal: true

source "https://rubygems.org"

git_source(:github) {|repo_name| "https://github.com/#{repo_name}" }

# gem "rails"
gem 'activesupport', github: 'rails/rails', ref: '8d06c108c7af1e9a5db9f6d3c79fc5584cc3784e'
# gem 'activesupport', '5.2.2'
gem 'rspec'

>> str = "か\u3099き\u3099く\u3099け\u3099こ\u3099"
=> "がぎぐげご"
>> str.truncate(1, omission: '')
=> "か"
>> str.truncate(2, omission: '')
=> "が"
>> str.truncate_bytes(6, omission: '')
=> "が"
>> str.truncate_bytes(7, omission: '')
=> "が"

切り詰める際の長さをバイト数で指定すれば良いという場合は String#truncate_bytes (相当の実装)を使えば良いのですが、あくまで「見た目上の文字」の長さで指定したい場合は困ってしまうわけです。

Ruby と grapheme cluster

Ruby 2.5.0 以降では String#grapheme_clusters や String#each_grapheme_cluster といった grapheme cluster を扱うメソッドが用意されています。

$ irb
>> str = "か\u3099き\u3099く\u3099け\u3099こ\u3099"
=> "がぎぐげご"
>> str.grapheme_clusters
=> ["が", "ぎ", "ぐ", "げ", "ご"]

また、 String#slice と正規表現を利用することで、 grapheme cluster 単位でスライスすることもできます。

$ irb
>> str[/\X{2}/]
=> "がぎ"

これらを利用し、コードポイント単位ではなく grapheme cluster 単位での文字列処理を実装することを考えます。

grapheme cluster 単位で文字列を切り詰める

String#truncate を参考に、適当な実装を考えます。

# truncate_graphemes.rb
class String
  def truncate_graphemes(truncate_at, options = {})
    return dup unless each_grapheme_cluster.size > truncate_at

    omission = options[:omission] || "..."
    length_with_room_for_omission = truncate_at - omission.each_grapheme_cluster.size
    truncated = slice(/\X{,#{length_with_room_for_omission}}/)

    if options[:separator] && cut_at = truncated.rindex(options[:separator])
      truncated = truncated[0, cut_at]
    end

    "#{truncated}#{omission}"
  end
end

# truncate_graphemes_spec.rb
require_relative './truncate_graphemes'

RSpec.describe String do
  describe '#truncate_graphemes' do
    context 'omission 未指定(default)' do
      context '切り詰め位置が切り詰め対象文字列の長さ(書記素クラスタ単位)未満' do
        context '切り詰め位置が omission (...) の長さ(書記素クラスタ単位)以下' do
          it 'omission だけを返す' do
            # ààààà
            original = "\u{0061 0300 0061 0300 0061 0300 0061 0300 0061 0300}"
            expect(original.truncate_graphemes(-1)).to eq '...'
            expect(original.truncate_graphemes(0)).to eq '...'
            expect(original.truncate_graphemes(3)).to eq '...'
          end
        end

        context '切り詰め位置が omission (...) の長さ(書記素クラスタ単位)より大きい' do
          it '書記素クラスタ単位で切り詰めた結果に omission を付与する' do
            # ààààà
            original = "\u{0061 0300}" * 5
            expect(original.truncate_graphemes(4)).to eq "\u{0061 0300}..."
          end
        end
      end

      context '切り詰め位置が切り詰め対象文字列の長さ(書記素クラスタ単位)以上' do
        it '切り詰めない' do
          # ààààà
          original = "\u{0061 0300}" * 5
          expect(original.truncate_graphemes(5)).to eq original
          expect(original.truncate_graphemes(6)).to eq original
        end
      end
    end

    context 'omission に書記素クラスタを含む' do
      it 'omission の長さも書記素クラスタ単位で数えた上で切り詰めを行う' do
        # ààààà
        original = "\u{0061 0300}" * 5
        # è
        omission = "\u{0065 0300}"
        expect(original.truncate_graphemes(3, omission: omission)).to eq "\u{0061 0300 0061 0300 0065 0300}"
      end
    end

    context 'separator 指定あり(書記素クラスタを含む)' do
      context '切り詰め対象文字列が separator を含む' do
        context '切り詰め位置が separator である' do
          it 'その位置で切り詰める' do
            # è
            separator = "\u{0065 0300}"
            # àààèàààèààà
            original = Array.new(3, "\u{0061 0300}" * 3).join(separator)

            truncated = original.truncate_graphemes(8, separator: separator, omission: '')
            expect(truncated).to eq "\u{0061 0300 0061 0300 0061 0300 0065 0300 0061 0300 0061 0300 0061 0300}"
          end
        end

        context '切り詰め位置が separator でない' do
          it '一つ前の separator 直前で切り詰める' do
            # è
            separator = "\u{0065 0300}"
            # àààèàààèààà
            original = Array.new(3, "\u{0061 0300}" * 3).join(separator)

            truncated = original.truncate_graphemes(7, separator: separator, omission: '')
            expect(truncated).to eq "\u{0061 0300 0061 0300 0061 0300}"
          end
        end
      end

      context '切り詰め対象文字が separator を含まない' do
        it '切り詰める' do
          # ààààà
          original = "\u{0061 0300}" * 5
          # è
          separator = "\u{0065 0300}"

          truncated = original.truncate_graphemes(3, separator: separator, omission: '')
          expect(truncated).to eq "\u{0061 0300 0061 0300 0061 0300}"
        end
      end
    end
  end
end

問題

grapheme cluster 単位で文字列を切り詰める、という目的は上記の様な実装で達成することができると思います。一方で、実行時間について制約がある場合、この様な実装では問題となります。

以下のとおり、 String#truncate と比較して String#truncate_graphemes は 300 倍ほど時間がかかってしまいます。

require 'benchmark'
require 'active_support'
require 'active_support/core_ext'
require_relative 'truncate_graphemes'

N = 1_000
S = 'がぎぐげご' * 1_000
G = "か\u3099き\u3099く\u3099け\u3099こ\u3099" * 1_000

Benchmark.bm(40) do |x|
  x.report('S.truncate(500, omission: "")') do
    N.times { S.truncate(500, omission: "") }
  end

  x.report('G.truncate(500, omission: "")') do
    N.times { G.truncate(500, omission: "") }
  end

  x.report('S.truncate_bytes(1500, omission: "")') do
    N.times { S.truncate_bytes(500, omission: "") }
  end

  x.report('G.truncate_bytes(1500, omission: "")') do
    N.times { G.truncate_bytes(500, omission: "") }
  end

  x.report('S.truncate_graphemes(500, omission: "")') do
    N.times { S.truncate_graphemes(500, omission: "") }
  end

  x.report('G.truncate_graphemes(500, omission: "")') do
    N.times { G.truncate_graphemes(500, omission: "") }
  end
end

__END__

$ bundle exec ruby benchmark.rb
                                               user     system      total        real
S.truncate(500, omission: "")              0.005782   0.000000   0.005782 (  0.005869)
G.truncate(500, omission: "")              0.005722   0.000000   0.005722 (  0.005736)
S.truncate_bytes(1500, omission: "")       0.098025   0.000000   0.098025 (  0.098045)
G.truncate_bytes(1500, omission: "")       0.052442   0.000000   0.052442 (  0.052447)
S.truncate_graphemes(500, omission: "")    1.571742   0.000263   1.572005 (  1.572038)
G.truncate_graphemes(500, omission: "")    1.707722   0.016025   1.723747 (  1.723783)

ベンチマーク: 文字列の長さ

先述の実装では、文字の長さを利用して切り詰め処理を実装しました。そこで、コードポイント、バイト、grapheme cluster それぞれの長さを得る処理の実行時間を確認します。

以下のとおり、 String#grapheme_clusters, String#each_grapheme_cluster, scan(/\X/) を利用して長さを得る場合、 String#size, String#bytesize と比べて著しく時間がかかることがわかります。

require 'benchmark'

N = 1_000
G = "か\u3099き\u3099く\u3099け\u3099こ\u3099" * 1_000

Benchmark.bm(32) do |x|
  x.report('G.size') do
    N.times { G.size }
  end

  x.report('G.bytesize') do
    N.times { G.bytesize }
  end

  x.report('G.each_grapheme_cluster.size') do
    N.times { G.each_grapheme_cluster.size }
  end

  x.report('G.each_grapheme_cluster.count') do
    N.times { G.each_grapheme_cluster.count }
  end

  x.report('G.grapheme_clusters.size') do
    N.times { G.grapheme_clusters.size }
  end

  x.report('G.grapheme_clusters.count') do
    N.times { G.grapheme_clusters.count }
  end

  x.report('G.scan(/\X/).size') do
    N.times { G.scan(/\X/).size }
  end

  x.report('G.scan(/\X/).count') do
    N.times { G.scan(/\X/).count }
  end
end

__END__

                                       user     system      total        real
G.size                             0.003570   0.000000   0.003570 (  0.003568)
G.bytesize                         0.000043   0.000000   0.000043 (  0.000043)
G.each_grapheme_cluster.size       1.499474   0.001309   1.500783 (  1.500750)
G.each_grapheme_cluster.count      1.895799   0.000026   1.895825 (  1.895797)
G.grapheme_clusters.size           1.860043   0.000008   1.860051 (  1.860016)
G.grapheme_clusters.count          1.857524   0.000000   1.857524 (  1.857491)
G.scan(/\X/).size                  2.288390   0.000001   2.288391 (  2.288346)
G.scan(/\X/).count                 2.309266   0.000005   2.309271 (  2.309221)

ベンチマーク: grapheme cluster 単位でのスライス

続いて grapheme cluster 単位で文字列をスライスする処理の実行時間を確認します。

こちらも、コードポイント単位と grapheme cluster 単位でのスライス(String#slice)を比べると、150 倍程度の違いがあることがわかります。

切り詰め位置を可変にするために、式展開を利用して正規表現オブジェクトを生成する場合、その分のオーバーヘッドも発生します。

require 'benchmark'

N = 1_000
G = "か\u3099き\u3099く\u3099け\u3099こ\u3099" * 1_000
L = 500

Benchmark.bm(40) do |x|
  x.report('G[0, L]') do
    N.times { G[0, L] }
  end

  x.report('G[/\X{500}/]') do
    N.times { G[/\X{500}/] }
  end

  x.report('G[/\X{#{L}}/]') do
    N.times { G[/\X{#{L}}/] }
  end

  x.report('G.each_grapheme_cluster.first(L).join') do
    N.times { G.each_grapheme_cluster.first(L).join }
  end

  x.report('G.grapheme_clusters.first(L).join') do
    N.times { G.grapheme_clusters.first(L).join }
  end
end

__END__

                                               user     system      total        real
G[0, L]                                    0.000821   0.000137   0.000958 (  0.000955)
G[/\X{500}/]                               0.143276   0.002752   0.146028 (  0.146055)
G[/\X{#{L}}/]                              0.201928   0.000000   0.201928 (  0.201956)
G.each_grapheme_cluster.first(L).join      0.209498   0.000000   0.209498 (  0.209539)
G.grapheme_clusters.first(L).join          1.874999   0.000000   1.874999 (  1.875052)

まとめ

文字列を grapheme cluster 単位で切り詰める実装について考えましたが、実行時間という大きな問題を解決できていません。

おまけ

Active Support を利用している場合、 ActiveSupport::Multibyte モジュールを利用して grapheme cluster 単位の長さを得ることができます(e.g. str.mb_chars.grapheme_length)。

ただし、5.2.2 の実装では著しく時間がかかるため、利用する際は注意してください。master ブランチでは scan(/\X/) を利用した実装に修正され、性能が大きく改善されているようです。

require 'benchmark'
require 'active_support'
require 'active_support/core_ext'

N = 10
G = "か\u3099き\u3099く\u3099け\u3099こ\u3099" * 1_000

Benchmark.bm(32) do |x|
  x.report('G.size') do
    N.times { G.size }
  end

  x.report('G.bytesize') do
    N.times { G.bytesize }
  end

  x.report('G.each_grapheme_cluster.size') do
    N.times { G.each_grapheme_cluster.size }
  end

  x.report('G.each_grapheme_cluster.count') do
    N.times { G.each_grapheme_cluster.count }
  end

  x.report('G.grapheme_clusters.size') do
    N.times { G.grapheme_clusters.size }
  end

  x.report('G.grapheme_clusters.count') do
    N.times { G.grapheme_clusters.count }
  end

  x.report('G.scan(/\X/).size') do
    N.times { G.scan(/\X/).size }
  end

  x.report('G.scan(/\X/).count') do
    N.times { G.scan(/\X/).count }
  end

  x.report('G.mb_chars.grapheme_length') do
    N.times { G.mb_chars.grapheme_length }
  end
end

__END__

[5.2.2]
                                       user     system      total        real
G.size                             0.000039   0.000007   0.000046 (  0.000043)
G.bytesize                         0.000010   0.000000   0.000010 (  0.000009)
G.each_grapheme_cluster.size       0.016010   0.000000   0.016010 (  0.016119)
G.each_grapheme_cluster.count      0.021273   0.000000   0.021273 (  0.021297)
G.grapheme_clusters.size           0.019911   0.000000   0.019911 (  0.019913)
G.grapheme_clusters.count          0.028932   0.000000   0.028932 (  0.028936)
G.scan(/\X/).size                  0.025493   0.000000   0.025493 (  0.025497)
G.scan(/\X/).count                 0.024883   0.000000   0.024883 (  0.024887)
G.mb_chars.grapheme_length        10.310216   0.004036  10.314252 ( 10.314405)

[master]
                                       user     system      total        real
G.size                             0.000039   0.000005   0.000044 (  0.000040)
G.bytesize                         0.000004   0.000001   0.000005 (  0.000004)
G.each_grapheme_cluster.size       0.014912   0.000325   0.015237 (  0.015352)
G.each_grapheme_cluster.count      0.021615   0.000000   0.021615 (  0.021620)
G.grapheme_clusters.size           0.020779   0.000000   0.020779 (  0.020783)
G.grapheme_clusters.count          0.019705   0.000000   0.019705 (  0.019710)
G.scan(/\X/).size                  0.023782   0.000000   0.023782 (  0.023786)
G.scan(/\X/).count                 0.023227   0.000000   0.023227 (  0.023231)
G.mb_chars.grapheme_length         0.035483   0.000000   0.035483 (  0.035488)