如何使用状态机统计一个文件中单词的数量

如何使用状态机统计一个文本中单词的数量

引言

在大一学习 C 语言的时候，依稀记得在课本上有一个关于统计一段文本中单词数量的一个程序，此程序的思路应该是读取每一个字符，通过设置一个标志 (FLAG) 来标记从单词到空格或从空格到单词，从而记录一个单词何时开始，何时结束。当时费了很长的时间才搞清楚程序的运行逻辑，因此印象深刻。在本篇文章中，我们将使用状态机的思想来解决这个问题，虽然它们本质上都是统计从空格到单词的次数，但使用状态机可以一目了然。

分析

首先让我们回到问题本身，如何统计文本中单词的数量呢？最容易想到的一个思路，就是遍历一个文本中的每一个字母和分隔符，每当从一个分隔符到一个字母时，我们就认为一个新的单词出现了，从而使计数器加一，但是这样的算法用程序来表示并不容易（如使用一个 FLAG ），如果稍有不慎，就会出错。此时，我们可以使用状态机的思想。

在状态机的思想下，我们将程序的运行分为若干个状态，当满足一定的条件时，我们就从一个状态到另一个状态，不论是在某一个状态下，还是在状态之间转换的过程中，我们都可以进行适当的操作，从而实现我们的目的。

思路

那么我们如何使用状态机来解决统计单词的问题呢？通过上述关于解决统计文件中单词数量的核心思路以及状态机的思想，我们可以使程序遍历一个文本中的每一个字符，将程序在遍历的过程中分为两个状态：

In

和

OUT

，分别表示在单词中，和不在单词中两种状态，如下图所示：

在初始状态下，我们默认为

OUT

状态，当程序读到第一个字母时，我们将程序转换到

In

状态，在此过程中，我们便可以使计数器加一，此后，当程序读到另一个非字母的字符（空格、换行、标点服符号等）时，我们再将程序转换到

OUT

的状态，如此往复，直到程序读取最后一个字符。

程序

实现程序如下：

#include<stdio.h>#defineIN1// 在单词中#defineOUT0// 在单词外intcount(char*filename){int word_nums =0;// 单词数量（计数器）int state = OUT;// 初始状态

    FILE *fp =fopen(filename,"r");// 以只读的方式打开文件if(fp ==NULL)return-1;char c;while((c =fgetc(fp))!=EOF){// 读取文件，一次一个字符if(!((c >='a'&& c <='z')||(c >='A'&& c <='Z'))){

            state = OUT;// 如果为分隔符，标志状态为 OUT}elseif(OUT == state){

            state = IN;// 如果为字母，且之前的状态为 OUT，则标志为 IN++word_nums;// 在每一次转换过程中，使计数器加一}}return word_nums;// 单词数量（计数器）}intmain(int argc,char*argv[]){if(argc <2)// 如果未提供文本文件return-1;printf("word: %d\n",count(argv[1]));// 打印单词数量return0;}

总结

我认为，状态机的思想非常简单，就是将程序的运行分为若干个状态，在每个状态中或状态之间的转换过程中适当操作，从而达到我们的目的，例如，本例中就是在从状态

OUT

到状态

IN

的转换过程中计数，从而统计单词数量。

在使用状态机的过程中，我们需要明确：

• 状态数量
• 状态含义
• 初始状态
• 状态条件

在编写 C 语言代码时，使用具有一定意义的字面量时，最佳实践是使用宏定义，这样可以帮助我们明确字面量的含义，以免使用时出现不明所以的情况。

思考

此程序只能完成最基本的要求，但在某些情况下，可能会出现 BUG，例如文本中可能存在的一种情况是：一个较长的单词在行末时，为了防止理解错误，往往会在单词中使用连字符

-

，然后换行，对于这种情况，上述程序必然会出现错误，我么该如何解决呢？此外，在某些时候，可能会有这样的需求：统计文本中每个单词出现的数量，我们该如何解决这个问题呢？

后记

推荐一个零声学院免费公开课程，个人觉得老师讲得不错，分享给大家：[Linux，Nginx，ZeroMQ，MySQL，Redis，fastdfs，MongoDB，ZK，流媒体，CDN，P2P，K8S，Docker，TCP/IP，协程，DPDK等技术内容，点击立即学习:

此文章主要用来作为课程学习过程中的总结，大家如果有什么问题也可以在评论区留言，我会尽力帮大家解决问题