BibTeX でもスターリンソートしてみる

2019-08-08   #BibTeX  #TeX 

最近まるでブログを更新できていませんでしたが,今日はゆきだるまの日なので記事を書くことにしました.ただし今年のネタはゆきだるまとはあまり関係がありません.予めご了承ください.

さて,1週間ほど前に Twitter で「スターリンソート」と呼ばれる斬新なソートアルゴリズムが提案され,話題になりました.

そして,おなじみの流れですが種々の言語でスターリンソートを実装するのがプチ流行しています.

対抗して TeX 言語や expl3 で実装してみてもいいですが,それは賢明な読者諸氏に託すことにして,今回はまったく別の言語でその実装に挑戦してみます.

BibTeX で文献リストをソートする

変態な TeX 言語者を除くフツーの (La)TeX ユーザにとって,TeX による文書作成で「ソート」を意識するのは索引や文献リストを作成するときでしょう.このうち文献リストの作成について,それを実現する方法はいくつかありますが,古典的には BibTeX がよく用いられてきました.例えば BibTeX の標準スタイル plain.bst を用いると,文献リストは著者名の辞書順にソートされて表示されます.

少し具体例を見てみましょう.まず文献データベース (*.bib) を用意します.

% bibstalin1.bib
@article{kuroyuki,
  author = {Kuroyuki, Daruma},
  title = {Snowmen conquer the world},
  journal = {Journal of Snowmen},
  year = 2019,
}

@article{duck,
  author = {Duck, Taro},
  title = {Hisroty of the duck revolution},
  journal = {Ducks Communication},
  year = 1986,
}

@article{yuki,
  author = {Yuki, Daruma},
  title = {Variety of font glyphs for snowmen},
  journal = {Journal of Snowmen},
  year = 2016,
}

続いて文献リストを載せる LaTeX 文書ソースを作成します.

% bibtest.tex
\documentclass[a4paper]{article}
\begin{document}
\bibliographystyle{plain}
\nocite{*}
\bibliography{bibstalin1}
\end{document}

これを通常の LaTeX + BibTeX 実行方法で処理します.念のため確認しておくと,例えば pdfLaTeX 利用なら次のようになります:

$ pdflatex bibtest
$ bibtex bibtest
$ pdflatex bibtest

上記の例では \cite を使用していないので必要ありませんが,多くの場合 BibTeX 実行後の pdfLaTeX 実行は複数回行う必要があります.ちなみに拙作 llmk を用いる場合は

source = "bibtest.tex"
latex = "pdflatex"

[programs.bibtex]
cmd = "bibtex"
target = "bibstalin1.bib"

という内容を llmk.toml に記述し llmk コマンドを1回実行するだけで求める出力結果が得られます.

$ llmk

どんなビルド方法を用いてもよいですが,いずれにせよ成功すると次のように著者名でソートされた文献リストが得られます.

plain.bst のテスト結果

BibTeX で文献リストをソートしない

さきほど BibTeX を使用して文献リストを作成したところ,リストは著者名について辞書順にソートされましたが,それは BibTeX の規定機能というわけではなく,あくまで plain.bst によってそう指定されているに過ぎません.BibTeX の標準スタイルには unsrt.bst というソートを行わないもの(それ以外の点では plain.bst とまったく同じ)もあります.

さきほどの LaTeX ファイルを少しだけ書き換えて次のようにします.

\documentclass[a4paper]{article}
\begin{document}
\bibliographystyle{unsrt}
\nocite{*}
\bibliography{bibstalin1}
\end{document}

この場合,文献リストは一切ソートが行われないまま出力されます.\cite を用いて通常通り文献を引用した場合は引用の登場順,今回のように \nocite{*} で一気に読み込んだ場合は bib データベースでの出現順のリストになります.

したがって,さきほどと同じ要領で PDF を生成すると次のような出力結果となります:

unsrt.bst のテスト結果

BibTeX のスタイル作成用言語

BibTeX による文献作成ではソートの有無(やその方法)は BibTeX スタイル (*.bst) で指定されていることがわかりました.では,これらの指示は一体どのように行われているのでしょうか?

実際に bst ファイルの中身を覗いてみるとわかりますが,bst ファイルは BibTeX のスタイル作成用の専用言語で記述されています.この言語は一種の独自なプログラミング言語なのですが,正式な名称はありません.界隈1では非公式に「BeaST 言語」や「bst 言語」などと呼ばれています

この言語についての情報はあまりありませんが,TeX Live に含まれる Designing BibTeX Styles (btxhak.pdf) という文書に最低限の解説があります2

$ texdoc btxhak

また BeaST 言語により記述された実際のソースコードを読んでみたい場合は btxbst.doc という標準 BibTeX スタイルの実装を見るとコメントに詳しい解説も記されています.このファイルは TeX Live なら例えば次のようにすると簡単に閲覧できるでしょう:

$ less $(kpsewhich --format=doc btxbst.doc)

さて,本題の BibTeX スタイルにおけるソート方法指定の仕方についてですが,さすがに BeaST 言語でソートアルゴリズムを自前実装する必要はなく,SORT という組み込みのコマンドを実行すると sort.key$ という規定の変数をキーとして BibTeX 本体がソートを行ってくれることになっています.BibTeX の実装を読むと,裏ではクイックソートが用いられていることがわかります3

クイックソートといえば平均計算量の $O(n\log n)$ の低速アルゴリズム(えっ)で,特にすでに整列済みの入力を与えようものなら最悪計算量の $O(n^2)$ になってしまいます.これでは長い文献リストを処理する人は困ってしまいますね(えっえっ).というわけで,plain.bst を改造して $O(n)$ のスターリンソートを行うようにしてみましょう(えっえっえっ).

BibTeX で文献リストをスターリンソートする

導入が長くなりましたが,クイックソートの代わりにスターリンソートで文献リストを整列する BibTeX スタイルを作ってみました.

何やらずいぶんと長い BeaST 言語コードのように見えますが,ほとんどの部分は plain.bst と共通で,私が手を加えた部分はソートに関わるわずかな部分だけです.実はさきほど言及した unsrt.bst もソート処理に該当する部分が削られているだけで plain.bst とほとんどの部分は共通です4plain.bstbibstalin.bst の diff を取るとこんな感じになります:

1051,1052d1051
< SORT
<
1090c1089,1126
< ITERATE {call.type$}
---
> INTEGERS { purge cursor tmp.chr.a tmp.chr.b }
>
> STRINGS { last.key current.key }
>
> FUNCTION {stalin.compare.str}
> { #1 'cursor :=
>   last.key empty$
>     { #0 'purge := }
>     { #-1 'purge :=
>         { purge #0 < }
>         { current.key cursor #1 substring$ chr.to.int$ 'tmp.chr.a :=
>           last.key cursor #1 substring$ chr.to.int$ 'tmp.chr.b :=
>           tmp.chr.a tmp.chr.b =
>             { cursor #1 + 'cursor := }
>             { tmp.chr.a tmp.chr.b <
>                 { #1 'purge := }
>                 { #0 'purge := }
>               if$
>             }
>           if$
>         }
>       while$
>     }
>   if$
> }
>
> FUNCTION {stalin.print}
> { sort.key$ 'current.key :=
>   stalin.compare.str
>   purge not
>     { current.key 'last.key :=
>       call.type$
>     }
>     'skip$
>   if$
> }
>
> ITERATE {stalin.print}

SORT コマンドによりソートを行う部分を削除して,代わりに文献リストの出力処理の中で stalin.print 関数によりスターリンソートを実現しています5

さて,既にお察しのことと思いますが,この BibTeX スタイルを使用するには下記のような LaTeX 文書を用意します.

\documentclass[a4paper]{article}
\begin{document}
\bibliographystyle{bibstalin}
\nocite{*}
\bibliography{bibstalin1}
\end{document}

このソースを例によって LaTeX + BibTeX で処理すると,次のような文献リストが得られます.

bibstalin.bst のテスト結果

どうやら Duck さんの文献が「粛清」されてしまったようですが,整列された文献リストが得られたので世界平和が保たれました.めでたしめでたし☃


  1. 「界隈」と言いましたが実質約1名かもしれません. [return]
  2. このドキュメントは BibTeXing (btxdoc.pdf) という文書の続きということになっており,そのため btxhak.pdf 自体はセクション5から始まるという構成になっていますが,BeaST 言語の習得のみが目的の場合は btxdoc.pdf を読む必要は特にありません. [return]
  3. 具体的には bibtex-3.c にその実装があります. [return]
  4. BibTeX には「DRY 原則」や「モジュール化」といった概念はないようですね…… [return]
  5. ジョーク BibTeX スタイルなので,境界ケースのケアなどはまったく考慮していません.ご了承ください. [return]