SPB Git

Repository Public

VectorIndex.swift 3.6 KB 79 lines swift

1// Author: Simon-Pierre Boucher — contact@spboucher.ai2// File: Packages/LocalChatKnowledge/Sources/VectorIndex.swift3// Description: Exact in-memory vector index of one collection: contiguous Float32 matrix of unit vectors, cosine scores with Accelerate, top-k with a heap.4import Accelerate5import Foundation67public struct ScoredChunk: Sendable, Hashable {8    public var rowID: Int649    public var score: Double10    public init(rowID: Int64, score: Double) { self.rowID = rowID; self.score = score }11}1213public enum VectorMath {14    /// Unit-length copy; a zero (or non-finite) vector stays zero.15    public static func normalized(_ v: [Float]) -> [Float] {16        guard !v.isEmpty else { return v }17        var norm: Float = 018        vDSP_svesq(v, 1, &norm, vDSP_Length(v.count))19        norm = norm.squareRoot()20        guard norm.isFinite, norm > 0 else { return [Float](repeating: 0, count: v.count) }21        var out = [Float](repeating: 0, count: v.count); var divisor = norm22        vDSP_vsdiv(v, 1, &divisor, &out, 1, vDSP_Length(v.count))23        return out24    }25    public static func dot(_ a: UnsafePointer<Float>, _ b: UnsafePointer<Float>, _ n: Int) -> Float {26        var r: Float = 0; vDSP_dotpr(a, 1, b, 1, &r, vDSP_Length(n)); return r27    }28    public static func data(_ v: [Float]) -> Data { v.withUnsafeBufferPointer { Data(buffer: $0) } }29}3031final class VectorIndex: Sendable {32    let dimension: Int33    let rowIDs: [Int64]        // ascending34    let matrix: [Float]        // rowIDs.count × dimension, row-major, unit vectors35    var count: Int { rowIDs.count }3637    init(dimension: Int, rowIDs: [Int64], matrix: [Float]) { self.dimension = dimension; self.rowIDs = rowIDs; self.matrix = matrix }3839    /// Cosine top-k against a unit query vector.40    func search(_ query: [Float], limit: Int) -> [ScoredChunk] {41        let n = count42        guard n > 0, limit > 0, query.count == dimension else { return [] }43        var scores = [Float](repeating: 0, count: n)44        vDSP_mmul(matrix, 1, query, 1, &scores, 1, vDSP_Length(n), 1, vDSP_Length(dimension))45        let k = min(limit, n)46        // min-heap of the k best (score, position)47        var heap: [(Float, Int)] = []; heap.reserveCapacity(k)48        func less(_ a: (Float, Int), _ b: (Float, Int)) -> Bool { a.0 < b.0 || (a.0 == b.0 && a.1 > b.1) }49        func siftDown(_ start: Int) {50            var i = start51            while true {52                let l = 2 * i + 1, r = l + 1; var m = i53                if l < heap.count, less(heap[l], heap[m]) { m = l }54                if r < heap.count, less(heap[r], heap[m]) { m = r }55                if m == i { return }56                heap.swapAt(i, m); i = m57            }58        }59        for i in 0..<n {60            let item = (scores[i], i)61            if heap.count < k {62                heap.append(item); var c = heap.count - 163                while c > 0 { let p = (c - 1) / 2; if less(heap[c], heap[p]) { heap.swapAt(c, p); c = p } else { break } }64            } else if less(heap[0], item) { heap[0] = item; siftDown(0) }65        }66        return heap.sorted { less($1, $0) }.map { ScoredChunk(rowID: rowIDs[$0.1], score: Double($0.0)) }67    }6869    func position(of rowID: Int64) -> Int? {70        var lo = 0, hi = rowIDs.count - 171        while lo <= hi { let mid = (lo + hi) / 2; if rowIDs[mid] == rowID { return mid }; if rowIDs[mid] < rowID { lo = mid + 1 } else { hi = mid - 1 } }72        return nil73    }7475    func similarity(_ a: Int, _ b: Int) -> Double {76        matrix.withUnsafeBufferPointer { p in Double(VectorMath.dot(p.baseAddress! + a * dimension, p.baseAddress! + b * dimension, dimension)) }77    }78}79
Files main
Menu

Theme