pdf2docx开发概要：对齐隐式表格线¶

发布于：2020-09-27 | 分类：process automation

---

开发概要：解析表格记录了隐式表格Stream Table的解析方式：根据文本块位置生成潜在的表格边线，然后采用与显式表格相同的处理方式解析这些边线。其中，两个遗留问题：

• 第一步假想表格线时，尽量对齐横纵边线以简化表格结构

• 兼容半隐式表格例如三线表

本文记录这两个问题的处理方案。

问题与模型简化¶

根据下图中绿色块表示的文本位置，我们已经识别出了潜在的表格区域；根据相邻块正中间插入分隔线的原则，得到了图示浅色线表示的表格结构。从显示上来说没有任何问题，因为这些边框线对于隐式表格来说都是隐藏的。

需要改进的地方是，从第二行开始，两列的分隔线可以对齐合并，这样使表格结构从6x6简化成6x3。

单独看一条竖直边线，它实际上可以在相邻的两个文本块之间活动；我们希望尽可能多的竖直边线通过同一x方向位置。于是这个问题简化为：

已知一系列的区间[x1_s,x1_e], [x2_s,x2_e], ...，确定尽可能少的垂线x1,x2,...，使得每个区间至少有一条线穿过。

下面不妨初始化区间为：

inputs = [[8, 10], [2, 6], [4, 6], [1, 6], [4, 6], [5, 6]]

求解简化模型¶

首先设计一个区间对象，它具有左、右边界属性，类似于竖直边线允许在一定范围内左右移动。我们的目标是确定此区间内的一个具体值，也就是固定这条边线。下面的代码可以看出，如果没有优化边线位置，默认取区间中点位置。

class Interval:
    def __init__(self, x_range:tuple=None):
        # valid range
        if x_range: x0, x1 = x_range
        else: x0, x1 = -9999, 9999
        self.LRange, self.URange = x0, x1

        # whether the position is fixed        
        self._x = None
        self.finalized = False

    @property
    def x(self):
        return self._x if self.finalized else (self.LRange+self.URange)/2.0

    def is_valid(self, x):
        '''Whether the given position `x` locates in the valid instance range.'''
        return self.LRange < x < self.URange

    def finalize(self, x):
        '''Finalize with given position.'''
        # can be finalized for only one time
        if self.finalized or not self.is_valid(x): return
        self._x = x
        self.finalized = True

接下来设计区间组对象，对应所有竖直边线或者所有水平边线。我们将优化组内的所有区间，得到优化后的位置common_x。具体过程其实就是扫描线算法：

• 取每个区间的左右端点并去重得到一系列x坐标，x1,x2,x3,...
• 相邻两个坐标组成一个考察区间，例如[x1,x2], [x2,x3], ...
• 取考察区间中点例如x=(x1+x2)/2作为候选位置，检测它通过原始区间的情况，例如用序列0,1,1...表示经过区间2和3
• 根据穿过区间数降序排列区间中点
• 依次取区间中点直到所有区间都被固定下来

class Intervals:
    '''Collection of Interval instances.'''
    def __init__(self):
        self._instances = []

    def append(self, instance): self._instances.append(instance)    

    def common_x(self):
        return set([instance.x for instance in self._instances])

    def solve(self):
        # collect interval points and sort in x-increasing order 
        x_points = set()
        for instance in self._instances:
            x_points.add(instance.LRange)
            x_points.add(instance.URange)

        x_points = list(x_points)
        x_points.sort()

        # check intersection status of each intervals
        x_status = []
        for i in range(len(x_points)-1):
            x = (x_points[i]+x_points[i+1])/2.0
            c = list(map(
                    lambda instance: int(instance.is_valid(x)), self._instances))
            x_status.append((x,c))

        # sort per count since preferring passing through more intervals
        x_status.sort(key=lambda item: sum(item[1]), reverse=True)

        # finalize instances
        num = len(self._instances)
        current_status = [0] * num
        for x, status in x_status:
            # terminate if all instances are finalized
            if sum(current_status) == num: break

            # only one line is allowed to pass through one interval -> sum(A.*B)=0
            #  e.g. A = [1,0,1,0], B=[0,1,0,0] -> valid
            #       A = [1,0,1,0], B =[1,0,0,0] -> invalid due to two lines passing through interval 1
            duplicated = sum([c1*c2 for c1,c2 in zip(current_status, status)])
            if duplicated: continue

            # update current status
            current_status = [c1+c2 for c1,c2 in zip(current_status, status)]

            # now, finalize instances
            for instance, instance_status in zip(self._instances, status):
                if instance_status: instance.finalize(x)

直接展示一下结果，如果去掉下面代码中I.solve()将得到{3.5, 4.0, 5.5, 5.0, 9.0}，也就是开始所说参差不齐的情况；如果加上区间优化，则得到{9.0, 5.5}，即实际上对齐后的边线。

if __name__ == '__main__':    

    inputs = [[8, 10], [2, 6], [4, 6], [1, 6], [4, 6], [5, 6]]

    I = Intervals()
    for x_range in inputs: I.append(Interval(x_range))

    I.solve() # optimize
    x = I.common_x()

    print(x)

    # if comment ot I.solve()
    # {3.5, 4.0, 5.5, 5.0, 9.0}

    # final result
    # {9.0, 5.5}

回到原始问题¶

• 第一步假想表格线时，尽量对齐横纵边线以简化表格结构

  类似于简化模型，分别优化横、纵边线。以竖直边线为例，注意不仅有左右区间属性（水平移动自由度），还有上、下边线属性，即引用限定竖直范围的两条水平边线。只有同时确定水平位置和上下边线后，这条竖直边线才得以确定。

• 兼容半隐式表格例如三线表

  上一个问题以尽量对齐边线为原则优化边线位置，当给定显式的表格线时，需要引入优先级更高的原则：尽量通过显式的表格线。

  以解析三线表中为例，已经给定了显式的水平表格线h_i（i=1,2,3），考察所有可能的水平边线集合H，如果某条水平边线H_i的竖直活动区间[yi_1,yi_2]涵盖显式边线h_i的yi坐标，并且H_i的左右两条竖直边线的可能活动区域[xi_1,xi_2]在h_i的水平区间内，则确定H_i的纵坐标y=yi。