はじめに
Sudachi では当初、辞書に格納できる文字列の長さを127文字までとしていました。その後もっと長い文字列を格納する必要ができたため互換性をたもったまま文字数をふやすことにしました。
辞書バイナリ内での文字列の構造
バイナリに可変長の文字列を埋め込むにはいくつか方法がありますが、つぎの2つが一般的です。
- 末尾にナル文字 (\0) を置く
- 先頭に文字列長を置く
Sudachi の辞書バイナリでは文字列を UTF-16 で埋め込むため方法1では文字列当たり2バイト必要になります。方法2であれば文字列長を byte で格納すれば1バイト節約できます。そこで Sudachi では2を採用し、文字列の長さ (1バイト) + 文字列の形で格納することにしました。Java の byte は符号付きなので最大127文字になります。
自然言語処理の神は無慈悲
設計したときは形態素の長さは127文字もあればじゅうぶんと想定していたのですが、世の中そんなにあまくありません。自然言語処理において、いくらなんでもこんなことは起こらないだろうと想定したことはだいたい起こります。
あなたの幸せが私の幸せ世の為人の為人類幸福繋がり創造即ち我らの使命なり今まさに変革の時ここに熱き魂と愛と情鉄の勇気と利他の精神を持つ者が結集せり日々感謝喜び笑顔繋がりを確かな一歩とし地球の永続を約束する公益の志溢れる我らの足跡に歴史の花が咲くいざゆかん浪漫輝く航海へ,1,803,32767,あなたの幸せが私の幸せ世の為人の為人類幸福繋がり創造即ち我らの使命なり今まさに変 革の時ここに熱き魂と愛と情鉄の勇気と利他の精神を持つ者が結集せり日々感謝喜び笑顔繋がりを確かな一歩とし地球の永続を約束する公益の志溢れる我らの足跡に歴史の花が咲くいざゆかん浪漫輝く航海へ,名詞,固有名詞,一般,*,*,*,アナタノシアワセガワタクシノシアワセヨノタメヒトノタメジンルイコウフクツナガリソウゾウスナワチワレラノシメイナリイママサニヘンカクノトキココニアツキタマシイトアイトジョウテツノユウキトリタノセイシンヲモツモノガケッシュウセリヒビカンシャヨロコビエガオツナガリヲタシカナイッポトシチキュウノエイゾクヲヤクソクスルコウエキノココロザシアフレルワレラノソクセキニレキシノハナガサクイザユカンロマンカガヤクコウカイヘ,あなたの幸せが私の幸せ世の為人の為人類幸福繋がり創造即ち我らの使命なり今まさに変革の時ここに熱き魂 と愛と情鉄の勇気と利他の精神を持つ者が結集せり日々感謝喜び笑顔繋がりを確かな一歩とし地球の永続を約束する公益の志溢れる我らの足跡に歴史の花が咲くいざゆかん浪漫輝く航海へ,*,C,10289/119649/409479/45393/599164/119649/409479/274475/119649/559991/284077/119649/559991/284473/409620/628692/322476/330333/445260/168773/119649/295005/113561/284776/148904/374639/119649/503266/58157/114140/1371858/762373/102544/440247/102544/438607/730247/119649/324636/102544/317311/119649/616260/171772/466617/636096/45393/621593/79871/168976/499478/440972/358363/613069/628692/171772/595664/109790/838134/102544/67772/366965/119649/532462/171772/616975/78815/305370/119649/429433/551485/445260/168773/119649/699439/114140/527438/119649/648779/45393/354995/15546/164064/171889/542790/708323/647544/142679,10289/119649/409479/45393/599164/119649/409479/274475/119649/559991/284077/119649/559991/284473/409620/628692/322476/330333/445260/168773/119649/295005/113561/284776/148904/374639/119649/503266/58157/114140/1371858/762373/102544/440247/102544/438607/730247/119649/324636/102544/317311/119649/616260/171772/466617/636096/45393/621593/79871/168976/499478/440972/358363/613069/628692/171772/595664/109790/838134/102544/67772/366965/119649/532462/171772/616975/78815/305370/119649/429433/551485/445260/168773/119649/699439/114140/527438/119649/648779/45393/354995/15546/164064/171889/542790/708323/647544/142679,10289/119649/409479/45393/599164/119649/409479/274475/119649/559991/284077/119649/559991/284473/409620/628692/322476/330333/445260/168773/119649/295005/113561/284776/148904/374639/119649/503266/58157/114140/1371858/762373/102544/440247/102544/438607/730247/119649/324636/102544/317311/119649/616260/171772/466617/636096/45393/621593/79871/168976/499478/440972/358363/613069/628692/171772/595664/109790/838134/102544/67772/366965/119649/532462/171772/616975/78815/305370/119649/429433/551485/445260/168773/119649/699439/114140/527438/119649/648779/45393/354995/15546/164064/171889/542790/708323/647544/142679,002562
133文字。神よ。
さてどうしよう
いちばん簡単なのは文字列長を2バイトに変更することですが、ただでもおおきい Sudachi 辞書が文字列あたり1バイトずつふえるのは避けたいところ。互換性がなくなるのも望ましくありません。
そこでちょっとしたトリックをつかいます。文字列長は正数なので最上位ビットはかならず0です。127文字以下のときはそのまま1バイトで表現し、128文字以上のときは最上位ビットを立ててつぎのバイトとあわせて2バイトで表現するフラグとしました。
if (length <= Byte.MAX_VALUE) {
byteBuffer.put((byte) length);
} else {
byteBuffer.put((byte) ((length >> 8) | 0x80));
byteBuffer.put((byte) (length & 0xFF));
}
これで互換性をたもちつつ、128文字以上の場合のみ2バイトにできました。
LEB128
この修正のあとで知ったのですが、このアイデアを汎用化した LEB128 という符号化方式があります。LEB128 には符号付きと符号なしがありますが、ここでは符号なし方式の符号化手順を説明します1。
- 対象となる正の整数を2進数で表現する
- 7ビットずつのグループに分割
- 最上位以外のグループに8ビット目の1を追加しバイト列とする
- 最下位から最上位の順でならべる
たとえば624485という値なら以下のようになります。
- 10011000011101100101
- 100110 0001110 1100101
- 100110 10001110 11100101 (0x26 0x8e 0xe5)
- 0xe5 0x8e 0x26
Sudachi とはエンディアンが逆になっていますね。16384文字以上の形態素がみつかったらこの方式に変更します。
ではよい Sudachi life を。