用图模型形式化文本位置关系，解决布局一致性与匹配难题
Position Spaces and Graphs
- 基于水平垂直顺序构建位置图，约束行列对齐关系
- 证明位置图的结构匹配问题仍为NP完全，具理论难度
- 适合文档分析、版面理解等需精确位置推理的场景
本文提出位置图（position graphs），一种基于位置空间形式化的图结构推理框架。该框架利用两个严格偏序关系，分别表示横向与纵向对齐及先后顺序，建模离散标记的相对位置。不同于一般定性空间演算，位置图受链条件和行列兼容性约束。我们对其进行了完整的理论分析，包括图一致性表征，并建立了确保一致性的条件。进一步研究了结构模式发现的计算复杂性，将其建模为诱导子图同构问题，证明即使在位置图限制下，该问题仍为NP完全。研究最初源于文档处理需求，但聚焦于基于位置约束的数学性质与代数一致性，提供独立于具体数据提取技术的形式逻辑层。
原文摘要 · Abstract (English)
In this paper, we introduce position graphs, a graph-based reasoning framework based on the formalization of position spaces. This framework utilizes two strict partial orders, representing horizontal and vertical alignment and precedence, to model the relative positions of discrete tokens. Unlike general qualitative spatial calculi, position graphs are constrained by a chain condition and compatibility requirements that focus on rows and columns. We provide a comprehensive theoretical analysis of this representation, beginning with a characterization of graph consistency. Conditions to ensure the consistency of position graphs are established. Furthermore, we investigate the computational complexity of structural pattern discovery, modeled as the induced subgraph isomorphism problem. We demonstrate that this problem remains NP-complete even within the restricted class of position graphs. While initially motivated by document processing, this work focuses on the underlying mathematical properties and algebraic consistency of position-based constraints, providing a formal logical layer that is independent of specific data extraction techniques.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。