SPB Git

Repository Public

SequenceDiff.swift 7.4 KB 156 lines swift

1// ORIX Docs2// File: Packages/ORIXDocsKit/Sources/DocReview/SequenceDiff.swift3// Description: Longest common subsequence of two integer sequences: unique-line (patience) anchors, then linear-space Myers with a cost cap.4//5// Author: Simon-Pierre Boucher6// Contact: contact@spboucher.ai7import Foundation89/// LCS over interned symbols. Memory is O(n + m): the Myers search keeps two diagonal vectors and recurses on the middle snake10/// (Myers 1986, section 4b), never a full edit graph.11enum SequenceDiff {12    /// Matched index pairs `(i, j)` with `a[i] == b[j]`, strictly increasing in both coordinates.13    /// - Parameters:14    ///   - anchors: first pin the symbols that occur exactly once on each side (patience diff), then run Myers between the pins.15    ///     This keeps far-apart identical blocks aligned even when the documents differ a lot.16    ///   - maxCost: when a Myers sub-problem needs more than this many edit steps the search stops and the sub-problem is17    ///     reported as having nothing in common (the caller pairs its content by similarity instead).18    static func lcs(_ a: [Int], _ b: [Int], anchors: Bool, maxCost: Int = 2048) -> [(Int, Int)] {19        var engine = Engine(a: a, b: b, cap: maxCost)20        var lo = 021        let limit = min(a.count, b.count)22        while lo < limit && a[lo] == b[lo] { engine.out.append((lo, lo)); lo += 1 }23        var suffix = 024        while suffix < limit - lo && a[a.count - 1 - suffix] == b[b.count - 1 - suffix] { suffix += 1 }25        let aHi = a.count - suffix, bHi = b.count - suffix26        if lo < aHi && lo < bHi {27            if anchors {28                var pa = lo, pb = lo29                for (i, j) in uniqueAnchors(a, b, lo, aHi, lo, bHi) {30                    engine.diff(pa, i, pb, j)31                    engine.out.append((i, j))32                    pa = i + 1; pb = j + 133                }34                engine.diff(pa, aHi, pb, bHi)35            } else {36                engine.diff(lo, aHi, lo, bHi)37            }38        }39        for k in 0..<suffix { engine.out.append((aHi + k, bHi + k)) }40        return engine.out41    }4243    /// Symbols occurring exactly once in each range, reduced to the longest chain that is increasing on both sides.44    private static func uniqueAnchors(_ a: [Int], _ b: [Int], _ aLo: Int, _ aHi: Int, _ bLo: Int, _ bHi: Int) -> [(Int, Int)] {45        var countA: [Int: Int] = [:], posB: [Int: Int] = [:], countB: [Int: Int] = [:]46        countA.reserveCapacity(aHi - aLo); countB.reserveCapacity(bHi - bLo)47        for i in aLo..<aHi { countA[a[i], default: 0] += 1 }48        for j in bLo..<bHi { countB[b[j], default: 0] += 1; posB[b[j]] = j }49        var cand: [(Int, Int)] = []50        for i in aLo..<aHi where countA[a[i]] == 1 && countB[a[i]] == 1 { cand.append((i, posB[a[i]]!)) }51        guard !cand.isEmpty else { return [] }52        // Longest increasing subsequence on the b coordinate (patience sorting with back pointers).53        var tails: [Int] = []          // index into cand of the last element of the best chain of each length54        var prev = Array(repeating: -1, count: cand.count)55        for (ci, c) in cand.enumerated() {56            var l = 0, h = tails.count57            while l < h {58                let mid = (l + h) / 259                if cand[tails[mid]].1 < c.1 { l = mid + 1 } else { h = mid }60            }61            if l > 0 { prev[ci] = tails[l - 1] }62            if l == tails.count { tails.append(ci) } else { tails[l] = ci }63        }64        var chain: [(Int, Int)] = []65        var cur = tails.last ?? -166        while cur >= 0 { chain.append(cand[cur]); cur = prev[cur] }67        return chain.reversed()68    }6970    private struct Engine {71        let a: [Int], b: [Int]72        let cap: Int73        var out: [(Int, Int)] = []74        var vf: [Int], vb: [Int]7576        init(a: [Int], b: [Int], cap: Int) {77            self.a = a; self.b = b; self.cap = cap78            let size = a.count + b.count + 879            vf = Array(repeating: -1, count: size)80            vb = Array(repeating: -1, count: size)81            out.reserveCapacity(min(a.count, b.count))82        }8384        mutating func diff(_ aLo0: Int, _ aHi0: Int, _ bLo0: Int, _ bHi0: Int) {85            var aLo = aLo0, bLo = bLo086            while aLo < aHi0 && bLo < bHi0 && a[aLo] == b[bLo] { out.append((aLo, bLo)); aLo += 1; bLo += 1 }87            var suffix = 088            while aLo < aHi0 - suffix && bLo < bHi0 - suffix && a[aHi0 - 1 - suffix] == b[bHi0 - 1 - suffix] { suffix += 1 }89            let aHi = aHi0 - suffix, bHi = bHi0 - suffix90            if aLo < aHi && bLo < bHi, let s = middleSnake(aLo, aHi, bLo, bHi) {91                diff(aLo, s.0, bLo, s.1)92                var k = 093                while s.0 + k < s.2 { out.append((s.0 + k, s.1 + k)); k += 1 }94                diff(s.2, aHi, s.3, bHi)95            }96            for k in 0..<suffix { out.append((aHi + k, bHi + k)) }97        }9899        /// The middle snake of the shortest edit path, as `(x0, y0, x1, y1)` in absolute coordinates; nil when the cost cap is hit.100        /// Points outside the grid are marked unreachable (-1) so a returned snake always lies inside the sub-problem.101        private mutating func middleSnake(_ aLo: Int, _ aHi: Int, _ bLo: Int, _ bHi: Int) -> (Int, Int, Int, Int)? {102            let n = aHi - aLo, m = bHi - bLo103            let delta = n - m104            let maxD = (n + m + 1) / 2105            let off = maxD + 2106            let odd = delta % 2 != 0107            for d in 0...maxD {108                if d > cap { return nil }109                var k = -d110                while k <= d {111                    var x = -1112                    if d == 0 { x = 0 } else {113                        if k > -d { let p = vf[off + k - 1]; if p >= 0 && p + 1 <= n { x = p + 1 } }114                        if k < d { let p = vf[off + k + 1]; if p >= 0 && p - k <= m && p > x { x = p } }115                    }116                    if x < 0 { vf[off + k] = -1; k += 2; continue }117                    var y = x - k118                    let x0 = x, y0 = y119                    while x < n && y < m && a[aLo + x] == b[bLo + y] { x += 1; y += 1 }120                    vf[off + k] = x121                    if odd {122                        let kb = delta - k123                        if kb >= -(d - 1) && kb <= d - 1 {124                            let r = vb[off + kb]125                            if r >= 0 && x + r >= n { return (aLo + x0, bLo + y0, aLo + x, bLo + y) }126                        }127                    }128                    k += 2129                }130                k = -d131                while k <= d {132                    var x = -1133                    if d == 0 { x = 0 } else {134                        if k > -d { let p = vb[off + k - 1]; if p >= 0 && p + 1 <= n { x = p + 1 } }135                        if k < d { let p = vb[off + k + 1]; if p >= 0 && p - k <= m && p > x { x = p } }136                    }137                    if x < 0 { vb[off + k] = -1; k += 2; continue }138                    var y = x - k139                    let x0 = x, y0 = y140                    while x < n && y < m && a[aHi - 1 - x] == b[bHi - 1 - y] { x += 1; y += 1 }141                    vb[off + k] = x142                    if !odd {143                        let kf = delta - k144                        if kf >= -d && kf <= d {145                            let f = vf[off + kf]146                            if f >= 0 && x + f >= n { return (aHi - x, bHi - y, aHi - x0, bHi - y0) }147                        }148                    }149                    k += 2150                }151            }152            return nil153        }154    }155}156
Files main
Menu

Theme