计算机学报
計算機學報
계산궤학보
CHINESE JOURNAL OF COMPUTERS
2013年
8期
1714-1728
,共15页
周军锋%王博%田姗姗%陈子阳%郭景峰
週軍鋒%王博%田姍姍%陳子暘%郭景峰
주군봉%왕박%전산산%진자양%곽경봉
可扩展标记语言%关键字查询%结果子树%自顶向下处理策略%最低最小公共祖先
可擴展標記語言%關鍵字查詢%結果子樹%自頂嚮下處理策略%最低最小公共祖先
가확전표기어언%관건자사순%결과자수%자정향하처리책략%최저최소공공조선
XML%keyword search%subtree results%top-down processing strategy%Smallest Lowest Common Ancestor(SLCA)
构建结果子树是XML关键字查询得以完成的关键步骤之一.针对已有方法求解子树效率低的问题,文中提出一种自顶向下的子树构建算法——TDTMS.TDTMS以自顶向下、深度优先的方式求解满足条件的子树根结点,避免了已有方法求解SLCA结点时存在的公共祖先重复处理问题.对于给定的子树根结点,TDTMS以自顶向下、广度优先的方式构建子树,可以在建树过程中快速裁剪无用结点,从而获得了最小的时间和空间复杂度.最后通过实验验证了TDTMS在时间和空间两方面的性能优势.
構建結果子樹是XML關鍵字查詢得以完成的關鍵步驟之一.針對已有方法求解子樹效率低的問題,文中提齣一種自頂嚮下的子樹構建算法——TDTMS.TDTMS以自頂嚮下、深度優先的方式求解滿足條件的子樹根結點,避免瞭已有方法求解SLCA結點時存在的公共祖先重複處理問題.對于給定的子樹根結點,TDTMS以自頂嚮下、廣度優先的方式構建子樹,可以在建樹過程中快速裁剪無用結點,從而穫得瞭最小的時間和空間複雜度.最後通過實驗驗證瞭TDTMS在時間和空間兩方麵的性能優勢.
구건결과자수시XML관건자사순득이완성적관건보취지일.침대이유방법구해자수효솔저적문제,문중제출일충자정향하적자수구건산법——TDTMS.TDTMS이자정향하、심도우선적방식구해만족조건적자수근결점,피면료이유방법구해SLCA결점시존재적공공조선중복처리문제.대우급정적자수근결점,TDTMS이자정향하、엄도우선적방식구건자수,가이재건수과정중쾌속재전무용결점,종이획득료최소적시간화공간복잡도.최후통과실험험증료TDTMS재시간화공간량방면적성능우세.
