«前の日記(2008-01-08) 最新 次の日記(2008-01-10)» 編集

Matzにっき


2008-01-09 [長年日記]

_ [言語] Well, I'm Back: String Theory

本当は[言語]タグではないような。

MozillaハッカーであるRobert O'Callahanによる、 「UTF-16はダメ、UTF-8でいいじゃん」という話。

私も前に書いたような気がするけど、 UTF-16は良くない。まず、第一にUTF-16はバイト単位のCES(Character Encoding Scheme)でないので エンディアンの影響を受ける。これは結局同じ名前で2種類のCESがあるのと同じである。

それを区別するための方策がBOM(Byte Order Mark)だが、 これが輪をかけてよくない。 BOMの文字としての意味は「ZERO WIDTH NON-BREAKING SPACE」なので、 これは見えない文字である。付いているかどうかひと目でわからない文字は 面倒なだけである。うっかり文字列やファイルの途中に混じってしまったら目も当てられない。

さらにその全身前身であるUCS2と比較して、 UTF-16は固定長ではない。ので、n番目の文字をアクセスするコストは 普通に実装すればO(n)である。

UCS2の頃に重大な選択を「してしまった」Javaとかはともかく、 これから選ぶならUTF-16はありえない。 もう、ダメの三連荘。

UTF-16がダメなら、なにを選ぶのか。 ここではUTF-8を推奨している。私も(条件つきで)賛成する。

UTF-8は、エンディンアン問題と無縁である。 BOMも不要だ(付けられるけど)。メモリ効率もUTF-16よりはずっといいし。 可変長であるという点はUTF-16同様だけど、 それもそんなに問題ではない。

というのも、そもそもn番目の要素へのアクセス(ここではCharAt(n)と呼ぶ)は そんなに登場しないからだ。実際に頻繁に現れるのは 文字の検索であり、それはもともとO(n・m)だったりするし、 UTF-8でBoyer Mooreを実装するのもたやすい(今のRubyはKarp Rabinを使ってるけど)。

_ [言語] StringRepresentations - The Larceny Project - Trac

LarcenyというScheme処理系でどのように文字列を表現するか、という話。 前にShiroさんが話してたものだね。

紹介されているのは以下の7通り。

flat1
バイト列。1バイトが1文字に相当。ASCIIやLatin-1(ISO-8859-1)に対応。
flat4
バイト列に似ているが、1文字あたり4バイト占有(UTF-32ライク)。Unicodeに対応。
record4
flat4を内包した構造体
record2
1文字あたり2バイトのバイト列で文字列を表現する。 2バイトで表現できない文字が来たら、補助配列を割り当て、 サロゲートペアの後半を補助配列の方に配置する。
record1
1文字あたり1バイトのバイト列で文字列を表現する。 1バイトで表現できない文字が来たら、元の配列の倍の長さの補助配列を割り当て、 文字の下位16ビットは補助配列に、 上位5ビットは元の配列に格納する。元の配列の最上位ビットは 補助配列を参照する必要があることを示すため立てておく。
utf16
UTF-16。だから使っちゃダメだって(笑
utf8
UTF-8。内部表現はバイト列。文字は可変長。

興味深いのはやはりrecord2やrecord1。 ただ、これってSchemeに閉じている時にはいいんだけど、 Cから文字列がほしい時にはrecord1やrecord2のフォーマットのままでは困るので、 毎回UTF-8なりUTF-16なりに変換してやる必要が出てきそうだ。 そうなったときに、変換やメモリ割り当てのコストがどのくらい効いてくるかが 興味深いところだ。少なくともRubyでは難しそうだなあ。

本日のツッコミ(全4件) [ツッコミを入れる]
_ 弟2 (2008-01-11 07:41)

あけおめ。「さらにその全身」→「さらにその前身」のまちがいかな?

_ kosaki (2008-01-11 12:02)

UTF-16が一番ダメなところは、ほとんどケースでUCS2とみなしても正しく動いてしまう為にサロゲートペアを考慮しないおばかさんが大量生産される事だと思う。<br>何度説明してもだって僕のところではうごくんだもん。とか抜かしやがる。

_ naruse (2008-01-11 21:25)

record1はおもしろそうだなぁと思ったのですが、これ結局日本語の場合UTF-8より容量食うんですね。Rubyの場合str_nthでsingle byteの場合はポインタに+nthするだけなので変わりませんから、non-asciiの場合のみですね。「CharAt(n)の登場頻度は低い」という仮定ではこれもうれしさは少ないでしょうし・・・。<br>もっとも、この手のバイト列と実際の格納形式が異なる場合の処理を入れておくと、ISO 2022シリーズを文字集合番号+バイト列でステートフル化したうえで格納、という方法を使いやすくなるので、そういったメリットはあるかもしれません。

_ okagawa (2008-01-13 02:08)

意図的かと思いますが、物理では"String Theory"は「弦理論」(重力を含む素粒子物理の理論)の事を指すのでタイトルを見てびっくりしました。http://en.wikipedia.org/wiki/String_theory

お名前:
E-mail:
コメント:
[]

«前の日記(2008-01-08) 最新 次の日記(2008-01-10)» 編集

track feed Matzにっき Creative Commons License This work is licensed under a Creative Commons License.