DAG PathFinder backup for Homa Assembler.

Homa_PathFinderDAG.swift

// MARK: - Homa.PathFinderDAG

extension Homa {
  final class PathFinderDAG {
    // MARK: Lifecycle

    /// 爬軌函式，會更新當前組字器的 walkedNodes。
    ///
    /// 找到軌格陣圖內權重最大的路徑。該路徑代表了可被觀測到的最可能的隱藏事件鏈。
    /// 這裡使用 Cormen 在 2001 年出版的教材當中提出的「有向無環圖的最短路徑」的
    /// 算法來計算這種路徑。不過，這裡不是要計算距離最短的路徑，而是計算距離最長
    /// 的路徑（所以要找最大的權重），因為在對數概率下，較大的數值意味著較大的概率。
    /// 對於 `G = (V, E)`，該算法的運行次數為 `O(|V|+|E|)`，其中 `G` 是一個有向無環圖。
    /// 這意味著，即使軌格很大，也可以用很少的算力就可以爬軌。
    ///
    /// - Remark: 利用該數學方法進行輸入法智能組句的（已知可考的）最開始的案例是
    /// 郭家寶（ByVoid）的《[基於統計語言模型的拼音輸入法](https://byvoid.com/zht/blog/slm_based_pinyin_ime/) 》；
    /// 再後來則是 2022 年中時期劉燈的 Gramambular 2 組字引擎。
    /// - Returns: 爬軌結果＋該過程是否順利執行。
    @discardableResult
    init(config: Homa.Config, assembledNodes: inout [Homa.Node]) {
      var newassembledNodes = [Homa.Node]()
      defer {
        assembledNodes = newassembledNodes
      }
      sortAndRelax(config: config)
      var iterated: NodeVertex? = leadingNode
      while let itPrev = iterated?.prev {
        // 此處必須得是 Copy，讓組字器外部對此的操作影響不到組字器內部的節點。
        newassembledNodes.insert(itPrev.node.copy, at: 0)
        iterated = itPrev
      }
      iterated = nil
      newassembledNodes.removeFirst()
    }

    // MARK: Internal

    internal class NodeVertex: @unchecked Sendable {
      // MARK: Lifecycle

      internal init(node: Homa.Node, prev: NodeVertex? = nil, distance: Double = .init(Int32.min)) {
        self.node = node
        self.prev = prev
        self.distance = distance
      }

      // MARK: Internal

      internal let node: Homa.Node
      /// 自身屬下的頂點陣列。
      internal var edges = [NodeVertex]()
      internal weak var prev: NodeVertex?
      /// 該變數用於最短路徑的計算。
      ///
      /// 我們實際上是在計算具有最大權重的路徑，因此距離的初始值是負無窮的。
      /// 如果我們要計算最短的權重/距離，我們會將其初期值設為正無窮。
      internal var distance: Double = .init(Int32.min)

      /// 在進行進行位相幾何排序時會用到的狀態標記。
      internal var topologicallySorted = false

      internal var value: String? {
        node.value
      }

      internal var spanLength: Int { node.spanLength }

      internal var score: Double {
        node.getScore(previous: prev?.value)
      }
    }

    typealias VertexSpan = [Int: NodeVertex]

    /// 組字器「文字輸入方向上的」最後方的虛擬節點。
    internal let trailingNode = NodeVertex(node: Homa.Node(keyArray: ["$TRAILING"]))
    /// 組字器「文字輸入方向上的」最前方的虛擬節點，也是根頂點。
    internal let leadingNode = NodeVertex(node: .init(keyArray: ["$LEADING"]))

    /// 先進行位相幾何排序、再卸勁。
    internal func sortAndRelax(config: Homa.Config) {
      guard !config.spans.isEmpty else { return }
      var spans = [VertexSpan]()
      config.spans.forEach { span in
        var newVertexSpan = VertexSpan()
        span.forEach { pos, node in
          newVertexSpan[pos] = .init(node: node.copy)
        }
        spans.append(newVertexSpan)
      }
      trailingNode.distance = 0
      spans.enumerated().forEach { location, theSpan in
        theSpan.values.forEach { theNode in
          let nextVertexPosition = location + theNode.spanLength
          if nextVertexPosition == config.spans.count {
            theNode.edges.append(leadingNode)
            return
          }
          spans[nextVertexPosition].values.forEach { theNode.edges.append($0) }
        }
      }
      trailingNode.edges.append(contentsOf: spans[0].values)
      topologicalSort().reversed().forEach { neta in
        neta.edges.indices.forEach { Self.relax(u: neta, v: &neta.edges[$0]) }
      }
    }

    // MARK: Private

    /// 卸勁函式。
    ///
    /// 「卸勁 (relax)」一詞出自 Cormen 在 2001 年的著作「Introduction to Algorithms」的 585 頁。
    /// - Remark: 自己就是參照頂點 (u)，會在必要時成為 target (v) 的前述頂點。
    /// - Parameters:
    ///   - u: 基準頂點。
    ///   - v: 要影響的頂點。
    private static func relax(u: NodeVertex, v: inout NodeVertex) {
      // 從 u 到 w 的距離，也就是 v 的權重。
      let w: Double = v.score
      // 這裡計算最大權重：
      // 如果 v 目前的距離值小於「u 的距離值＋w（w 是 u 到 w 的距離，也就是 v 的權重）」，
      // 我們就更新 v 的距離及其前述頂點。
      guard v.distance < u.distance + w else { return }
      v.distance = u.distance + w
      v.prev = u
    }

    /// 對持有單個根頂點的有向無環圖進行位相幾何排序（topological
    /// sort）、且將排序結果以頂點陣列的形式給出。
    ///
    /// 這裡使用我們自己的堆棧和狀態定義實現了一個非遞迴版本，
    /// 這樣我們就不會受到當前線程的堆棧大小的限制。以下是等價的原始算法。
    /// ```
    ///  func topologicalSort(node: Node) {
    ///    node.edges.forEach { nodeNode in
    ///      if !nodeNode.topologicallySorted {
    ///        dfs(nodeNode, result)
    ///        nodeNode.topologicallySorted = true
    ///      }
    ///      result.append(nodeNode)
    ///    }
    ///  }
    /// ```
    /// 至於其遞迴版本，則類似於 Cormen 在 2001 年的著作「Introduction to Algorithms」當中的樣子。
    /// - Returns: 排序結果（頂點陣列）。
    private func topologicalSort() -> [NodeVertex] {
      class State {
        var iterIndex: Int
        let node: NodeVertex
        init(node: NodeVertex, iterIndex: Int = 0) {
          self.node = node
          self.iterIndex = iterIndex
        }
      }
      var result = [NodeVertex]()
      var stack = [State]()
      stack.append(State(node: trailingNode))
      while !stack.isEmpty {
        let state = stack[stack.count - 1]
        let theNode = state.node
        if state.iterIndex < state.node.edges.count {
          let newNode = state.node.edges[state.iterIndex]
          state.iterIndex += 1
          if !newNode.topologicallySorted {
            stack.append(.init(node: newNode))
            continue
          }
        }
        theNode.topologicallySorted = true
        result.append(theNode)
        stack.removeLast()
      }
      return result
    }
  }
}