基于正则表达式的结构化修复改进算法

摘要

针对结构化数据的清洗问题,以基于正则表达式的结构化修复(RSR)算法为基础,借鉴字符串之间编辑距离的计算思想,将违反偏序关系的边从自动机的边集中提取出来,仅对得到的边引入优先级队列来修正所对应的编辑距离,而其他边由于满足偏序关系则可直接通过递推式来计算,从而提出一种改进RSR算法。算法测试与分析结果表明,改进RSR算法在时间复杂度方面有明显优势,相对原算法的提升显著且稳定。