D0I:10.13374/j.issnl00I63.2006.12.042 第28卷第12期 北京科技大学学报 Vol.28 No.12 2006年12月 Journal of University of Science and Technology Beijing Dec.2006 基于语义单元表示树剪枝的关键字过滤方法 高庆狮李莉刘宏岚 北京科技大学智能、语言与计算机科学研究所，北京100083 摘要传统的关键字过滤技术满足了人们一定的需要，但是其灵活性差，效果有限，难以识别和 过滤变形过的关键字，本文将语义单元应用在网络监测中，提出了一种新的关键字过滤方法，这 种方法可以有效地识别和过滤网络中经过变形的关键字，其时间复杂度为O(L)而非O(LN),其 中L是文本的长度，N是关键字集的规模，即无论关键字集有多么大的规模，算法消耗的时间是 固定不变的，这对网络监测和信息过滤有着较强的实用性· 关键词网络监测：信息过滤：关键字；语义单元 分类号TP18 随着网络的迅速普及，大量的信息出现在互 题，这种方法的执行速度慢，不易理解，在实际的 联网上，网络在造福于人类的同时，也给用户带来 网络信息处理中并不实用]；神经网络法进行 了很多问题，针对日益增多的不良信息，如何对 过滤的思想是在其内部存储可行模式的整个集 互联网进行有效的监测，维护网络空间的安全和 合，当文本的关键字被抽出并输入时，可通过存储 稳定，是亟待解决的问题，网络信息过滤技术专 的信息对文本进行主题判断叮，但是这种方法同 门对网络上的海量信息进行分辨、匹配、过滤、屏 样存在方法一的缺陷，无论哪种算法，面对种类 蔽等，从而提供给用户真正感兴趣的信息，屏蔽掉 繁多、格式多变的各种网络信息，都难以达到较好 无用或者不良信息山，但是针对网络上的反动、 的效果，本文通过分析非法网络信息的特征，提 色情、暴力等不良信息，仅仅采用通常的基于关键 出一种基于语义单元表示树集的关键字过滤算 字的屏蔽远不能解决问题，传播者稍微改变某些 法，将引文[]中提出的机器翻译方法应用在信 关键字的形式即可躲过检查，大量新的词汇也在 息过滤中，可以有效提高关键字过滤的效果， 不断出现，因而如何识别这类非法信息并将它们 从网络中过滤掉成为网络安全和信息过滤的重要 1非法网络信息的内容和特征 研究课题 关键字过滤技术的宗旨在于防止非授权的信 目前常用的过滤算法主要有关键字匹配法、 息内容进出网络，包括政治性、健康性、保密性、隐 潜在语义索引法、神经网络法]，关键字匹配法 私性、产权性、防护性几个方面0的信息， 以特征向量为基础，用特征向量来表示用户模板 由于非法信息的特殊性，网络中的词通常以 和待过滤文本，通过计算其夹角余弦来衡量其相 非正常形式出现，以逃避基于关键字过滤方法的 似程度，这种方法简单易行，但是不能确保关键字 屏蔽；同时，网络上的网页文件多使用大量的标签 选取的准确性，而且词与词之间相互独立的假设 来表达不同的格式信息，这些标签本身也成为某 在实际环境中很难满足]；潜在语义索引法认 些非法信息躲避过滤的工具，网络上的非法信息 为文本中的词与词之间存在潜在的语义结构，用 的特征如下山 这种结构表示词和文本，在消除词与词之间的相 (1)用特殊字符将敏感字分开，如：“发，* 关性、化简文本向量之后，计算待过滤文本和用户 *.财”，“本￥%拉并※登”； 模板之间的相似度来判断两者是否属于同一个主 (②)用拼音或其他形式进行字的替换，如“Da 收稿日期：2005-09-20修回日期：2006-05-09 纪Yan”,“心#70；r；e：”； 基金项目：国家自然科学基金资助项目(N。.CJZRJ小60343010， (③)用标点或者空格代替，如“**访问美 GZRJ-60573014):国家“973”计划资助项目(No 2003CB317007) 国”暗指国家领导人等 作者简介：高庆狮(1931一)，男，教授，中国科学院院士 鉴于非法网络信息格式的多变性和复杂性
基于语义单元表示树剪枝的关键字过滤方法 高庆狮 李 莉 刘宏岚 北京科技大学智能、语言与计算机科学研究所北京100083 摘 要 传统的关键字过滤技术满足了人们一定的需要但是其灵活性差效果有限难以识别和 过滤变形过的关键字．本文将语义单元应用在网络监测中提出了一种新的关键字过滤方法．这 种方法可以有效地识别和过滤网络中经过变形的关键字其时间复杂度为 O（ L ）而非 O（ L N）其 中 L 是文本的长度N 是关键字集的规模即无论关键字集有多么大的规模算法消耗的时间是 固定不变的这对网络监测和信息过滤有着较强的实用性． 关键词 网络监测；信息过滤；关键字；语义单元 分类号 TP18 收稿日期：20050920 修回日期：20060509 基金项目：国家自然科学基金资助项目（No．GJZRJJ－60343010 GJZRJJ －60573014）；国 家 “973” 计 划 资 助 项 目 （ No． 2003CB317007） 作者简介：高庆狮（1934－）男教授中国科学院院士 随着网络的迅速普及大量的信息出现在互 联网上网络在造福于人类的同时也给用户带来 了很多问题．针对日益增多的不良信息如何对 互联网进行有效的监测维护网络空间的安全和 稳定是亟待解决的问题．网络信息过滤技术专 门对网络上的海量信息进行分辨、匹配、过滤、屏 蔽等从而提供给用户真正感兴趣的信息屏蔽掉 无用或者不良信息［1］．但是针对网络上的反动、 色情、暴力等不良信息仅仅采用通常的基于关键 字的屏蔽远不能解决问题传播者稍微改变某些 关键字的形式即可躲过检查大量新的词汇也在 不断出现因而如何识别这类非法信息并将它们 从网络中过滤掉成为网络安全和信息过滤的重要 研究课题． 目前常用的过滤算法主要有关键字匹配法、 潜在语义索引法、神经网络法［2］．关键字匹配法 以特征向量为基础用特征向量来表示用户模板 和待过滤文本通过计算其夹角余弦来衡量其相 似程度这种方法简单易行但是不能确保关键字 选取的准确性而且词与词之间相互独立的假设 在实际环境中很难满足［3－4］；潜在语义索引法认 为文本中的词与词之间存在潜在的语义结构用 这种结构表示词和文本在消除词与词之间的相 关性、化简文本向量之后计算待过滤文本和用户 模板之间的相似度来判断两者是否属于同一个主 题这种方法的执行速度慢不易理解在实际的 网络信息处理中并不实用［5－6］；神经网络法进行 过滤的思想是在其内部存储可行模式的整个集 合当文本的关键字被抽出并输入时可通过存储 的信息对文本进行主题判断［7］但是这种方法同 样存在方法一的缺陷．无论哪种算法面对种类 繁多、格式多变的各种网络信息都难以达到较好 的效果．本文通过分析非法网络信息的特征提 出一种基于语义单元表示树集的关键字过滤算 法将引文［8－9］ 中提出的机器翻译方法应用在信 息过滤中可以有效提高关键字过滤的效果． 1 非法网络信息的内容和特征 关键字过滤技术的宗旨在于防止非授权的信 息内容进出网络包括政治性、健康性、保密性、隐 私性、产权性、防护性几个方面［10］的信息． 由于非法信息的特殊性网络中的词通常以 非正常形式出现以逃避基于关键字过滤方法的 屏蔽；同时网络上的网页文件多使用大量的标签 来表达不同的格式信息这些标签本身也成为某 些非法信息躲避过滤的工具．网络上的非法信息 的特征如下［11］： （1） 用特殊字符将敏感字分开如：“发．∗∗ ∗．财”“本￥％拉＃※登”； （2） 用拼音或其他形式进行字的替换如“Da 纪 Yuan”“＆＃70；＆＃114；＆＃101；”； （3） 用标点或者空格代替如“∗∗访问美 国”暗指国家领导人等． 鉴于非法网络信息格式的多变性和复杂性 第28卷 第12期 2006年 12月 北 京 科 技 大 学 学 报 Journal of University of Science and Technology Beijing Vol．28No．12 Dec．2006 DOI:10．13374／j．issn1001－053x．2006．12．042
.1192 北京科技大学学报 2006年第12期 通常的基于关键字的过滤技术很难过滤掉这些信 讨论过，此处只作简单介绍 息，需要对这些过滤算法进行改进 使用不同自然语言的人们彼此可以沟通，不 2网络监测方法的原理 同自然语言可以互译，是因为它们的句子有相同 语义，任何一个具体的自然语言中一个句子的语 假定通常情况下文本中待过滤的关键字为字 言层次上的语义，我们称之为句义，在句义中表 符串（如“本拉登”），对于关键字中的每个字符，在 达一个意思的单元称为语义单元(SE)·句义由语 待过滤文本中都可能出现其变化格式；或者在字 义单元构成，任何一个具体的自然语言中表达一 符之间插入各种各样的干扰字符，以防止通常的 个意思的单元称为该语义单元在该具体自然语言 关键字过滤方法对其进行过滤， 中的“语义单元表示”(SER)·一个具体的自然语 首先建立一个关键字集S,S中每个元素S: 言的句子是一个句义在该具体的自然语言中的 均是代表非法网络信息的关键字；对关键字S:中 “句义表示” 的每一个字符W(S:)j(简写为W),通常存在 全部语义单元构成语义语言，显然，语义语 的格式变换（例如拼音变换、ASCIⅡ码变换、同音 言包括全部句义，全部在【自然语言的语义单元 字变换等)称为U(W,)变换；称由U(W)变 表示构成自然语言I.自然语言【包括全部在I 换产生的字符集为U(W,时)变换集；所有的 自然语言的句子，一种自然语言可以看成为语义 U(W,)变换集组成关键字集S的U变换库= 语言的在该语言上的一个表示，从这个角度看， {U(W)变换集|W,∈S:且S:∈S}. 句子（句义表示）是由（带变量和不带变量的）语义 对应于关键字的各个字符之间插入的格式多 单元表示构成，两个自然语言(I,J)之间的翻译 变的干扰字符，我们称这种变换为V变换；亦建 可以看作为两种表示之间的转换。 立相应的干扰字符集合，称其为V变换集，V变 例如，英语的句子“This coat belongs to you'”, 换集同时为所有的关键字所共享，注意，通常情 是句义“这件外套的归属权是你”在英文中的表 况下，V变换只在关键字的各个字符之间出现， 示，句义在中文中的表示是“这件外套是我的”. 不会出现在关键字之前或者之后 该句义可以写成“B.ogto(Thi(coat),you)”,它由 例如：对于关键字“本拉登”来说，“本”的U “Belong to(X,Y)”,“Thi(N)”,“coat”,“you”这四个 变换集={本，ben,BEN,Ben,…},“拉”的U变 不可弃语义单元组成，其中“Bogo(X,Y)”和 换集={拉，la,La,LA,…},“登”的U变换集= Thi(N)”中的参数X,Y和N均表示事物义. {登，deng,Deng,DENG,…;V变换集为“，”， 在计算机系统内部可以表示为表1， *,一，%，，8，，，@，#，！，~，十，8， 表1语义单元与语义单元表示库 …}. Table 1 Semantic element and SER-base 这样，原来关键字S:=W,1W,2…Wi,m(其 语义单元参数 汉语表示 英语表示类型 中n为关键字S:的长度)变换为如下扩展形式： 1 2,N,N2N是N2的N belong to N2J 1,N 这L(N)N this N N S=W,1V1W.2V2…W,n-1Vn-1W,m,其中 3 0 外套 coat 9 Wk∈U(W,k)变换集，k=1,…,n;V;V变 4 0 你 You N人 换集的闭包，=1,2，…，n一1；以往从文本中简 注意，表1中L(N)是N对应的计量词，由 单屏蔽关键字S:的操作就被扩展到屏蔽符合S 专门的函数来实现；N人是比N更细化的类型， 这一模式的任何字符串.这种形式正好与文献[8 字符串在匹配N人的同时也匹配N,这样分类可 9]中句子由语义单元表示交错构成相对应，于 以使语义单元包含更多的语义信息， 是将S=Wi.1V1W.2V2…W-1Vm-1W,n 语义单元有带参数（如“this N”)和不带参数 看作语义单元，查找关键字S:=W,1Wi,2…W.n (如“coat”)两种，对应三种语义单元表示：实量 的操作即可转化为从句子中匹配S:的语义单元 (例如“coat”)、纯虚量（如“AN”,其中A是形容 的操作（下一节将简单介绍语义单元的概念）· 词，N为名词)、实量虚量混合（例如“this N) 语义单元表示中实量虚量排列的所有可能可 3 语义语言及语义单元表示树集 以规范成四种基本形式(S,SX,XS,XSX)及其 语义语言的基本概念已经在文献[8]中详细 之间的连接，如表2所示，其中S表示实量串，X
通常的基于关键字的过滤技术很难过滤掉这些信 息需要对这些过滤算法进行改进． 2 网络监测方法的原理 假定通常情况下文本中待过滤的关键字为字 符串（如“本拉登”）对于关键字中的每个字符在 待过滤文本中都可能出现其变化格式；或者在字 符之间插入各种各样的干扰字符以防止通常的 关键字过滤方法对其进行过滤． 首先建立一个关键字集 SS 中每个元素 Si 均是代表非法网络信息的关键字；对关键字 Si 中 的每一个字符 W （ Si）j （简写为 Wij）通常存在 的格式变换（例如拼音变换、ASCII 码变换、同音 字变换等）称为 U（ Wij）变换；称由 U（ Wij）变 换产生的字符集为 U （ Wij ） 变换集；所有的 U（ Wij）变换集组成关键字集 S 的 U 变换库＝ ｛U（ Wij）变换集｜Wij∈Si 且 Si∈S｝． 对应于关键字的各个字符之间插入的格式多 变的干扰字符我们称这种变换为 V 变换；亦建 立相应的干扰字符集合称其为 V 变换集V 变 换集同时为所有的关键字所共享．注意通常情 况下V 变换只在关键字的各个字符之间出现 不会出现在关键字之前或者之后． 例如：对于关键字“本拉登”来说“本”的 U 变换集＝｛本benBENBen…｝“拉”的 U 变 换集＝｛拉laLaLA…｝“登”的 U 变换集＝ ｛登dengDengDENG…｝；V 变换集为｛“” ∗－％＾＆∗＜＞＠＃！～＋＆ …｝． 这样原来关键字 Si＝ Wi1 Wi2… Win （其 中 n 为关键字 Si 的长度）变换为如下扩展形式： S ∗ i ＝ W ∗ i1V1W ∗ i2V2… W ∗ in－1V n－1 W ∗ in其中 W ∗ ik∈ U（ Wik）变换集k＝1…n；V j∈ V 变 换集的闭包j＝12…n－1；以往从文本中简 单屏蔽关键字 Si 的操作就被扩展到屏蔽符合 S ∗ i 这一模式的任何字符串．这种形式正好与文献［8 －9］中句子由语义单元表示交错构成相对应于 是将 S ∗ i ＝ W ∗ 11 V1W ∗ i2 V2… W ∗ in－1 V n－1 W ∗ in 看作语义单元查找关键字 Si＝ Wi1Wi2… Win 的操作即可转化为从句子中匹配 S ∗ i 的语义单元 的操作（下一节将简单介绍语义单元的概念）． 3 语义语言及语义单元表示树集 语义语言的基本概念已经在文献［8］中详细 讨论过此处只作简单介绍． 使用不同自然语言的人们彼此可以沟通不 同自然语言可以互译是因为它们的句子有相同 语义．任何一个具体的自然语言中一个句子的语 言层次上的语义我们称之为句义．在句义中表 达一个意思的单元称为语义单元（SE）．句义由语 义单元构成．任何一个具体的自然语言中表达一 个意思的单元称为该语义单元在该具体自然语言 中的“语义单元表示”（SER）．一个具体的自然语 言的句子是一个句义在该具体的自然语言中的 “句义表示”． 全部语义单元构成语义语言．显然语义语 言包括全部句义．全部在 I 自然语言的语义单元 表示构成自然语言 I．自然语言 I 包括全部在 I 自然语言的句子．一种自然语言可以看成为语义 语言的在该语言上的一个表示．从这个角度看 句子（句义表示）是由（带变量和不带变量的）语义 单元表示构成两个自然语言（ IJ）之间的翻译 可以看作为两种表示之间的转换． 例如英语的句子“This coat belongs to you” 是句义“这件外套的归属权是你”在英文中的表 示句义在中文中的表示是“这件外套是我的”． 该句义可以写成“Belong to（This（coat）you）”它由 “Belong to（ XY ）”“This（ N）”“coat”“you”这四个 不可弃语义单元组成其中“Belong to （ XY ）” 和 “This（ N）”中的参数 XY 和 N 均表示事物义． 在计算机系统内部可以表示为表1． 表1 语义单元与语义单元表示库 Table1 Semantic element and SER-base 语义单元 参数 汉语表示 英语表示 类型 1 2NN2 N 是 N2 的 N belong to N2 J 2 1N 这 L （ N） N this N N 3 0 外套 coat N 4 0 你 You N人 注意表1中 L （ N）是 N 对应的计量词由 专门的函数来实现；N人 是比 N 更细化的类型 字符串在匹配 N人 的同时也匹配 N这样分类可 以使语义单元包含更多的语义信息． 语义单元有带参数（如“this N”）和不带参数 （如“coat ”）两种对应三种语义单元表示：实量 （例如“coat”）、纯虚量（如“ A N”其中 A 是形容 词N 为名词）、实量虚量混合（例如“this N”）． 语义单元表示中实量虚量排列的所有可能可 以规范成四种基本形式（ SSXXSXSX）及其 之间的连接如表2所示．其中 S 表示实量串X ·1192· 北 京 科 技 大 学 学 报 2006年第12期
Vol.28o.12 高庆狮等：基于语义单元表示树剪枝的关键字过滤方法 .1193 表示虚量串，“”表示匹配开始，“$”表示两个基 如果几个语义单元表示中的第一个实量都是 同一个字，那么这些语义单元表示可以构成一棵 本形式之间的连接，除了纯虚量串X以外，所有 以该字开始的语义单元表示树.例如，以more开 的匹配比较总是从实量开始，然后是实量前的虚 始的语义单元表示树为： 量，最后才是实量后的虚量， (VI J.I-)more (N*I J*than (SL*IJ 表2语义单元表示由四种基本形式(S,SX,KS,XSX)和连接 ￥hesitated￥|N(S's米|$can(describe￥| ($)构成 shake a stick at ))lenough *lonce*lordinarily Table 2 SER consists of four basic types (S,SX,XS,XSX)and their connections ($ *Ipleased￥|satisfied*|sufficient米kS)米|…) I and (more (*lbetter lless *l are SER排列类型 实现 SER排列类型 实现 drowned…*lbeef*…),其中*”表示语义单 s Is XS XIS 元表示的有关信息，如编号、类型等。 SX I SX XSX XISX 一棵语义单元表示树转换成为一棵语义单元 SXS IsxSIs XSXS xIsx$Is 表示主表示和一个语义单元表示子表示集，例如： SXSX ISX SI SX XSXSX XI SXSI SX "more (than (N $'s *IN $can (describe SXS...XS IsxsIs...xSIs XSXSX…S xIsxSIsx...sIs shake a stick at *))lfire in N $'s bed straw SXS…XSX ISXSs…xSI sx XSXSX…SX xIsxSIsx...$Isx N $than N2 $'s IJ*)I A $than A2*)" X 示为表3，该语义单元表示树可以转换成为主表 示（表4）和一个子表示集（表5）， 表3一个以实量“more”开始的语义单元表示树的例子 Table 3 An example of SER-Tree starting with real-string"more" 语义单元表示 语义 more than $'s* 比N的多 more than Scan describe 并非N所能描述 more than N Scan shake stick N数不清的 more fire in $'s bed straw* N的前途暗礁重重 more N $than N2 $'5 比N2多的N more N Sthan 比J多的N more Sthan A20 A比A2多 表4以“moe”开始的语义单元表示树对应的主表示 表5以“moe”开始的语义单元表示树对应的子表示集 Table 4 Main-representation in the example of SER-Tree starting Table 5 Sub-representation of SER-Tree starting with"more" with“moe” 编号 SER子表示集 SER主表示 1 more than N S1* $can describe* more than $2* shake stick more than N $3* 4 S's bed straw more fire in N S4* 5 Sthan N2 $8=S1* more S5* 6 Sthan more $6* Sthan A20 more $7* 把语义单元表示库中含两个及以上实量串的 示集并入库中，经过排序等处理程序，把新的语义 语义单元表示如表4和表5那样分解为主表示和 单元表示库转换为树形，称为语义单元表示树， 子表示集，用主表示修改语义单元表示库，把子表
表示虚量串“｜”表示匹配开始“＄”表示两个基 本形式之间的连接．除了纯虚量串 X 以外所有 的匹配比较总是从实量开始然后是实量前的虚 量最后才是实量后的虚量． 表2 语义单元表示由四种基本形式（ SSXXSXSX）和连接 （＄）构成 Table2 SER consists of four basic types （ SSXXSXSX） and their connections （＄） SER 排列类型 实现 S ｜S SX ｜SX SXS ｜SX＄｜S SXSX ｜SX＄｜SX SXS… XS ｜SX＄｜S… X＄｜S SXS… XSX ｜SX＄｜S… X＄｜SX X ｜X SER 排列类型 实现 XS X｜S XSX X｜SX XSXS X｜SX＄｜S XSXSX X｜SX＄｜SX XSXSX… S X｜SX＄｜SX…＄｜S XSXSX… SX X｜SX＄｜SX…＄｜SX 如果几个语义单元表示中的第一个实量都是 同一个字那么这些语义单元表示可以构成一棵 以该字开始的语义单元表示树．例如以 more 开 始的语义单元表示树为： （ V｜J｜－） more （ N∗｜J∗｜than （ SL∗｜J ∗｜〈hesitated〉∗｜N（＄’s∗｜＄can （describe∗｜ shake a stick at∗））｜enough∗｜once∗｜ordinarily ∗｜pleased∗｜satisfied∗｜sufficient∗｜〈S〉∗｜…） ｜and （more （∗｜〈a〉∗）｜better∗｜less∗）｜are drowned …∗｜beef∗｜…）其中“∗”表示语义单 元表示的有关信息如编号、类型等． 一棵语义单元表示树转换成为一棵语义单元 表示主表示和一个语义单元表示子表示集例如： 树“more （than （N ＄’s∗｜N ＄can （describe∗｜ shake a stick at∗））｜fire in N ＄’s bed straw ∗｜ N ＄than （ N2＄’s∗｜J∗）｜A ＄than A2∗）”表 示为表3该语义单元表示树可以转换成为主表 示（表4）和一个子表示集（表5）． 表3 一个以实量“more”开始的语义单元表示树的例子 Table3 An example of SER-Tree starting with rea-l string “more” 语义单元表示 语义 more than N ＄’s∗ 比 N 的多 more than N ＄can describe∗ 并非 N 所能描述 more than N ＄can shake a stick at∗ N 数不清的 more fire in N ＄’s bed straw∗ N 的前途暗礁重重 more N ＄than N2 ＄’s∗ 比 N2 多的 N more N ＄than J∗ 比 J 多的 N more A ＄than A2∗ A 比 A2 多 表4 以“more”开始的语义单元表示树对应的主表示 Table4 Main-representation in the example of SER-Tree starting with “more” SER 主表示 more than N ＄1∗ more than N ＄2∗ more than N ＄3∗ more fire in N ＄4∗ more N ＄5∗ more N ＄6∗ more A ＄7∗ 表5 以“more”开始的语义单元表示树对应的子表示集 Table5 Sub-representation of SER-Tree starting with “more” 编号 SER 子表示集 1 ＄’s∗ 2 ＄can describe∗ 3 ＄can shake a stick at∗ 4 ＄’s bed straw∗ 5 ＄than N2 ＄8＝＄1∗ 6 ＄than J∗ 7 ＄than A2∗ 把语义单元表示库中含两个及以上实量串的 语义单元表示如表4和表5那样分解为主表示和 子表示集用主表示修改语义单元表示库把子表 示集并入库中经过排序等处理程序把新的语义 单元表示库转换为树形称为语义单元表示树． Vol．28No．12 高庆狮等： 基于语义单元表示树剪枝的关键字过滤方法 ·1193·
,1194 北京科技大学学报 2006年第12期 〈根据字W:对已经取出的所有关键 4 算法设计及分析 字表示树进行剪枝； 关键字S:=W,1W.2…W,n(其中n为关 } 键字S:的长度)变换为扩展形式S= else W.1V1W.2V2…Wa-1Vm-1W,n(其中 读入下一个字符； Wk∈U(W.k)变换集，k=1,,n;V;∈V变 换集的闭包，=1,2，…，n一1)之后，以往从文本 f(不存在没有被剪掉的表示树) 中简单屏蔽关键字S:的操作就被扩展到屏蔽符 S需要被过滤； 合S这一模式的任何字符串. else 依照上一节中将语义单元表示库转换为语义 S可正常输出： } 单元表示树的方法，我们也同样可以将S= 设网络信息文本中句子的长度为L,1是关 W1V1W.2V2…W,-1Vn-1Wn转换为以下 键字表示的平均长度，是每棵关键字表示树结 树形表示，其中W是W对应的关键字符，= 点的平均分支数，N是关键字表示库的容量，M 1,,n 是U变换集的容量，m是每个字符的U变换集 W,1(V1,$1); 中的平均元素数目， $1: W.2(V2,$2); 对句子中每个字，从U变换库中取出其对应 的关键字符的时间为O(m),从语义单元库中取 $n-2:W.a-1(Vm-1,Sn-1) 出该关键字符的语义单元表示树所需的时间为 $n-1:Wi,m; 0(ln),所以对整个句子而言，取出语义单元表示 将所有的S:(S:∈关键字集S)的扩展形式 树的总时间为O(Lm十Lln) S转换为树形表示，形成关键字表示库，对其进 剪枝的时间是根据L个字逐一对已经取出 行排序之后，得到关键字集$的关键字表示树 的语义单元表示树进行剪枝，设每个字要对已经 (与上节中的语义单元表示树类似)， 被取出的数目为x(x<)的树进行剪枝，对每棵 以句子为单位，依次取出待过滤的文本信息； 树的一个节点平均要比较n次，因此总的剪枝时 对每一句，依次取出其中每一个字符；对每一个字 间为(0+1+2+…+1+l+l)n≤ 符，分析其是否存在于U变换库中，若存在，可以 O(Lln)≤O(Lm+Lln),由于l,n,m均为固 得到对应的关键字符W,;取以W,为实量开始 定值，所以该算法的计算时间T=O(L),与N 的关键字表示树，使用文献[9]中提出的快速剪枝 无关，也就是说，即使关键字达到几十万或者上百 算法，根据W,对已经取出的所有关键字表示树 万，算法消耗的时间是不变的， 进行剪枝，如果最终存在没有被剪掉的关键字表 5实验设计 示树，说明该句中含有需要过滤的关键字，该句子 被屏蔽。算法如下： 笔者从信箱收到的垃圾邮件和某些网站的文 while网络信息文本的内容非空{ 章中提取了部分关键字，作为试验用关键字表示 〈从文本中取出一句话(S》 集；从网络上下载了部分文本数据作为试验用的 while句子非空{ 网络信息文本，在计算机上编程实现后，得到的部 从句子中依次取出一个字符(S:); 分实验结果如表6所示 f(S:)在U变换库中){ 由结果来看，算法能够有效地对各种非法网 〈得到S:对应的关键字符W); 络信息进行识别和过滤，在实际应用过程中，可 〈取以W:为开始的语义单元表示 以灵活地对关键字集进行增加和删减，以满足不 树； 同场合的需要
4 算法设计及分析 关键字 Si＝ Wi1 Wi2… Win （其中 n 为关 键字 Si 的 长 度） 变 换 为 扩 展 形 式 S ∗ i ＝ W ∗ i1V1W ∗ i2V2 … W ∗ in－1 V n－1 W ∗ in （ 其 中 W ∗ ik∈ U（ Wik）变换集k＝1…n；V j∈ V 变 换集的闭包j＝12…n－1）之后以往从文本 中简单屏蔽关键字 Si 的操作就被扩展到屏蔽符 合 S ∗ i 这一模式的任何字符串． 依照上一节中将语义单元表示库转换为语义 单元表示树的方法我们也同样可以将 S ∗ i ＝ W ∗ i1V1W ∗ i2V2… W ∗ in－1V n－1 W ∗ in转换为以下 树形表示其中 Wij是 W ∗ ij对应的关键字符j＝ 1…n． Wi1（ V1＄1）； ＄1： Wi2（ V2＄2）； … … ＄ n－2： Win－1（ V n－1＄ n－1）； ＄ n－1： Win； 将所有的 Si（ Si∈关键字集 S）的扩展形式 S ∗ i 转换为树形表示形成关键字表示库对其进 行排序之后得到关键字集 S 的关键字表示树 （与上节中的语义单元表示树类似）． 以句子为单位依次取出待过滤的文本信息； 对每一句依次取出其中每一个字符；对每一个字 符分析其是否存在于 U 变换库中若存在可以 得到对应的关键字符 Wij；取以 Wij为实量开始 的关键字表示树使用文献［9］中提出的快速剪枝 算法根据 Wij对已经取出的所有关键字表示树 进行剪枝．如果最终存在没有被剪掉的关键字表 示树说明该句中含有需要过滤的关键字该句子 被屏蔽．算法如下： while〈网络信息文本的内容非空〉｛ 〈从文本中取出一句话（ S）〉 while〈句子非空〉｛ 从句子中依次取出一个字符（ Si）； if（ Si）在 U 变换库中）｛ 〈得到 Si 对应的关键字符 Wi〉； 〈取以 Wi 为开始的语义单元表示 树〉； 〈根据字 Wi 对已经取出的所有关键 字表示树进行剪枝〉； ｝ else 读入下一个字符； ｝ if（不存在没有被剪掉的表示树） S 需要被过滤； else S 可正常输出； ｝ 设网络信息文本中句子的长度为 Ll 是关 键字表示的平均长度n 是每棵关键字表示树结 点的平均分支数N 是关键字表示库的容量M 是 U 变换集的容量m 是每个字符的 U 变换集 中的平均元素数目． 对句子中每个字从 U 变换库中取出其对应 的关键字符的时间为 O（ m）从语义单元库中取 出该关键字符的语义单元表示树所需的时间为 O（ ln）所以对整个句子而言取出语义单元表示 树的总时间为 O（ Lm＋ L ln）． 剪枝的时间是根据 L 个字逐一对已经取出 的语义单元表示树进行剪枝设每个字要对已经 被取出的数目为 x（ x＜ l）的树进行剪枝．对每棵 树的一个节点平均要比较 n 次因此总的剪枝时 间为 （0＋1＋2＋ … ＋ l ＋ l ＋ l ） n ≤ O（ L ln）≤ O（ Lm＋ L ln）．由于 lnm 均为固 定值所以该算法的计算时间 T ＝ O（ L ）与 N 无关也就是说即使关键字达到几十万或者上百 万算法消耗的时间是不变的． 5 实验设计 笔者从信箱收到的垃圾邮件和某些网站的文 章中提取了部分关键字作为试验用关键字表示 集；从网络上下载了部分文本数据作为试验用的 网络信息文本在计算机上编程实现后得到的部 分实验结果如表6所示． 由结果来看算法能够有效地对各种非法网 络信息进行识别和过滤．在实际应用过程中可 以灵活地对关键字集进行增加和删减以满足不 同场合的需要． ·1194· 北 京 科 技 大 学 学 报 2006年第12期
Vol.28 No.12 高庆狮等：基于语义单元表示树剪枝的关键字过滤方法 .1195. 表6部分实验结果 Table 6 Part of experimental results 待过滤文本 发现的关健字 采用的操作 少奋斗20年赚钱机会，四您发财梦：www.ff555.com 赚饯、发财 过滤 致富信总：千元做老板，呼吸之间狂赚钱！ 致富、赚钱 过泌 开新奇爨利小店好赚钱！ 曇利、赚钱 过滤 运用无-坏-网或助\‘态\‘网的突破一网络封额的利器， 无界网、动态网 过滤 当前无-坏-网址：Https:∥ul.loUrdeSamarillo..com 无界网 过滤 当前助\'态\'网网址：HtpS:∥www.lIaOyang.X24hr.com 动态网 过滤 程，2005,23(10)：122 6结论 []曾致远，张莉·基于向量空间模型的网页文本表示改进算 法.计算机工程，2006,32(3)：134 介绍了一种新的关键字过滤方法，其算法的 [⑤]盖杰，王怡，武港山·潜在语义分析理论及其应用，计算机 时间复杂度为O(L),其中L为文本的长度，与 应用研究，2004,3：9 关键字库的规模无关，也就是说，即使关键字达到 [6]沈丽虹，周昌乐。基于语义空间的支持向量机的文本过滤 几十万或者上百万，算法消耗的时间是不变的. 计算机应用，2005,25(3)：664 初步实验证明，它可以有效过滤网络中经过变形 [7]任三，项婧·基于神经网络的电子邮件分类与过滤.计算机 的非法字，对网络监测、信息过滤等有较强的实用 工程与设计，2005,27(6)：1021 [8]Gao QS.Hu Y,Li L,et al.Semantic language and multi- 性，值得进行进一步的研究， language MT approach based on SL.J Comput Sci Technol. 2003,18(6):848 参考文献 [9]高小宇，高庆狮，胡二，等.基于语义单元表示树剪枝的高 [1]刘伟成，焦玉英，网络信息过滤的方法与相关技术研究.现 速多语言机器翻译.软件学报，2005,16(11)：P1909 代图书情报技术，2002,3,48 [10]张宏莉，翟健宏，胡铭曾.信息内容安全的主要技术及国 [2]何静，刘海燕，张惠民。基于文本的内容过滤算法的比较 内外对比.计算机教育，2005,1：74 计算机工程，2002,28(11)：9 [1]李东艳.互联网信息内容安全过滤方法研究[学位论文] [3】贺卫红，曹毅·基于向量空间模型文本过滤算法，系统工 太原：山西大学计算机与信息技术学院，2004：13 Key word filter method based on pruning on the tree representations of semantic elements GAO Qingshi,LILi,LIU Honglan Institute of Intelligence.Linguistics and Computer Science,University of Science and Technology Beijing Beijing 100083.China ABSTRACI Traditional key word filtering technology meets people s common need,but the flexibility and effect is too limited to recognize or filter the transformed key words.Semantic elements were applied to net monitor and a new key word filter method was proposed.This method could recognize and filter the transformed key words effectively.The filter time was 0(L)rather than general O(LN),where L was the length of text and N was the size of Keyword-base.It means this algorithm costs constant time even if N is hundreds of thousands or millions.It is very practical in net monitor and information filter. KEY WORDS net monitor;information filter;key word;semantic element
6 结论 介绍了一种新的关键字过滤方法其算法的 时间复杂度为 O（ L ）其中 L 为文本的长度与 关键字库的规模无关也就是说即使关键字达到 几十万或者上百万算法消耗的时间是不变的． 初步实验证明它可以有效过滤网络中经过变形 的非法字对网络监测、信息过滤等有较强的实用 性值得进行进一步的研究． 参 考 文 献 ［1］ 刘伟成焦玉英．网络信息过滤的方法与相关技术研究．现 代图书情报技术20023：48 ［2］ 何静刘海燕张惠民．基于文本的内容过滤算法的比较． 计算机工程200228（11）：9 ［3］ 贺卫红曹毅．基于向量空间模型文本过滤算法．系统工 程200523（10）：122 ［4］ 曾致远张莉．基于向量空间模型的网页文本表示改进算 法．计算机工程200632（3）：134 ［5］ 盖杰王怡武港山．潜在语义分析理论及其应用．计算机 应用研究20043：9 ［6］ 沈丽虹周昌乐．基于语义空间的支持向量机的文本过滤． 计算机应用200525（3）：664 ［7］ 任 项婧．基于神经网络的电子邮件分类与过滤．计算机 工程与设计200627（6）：1021 ［8］ Gao Q SHu YLi Let al．Semantic language and mult-i language MT approach based on SL．J Comput Sci Technol 200318（6）：848 ［9］ 高小宇高庆狮胡 等．基于语义单元表示树剪枝的高 速多语言机器翻译．软件学报200516（11）：P1909 ［10］ 张宏莉翟健宏胡铭曾．信息内容安全的主要技术及国 内外对比．计算机教育20051：74 ［11］ 李东艳．互联网信息内容安全过滤方法研究［学位论文］． 太原：山西大学计算机与信息技术学院2004：13 Key word filter method based on pruning on the tree representations of semantic elements GAO QingshiLI L iLIU Honglan Institute of IntelligenceLinguistics and Computer ScienceUniversity of Science and Technology BeijingBeijing100083China ABSTRACT Traditional key word filtering technology meets people’s common needbut the flexibility and effect is too limited to recognize or filter the transformed key words．Semantic elements were applied to net monitor and a new key word filter method was proposed．This method could recognize and filter the transformed key words effectively．The filter time was O（ L） rather than general O（ LN）where L was the length of text and N was the size of Keyword-base．It means this algorithm costs constant time even if N is hundreds of thousands or millions．It is very practical in net monitor and information filter． KEY WORDS net monitor；information filter；key word；semantic element Vol．28No．12 高庆狮等： 基于语义单元表示树剪枝的关键字过滤方法 ·1195·