Unicode Collation Algorithm

この記事はLibreOffice Advent Calendar 2020の記事です。時間オーバーして2020-12-24に公開していますが、2020-12-23の記事です。

自分がなにか書く時って大抵最近(?)出会ったバグレポをとっかかりにすることが多く、今回もネタとしては、tdf#125363 - UI: LibreOffice Calc's AutoFilter treats combining and modifier letters the same as plain letters in the value listからとなります。自分のtwitterでも確か何度か出していたと思うので、そこからもう既に原因を調べた人には本記事は無用です。

このバグがなぜ起きているかを理解するためには、Unicode Collation Algorithmを理解する必要があり、本記事はそれを解説しようとして能力不足で箇条書きに留まったもの。この記事はLibreOffice Advent Calendarだというのに(汗

文字の並び順は、色んな要素によって変わります。その要素の一つが言語。スウェーデン語もドイツ語もzやöという文字を使いますが、スウェーデン語では普通のアルファベットとは別の文字としてzの後に来ます。ドイツ語の辞書でöはoの仲間として登場するから、zよりも前に来ます。ところで、ドイツ語の辞書ではoはöよりも前に来るのに、アドレス帳ではöはoより前に来ます。また、小文字のほうが先に並ぶようにしたいときもあれば、大文字を先に並べたいときもあるでしょう。「Ж, ש, ♫, ∞, ◊, ⌂」などの文字のように順番が決まってないものもあります。並び方はどんな使い方をするかによって様々に変わります。当然Unicodeのコードポイント順とは異なります。

あ、ちなみにUnicodeで同じ文字列を表現できる方法は複数あるけれど、それらの並び順が変わったりしないように、NFD(Normalization Form D)っていう正規化形式に一旦直してから考えます。

今はもう多言語を同時に扱えること、なんてのはアプリケーションとして一般的なことであって特別なことじゃないけど、どうしよう?ってな動機で作られたのがこの規格です。

DUCET(Default Unicode Collation Element Table)って表を規格側で用意しました。実際には全ての文字列は載っておらず、日本語など、コードポイント等から計算するものもありますが。なお、並び順自体はカスタマイズ可能な方法が残されています。 ユーザーに深く関わるロケールはカスタマイズされることを前提に、それ以外のロケールの文字のそれほど不自然ではない並び順を用意しましょう、と。

この表はフォーマットの仕様によると、11C32 ; [.320D.0020.0002]0E40 0E01 ; [.3217.0020.0002][.3251.0020.0002]のように、基本的には「16進数で表されたコードポイント1つ以上」「区切りとしてセミコロン」「『角括弧内にピリオド区切りされた16進数3つ』のセットが1つ以上」を1行として、これが羅列されます。用語の定義によればこの320Dや0020や0002の非負整数をWeight、 角括弧で区切られた数値の塊をElement、数値の位置をLevelというそうです。このファイルではWeightは3つですが、Variable Weighting(後述)のようにレベル4以上を持つElementを揃えることも出来ます。Level 1のWeightをPrimary Weight, Level 2のWeightをSecondary Weight, Level 3のWeightをTertiary Weight, Level 4のWeightを Quaternary Weightとも言います。同様に、Level 1からLevel 3までのWeightが全て0なElementを Quaternary Collation Element,Level 1からLevel 2までが0なElementをTertiary Collation Element, Level 1が0のElementをSecondary Collation Element, 全てのWeightが非ゼロなときPrimary Collation Elementといいます。

各Levelの大まかな役割は、Level 1が基本文字、Level 2がアクセント、Level 3が大文字小文字、Level 4が句読点等。

これらのElement達はDUCET内で整合性(Well-Formedness)を満たす順番で並んでいます。

  • 一部の特例を除き、あるElementの、自然数なWeightの後には0となるWeightは来ない
  • n個の0であるWeightを飛ばし、最初に自然数となるWeightがあった以降のWeightは、それ以前のElementの同じLevelのWeightよりも大きい
  • VariableなElement(後述)のPrimary Weightは0ではない
  • 2つの異なるVariableなElementの間にあるElementはVariable
  • 言語によっては連続するNのCodePointに、N-1個以下のElementが載っているが、このような事例において、その最後のCodePointが結合文字等Non-Starterであるときは、最後の文字を除いたN-1個の文字もN-2以下のElementが対応する

で、ある文字列があったときに、DUCET第一列に存在する、できるだけ長い部分文字列を、その対応する1以上のElementにして順につなげることを繰り返します。この際、繋げるElementは、アクセントの扱いや、句読点の処理のため、Variable Weightingという処理を通ってからにします。

こうすると一つの文字列から1つ以上のElementが順に並んだものが生成されます。

文字列同士を比較できるキーを生成するため、各ElementのLevel 1のゼロ以外のWeightを連結したもの、それに続けてLevel 2のゼロ以外のWeightを連結したもの、という連結処理を繰り返し、これらのキー同士を比較することで文字列比較に用いることができるようになっています。

後回しにしたVariable Weightingについて。句読点をはじめとした文字達はPrimary Weightの先頭に*がついています。句読点も普通の文字として普通にDUCETのElementをくっつける方法をNon-ignorable、句読点は無いものと見なすため、Elementの全てのWeightを0として扱うのがBlanked、句読点等はほぼ無いものとみなすが句読点等同士については区別するため、0から3番目のWeightを0にしつつ4番目のWeightを設定するのがShiftedというもので、句読点等の扱いを区別したいときのカスタマイズ方法として残されています。

文字列のマッチングについては、各レベルに与えられた役割のうち、どこまでを対象とするかを設定できるようになっています。たとえばLevel 2まで対象とするななら、アクセントのある文字とない文字は別の文字と見なすが、大文字小文字は同じ文字と見なす、というものになります

ここまでの説明が非常に長かったと思いますが、準備は整ったので本題のtdf#125363について短く説明します。CalcにおけるオートフィルタはLevel 2までを対象とするため、 [.2217.0020.0002] [.213C.0020.0002] であるuoと[.2217.0020.0002] [.213C.0020.0004]を同一の文字列とみなします。以上。