GoのGenericsで差分アルゴリズムを実装してみた

Go1.18でGenericsが入ったので、昔書いた編集距離(Edit Distance)、LCS(Longest Common Subsequence)、SES(Shortest Edit Script)の計算ができる拙作のdiff実装に適用してみた。

use generics #3

元々はこんな風に文字列(string)にしか適用できなかったが、

diff := gonp.New("abc", "abd")
diff.Compose()
ed := diff.Editdistance() // 編集距離 is 2
lcs := diff.Lcs()) // lcs is "ab"
 
ses := diff.Ses()
// ses is []SesElem{
//   {e: 'a', t: Common},
//   {e: 'b', t: Common},
//   {e: 'c', t: Delete},
//   {e: 'd', t: Add},
//   }

今回の変更で整数の配列に適用したり、

diff := gonp.New([]int{1,2,3}, []int{1,5,3})
diff.Compose()
ed := diff.Editdistance() // 編集距離 is 2
lcs := diff.Lcs() // lcs is [1,3]

ses := diff.Ses()
// ses is []SesElem{
//        {e: 1, t: Common},
//        {e: 2, t: Delete},
//        {e: 5, t: Add},
//        {e: 3, t: Common},
//        }

文字列の配列に適用できるようになった。

a := []string{"abc", "def", "ghi"}
b := []string{"abc", "def", "ihg"}
diff := gonp.New(a, b)
diff.Compose()
ed := diff.Editdistance() // 編集距離 is 2
lcs := diff.Lcs() // lcs is "[abc def]"
 
ses := diff.Ses()
// ses is []SesElem{
//        {e: "abc", t: Common},
//        {e: "def", t: Common},
//        {e: "ghi", t: Delete},
//        {e: "ihg", t: Add},
//        }

なお、文字列に適用する際はruneの配列として渡す。

diff := gonp.New([]rune("abc"), []rune("abd"))
diff.Compose()
ed := diff.Editdistance() // 編集距離 is 2
lcs := diff.Lcs() // lcs is "ab"
 
ses := diff.Ses()
// ses is []SesElem{
//        {e: 'a', t: Common},
//        {e: 'b', t: Common},
//        {e: 'c', t: Delete},
//        {e: 'd', t: Add},
//        }

Type Constraintsや大元の構造体の定義はこんな感じ。(Genericsを使う前はTの部分がrune型で固定だった)

type Elem interface {
        // int32 overlaps rune
        ~rune | ~string | ~byte | ~int | ~int8 | ~int16 | ~int64 | ~float32 | ~float64
}

// SesElem is element of SES
type SesElem[T Elem] struct {
        e T
        t SesType
}

// Diff is context for calculating difference between a and b
type Diff[T Elem] struct {
        a, b           []T
        m, n           int
        ed             int
        lcs            []T
        ses            []SesElem[T]
        reverse        bool
        path           []int
        onlyEd         bool
        pointWithRoute []PointWithRoute
}

というわけで、Goで導入されたばかりのGenericsを使ってみた感想ですが、思っていたよりシンプルで使いやすいなと思いました。一方でもう少し色々できてほしいなと思ったり(今回の場合、SESの出力時に使うprintf文字列内の修飾子を特定の型向けにカスタムするためにメソッドのオーバーロード機能がほしくなりました)。まぁ、今後に期待。