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

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