Skip to content

Latest commit

 

History

History
153 lines (112 loc) · 5.55 KB

chapter2-11-chinese.md

File metadata and controls

153 lines (112 loc) · 5.55 KB
Raw

实现词频计数器——std::map

std::map在收集和统计数据方面非常有用，通过建立键值关系，将可修改的对象映射到对应键上，可以很容易的实现一个词频计数器。

How to do it...

本节中，我们将从标准输入中获取用户的输入，或是从记录一部小说的文本文件。我们会去标记输入单词，并统计一共有多少个单词。

  1. 包含必要的头文件。

    #include <iostream>
#include <map>
#include <vector>
#include <algorithm>
#include <iomanip>

  2. 声明所使用的命名空间。

    using namespace std;

  3. 我们将使用一个辅助函数，对输入中的符号进行处理。

    string filter_punctuation(const string &s)
{
    const char *forbidden {".,:; "};
    const auto idx_start (s.find_first_not_of(forbidden));
    const auto idx_end (s.find_last_not_of(forbidden));
    return s.substr(idx_start, idx_end - idx_start + 1);
}

  4. 现在，我们来实现真正要工作的部分。使用map表对输入的每个单词进行统计。另外，使用一个变量来保存目前为止看到的最长单词的长度。程序的最后，我们将打印这个map表。

    int main()
{
    map<string, size_t> words;
    int max_word_len {0};

  5. 将标准输入导入std::string变量中，标准输入由空格隔开。通过如下方法获取输入单词。

        string s;
    while (cin >> s) {

  6. 我们获得的单词可能包含标点符号，因为这些符号可能紧跟在单词后面。使用辅助函数将标点符号去除。

    		auto filtered (filter_punctuation(s));

  7. 如果当前处理的单词是目前处理最长的单词，我们会更新max_word_len变量。

    		max_word_len = max<int>(max_word_len, filtered.length());

  8. 然后，我们将增加该词在words map中的频率。如果是首次处理该单词，那么将会隐式创建一个键值对，然后插入map，之后再进行自加操作。

        	++words[filtered];
    }

  9. 当循环结束时，words map会保存所有输入单词的频率。map中单词作为键，并且键以字母序排列。我们想要以频率多少进行排序，词频最高的排第一位。为了达到这样的效果，首先实现一个vector，将所有键值对放入这个vector中。

        vector<pair<string, size_t>> word_counts;
    word_counts.reserve(words.size());
    move(begin(words), end(words), back_inserter(word_counts));

  10. 然后，vector中将将具有words map中的所有元素。然后，我们来进行排序，把词频最高的单词排在最开始，最低的放在最后。

    sort(begin(word_counts), end(word_counts),
        [](const auto &a, const auto &b) {
        return a.second > b.second;
        });

  1. 现在所有元素如我们想要的顺序排列，之后将这些数据打印在用户的终端上。使用std::setw流控制器，可以格式化输出相应的内容。

        cout << "# " << setw(max_word_len) << "<WORD>" << " #<COUNT>\n";
    for (const auto & [word, count] : word_counts) {
        cout << setw(max_word_len + 2) << word << " #"
        	 << count << '\n';
    }
}

  2. 编译后运行，我们就会得到一个词频表：

    $ cat lorem_ipsum.txt | ./word_frequency_counter
# <WORD> #<COUNT>
et #574
dolor #302
sed #273
diam #273
sit #259
ipsum #259
...

How it works...

本节中，我们使用std::map实例进行单词统计，然后将map中的所有元素放入vector中，然后进行排序，再打印输出。为什么要这么做？

先看一个例子。当我们要从a a b c b b b d c c字符串中统计词频时，我们的map内容如下：

a -> 2
b -> 4
c -> 3
d -> 1

不过，这是未排序的，这不是我们想要给用户展示的排序。我们的程序要首先输出b的频率，因为b的频率最高。然后是c，a，d。不幸的是，我们无法要求map使用键所对应的值进行排序。

这就需要vector帮忙了，将map中的键值对放入vector中。这个方法明确的将这些元素从map中删除了。

vector<pair<string, size_t>> word_counts;

然后，我们使用std::move函数将词-频对应关系填充整个vector。这样的好处是让单词不会重复，不过这样会将元素从map中完全删除。使用move方法，减少了很多不必要的拷贝。

move(begin(words), end(words), back_inserter(word_counts));

Note

一些STL的实现使用短字符优化——当所要处理的字符串过长，这种方法将无需再在堆上分配内存，并且可以将字符串直接进行存储。在这个例子中，移动虽然不是最快的方式，但也不会慢多少。

接下来比较有趣的就是排序操作，其使用了一个Lambda表达式作为自定义比较谓词：

sort(begin(word_counts), end(word_counts),
	[](const auto &a, const auto &b) { return a.second > b.second; });

排序算法将会成对的处理元素，比较两个元素。通过提供的Lambda函数，sort方法将不会再使用默认比较谓词，其会将a.second和b.second进行比较。这里的键值对中，第二个值为词频数，所以可以使用.second得到对应词频数。通过这种方式，将移动所有高频率的词到vector的开始，并且将低频率词放在末尾。