String Sort Library

Multikey Quicksort

マルチキークイックソート ( Multikey Quicksort, Ternary Quicksort )は, 大量の文字列を整列するのに適した整列手法です. 文字単位の比較に基づいて整列を進めるという特徴があり, 通常のクイックソートなどより高速に文字列を整列できます.

クイックソートで大量の文字列を整列する場合の問題は,整列の終盤において, 前半部分が一致している文字列同士を何度も比較しなければならないことです. 通常,文字列の比較は先頭の文字から順に照合をおこなうので, とても効率が悪くなります.

一方,マルチキークイックソートでは, クイックソートの基本である分割を文字単位で進めるので, 前半の一致部分に対する比較を繰り返す必要がありません. 詳細については他に説明しているサイトがありますので, そちらを参照していただきたいと思います.
Algorithms with Python
Sorting and Searching Strings

Introduction

SZSort は, 基数ソート( Radix Sort ), マルチキークイックソート ( Multikey Quicksort, Ternary Quicksort ), 挿入ソート( Insertion Sort ) を併用して大量の文字列を高速に整列するためのライブラリです. 重複している文字列を検出する機能があり, 文字列の重複を見つけた時点で整列を中止したり, 各文字列の重複数を求めたりすることができます.

マクロ版( szsort_macros.h )は, マクロを使って関数を定義するという凶悪な仕様になっているため, 使い方に癖がある上にデバッグが困難になる恐れがあります. C++ が使えるのであれば, テンプレート版( szsort.h )の使用を推奨します. ただし,作者が C++ に慣れていないので, 問題が含まれているかもしれません. 問題を見つけた方は,連絡していただけると助かります.

テンプレート版とマクロ版では提供する機能が異なります. テンプレート版では Unicode も扱えますが, マクロ版では扱えません. 一方,マクロ版には基数ソートを併用して動的に確保した領域に整列結果を 格納して返す機能がありますが,テンプレート版では提供していません.

Source

利用や再配布などに関する制限はありません. 自己責任にてお使いください.

szsort-301.tgz - 3,128 bytes
szsort-300.tgz - 2,828 bytes
szsort-203.tgz - 2,646 bytes
szsort-202.tgz - 2,605 bytes
szsort-202-macros.tgz - 2,946 bytes
szsort-201.tgz - 4,725 bytes
szsort-200.tgz - 4,765 bytes
szsort-100.tgz - 2,876 bytes

Visual Studio 2005MinGW gcc 3.4.5 で動作確認をしています.

Update

December 20, 2007 - Version 3.01
コメントを修正しました.
December 18, 2007 - Version 3.00
typeof は環境依存なのでやめました.
HandleSameKeysbool を返り値とするようように変更しました.
false を返すことによって整列を中止できます.
いくつかの inline を消しました.
December 17, 2007 - Version 2.03
typeof を使って GetLetter の返り値の型を取得するように変更しました.
size_t の代わりに std::size_tを使うように変更しました.
December 16, 2007 - Version 2.02
マクロ版とテンプレート版を分割しました.
ヘッダに少し修正を加えて,サンプルのファイル名を変更しました.
December 12, 2007 - Version 2.01
無駄にインクルードしていたヘッダを外しました.
December 11, 2007 - Version 2.00
テンプレート版を追加して,マクロ版のファイル名を変更しました.
December 9, 2007 - Version 1.00
動く状態になったので公開します.

Template version

szsort.h からの抜粋になりますが, 以下のような関数を提供します.

// マルチキークイックソートと挿入ソートを使って文字列を整列
// 引数:
//  l, r            整列したいデータの範囲 [l, r)
//  depth           整列には depth 以降の文字を使用
//  GetLetterType   各メンバから文字を取り出す関数
//  HandleSameKeys  重複している文字列を見つけたときに呼び出される関数
template <typename RandomAccessIterator, typename GetLetter,
          typename HandleSameKeys>
inline void  StringSort::Sort(
    RandomAccessIterator l, RandomAccessIterator r, size_t depth,
    GetLetter get_letter, HandleSameKeys handle_same_keys);

StringSort::Sort による整列では, 文字を参照するために関数 GetLetter を呼び出します. また,重複している文字列を発見した場合, 関数 HandleSameKeys を呼び出します. これらの関数は使用者が準備するものであり, 以下のように関数オブジェクトとして定義してやると効率が出ます. HandleSameKeys を省略した場合, 文字列の重複を見つけても何もしません.

// データから文字を取り出す
struct GetLetter {
  unsigned operator()(const Key &key, size_t depth) {
    return (unsigned char)key.str[depth];
  }
};
// 重複している文字列を受け取る
// false を返すと整列を中止する
struct HandleSameKeys {
  bool operator()(Key *l, Key *r) {
    std::cout << key.str << std::endl;
    return true;
  }
};

Macro version

szsort_macros.h からの抜粋になりますが, 以下のようなマクロを提供します.

// マルチキークイックソートと挿入ソートを併用する関数を定義
// 定義する関数の名前を StringSort に指定する
// 配列のメンバの型を Type に指定する
// Type から文字を取り出す関数を GetLetter に指定する
// 同じ文字列を見つけたときに呼び出される関数を HandleSameKeys に指定する
DEFINE_SZSORT(StringSort, Type, GetLetter, HandleSameKeys);
// 基数ソートとマルチキークイックソートと挿入ソートを併用する関数を定義
// 定義する関数の名前を HugeStringSort に指定する
// 残りは DEFINE_SZSORT と同じ
DEFINE_HSZSORT(HugeStringSort, Type, GetLetter, HandleSameKeys);

マクロ版の SZSort では, 関数の名前,整列対象の型,その型から文字を取り出す関数, 重複する文字列の取り扱いを規定する関数を引数するマクロにより関数を定義します. 関数のポインタを使用せずにマクロで埋め込むようにした理由は, コンパイラによるインライン化を可能にするためです.

定義される関数の例を以下に示します.

// 文字列を持つデータを整列
// l, r には整列したいデータの範囲 [l, r) を指定する
// depth には整列の基準として使用する文字の位置を指定する
// depth = 7 とした場合,8 文字目以降のみを使って整列する
// 先頭に "http://" のような共通する文字列を持つ場合に利用できる
static void  StringSort(Type *l, Type *r, size_t depth);
// 文字列を持つデータを整列
// StringSort() とは異なり,新たに確保した領域に整列結果を入れて返す.
// 返された領域は呼び出し側で解放しなければならない.
static Type  *HugeStringSort(Type *l, Type *r, size_t depth);

StringSortHugeStringSort による整列では, 文字を参照する度に関数 GetLetter を呼び出します. また,重複している文字列を発見した場合, 関数 HandleSameKeys を呼び出します. これらの関数は使用者が準備するものであり, 以下のように定義する必要があります.

// データから文字を取り出す
static  unsigned char  GetLetter(const Type *key, size_t depth);
// 重複している文字列を受け取る
static  void  HandleSameKeys(Type *l, Type *r);

Sample

szsort_macros_test.c(マクロ版)と szsort_test.cppszsort_file_test.cpp(テンプレート版) を参考にしてください.

To Do

テスト用のコードを充実させたいと思っています.

References

Back
Last-Modified: December 20, 2007