计算机研究与发展
計算機研究與髮展
계산궤연구여발전
JOURNAL OF COMPUTER RESEARCH AND DEVELOPMENT
2013年
11期
2444-2454
,共11页
王开云%孔思淇%付云生%潘泽友%马卫东%赵强
王開雲%孔思淇%付雲生%潘澤友%馬衛東%趙彊
왕개운%공사기%부운생%반택우%마위동%조강
最长公共子串%双向比较%连续同值区间%跨越%亚线性
最長公共子串%雙嚮比較%連續同值區間%跨越%亞線性
최장공공자천%쌍향비교%련속동치구간%과월%아선성
longest common substring%bi-directional comparison%continuous same value segment%skip%sublinear
查找两个给定字符串的最长公共子串(LCSstr)是一类重要字符串分析问题,在字符串近似匹配、计算机病毒特征码对比等方面有着广泛的用途.最长公共子串算法目前主要包括动态规划算法(LCSstrDP)和后缀数组算法(LCSstrSA),分别用于短串和长串的最长公共子串计算.前者代码简洁,但计算速度较慢,后者速度很快但算法非常复杂.提出两种基于双向比较的最长公共子串算法,即LCSstrSeL和LCSstrSCeL.LCSstrSeL跨越已有的最长公共子串长度,与LCSstrDP相比,代码同样简洁,平均计算效率提高近一个数量级,并且不需要额外的存储空间.LCSstrSCeL是在LCSstrSeL的基础上,增加字符跨越、连续同值区间跨越等机制,平均效率较LCSstrSeL亦有一定程度的提高,内存开销与LCSstrDP相近,在中小长度的字符串LCSstr计算中,平均计算效率高于LCSstrSA,某些情况下的计算效率可达到亚线性的速度.
查找兩箇給定字符串的最長公共子串(LCSstr)是一類重要字符串分析問題,在字符串近似匹配、計算機病毒特徵碼對比等方麵有著廣汎的用途.最長公共子串算法目前主要包括動態規劃算法(LCSstrDP)和後綴數組算法(LCSstrSA),分彆用于短串和長串的最長公共子串計算.前者代碼簡潔,但計算速度較慢,後者速度很快但算法非常複雜.提齣兩種基于雙嚮比較的最長公共子串算法,即LCSstrSeL和LCSstrSCeL.LCSstrSeL跨越已有的最長公共子串長度,與LCSstrDP相比,代碼同樣簡潔,平均計算效率提高近一箇數量級,併且不需要額外的存儲空間.LCSstrSCeL是在LCSstrSeL的基礎上,增加字符跨越、連續同值區間跨越等機製,平均效率較LCSstrSeL亦有一定程度的提高,內存開銷與LCSstrDP相近,在中小長度的字符串LCSstr計算中,平均計算效率高于LCSstrSA,某些情況下的計算效率可達到亞線性的速度.
사조량개급정자부천적최장공공자천(LCSstr)시일류중요자부천분석문제,재자부천근사필배、계산궤병독특정마대비등방면유착엄범적용도.최장공공자천산법목전주요포괄동태규화산법(LCSstrDP)화후철수조산법(LCSstrSA),분별용우단천화장천적최장공공자천계산.전자대마간길,단계산속도교만,후자속도흔쾌단산법비상복잡.제출량충기우쌍향비교적최장공공자천산법,즉LCSstrSeL화LCSstrSCeL.LCSstrSeL과월이유적최장공공자천장도,여LCSstrDP상비,대마동양간길,평균계산효솔제고근일개수량급,병차불수요액외적존저공간.LCSstrSCeL시재LCSstrSeL적기출상,증가자부과월、련속동치구간과월등궤제,평균효솔교LCSstrSeL역유일정정도적제고,내존개소여LCSstrDP상근,재중소장도적자부천LCSstr계산중,평균계산효솔고우LCSstrSA,모사정황하적계산효솔가체도아선성적속도.
