118 lines
4.2 KiB
Go
118 lines
4.2 KiB
Go
// Package comparer реализует построчно-словесное сравнение двух текстов
|
||
// (аналог вкладки Comparer в Burp) на основе классического LCS-алгоритма.
|
||
package comparer
|
||
|
||
import "regexp"
|
||
|
||
// tokenPattern разбивает текст на чередующиеся куски пробелов и
|
||
// непробельных последовательностей — так diff получается на уровне
|
||
// "слов" (примерно как режим "Words" в Burp Comparer), но при этом
|
||
// исходный текст полностью восстанавливается конкатенацией токенов,
|
||
// включая переносы строк и пробелы между ними.
|
||
var tokenPattern = regexp.MustCompile(`\s+|\S+`)
|
||
|
||
func tokenize(s string) []string {
|
||
return tokenPattern.FindAllString(s, -1)
|
||
}
|
||
|
||
// Op — тип операции над токеном при переходе от a к b.
|
||
type Op int
|
||
|
||
const (
|
||
OpEqual Op = iota
|
||
OpDelete
|
||
OpInsert
|
||
)
|
||
|
||
// Chunk — последовательность токенов с одной и той же операцией,
|
||
// склеенных в одну строку для компактного вывода.
|
||
type Chunk struct {
|
||
Op Op
|
||
Text string
|
||
}
|
||
|
||
// Diff сравнивает a и b на уровне токенов (слов и пробельных
|
||
// промежутков) через LCS и возвращает последовательность чанков:
|
||
// OpEqual — совпадающие куски, OpDelete — есть только в a,
|
||
// OpInsert — есть только в b.
|
||
//
|
||
// Сложность O(n·m) по числу токенов в a и b — для вставки HTTP-запросов
|
||
// (сотни-тысячи токенов) это доли миллисекунды; для вставки многомегабайтных
|
||
// текстов такой алгоритм не годится, но это осознанно не наш случай.
|
||
func Diff(a, b string) []Chunk {
|
||
ta := tokenize(a)
|
||
tb := tokenize(b)
|
||
|
||
lcs := lcsTable(ta, tb)
|
||
ops := backtrack(lcs, ta, tb, len(ta), len(tb))
|
||
|
||
return mergeChunks(ops)
|
||
}
|
||
|
||
type tokenOp struct {
|
||
op Op
|
||
text string
|
||
}
|
||
|
||
// lcsTable строит стандартную DP-таблицу длин наибольшей общей
|
||
// подпоследовательности для токенов ta и tb.
|
||
func lcsTable(ta, tb []string) [][]int {
|
||
n, m := len(ta), len(tb)
|
||
table := make([][]int, n+1)
|
||
for i := range table {
|
||
table[i] = make([]int, m+1)
|
||
}
|
||
for i := 1; i <= n; i++ {
|
||
for j := 1; j <= m; j++ {
|
||
if ta[i-1] == tb[j-1] {
|
||
table[i][j] = table[i-1][j-1] + 1
|
||
} else if table[i-1][j] >= table[i][j-1] {
|
||
table[i][j] = table[i-1][j]
|
||
} else {
|
||
table[i][j] = table[i][j-1]
|
||
}
|
||
}
|
||
}
|
||
return table
|
||
}
|
||
|
||
// backtrack восстанавливает последовательность операций из DP-таблицы,
|
||
// двигаясь от (n, m) к (0, 0), и разворачивает её в порядок a→b.
|
||
func backtrack(table [][]int, ta, tb []string, i, j int) []tokenOp {
|
||
var reversed []tokenOp
|
||
for i > 0 || j > 0 {
|
||
switch {
|
||
case i > 0 && j > 0 && ta[i-1] == tb[j-1]:
|
||
reversed = append(reversed, tokenOp{OpEqual, ta[i-1]})
|
||
i--
|
||
j--
|
||
case j > 0 && (i == 0 || table[i][j-1] >= table[i-1][j]):
|
||
reversed = append(reversed, tokenOp{OpInsert, tb[j-1]})
|
||
j--
|
||
default:
|
||
reversed = append(reversed, tokenOp{OpDelete, ta[i-1]})
|
||
i--
|
||
}
|
||
}
|
||
|
||
ops := make([]tokenOp, len(reversed))
|
||
for k, v := range reversed {
|
||
ops[len(reversed)-1-k] = v
|
||
}
|
||
return ops
|
||
}
|
||
|
||
// mergeChunks склеивает подряд идущие токены с одинаковой операцией
|
||
// в один Chunk — иначе на каждое слово приходился бы отдельный чанк,
|
||
// что нечитаемо в выводе.
|
||
func mergeChunks(ops []tokenOp) []Chunk {
|
||
var chunks []Chunk
|
||
for _, o := range ops {
|
||
if len(chunks) > 0 && chunks[len(chunks)-1].Op == o.op {
|
||
chunks[len(chunks)-1].Text += o.text
|
||
continue
|
||
}
|
||
chunks = append(chunks, Chunk{Op: o.op, Text: o.text})
|
||
}
|
||
return chunks
|
||
}
|