一种最长扩展公共子序列新算法

在最长填充公共子序列问题中提出一种新问题:假设有一个完整序列C和一个不完整序列Q,长度分别为m和n,Q中丢失的元素为相邻的相同元素,要求寻找一个丢失前的序列Q,使得C和Q具有最长的公共子序列。针对此问题,首先将Q中每个元素复制m-1个并插入Q中原来的位置,生成长度为mn的扩展序列Q^(*),然后证明了C和Q的最长扩展公共子序列是两序列C和Q^(*)的最长公共子序列,最后提出一种时空复杂度为O(mn)的最长扩展公共子序列求解新算法,并用轨迹实验证明了该算法对强噪声干扰和轨迹点丢失的同时有效性。

基于网络爬虫的导航深度服务信息自动采集

根据近来对地理信息Web服务搜索引擎的研究,设计一种基于网络爬虫自动采集POI(Point Of Interest)深度服务信息的方法。使用网络爬虫与DOM(Document Object Model)技术从发布相关POI深度服务信息的网站抓取实时信息,并通过编辑距离与针对地址匹配的改进最大公共子序列分析页面内容与POI主题相关度,进而将相关度最高的深度服务信息与POI点匹配,生成深度服务信息点特征。实验证明了方法的有效性。