バーストソート

バーストソートとその派生は、文字列をソートするためのキャッシュ効率の良いアルゴリズムです。これらは従来の基数ソートの派生ですが、一般的な文字列の大規模なデータセットに対してはより高速で、2003年に初めて公開され、その後数年にわたって最適化バージョンも公開されました。^[1]

バーストソート アルゴリズムは、文字列のプレフィックスを格納するためにトライを使用し、ソートされた一意のサフィックス (バケットと呼ばれる) を含むエンド ノードとしてポインタの拡張可能な配列を使用します。一部のバリアントでは、文字列の末尾がバケットにコピーされます。バケットが所定のしきい値を超えると、バケットはトライに「バースト」されるため、このソートに名前が付けられています。最近のバリアントでは、メモリ使用量を削減するために、より小さなサブバケットを持つバケット インデックスを使用しています。ほとんどの実装では、バケットの内容をソートするために、3 方向基数クイックソートの拡張であるマルチキー クイックソートに委任しています。入力を共通のプレフィックスを持つバケットに分割することで、キャッシュ効率の高い方法でソートを実行できます。

バーストソートは、 MSD基数ソートに似たソートとして導入されましたが、^[1]キャッシュと、トライ構造の特性により関連する基数が互いに近い場所に格納されることを考慮すると、より高速です。これは、現実世界でよく見られる文字列の特性を利用します。また、漸近的には基数ソートと同じで、時間計算量はO ( wn ) ( w – ワード長、n – ソートする文字列の数) ですが、メモリの分散が優れているため、文字列の大きなデータセットでは 2 倍の速度になる傾向があります。これは、「大規模な文字列セットをソートする最も高速な既知のアルゴリズム」と宣伝されています。^[2]

• バーストソートの派生 (C-バーストソート) はバーストソートよりも高速です: Sinha, Ranjan; Zobel, Justin; Ring, David (2006 年 1 月)。「コピーを使用したキャッシュ効率の良い文字列ソート」(PDF)。Journal of Experimental Algorithmics。11 ( 1.2): 1.2。CiteSeerX 10.1.1.85.3498。doi : 10.1145 /1187436.1187439。S2CID 3184411。2007年 10 月 1 日に オリジナル (PDF) からアーカイブ。2007年5月 31 日に取得。 
• バーストソートで使用されるデータ型: Heinz, Steffen; Zobel, Justin; Williams, Hugh E. (2002 年 4 月)。「バースト トライ: 文字列キー用の高速で効率的なデータ構造」( PDF)。ACM Transactions on Information Systems。20 ( 2): 192–223。CiteSeerX 10.1.1.18.3499。doi : 10.1145 /506309.506312。S2CID 14122377。2013年 12 月 5 日に オリジナル(PDF)からアーカイブ。2007年 9 月 25日に取得。 
• Sinha, Ranjan; Zobel, Justin (2003)。「大規模な文字列セットの効率的なトライベースソート」( PDF)。第 26 回オーストラレーシア コンピュータ サイエンス カンファレンスの議事録。第 16 巻。11 ～ 18 ページ。CiteSeerX  10.1.1.12.2757。ISBN 978-0-909-92594-9. 2012年2月8日にオリジナル（PDF）からアーカイブ。2007年9月25日に閲覧。
• Sinha, Ranjan; Wirth, Anthony (2010年3 月)。「エンジニアリング バーストソート: 高速インプレース文字列ソートに向けて」(PDF)。ACM Journal of Experimental Algorithmics。15 ( 2.5): 1–24。doi : 10.1145 /1671970.1671978。S2CID 16410080  。

• Java でのバーストソートの実装: burstsort4j
• Judy配列はコピーバーストソートの一種です: C実装