LoginSignup
4
0

More than 5 years have passed since last update.

@koshigoein株式会社フィードフォース

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

Last updated at Posted at 2019-02-08

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)
4
0
3

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
Sign upLogin
4
0