Skip to content

quenbyako/gonp

 
 

Repository files navigation

workflow status

gonp

gonp is a diff algorithm implementation in Go.

Algorithm

The algorithm gonp uses is based on "An O(NP) Sequence Comparison Algorithm" by described by Sun Wu, Udi Manber and Gene Myers. An O(NP) Sequence Comparison Algorithm(following, Wu's O(NP) Algorithm) is the efficient algorithm for comparing two sequences.

Computational complexity

The computational complexity of Wu's O(NP) Algorithm is averagely O(N+PD), in the worst case, is O(NP).

Getting started

string difference

diff := gonp.New([]rune("abc"), []rune("abd"))
diff.Compose()
ed := diff.EditDistance() // ed 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},
//        }

int slice difference

diff := gonp.New([]int{1,2,3}, []int{1,5,3})
diff.Compose()
ed := diff.EditDistance() // ed 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},
//        }

unified format difference

diff := gonp.New([]rune("abc"), []rune("abd"))
diff.Compose()

uniHunks := diff.UnifiedHunks()
diff.PrintUniHunks(uniHunks)
// @@ -1,3 +1,3 @@
//  a
//  b
// -c
// +d

Example

strdiff

$ make strdiff
go build -o strdiff examples/strdiff.go
$ ./strdiff abc abd
EditDistance: 2
LCS: ab
SES:
  a
  b
- c
+ d

intdiff

$ make intdiff
go build -o intdiff examples/intdiff.go
$ ./intdiff
diff [1 2 3 4 5] [1 2 9 4 5]
EditDistance: 2
LCS: [1 2 4 5]
SES:
  1
  2
- 3
+ 9
  4
  5

unistrdiff

$ make unistrdiff
go build -o unistrdiff examples/unistrdiff.go
$ ./unistrdiff abc abd
EditDistance:2
LCS:ab
Unified format difference:
@@ -1,3 +1,3 @@
 a
 b
-c
+d

uniintdiff

$ make uniintdiff
go build -o uniintdiff examples/uniintdiff.go
$ ./uniintdiff
diff [1 2 3 4 5] [1 2 9 4 5]
EditDistance: 2
LCS: [1 2 4 5]
Unified format difference:
@@ -1,5 +1,5 @@
 1
 2
-3
+9
 4
 5

unifilediff

$ make unifilediff
go build -o unifilediff examples/unifilediff.go
$ cat a.txt
a
b
c
$ cat b.txt
a
b
d
$ ./unifilediff a.txt b.txt
@@ -1,3 +1,3 @@
 a
 b
-c
+d

About

diff algorithm in Go

Resources

License

Stars

Watchers

Forks

Releases

No releases published

Packages

No packages published

Languages

  • Go 98.2%
  • Makefile 1.8%