计算机科学
計算機科學
계산궤과학
COMPUTER SCIENCE
2014年
4期
178-183
,共6页
XML模式%模式推断%正则表达式%自动机%算法
XML模式%模式推斷%正則錶達式%自動機%算法
XML모식%모식추단%정칙표체식%자동궤%산법
XML schema%Schema inference%Regular expression%Automata%Algorithm
XML模式推断问题的主要任务可以归约为从一个句子集合中推断出对应的确定型正则表达式.提出了一类在XML模式中大量出现的受限正则表达式,给出了该类正则表达式的推断算法.该算法首先根据给定的句子集合构造自动机,然后根据自动机和句子集合推断出对应的正则表达式.该算法的时间复杂度为max(O(|V| +|E|),C(L)),其中V和E分别表示自动机的节点集合和边集合,L表示句子集合中所有句子的长度之和.对算法的终止性和正确性进行了证明.
XML模式推斷問題的主要任務可以歸約為從一箇句子集閤中推斷齣對應的確定型正則錶達式.提齣瞭一類在XML模式中大量齣現的受限正則錶達式,給齣瞭該類正則錶達式的推斷算法.該算法首先根據給定的句子集閤構造自動機,然後根據自動機和句子集閤推斷齣對應的正則錶達式.該算法的時間複雜度為max(O(|V| +|E|),C(L)),其中V和E分彆錶示自動機的節點集閤和邊集閤,L錶示句子集閤中所有句子的長度之和.對算法的終止性和正確性進行瞭證明.
XML모식추단문제적주요임무가이귀약위종일개구자집합중추단출대응적학정형정칙표체식.제출료일류재XML모식중대량출현적수한정칙표체식,급출료해류정칙표체식적추단산법.해산법수선근거급정적구자집합구조자동궤,연후근거자동궤화구자집합추단출대응적정칙표체식.해산법적시간복잡도위max(O(|V| +|E|),C(L)),기중V화E분별표시자동궤적절점집합화변집합,L표시구자집합중소유구자적장도지화.대산법적종지성화정학성진행료증명.
