PDFから「使える」テキストを取り出す（第4回）

昨日までで、PDFからテキストを取り出すにあたり、グリフから文字を手に入れるところまでを説明しました。

いや本当のことを言うと、まだ全然説明できてないんです。でも、文字の話ばかりしていても先に進めないので、今日は（可能な場合には）PDFから文字を入手できるものとし、そこからテキストを再構築する話に進みます。

文字については改めて明後日にでも補足記事を書くかも（このシリーズはいちおう今日と明日で終わる予定）。

PDFオペレータを読むとグリフを置く場所がわかる

昨日に引き続き、次のようなテキストセクションで考えます。グリフから文字の解決は済んでいるということにして、TJオペレータの引数は文字そのものに置き換えました。

BT
  /F1
  12.4811 Tf
  125.585 -462.55 Td
  [(#1)] TJ
  /F2
  13.2657 Tf
  19.932 0 Td
  [(代数的データ型とパターンマッチの基礎)] TJ
ET

一般にPDFビューワーでは、「ページ上のどこにグリフを置くか」を、ページを抽象化した「テキスト空間」の座標として計算しています。そして、テキスト空間における現在の位置を更新するオペレータや、テキスト空間を変形させるオペレータがいくつか用意されています。スタックマシンを実行すると、そうしたオペレータにより、テキストの現在の位置が更新されていきます。その途中でTJのようなテキスト描画のためのオペレータがあれば、そこに引数のテキストが配置されます。

人間がペンで紙に文字を書くときは、腕の位置を移動させたり、逆に紙を移動させたりしながら、互いに重ならないように文字を配置していくわけですが、それと同じようなことをスタックマシンの実行によりやっている感じです。

で、上記のうちTdというオペレータが、腕の位置を動かす役目のやつです。引数を2つ取っていることがわかると思いますが、これらが動かす先のxy座標におおむね相当します。

どういうことなのか、上記の例で見てみましょう。

1つめのTdは引数として125.585と-462.55を取ります。これは直観的に解釈すると、「横方向に125.585単位、縦方向に-462.55単位だけ腕を動かす」という感じになります。そうやって腕を動かした場所に、その次に出てくるTJオペレータによって「#1」というテキストが描画されます。

同様に、2つめのTdの引数は19.932と0です。これは2つめの引数がゼロなので、縦方向には動かないっていうことだな、というのが読み取れます。横方向に少し移動し、そこで次に出てくるTJオペレータによって「代数的データ型とパターンマッチの基礎」というテキストの各文字が描画される、という具合です。

ちなみにTfというオペレータは、描画するフォントのサイズを変える働きをします。この例だと、最初の「#1」というテキストの各文字は、「フォントリソース/F1のフォントをサイズ12.4811単位で描画する」ということがわかります。同様に、次の「代数的データ型とパターンマッチの基礎」というテキストの各文字は、「フォントリソース/F2のフォントをサイズ13.2657単位で描画する」ということがわかります。

グリフを置く場所からテキストを推測する

さて、ここで注意してもらいたいんですが、ここまでに説明したPDFオペレータの動作は「PDFのページにテキストを描画する」ために用意されています。つまり、そうやって描画されたテキストをどう読めばいいのかは、この仕様からはわかりません。「各文字の座標からテキストを意味がある順番に再構築」って、いったいどうやればいいんでしょう？

それほど自明な解決方法はないような気がしますが、とりあえずPDFの仕様に戻って考えてみます。

先ほどは、TDオペレータの動きを、「xy座標に沿ってテキストを描画する位置を動かす」という、なんとなくタイプライターっぽいモデルで説明しました。実は、PDFの仕様では、こういうタイプライターモデルは使われていません。代わりに、「各文字が描画されるべき座標」を、「テキスト行列」と呼ばれる3x3行列でぐるぐる変換していくことになっています。 Tdオペレータも、実際には、このテキスト行列を更新するためのオペレータとして考えるべきです。

行列計算といっても、テキスト行列のほとんどの要素はゼロで、実際に計算に必要な値は3x3行列の9つある要素のうち6つだけです。仕様でも、これら6つの値を[a, b, c, d, e, f]という配列で管理するものとしています。

たとえば、コンテンツストリームにt1 t2 Tdというオペレータが登場したとしましょう。これにより、[a, b, c, d, e, f]というテキスト行列が、[a, b, c, d, a*t1 + c*t2 + e, b*t1 + d*t2 + f]というテキスト行列へと更新されることが単純な手計算でわかります。なので、このような行列の更新としてTdオペレータの挙動を定義できます。

さらに、こちらのほうがむしろテキストを取り出すという目的にとっては重要なんですが、このテキスト行列の更新を観察することで、「改行が発生するかどうか」を推測できます。何を根拠にして推測するかというと、とりあえずPDFが横書きだと想定し、「次の2つのいずれかの状況になったら、このTdオペレータによって次のテキスト描画のタイミングで改行が発生する」と決めます。

現在のテキストの横方向の位置が、行列変換によって、それまでよりも小さくなった（改行が発生していなければ右になるはず）
現在のテキストの縦方向の位置が、行列変換によって、それまでと極端に変わった（改行が発生していなければほぼ同じになるはず）

テキスト行列に変化をもたらすオペレータは、TdのほかにTmなどがあります。それらのオペレータの仕様の記述をにらみながら、同様の推測をすることで、「人間が期待するような順番でテキストを再構築」しようというわけです。

ちなみに今の話に直接は関係ないですが、文字を取り出すのにOCRするアプローチでも、この「人間が読む順番を表現したメタ知識をどうやって与えてあげるか」という問題の解決策は必要になりますね。コンテンツストリームから取り出すのとは別のヒューリスティックが必要になるような気がします。

PDFのページ上のテキストをhpdftで取り出す

グリフから文字を取り出せるようになり、テキスト行列をだいたい制御できるようになったら、いよいよPDFのページからテキストを取り出せます！

hpdftでは-pオプションでページ番号を指定してテキストを抜き出せるようにしてあります。

$ hpdft -p 1 NML-book.pdf

#1 代数的データ型とパターンマッチの基礎 3een
#2 パターンマッチ in Ruby 辻本 和樹
Vol.1, No.3
Nov . 2019

だいたい期待どおりの改行位置とスペーシングでテキストが抜き出せてますね！ただ、3eenという文字列は本当ならκeenとなってほしいので、CMapの扱いはもうちょっと詰める必要がありそうです。

ちなみに、このくらいであれば、pdftotextのような既存のツールでもだいたい意図したとおりに改行とスペーシングを見つけ出してくれます。さすが、「κ」もちゃんと変換できてますね。

$ pdftotext -f 1 -l 1 NML-book.pdf
$ cat NML-book.txt
#1 代数的データ型とパターンマッチの基礎 κeen
#2 パターンマッチ in Ruby 辻本 和樹

Vol.1, No.3
Nov . 2019

ただ、もうちょっとテキストが多いページになると、pdftotextの出力結果はわりと破綻してきます。同じPDFの7ページはこんな感じ。

$ pdftotext -f 7 -l 7 NML-book.pdf
$ cat NML-book.txt
Lambda Note

1.2 SML♯ の REPL で速習 SML

3

本記事には、特に断りがない限り、処理系依存のコードは登場しません。そのた
め、本記事を読むうえでは、規格を満たす処理系であれば上記に限らず何を利用して
も問題ないはずです。
C と SML 以外の言語の話も少しだけ出てきます。それらについては、想定する処理

系をそのつど個別に記載します。

1.2 SML♯ の REPL で速習 SML
パターンマッチの話題に入る前に、SML の基本的な挙動を確認しておきましょう。
幸い SML♯ には REPL（対話的実行環境）があるので、これを利用して以降の解説に必
要な最低限の情報をまとめます。
シェルから smlsharp として SML♯ を起動すると、下記のように REPL が立ち上が
ります。 # が SML♯ のプロンプト記号です。
1
2
3

$ smlsharp
SML# 3.4.0 (2017-08-31 19:31:44 JST) for x86_64-pc-linux-gnu with LLVM 3.7.1
#

hpdfだと同じ範囲はこうなります。

$ hpdft -p 7 NML-book.pdf

Lambda Note 1.2 SML ♯のREPL で速習 SML 3
Vol.1, No.3(2019)-#1
? SML: SML ♯?33.4.0
? C: GCC 8.3.0
本記事には、特に断りがない限り、処理系依存のコードは登場しません。そのた
め、本記事を読むうえでは、規格を満たす処理系であれば上記に限らず何を利用して
も問題ないはずです。
C とSML 以外の言語の話も少しだけ出てきます。それらについては、想定する処理
系をそのつど個別に記載します。
1.2 SML ♯のREPL で速習 SML
パターンマッチの話題に入る前に、 SML の基本的な挙動を確認しておきましょう。
幸い SML♯には REPL （対話的実行環境）があるので、これを利用して以降の解説に必
要な最低限の情報をまとめます。
シェルから smlsharp として SML♯を起動すると、下記のように REPL が立ち上が
ります。 #がSML♯のプロンプト記号です。


1 $smlsharp ?
2 SML# 3.4.0 (2017-08-31 19:31:44 JST) for x86_64-pc- linux-gnu with LLVM 3.7.1
3 #