一种基于模式的实体解析算法.pdfVIP

第 卷 第 期 计 算 机 学 报 ３８ ９ 　 　　 　　 　　 　　 Ｖｏｌ．３８ Ｎｏ．９ 年 月 ２０１５ ９ Ｓｅｔ．２０１５ ＣＨＩＮＥＳＥＪＯＵＲＮＡＬＯＦＣＯＭＰＵＴＥＲＳ ｐ 　 一种基于模式的实体解析算法 刘辉平 金澈清 周傲英 　 　 （华东师范大学软件学院数据科学与工程研究院 上海 ２０００６２） 　 　 摘 要 实体解析是数据融合和数据清洗的关键步骤，旨在从大量的数据集中找出描述相同实体的记录 当前主 ． 　 　 要有两种基本的解决思路，一种是穷尽式的实体解析，通过两两比较数据集中的所有记录，然后再合并相似的记 ２ 录，从而找到描述某一个实体的若干记录集合 然而，该方法的计算复杂度比较高（ （ ），其中 表示数据集合的 ． 犗 狀 狀 规模），难以处理大型数据集合 另一种思路是基于分块的实体解析，它调用特定的分块函数（如哈希函数、滑动窗 ． 口技术等）将集合中较为相似的记录划分到同一个块中，再仅对属于同一块中的记录进行两两比较 这种方法显著 ． 降低了运行时间，但会损失部分精度，因为某些描述同一实体的记录可能没有被分到同一个块中 文中提出了一种 ． 基于模式的实体解析算法，通过将相似的记录合并成记录集合并尝试生成对应的记录模式，然后进行模式之间的 两两比较来产生一个边界值，以确定对应的记录集合是否需要进行进一步的精确比较，从而判断是否属于同一个 实体 与第一种方法相比，该方法可有效地过滤部分不可能相似的记录，从而避免了针对所有数据记录进行两两比 ． 较，显著地降低了时间复杂度；与第二种方法相比，该方法并不损失任何精度 基于真实和模拟数据集合的实验结 ． 果验证了新方法的执行效率和有效性． 关键词 数据融合；数据清洗；实体解析；编辑距离；字符串相似度 　 中图法分类号 号 ／ ＴＰ３１１ 犇犗犐 １０．１１８９７ＳＰ．Ｊ．１０１６．２０１５．０１７９６ 　　　 犃犘犪狋狋犲狉狀犅犪狊犲犱犈狀狋犻狋犚犲狊狅犾狌狋犻狅狀犃犾狅狉犻狋犺犿 狔 犵 ＬＩＵＨｕｉＰｉｎ ＪＩＮＣｈｅＱｉｎ ＺＨＯＵＡｏＹｉｎ