通信学报
通信學報
통신학보
JOURNAL OF CHINA INSTITUTE OF COMMUNICATIONS
2014年
12期
10-20
,共11页
陈子阳%韩玉俊%王璿%周军锋
陳子暘%韓玉俊%王璿%週軍鋒
진자양%한옥준%왕선%주군봉
字符串相似性%非对称特征方案%长度跳跃索引
字符串相似性%非對稱特徵方案%長度跳躍索引
자부천상사성%비대칭특정방안%장도도약색인
string similarity%asymmetric signature scheme%length-skip index
研究基于编辑距离的top-k相似字符串查询处理方法,即对于给定的字符串集合S和查询串σ,返回S中前k个与σ编辑距离最小的字符串.首先提出了基于长度跳跃索引的2种自适应过滤策略来减少字符串之间编辑距离的计算次数;其次提出了查询字符串与不匹配字符串集合的编辑距离下界,以便在处理和σ无公共特征的字符串时,进一步减少编辑距离的计算次数;最后给出了基于上述过滤策略的高效top-k相似字符串查询算法,并在3个真实的数据集上进行了实验,实验结果验证了所提算法的高效性.
研究基于編輯距離的top-k相似字符串查詢處理方法,即對于給定的字符串集閤S和查詢串σ,返迴S中前k箇與σ編輯距離最小的字符串.首先提齣瞭基于長度跳躍索引的2種自適應過濾策略來減少字符串之間編輯距離的計算次數;其次提齣瞭查詢字符串與不匹配字符串集閤的編輯距離下界,以便在處理和σ無公共特徵的字符串時,進一步減少編輯距離的計算次數;最後給齣瞭基于上述過濾策略的高效top-k相似字符串查詢算法,併在3箇真實的數據集上進行瞭實驗,實驗結果驗證瞭所提算法的高效性.
연구기우편집거리적top-k상사자부천사순처리방법,즉대우급정적자부천집합S화사순천σ,반회S중전k개여σ편집거리최소적자부천.수선제출료기우장도도약색인적2충자괄응과려책략래감소자부천지간편집거리적계산차수;기차제출료사순자부천여불필배자부천집합적편집거리하계,이편재처리화σ무공공특정적자부천시,진일보감소편집거리적계산차수;최후급출료기우상술과려책략적고효top-k상사자부천사순산법,병재3개진실적수거집상진행료실험,실험결과험증료소제산법적고효성.
