目录用状态机和字典树统计单词从“能数”到“数得清楚”用状态机和字典树统计单词从“能数”到“数得清楚”学习代码count/count.c、count/count_every_word.c这个练习看起来只是统计文本单词数量但真正训练的是“状态机思维”。如果只是遇到字母就加一很快会出错因为一个单词包含多个字母连续字母不能重复计数。正确的想法是遍历每个字符时先判断自己当前处在什么状态再根据输入字符决定是否切换状态。在count.c里我把状态拆成三个#defineOUT0#defineDASH1#defineIN2核心逻辑是从OUT读到字母时说明一个新单词开始所以计数加一如果已经在IN状态再读到字母就不重复加。代码片段如下if(isalpha((unsignedchar)c)){if(statusOUT)words;statusIN;}elseif(c-statusIN){statusDASH;}elseif(c\nstatusDASH){statusIN;}else{statusOUT;}这里我觉得最有价值的是DASH状态。英文文本里可能出现word-\nword这种换行断词如果简单把横杠和换行都当成分隔符就会把一个词误判成两个词。新增DASH状态后程序能表达“我刚刚在单词中遇到了横杠下一步要看是不是换行”的中间态。这个中间态就是状态机比简单 if 判断更清晰的地方。在count_every_word.c中需求从统计总数升级到统计每个单词出现次数于是引入字典树typedefstructTrieNode_s{structTrieNode_s*nodes[26];intcounts;}TrieNode;每读到一个字母就沿着nodes[c - a]往下走单词结束时在当前节点counts。字典树的好处是前缀可以复用比如app和apple前三个节点共用查询和插入的复杂度主要取决于单词长度。我的体会是文本处理不能只盯着“字符”还要盯着“上下文”。状态机负责识别单词边界字典树负责保存统计结果一个解决解析问题一个解决存储问题。把这两个工具组合起来代码就从零散判断变成了有结构的程序。学习链接: https://github.com/0voice
