在文件中找到 n 个最常用的词

Question

我想在文本文件中找到 10 个最常见的单词。首先，解决方案应该针对击键进行优化（换句话说 - 我的时间）。其次，对于业绩。以下是我目前获得前 10 名的条件：

cat test.txt | tr -c '[:alnum:]' '[\n*]' | uniq -c | sort -nr | head  -10
  6 k
  2 g
  2 e
  2 a
  1 r
  1 k22
  1 k
  1 f
  1 eeeeeeeeeeeeeeeeeeeee
  1 d

我可以制作一个 java、python 等程序，我将 (word, numberOfOccurences) 存储在字典中并对值进行排序，或者我可以使用 MapReduce，但我针对击键进行了优化。

是否存在误报？有没有更好的办法？

Answer 1

这几乎是查找“N 个最常见事物”的最常用方法，除了您缺少一个sort，并且您得到了一个无偿的cat：

tr -c '[:alnum:]' '[\n*]' < test.txt | sort | uniq -c | sort -nr | head  -10

如果你不在sort之前输入 auniq -c 你可能会得到很多错误的单例词。 uniq只做独特的线条，而不是整体的独特性。

编辑：我忘记了一个技巧，“停用词”。如果您正在查看英文文本（抱歉，这里是北美单语），诸如“of”、“and”、“the”之类的词几乎总是排在前两三位。您可能想消除它们。GNU Groff 发行版中有一个名为的文件eign，其中包含一个相当不错的停用词列表。我的 Arch 发行版有/usr/share/groff/current/eign，但我想我也见过/usr/share/dict/eign或/usr/dict/eign在旧的 Unix 中。

你可以像这样使用停用词：

tr -c '[:alnum:]' '[\n*]' < test.txt |
fgrep -v -w -f /usr/share/groff/current/eign |
sort | uniq -c | sort -nr | head  -10

我的猜测是，大多数人类语言都需要从有意义的词频计数中删除类似的“停用词”，但我不知道在哪里建议获取其他语言的停用词列表。

编辑： fgrep应该使用-w启用全字匹配的命令。这避免了仅包含短暂停止工作的单词的误报，例如“a”或“i”。

Answer 2

这对 utf-8 更有效：

$ sed -e 's/\s/\n/g' < test.txt | sort | uniq -c | sort -nr | head  -10

Answer 3

让我们使用AWK！

此函数按降序列出在提供的文件中出现的每个单词的频率：

function wordfrequency() {
  awk '
     BEGIN { FS="[^a-zA-Z]+" } {
         for (i=1; i<=NF; i++) {
             word = tolower($i)
             words[word]++
         }
     }
     END {
         for (w in words)
              printf("%3d %s\n", words[w], w)
     } ' | sort -rn
}

你可以像这样在你的文件上调用它：

$ cat your_file.txt | wordfrequency

以及前 10 个词：

$ cat your_file.txt | wordfrequency | head -10

资料来源：AWK-ward Ruby

Answer 4

这是一个经典问题，在 1986 年引起了一些共鸣，当时Donald Knuth在一个 8 页长的程序中使用哈希尝试实现了一个快速解决方案，以说明他的文学编程技术，而 Unix 管道教父 Doug McIlroy 则以一句台词，虽然没那么快，但完成了工作：

\n\n

tr -cs A-Za-z \'\\n\' | tr A-Z a-z | sort | uniq -c | sort -rn | sed 10q\n

\n\n

当然，McIlroy 的解决方案的时间复杂度为 O(N log N)，其中 N 是单词总数。有更快的解决方案。例如：

\n\n

这是一个 C++ 实现，其上限时间复杂度为 O((N + k) log k)，通常 \xe2\x80\x93 几乎是线性的。

\n\n

下面是一个使用哈希字典和堆的快速 Python 实现，时间复杂度为 O(N + k log Q)，其中 Q 是多个唯一单词：

\n\n

import collections, re, sys\n\nfilename = sys.argv[1]\nk = int(sys.argv[2]) if len(sys.argv)>2 else 10\n\ntext = open(filename).read()\ncounts = collections.Counter(re.findall(\'[a-z]+\', text.lower()))\nfor i, w in counts.most_common(k):\n    print(i, w)\n

\n\n

这是 Anders Kaseorg 提出的一个非常快速的Rust 解决方案。

\n\n

CPU时间比较（以秒为单位）：

\n\n

                                     bible32       bible256\nRust (prefix tree)                   0.632         5.284\nC++ (prefix tree + heap)             4.838         38.587\nPython (Counter)                     9.851         100.487\nSheharyar (AWK + sort)               30.071        251.301\nMcIlroy (tr + sort + uniq)           60.251        690.906\n

\n\n

笔记：

\n\n

\n
• bible32 是 Bible 与自身连接 32 次 (135 MB)，bible256 \xe2\x80\x93 分别连接 256 次 (1.1 GB)。
\n
• Python 脚本的非线性减慢纯粹是由于它完全在内存中处理文件，因此对于大文件，开销会变得更大。
\n
• 如果有一个 Unix 工具可以构建一个堆并从堆顶部选取 n 个元素，那么 AWK 解决方案可以实现接近线性的时间复杂度，而目前它是 O(N + Q log Q)。
\n

\n