LlosLabソフトウェア開発ブログPDF、Delphi、およびドキュメントソフトウェア開発者向けのエンジニアリングノート。

技術記事

Uniscribe なしの PDF テキスト向け BiDi 埋め込みレベル

PDFium Component

Uniscribe は、ほとんどの呼び出し側が思うより多くの仕事をしています。ScriptItemize は双方向分析とスクリプト分割を 1 パスで行い、ScriptLayout はでき上がったランの視覚順を生み出します。多くの人が手を伸ばすポータブルな代替、HarfBuzz はどちらも行いません。誰かがすでに方向とスクリプトを決めた単一のランをシェープするだけです。したがって、Windows の PDF テキストパイプラインを Linux や macOS へ持っていくことの難所は、シェーピングエンジンをバインドすることではありません。Uniscribe が黙って提供していた双方向アルゴリズムを供給することであり、PDFium コンポーネントでは、それが FPdfBidi の役割です

このユニットは UAX #9 を直接実装します。段落方向のための P2 と P3、明示的な埋め込みと isolate のための X1 から X10、弱い型のための W1 から W7、中立と括弧のための N0 から N2、暗黙レベルのための I1 と I2、そして最終的な並べ替えのための L1 と L2 です。2 つの関数がこれを担います。PdfResolveBidiLevels は UTF-16 コードユニットごとに 1 つの埋め込みレベルを返し、PdfBidiVisualOrder はそれらのレベルを、コードユニットを左から右へ置く順列に変えます

アルゴリズムが与えるものと、与えないもの

与えるのは数です。偶数レベルは左から右、奇数レベルは右から左であり、各文字のレベルは、その文字が座っている方向ランのネストをエンコードします。L2 はそれらの数から順列を導きます。アルゴリズムが意図的にしないのは、どのフォントを使うかの決定、合字の形成、クラスタ内のグリフの並べ替えです。それらはシェーピングの関心事であり、この次の段階に属します

Uniscribe なしの PDF テキスト向け FPdfBidi パイプライン。PdfResolveBidiLevels が UTF-16 コードユニットごとに UAX #9 埋め込みレベルを割り当て、PdfBidiVisualOrder が規則 L2 を適用して視覚順を生み出す。
レベルはランのネストをエンコードし、規則 L2 がそれらを、左から右へ読む順列へ変えます
uses
  FPdfBidi;

var
  Levels: TPdfBidiLevels;
  Order: TPdfBidiOrder;
  ParagraphLevel: Byte;
  Text, Visual: WideString;
  I: Integer;
begin
  Text := SourceLine;
  // pbdAuto は P2-P3 を適用する：最初の強い文字が決める
  if PdfResolveBidiLevels(Text, pbdAuto, Levels, ParagraphLevel) then
  begin
    Order := PdfBidiVisualOrder(Text, Levels);
    SetLength(Visual, Length(Order));
    for I := 0 to High(Order) do
      Visual[I + 1] := Text[Order[I] + 1];
    // Visual は今や左から右へ読める。Levels[] は今もどのランが
    // RTL かを告げるため、シェーパーへ正しい方向を渡せる
  end;
end;

文字クラスのテーブルは生成されるものであり、書かれるものではない

すべてのコードポイントは Bidi_Class プロパティを持ち、アルゴリズムはそれを絶えず参照します。したがってテーブルは、他のすべてが立つ土台です。手で保守されるのではなく、Unicode Character Database から生成されます。UnicodeData.txt の第 5 フィールドが割り当てられたクラスを与え、DerivedBidiClass.txt の @missing 宣言が、データベースが割り当てないコードポイントの既定値を与えます。未割り当てブロックが L ではなく正しく R、AL、ET、BN を既定とする仕組みです

圧縮の工夫は、クラスが L でない範囲だけを出力することです。どの範囲にも落ちないものは L であり、これは Unicode の既定でありかつ圧倒的多数のコードポイントのクラスでもあります。これにより、そうでなければ数千エントリに及ぶテーブルが、745 範囲と約 6.7 KB に収まります。運用上の帰結は述べる価値があります。新しい Unicode バージョンへ移るときは、ジェネレータを再実行してください。include ファイルを手で編集しても動きますが、次のアップグレードでデータベースと黙って分岐します

L2 が並べ替えるのはコードポイントであり、UTF-16 コードユニットではない

これは本当に破損した出力を生むミスであり、最初の実装がやりました。L2 は、最高位から最も低い奇数レベルまで、各レベルで連続するランを逆順にせよと言います。UTF-16 文字列に対して書くと、「ランを逆順にする」は自然に、その中のコードユニットを逆順にすることを意味します。Basic Multilingual Plane の文字ならそれで構いません。追加面の RTL 文字、たとえば U+10800 付近のキプロス文字や南アラビア文字のブロックのものはそうはいきません。その文字はサロゲートペアであり、ランを逆順にすると下位サロゲートが上位の前に来て、文字列は 1 つの文字の代わりに 2 つのペアでないサロゲートを含むことになります。下流の何ものもこれを復元できません

修正は、L2 をコードポイント単位で行うことです。実装はコードユニットをコードポイント単位へ併合し、それらの単位に対して逆順を行い、最後に結果をコードユニットのインデックスへ展開し戻します。PdfBidiVisualOrder が、レベル配列だけでなくテキストを受け取るのはこのためです。レベルだけからは、サロゲートの境界がどこか分からないからです。同じサロゲートペアの規律はテキスト API 全般を貫いており、絵文字、CJK とサロゲートペアの記事に述べています

双方向並べ替えでのサロゲートペア破損。UTF-16 コードユニットの逆順は U+10800 付近の追加面文字をペアでないサロゲートへ分裂させ、併合済みコードポイント単位の逆順は文字を無傷に保つ。
規則 L2 は、逆順にする前にコードユニットをコードポイントへ併合し、その後で展開し戻さなければなりません

レベルの降下は、現れないレベルも含まなければならない

2 つ目のミスはより微妙であり、クラッシュを生まず、ただ並べ替えられていないテキストを生みます。L2 は、存在する最高レベルから始め、最も低い奇数レベルまで降りるように言います。自然な最適化は、実際に現れるレベルの集合を収集し、その集合に対して反復することです。それは誤りです

右から左の埋め込みの内側にあるラテン文字の 1 行を考えてください。段落レベルは 0 であり、埋め込みはラテン文字をレベル 2 へ押し上げ、レベル 1 に座る文字はありません。現れるレベルに対する反復は 0 と 2 だけを見つけ、奇数レベルはまったくないため、ループは逆順を行いません。その答えは正しいです。しかし、最適化が知らない理由で正しいのです。レベル 2 の逆順にレベル 1 の逆順が続くと正確に打ち消し合うため、どちらも行わないのが正しい帰結です。入力を少し変え、レベル 1 とレベル 3 の文字が存在するがレベル 2 が存在しないようにすると、集合ベースのループは、アルゴリズムが必要とするレベル 2 の逆順をスキップします

// 正しい：最大から最も低い奇数レベルまで、実際にどの文字も
// 持たないレベルを含めてすべてのレベルを歩く
Level := MaxLevel;
while Level >= LowestOddLevel do
begin
  ReverseRunsAtOrAbove(Level);   // 条件を満たすランがないときは no-op
  Dec(Level);
end;

単純な減少ループとして書けば、振る舞いはおまけのように得られ、no-op の反復は測定可能な代償を払いません。これは、自明な最適化がわずかに誤りなのではなく、小さなテストコーパスでは決して明らかにならない、入力依存の形で誤りであるケースです

UAX #9 の BiDi レベル降下の落とし穴。現れるレベルだけの反復は必要なレベル 2 の逆順をスキップし、MaxLevel から最も低い奇数レベルまでの単純な減少ループは常に正しく並べ替える。
最も低い奇数レベルまですべてのレベルを歩くのは、代償ゼロであり、必要な逆順をスキップすることも決してありません

括弧：実用的なテーブルによる BD16

規則 N0 と BD16 の括弧ペアアルゴリズムが存在するのは、混合方向テキストの中の括弧が、たまたま隣にあるものではなく、囲むものの方向へ解決されるようにするためです。これには括弧ペアのテーブルが必要です。実装は、Unicode の括弧ファイルの全内容ではなく、一般に使われるペアを運びます。ASCII、CJK、全角、数学、装飾の括弧です

一覧にない括弧はエラーではありません。N1 と N2 を通って普通の中立として解決されます。Unicode 6.3 が N0 を導入する前にすべての実装が持っていた振る舞いとまったく同じです。したがって境界は「まれな括弧に対する洗練の欠如」であって「不正確」ではありません。明示的な処理を必要とする細部が 1 つあります。U+2329 と U+232A の角括弧と U+3008 と U+3009 の角括弧の間の正準等価は、ペアの照合時に折りたたまなければなりません。さもないと、ある書き方で書かれた開き括弧が、別の書き方で書かれた閉じ括弧とペアを組みに失敗します

相互作用する 30 の規則をどうテストするか

大きなコーパスでは、少なくとも最初は違います。生産的だった方法は、手で検証した 16 ケースでした。それぞれが特定の規則を試すよう選ばれ、それぞれが UAX #9 が生むべきと言うレベルと照合されました。P2 と P3 の下の段落方向の検出、弱い型の規則 W2、W3、W7、暗黙レベルの規則 I1 と I2、X2 と X7 による明示的埋め込み、X5a と X6a による isolate、末尾の空白と区切りの L1 リセット、N0 の括弧ケース、そしてサロゲート処理を固めるための追加面文字を含む 1 ケースです

既知の正しい期待レベルを持つ 16 ケースは、もっともらしい外見の出力を持つ 1600 ケースよりも多く捕まえます。双方向実装の障害モードは、ほとんど正しく読めるテキストだからです。これらが通った後は、コーパスがテーブルの隙間と性能問題を見つけるのに役立ちます。それらは別のクラスの欠陥です

PDFium コンポーネントの内部では、レベルは 2 つの消費者に供給されます。書き込み側では、シェーピングバックエンドへ各ランの方向を告げます。HarfBuzz が必要とする入力です。読み取り側では、選択ジオメトリと読み順を知らせます。RTL テキストの中のクリックは、視覚位置ではなく論理位置へ対応しなければならないためです。その対応は視覚行選択の記事に、読み順モデルは構造化テキストブロックと読み順にあります。コンポーネントのプラットフォーム対応の詳細は、PDFium Delphi component の製品ページにあります