基于0－1 规划模型的规则中文碎片拼接复原研究

2014-03-13沈鸿平章毅鹏王义康

电子科技 2014年6期

关键词：模型

沈鸿平，章毅鹏，王义康

(中国计量学院理学院，浙江杭州 310018)

破碎文件的拼接在司法物证复原、历史文献修复以及军事情报获取等领域均有着重要的应用［1］。传统的拼接复原工作需由人工完成，虽准确率较高，但效率较低。尤其是当碎片数量巨大时，人工拼接难以在短时间内完成。随着计算机技术的发展，人们试图开发碎片自动拼接技术，以提高拼接复原效率。目前二维碎片拼接研究主要集中在两方面:一是基于不规则碎片的轮廓拼接研究［2－6］，不规则碎片研究在拼接过程中可利用边界轮廓信息进行形状匹配;另一方面是基于碎片文本信息及其特征的拼接研究［7－9］，由于汉字复杂多样，语义识别较为复杂，在解决拼接问题的同时会带来诸多新问题。以上两者比较而言，由于轮廓边界几何特征信息量较少，对其数学模型的研究便显得更为困难。

本文在基于碎片边界轮廓无明显几何匹配特征信息的情况下，通过对碎片内文字行平面分布特征以及行特征信息获取方法的研究，建立基于0－1 规划的中文规则碎片拼接模型。考虑到模型本身的复杂性和求精确解的困难性，提出利用贪婪算法进行求解，并对某一碎片文件进行了拼接模拟仿真，结果表明该方法效果良好。