UUIDを任意の文字列で可逆的に短くする、たったN個の冴えたやりかた

※この記事は「COUNTERWORKS Advent Calendar」の9日目の記事です。

はじめに

UUIDって長いですよね。16進数表記だとハイフンありで36文字、ハイフンを取っても32文字です。
人間の目からすると辛いので、短くしたいニーズはあると思います。
今回は任意の文字列だけを使って、少しでも短く、可逆的に変換できる方法を実装しました。

任意の文字列、可逆的な理由

なぜ可逆的かと言うと、計算によって出せるなら、UUIDとのマッピングは不要となる為です。
任意の文字列にする理由は、可逆的に短縮する方法はBase64やSqidsなどがありますが、URLセーフかつ可読性を重視して記号など一部文字を使いたくなかったり、大文字小文字を区別したくないケースもある為でした。

実装方針

Base58は、変換用の文字セットに、flickr用の短縮URL用のものやビットコインのアドレス用のものがあり、これをベースにすれば自由にできます。
Rubyではgem base58 があったのでこの実装を再発明して任意の文字セットでできるようにしました。
他の言語でも同様に実装すれば同じ結果が得られると思います。

結果が可変長文字列となる実装

実装

下記が実装となります。

# 有効な文字セット。任意の文字セットを定義
def base_strings
  # Base58だと最大22文字で可変
  # '123456789abcdefghijkmnopqrstuvwxyzABCDEFGHJKLMNPQRSTUVWXYZ' # flickr方式
  # '123456789ABCDEFGHJKLMNPQRSTUVWXYZabcdefghijkmnopqrstuvwxyz' # Bitcoin方式  
  'ABCDEFGHJKLMNPQRSTUVWXYZ23456789' # アルファベットと数字で視認性の低いI,1,0,Oを除外した32通り(文字)の大文字英数字
end

def uuid_to_base_n(uuid)
  uuid_int = uuid.delete('-').to_i(16) # UUIDからハイフンを削除し、10進数を取得
  int_to_base_n(uuid_int) # 10進数からbaseN文字列を取得
end

def base_n_to_uuid(base_n_val)
  base_n_to_int(base_n_val) # baseN文字列から10進数を取得
    .to_s(16) # 16進数文字列に変換
    .rjust(32, '0') # UUIDは32文字の16進数文字列なので、文字数が足りない場合先頭から0埋め
    .unpack('a8a4a4a4a12').join('-') # UUIDとして定められた文字数ごとにハイフンで区切りUUIDにする
end

def base_number
  base_strings.length
end

def int_to_base_n(int_val)
  raise ArgumentError, 'Value passed is not an Integer.' unless int_val.is_a?(Integer)

  encoded_val = ''
  while(int_val >= base_number)
    mod = int_val % base_number
    encoded_val = base_strings[mod, 1] + encoded_val
    int_val = (int_val - mod) / base_number
  end
  base_strings[int_val, 1] + encoded_val
end

def base_n_to_int(base_n_val)
  int_val = 0
  base_n_val.reverse.split(//).each_with_index do |char, index|
    raise ArgumentError, 'Value passed not a valid BaseN String.' if (char_index = base_strings.index(char)).nil?

    int_val += (char_index) * (base_number ** (index))
  end
  int_val
end

検証

uuid_to_base_n('00000000-0000-0000-0000-000000000000') # => A
base_n_to_uuid('A') # => 00000000-0000-0000-0000-000000000000
uuid_to_base_n('ffffffff-ffff-ffff-ffff-ffffffffffff') # => H9999999999999999999999999
base_n_to_uuid('H9999999999999999999999999') # => ffffffff-ffff-ffff-ffff-ffffffffffff

100_000.times.all? do
  uuid = SecureRandom.uuid_v4
  encoded = uuid_to_base_n(uuid)
  decoded = base_n_to_uuid(encoded)
  p [uuid, encoded, encoded.size]
  uuid == decoded
end # => true

10万回の試行では可逆的に変換できていました。

結果が固定長文字列となる実装

上記実装だとUUIDは最大22文字で可変となる為、長さを固定化したい場合別の実装を考える必要があります。

UUIDは128bitの文字列です。
UUIDから短縮された可逆的な文字列の文字数を固定化したい場合、Base64などを参考に、3ビット（8通り）、4ビット（16通り）、5ビット(32通り)...とキリがよければ固定化できそうです。
32通りの文字セットの場合は5ビットで、128ビット/5ビット=25に余りが出るので、キリが良い130ビットにしたら26文字に変換できそうです。
64通り（6ビット）の場合は132ビットにして22文字で固定できそうですね。

実装

以下32文字の文字セットで試してみます。

def custom_base32_strings
  # 有効な文字セットはアルファベットと数字で視認性の低いI,1,0,Oを除外した32通り(文字)の大文字英数字
  'ABCDEFGHJKLMNPQRSTUVWXYZ23456789'
end

def uuid_to_custom_base32(uuid)
  uuid_hex = uuid.delete('-') # UUIDからハイフンを除去し、32文字の16進数文字列にする
  uuid_bit_string = uuid_hex.chars.map { _1.hex.to_s(2).rjust(4, '0') }.join # 1文字ごとに2進数に変換、桁数を固定したいので0000から1111の4ビット文字列にし、全て結合して128ビット文字列とする
  "#{uuid_bit_string}00" # 128ビット/5ビットだと割り切れない為、2ビット分0を最後に追加し、130ビット文字列にする
    .scan(/.{5}/).map { custom_base32_strings[_1.to_i(2)] } # 130ビット文字列を5ビットごとに区切り、それぞれ0から31の10進数に変換し、変換表により文字列を変換
    .join # 結合して26文字の文字列にする
end

def custom_base32_to_uuid(base32_val)
  base32_val.chars.map { custom_base32_strings.index(_1).to_s(2).rjust(5, '0') } # 変換済の26文字の文字列を、文字ごとに変換表から0から31の10進数に変換、5ビットの2進数文字列にする
    .join.delete_suffix('00') # 結合して130ビット文字列にし、末尾の2ビットの0を削除し128ビット文字列にする
    .scan(/.{4}/).map { _1.to_i(2).to_s(16) }.join # 4ビットごとに区切り、それぞれ16進数に変換し、結合して32文字の16進数文字列に
    .unpack('a8a4a4a4a12').join('-') # UUIDとして定められた文字数ごとにハイフンで区切りUUIDにする
end

検証

uuid_to_custom_base32('00000000-0000-0000-0000-000000000000') # => AAAAAAAAAAAAAAAAAAAAAAAAAA
custom_base32_to_uuid('AAAAAAAAAAAAAAAAAAAAAAAAAA') # => 00000000-0000-0000-0000-000000000000
uuid_to_custom_base32('ffffffff-ffff-ffff-ffff-ffffffffffff') # => 99999999999999999999999996
custom_base32_to_uuid('99999999999999999999999996') # => ffffffff-ffff-ffff-ffff-ffffffffffff

100_000.times.all? do
  uuid = SecureRandom.uuid_v4
  encoded = uuid_to_custom_base32(uuid)
  decoded = custom_base32_to_uuid(encoded)
  p [uuid, encoded, encoded.size]
  uuid == decoded && encoded.size == 26
end # => true

10万回試行では可逆的に、かつ固定長で変換できていました。

終わりに

色々な方法があって面白かったです。Base64はよく使いますが、人間の視覚的に辛いケースもあったので、今回の方法を元に人間が読みやすい形で表示できればと思いました。
もちろん、必要があればマッピングを作り、別のフォーマットで保存した方が人間に優しいケースもあるのでうまく使い分けていきます。

最後に、株式会社カウンターワークスでは、人間の目に優しい実装や出力を心がけられる心優しいメンバーを募集しています！
興味のある方はぜひ以下のリンクからご応募ください！