0192. Word Frequency ==================== 题目信息 -------- :题号: 0192. 统计词频 :难度: Medium :主题: Shell、文本流、分组计数、数值排序 :原题: `LeetCode 0192 `_ :重点: 先把任意空白分隔文本规范为每词一行,再排序聚组、计数并调整输出字段 题目重述 -------- 编写 Bash 脚本读取当前目录中的 ``words.txt``。文件包含若干单词,单词之间由一个或多个 空白字符分隔。 统计每个不同单词在整个文件中的出现次数,每行输出 ``word count``,并按次数从高到低 排列。相同次数之间没有指定顺序。 自建示例 -------- .. code-block:: text words.txt: red blue red green blue red blue 一种合法输出: blue 3 red 3 green 1 连续空格和换行都只是分隔符,计数范围跨越全部行。 Bash 实现 --------- .. code-block:: 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`` 再把连续 换行压成一个。于是无论原文件如何换行或使用多个空格,输出都变成: .. code-block:: text red blue red green blue red blue 输入重定向 ``< words.txt`` 只把文件内容送入标准输入,不把文件名本身当作普通参数或 输出。空文件及只有空白的文件不会产生单词记录。 题目按空白定义单词,所以标点和大小写不会被额外规范化:``Word`` 与 ``word`` 是两个 不同词,``word,`` 中的逗号也属于词本身。脚本不擅自加入题目之外的清洗规则。 第二阶段:让相同记录相邻 ~~~~~~~~~~~~~~~~~~~~~~~~~~ ``uniq -c`` 只能合并 **相邻** 的相同行,不能在整条流中寻找分散重复项。若直接对上一步 结果执行 ``uniq``,三个 ``blue`` 被其他词隔开,无法合并。 第一个 ``sort`` 按单词排列,使相同词形成连续组;``uniq -c`` 随后把每组压缩成一行, 并把计数放在前面: .. code-block:: text 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`` 的默认输出字段分隔符是一个空格,正好符合格式。 完整状态走读 ~~~~~~~~~~~~ 示例经过各阶段的核心状态为: .. code-block:: text 空白规范化: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 工具的外部排序能力。