文字列の中に数値があるような場合、ソートの時にその数値の桁がそろっていないと意図しない順番になることがあります。

a1
a10
a2

のようなケースです。実際には

a1
a2
a10

のように数字順に並んでほしいですよね、それを実現するのが自然順ソート(Natural Sort) です。

アルゴリズム

以下のURLに詳細なアルゴリズムが記述されています。

Natural Order String Comparison

ただ、いかんせん英語なのであまり理解ができませんでした。

同ページにC言語で記述されたソースコードへのリンク(http://sourcefrog.net/projects/natsort/strnatcmp.c) があったので、それをもとに私の理解を以下に記します。

文字列を1文字ずつ走査して数値が出現したタイミングで数値比較を行います。ゼロパディング(数値の頭をそろえるために0埋めすること)をされている場合は左寄せ比較(文字列比較とほぼ等価の比較)を行い、それ以外の場合は右寄せ比較を行います。右寄せ比較では桁数が判明するまで1文字ずつ数値比較を行い、桁数が判明した段階で、大小関係を確定させます。また、空白は無視します。結構単純なアルゴリズムですが、これだけのことで数値があべこべにならずにソートされます。

左寄せ比較

左寄せ比較では、文字が数値以外になるまで左から順番に文字比較を行います。数値がイコールなら次の文字を比較し、大小関係が判明すればその時点で比較は終了します。もし、数値以外の文字がどちらかの比較文字に現れた場合は、もう片方の数値より桁が小さいということになり、その時点で大小関係が判明するので比較は終了します。もし同時に数値ではない文字が現れた場合は数値部分はイコールとなり、文字列比較を続けます。

例1 : ゼロパディングされた数値

A: 0012
B: 0135

A[0] -> 0, B[0] -> 0 : 数値なので数値比較, 数値が0なので左寄せ比較
A[1] -> 1, B[1] -> 0 : A[1] < B[1] なので A < B となり比較終了

例2 : 数値以外の文字が後ろにつくケース

A: 01a
B: 015

A[0] -> 0, B[0] -> 0 : 数値なので数値比較, 数値が0なので左寄せ比較
A[1] -> 1, B[1] -> 1 : 数値がイコールなので次の文字を比較
A[2] -> a, B[2] -> 5 : A[2]が文字なので、Bのほうが数値の桁数が多いと
                       判断できるため、A < B となり比較終了

例3 : 数値が文字列中に複数回存在する場合

A: 0a03a
B: 0a02b

A[0] -> 0, B[0] -> 0 : 数値なので数値比較, 数値が0なので左寄せ比較
                       数値はイコールなので次の文字を比較
A[1] -> a, B[1] -> a : 数値以外の文字が出現したので左寄せ数値比較は行わず
                       文字比較を行う。比較の結果イコールであるため
                       次の文字を比較
A[2] -> 0, B[2] -> 0 : 数値なので数値比較, 数値が0なので左寄せ比較
                       数値はイコールなので次の文字を比較
A[3] -> 3, B[3] -> 2 : A[3] > B[3] なので A > B となり比較終了

右寄せ比較

右寄せ比較では、左寄せ比較と同様に左から一文字ずつ数値比較を行いますが、大小関係が判明しても比較を終了せず、桁数が判明するまで大小関係を保持します。桁数が同じだった場合、保持していた大小比較でもって大小判定を行い、桁数が違った場合は桁数で大小判定を行います。

例1 : 桁数が同じ場合

A: a20
B: a15

A[0] -> a, B[0] -> a : 文字列比較、イコールなので次の文字を比較
A[1] -> 2, B[1] -> 1 : A > B となるが、桁数が確定しないので、大小比較結果を保存し、次の文字を比較
A[2] -> 0, B[2] -> 5 : 数値の続きなので、比較をスキップし次の文字を比較
A[3] -> *, B[3] -> * : 両方が終端に達し、桁数が同じなので、保存していた大小結果を最終結果とする

例2 : 桁数が違う場合

A: a2b
B: a15c

A[0] -> a, B[0] -> a : 文字列比較、イコールなので次の文字を比較
A[1] -> 2, B[1] -> 1 : A > B となるが、桁数が確定しないので、次の文字を比較
A[2] -> b, B[2] -> 5 : Aが終端に達したので 桁数が A < B となり、大小判定が確定

Goでの実装

2019/4/16 AM 8:00 追記

すでに実装があるので、そちらを見ていただいたほうがいいと思います。 mattn.kaoriya.net せっかくなので以下のソースは残しておきます。

2019/4/17 追記

改良版書きました!!

自然順ソート(マルチバイト対応改良版 & Windows エクスプローラー準拠) - bamch0h’s diary

Goでの実装はこんな感じになります。もうちょっとうまく書く方法がありそうですが、さしあたってはうまく動いているようです。

package main

import (
    "fmt"
    "sort"
    "unicode"
)

func compareLeft(a, b string) int {
    var ai, bi int
    for {
        if (len(a) <= ai || !unicode.IsDigit(rune(a[ai]))) && (len(b) <= bi || !unicode.IsDigit(rune(b[bi]))) {
            return 0
        }

        if len(a) <= ai || !unicode.IsDigit(rune(a[ai])) {
            return -1
        }

        if len(b) <= bi || !unicode.IsDigit(rune(b[bi])) {
            return 1
        }

        ca, cb := rune(a[ai]), rune(b[bi])

        if ca < cb {
            return -1
        }

        if ca > cb {
            return 1
        }

        ai++
        bi++
    }
}

func compareRight(a, b string) (bias int) {
    for ai, bi := 0, 0; ; ai, bi = ai+1, bi+1 {
        if (len(a) <= ai || !unicode.IsDigit(rune(a[ai]))) && (len(b) <= bi || !unicode.IsDigit(rune(b[bi]))) {
            return bias
        }

        if len(a) <= ai || !unicode.IsDigit(rune(a[ai])) {
            return -1
        }

        if len(b) <= bi || !unicode.IsDigit(rune(b[bi])) {
            return 1
        }

        ca, cb := rune(a[ai]), rune(b[bi])

        switch {
        case ca < cb:
            if bias == 0 {
                bias = -1
            }
        case ca > cb:
            if bias == 0 {
                bias = 1
            }
        }
    }
}

func getRune(s string, i int) (rune, int) {
    for x := i; x < len(s); x++ {
        if unicode.IsSpace(rune(s[x])) {
            continue
        }
        return rune(s[x]), x
    }
    return rune(0), len(s)
}

func natualSort0(a, b string) int {
    var ca, cb rune
    for ai, bi := 0, 0; ; ai, bi = ai+1, bi+1 {
        if len(a) <= ai && len(b) <= bi {
            return 0
        }

        if len(a) <= ai {
            return -1
        }

        if len(b) <= bi {
            return 1
        }

        ca, ai = getRune(a, ai)
        cb, bi = getRune(b, bi)

        if unicode.IsDigit(ca) && unicode.IsDigit(cb) {
            if ca == '0' || cb == '0' {
                if ret := compareLeft(a[ai:], b[bi:]); ret != 0 {
                    return ret
                }
            } else {
                if ret := compareRight(a[ai:], b[bi:]); ret != 0 {
                    return ret
                }
            }
        }

        if ca < cb {
            return -1
        }

        if ca > cb {
            return 1
        }
    }
}

func naturalSort(strings []string) func(i, j int) bool {
    return func(i, j int) bool {
        return natualSort0(strings[i], strings[j]) <= 0
    }
}

func dumpByNaturalSort(strings []string) {
    sort.Slice(strings, naturalSort(strings))
    for i, s := range strings {
        if i != 0 {
            fmt.Print(" < ")
        }
        fmt.Printf("%+v", s)
    }
    fmt.Println()
}

func main() {
    dumpByNaturalSort([]string{"a20", "a10", "a2", "a1b", "a1a", "a1", "a0", "a"})
    // a < a0 < a1 < a1a < a1b < a2 < a10 < a20

    dumpByNaturalSort([]string{"x8-y8", "x2-y08", "x2-y7", "x2-g8"})
    // x2-g8 < x2-y08 < x2-y7 < x8-y8

    dumpByNaturalSort([]string{"1.3", "1.1", "1.02", "1.010", "1.002", "1.001"})
    // 1.001 < 1.002 < 1.010 < 1.02 < 1.1 < 1.3

    dumpByNaturalSort([]string{"001", "01", "1", "10", "010", "2", "002"})
    // 001 < 002 < 01 < 010 < 1 < 2 < 10

    dumpByNaturalSort([]string{"a001", "a01", "a1", "a10", "a010", "a2", "a002"})
    // a001 < a002 < a01 < a010 < a1 < a2 < a10
}

まとめ

自然順ソートについて理解し、Goで実装してみました。ある程度はうまく動いているようですが、ゼロパディングされた数値とそうでない数値が混在するような場合や、ゼロパディングされた数値同士でも桁が違う場合などは期待した結果にはなってくれませんでした。これを解決する案はぼんやりあって、ゼロパディングされた数値文字列を取り出して数値比較を行うことで解決できるんじゃないかなぁとは思っていますが、まだ実装するには至っていません。

bamchoh’s diary

自然順ソートをGoで実装

アルゴリズム

左寄せ比較

右寄せ比較

Goでの実装

まとめ