计算机科学
計算機科學
계산궤과학
COMPUTER SCIENCE
2014年
6期
243-249
,共7页
近似串匹配%过滤算法%q-gram过滤%q元语法
近似串匹配%過濾算法%q-gram過濾%q元語法
근사천필배%과려산법%q-gram과려%q원어법
Approximate string matching%Filter algorithm%q-gram filter%q-gram
近似串匹配是生物信息学、文本检索、信号处理等领域的一个基础问题,如何提高近似串匹配的速度一直都是研究的关键问题.提出一种新的在大文本库中快速查找近似匹配的无损过滤算法.为保证在大文本库中的匹配速度,本算法使用了查询速度较快的q-gram索引.为通过提高过滤算法的过滤效率达到提升算法整体性能的目的,详细分析了含有匹配串的文本区域,提取了一些基于尾匹配q-gram特征的新过滤条件,然后用这些特征优化了过滤算法的过滤标准.实验数据表明,新过滤条件有效地提高了算法的过滤效率,提升了算法的整体性能.结果显示新算法适合各种匹配错误率下的近似匹配,算法的通用性较强.
近似串匹配是生物信息學、文本檢索、信號處理等領域的一箇基礎問題,如何提高近似串匹配的速度一直都是研究的關鍵問題.提齣一種新的在大文本庫中快速查找近似匹配的無損過濾算法.為保證在大文本庫中的匹配速度,本算法使用瞭查詢速度較快的q-gram索引.為通過提高過濾算法的過濾效率達到提升算法整體性能的目的,詳細分析瞭含有匹配串的文本區域,提取瞭一些基于尾匹配q-gram特徵的新過濾條件,然後用這些特徵優化瞭過濾算法的過濾標準.實驗數據錶明,新過濾條件有效地提高瞭算法的過濾效率,提升瞭算法的整體性能.結果顯示新算法適閤各種匹配錯誤率下的近似匹配,算法的通用性較彊.
근사천필배시생물신식학、문본검색、신호처리등영역적일개기출문제,여하제고근사천필배적속도일직도시연구적관건문제.제출일충신적재대문본고중쾌속사조근사필배적무손과려산법.위보증재대문본고중적필배속도,본산법사용료사순속도교쾌적q-gram색인.위통과제고과려산법적과려효솔체도제승산법정체성능적목적,상세분석료함유필배천적문본구역,제취료일사기우미필배q-gram특정적신과려조건,연후용저사특정우화료과려산법적과려표준.실험수거표명,신과려조건유효지제고료산법적과려효솔,제승료산법적정체성능.결과현시신산법괄합각충필배착오솔하적근사필배,산법적통용성교강.