成都信息工程学院学报
成都信息工程學院學報
성도신식공정학원학보
JOURNAL OF CHENGDU INSTITUTE OF METEOROLOGY
2014年
6期
616-624
,共9页
王远超%安俊秀%程芃森%王鹏
王遠超%安俊秀%程芃森%王鵬
왕원초%안준수%정봉삼%왕붕
计算机软件与理论%大数据技术%编辑距离%相似度%最优路径%关键区域%动态规划
計算機軟件與理論%大數據技術%編輯距離%相似度%最優路徑%關鍵區域%動態規劃
계산궤연건여이론%대수거기술%편집거리%상사도%최우로경%관건구역%동태규화
computer software and theory%big data technology%edit distance%similarity%optimal path%critical area%dynamic programming
传统编辑距离算法采用动态规划方法用一个维度大小分别为源字符串长度和目标字符串长度的二维数组保存计算过程中求得编辑距离值.这种传统求解方式在时间效率和空间效率上开销较大,限制了编辑距离算法在长字符串中地应用.针对传统方法存在的问题,经深入研究编辑距离的求解过程,发现在某个关键区域内存在一条最优路径,通过确定最优路径所在关键区域可以快速地求解两字符串之间的编辑距离值.实验表明,方法在计算两字符串之间的编辑距离与传统方法相比可以降低问题的求解规模,提高算法的时间效率和空间效率.所描述的方法同样适用于图论中使用动态规划方法求解一般问题地应用,比如最优分配问题和背包问题等.
傳統編輯距離算法採用動態規劃方法用一箇維度大小分彆為源字符串長度和目標字符串長度的二維數組保存計算過程中求得編輯距離值.這種傳統求解方式在時間效率和空間效率上開銷較大,限製瞭編輯距離算法在長字符串中地應用.針對傳統方法存在的問題,經深入研究編輯距離的求解過程,髮現在某箇關鍵區域內存在一條最優路徑,通過確定最優路徑所在關鍵區域可以快速地求解兩字符串之間的編輯距離值.實驗錶明,方法在計算兩字符串之間的編輯距離與傳統方法相比可以降低問題的求解規模,提高算法的時間效率和空間效率.所描述的方法同樣適用于圖論中使用動態規劃方法求解一般問題地應用,比如最優分配問題和揹包問題等.
전통편집거리산법채용동태규화방법용일개유도대소분별위원자부천장도화목표자부천장도적이유수조보존계산과정중구득편집거리치.저충전통구해방식재시간효솔화공간효솔상개소교대,한제료편집거리산법재장자부천중지응용.침대전통방법존재적문제,경심입연구편집거리적구해과정,발현재모개관건구역내존재일조최우로경,통과학정최우로경소재관건구역가이쾌속지구해량자부천지간적편집거리치.실험표명,방법재계산량자부천지간적편집거리여전통방법상비가이강저문제적구해규모,제고산법적시간효솔화공간효솔.소묘술적방법동양괄용우도론중사용동태규화방법구해일반문제지응용,비여최우분배문제화배포문제등.
