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

いよいよ今日は、皆さんお待ちかねの、#ﾅﾝﾄｶの日！#ﾅﾝﾄｶ pic.twitter.com/BJMxT3oWRh
— 某ZR🤯 (@zr_tex8r) August 7, 2019

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

ソートされていない要素を粛清することでO(N)でソートできるスターリンソートとかいうのを見て爆笑してる
— やんぎん (@4116You) 2019年7月28日

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

対抗して 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 のスタイル作成用の専用言語で記述されています．この言語は一種の独自なプログラミング言語なのですが，正式な名称はありません．界隈¹では非公式に「BeaST 言語」や「bst 言語」などと呼ばれています．

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

$ texdoc btxhak

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

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

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

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

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

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

wtsnjp/bibstalin.bst - gist

何やらずいぶんと長い BeaST 言語コードのように見えますが，ほとんどの部分は plain.bst と共通で，私が手を加えた部分はソートに関わるわずかな部分だけです．実はさきほど言及した unsrt.bst もソート処理に該当する部分が削られているだけで plain.bst とほとんどの部分は共通です⁴．plain.bst と bibstalin.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 関数によりスターリンソートを実現しています⁵．

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

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

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

bibstalin.bst のテスト結果

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

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

ラング・ラグー

ニッチな話題をつぶさに語る

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

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

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

BibTeX のスタイル作成用言語

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