基于上下文无关文法的数据抽取规则
2010-08-15宋娜娜
宋娜娜
(郑州航空工业管理学院信息科学学院,河南郑州450000)
通过分析大量的企业信息系统产生的文本数据的异同点,从文本数据携带的信息和数据结构形式出发,将文本数据文件结构归纳为：
文件名：在文件名中存在的一些重要数据应该被提取出来。
文件内容：文本文件的内容是最重要的部分,从结构上又可将文件的内容分为表头、表体、表尾三大部分。分别表示实际数据的不同方面,综合起来则可以表示完整的无缺失的数据。
在对文本数据文件结构分析的基础上,需要将这些数据的抽取规则[1]表示出来。文法是描述语言的语法结构的形式规则,这些规则是准确和易于理解的,而且有相当强的描述能力,足以描述各种不同的结构,上下文无关文法所定义的语法范畴是完全独立于这种范畴可能出现的环境的[2],用上下文无关文法来表示数据抽取规则比较合适。
1 上下文无关文法
上下文无关文法包括四个组成部分：一组终结符号,一组非终结符号,一个开始符号以及一组产生式。
形式上讲,一个上下文无关文法G是一个四元式(Vt,Vn,S,Φ),其中：
Vt是一个非空有限集,它的每个元素称为终结符号;
Vn是一个非空有限集,它的第个元素称为非终结符号,Vt∩Vn=φ;
S是一个非终结符号,称为开始符号;
Φ是一个产生式集合(非空有限集),每个产生式的形式是P→a,其中,P∈Vt,a∈(Vt∪Vn)＊。开始符号S至少必须在某个产生式的左部出现一次。
本文用：：=代替→,用＜＞表示终结符号,用《》表示非终结符号。
2 文件名结构分析
大量的企业信息系统都有自己的一套文本数据文件名的生成规则,即在“.”后面放置有用的信息或在文件名的特定几位上表示所需要的有用信息。
若在有用信息与其它信息之间有某种特定的分隔符,则以这个特定的分隔符为标记,提取出有用信息。若在有用信息与其它信息之间没有特定的分隔符,而是在特定的位上放置有用信息,则指定信息提取的起始位置和长度,并取出有用信息。
文件名数据抽取规则的文法表示为：
《文件名》：：=《按分隔符抽取》|《按位置抽取》
《按分隔符抽取》：：=＜分隔符号＞＜从第几个符号开始＞＜至第几个符号结束＞《按分隔符抽取》
＜分隔符号＞：：=某个特定符号
＜从第几个符号开始＞：：=开始分隔符编号(数字值)
＜至第几个符号结束＞：：=结束分隔符编号(数字值)
《按位置抽取》：：=＜数据开始位置＞＜抽取数据长度＞《按位置抽取》
＜数据开始位置＞：：=数据在文件名中的开始位置值(数字值)
＜抽取数据长度＞：：=需提取的数据长度(字符个数,数字值)
3 文件内容分析
将文件内容的结构分为表头、表体、表尾三部分分别进行研究。其中,表头和表尾在某些文本数据文件中可能存在,也可能不存在,但表体作为表达数据信息的主体部分应该总是存在的。
3.1 表头数据的结构分析
作为基本结构的开始,表头部分往往包含着以下信息：
⑴需滤掉的说明信息行：指整个数据块的说明部分,包括数据来源、对应的报表名称等。
⑵需保留的数据行：相对于之前需滤掉的多余信息,这部分信息是需要保存到数据库中的。不论这部分数据量的大小,它们都将被抽取出来,并与后面的表体数据和表尾数据组合成一个完整的数据行。
对这些需保留的数据的抽取方法主要有以下两种：
⑴从特定分隔字符后抽取指定长度的字符;
⑵从指定位置开始直接抽取指定长度的字符。
综合以上的分析,可以得到描述表头结构及抽取规则的文法如下：
《表头数据》：：=《行数据信息》《表头数据》|《行数据信息》
《行数据信息》：：=《开始标志行》|《需过滤数据行》|《需保留数据行》
《开始标志行》：：=《包含特征字符串行》|《等于特征字符串行》|《匹配特征字符串行》
《需过滤数据行》：：=《包含特征字符串行》|《等于特征字符串行》|《匹配特征字符串行》
《包含特征字符串行》：：=＜特征字符串＞＜包含比较方法＞
《等于特征字符串行》：：=＜特征字符串＞＜等于比较方法＞
《匹配特征字符串行》：：=＜特征字符串＞＜匹配比较方法＞
《需保留数据行》：：=《按分隔符抽取》|《按位置抽取》
《按分隔符抽取》：：=＜分隔符号＞＜从第几个符号开始＞＜至第几个符号结束＞
《按分隔符抽取》|＜分隔符号＞＜从第几个符号开始＞＜至第几个符号结束＞
＜分隔符号＞：：=某个特定符号
＜从第几个符号开始＞：：=开始分隔符编号(数字值)
＜至第几个符号结束＞：：=结束分隔符编号(数字值)
《按位置抽取》：：=＜数据开始位置＞＜抽取数据长度＞《按位置抽取》|＜数据开始位置＞＜抽取数据长度＞
＜数据开始位置＞：：=数据在文件中的开始位置值(数字值)
＜抽取数据长度＞：：=需提取的数据长度(字符个数,数字值)
＜特征字符串＞：：=字符串
＜包含比较方法＞：：=判断目标字符串是否包含特征字符串
＜等于比较方法＞：：=判断目标字符串是否等于特征字符串
＜匹配比较方法＞：：=判断目标字符串是否匹配特征字符串
3.2 表体数据的结构分析
表体部分作为数据的主体部分,包含着绝大部分需提取的信息,正确、高效地抽取出数据是进一步将数据加载到数据库的关键[3]。表体数据包含了最终记录中的主要字段值,它们主要通过两种方式被抽取出来：
第一种是通过特定的分隔符将各字段值分隔开,常用的有逗号、“ˆ”、“|”等符号,各字段值的长度不是固定的,对这种类型的数据在抽取时要识别出分隔符,并以这些特定的符号为边界抽取各个字段。
第二种情况正好相反,各个字段值的长度是固定的,没有特定的分隔符来分隔这些字段,对这类数据的抽取应当采取指定各个字段在数据行中的开始位置和长度的方法。
综合这两种情况,可以得到描述表体数据的结构和抽取规则的文法为：
《表体数据》：：=《行数据信息》《表体数据》|《行数据信息》
《行数据信息》：：=《需过滤数据行》|《标准数据行》|《需字段填充数据行》|《需组合数据行》|《需字段替换数据行》
《需过滤数据行》：：=《包含特征字符串行》|《等于特征字符串行》|《匹配特征字符串行》
《包含特征字符串行》：：=＜特征字符串＞＜包含比较方法＞
《等于特征字符串行》：：=＜特征字符串＞＜等于比较方法＞
《匹配特征字符串行》：：=＜特征字符串＞＜匹配比较方法＞
＜特征字符串＞：：=针对具体应用的字符串
＜包含比较方法＞：：=判断目标字符串是否包含特征字符串
＜等于比较方法＞：：=判断目标字符串是否等于特征字符串
＜匹配比较方法＞：：=判断目标字符串是否匹配特征字符串
《标准数据行》：：=《按分隔符抽取》|《按位置抽取》
《按分隔符抽取》：：=＜分隔符号＞＜从第几个符号开始＞＜至第几个符号结束＞《按分隔符抽取》|＜分隔符号＞＜从第几个符号开始＞＜至第几个符号结束＞
＜分隔符号＞：：=某个特定符号
＜从第几个符号开始＞：：=开始分隔符编号(数字值)
＜至第几个符号结束＞：：=结束分隔符编号(数字值)
《按位置抽取》：：=＜数据开始位置＞＜抽取数据长度＞《按位置抽取》|＜数据开始位置＞＜抽取数据长度＞
＜数据开始位置＞：：=数据在文件中的开始位置值(数字值)
＜抽取数据长度＞：：=需提取的数据长度(字符个数,数字值)
《需字段填充数据行》：：=《需填充字段》《需字段填充数据行》|《完整字段》《需字段填充数据行》|《需填充字段》|《完整字段》
《需填充字段》：：=《按分隔符抽取》|《按位置抽取》
《完整字段》：：=《按分隔符抽取》|《按位置抽取》
《需字段替换数据行》：：=《需替换字段》《需字段替换数据行》|《完整字段》《需字段替换数据行》|《需替换字段》|《完整字段》
《需替换字段》：：=《按分隔符抽取》|《按位置抽取》
《完整字段》：：=《按分隔符抽取》|《按位置抽取》
《需组合数据行》：：=《元素数据行》《需组合数据行》|《元素数据行》
《元素数据行》：：=《按分隔符抽取》|《按位置抽取》
3.3 表尾数据结构分析
表尾数据部分和表头部分数据类似,往往都包含着记录行的一些关键字段,也有一些多余的无用信息需要被过滤掉,在此不赘述。
以上是对数据结构表示文法的分析。结合当前流行的XML语言的特点也可以使用XML来实现文本数据文件结构的表示文法。
[1] 蒋立源,康慕宁.编译原理[M].西安：西北工业大学出版社,2005.
[2] 张云.谈数据仓库建设中的ETL过程[J].计算机系统应用,2005(8)：36-37.
[3] 王晓东.计算机算法设计与分析[M].北京：电子工业出版社,2001.
