Ed-Sjoin：一种优化的字符串相似连接算法
相似连接(similarity join)在数据清洗、生物信息、模式识别等应用领域中有着广泛应用，其中基于编辑距离的字符串相似连接是一种重要的相似连接．尽管当前有一些基于编辑距离的字符串连接算法提出，然而，当前的算法存在着大量的多余计算，影响了算法的效率．为了高效计算基于编辑距离的字符串连接，提出了一种优化的算法Ed—Sjoin，分别从优化筛选算法和基于前缀的重复消减策略两方面对算法进行优化，这些优化策略可以实现更加有效的剪枝，并且避免了部分重复计算，从而加速算法的执行．实验结果表明，提出的方法优于现有方法．
相似连接 编辑距离 字符串 Ed-Sjoin算法 优化筛选算法 重复消减策略
李璐 王宏志 李建中 高宏
哈尔滨工业大学计算机科学与技术学院 哈尔滨 150001
国内会议
南昌
中文
319-325
2009-10-15（万方平台首次上网日期，不代表论文的发表时间）