使用有限状态机原理实现英文分词

提出问题

使用Python开发一个英文句子分词程序,把一段英文句子切分为每一个单词。不能导入任何官方的或者第三方的库,也不能使用字符串的split()方法。

代码是如何一步一步恶化的

单词与空格

对于只有单词和空格,不含其他符号的英语句子,可以使用空格来切分单词。于是对于句子I am kingname, 一个字符一个字符的进行遍历。首先遍历到I,发现它是一个字母,于是把它存到一个变量word中,然后遍历到空格,于是把变量word的值添加到变量word_list中,再把word清空。接下来遍历到字母a,又把a放到变量word中。再遍历到m,发现它还是一个字母,于是把字母m拼接到变量word的末尾。此时变量word的值为am。再遍历到第二个空格,于是把word的值添加到word_list中,清空word

最后,由于第三个单词kingname的末尾没有空格,所以需要手动把它添加到列表word_list中。

完整的代码如下:

 def split(target): 
     if not target: 
         return [] 
     word_list = [] 
     word = '' 
     for letter in target: 
         if letter == ' ': 
             word_list.append(word) 
             word = '' 
         else: 
             word += letter 
     return word_list 


 if __name__ == '__main__': 
     sentence = 'I am kingname' 
     result_word_list = split(sentence) 
     print(result_word_list)

运行效果如下图所示。

单词空格与逗号句号

现在不仅仅只有单词和空格,还有逗号和句号。有这样一个句子:”I am kingname,you should remember me.”如果使用上一小节的程序,那么代码就会出现问题,如下图所示。

其中,”kingname,you”应该是两个单词,但是在这里变成了一个单词。所以现在不仅遇到空格要进行切分,遇到逗号句号还需要进行切分。那么对代码做一些修改,变成如下代码:

 def split(target): 
     if not target: 
         return [] 
     word_list = [] 
     word = '' 
     for letter in target: 
         if letter in [' ', ',', '.']: 
             word_list.append(word) 
             word = '' 
         else: 
             word += letter 
     if word: 
         word_list.append(word) 
     return word_list 


 if __name__ == '__main__': 
     sentence = 'I am kingname,you should remember me.' 
     result_word_list = split(sentence) 
     print(result_word_list)

现在运行起来看上去没有问题了,如下图所示。

然而,有些人写英文的时候喜欢在标点符号右侧加一个空格,例如:”I am kingname, you should remember me.”这样小小的一修改,上面的代码又出问题了,如下图所示。

分词出来的结果里面凭空多出来一个空字符串。为了解决这个问题,再加一层判断,只有发现word不为空字符串的时候才把它加入到word_list中,代码继续修改:

 def split(target): 
     if not target: 
         return [] 
     word_list = [] 
     word = '' 
     for letter in target: 
         if letter in [' ', ',', '.']: 
             if not word: 
                 continue 
             word_list.append(word) 
             word = '' 
         else: 
             word += letter 
     if word: 
         word_list.append(word) 
     return word_list 


 if __name__ == '__main__': 
     sentence = 'I am kingname, you should remember me.' 
     result_word_list = split(sentence) 
     print(result_word_list)

代码看起来又可以正常工作了。如下图所示。

单词空格与各种标点符号

标点符号可不仅仅只有逗号句号。现在又出现了冒号分号双引号感叹号问号等等杂七杂八的符号。英文句子变为:”I am kingname, you should say: “Kingname Oba” to me, will you?”

使用上面的代码,发现运行起来又出问题了。如下图所示。

为了能覆盖到所有的标点符号,现在修改一下逻辑。原来是“遇到空格/逗号/句号”就把word放到word_list中。现在要改为“如果当前字符不是字母,就把word放到word_list中”。于是代码进一步做修改:

 constant = 'abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ' 


 def split(target): 
     if not target: 
         return [] 
     word_list = [] 
     word = '' 
     for letter in target: 
         if letter not in constant: 
             if not word: 
                 continue 
             word_list.append(word) 
             word = '' 
         else: 
             word += letter 
     if word: 
         word_list.append(word) 
     return word_list 


 if __name__ == '__main__': 
     sentence = 'I am kingname, you should say: "Kingname Oba" to me, will you?' 
     result_word_list = split(sentence) 
     print(result_word_list)

代码修改以后又可以正常工作了,其运行效果如下图所示:

奇奇怪怪的单引号

如果双引号包含的句子里面还需要用到引号,那么就需要在内部使用单引号。例如有这样一个句子:“I am kingname, you should say: “Kingname Oba, I always remember your motto: ‘kingname is genius’” to me, will you?”

使用前面的代码,运行起来似乎没有问题,如下图所示。

但是,单引号还有其他用途——有人喜欢把两个单词合并成一个单词,例如:

  • “do not” == “don’t”
  • “is not” == “isn’t”
  • “I will” == “I’ll”
  • “I have” == “I’ve”

在这种情况下,就应该把单引号连接的两部分看作是一个单词,不应该把它们切开。

如果句子变成:I'm kingname, you should say: "Kingname Oba, I always remember your motto: 'kingname's genius'" to me, won't you?继续使用上面的代码,就发现返回的单词列表又不对了。如下图所示。

要解决这个问题,就需要确定单引号具体是做普通的引号来使用,还是放在缩写里使用。

作为普通单引号使用的时候,如果是前单引号,那么它的左边必定不是字母,如果作为后单引号,那么它的右边必定不是字母。而缩写里面的单引号,它左右两侧必定都是字母。并且需要注意,如果是句子里面第一个符号就是单引号,那么此时它左边没有字符;如果句子里面最后一个符号是单引号,那么它右边没有字符,此时如果使用下标来查找,就需要当心下标越界。

对代码进一步修改:

 constant = 'abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ' 


 def split(target): 
     if not target: 
         return [] 
     word_list = [] 
     word = '' 
     for index, letter in enumerate(target): 
         if letter not in constant and letter != "'": 
             if not word: 
                 continue 
             word_list.append(word) 
             word = '' 
         elif letter == "'": 
             if 0 < index < len(target) - 1 \ 
                     and target[index - 1] in constant \ 
                     and target[index + 1] in constant: 
                 word += letter 
         else: 
             word += letter 
     if word: 
         word_list.append(word) 
     return word_list 


 if __name__ == '__main__': 
     sentence = '''I'm kingname, you should say: "Kingname Oba, 
                   I always remember your motto: 'kingname's genius'" to me, won't you?''' 
     result_word_list = split(sentence) 
     for word in result_word_list: 
         print(word)

现在代码又可以成功运行了,如下图所示。

但是请细看代码,现在已经混乱到难以阅读难以理解了。如果再增加一个连字符又怎么改?如果单词内部出现了两个单引号怎么改?这种为了增加一个功能,要把很多不相干代码也进行修改的编码方式,相信可以击中很多初学者甚至是不少自称为软件工程师的人。

状态转义图

根据分词逻辑,遇到各种符号应该怎么处理,画一个分词的状态转移图出来。

从这个图上可以看出来,其实程序只需要知道当前是什么状态,以及遇到什么字符需要转移到什么状态就可以了。没有必要知道自己是从哪个状态转移过来的,也没有必要知道和自己不相干的其他状态。

举一个例子:I'm kingname, you should say: "Kingname Oba, I always remember your motto: 'kingname's genius'" to me, won't you?这个句子中,should这个单词就是处于“单词状态”。它不在单引号内部,它也不是一个缩写。当我们对句子每个字符进行遍历的时候,遍历到“should”的“s”时进入“单词状态”,在单词状态,只需要关心接下来过来的下一个字符是什么,如果是字母,那依然是单词状态,把字母直接拼接上来即可。如果是单引号,那么进入“单引号在单词中状态”。至于“单引号在单词中状态”有什么逻辑,单词状态的代码根本不需要知道。这就像是接力赛,我把棒交给下一个人,我的任务就做完了,下一个人是跑到终点还是爬到终点,都和我没有关系。

这就是有限状态机FSM的原理。

使用状态机

根据这个原理,使用状态和转移关系来改写代码,就可以让代码的逻辑变得非常清晰。改进以后的代码如下:

 class Spliter(object):
     def __init__(self):
         self.constant = 'abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ'
         self.state = '初始状态'
         self.word = ''
         self.word_list = []
         self.state_dict = {'初始状态': self.parse_init,                            '单词状态': self.parse_word,                            '单引号在单词中状态': self.parse_contraction}     def parse_init(self, letter):
         if letter in self.constant:
             self.state = '单词状态'
             self.word += letter     def parse_word(self, letter):
         if letter in self.constant:
             self.word += letter         elif letter == "'":
             self.state = '单引号在单词中状态'
             self.word += "'"
         else:
             self.word_list.append(self.word)
             self.state = '初始状态'
             self.word = ''

     def parse_contraction(self, letter):
         if letter in self.constant:
             self.word += letter
             self.state = '单词状态'
         else:
             self.word_list.append(self.word[:-1])
             self.word = ''
             self.state = '初始状态'

     def split(self, target):
         for letter in target:
             self.state_dict[self.state](letter)         return self.word_listif __name__ == '__main__':
    spliter = Spliter()
    sentence = '''I'm kingname, you should say: "Kingname Oba, 
                      I always remember your motto: 'kingname's genius'" to me, won't you?'''
    print(spliter.split(sentence))

代码运行效果如下图所示。

需要注意的是,图中的代码只是使用了有限状态机的原理,而并非一个有限状态机。

原文发布于微信公众号 - 未闻Code(itskingname)

原文发表时间:2017-12-10

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏田云专栏

virtualdom diff算法实现分析

这两个月接触下vue ,花了两天时间了解了下vue的virtualdom实现,记录下学习心得。

37660
来自专栏软件开发 -- 分享 互助 成长

string.length()与-1比较为什么会出现匪夷所思的结果

今天调试程序发现了个匪夷所思的事情,-1与string.length()比较永远是-1大,看下面代码 #include<iostream> #include<s...

25380
来自专栏高爽的专栏

HashMap深度解析(二)

上一篇比较深入的分析了HashMap在put元素时的整体过程,Java Collections Framework中实际操作的都是数组或者链表,而我们通常...

23800
来自专栏令仔很忙

新手学HighCharts(二)----对比柱状图的动态加载

上一篇文章 新手学HighCharts(一)—-基本使用 中介绍了highCharts的基本使用,今天给大家介绍对比柱状图的使用,贴张图先:

10410
来自专栏nnngu

Hibernate的继承映射

对象模型示例: ? 继承映射的实现方式有以下三种: (一)每棵类继承树一张表 (二)每个类一张表 (三)每个子类一张表 (一)每棵类继承树一张表 关系模型如下:...

28340
来自专栏窗户

Scheme来实现八皇后问题(2)

  上一章讲了用1~n的排序来表示n皇后的解,然后通过枚举1~n所有的排列、判定谓词过滤所有排列得到最终的所有解。

15530
来自专栏猿人谷

习题3.13

题目(习题3.13):读一组整数到vector对象,计算并输出每对相邻元素的和。如果读入元素个数为奇数,则提示用户最后一个元素没有求和,并输出其值。然后修改程序...

21570
来自专栏C语言C++游戏编程

C语言的这个小知识点,竟然连开发多年的老司机都了解的不完全

说明:这是学C语言最基本的知识点,简单的使用不难, 但是里面的一些细节和原理就值得我们好好推敲了,想要学好C语言或者编程语言的小伙伴,真的可以好好看看哦~

9710
来自专栏Java爬坑系列

【Java入门提高篇】Day22 Java容器类详解(五)HashMap源码分析(上)

准备了很长时间,终于理清了思路,鼓起勇气,开始介绍本篇的主角——HashMap。说实话,这家伙能说的内容太多了,要是像前面ArrayList那样翻译一下源码,稍...

25950
来自专栏java一日一条

Python开发的10个小贴士

下面是十个Python中很有用的贴士和技巧。其中一些是初学这门语言常常会犯的错误。

8720

扫码关注云+社区

领取腾讯云代金券