0192. Word Frequency¶
题目信息¶
- 题号:
统计词频
- 难度:
Medium
- 主题:
Shell、文本流、分组计数、数值排序
- 原题:
- 重点:
先把任意空白分隔文本规范为每词一行,再排序聚组、计数并调整输出字段
题目重述¶
编写 Bash 脚本读取当前目录中的 words.txt。文件包含若干单词,单词之间由一个或多个
空白字符分隔。
统计每个不同单词在整个文件中的出现次数,每行输出 word count,并按次数从高到低
排列。相同次数之间没有指定顺序。
自建示例¶
words.txt:
red blue red
green blue red
blue
一种合法输出:
blue 3
red 3
green 1
连续空格和换行都只是分隔符,计数范围跨越全部行。
Bash 实现¶
#!/usr/bin/env bash
export LC_ALL=C
tr -s '[:space:]' '\n' < words.txt |
sort |
uniq -c |
sort -k1,1nr -k2,2 |
awk '{print $2, $1}'
题解¶
原始输入的记录粒度不对¶
Shell 工具通常按行处理,但题目的逻辑记录是“一个单词”。如果直接对文件行排序或去重,
"red blue" 会被当成一个整体,既不能跨行统计,也不能区分同一行中的多个词。
可以先收集所有不同单词,再为每个单词重新扫描文件计数;这样同一文本会被读取多次,工作 量随不同单词数增长。主脚本改为一次管道:每一阶段只解决一种数据形态转换,并把结果流给 下一阶段。
第一阶段:每个单词变成一行¶
tr -s '[:space:]' '\n' 把空格、制表符、换行等空白统一映射为换行,-s 再把连续
换行压成一个。于是无论原文件如何换行或使用多个空格,输出都变成:
red
blue
red
green
blue
red
blue
输入重定向 < words.txt 只把文件内容送入标准输入,不把文件名本身当作普通参数或
输出。空文件及只有空白的文件不会产生单词记录。
题目按空白定义单词,所以标点和大小写不会被额外规范化:Word 与 word 是两个
不同词,word, 中的逗号也属于词本身。脚本不擅自加入题目之外的清洗规则。
第二阶段:让相同记录相邻¶
uniq -c 只能合并 相邻 的相同行,不能在整条流中寻找分散重复项。若直接对上一步
结果执行 uniq,三个 blue 被其他词隔开,无法合并。
第一个 sort 按单词排列,使相同词形成连续组;uniq -c 随后把每组压缩成一行,
并把计数放在前面:
3 blue
1 green
3 red
这两个命令共同完成“按单词分组并统计”,不能删除或交换顺序。
第三阶段:按数字而不是文本排序¶
uniq -c 的当前字段顺序是 count word。sort -k1,1nr 只使用第一字段,n 表示
数值比较,r 表示降序。若遗漏 n,文本排序会把 10 当作排在 2 前后的字典文本,
无法保证频次顺序。
-k2,2 只作为次数相同时的单词升序次关键字,使输出稳定;题目不要求该顺序,但它不
违反主排序条件。LC_ALL=C 让字符排序规则不随运行环境区域设置变化,也不会改变计数。
最后,awk '{print $2, $1}' 把字段从 count word 调整成题目要求的 word count。
awk 的默认输出字段分隔符是一个空格,正好符合格式。
完整状态走读¶
示例经过各阶段的核心状态为:
空白规范化:red, blue, red, green, blue, red, blue(每项独占一行)
单词排序: blue, blue, blue, green, red, red, red
聚组计数: 3 blue;1 green;3 red
数值降序: 3 blue;3 red;1 green
字段交换: blue 3;red 3;green 1
每个阶段的输入不变量正是上一阶段的输出保证,因此无需在 awk 中再次解析原始文本或
维护复杂状态。
复杂度与方案选择¶
设共有 W 个单词。空白规范化和计数扫描为线性工作;主成本是单词排序,通常为
O(W log W),外部 sort 可使用临时文件处理超过内存的数据。也可用单个 awk
关联数组在线计数,再只排序 U 个不同单词;那会把全部频次状态放入内存。主脚本采用
标准 sort + uniq 流水线,阶段语义清楚,并利用 Shell 工具的外部排序能力。