正在加载图片...
,702 北京科技大学学报 第30卷 个语义单元重复是指它们在所有的自然语言上表示 采用特征分类法后整个语义单元知识库的处理效率 都一样，若只是在某些语言上的表示相同而在另一 将大大提高， 些语言上表示中不同，则它们不是重复的语义单元， 3,2特征分类下的去重复、去可弃 而是在相同表示的语言上存在歧义，需进行消歧 (1)特征分类下的去重复.对整个语义单元库 处理， 去重复时，如果采用2.3节中处理子库的去重复算 (2)去可弃处理，对子库中的全部语义单元集 法，则其计算复杂性是串行排序复杂性O(NbN), 进行去可弃处理与对单个句子的语义单元集去可弃 其中N是语义单元集的大小，由于整体库的规模 处理类似，但对子库处理的数据规模远远大于单句 远远大于各子库的规模，采用此方法效率较低 语义单元集.假设语义单元的所有的参数类型与语 采用特征分类法后去重复计算复杂性可以降低 义单元本身类型不同，而且其参数个数最多k个， 到O(NhM),其中N=KM,K是类别数量，M是 一般k≤4. 每一类的平均大小.例如，N=2×105,K=1000, 先从参数个数t=1(t≤k)的语义单元入手，代 M=1000,排序计算量可以降低一半.各个不同特 入类型为该参数类型的语义单元，然后检查是否有 征分类之间还可以并行计算（见3.3节） 语义单元与其相同，如果有，就清除与其相同的语 (2)特征分类下的去可弃.对整个语义单元库 义单元：如果代入的语义单元本身还带参数，也需要 去可弃时，如果采用2.3节的处理子库的去可弃算 代入类型为该参数类型的语义单元进行检查，所有 法，则数百万语义单元集合去可弃在一般非高性能 的带t个参数的语义单元处理完之后，处理带t= 计算机上的处理时间过长，采用特征分类法后由于 t十1个参数的语义单元，直到带有参数的语义单元 各个不同特征分类集合中各自进行排序消去，其计 全部处理完毕，为简化讨论，假设卫：是参数个数为 算复杂性可大幅度降低，具体方法是：从t=1开 k中的参数类型为i类型的语义单元个数的平均值， 始，对各个不同特征的分类集合中的语义单元，进行 在没有循环代入的情况下其去可弃计算复杂性为 代入和比较，消去t=0及t=1中的可弃语义单元. O(NN':),其中，N是语义单元集的大小，N'是 消去比较过程中，不仅充分利用特征分类大幅度地 带有参数的语义单元个数；卫：是参数个数为k中的 缩小比较的计算量，而且充分利用“可能被消去的语 参数类型为i类型的平均语义单元个数：如果语义 义单元的长度，等于被代入的语义单元长度加所代 单元的某个参数类型与语义单元本身类型相同，需 入的各个参量的语义单元长度减1”的这个特点，将 要引入长度控制机制，避免出现无限循环响计算复 搜索限制在一定长度的语义单元子集中，从而进一 杂性 步大幅度降低计算量 3将多个受限领域、场所、情景的完备的、无 (3)特征分类下的的目标驱动法去可弃，在采 可弃、无重复的多语语义单元子库进行合 用特征分类的情况下，还可以进一步采用以下“目标 驱动”"方法，从语义单元参数个数t=1入手，根据 并形成统一的多语语义单元知识库 参数在语义单元表示中位置，通过左串、右串及左右 将多个受限领域的多语语义单元子库进行合 串与t=0中的同特征分类单元进行匹配，寻找t= 并，并消除非正常歧义，形成高质量的统一多语语义 0中及部分t=1中的可弃语义单元，不需要全部进 单元知识库过程，如图2所示. 行代入·匹配方法可以采用类似子树剪枝法可.对 统一的多语语义单元知识库的形成过程中最主 t=2的处理，与t=1类似，只是位置结构复杂一 要的工作是对数量巨大（数百万）的语义单元及其表 些，同时寻找的可弃语义单元，不仅在t=1及部分 示去重复、去可弃和对非正常歧义进行消歧处理， t=2的单元中，而且也可能在t=0的单元中.对 由于处理数据量巨大，在处理过程中引入了降低计 >2的单元处理类似.由于计算量依赖于同特征分 算量的有效方法—特征分类法 类下可弃语义单元的数量，而不是搜索整个库中所 3.1特征分类 有的可能代入，所以计算复杂性还可以进一步下降. 语义单元及其表示有许多重要的特征，如语义 综上所述，采用特征分类法和目标驱动法后，其 单元的类型、参量的数目、各参量的类型或语义单元 计算复杂性已由原来的O(NNV:),降低到小于 类型的逻辑：特征分类是指综合语义单元的众多特 等于0(NMbm+ 征采用的均匀分类方法，语义单元类型数目根据粗 宫usem)产0(Nbm十 细可小可大，如果某类型比较大，就可以再细分 Nam)=O(Nam)=O(BN),其中U是参数个语义单元重复是指它们在所有的自然语言上表示 都一样．若只是在某些语言上的表示相同而在另一 些语言上表示中不同则它们不是重复的语义单元 而是在相同表示的语言上存在歧义需进行消歧 处理． （2） 去可弃处理．对子库中的全部语义单元集 进行去可弃处理与对单个句子的语义单元集去可弃 处理类似但对子库处理的数据规模远远大于单句 语义单元集．假设语义单元的所有的参数类型与语 义单元本身类型不同而且其参数个数最多 k 个 一般 k≤4． 先从参数个数 t＝1（ t≤k）的语义单元入手代 入类型为该参数类型的语义单元然后检查是否有 语义单元与其相同．如果有就清除与其相同的语 义单元；如果代入的语义单元本身还带参数也需要 代入类型为该参数类型的语义单元进行检查所有 的带 t 个参数的语义单元处理完之后处理带 t＝ t＋1个参数的语义单元直到带有参数的语义单元 全部处理完毕．为简化讨论假设 V ki是参数个数为 k 中的参数类型为 i 类型的语义单元个数的平均值 在没有循环代入的情况下其去可弃计算复杂性为 O（ NN′V k ki）其中N 是语义单元集的大小N′是 带有参数的语义单元个数；V ki是参数个数为 k 中的 参数类型为 i 类型的平均语义单元个数；如果语义 单元的某个参数类型与语义单元本身类型相同需 要引入长度控制机制避免出现无限循环响计算复 杂性． 3 将多个受限领域、场所、情景的完备的、无 可弃、无重复的多语语义单元子库进行合 并形成统一的多语语义单元知识库 将多个受限领域的多语语义单元子库进行合 并并消除非正常歧义形成高质量的统一多语语义 单元知识库过程如图2所示． 统一的多语语义单元知识库的形成过程中最主 要的工作是对数量巨大（数百万）的语义单元及其表 示去重复、去可弃和对非正常歧义进行消歧处理． 由于处理数据量巨大在处理过程中引入了降低计 算量的有效方法———特征分类法． 3∙1 特征分类 语义单元及其表示有许多重要的特征如语义 单元的类型、参量的数目、各参量的类型或语义单元 类型的逻辑；特征分类是指综合语义单元的众多特 征采用的均匀分类方法语义单元类型数目根据粗 细可小可大．如果某类型比较大就可以再细分． 采用特征分类法后整个语义单元知识库的处理效率 将大大提高． 3∙2 特征分类下的去重复、去可弃 （1） 特征分类下的去重复．对整个语义单元库 去重复时如果采用2∙3节中处理子库的去重复算 法则其计算复杂性是串行排序复杂性 O（ Nlb N） 其中 N 是语义单元集的大小．由于整体库的规模 远远大于各子库的规模采用此方法效率较低． 采用特征分类法后去重复计算复杂性可以降低 到 O（ Nlb M）其中 N＝ K MK 是类别数量M 是 每一类的平均大小．例如N＝2×106K ＝1000 M＝1000排序计算量可以降低一半．各个不同特 征分类之间还可以并行计算（见3∙3节）． （2） 特征分类下的去可弃．对整个语义单元库 去可弃时如果采用2∙3节的处理子库的去可弃算 法则数百万语义单元集合去可弃在一般非高性能 计算机上的处理时间过长．采用特征分类法后由于 各个不同特征分类集合中各自进行排序消去其计 算复杂性可大幅度降低．具体方法是：从 t ＝1开 始对各个不同特征的分类集合中的语义单元进行 代入和比较消去 t＝0及 t＝1中的可弃语义单元． 消去比较过程中不仅充分利用特征分类大幅度地 缩小比较的计算量而且充分利用“可能被消去的语 义单元的长度等于被代入的语义单元长度加所代 入的各个参量的语义单元长度减1”的这个特点将 搜索限制在一定长度的语义单元子集中从而进一 步大幅度降低计算量． （3） 特征分类下的的目标驱动法去可弃．在采 用特征分类的情况下还可以进一步采用以下“目标 驱动”方法．从语义单元参数个数 t＝1入手根据 参数在语义单元表示中位置通过左串、右串及左右 串与 t＝0中的同特征分类单元进行匹配寻找 t＝ 0中及部分 t＝1中的可弃语义单元不需要全部进 行代入．匹配方法可以采用类似子树剪枝法［5］．对 t＝2的处理与 t ＝1类似只是位置结构复杂一 些同时寻找的可弃语义单元不仅在 t＝1及部分 t＝2的单元中而且也可能在 t＝0的单元中．对 t＞2的单元处理类似．由于计算量依赖于同特征分 类下可弃语义单元的数量而不是搜索整个库中所 有的可能代入所以计算复杂性还可以进一步下降． 综上所述采用特征分类法和目标驱动法后其 计算复杂性已由原来的 O（ NN′V 4 ki）降低到小于 等于 O （ Nlb m ＋ ∑ 4 k＝1∑i Ukiα4m 4） ≈ O （ Nlb m ＋ Nα4m 4）＝ O（ Nα4m 4）＝ O（βN）其中 Uki是参数 ·702· 北 京 科 技 大 学 学 报 第30卷