Ruby

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_clustersString#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)