Beautiful Data-统计语言模型的应用三:分词8

  对于一个包含n个字符的单词来说,利用语言模型进行分词的前提是首先枚举出所有的候选切分,而segment函数中:
  candidates = ( [first] + segment( rem ) for first, rem in splits( text ) )
的作用正是如此,它包含了递归调用,因此能枚举出所有的候选切分。那么,这个函数的时间复杂度是多少呢?一个包含n个字符的字符串有2^(n-1)种不同的分词方案(在字符之间有n-1个位置,每一个位置既可以作为单词边界也可以不作为边界),因此segment函数的时间复杂度为O(2^n),难怪之前的测试当字符串比较长时就跑不出结果了!
  那么,我们应该如何来改进这个递归的分词程序呢?如果你了解一些算法知识,大概会想到动态规划算法:

  动态规划是一种在数学和计算机科学中使用的,用于求解包含重叠子问题的最优化问题的方法。其基本思想是,将原问题分解为相似的子问题,在求解的过程中通过子问题的解求出原问题的解。
  动态规划在查找有很多重叠子问题的情况的最优解时有效。它将问题重新组合成子问题。为了避免多次解决这些子问题,它们的结果都逐渐被计算并被保存,从简单的问题直到整个问题都被解决。因此,动态规划保存递归时的结果,因而不会在解决同样的问题时花费时间。(注:引自维基百科)

  在segment.py中,segment函数的确是将问题划归成[first] + segment( rem )的子问题进行处理了,因此利用动态规划算法优化来改进segment函数应该成为首选了!不过, Peter Norvig大牛利用了Decorator。事实上,我也是python新手,当我读Beautiful Data中的这段源程序时,Decorator是最让我丈二和尚摸不着头脑的,所以找了一些关于Python Decorator的资料来学习,觉得对于本例,最需要注意的两点是:
  第一,在Python中,一个函数可以将另一个函数作为参数,对另一个函数进行“包装“以加入新的相关操作,并最终返回一个新的函数。这话说得不太清楚,我们来看一个例子,例子来源于”The Quick Python Book, 2nd”中9.8节的例子,基于Python3.0,这里稍作调整:
  首先定义一个myfunction:
  >>> def myfunction( parameter ):
  …   print( parameter )
  …
  测试myfunciton:
  >>> myfunction( “Hello, Python Decorator!” )
  Hello, Python Decorator!
  然后定义一个decorate:
  >>> def decorate( func ):
  …   print ( “in decorate function, decroating”, func.__name__ )
  …   def wrapper_func( *args ):
  …     print( “Executing”, func.__name__ )
  …     return func( *args )
  …   return wrapper_func
  用decorate“包装”myfunction:
  >>> myfunction = decorate( myfunction )
  (‘in decorate function, decroating’, ‘myfunction’)
  再执行:
  >>> myfunction( “Hello, Python Decorator!” )
  (‘Executing’, ‘myfunction’)
  Hello, Python Decorator!
  看看输出结果,myfunction的确已经被“包装”了,事实上这一过程中没有什么新东西,不过就是重新返回了一个 wrapper_func函数给myfunction了,其实Python Decorator做得是同一样的事,只不过它的code更简洁和易读,所以被称之为Syntax sugar(语法糖),关于为何名为Syntax sugar, Bruce Eckel的“Python Decorators入门“介绍中译者给了如下的解释:

  意指那些没有给计算机语言添加新功能,而只是对人类来说更“甜蜜“的语法。语法糖往往给程序员提供了更实用的编码方式,有益于更好的编码风格,更易读。不过其并没有给语言添加什么新东西。

  解释的真是贴切,我们继续这个例子,为了区别对待myfunction,我们重新定义一个ourfunciton,不过在定义ourfunction之前先加上这块儿语法糖“@”,表明其是Python Decorator程序:
  >>> @decorate
  … def ourfunction( parameter ):
  …   print( parameter )
  …
  (‘in decorate function, decroating’, ‘ourfunction’)
  以上的输出以表明ourfunction被decorate”包装“,继续测试ourfunction,
  >>> ourfunction( “Hello, Python Decorator!” )
  (‘Executing’, ‘ourfunction’)
  Hello, Python Decorator!
  效果确实与上同,只不过这一次的代码要简洁很多。

未完待续…

注:原创文章,转载请注明出处“我爱自然语言处理”:www.52nlp.cn

本文链接地址:http://www.52nlp.cn/beautiful-data-统计语言模型的应用三分词8

此条目发表在中文分词, 语言模型分类目录,贴了, , , , , , , , , 标签。将固定链接加入收藏夹。

Beautiful Data-统计语言模型的应用三:分词8》有 2 条评论

  1. liu说:

    Beautiful Data-统计语言模型的应用三:分词8

    未完待续!

    请问作者还续吗?一口气看到第八节,后面没有了,有点扫兴

    [回复]

    52nlp 回复:

    可以直接看原版了,比这里精彩!呵呵!

    [回复]

发表评论

电子邮件地址不会被公开。 必填项已用*标注