词频统计

Question

在预面试中，我面临这样的问题：

给定一个由单个空格分隔的单词组成的字符串，按单词在字符串中出现的次数降序打印单词。

例如，输入字符串“abb”将生成以下输出：

b : 2
a : 1

首先，我想说，输入字符串是由单字母单词还是由多字母单词组成并不那么清楚。如果是前者，事情可能会很简单。

这是我的想法：

int c[26] = {0};
char *pIn = strIn;

while (*pIn != 0 && *pIn != ' ')
{
    ++c[*pIn];
    ++pIn;
}

/* how to sort the array c[26] and remember the original index? */

我可以统计输入字符串中每个单字母单词的频率，并且可以对其进行排序（使用 QuickSort 或其他方式）。但是在计数数组排序后，如何获取与计数相关的单字母单词，以便稍后将它们成对打印出来？

如果输入字符串由多字母单词组成，我计划使用 map 来跟踪频率。但同样，如何对映射的键值对进行排序？

问题是用 C 或 C++ 编写的，欢迎提出任何建议。

谢谢！

Answer 1

我将使用 std::map 来存储单词及其计数。然后我会使用这样的东西来获取单词：

while(std::cin >> word) {
    // increment map's count for that word
}

最后，您只需要弄清楚如何按频率顺序打印它们，我将把它作为练习留给您。

Answer 2

您假设只需要 26 个选项，这绝对是错误的，因为您的雇主也希望允许使用多字符单词（甚至可能是数字？）。

这意味着您将需要一个可变长度的数组。我强烈建议使用矢量，或者更好的是使用地图。

要查找字符串中的字符序列，请查找当前位置（从 0 开始）和下一个空格的位置。然后就是这个词了。将当前位置设置为空格并再次执行。不断重复此操作，直到结束。

通过使用地图，您已经可以获得可用的字数/计数。

如果您申请的工作需要大学技能，我强烈建议通过添加某种哈希函数来优化地图。然而，从问题的难度来看，我认为情况并非如此。

Answer 3

以 C 语言为例：

我喜欢暴力、简单的算法，所以我会这样做：

1. 对输入字符串进行分词以给出未排序的单词数组。我实际上必须物理地移动每个单词（因为每个单词的长度都是可变的）；我认为我需要一个 char* 数组，我将使用它作为 qsort( ) 的参数。

2. qsort( ) （降序）该单词数组。 （在 qsort() 的 COMPAR 函数中，假设较大的单词是较小的单词，以便数组获得降序排序顺序。）

3.a.遍历现在已排序的数组，查找相同单词的子数组。子数组的结尾和下一个子数组的开头由我看到的第一个不相同的单词表示。
3.b.当我到达子数组的末尾（或排序数组的末尾）时，我知道（1）单词和（2）子数组中相同单词的数量。

编辑新步骤 4： 在另一个数组（称为 array2）中保存子数组中单词的 char* 以及子数组中相同单词的计数。

1. 当排序数组中不再有单词时，我就完成了。是时候打印了。

2. qsort( ) array2 按词频。

3. 遍历 array2，打印每个单词及其频率。

我受够了！我们去吃午饭吧。

Answer 4

在我之前的所有答案都没有给出真正的答案。

让我们思考一个可能的解决方案。

有一种或多或少的标准方法来计算容器中的东西。

我们可以使用关联容器，例如 std::map 或 std::unordered_map。在这里，我们将“键”（在本例中为单词）与计数和值（在本例中为特定单词的计数）相关联。

幸运的是，这些地图有一个非常好的索引operator[]。这将查找给定的键，如果找到，则返回对该值的引用。如果未找到，则它将使用该密钥创建一个新条目并返回对新条目的引用。因此，在这两种情况下，我们都会获得用于计数的值的引用。然后我们可以简单地写：

std::unordered_map<char,int> counter{};
counter[word]++;

这看起来非常直观。

完成此操作后，您就已经有了频率表。可以使用 std::map 按键（单词）排序，也可以不排序，但使用 std::unordered_map 可以更快地访问。

现在您想根据频率/计数进行排序。不幸的是，这对于地图来说是不可能的。

因此，我们需要使用第二个容器，例如 ```std::vector`````，然后我们可以对任何给定谓词进行 unsing std::sort 排序，或者，我们可以复制将值放入容器中，例如隐式对其元素进行排序的 std::multiset 。

为了获取 std::string 的单词，我们只需使用 std::istringstream 和标准提取运算符 >>。没什么大不了的。

因为要为 std 容器编写所有这些长名称，所以我们使用 using 关键字创建别名。

毕竟，我们现在编写超紧凑的代码，只需几行代码即可完成任务：

#include <iostream>
#include <string>
#include <sstream>
#include <utility>
#include <set>
#include <unordered_map>
#include <type_traits>
#include <iomanip>

// ------------------------------------------------------------
// Create aliases. Save typing work and make code more readable
using Pair = std::pair<std::string, unsigned int>;

// Standard approach for counter
using Counter = std::unordered_map<Pair::first_type, Pair::second_type>;

// Sorted values will be stored in a multiset
struct Comp { bool operator ()(const Pair& p1, const Pair& p2) const { return (p1.second == p2.second) ? p1.first<p2.first : p1.second>p2.second; } };
using Rank = std::multiset<Pair, Comp>;
// ------------------------------------------------------------

std::istringstream text{ " 4444 55555 1 22 4444 333 55555 333 333  4444  4444 55555  55555 55555 22 "};

int main() {

    Counter counter;
    
    // Count
    for (std::string word{}; text >> word; counter[word]++);

    // Sort
    Rank rank(counter.begin(), counter.end());

    // Output
    for (const auto& [word, count] : rank) std::cout << std::setw(15) << word << " : " << count << '\n';
}