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

いよいよ今日は、皆さんお待ちかねの、#ﾅﾝﾄｶの日！#ﾅﾝﾄｶ 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で文献リストをスターリンソートする