关系分词技术

收稿日期:2007-10-17;修回日期:2007-12-27基金项目:国家科技基础条件平台应用服务支撑系统资助项目(2005DKA63900)作者简介:梁娜(1983-),硕士研究生,主要研究方向为网络信息处理(liangna1983@126.
com);耿国华(1955-),女,教授,博导,主要研究方向为网络信息处理、数据挖掘;周明全(1954-),男,教授,博导,主要研究方向为科学计算技术、智能信息处理.
自然语言处理中的语义关系与句法模式互发现*梁娜1,耿国华1,周明全2(1.
西北大学信息科学与技术学院,西安710127;2.
北京师范大学信息科学与技术学院,北京100875)摘要:在国家科技基础条件平台中如何建设汉语字词之间的语义关系库,并且利用初始的语义关系库自动获取句法模式和新的关系.
使用了句法模式的概念,并提出了利用已有关系发现新模式、利用已有模式发现新关系的方法,创造性地设计相关模型并实现了一个中文语义关系知识库系统.
利用此系统结合自然语言处理相关技术,从搜狗语料库和百度百科页面文件中大规模自动化获取了有效关系200多个,并从中提取了继承、同义等有效的新关系1000多条.
实验证明其效率达到约40%,主要取决于关系中查询词的距离取值和语料库本身的性质.
关键词:自然语言处理;信息抽取;语义关系抽取;句法模式中图分类号:TP301.
2文献标志码:A文章编号:1001-3695(2008)08-2295-04Mutual-extractionbetweensemanticrelationshipsandlexicalpatternsinnaturallanguageprocessingLIANGNa1,GENGGuo-hua1,ZHOUMing-quan2(1.
SchoolofInformationScience&Technology,NorthwestUniversity,Xi'an710127,China;2.
CollegeofInformationScience&Technology,BeijingNormalUniversity,Beijing100875,China)Abstract:Thispaperfocusedonanautomaticapproachtobuildasemanticrelationshipdatabaseinthenationalscienceandtechnologyinfrastructureplatform,identifiedlexicalpatternsandextendednewsemanticrelationshipsbyexistingonesfromcorpus.
Infacttherewerealotofpotentialrelationshipsbetweenwords,andthesewordscouldbeconnectedtoabignetworkbythem.
Sotheproblemwashowtomodelthisnetworkandhowtogetrelationshipsautomatically.
Withtheconceptoflexicalpattern,devisedanewmethod:generalizednewpatternsformtheexistingrelationshipsandgeneralizednewrelationshipsfromexistingpatterns.
ThispaperdesignedandrealizedaChinesesemanticrelationshipsknowledgebasesystem.
UsingthissystemandNLPtechnology,extractedmorethan200effectiverelationshipsandmorethan1000newrelationships(suchasinheritandsynonym)fromSogoucorpusandBaiduBaike.
Theexperimentresultshowsthattheprecisionoftheserelationshipsisaround40%,dependsonthedistancebetweenthesearchingwordsandthetypeofarticlesincorpus.
Keywords:naturallanguageprocessing(NLP);informationextraction;relationextraction;lexicalpatterns0引言自然语言处理是计算机科学领域与人工智能领域中的一个重要方向.
实现人机间自然语言通信意味着要使计算机既能理解自然语言文本的意义,也能以自然语言文本来表达给定的意图、思想等.
前者称为自然语言理解,后者称为自然语言生成.
然而这两者都远不如人们原来想象的那么简单.
造成困难的根本原因是自然语言广泛存在的各种各样的歧义性或多义性;自然语言的形式(字符串)与其意义之间是一种多对多的关系,且相互间存在大量的关系.
大约20世纪90年代开始,自然语言处理领域发生了巨大的变化.
首先对系统输入,要求研制的自然语言处理系统能处理大规模的真实文本,而不是如以前的研究性系统那样,只能处理很少的词条和典型句子;其次对系统的输出,鉴于真实理解自然语言是十分困难的,对系统并不要求能对自然语言文本进行深层的理解,但要能从中抽取有用的信息,如自动提取索引词、过滤、检索、进行自动摘要等.
虽然上述新趋势给自然语言处理领域带来了成果,但从理论方法的角度看,由于采集、整理、表示和有效应用大量知识的困难,这些系统更依赖于统计学的方法和其他简单的方法或技巧,如马尔可夫模型、向量空间模型、TF-IDF算法等.
这些统计学的方法和其他简单的方法似乎也快达到它们的极限了.
因此,近年来人们开始越来越重视字词间语义关系的基础工作,展开了大规模真实语料库的研制以及大规模、信息丰富的词典编制工作等.
比如普林斯顿大学认知科学实验室开发了一部在线词典数据库系统WordNet,将英文的单词组织为同义词集合,每一个集合表示一个基本的词汇概念,并在这些词汇概念间建立了多种词汇语义关系.
目前,WordNet被成功地用于词义消歧、语言学自动处理、双语及多国语机器翻译、检索系统等一系列语言工程[1].
在WordNet的影响下,许多国家都已着手实施构造本民族语言的WordNet,我国也出现了CWB中文词库等一些手工建立的语义词典.
这些基础性的工作为自然语言处理作出了很大的贡献.
但是必须看到,这些基础性的工作也还是远远不够的,它们仅仅是静态的、最原始的数据,必须从大规模语料和词第25卷第8期2008年8月计算机应用研究ApplicationResearchofComputersVol.
25No.
8Aug.
2008典中获取动态的字词间关系,并且这个过程应当是自动化的、可自学习的.
综合以上观点,笔者认为,要取得新的更大的进展,仅靠目前已有的方法是远远不够的.
因此,在国家科技基础条件平台应用服务支撑系统中,本文将基于字词间语义关系的推理方法与基于统计的方法结合起来,创造性地提出并实现了一个语义关系知识库系统,包括基于句法模式的语义关系自动化发现等功能(本系统是基于中文的自然语言处理工作,本文所提到的字词均指汉语字词).
1语义关系和句法模式1.
1字词间的语义关系语义关系是字词之间具有的各种广泛而大量的关系,所有字词依靠关系构成一个巨大的语义网络.
定义1词间关系两个以上的词之间会有某种语义上的联系,这里只研究词之间的二元关系.
设W是所有词的集合,R是W上所有具有某种语义联系的词的偶对集合.
显然,R是W*W的一个子集,有RW*W.
例如,词W1与W2是W中的两个元素,若它们之间在语义上具有某种确定的关系R(如同义、反义等),则称它们之间具有语义关系R,记为W1RW2.
本文定义的词间主要的语义关系有:a)Ris-a———从属,即面向对象中的继承—泛化关系,表示为Ris-a={(father,son)|father∈W∧son∈W∧Sonisakindoffather}.
说明:此关系为自反、反对称、传递的,因此是W上的半序关系.
b)Rcomp———组合,表示整体与部分的关系,如计算机—内存,表示为Rcomp={(whole,part)|whole∈W∧part∈W∧partisacomponentofwhole}.
c)Rattr———属性,这里指一个词描述了另一个对象的属性,如葡萄—味道.
d)Rattr-v———属性值,这里指一个词作为描述另一个对象的属性的值,如葡萄—酸甜.
e)Raction———动作,一个词作为对象的某种操作,如狗—吠.
f)Rsynonym———同义,词义相同或相近.
说明:此关系为自反、对称、传递的,因此是W上的等价关系,所有的同义词构成W上的一个划分,将W划分为若干个等价类.
g)Rantonym———反义,词义相反或相对.
说明:此关系为反自反、对称的.
h)Rgeneral———一般关联,两个或多个词的某种关系,如水果—果脯.
说明:此关系为广泛意义的关联,所有未归类为以上关系的二元集合均可视为这里的一般关联.
以上对关系的几种定义方法部分来自于面向对象思想,并且可以产生自动演绎、归纳等特性.
这是现有的WordNet、CBW中文词典等尚未做到的.
将一个词代表的具体东西看做一个对象,将一个词代表的本体看做一个类,则词与词之间就会产生面向对象中的各种关系.
最广泛、最直接的关系是继承、组合、关联等.
子类的一些特性可以从父类得到继承,系统会自动演绎出子类的基本特性.
同样,系统也能归纳某父类下所有的子类字词,如果它们都具有某种相同属性词或操作词,那么这个词就会自动上移到父类.
1.
2句法模式句法模式是一种用来在语料库中匹配句子、发现关系的语法规则.
例如:"A是一种B"或"A是B的一种",就是两个用来发现继承关系的模式.
本文中模式的书写规则以正则表达式为基础,略加修改,概述如下:a)[],里面的词描述了一个取值范围,如[father]代表继承关系中父类集合中的某个词.
b)+,代表1或多个正好在它之前的那个字符,如A+代表A、AA、AAA等.
c)*,代表0或多个任意字符.
d)$,代表行结束符,如".
$"能够匹配字符串"这是一个苹果.
"的句尾.
此符号在后文中主要用来断句.
e)&,代表AND关系,如[father&N.
]表示既符合父类又是名词的一个取值.
f)|,代表OR关系,如[、|.
]表示顿号或句号.
在语料库中的一个实例:S=软玉主要是由透闪石、阳起石等组成的一种矿物.
———语料来自新华网以上书写规则对应的模式为M=[whole&son]是由([part]、)+[part]等组成的一种[father]另外,模式也有好坏之分.
通过好的模式可以发现新的正确的关系.
比如通过以上模式发现了语料中的三个关系:Rcomp:软玉—透闪石,软玉—阳起石;Ris-a:软玉—矿物.
2语义关系的自动获取2.
1问题陈述定义2词是语义中代表某种概念实体的、可以独立运用的最小单位.
定义3句子是能表达一个完整的意思、由m个词W与标点符号连接的有序集合,句尾一般使用句号、问号、省略号、感叹号等结束,记为S={W|W1W2…Wm}.
定义4文章是由n个句子S与段落标记组成的有序集合,记为A={S|S1S2…Sn}.
定义5语料库是由p篇不重复文章A组成的集合,记为D={A|A1A2…Ap}.
若已知:a)自然语言中存在某些确定的词间关系R1,R2,…,这里用Ri统一表示.
b)已有一些词间关系Ri的子集Ri′,其中:Ri′Ri.
c)大规模语料库D.
如何利用已知的Ri′和D扩充Ri′为Ri″,使得Ri′Ri″且Ri″/Ri趋向于Φ(即如何利用已知的关系Ri′从D中得到尽可能多的未知关系).
2.
2问题分析既然R是词间广泛存在的某种关系,这种关系又是存在于自然语言中的本质属性,那么R必然在自然语言中有所体现.
一个比较具体的例子是:·6922·计算机应用研究第25卷现有大规模语料库D1,保存有大量不同种类的常见文本.
其中:句子S1,S2∈D1,且S1和S2的内容为S1=20世纪20年代初,上海马路各式交通工具混杂,据当时报纸报道,上海街头"每天要通过大量各式各样的车辆———汽车、卡车、电车、马车、人力车、独轮推车、手推车……以及成千上万的行人".
S2=最新与最旧的、最快与最慢的,以及最自由散漫的行人,并驾齐驱,蔚为大观.
———《车影行踪》,上海档案信息网若在分析此段语料之前,已有关于"车"的关系的记录,保存在两张表中,如表1、2所示.
表1Word_basic相关词synonymantonymgrammarexplain车车辆/N.
(略.
)新/旧A.
(略.
)快/慢A.
(略.
)………表2Word_relations相关词关系相关词关系交通工具车Ris-a车马路Rgeneral车汽车Ris-a车速度Rattr车电车Ris-a速度快Rattr-v车马车Ris-a速度慢Rattr-v……可根据表中的数据,将隐藏在句子S1中的关系挖掘出来:S′1=车辆———汽车、卡车、电车、马车、人力车、独轮推车、手推车…从中可以看到一定的句法模式.
事实上,设满足一定的模式记为M,则从S1′中可推得:M1=[father]———([son]、)+[son]…其中:+号代表1或多个在它之前的单词.
通过模式M1可以有效地发现新的关系,如(车辆,卡车)∈Ris-a等.
同理,可从S2中利用已有关系发现蕴涵的模式M2:S2=最新与最旧的、最快与最慢的,以及最自由散漫的行人,并驾齐驱,蔚为大观.
M2=(最[synonym1&adj]与最[synonym1&adj]的[、|,])+可见,需要做的是找到某种算法,从语料库D中自动化地得到有效的模式,再利用各种模式来发现更多词间关系,从而扩充已有的关系集.
3实现方法3.
1系统设计本系统分为语义关系数据库、系统程序模块组、大规模语料库和应用程序接口四部分,如图1所示.
本文着重阐述的是系统程序模块组中的关系发现维护组件和模式发现维护组件.
3.
2主要思路和使用的技术1)断句原理和标准要对句子进行处理,首先要对大规模文本库D中的文章进行断句.
本文对于文章的断句提出了采用基于标点符号与句子长度相结合(防止句子过长或无标点)的方法.
设文章A可被断句为n个句子:A={S|S1S2…Sn},可作为断句依据的标点符号集合为P,句子长度为L,最大长度为Lmax,则认为满足以下条件的划分为一次满足要求的断句:(i∈Γ)($i∈P)∨L分词技术得到了句子,接下来就要对句子进行分析,分词是其中必不可少的一个步骤.
本系统使用基于统计学的二阶马尔可夫分词模型进行分词.
一般来说,N阶马尔可夫模型就是假设当前词的出现概率只与它前面的N个词有关(马尔可夫假设).
这样,一个句子就构成了一条马尔可夫链.
重要的是这些概率参数都是可以通过大规模语料库来计算的.
比如三元概率有P(Wi|Wi-2Wi-1)≈count(Wi-2Wi-1Wi)/count(Wi-2Wi-1).
其中:count(…)表示一个特定词序列在整个语料库中出现的累计次数.
这样,若一个句子可以有多种划分,本文认为满足最大概率的划分是最合理的分词,即取P(W1,W2,W3,…,Wn)的最大值为最佳分词结果.
关于这方面详细资料参见文献[2].
3)倒排索引思想在句子集上的应用对于文档集合上的关键词检索,最基本的查询方法可以通过顺序扫描文本的方式来实现,这种方法称为顺序查找.
顺序查找基本上无须对文档集合中的信息作任何形式的预处理,查询时直接在文档中进行基于字符串的简单匹配.
这种方法相对比较简单,容易实现,但当需要查找的文件大小达到一定数量级别时,其效率就非常低.
正因如此,人们提出了各种不同的查找方法,倒排索引就是其中的一种方法.
索引是在搜索时使用到的一种特殊的数据结构.
当文档的数量相当庞大,并且这些文档中的信息相对稳定时,建立索引可以大大提高搜索时的效率.
索引的技术主要有以下三种:倒排索引、后缀数组和签名文件.
其中,倒排索引在当前大多数的信息检索系统中得到了广泛的应用,它对于关键词的搜索非常有效.
倒排索引是一种面向单词的索引机制.
通常情况下,倒排索引结构由词典和出现情况两部分组成.
对于每一个单词,都会有一个词汇列表记录单词在所有文档中出现的位置,这些位置可以是单词的位置(文本中的第几个单词),也可以是字符的位置(文本中的第几个字符).
更多详情参见文献[3].
以上文出现的两个句子S1、S2简单举例说明.
首先在对所有的文章进行断句、分词后,将所有句子的集合进行自动编号,得到关于句子(已分词)的表,如表3所示.
表3关于句子的表S_IDsentence120世纪20年代初,上海马路各式交通工具混杂,据当时报纸报道,上海街头"每天要通过大量各式各样的车辆———汽车、卡车、电车、马车、人力车、独轮推车、手推车……以及成千上万的行人"2最新与最旧的、最快与最慢的,以及最自由散漫的行人,并驾齐驱,蔚为大观3……设表3中一共有m个句子,利用此表中句子的编号,对每个出现过的词都建立一个m位的二进制索引值,每个索引值的第i位以0(或1)表示这个词没有(或有)在第i篇出现过.
比如车辆在句子S1中出现过,在S2中没有出现过,则末两位为01.
结果如表4所示.
·7922·第8期梁娜,等:自然语言处理中的语义关系与句法模式互发现汉语字词语义关系数据库大规模语料库字维护组件词维护组件关系发现、维护组件模式发现、维护组件各种应用程序:聚类搜索引擎、自动作诗软件…字词字词间关系句法模式语义关系数据库系统程序图1语义知识库的系统构架一览表4实验结果item_IDiteminverted_Index1车辆xxx…xxx012行人xxx…xxx113……这样,在系统中去查询一个单词在哪些句子中出现过,则只需读出这个单词的索引,取出值为1的位号即可.
4)句法模式发现方法在实际使用中,设多个有一定关系R的词记为Wi,则Wi∈R,将它们的集合记为Wsearch,使用它们作为关键词进行查询.
现需查询它们同时在哪些句子中出现,则可将它们的反向索引相与:result=ANDi∈Wsearchinverted_Indexi其中:result为代表结果的二进制串,最后将其中值为1的序号读出即可得到满足要求的句子.
接下来,对找到的句子进行去噪预处理、词性标注、关系代词替换、冗余信息截去等工作后,即可得到一条模式.
3.
3算法设计与优化1)建立句子的倒排索引表对语料库D中的所有文章A进行预处理、断句、分词,得到所有句子的集合S,并对S按照上文所说原理建立倒排索引.
2)两个词result计算选定R,令初始的Wsearch只有两个元素:Wsearch={W1,W2},W1,W2∈R.
利用倒排索引表计算包含这两个词的所有的句子集合,其序号记为result1,2,则有result1,2=W1∧W2可以用同样的方法计算R中的所有n*(n-1)/2个W对,得到n*(n-1)/2个result.
但注意到同样的关系集R里并不是任何两个单词都有关系R.
因此将所有R上的词以它们的关系连接为图,记d为图上两点的距离.
规定满足条件d(W1,W2)=1的两个词才进行索引的并操作.
此步骤实际是限制只对具有直接关系的单词对进行查找,大大提高了效率.
3)多词result合并将所有具有一个相同W且值不为零的result进行两两相与操作,得到的结果中为1的位代表了三个相关单词同时出现的句子.
将新的result重复进行上面的两两相与操作,以找出同时出现四个、五个、……相关词的句子,直到result全为零,或只剩一个result为止.
4)从句子中提取模式将所有的result进行整理,一一读出对应的句子序号,记录在一张初始表中.
表中记录了初步满足要求的句子,表项主要有:句子序号S_ID使用的关系R已分词的句子S′根据这张初始表,对找到的句子进行词性标注、关系代词替换、冗余信息截去等工作后,就可得到一条模式.
将模式记录在一张模式表中:模式序号M_ID模式M出现次数F原句ID列表在此同时注意合并同类模式并记录相同模式出现的次数T.
由于自然语言的多样性,在实际使用中这样的处理也会得到大量无意义的模式,可以使用基于统计的方法来消歧,将出现概率极小的模式和关系视为无效.
设最小支持度是某模式出现的次数,记为supmin(F).
在本系统中,认为满足supmin(F)>2的模式为可信模式.
5)对每个关系集合Rj上的所有元素分别作如上步骤1)~4)的操作,找出所有的句子,并进行步骤4)的处理,得到模式.
在这里只是简单介绍了字词关系、倒排索引、句子模式等在句子集上应用的基本原理,系统中真正的细节会比此处介绍的复杂很多.
3.
4实现过程与结果分析1)语料的选取本系统采用了搜狗语料库和百度百科作为对比.
搜狗语料库是搜狗lab提供的文本分类语料库(精简版),来源于Sohu新闻网站保存的大量经过编辑手工整理与分类的新闻语料与对应的分类信息,包括财经、IT、健康、体育、旅游、教育、招聘、文化、军事九大类.
精简版共17910个文件,平均每个文件占1~10KB,共约2500万字,可以说是十分翔实丰富的,基本代表了一个完整覆盖面广的语料环境[4].
另外,还抓取了百度百科的17000个网页作为对比,平均每个网页的大小与搜狗文本相近.
百度百科是基于维基思想的在线百科辞典,采集它的网页作为语料库实验材料有涵盖面很全面、解释性和陈述性的词语多等特点,无疑是非常好的语料库资源[5].
2)初始语义关系库的获取对于相关词的语义库,可以采用多种方法,如人工收集、结合程序自动导入已有关系列表等来完成初始关系库的建立,为后面的自动化挖掘采集作准备.
3)实验及结果分析最终利用上文所讲的方法编写PHP程序进行了实现.
模式和关系的发现经历了如下过程:初步模式→有效模式→初步关系→有效关系.
首先从语料库中得到了大量的初步模式,经过支持度计算筛选出有效模式;再将有效模式中的初步关系抽取出来;最后对关系进行人工鉴定,找出认为有效的关系.
图2显示了在两种语料库中发现的关系和模式数量对比.
由图2可见,用此方法产生了大量的无效初步模式.
但使用经过自动统计支持度后得到的200多条有效模式,最终发现了一些关系,有效关系约1000多条,它们的正确率在搜狗语料库和百度百科中分别是40%和42%.
由此可见这个方法是有一定效果的.
有趣的是,其中最有效的几条模式是由标点符号发挥了重大作用,如模式[son、]+[son]等[*]的[father].
这样简短而有效的模式在系统中占了绝大多数.
4结束语现有的很多基础知识库或本体系统都是手工构建的,近年来有关如何自动或半自动地构建类似系统的研究越来越多.
本文基于自然语言处理目前的现状和不足,提出了建设基础知识库和语义库的重要性及一个具体的半自动化构建方法,使得计算机实现语义级别的检索和分类有了一条可行的途径.
经实验,该方法能够大大提高语义关系的构建效率,且在一定程度上能够保证质量.
(下转第2308页)·8922·计算机应用研究第25卷自动化,2004,26(5):46-48.
[2]姚丽.
21世纪我国制造业信息化发展新趋势———APS,ERP和MES系统集成研究[J].
物流技术,2005(10):237-240.
[3]HARDWICKM.
TheSTEPservicesreferencemanual,Teckreport96004[R].
NewYork:LaboratoryforIndustrialInformationInfra-structure,RensselaerPolytechnicInstitute,1995.
[4]陈斗雪,黎毅明,陈一天,等.
无线射频识别及其在制造业中的应用[J].
计算机工程与设计,2006,27(8):1359-1361.
[5]AMER-YAHIAS.
AWeb-servicesarchitectureforefficientXMLdataexchange[C]//Procofthe20thInternationalConferenceonDataEngineering.
Boston:IEEEComputerSociety,2004.
[6]仇丽青,赵庆祯.
Web服务在动态联盟中的应用[J].
计算机应用与软件,2005,22(11):68-70.
[7]蓝伯雄.
企业资源优化与优化模型[J].
计算机集成制造系统—CIMS,2004,10(3):241-251.
[8]王海军,马士华,赵勇.
大量定制环境下基于延迟制造的多级供应控制模型研究[J].
管理工程学报,2005,19(1):6-9.
[9]汪定伟,于海斌.
敏捷制造ERP中的关键优化问题及其数学模型[J].
控制工程,2002,9(6):1-6.
[10]周水银,陈荣秋.
面向顾客需求的供应链合作伙伴选择模型[J].
华中科技大学学报,2001,29(5):38-40.
[11]CHENKe-jia,JIPing.
Amixedintegerprogrammingmodelforad-vancedplanning,andscheduling(APS)[J].
EuropeanJournalofOperationalResearch,2007,181(11):515-522.
[12]HASTINGSNAJ,YEHCH.
Billofmanufacture[J].
ProductionandInventoryManagementJournal,1992,33(4):27-31.
[13]OKAMOTOA,GENM,SUGAWARAM.
Integrateddatastructureandschedulingapproachformanufacturingandtransportationusinghybridgeneticalgorithm[J].
JournalofIntelligentManufactu-ring,2006,17(4):411-421.
[14]NISHIOKAY.
Supplychainplanningforcomputeroptimizedmanufacturing[J].
ManagementSystemsJapanIndustrialManage-mentAssociation,1999,9(3):132-136.
[15]NISHIOKAY.
Anewturnofmanufacturingenterprisearchitecturewithadvancedplanningandscheduling[J].
ManagementSys-tems,JapanIndustrialManagementAssociation,2002,12(1):9-13.
[16]PSLXConsortium.
PSLXtechnicalspecifications,recommendation[EB/OL].
(2003).
http://www.
pslx.
org.
[17]MESXJointWorkingGroup.
MESXwhitepaper[EB/OL].
(2004).
http://www.
mstc.
or.
jp/faop/doc/informative/MESX-WP.
pdf.
[18]OKAMOTOA,GENM,SUGAWARAM.
APSsystembasedonschedulermoGAandXML[J].
JournaloftheSocietyofPlantEn-gineersJapan,2005,17(2):15-24.
[19]OKAMOTOA,GENM,SUGAWARAM.
SchedulingapproachusingbillofmanufacturingandgeneticalgorithminAPS[C]//ProcofWorkshoponIntelligentManufacturing&LogisticsSystems.
2005.
[20]DYCKHOFFH.
Atypologyofcuttingandpackingproblem[J].
Eu-ropeanJournalofOperationalResearch,1990,44(2):145-159.
[21]WSCHERG,HAUSSNERH,SCHUMANNH.
Animprovedtypo-logyofcuttingandpackingproblems[J].
EuropeanJournalofOp-erationalResearch,2006.
[22]JrCOFFMANEG,GAREYMR,JOHNSONDS.
Approximationalgorithmsforbinpacking:anupdatedsurvey[M]//AUSIELLOG,LUCERTINIM,SERAFINIP.
Algorithmsdesignforcomputersystemdesign.
NewYork:Springer,1984:49-106.
[23]JrCOFFMANEG,GAREYMR,JOHNSONDS.
Approximationalgorithmsforbinpacking:asurvey[M]//HOCHBAUMD.
Approx-imationAlgorithmsforNP-hardProblems.
Boston:PWSPublishingCo.
,1981:147-172.
[24]HAESSLERR,SWEENEYP.
Cuttingstockproblemsandsolutionprocedures[J].
EuropeanJournalofOperationalResearch1991,54(2):141-150.
[25]蔡力钢,吕文林.
面向集中下料的钣金排样编程系统[J].
华中理工大学学报,1999,27(6):66-68.
(上接第2298页)本文提出的语义关系模型只定义了几种比较常见的关系,并且词间关系没有强弱权值.
事实上在自然语言中,关系广泛而大量地存在,许多关系无法精确分类,或是并不明显.
在系统的实现中,仅用二元关系去建模也显露出一些缺点.
今后的工作中将着重致力于语义关系模型的改进,包括基于统计的软关系自动生成和词间关系的模糊化等.
参考文献:[1]ELLBARUMC.
WordNet:anelectroniclexicaldatabase[M].
Mas-sachusetts:MITPress,1998:1-22.
[2]梁南元.
书面汉语自动分词系统———CDWS[J].
中文信息学报,1987,1(2):44-52.
[3]李栋,史晓东.
一种支持高效检索的实时更新倒排索引策略[J].
情报学报,2006,25(1):16-20.
[4]搜狗实验室[EB/OL].
http://www.
sogou.
com/labs/.
[5]百度百科[EB/OL].
http://baike.
baidu.
com.
[6]RUIZ-CASADOM,ALFONSECAE,CASTELLSP.
Automatisingthelearningoflexicalpatterns:anapplicationtotheenrichmentofWord-NetbyextractingsemanticrelationshipsfromWikipedia[J].
Data&KnowledgeEngineering,2007,61(3):484-499.
[7]姚天顺,朱靖波,张利,等.
自然语言理解:一种让机器懂得人类语言的研究[M].
2版.
北京:清华大学出版社,2002.
[8]晋耀红.
HNC(概念层次网络)语言理解技术及其应用[M].
北京:科学出版社,2006.
[9]XIASun,ZHENGQing-hua.
Anapproachtoacquiresemanticrela-tionshipsbetweenterms[C]//ProcofACMSymposiumonAppliedComputing.
NewYork:ACMPress,2005:1630-1633.
[10]ZHUGEHai,ZHENGLi-ping,ZHANGNan,etal.
Anautomaticse-manticrelationshipsdiscoveryapproach[C]//Procofthe13thInterna-tionalWorldWideWebConferenceonAltermateTrackPapers&Pos-ters.
NewYork:ACMPress,2004:278-279.
[11]ZHANGKuo,WUGang,LIJuan-zi.
Logicalstructurebasedseman-ticrelationshipextractionfromsemi-structureddocuments[C]//Procofthe15thInternationalConferenceonWorldWideWeb.
NewYork:ACMPress,2006:1063-1064.
[12]王永庆.
人工智能原理与方法[M].
西安:西安交通大学出版社,1998.
[13]BERRYMJA,LINDFFGS.
数据挖掘技术[M].
北京:机械工业出版社,2006.
[14]戴汝为.
社会智能科学[M].
上海:上海交通大学出版社,2007.
[15]曹晶.
同义词挖掘及其在概念信息检索系统中的应用研究[D].
长春:东北师范大学,2006.
[16]饶弋宁,刘强,杜晓黎,等.
支持智能搜索的自扩展知识库模型的研究和设计[J].
计算机应用研究,2006,23(6):223-226.
·8032·计算机应用研究第25卷