Hatena::ブログ(Diary)

まめめも このページをアンテナに追加 RSSフィード

2018-06-08

[] ruby 0.62 のソースコードを復活させた

RubyKaigi の後夜祭で、akr さんが「327 種類の Ruby をビルドする方法 〜0.49 から 2.6.0-preview2 まで〜」という発表をされていました。

その中で、ruby-0.62.tar.gz と ruby-0.63.tar.gz のファイルは「gzip 形式じゃないといわれて展開できない」ということで、ビルド対象から外されていました。

いろいろやって、めでたくこの 2 ファイルを復活させることに成功しました。そのプロセスを書きます。

なお、壊れていたファイルも記念として次の URL に残されています(拡張子が .broken になってます)。

どのように壊れているのかを突き止める

とりあえず当該ファイルをダウンロードし、file してみました。

$ file ruby-0.62.tar.gz ruby-0.63.tar.gz 
ruby-0.62.tar.gz: data
ruby-0.63.tar.gz: data

にべもありません。しょうがないので、バイナリを観察しました。

$ od -c ruby-0.62.tar.gz
0000000   " 253   G 342 302   ;   "       ;   " 243   Y   ' 324 270 354
0000020 210 200 003 262   * 373 016 276   \ 304 325 346 276   e 177 212
0000040 327 214   u 021 030 231   X   F   G 342   ] 231 265 343 216   x
0000060 253 016   ` 222   Y 251 235 255 273   "   *   " 253   b  \v   -
0000100   [   C   N 217 016 257  \f   $ 366 177 361   r   Z 360 256 310
0000120 210 016 310 250   "   (   < 221 207   .   I   ?   &   H 267 004
0000140 021 262   H   N 310 210 016 310 253 211 306   p 035 211 226   d
0000160   Y   * 324 273   "   *   " 253   D 332 257 373 336 353 326 313
0000200   F   P 266 006   v   6 266 235       }   ~ 207   w 337   o   }
0000220 366 257 212 305   ;   O   v   t 032 033 333   v 275   w 024 336
0000240 226 034 330 326 322 373   "   * 240 226   d   Y   * 324 273   "
0000260   *   " 253   B 336 343 214   y 232 032   i 027 332   2   W 336
0000300 206 206   Z 332   [   Z 333 232 266   {   \  \r   0 346   ( 354
0000320   m   {   N   u 274 255 002  \f 217 364   \   1 005   X 273 016
0000340   {   "   * 240 226   d   Y   * 324 273   "   *   " 253   o 312
0000360 374 256 373 346 371 334   j 177 230   8 026   T   = 023  \a 356
0000400 322 177 347   C   W   ~ 347 201 203 221 330 330 332 334 374 350
0000420 375   ; 332 032 233 234 250   ? 246 366 346 273   "   * 240 226
0000440   d   Y   * 324 273   "   *   " 253   V 366 226 207   [   j   ?
0000460 365 251 267   s 354   q 251 320   S   ?   | 377 327 177 357 367
0000500 263 224   ; 353       l   a 247   C   {   * 036 210 220 203   ]
0000520 322 035   Q   U 354 210 200 354 212 275 317 262   " 252 004 273
0000540   "   *   " 253   Q   g   ; 032 025 031   a 367 004   T 005   \
0000560 315 016 307   K   s 261 221 275 222 263 324   y 236   <   q   w
0000600   b 234 201 354 210 200 354 212 266 242   M 245   r 356 275 226
0000620 030 236 326 257   h 357 262   " 252 004 273   "   *   " 253   |
0000640  \r 351   J   "   c   ( 254   5 316 356 227 366 302 357 343   8
0000660   O   ;   c   - 250 211   m   ] 355   < 326 247 225 305 264 362
0000700   M 023 374   c   Q   1 263 205 230 362 352 357   ;   "   * 240
0000720 357 262   " 252 004 273   "   *   " 253   ~   7 200 347 271 002
0000740 366 216   {   D 313   A   L 304 237 030   ~   L 271 337   0 363
0000760 251 274 377  \t 220 222   O   x  \r 304 346   z 266 223 227 240
0001000 265 314 226 254   _   c 262   " 003 262   *   _ 262   " 252 004
0001020 273   "   *   " 253   q 363 351 177 341   2 376 026 337   8 302
0001040   3 323   e   >   C   o 244   R 263 374   &   D 263 330   i 307
0001060   `   D 024   B   !   c 374 223   _ 243 305 303   c 354 210 200

ダブルクォートとアスタリスクが多いな、という印象ですが、さっぱりわかりません。ただ、NUL 文字で埋まっているとかでもないので、完全に無意味なデータとも思えません。

そこでまず、Ruby の歴史を文献調査しました。高橋会長の Ruby 年表によると、Ruby 0.62 は itojun 氏提供のクローズドなメーリングリストで配布されていたらしい。メール配布でデータが壊れる原因と言えば、BASE64uuencode などのバイナリ・テキスト変換が頭をよぎります。

そうこうしていると、shinh さんから重要なヒントが。

xxd -c 59 の結果はこちら。

00000000: 22ab 47e2 c23b 2220 3b22 a359 27d4 b8ec 8880 03b2 2afb 0ebe 5cc4 d5e6 be65 7f8a d78c 7511 1899 5846 47e2 5d99 b5e3 8e78 ab0e 6092 59a9 9dad bb22 2a  ".G..;" ;".Y'.......*...\....e....u...XFG.]....x..`.Y...."*
0000003b: 22ab 620b 2d5b 434e 8f0e af0c 24f6 7ff1 725a f0ae c888 0ec8 a822 283c 9187 2e49 3f26 48b7 0411 b248 4ec8 880e c8ab 89c6 701d 8996 6459 2ad4 bb22 2a  ".b.-[CN....$...rZ......."(<...I?&H....HN.......p...dY*.."*
00000076: 22ab 44da affb deeb d6cb 4650 b606 7636 b69d 207d 7e87 77df 6f7d f6af 8ac5 3b4f 7674 1a1b db76 bd77 14de 961c d8d6 d2fb 222a a096 6459 2ad4 bb22 2a  ".D.......FP..v6.. }~.w.o}....;Ovt...v.w........"*..dY*.."*
000000b1: 22ab 42de e38c 799a 1a69 17da 3257 de86 865a da5b 5adb 9ab6 7b5c 0d30 e628 ec6d 7b4e 75bc ad02 0c8f f45c 3105 58bb 0e7b 222a a096 6459 2ad4 bb22 2a  ".B...y..i..2W...Z.[Z...{\.0.(.m{Nu......\1.X..{"*..dY*.."*
000000ec: 22ab 6fca fcae fbe6 f9dc 6a7f 9838 1654 3d13 07ee d27f e743 577e e781 8391 d8d8 dadc fce8 fd3b da1a 9b9c a83f a6f6 e6bb 222a a096 6459 2ad4 bb22 2a  ".o.......j..8.T=......CW~...........;.....?...."*..dY*.."*
00000127: 22ab 56f6 9687 5b6a 3ff5 a9b7 73ec 71a9 d053 3f7c ffd7 7fef f7b3 943b eb20 6c61 a743 7b2a 1e88 9083 5dd2 1d51 55ec 8880 ec8a bdcf b222 aa04 bb22 2a  ".V...[j?...s.q..S?|.......;. la.C{*....]..QU........"..."*
00000162: 22ab 5167 3b1a 1519 61f7 0454 055c cd0e c74b 73b1 91bd 92b3 d479 9e3c 7177 629c 81ec 8880 ec8a b6a2 4da5 72ee bd96 189e d6af 68ef b222 aa04 bb22 2a  ".Qg;...a..T.\...Ks......y.<qwb.........M.r.......h.."..."*
0000019d: 22ab 7c0d e94a 2263 28ac 35ce ee97 f6c2 efe3 384f 3b63 2da8 896d 5ded 3cd6 a795 c5b4 f24d 13fc 6351 31b3 8598 f2ea ef3b 222a a0ef b222 aa04 bb22 2a  ".|..J"c(.5.......8O;c-..m].<......M..cQ1......;"*..."..."*
000001d8: 22ab 7e37 80e7 b902 f68e 7b44 cb41 4cc4 9f18 7e4c b9df 30f3 a9bc ff09 9092 4f78 0dc4 e67a b693 97a0 b5cc 96ac 5f63 b222 03b2 2a5f b222 aa04 bb22 2a  ".~7......{D.AL...~L..0.......Ox...z........_c."..*_."..."*
00000213: 22ab 71f3 e97f e132 fe16 df38 c233 d365 3e43 6fa4 52b3 fc26 44b3 d869 c760 4414 4221 63fc 935f a3c5 c363 ec88 80ec 8a82 459f e1b7 b222 aa04 bb22 2a  ".q....2...8.3.e>Co.R..&D..i.`D.B!c.._...c......E...."..."*
0000024e: 22ab 57ab 16ef 0d31 4af4 d8df 1879 9388 4e7c 4b4b c885 3ec8 880e c8aa 4d66 6a6a 3bce 49d8 0c63 ea73 1e58 bf1e bfc9 c402 e501 10af b222 aa04 bb22 2a  ".W....1J....y..N|KK..>.....Mfjj;.I..c.s.X..........."..."*
00000289: 22ab 52b8 5cb9 aaf8 54dc fae6 6bde c888 0ec8 a812 bc1a f0fa 4812 f8ec 66f2 6716 044f 0aaa be3d 9b80 e89d 2e98 bf7b 9097 b2b2 456f b222 aa04 bb22 2a  ".R.\...T...k...........H...f.g..O...=.......{....Eo."..."*
000002c4: 22ab 5a5d b673 b8a6 fe49 683e eda5 b599 ad51 57b9 1967 31ca c4f5 de0a bf8b 7810 fb22 203b 22a9 8f2c 65f8 6be3 6c12 ba01 fc6c 0dfb b222 aa04 bb22 2a  ".Z].s...Ih>.....QW..g1.......x.." ;"..,e.k.l....l..."..."*
000002ff: 22ab 52c2 06d5 af81 6c09 ad05 1c93 2c8b fcfb 2220 3b22 ab9f dba8 33ec 8880 ec8a b08a e0a5 8533 669e 3ec8 880e c8ab 2fc5 0bc8 cd04 4636 9fb2 2203 b2  ".R.....l.....,..." ;"....3..........3f.>...../.....F6.."..
0000033a: 22ab 4bbc cbfe 0b2c 2740 2467 44ae 0599 82d2 ef0c 3c73 7525 e085 a127 e738 7acc e7cb 4f08 0548 719e e125 5e27 bf4f 1fbb 222a a004 4636 9fb2 2203 b2  ".K....,'@$gD.......<su%...'.8z...O..Hq..%^'.O.."*..F6.."..
00000375: 22ab 7572 6d1a f013 c5a3 1a06 ec88 80ec 8ab1 a98e ec68 62c8 3db3 9c56 cabb cf68 1963 5888 b79a e142 7c1a a8b7 6c40 1926 425d 47ec 8880 aa02 2203 b2  ".urm................hb.=..V...h.cX....B|...l@.&B]G....."..
000003b0: 22ab 693b 9d46 c8dd 3950 ac8e 2b27 75bb 8353 fc8f 2b11 376c 28d1 e919 429f 5133 10ad 990c a835 8708 3e28 eda8 7959 e5fb 222a a0ec 8880 aa02 2203 b2  ".i;.F..9P..+'u..S..+.7l(...B.Q3.....5..>(..yY.."*......"..
000003eb: 22ab 6b4c 1cd7 d1dd f3f7 bbf4 c83f 2f69 e961 93da 5af4 3dc6 742e 8c6d cf8f ab5e fb22 203b 22a4 2fd4 7bce a1f7 7aec 8880 ec8a 9eb3 3b5c e170 fb22 2a  ".kL.........?/i.a..Z.=.t..m...^." ;"./.{...z.......;\.p."*
00000426: 22ab 45bd cec8 880e c8aa 127a 77b2 2203 b22a 65d7 ed72 4678 7a28 06ac 8482 9a80 8378 eec8 880e c8aa 0301 cbca 1d33 b222 03b2 2abf 9cbc 8974 56d0 45  ".E........zw."..*e..rFxz(.......x...........3."..*....tV.E

各行が必ず 22ab で始まります(shinh さんの言うとおり、この傾向は最初の約 59000 バイトまでで、その後は規則性がなくなります)。

ここで、各行の 3 文字目がだいたいアルファベットに揃っていることに気づきました。これは、3 文字目の上位 2 ビットが固定されている兆候です。つまり、やはり BASE64 ではないか?と思い、59 バイトずつ BASE64 エンコードしてみると

$ ruby -e 'File.binread("ruby-0.62.tar.gz").scan(/.{59}/m) {|s| puts [s].pack("m0") }'
IqtH4sI7IiA7IqNZJ9S47IiAA7Iq+w6+XMTV5r5lf4rXjHURGJlYRkfiXZm14454qw5gklmpna27Iio=
IqtiCy1bQ06PDq8MJPZ/8XJa8K7IiA7IqCIoPJGHLkk/Jki3BBGySE7IiA7Iq4nGcB2JlmRZKtS7Iio=
IqtE2q/73uvWy0ZQtgZ2NradIH1+h3ffb332r4rFO092dBob23a9dxTelhzY1tL7IiqglmRZKtS7Iio=
IqtC3uOMeZoaaRfaMlfehoZa2lta25q2e1wNMOYo7G17TnW8rQIMj/RcMQVYuw57IiqglmRZKtS7Iio=
Iqtvyvyu++b53Gp/mDgWVD0TB+7Sf+dDV37ngYOR2Nja3Pzo/TvaGpucqD+m9ua7IiqglmRZKtS7Iio=
IqtW9paHW2o/9am3c+xxqdBTP3z/13/v97OUO+sgbGGnQ3sqHoiQg13SHVFV7IiA7Iq9z7IiqgS7Iio=
IqtRZzsaFRlh9wRUBVzNDsdLc7GRvZKz1HmePHF3YpyB7IiA7Iq2ok2lcu69lhie1q9o77IiqgS7Iio=
Iqt8DelKImMorDXO7pf2wu/jOE87Yy2oiW1d7TzWp5XFtPJNE/xjUTGzhZjy6u87Iiqg77IiqgS7Iio=
Iqt+N4DnuQL2jntEy0FMxJ8Yfky53zDzqbz/CZCST3gNxOZ6tpOXoLXMlqxfY7IiA7IqX7IiqgS7Iio=
Iqtx8+l/4TL+Ft84wjPTZT5Db6RSs/wmRLPYacdgRBRCIWP8k1+jxcNj7IiA7IqCRZ/ht7IiqgS7Iio=
IqtXqxbvDTFK9NjfGHmTiE58S0vIhT7IiA7Iqk1mamo7zknYDGPqcx5Yvx6/ycQC5QEQr7IiqgS7Iio=
IqtSuFy5qvhU3Prma97IiA7IqBK8GvD6SBL47GbyZxYETwqqvj2bgOidLpi/e5CXsrJFb7IiqgS7Iio=
IqtaXbZzuKb+SWg+7aW1ma1RV7kZZzHKxPXeCr+LeBD7IiA7IqmPLGX4a+NsEroB/GwN+7IiqgS7Iio=

いくつか気づくことがあります。

  • 綺麗に先頭が Iqt で揃っている。よくわからないけれど冗長なデータ。
  • 最後の方の 10 文字くらいは、なんだか前の行と同じことが多い。つまり、59 バイト全部に情報が詰まっているわけではなさそう。*1
  • 先頭の Iqt を含め、Iq が頻出している。これがダブルクォート頻出の正体ですね。

さて、冒頭の Iqt が何なのかはともかく、あきらかに冗長なデータなので、展開に必要な情報ではありません。よって、これを取り除いて BASE64デコードしてみようと思うのは自然なことです。

$ ruby -e 'print [File.binread("ruby-0.62.tar.gz")[0, 59]].pack("m0")[3, 60].unpack("m").first' | xxd
00000000: 1f8b 08ec 8880 ec8a 8d64 9f52 e3b2 2200  .........d.R..".
00000010: 0ec8 abec 3af9 7313 579a f995 fe2b 5e31  ....:.s.W....+^1
00000020: d444 6265 6119 1f89 7666 d78e 39         .Dbea...vf..9

"1f 8b 08" がでてきました。これは gzip のファイルヘッダです。冒頭 3 文字が偶然一致するとは思えないので、やはりこれは tar.gz のようです。しかし、このままでは gzip 展開できません。

$ ruby -e 'puts [File.binread("ruby-0.62.tar.gz")[0, 59]].pack("m0")[3, 60].unpack("m").first' | gzip -cd
gzip: stdin is encrypted -- not supported

正常に展開できる ruby-0.60.tar.gz や ruby-0.64.tar.gz を見ると、ヘッダは "1f 8b 08 00 (タイムスタンプ 4 バイト) 00 03" となるのが正しそうです。しかし、上のように、"1f 8b 08 ec" となっているのでダメなようです。

もう少しヒントを得るために、タイムスタンプを探すことにしました。ruby-0.60.tar.gz のタイムスタンプは 0x2ee6c66d (1994-12-08 17:40:13 +0900) 、ruby-0.64.tar.gz のタイムスタンプは 0x2f1267f7 (1995-01-10 19:56:55 +0900) なので、この間の数値と思われます。0x2e か 0x2f のビットパターン、つまり 00101110 か 00101111 を探します。

$ ruby -e 'print [File.binread("ruby-0.62.tar.gz")[0, 59]].pack("m0")[3, 60].unpack("m").first' | xxd -b
00000000: 00011111 10001011 00001000 11101100 10001000 10000000  ......
00000006: 11101100 10001010 10001101 01100100 10011111 01010010  ...d.R
0000000c: 11100011 10110010 00100010 00000000 00001110 11001000  .."...
00000012: 10101011 11101100 00111010 11111001 01110011 00010011  ..:.s.
00000018: 01010111 10011010 11111001 10010101 11111110 00101011  W....+
0000001e: 01011110 00110001 11010100 01000100 01100010 01100101  ^1.Dbe
00000024: 01100001 00011001 00011111 10001001 01110110 01100110  a...vf
0000002a: 11010111 10001110 00111001                             ..9

発見。

$ ruby -e 'print [File.binread("ruby-0.62.tar.gz")[0, 59]].pack("m0")[3, 60].unpack("m").first' | xxd -b
00000000: 00011111 10001011 00001000 11101100 10001000 10000000  ......
00000006: 11101100 10001010 10001101 01100100 10011111 01010010  ...d.R
                                                           ^~~~
0000000c: 11100011 10110010 00100010 00000000 00001110 11001000  .."...
          ~~~~

ここからリトルエンディアンでタイムスタンプの 4 バイトを取り出すと、

$ ruby -e 'print [File.binread("ruby-0.62.tar.gz")[0, 59]].pack("m0")[3, 60].unpack("m").first' | xxd -b
00000000: 00011111 10001011 00001000 11101100 10001000 10000000  ......
00000006: 11101100 10001010 10001101 01100100 10011111 01010010  ...d.R
                                ^~~~ ~~~~^~~~ ~~~~^~~~ ~~~~^~~~
0000000c: 11100011 10110010 00100010 00000000 00001110 11001000  .."...
          ~~~~

0x2ef549d6 (1994-12-19 17:52:38 +0900) になります。夕方なのがそれっぽい *2

ということで、"1f 8b 08 00 (タイムスタンプ 4 バイト) 00 03" のうち、最初の 3 バイトとタイムスタンプの位置は特定できました。が、間の 00 はどこへ行ったのか。

BASE64 なり uuencode なり、6 ビットごとに区切ったデータにノイズが混ざったのではないか、という確信を得つつあったので、6 ビットごとに区切って観察します。

$ ruby -e 'print File.binread("ruby-0.62.tar.gz").unpack1("B*").scan(/.{6}/)[0, 20].join(" ")'
001000 101010 101101 000111 111000 101100 001000 111011 001000 100010 000000 111011 001000 101010 001101 011001 001001 111101 010010 111000
                     ^~~~~~ ~~^~~~ ~~~~^~ ~~~~~~                      ^~~~~~                        ^~~~ ~~~~^~ ~~~~~~ ^~~~~~ ~~^~~~ ~~~~
		     1f       8b       08                             ??????                        timestamp (4 bytes)

いま探しているのは 00 なので、?????? の部分が目につきます。これに着目すると、000000 が "111011 001000 100010" と "111011 001000 101010" で挟まれているんじゃないか?と感じました。他の行も探してみると、どうも "111011 001000 100010" や "111011 001000 101010" は頻出で、その間は 000000 であることに気づきます。まるで、000000 をエスケープするためのモード切替のよう。

と感じた瞬間にピンと来ました。モード切替といえば、ISO-2022-JP のエスケープシーケンスだ!

ISO-2022-JP(いわゆる JIS 文字コード)は、"ESC ( B" という 3 文字で ASCII モードに、"ESC ( J" という 3 文字で日本語モードに切り替わる文字エンコーディングです。これが "111011 001000 100010" や "111011 001000 101010" に対応しているんじゃないか。

BASE64 で 000000 は "A" の文字で、"A" だけエスケープされる理由は謎だったので、uuencode を疑います。uuencode はよく知らなかったので、Wikipedia を調べます。

デコードにおいては、変数 c にエンコードされた文字のASCIIコードが入っているとすると (c XOR 0x20) AND 0x3f でデコードできる(範囲外の文字が入っている可能性は考慮していない)。

uuencode - Wikipedia

早速 "ESC ( B" をこれでデコードしてみます。

$ ruby -e '"\e(B".bytes {|c| p "%06b" % ((c ^ 0x20) & 0x3f) }'
"111011"
"001000"
"100010"

$ ruby -e '"\e(J".bytes {|c| p "%06b" % ((c ^ 0x20) & 0x3f) }'
"111011"
"001000"
"101010"

ビンゴ! みごと、問題の断片がでてきました。

古い uuencode で 000000 は、空白文字になります。よって、何らかのアクシデントで、uuencode されたデータの中の空白文字ASCII モードに、空白文字以外は日本語モードになるように、エスケープシーケンスが混ざってしまったのでしょう(最初の 59000 バイトだけそうなったのは、この時点では原因不明でしたが、あとでわかります)。

こうして見直すと、各行冒頭の "001000 101010" も、エスケープシーケンスの 2 文字目と 3 文字目なんじゃないかと気づきます。1 文字目はどこに行ったのか。

行の先頭はその行に含まれるオクテット数を示す。通常は45オクテットなので「M」であり、45オクテットに満たない行は別の文字となる。

uuencode - Wikipedia

とあります。「M」ではなく ESC 文字がオクテット数として解釈されたのでは?と思い至り、調べます。すると ESC 文字は 0b111011 、つまり 59 です。これが、shinh さんの指摘した 59 バイト周期の理由。本当は 45 オクテットしかないのに、59 オクテットあるとみなして無理やりデコードされたのでした(ちなみに各行 3 つめの 101101 は、uuencode で「M」で、Wikipedia に書いてある本来のオクテット数です)。

59 バイトの終盤部分が妙に繰り返していたのも、45 オクテット分の情報しかないのに 59 オクテットとしてデコードしたため、バッファの終わりのほうがちゃんと初期化されなかったからでしょう。すべてが腑に落ちていきます。

ということで、

という確信を得ました。これを実証するには、エスケープシーケンスっぽい 3 文字を取り除いて uudecode してみればいいのです。

めでたく(冒頭のみですが)gzip 展開できて、tar っぽいデータがでてきました。やった!

gzip回復を試みる

壊れ方がわかったので、元のメールが得られれば容易に回復できることは明らかでした。が、クローズドなメーリングリストだったので、アーカイブなどはありません。しょうがないので壊れたデータからの回復を試みます。

基本的には、エスケープシーケンスを取り除くだけです。本来 45 バイトなのに、59 バイトあるものとして無理やり uudecode されているため、多少エスケープシーケンスが混ざっていても、情報は欠損しません。それでも、不幸にも大量のエスケープシーケンスが混ざってしまった行については、情報の欠損が発生します。調べてみると、200 バイトほど欠損しているとわかりました。

今回は、ruby-0.60.tar.gz や ruby-0.64.tar.gz が正常に展開できるので、欠損部分もだいたい想像できます。DEFLATE をデコードしていき、欠損部分については前後バージョンから平文を推定し、それを DEFLATE エンコードすることで、欠損データを補完していくスクリプトを書きました。簡単に言ってますが一晩はかかってます。

この方法でデータ部分は回復していけたのですが、残念ながら、途中でハフマンテーブルが 100 ビットほど欠損していることがわかりました。これは致命傷で、自分にはブルートフォースしか思いつきませんでしたが、2^100 のブルートフォースは現代の計算機ではちょっと無理です。

ということで、諦めモードに。

すると

ということで、石塚さんに問合せました。すると、ほんの数時間で「元メイルをお送りします」という返事が! 20 年以上前のメールをパッと引っ張り出せる石塚さんすごい!

あとはごく普通に uudecode したら、無事に解凍できる ruby-0.62.tar.gz と ruby-0.63.tar.gz を得ることができました。復元の苦労はなんだったのか。

ちなみに、ruby-0.62.tar.gz は uuencode で 1000 行ずつ、5 通のメールに分割されて送信されていました。1 通めだけ冒頭に日本語が書かれていて、残りの 4 通は uuencode のデータだけでした。そのせいで、冒頭 59000 バイト程度だけ ISO-2022-JP のエスケープシーケンスが混ざっていたのでした。


まとめ

ruby-0.62.tar.gz と ruby-0.63.tar.gz を回復するまでの道のりでした。しいて教訓っぽいものを得るとしたら、目の前の資料を化学分析するだけではなく、発掘のようなフィールドワークも大切にしよう、みたいな。なんにせよ、考古学は楽しい。

なお、回復されたデータはすでに公式に配布されています。

https://cache.ruby-lang.org/pub/ruby/1.0/

また、akr さんの all-ruby にも含めてもらったようです。

*1:C 言語に慣れてる人は、「未初期化メモリを参照したような挙動だな」という直感が働きます。

*2ruby-0.63.tar.gz のほうは昼過ぎでしたが気にしない。

2018-02-15

[] emruby: emscriptenブラウザで動く MRI

(この記事は Ruby 25th anniversary のための寄稿です)

Rubyブラウザで動かすというと Opal ですが、他の選択肢として、C で書かれた Ruby 処理系emscriptenJS に変換するという選択肢もあります。

しかし調べてみたところ、mruby を WebAssembly に変換した記録は見つかりましたが、MRI でやった例が見つけられなかったので、やってみました。

デモ

https://mame.github.io/emruby/

手順

https://github.com/mame/emruby/ に書いてあるとおりです。

ビルドコマンドは次の通り。

$ emconfigure ./configure CFLAGS="-m32 -s EMULATE_FUNCTION_POINTER_CASTS=1"
$ emmake make V=1 miniruby.js EXEEXT=.js

emconfigure は emscriptenコンパイラとして使う前提で configure を動かすためのラッパ。しかしあまり出来はよくなくて、64 bit 環境で動かすと SIZEOF_LONG が 8 と推定されてしまった(JS 上で sizeof(long) は 4 になるので食い違う)ので、手動で "-m32" を与えています。そのため -m32 でコンパイルできる環境が必要で、ubuntu なら apt-get install libc6-dev-i386 などする必要があります。

また、MRI関数ポインタについてあまり行儀がよくない(3 引数関数に 4 つの引数を渡すとかがそこらじゅうにある)ので、"-s EMULATE_FUNCTION_POINTER_CASTS=1" を与える必要があります(参考:emscripten の Function Pointer Issues)。

emmake は make のラッパ。単に miniruby.js を生成するだけです。


所感など

  • 動作するまでに細かい問題がいくつかありましたが、Ruby 側を少しだけいじって対応しました(変更 1変更 2変更 3)。Ruby が公式に emscripten に対応するのは難しそうな印象ですが、本体に無害なパッチならこっそり取り込めると思うので、プルリクお願いします。
  • Kernel#emscripten_run_script を生やしています。(パッチ)
  • miniruby ではなく ruby が動かしたい。(プルリクウェルカム)
  • ファイルシステムを調べて irb くらい動くようにしたい。(プルリクウェルカム)
  • Run ボタンが一回しか押せない。プロセス再実行する方法が見つけられなかった。
  • miniruby.js が 29 MB もある。WebAssembly だと 5 MB くらいになるようですが、Chrome で素直に動かなかったのでよく見ていません。
  • WebAssembly で Ruby が Web フロントエンド市場に(今度こそ)進出できるといいなあ。Opal は JS に合わせて Ruby の仕様を歪めてるのがあんまり好きじゃなくて、emscripten/WebAssembly なら幸せになるかと思ったけど、まだよくわかりません。

2018-01-30

[] SA-IS 法のメモ

suffix array を線形時間で構築する SA-IS 法についてのメモです。

SA-IS 法の解説はわりと世の中にいっぱいありますが、実際のプログラムにする方法がよくわからなったり、どうしてそれでうまく行くのか書かれてなくて気持ち悪かったりするものが多くて、自分の望む感じのものがありませんでした。アルゴリズムは当然プログラムで見たいし、厳密な証明は要らないけど直観的な理由は知りたい。

ということで、自分なりの理解を書いてみました。

suffix array とは

文字列の suffix とは、文字列の途中から最後までの部分文字列のことです。題材の文字列を "mmiissiissiippi" とすると、次の 17 個の部分文字列です。

 0 mmiissiissiippii$
 1 miissiissiippii$
 2 iissiissiippii$
 3 issiissiippii$
 4 ssiissiippii$
 5 siissiippii$
 6 iissiippii$
 7 issiippii$
 8 ssiippii$
 9 siippii$
10 iippii$
11 ippii$
12 ppii$
13 pii$
14 ii$
15 i$
16 $

最後の $ は番兵です。

これを普通に辞書順にソートします。文字には普通に全順序があり、番兵は他のどの文字よりも小さいとします。

16 $
15 i$
14 ii$
10 iippii$
 6 iissiippii$
 2 iissiissiippii$
11 ippii$
 3 issiissiippii$
 7 issiippii$
 1 miissiissiippii$
 0 mmiissiissiippii$
13 pii$
12 ppii$
 9 siippii$
 5 siissiippii$
 8 ssiippii$
 4 ssiissiippii$

このときのインデックスの列、[16, 15, 14, 10, 6, 2, 11, 7, 3, 1, 0, 13, 12, 9, 5, 8, 4] を suffix array といいます。今回説明しませんが、suffix array は検索や圧縮などでいろいろと役立つ数列です。

suffix array を求めるプログラムRubyナイーブに書くと、これだけです。

s = "mmiissiissiippii".bytes + [0]

p (0...s.size).sort_by {|i| s[i..-1] }
#=> [16, 15, 14, 10, 6, 2, 11, 7, 3, 1, 0, 13, 12, 9, 5, 8, 4]

このプログラムは、ソートに O(n log n) 、しかも各比較に O(n) もかかるので、全体で O(n^2 log n) もかかります。SA-IS はこれを O(n) でやってしまいます。すごい。

SA-IS 法の超概要

流れとしては、次のような感じのアルゴリズムです。

  1. 適当な「種」を元に、induced sort というのをやる → 間違った suffix array が得られる
  2. 間違った suffix array を使って、正しい「種」を得る
  3. 正しい「種」を元に、induced sort をもう一度やる → 正しい suffix array が得られる

「種」が何かはあとで説明するとして、最初の目標は induced sort というものを理解することです。しかし induced sort を理解するには、「L 型と S 型」「LMS」「ビン」という概念をまず理解する必要があります。順に説明します。

L 型と S 型

文字列 s のインデックス i から始まる suffix を s[i..] と書くことにします。s[0..] = "mmiissiissiippii$" です。

インデックスを、次のルールで L 型と S 型に分けます。

インデックス i が L 型」と言ったり、「s[i..] が L 型」と言ったりします。なお、すべての suffix は長さが異なるので、s[i..] == s[i+1..] になることはありません。

例題の文字列を分類すると次の通り。

mmiissiissiippii$
LLSSLLSSLLSSLLLLS

これを計算するには、文字列を逆順に走査して決めていけばいいです。基本的に s[i] と s[i+1] の文字を比べて決めていきます。

# 題材の文字列
s = "mmiissiissiippii".bytes + [0]
k = 256 # 文字種の数

# L 型か S 型か
t = [nil] * s.size

# 最後は S
t[-1] = :S

(s.size - 2).downto(0) do |i|
  # s[i] < s[i+1] なら明らかに s[i..] < s[i+1..] => i は S 型
  # s[i] > s[i+1] なら明らかに s[i..] > s[i+1..] => i は L 型
  # s[i] == s[i+1] の場合、s[i..] <=> s[i+1..] の比較結果は
  # s[i+1..] <=> s[i+2..] に準ずる (つまり t[i + 1] と同じ)
  case
  when s[i] < s[i + 1] then t[i] = :S
  when s[i] > s[i + 1] then t[i] = :L
  else                      t[i] = t[i + 1]
  end
end

LMS と LMS 部分文字列

インデックス i - 1 が L 型、i が S 型になっているとき、i を LMS(Left-most S, 最も左の S)と言います。

例題で言えば、2 番目、6 番目、10 番目、16 番目が LMS 。印をつけた位置。

          1111111
01234567890123456
mmiissiissiippii$
LLSSLLSSLLSSLLLLS
  ^   ^   ^     ^ <= LMS のインデックス

ついでに、LMS から次の LMS までの部分文字列を LMS 部分文字列と言います。これはだいぶ後で出てきます。

mmiissiissiippii$
LLSSLLSSLLSSLLLLS
  ^   ^   ^     ^
  iissi           <= LMS 部分文字列
      iissi       <= LMS 部分文字列
          iippii$ <= LMS 部分文字列
                $ <= LMS 部分文字列

ビン

まず、文字列 s と同じ長さの配列 sa を用意します。ここに suffix array の数列を入れるのが目標です。

# 作業領域
sa = [nil] * s.size

冒頭の suffix array を見ると、i で始まる suffix は 1 番目から 8 番目、m で始まる suffix は 9 番目から 10 番目、というように、suffix の先頭の文字ごとに範囲が決まっています。この範囲を、文字の「ビン」といいます。たとえば、「文字 i のビン」は 1 番目から 8 番目です。

このビンは、文字列 s の中の各文字の出現回数を数えればわかります。

# s に出現する文字種ごとのカウント
bin = [0] * (k + 1)
s.each {|ch| bin[ch + 1] += 1 }

# 文字種を累積することで bin のインデックスを決める
sum = 0
bin = bin.map {|v| sum += v }

これによって、文字 ch で始まる suffix は、sa の bin[ch] 番目から bin[ch+1] - 1 番目のどこかに入れればよい、ということになります。

それから、L 型の suffix と S 型の suffix が同じビンに入る場合(つまり先頭の文字が同じ場合)、必ず L 型の方を前に入れることになります。理由は→*1

ということで、配列 sa を次のように表現することにします。

 0 $ S : --
 1 i L : --
 2 i L : --
 3 i S : --
 4 i S : --
 5 i S : --
 6 i S : --
 7 i S : --
 8 i S : --
 9 m L : --
10 m L : --
11 p L : --
12 p L : --
13 s L : --
14 s L : --
15 s L : --
16 s L : --

左端の数字は sa 内のインデックス、その右の文字はビン、さらにその右の文字は L 型か S 型かを表してます。たとえば、i で始まる S 型の suffix は 3 番目から 8 番目のどこかに入ります。induced sort では、このルールを満たすように suffix のインデックスを入れていきます。

induced sort

いよいよ最初の目標であった induced sort の説明に入ります。induced sort は 3 つの段階からなります。

  1. LMS のインデックスをビンの終わりから詰めていく
  2. L 型のインデックスをビンの頭から詰めていく
  3. S 型のインデックスを(LMS を含めて再度)ビンの終わりから詰めていく

とりあえずアルゴリズムを説明して、それからそれがだいたい何をやっているか説明します。

induced sort: ステップ 1

ステップ 1 は、LMS のインデックスを詰めていきます。LMS の 2 、6 、10 、16 を、それぞれ i 、i 、i 、$ のビンに終わりから入れます。

 0 $ S : 16 $
 1 i L : --
 2 i L : --
 3 i S : --
 4 i S : --
 5 i S : --
 6 i S :  2 iissiissiippii$
 7 i S :  6 iissiippii$
 8 i S : 10 iippii$
 9 m L : --
10 m L : --
11 p L : --
12 p L : --
13 p L : --
14 p L : --
15 s L : --
16 s L : --

右端に、インデックスから始まる suffix を参考に書いています。

ステップ 1 を Ruby で書くとこんな感じ。

# インデックス i が LMS かどうか
def lms?(t, i)
  i > 0 && t[i - 1] == :L && t[i] == :S
end

# LMS のインデックスだけ取り出したリスト(「種」)
lmss = (0...s.size).select {|i| lms?(t, i) }

# ステップ 1: LMS のインデックスをビンの終わりの方から入れる

count = [0] * k # ビンごとにすでに挿入した数をカウントする

# 挿入する順序は適当
lmss.reverse_each do |i|
  ch = s[i]
  # ch を入れるビンの終わり (bin[ch + 1] - 1) から詰めていれる
  sa[bin[ch + 1] - 1 - count[ch]] = i
  count[ch] += 1
end

実はこのとき、LMS をどういう順序で挿入するかが、超概要で言っていた「種」です。正しい順で LMS を挿入すれば、induced sort によって正しい suffix array が計算できてしまいます。しかし、この時点で正しい順序はわからないので、適当に 2 、6 、10 と並べました。正しくは上から 10 、6 、2 の順にならないといけないので、不正解です。最終的な結果も間違ったものになります。しかし不思議なことに、その間違った結果から、正しい「種」を抽出できるのです。詳しくは後で。

induced sort: ステップ 2

ステップ 2 は、sa を正順に走査して L 型の suffix を埋めていきます。

まず、sa に入っている最初のインデックスは 16 です。その 1 つ前のインデックス 15 は L 型なので、ステップ 2 で扱う対象です。s[15] は i なので i のビンに入れます。このとき、ビンの頭に詰めます。

 0 $ S : 16 $    <===== 今見ているところ
 1 i L : 15 i$   <===== 挿入位置
 2 i L : --
 3 i S : --
 4 i S : --
 5 i S : --
 6 i S :  2 iissiissiippii$
 7 i S :  6 iissiippii$
 8 i S : 10 iippii$
 9 m L : --
10 m L : --
11 p L : --
12 p L : --
13 p L : --
14 p L : --
15 s L : --
16 s L : --

このとき、「挿入位置」は必ず「今見ているところ」より後に来ます。理由→*2

次は、入れたばかりの 15 です。14 も L 型なので入れます。これを繰り返していくと、最終的に次のようになります。

 0 $ S : 16 $
 1 i L : 15 i$
 2 i L : 14 ii$
 3 i S : --
 4 i S : --
 5 i S : --
 6 i S :  2 iissiissiippii$
 7 i S :  6 iissiippii$
 8 i S : 10 iippii$
 9 m L :  1 miissiissiippii$
10 m L :  0 mmiissiissiippii$
11 p L : 13 pii$
12 p L : 12 ppii$
13 s L :  5 siissiippii$
14 s L :  9 siippii$
15 s L :  4 ssiissiippii$
16 s L :  8 ssiippii$

ステップ 2 を Ruby で書くとこんな感じ。

# ステップ 2: sa を昇順に走査していく

count = [0] * k # ビンごとにすでに挿入した数をカウントする

sa.each do |i|
  next if i == nil
  next if i == 0
  next if t[i - 1] == :S

  # sa に入っているインデックス i について、i - 1 が L 型であるとき、
  # 文字 s[i - 1] に対応するビンに i - 1 を頭から詰めていれる
  ch = s[i - 1]
  sa[bin[ch] + count[ch]] = i - 1
  count[ch] += 1
end

induced sort: ステップ 3

ステップ 3 は、sa を逆順に捜査して S 型の suffix を埋めていきます。LMS も S 型の一種なので埋めなおします。

まず、sa の最後に入っているインデックスは 8 です。その 1 つ前のインデックス 7 は S 型なので埋めます。s[7] は i なので i のビンに入れます。このとき、ビンの終わりから詰めていれます。

 0 $ S : 16 $
 1 i L : 15 i$
 2 i L : 14 ii$
 3 i S : --
 4 i S : --
 5 i S : --
 6 i S :  2 iissiissiippii$
 7 i S :  6 iissiippii$
 8 i S :  7 issiippii$   <===== 挿入位置
 9 m L :  1 miissiissiippii$
10 m L :  0 mmiissiissiippii$
11 p L : 13 pii$
12 p L : 12 ppii$
13 s L :  5 siissiippii$
14 s L :  9 siippii$
15 s L :  4 ssiissiippii$
16 s L :  8 ssiippii$    <===== 今見ているところ

ステップ 2 と同じように、「挿入位置」は必ず「今見ているところ」より前に来ます。理由も同様です。

なお、もともと入っていた 10 を書きつぶしていることに注意。最初から入っていた LMS は("$" を除いて)いったん全部書きつぶされ、その後で再挿入されます。理由は次の節で。

これを繰り返すと、最終的に次のようになります。

 0 $ S : 16 $
 1 i L : 15 i$
 2 i L : 14 ii$
 3 i S : 10 iippii$
 4 i S :  2 iissiissiippii$
 5 i S :  6 iissiippii$
 6 i S : 11 ippii$
 7 i S :  3 issiissiippii$
 8 i S :  7 issiippii$
 9 m L :  1 miissiissiippii$
10 m L :  0 mmiissiissiippii$
11 p L : 13 pii$
12 p L : 12 ppii$
13 s L :  5 siissiippii$
14 s L :  9 siippii$
15 s L :  4 ssiissiippii$
16 s L :  8 ssiippii$

確かに LMS の 2 と 6 と 10 が(元と異なる位置に)挿入されています。

こうして得られた sa は、ほぼソートされているように見えますが、一部間違っています。例えば、s[4..] = "ssiissiippii$" が 15 番目、s[8..] = "ssiippii$" が 16 番目に来ていますが、この順序は逆ですね。これは後で直します。

Ruby はこちら。

# ステップ 3: sa を逆順に走査していく

count = [0] * k # ビンごとにすでに挿入した数をカウントする

sa.reverse_each do |i|
  next if i == nil
  next if i == 0
  next if t[i - 1] == :L

  # sa に入っているインデックス i について、i - 1 が S 型であるとき、
  # 文字 s[i - 1] に対応するビンに i - 1 を終わりから詰めていれる
  ch = s[i - 1]
  sa[bin[ch + 1] - 1 - count[ch]] = i - 1 # 上書きすることもある
  count[ch] += 1
end

induced sort の結果の考察

induced sort をしたとき、その結果はどんな性質を満たしているでしょうか。

ステップ 1 はビンソートなので、少なくとも各 suffix の最初の文字についてはちゃんとソートできています。しかし、各 suffix の 2 文字目以降はソートされていないかもしれません。次の図はステップ 1 の結果で、ソートされていないかもしれないところを ... で省略して表示しています。

 0 $ S : 16 $
 1 i L : --
 2 i L : --
 3 i S : --
 4 i S : --
 5 i S : --
 6 i S :  2 i...
 7 i S :  6 i...
 8 i S : 10 i...
 9 m L : --
10 m L : --
11 p L : --
12 p L : --
13 s L : --
14 s L : --
15 s L : --
16 s L : --

ステップ 2 では、すでに入っている suffix より 1 つ長い suffix を入れていきます。このとき、先頭 n 文字についてソートされていた suffix を 1 つ伸ばした suffix は、先頭 n + 1 文字がソートされていることが保証されます。理由→*3

これを繰り返すと、ステップ 2 完了時点で次のようになります。

 0 $ S : 16 $
 1 i L : 15 i$
 2 i L : 14 ii$
 3 i S : --
 4 i S : --
 5 i S : --
 6 i S :  2 i...
 7 i S :  6 i...
 8 i S : 10 i...
 9 m L :  1 mi...
10 m L :  0 mmi...
11 p L : 13 pii$
12 p L : 12 ppii$
13 s L :  5 si...
14 s L :  9 si...
15 s L :  4 ssi...
16 s L :  8 ssi...

ステップ 3 はステップ 2 と全く同様です。

 0 $ S : 16 $
 1 i L : 15 i$
 2 i L : 14 ii$
 3 i S : 10 iippii$
 4 i S :  2 iissi...
 5 i S :  6 iissi...
 6 i S : 11 ippii$
 7 i S :  3 issi...
 8 i S :  7 issi...
 9 m L :  1 mi...
10 m L :  0 mmi...
11 p L : 13 pii$
12 p L : 12 ppii$
13 s L :  5 si...
14 s L :  9 si...
15 s L :  4 ssi...
16 s L :  8 ssi...

ということで、... になっていない部分についてはソートされていることが保証されます。これが induced sort によって言えること。

さて、もしもステップ 1 の段階で、LMS が正しい順序(「種」)で挿入されていたとします。ステップ 2 とステップ 3 の「先頭 n 文字についてソートされている suffix を元に、1 つ長い suffix を先頭 n + 1 文字についてソートされた状態で挿入する」という性質から、正しい「種」から始めて最終的に得られる sa は、すべての suffix の全体についてソートされていることになります。それはすなわち、正しい suffix array です。

ということで、どうにか正しい「種」を得るというのが残る課題です。実はこれは、上記の「間違った induced sort の結果」を使って取り出すことができるのですが、その前に正しい「種」とは何かを考察します。

正しい「種」

正しい「種」を取り出すナイーブな実装としては、LMS の suffix を列挙して、辞書順にソートすればいいです。

LMS の suffix を列挙したもの。

 2: iissiissiippii$
 6: iissiippii$
10: iippii$
16: $

↓ソート

16: $
10: iippii$
 6: iissiippii$
 2: iissiissiippii$

この [16, 10, 6, 2] が求める「種」です。induced sort のステップ 1 で、この「種」を逆順に走査して、各ビンの最後から詰めていくと次のようになります。

 0 $ S : 16 $
 1 i L : --
 2 i L : --
 3 i S : --
 4 i S : --
 5 i S : --
 6 i S : 10 iippii$
 7 i S :  6 iissiippii$
 8 i S :  2 iissiissiippii$
 9 m L : --
10 m L : --
11 p L : --
12 p L : --
13 p L : --
14 p L : --
15 s L : --
16 s L : --

この状態でステップ 2 と 3 を実行すれば、めでたく正しい suffix array が得られます。

ただ、ナイーブな実装では O(n) が達成できません。そこで、このソートに SA-IS 法を再帰的に使うというのが、SA-IS 法の肝です。

SA-IS 法の再帰

LMS の suffix の列を SA-IS 法でソートするために、suffix の文字単位を「粗く」するのがポイントです。

"mmiissiissiippii$" を LMS 部分文字列(LMS を導入したときについでに説明してました)で分割すると、["iissi", "iissi", "iippii$", "$"] になります *4 。ここで、"iissi" や "iippii$" を 1 つの「文字」とみなし、この列を「文字列」と考えます。そして、この「文字列」のすべての suffix を並べてみます。

0: ["iissi", "iissi", "iippii$", "$"] ( 2: iissiissiippii$)
1: ["iissi", "iippii$", "$"]          ( 6: iissiippii$)
2: ["iippii$", "$"]                   (10: iippii$)
3: ["$"]                              (16: $)

最後の "(2: iissiissiippii$)" や "(16: $)" は、各 suffix が元の文字列のどの suffix に対応するかを表しています。

各「文字」の順序関係("$" < "iippii$" < "iissi")に注意しつつ、この「文字列」の suffix の列をソートします。

3: ["$"]                              (16: $)
2: ["iippii$", "$"]                   (10: iippii$)
1: ["iissi", "iippii$", "$"]          ( 6: iissiippii$)
0: ["iissi", "iissi", "iippii$", "$"] ( 2: iissiissiippii$)

注目すべきは、元文字列のインデックスの列。めでたく、[16, 10, 6, 2] という正しい「種」が得られています。

ところで、今おこなったソートは、"iissi" などを「文字」とみなした「文字列」の suffix array を作ったのと同じです。よって SA-IS 法が再帰的に適用できます。再帰すると全体で O(n) にならなくなりそうですが、「文字列」の長さは元の文字列の長さに比べて半分未満になってるので、O(n + n/2 + n/4 + ...) = O(2n) = O(n) ということで、線形時間が保たれます。すごい。

ちなみに、このアルゴリズム構成技法再帰減速(recursive slowdown)といいます。余談ですが、これを遅延評価でやった暗黙的再帰減速(implicit recursive slowdown)という技法もあります。こういうのが面白いなと思った人は、次の本がとても面白いかもしれません。

純粋関数型データ構造
Chris Okasaki
KADOKAWA (2017-04-28)
売り上げランキング: 82,013

「文字」に番号を振る

さて、"iissi" や "iippii$" を 1 つの「文字」として扱うと言いましたが、実際にこういう部分文字列を切り出すと、比較に O(n) かかってしまうのでダメです。そこで、次のように番号を振ることを考えます。

"$"       => 0
"iippii$" => 1
"iissi"   => 2

この番号付けは、"$" < "iippii$" < "iissi" という順序関係を維持しています。そして、番号同士なら比較が O(1) でできます。よって、番号で置き換えてから SA-IS 法を再帰すれば OK です。

ただ、この番号を振る方法は自明ではありません。下手をしたら番号を振るために O(n^2) とかかかってしまいます。

この番号付けのために、1 回目の induced sort の(間違った)結果が使えます。再掲。

 0 $ S : 16 $
 1 i L : 15 i$
 2 i L : 14 ii$
 3 i S : 10 iippii$
 4 i S :  2 iissi...
 5 i S :  6 iissi...
 6 i S : 11 ippii$
 7 i S :  3 issi...
 8 i S :  7 issi...
 9 m L :  1 mi...
10 m L :  0 mmi...
11 p L : 13 pii$
12 p L : 12 ppii$
13 s L :  5 si...
14 s L :  9 si...
15 s L :  4 ssi...
16 s L :  8 ssi...

ここから、LMS の suffix だけを取り出してみます。

 0 $ S : 16 $
 3 i S : 10 iippii$
 4 i S :  2 iissi...
 5 i S :  6 iissi...

... を除くと、LMS 部分文字列ばかり出てきました。これは偶然ではありません。理由→*5

よって、この情報を活用することで、さっきのような番号付けを実現できます。隣り合う LMS 部分文字列を比べて、異なる場合は別の番号を、同じ場合は同じ番号を順に振っていけば OK です。具体的には次のような感じ。

  • "$" に番号 0 を振っておく
  • "$" と "iippii$" は異なるので、"iippii$" に番号 1 を振る
  • "iippii$" と "iissi" は異なるので、"iissi" に番号 2 を振る
  • "iissi" と "iissi" は同じなので、新しい番号は振らない

これで所望の番号付けができました。ちなみに、このときは LMS 部分文字列を直接比較しますが、文字の比較回数の合計が O(n) なので、問題ありません。

実装

実際にほしいのは、単なる番号付けではなく、["iissi", "iissi", "iippii$", "$"] の各 LMS 部分文字列を番号で置き換えたもの、つまり [2, 2, 1, 0] です。これを一気に求めます。

# induced sort の結果から LMS の suffix だけ取り出す
sa = sa.select {|i| lms?(t, i) }

# LMS のインデックス i に対して番号 nums[i] を振る
nums = []

# sa[0] の LMS は $ と決まっているので、番号 0 を振っておく
nums[sa[0]] = num = 0

# 隣り合う LMS を比べる
sa.each_cons(2) do |i, j|
  diff, d = false, 0

  # 隣り合う LMS 部分文字列の比較
  s.size.times do |d|
    if s[i + d] != s[j + d] || lms?(t, i + d) != lms?(t, j + d)
      # LMS 部分文字列の範囲で異なる文字があった
      diff = true
      break
    elsif d > 0 && (lms?(t, i + d) || lms?(t, j + d))
      # LMS 部分文字列の終端に至った
      break
    end
  end

  # 隣り合う LMS 部分文字列が異なる場合は、番号を増やす
  num += 1 if diff
  
  # LMS のインデックス j に番号 num を振る
  nums[j] = num
end

# nums の中に出現する番号のみを並べると、LMS 部分文字列を番号に置き換えた列が得られる
nums = nums.compact

sa.each_cons(2) の中で sa.size.times を使っているので、一瞬 O(n^2) の二重ループのようにも見えますが、よく考えるとループの実行回数は最大でも元の文字列全体を 1 回走査するのと同じなので、O(n) に収まります。

さて、これで得られた nums に SA-IS 法を再帰適用します。ただ、もし隣り合う LMS 部分文字列が全部異なるものだった場合、つまり番号の重複がない場合は、いちいち再帰するまでもなく、ビンソート(各ビンのサイズは 1)の考え方で suffix array を直接求めることができます。

if num + 1 < nums.size
  # 番号の重複があるので再帰
  sa = sa_is(nums, num + 1)
else
  # 番号の重複がない場合、suffix array を容易に求められる
  sa = []
  nums.each_with_index {|ch, i| sa[ch] = i }
end

そして、これで得られる sa は上記で言う [3, 2, 1, 0] に相当する数列なので、これを LMS インデックスの列 [16, 10, 6, 2] に変換します。

lmss = (0...s.size).select {|i| lms?(t, i) }
seed = sa.map {|i| lmss[i] }

そして、この「種」を元に induced sort を再度行えば、ついに完了です。長かった。

まとめ

suffix array を O(n) で作るアルゴリズム SA-IS 法を説明しました。

世にある解説が自分にはいまいちわかりにくいものしか見つからなかったので書いてみましたが、やっぱりこれも他の人にとってはわかりにくいものになっているのかもしれません。コメントをくれたら改良を考えます。

おまけ:プログラム全体

# インデックス i が LMS かどうか
def lms?(t, i)
  i > 0 && t[i - 1] == :L && t[i] == :S
end

def induced_sort(s, k, t, lmss)
  # 作業領域
  sa = [nil] * s.size

  # s に出現する文字種ごとのカウント
  bin = [0] * (k + 1)
  s.each {|ch| bin[ch + 1] += 1 }

  # 文字種を累積することで bin のインデックスを決める
  sum = 0
  bin = bin.map {|v| sum += v }
  
  # ステップ 1: LMS のインデックスをビンの終わりの方から入れる

  count = [0] * k # ビンごとにすでに挿入した数をカウントする

  lmss.reverse_each do |i|
    ch = s[i]
    # ch を入れるビンの終わり (bin[ch + 1] - 1) から詰めていれる
    sa[bin[ch + 1] - 1 - count[ch]] = i
    count[ch] += 1
  end

  # ステップ 2: sa を昇順に走査していく

  count = [0] * k # ビンごとにすでに挿入した数をカウントする

  sa.each do |i|
    next if i == nil
    next if i == 0
    next if t[i - 1] == :S

    # sa に入っているインデックス i について、i - 1 が L 型であるとき、
    # 文字 s[i - 1] に対応するビンに i - 1 を頭から詰めていれる
    ch = s[i - 1]
    sa[bin[ch] + count[ch]] = i - 1
    count[ch] += 1
  end

  # ステップ 3: sa を逆順に走査していく

  count = [0] * k # ビンごとにすでに挿入した数をカウントする

  sa.reverse_each do |i|
    next if i == nil
    next if i == 0
    next if t[i - 1] == :L

    # sa に入っているインデックス i について、i - 1 が S 型であるとき、
    # 文字 s[i - 1] に対応するビンに i - 1 を終わりから詰めていれる
    ch = s[i - 1]
    sa[bin[ch + 1] - 1 - count[ch]] = i - 1 # 上書きすることもある
    count[ch] += 1
  end

  sa
end

def sa_is(s, k)
  # L 型か S 型かのテーブル
  t = [nil] * s.size

  # 最後は S
  t[-1] = :S

  (s.size - 2).downto(0) do |i|
    # s[i] < s[i+1] なら明らかに s[i..] < s[i+1..] => i は S 型
    # s[i] > s[i+1] なら明らかに s[i..] > s[i+1..] => i は L 型
    # s[i] == s[i+1] の場合、s[i..] <=> s[i+1..] の比較結果は
    # s[i+1..] <=> s[i+2..] に準ずる (つまり t[i + 1] と同じ)
    case
    when s[i] < s[i + 1] then t[i] = :S
    when s[i] > s[i + 1] then t[i] = :L
    else                      t[i] = t[i + 1]
    end
  end

  # LMS のインデックスだけを集めた配列
  lmss = (0...s.size).select {|i| lms?(t, i) }

  # 適当な「種」:seed = lmss.shuffle でもよい
  seed = lmss

  # 1 回目の induced sort
  sa = induced_sort(s, k, t, seed)

  # induced sort の結果から LMS の suffix だけ取り出す
  sa = sa.select {|i| lms?(t, i) }

  # LMS のインデックス i に対して番号 nums[i] を振る
  nums = []

  # sa[0] の LMS は $ と決まっているので、番号 0 を振っておく
  nums[sa[0]] = num = 0

  # 隣り合う LMS を比べる
  sa.each_cons(2) do |i, j|
    diff, d = false, 0

    # 隣り合う LMS 部分文字列の比較
    s.size.times do |d|
      if s[i + d] != s[j + d] || lms?(t, i + d) != lms?(t, j + d)
        # LMS 部分文字列の範囲で異なる文字があった
        diff = true
        break
      elsif d > 0 && (lms?(t, i + d) || lms?(t, j + d))
        # LMS 部分文字列の終端に至った
        break
      end
    end

    # 隣り合う LMS 部分文字列が異なる場合は、番号を増やす
    num += 1 if diff
  
    # LMS のインデックス j に番号 num を振る
    nums[j] = num
  end

  # nums の中に出現する番号のみを並べると、LMS 部分文字列を番号に置き換えた列が得られる
  nums = nums.compact

  if num + 1 < nums.size
    # 番号の重複があるので再帰
    sa = sa_is(nums, num + 1)
  else
    # 番号の重複がない場合、suffix array を容易に求められる
    sa = []
    nums.each_with_index {|ch, i| sa[ch] = i }
  end

  # 正しい「種」
  seed = sa.map {|i| lmss[i] }

  # 2 回目の induced sort
  sa = induced_sort(s, k, t, seed)

  sa
end

# 題材の文字列
s = "mmiissiissiippii".bytes + [0]
k = 256 # 文字種の数
p sa_is(s, k)

なお、このプログラムRuby らしく大変富豪的に書かれています(配列作りまくり)。元論文の C プログラムは、ビンの位置以外の配列をすべて SA という 1 つの配列の再利用で解決していてかっこいいです。

出典

  • Ge Nong, Sen Zhang, and Wai Hong Chan. Two Efficient Algorithms for Linear Time Suffix Array Construction

追記(2018-02-10):コメントでの指摘を受けてバグ修正。「隣り合う LMS 部分文字列の比較」のループ終了条件が間違ってました。

*1:L 型は、1 文字目が 2 文字目より Larger です(例:"ba...")。S 型は、1 文字目が 2 文字目より Smaller です(例:"bc...")。明らかに "ba..." < "bc..." なので、確かに L 型は S 型より前に来てます。1 文字目と 2 文字目が同じになっている文字列の場合もまあ同じように証明できます。

*2インデックス i に対して i-1 が L 型のときだけ挿入する。L 型の定義から s[i-1..] > s[i..] 。つまり s[i-1..] の挿入位置は s[i..] より後になる。

*3インデックス 10 の suffix "i..." は先頭 1 文字についてソートされています。今回は、インデックス 10 を元に、インデックス 9 の suffix "si..." が sa[15] の位置に挿入されました。これに注目してみます。もしも "si..." を s[15] に入れることが間違いだとしたら、sa[15] は文字 s のビン内なので、"si..." より大きいか、または小さい文字列が入るべきだったことになります。もし仮に、s[15] の位置には "si..." より大きい文字列(たとえば "sz...")が入るべきだったとすると、s[13] から s[14] はすでに埋まっていることから、"si..." はいったいどこに行けばいいのかわからない、ということになるので矛盾。s[15] の位置に "si..." より小さい文字列(たとえば "sa...")が入るべきだったとすると、a の文字のビンの中に "a..." のような文字列があったはずです。そしてステップ 2 では上から順番に処理しているので、その文字列が先に処理され、sa[15] にはすでに "sa..." が入っていたはずです。しかし実際には sa[15] にそういう文字列が入っていなかったので、矛盾。ということで、インデックス 5 の suffix "si..." が入るのが正しいということになります。

*4:先頭の "mm" は LMS 部分文字列ではないので捨てます。また、LMS 部分文字列の切れ目で 1 文字重複してます。

*5:特定の suffix に注目して induced sort の動きを見てみます。ステップ 1 で sa[8] (sa の 8 番目) に入れられたインデックス 10 に注目してみましょう。ステップ 2 では、インデックス 10 を元に、L 型インデックス 9 が s[14] に入れられました。そのインデックス 9 を元に、L 型インデックス 8 が s[16] に入れられました。次のインデックス 7 は S 型なので、ステップ 2 はここで終わりです。ステップ 3 では、インデックス 8 を元に、S 型インデックス 7 が s[8] に入れられました。インデックス 7 を元に、S 型インデックス 6 が s[5] に入れられました。次のインデックス 5 は L 型なので、ステップ 3 はここで終わり。要するに、LMS から始めてその前の L 型を順次追加し、さらにその前の S 型を順次追加する、スタートの LMS からみて 1 つ前の LMS にたどり着いた時点で終了、という動きになっています。LMS から 1 つ前の LMS までの範囲(すなわち LMS 部分文字列)についてソートされる、ということになります。

2017-10-12

テスト駆動開発』を読んで

テスト駆動開発
テスト駆動開発
posted with amazlet at 17.10.12
Kent Beck
オーム社
売り上げランキング: 563

オーム社さまから電子書籍を贈本いただきました。ありがとうございます。

本書はテスト駆動開発TDD)の原典で、たいへん有名な本です。が、自分は食わず嫌いで読んだことがありませんでした。

というか、TDD 自体もちゃんと理解したことがありませんでした。なんだろう、なんか怖かった。

そんな自分が今回この本をいまさら読んでみたら、なるほどこれは確かにいい本でした。なんというか、語りたくなる感じ。ということでご紹介。

紹介

テストとプログラムを交互に書いていく開発方法 TDD を、例題を用いて実演していく本です。

TDD というと「プログラムより先にテストを書く」というところだけ強調されますが、正直それではよくわからないのでした *1 。本書によると、

  1. テストを 1 つ書き足す
  2. それをパスする仮実装を追加する
  3. 仮実装をまともな実装にする

を細かく繰り返す、というものだそうです。仮実装は本当にテキトーで、テストの期待値をそのままプログラムに埋め込んだりします。「仮実装をまともな実装にする」は、本書では「テストとプログラムの間で重複を省く」と表現されています。というのも、プログラムに期待値を埋め込むことで、その期待値がテストとプログラムの間で重複するので。この重複をいい感じに省くことで、徐々にまともな実装になっていく。

テスト駆動開発」という名前ですが、テストを書くための方法ではなく、あくまで設計開発の方法ということがよくわかりました。テストはあくまで実装のガイド。テストはそえるだけ。

構成としては、第 1 部は通貨の足し算や掛け算を扱うプログラムJava で、第 2 部はテスティングフレームワークPython で、それぞれ TDD の実演で開発してみせます。上記の繰り返しそのときどきの思考が、なんというか非常に生々しく書かれていて、ライブ感に溢れています(訳者あとがきで「まるで Kent Beck とペア・プログラミングしているかのような体験をしました」と書かれていて、まさにそんな感じ)。第 3 部は TDD にまつわる色々な話題を集めていて、まえがきによると「リファレンスとして使うのがよいだろう」だそうですが、自分の印象としてはエッセイ集みたいな感じです。ただ、第 3 部はまだ流し読みしかしていないので、あとでちゃんと読む。

本書自体も(読んだことのなかった自分には)面白い内容でしたが、この翻訳には訳者の t_wada さんによる「訳者解説:テスト駆動開発の現在」という付録がついてます。TDD の原著が出てから現在までの歴史と現状が非常にコンパクトにまとまっていて、さらに現代で TDD とどう向き合っていくべきかが書かれています。ここの良さを説明するのは困難ですが、とりあえず、自分が TDD強迫観念みたいに感じていた理由と、別に怖くない(人もいる)というのがよくわかりました。

所感

まあ、自分が TDD を実践したくなったかと言うと、そうでもないです。TDD の真のポイントは TODO 管理だと思うんですよね。仮実装が一部仮のまま次のテストに進むことがあったり、テストとプログラムの間で頻繁にコンテキストスイッチしたりするので、TODO を忘れずにこなせる人でないと厳しそう。普段の生活でも TODO 管理が辛いのに。

とはいえ、テストをパスする状態を維持するというのは強く共感しました(というか、こういう本などが布教した考え方なんだろう)。Quine を書くときも、まずはでかくて不格好でもとにかく動く Quine にし、そのあとは動く状態を維持しつつ形や長さを改良する修正を少しずつやっていきますよね。うん。あと、こういう頻繁にテストを実行するやり方では、コンパイルに数秒もかかるような言語処理系では無理だよねー。

それから、TDD が別に万能ではないことがちゃんと書かれているのが好印象でした。設計のひらめき自体は TDD では得られない(83 ページ)とか、アサーションで使う述語自体が間違ってたら TDD は無力になる(27 ページ)とか。あと、通貨換算の責務は Expression ではなく Bank に持たせたい(83 ページ)と言いつつ、その後はせっせと Expression#reduce を実装してたり、最適化を実装しようとしたものの抽象度が壊れるから諦めて(128 ページ)、「パフォーマンスの懸念もあるが、実際の使われ方を見てから最適化を考えるので十分だと思う」(135 ページ)とか強がるあたり、ニヤニヤしながら読めた。そんな気取らない作風でした。

まとめ

TDD の考え方がよくわかる本でした。自分と同じように「なんか TDD とか聞くけどよくわかってない」という人は読んでみるといいです。t_wada さんによる付録で、原著以降の BDD などの歴史や現状、TDD の用法・用量までよくわかるおまけつき。TDD くらいすでに知ってるよ、という人も、この付録は読む価値があると思います。

*1:中にはちゃんと説明してくれている人もいたんだろうけど、自分の方がちゃんと聞く気がなかった。

2017-09-15

[] RubyKaigi 2017 の予稿:An introduction and future of Ruby coverage library

RubyKaigi 2017 の 2 日目に "An introduction and future of Ruby coverage library" というタイトルで発表します。事前資料の公開が推奨されていたので、簡単ですがどんな内容かを書いておきます。

要約

カバレッジ(テストカバレッジ、コードカバレッジ)は、ソースコードのどの程度の割合がテストによって実行されたかを表す指標で、「テストの良さ」に関するヒントを与えてくれるものです。Rubyでは、品質を保証する手段がいまのところテストしかないので、カバレッジをうまく使うことは重要です。

本発表では、我々が経験や見聞を通じて得たカバレッジとの付き合い方を紹介します。簡単に言うと、カバレッジは「コードに対する網羅率」に過ぎず、「仕様や設計に対する網羅率」ではないことを理解した上で、前者だけでなく後者も上げるためのヒントとしてカバレッジを活用することです。(なお、カバレッジの定義から丁寧に説明するので、前提知識は必要ありません。)

また、Rubyカバレッジ測定の現状として、SimpleCov や coverage.so などを紹介した上で、2.5 に向けての coverage.so の拡張計画を説明します。具体的には、関数カバレッジと分岐カバレッジの測定を可能にする予定で、そのために現在検討中の coverage.so の仕様を紹介します。他言語のカバレッジ管理ツールとの連携のために必要な情報を提供するように設計していて、実際に LCOV や Cobertura で可視化できることをデモする予定です。

解説

Ruby3x3 で導入される(とされている)型システムに注目が集まっていますが、プログラム堅牢性を高める手段は、なにも型だけではありません。コードレビューだって立派な品質保証手段ですし、普通の型よりも強力に検証する手段もあります。しかし、現時点で一番普及している手段は明らかに、テストです。そこでテストの度合いのヒントとなるカバレッジは重要なはずですが、テストに比べると普及度が低いように感じています。

カバレッジが十分に活用されていない理由はいろいろ考えられますが、「カバレッジの(うまい)活用方法があまり知られていない」「Rubyカバレッジ測定ライブラリが貧弱」という 2 つの問題を緩和するために、今回発表してみることにしました。

2008 年にコミッタになって最初にやった仕事が、Ruby 本体のテストカバレッジ向上でした。主にそのころに得た知見と反省などを元に、漠然と考えていた「カバレッジのうまい活用方法」を明文化してみたので、共有したいと思います。

そのころに作った Ruby カバレッジ測定ライブラリ coverage.so は、便利なラッパ SimpleCov が登場したおかげでそこそこ使われているようです。しかし、当時 coverage.so の仕様を適当に決めてしまったために、行カバレッジ以外をサポートしづらく、放置していました(すみません)。今回一念発起し、関数カバレッジと分岐カバレッジをサポートする方向で仕様の検討と実装の試作をし、昨日コミットしました。まだ細かいところが詰めきれていないのですが、2.5 のリリースまでには決めたいと思っています。

なお、超絶技巧みたいな話は今回はありません。ない予定です。ないんじゃないかな。期待しないでください。

宣伝

拙著『Ruby でつくる Ruby』が、ジュンク堂書店の RubyKaigi 出張店で販売される予定です。サイン会もあるみたいなので、ぜひお買上げを!なお、RubyKaigi 出張店は RubyKaigi 1 日め(9/18(月・祝))だけなので要注意です。サイン会も 1 日めですが、本さえあればいつでもサインするので適当に捕まえてください。

さらに、ラムダノートがRubyKaigi 2017 便乗、サイン入り書籍プレゼント企画!(connpass)をしています。RubyKaigi に参加できない方はこっちに応募してみてください!

Connection: close