Skip to content

Latest commit

 

History

History
193 lines (148 loc) · 8.12 KB

chapter6-1-chinese.md

File metadata and controls

193 lines (148 loc) · 8.12 KB
Raw

使用STL算法实现单词查找树类

所谓的trie数据类型，能够对感兴趣的数据进行存储，并且易于查找。将文本语句分割成多个单词，放置在列表中，我们能发现其开头一些单词的共性。

让我们看下下图，这里有两个句子“hi how are you”和“hi how do you do”，存储在一个类似于树的结构体中。其都以“hi how”开头，句子后面不同的部分，划分为树结构：

因为trie数据结构结合了相同的前缀，其也称为前缀树，很容易使用STL的数据结构实现。本章我们将关注如何实现我们自己的trie类。

How to do it...

本节，我们将使用STL数据结构和算法实现前缀树结构。

  1. 包含必要的头文件和声明所使用的命名空间

    #include <iostream>
#include <optional>
#include <algorithm>
#include <functional>
#include <iterator>
#include <map>
#include <vector>
#include <string>

using namespace std;

  2. 我们首先实现一个类。我们的实现中，trie为map的递归映射。每个trie节点够包含一个map，节点的有效值T映射了下一个节点：

    template <typename T>
class trie
{
	map<T, trie> tries;

  3. 将新节点插入队列的代码很简单。使用者需要提供一个begin/end迭代器对，并且会通过循环进行递归。当用户输入的序列为{1, 2, 3}时，我们可以将1作为一个子trie，2为下一个子trie，以此类推。如果这些子trie在之前不存在，其将会通过std::map的[]操作符进行添加：

    public:
    template <typename It>
    void insert(It it, It end_it) {
        if (it == end_it) { return; }
        tries[*it].insert(next(it), end_it);
    }

  4. 我们这里也会定义一个辅助函数，用户只需要提供一个容器，之后辅助函数就会通过迭代器自动进行查询：

    	template <typename C>
    void insert(const C &container) {
    	insert(begin(container), end(container));
    }

  5. 调用我们的类时，可以写成这样my_trie.insert({"a", "b","c"}); ，必须帮助编译器正确的判断出这段代码中的所有类型，因此我们又添加了一个函数，这个函数用于重载的插入接口：

    	void insert(const initializer_list<T> &il) {
		insert(begin(il), end(il));
	}

  6. 我们也想了解，trie中有什么，所以我们需要一个打印函数。为了打印，我们可以对tire进行深度遍历。这样根节点下面的是第一个叶子节点，我们会记录我们所看到的元素的负载。当我们达到叶子节点，那么就可以进行打印了。我们会看到，当到达叶子的时候tries.empty()为true。递归调用print后，我们将再次弹出最后添加的负载元素：

        void print(vector<T> &v) const {
        if (tries.empty()) {
            copy(begin(v), end(v),
            	ostream_iterator<T>{cout, " "});
            cout << '\n';
        }
        for (const auto &p : tries) {
            v.push_back(p.first);
            p.second.print(v);
            v.pop_back();
        }
    }

  7. 打印函数需要传入一个可打印负载元素的列表，不过用户不需要传入任何参数就能调用它。这样，我们就定义了一个无参数的打印函数，其构造了辅助列表对象：

    	void print() const {
        vector<T> v;
        print(v);
    }

  8. 现在，我们就可以创建和打印trie了，我们将先搜索子trie。当trie包含的序列为{a, b, c}和{a, b, d, e}，并且我们给定的序列为{a, b}，对于查询来说，返回的子序列为包含{c}和{d, e}的部分。当我们找到子trie，将返回一个const的引用。在搜索中，也会出现没有要搜索序列的情况。即便如此，我们还是要返回些什么。std::optional是一个非常好的帮手，因为当没有找到匹配的序列，我们可以返回一个空的optional对象：

        template <typename It>
    optional<reference_wrapper<const trie>>
    subtrie(It it, It end_it) const {
        if (it == end_it) { return ref(*this); }
        auto found (tries.find(*it));
        if (found == end(tries)) { return {}; }
        
        return found->second.subtrie(next(it), end_it);
    }

  9. 与insert方法类似，我们将提供一个只需要一个参数的subtrie方法，其能自动的从输入容器中获取迭代器：

        template <typename C>
    auto subtrie(const C &c) {
    	return subtrie(begin(c), end(c));
    }
};

  10. 这样就实现完了。我们在主函数中使用我们trie类，使用std::string类型对类进行特化，并实例化对象：

    int main()
{
    trie<string> t;
    t.insert({"hi", "how", "are", "you"});
    t.insert({"hi", "i", "am", "great", "thanks"});
    t.insert({"what", "are", "you", "doing"});
    t.insert({"i", "am", "watching", "a", "movie"});

  11. 打印整个trie：

    	cout << "recorded sentences:\n";
	t.print();

  12. 而后，我们将获取输入语句的子trie，其以“hi”开头：

        cout << "\npossible suggestions after \"hi\":\n";

    if (auto st (t.subtrie(initializer_list<string>{"hi"}));
        st) {
        st->get().print();
    }
}

  13. 编译并运行程序，其会返回两个句子的以“hi”开头的子trie：

    $ ./trie
recorded sentences:
hi how are you
hi i am great thanks
i am watching a movie
what are you doing

possible suggestions after "hi":
how are you
i am great thanks

How it works...

有趣的是，单词序列的插入代码要比在子trie查找给定字母序列的代码简单许多。所以，我们首先来看一下插入代码：

template <typename It>
void trie::insert(It it, It end_it) {
    if (it == end_it) { return; }
    tries[*it].insert(next(it), end_it);
}

迭代器对it和end_it，表示要插入的字符序列。tries[*it]代表在子trie中要搜索的第一个字母，然后调用.insert(next(it), end_it);对更低级的子trie序列使用插入函数，使用迭代器一个词一个词的推进。 if (it == end_it) { return; }行会终止递归。返回语句不会做任何事情，这到有点奇怪了。所有插入操作都在tries[*it]语句上进行，std::map的中括号操作将返回键所对应的值或是创建该键，相关的值(本节中映射类型是一个trie)由默认构造函数构造。这样，当我们查找不理解的单词时，就能隐式的创建一个新的trie分支。

查找子trie看起来十分复杂，因为我们没有必要隐藏那么多的代码：

template <typename It>
optional<reference_wrapper<const trie>>
subtrie(It it, It end_it) const {
    if (it == end_it) { return ref(*this); }
    auto found (tries.find(*it));
    if (found == end(tries)) { return {}; }

    return found->second.subtrie(next(it), end_it);
}

这段代码的主要部分在于auto found (tries.find(*it));。我们使用find来替代中括号操作符。当我们使用中括号操作符进行查找时，trie将会为我们创建丢失的元素(顺带一提，当我们尝试这样做，类的函数为const，所以这样做事不可能的。这样的修饰能帮助我们减少bug的发生)。

另一个细节是返回值optional<reference_wrapper<const trie>>。我们选择std::optional作为包装器，因为其可能没有我们所要找打tire。当我们仅插入“hello my friend”，那么就不会找到“goodbye my friend”。这样，我们仅返回{}就可以了，其代表返回一个空optional对象给调用者。不过这还是没有解释，我们为什么使用reference_wrapper代替optional<const trie &>。optional的实例，其为trie&类型，是不可赋值的，因此不会被编译。使用reference_warpper实现一个引用，就是用来对对象进行赋值的。