基于字典树的前向/后向分词器

程序员文章站 2022-07-14 14:40:04

...

NLPHW2——基于字典树的前向/后向分词器

作者：王赛宇

完成列表：

基于字典树的前向分词器
在字典树前向分词器的基础上改进为后向分词器

重要说明：项目必须运行在GBK编码环境下

这次作业的目标是实现一个前向、后向分词器。在了解算法后，我认为这里最关键的技术是：如何在一个大的词库中快速的匹配当前的字符串？那么我们先从这个问题的由来开始学起：

什么是前向分词器？

其原理非常简单，实质上就是以句子中的某一个字为起点，从最大长度开始检索，寻找以该字为起点能够组成的最长词语，进行分词的方法，看一个例子：

我是一个非常非常好的人
假定最大长度为5，那么我们从第一个字开始检索：

检索长度检索词是否成词

5 我是一个非否

4 我是一个否

3 我是一否

2 我是是
在检测到长度为2的时候“我是”是一个词，所以进行一次划分，句子被划分为：我是/ 一个非常非常好的人
然后再从划分后的位置开始重新划分

检索长度	检索词	是否成词
5	我是一个非	否
4	我是一个	否
3	我是一	否
2	我是	是

我们可以注意到这种方法十分十分简单；在这一小节中，我们简单了解了什么是前向分词器，在下一节中我们来简单的谈一下他的实现以及存在的问题。

前向分词器的简单实现及其存在的问题

我们已经学会了前向分词器了，如果要实现一个前向分词器，就需要我们：

维护一个词库，用于检索
对句子中的每个字句进行检索

我们在这里说的笼统些，因为这个本身也非常好理解；那么在知道他的简单实现后，我们就会发现，在极端情况下，一个长度为n，最大词长为m的句子，在一个词数为k的词库中进行检索，时间复杂度为：
O ( n m k ) O(n m k) O(nmk)
假设我们的句子有10个字，可能的最大词长为6，词库中有20万词，那么最终检索就需要：6,000,000次运算，如果要进行大规模的分词，这样的速度会非常拉跨。那么现在，我们需要思考：问题的核心是什么？我们回到上面的时间复杂度式子，n和m都是由算法本身带来的，这无法避免。但是在词库中匹配的方法却是可以改变的，那么就有非常多的方法可以去优化它，下面我们来讨论几种，我们从简到难（实现来说）：

最简单的方法：给每一个词一个哈希，将他们排序后插在一个数组中，当我们寻找一个词的时候直接二分就可以了（时间复杂度已经达到要求了）
和上面时间空间一样的方法：直接用自带的Map（红黑树）来实现就可以
更优秀的方法：上面都需要把整个词库存下来，这样就导致很多空间被浪费，如：我，我是，我和，这里面的我重复了三次，非常浪费，于是我们可以建一个中文字典树，来进行检索，这样还有一个好处，就是我们匹配的时候只需要从小到大匹配，匹配到无法进行的时候就是我们想要找的最长词，这个时候可以直接进行分词

本次采用的是字典树的方法对词库进行存储，以及匹配。

基于字典树的前向分词设计与实现

树的节点

树的结点需要记录以下信息：

当前点存储的是哪个字？
当前点是否是一个词的结尾
记录当前点的孩子们

针对于此，我们构建一个结构体来描述：

/**
 * 字典树的树节点
 * @param chineseChar 一个汉字， GBK编码存储，固定为两个字节
 * @bool isEnd 当前字是否是一个词的结尾
 * @param next 一个哈希map， 用于记录当前点的下一个词语
 */
class Node{
public:
    unsigned short chineseChar;
    bool isEnd;
    unordered_map<unsigned short, Node*> next;
};

树的构建

数据成员

首先考虑这颗字典树需要维护的数据成员，在字典树中的检索，只需要保存树根，就可以检索到其他所有的节点了，所以我们直接存储树根即可。

class TrieTree {
    struct Node* root;
};

成员函数

首先，一个类需要构造、析构函数，除此之外，还需要：

向TireTree中添加一个词语
创建一个Node节点
检索一个词语，返回最长检索到多少的长度
一个工具函数，将字符串格式化

最后创建的结果如下：

/**
 * 中文字典树
 */
class TrieTree {

public:
    // 数据成员
    Node* root;

    // 成员函数
    TrieTree(); // 构造函数
    ~TrieTree(); // 析构函数


    // 析构函数时实用的工具函数
    void dfsDelete(Node* treeNode);

    // 向树中插入一个词语
    void insertWord(char* insertString);

    // 在当前树中查询一个词语
    int searchWord(char* searchString);

private:
    // 将一个字符串转化成 vector<unsigned short>
    vector<unsigned short>* transformString(char* transformedString);

};

析构函数与构造函数

析构函数使用深度优先搜索对树的节点进行遍历删除，构造函数直接对根节点进行初始化。

/**
 * 字典树的构造函数，初始化树根
 */
TrieTree::TrieTree() {
    // 初始化树根
    this->root = new struct Node;
    this->root->chineseChar = 0;
    this->root->isEnd = false;
}

/**
 * 析构函数，使用深度优先搜索 遍历、删除节点
 */
TrieTree::~TrieTree() {
    dfsDelete(this->root);
    this->root = nullptr;
}

/**
 * 给出根节点，从根节点开始删除整个trie树
 * @param treeNode 树的节点
 */
void TrieTree::dfsDelete(Node* treeNode) {

    // 创建迭代器
    unordered_map<unsigned short, struct Node*>::iterator iter = treeNode->next.begin();
    for(iter; iter != treeNode->next.end(); iter++){ // 遍历所有节点
        dfsDelete(iter->second);
    }
    // 删除完所有子节点之后，删除当前节点
    delete treeNode;
}

插入单词

插入单词实质上就是插入一个字符串，我们将插入一个字符串分为两步：

一、将字符串变为unsigned short数组
二、将unsigned short数组在树中检索、插入

将字符串转化为数组

/**
 * 将transformedString转化为一个unsigned short数组
 * @param transformedString 被转化的字符串
 * @return 返回一个vector数组，每个元素代表一个字符
 */
vector<unsigned short> *TrieTree::transformString(char *transformedString) {
    auto resList = new vector<unsigned short >();
    unsigned short addItem = 0;
    bool havePre = false;

    // 遍历当前数组
    for(int index = 0; transformedString[index] != '\0'; index++){
        // 如果当前是中文字符的第二个字符
        if(havePre){
            resList->push_back(addItem + ((unsigned short) transformedString[index]));
            havePre = false;
            addItem = 0;
        }
        // 如果是中文字符
        else if(((short) transformedString[index]) < 0){
            addItem = (((unsigned short) transformedString[index]) << 8);
            havePre = true;
        }
        // 如果是英文字符，那么直接放入
        else {
            resList->push_back((((unsigned short) transformedString[index]) << 8));
        }
    }

    return resList;
}

向Trie树中插入字符串

/**
 * 向Trie树中插入一个字符串
 * @param insertString
 */
void TrieTree::insertWord(char *insertString) {
    // 根据字符串获取数字列表
    auto wordList = this->transformString(insertString);

    auto curPoint = this->root;
    for(int index = 0; index < wordList->size(); index ++){
        // 如果当前词段已经存在，那么就直接前进
        if(curPoint->next.count((*wordList)[index])) {
            curPoint = curPoint->next[(*wordList)[index]];
        }
        // 如果当前词段没有存在，那么就创建树的节点，完成添加
        else {
            // 新建子节点
            auto newTreePoint = new Node();
            newTreePoint->next.clear();
            newTreePoint->isEnd = false;
            newTreePoint->chineseChar = (*wordList)[index];
            // 添加父子关系
            curPoint->next[(*wordList)[index]] = newTreePoint;
            // 更新当前点
            curPoint = newTreePoint;
        }
        if(index == wordList->size() - 1){ // 如果是最后一个字，那么就打标记
            curPoint->isEnd = true;
        }
    }
}

在树中查询字符串

/**
 * 给出一个字符串，返回Trie树中找到的最长的长度
 * @param searchString 想要查询的字符串
 * @return 一个数字，表示当前字符串在词库中的最大匹配前缀
 */
int TrieTree::searchWord(char *searchString) {
    // 根据字符串获取数字列表
    auto wordList = this->transformString(searchString);

    auto curPoint = this->root;
    int maxLength = 0;
    int curLength = 0;

    for(auto item: *wordList){
        // 如果当前词段已经存在，那么就直接前进
        if(curPoint->next.count(item)) {
            curPoint = curPoint->next[item];
            curLength ++;
            if(curPoint->isEnd) { // 如果当前是一个词的结束，那么这里才会进行更新
                maxLength = curLength;
            }
        }
        // 否则退出、返回
        else {
            break;
        }
    }

    return max(maxLength, 1);
}

简单测试：

#include "TrieTree.h"
using namespace std;

int main () {
    auto myTrieTree = new TrieTree;
    myTrieTree->insertWord("我是");
    myTrieTree->insertWord("你爸爸是");

    cout << myTrieTree->searchWord("我是") << endl;
    cout << myTrieTree->searchWord("我是你爸爸") << endl;
    cout << myTrieTree->searchWord("你爸爸是我") << endl;
    cout << myTrieTree->searchWord("你爸爸") << endl;
    cout << myTrieTree->searchWord("你爸爸是") << endl;

    return 0;
}

这里的输出如下：

结果符合预期。

为字典树添加读取文件的功能

由于这次作业的数据格式并不统一，所以我们不再将读取特定文件的功能集成到字典树中，而是直接用一个类来进行描述，这样我们就可以指定不同的分词器，只要约定注入的分词器必须有insertData和searchData方法即可：

/**
 * 用于描述数据集
 */
template<class T>
class DataSet {
private:
     T* method; // 需要由外部注入，用于更换方法
public:
    DataSet(); // 构造函数
    ~DataSet(); // 析构函数

    void insertData(char* filename); // 给出数据集的地址，插入数据集
    string searchData(string &sentence); // 给出句子，进行解析

};

实现构造函数与析构函数

/**
 * DataSet的构造函数
 * @tparam T 分词器
 */
template<class T>
DataSet<T>::DataSet() {
    this->method = new T;
}

/**
 * DataSet的析构函数
 * @tparam T 分词器
 */
template<class T>
DataSet<T>::~DataSet() {
    delete this->method;
}

通过分词器添加数据集

/**
 * 给出数据集的地址，插入数据集
 * @tparam T 分词器
 * @param filename 文件名，用于引导程序找到数据集
 */
template<class T>
void DataSet<T>::insertData(char *filename) {

    // 重定向输入
    freopen(filename, "r", stdin);
    string num, word;
    while(cin>> num >> word){
        this->method->insertWord(word);
    }
    cin.clear(); // 清空EOF
    freopen("CON", "r", stdin); // 重定向回控制台
}

给出被分词的语句，进行分词

/**
 * 进行查询，给出一个纯中文字符串，返回一个分句后的字符串
 * @tparam T 分词器
 * @param sentence 被分词的句子
 * @return 分词后的句子
 */
template<class T>
string DataSet<T>::searchData(string &sentence) {
    string resData = sentence.substr(0, sentence.size()); // 用于返回的字符串

    string searchString;
    int curIndex = 0;
    while(curIndex < resData.size()){
        int surplusLength = resData.size() - curIndex;
        searchString = resData.substr(curIndex, min(WORD_MAX_LENGTH, surplusLength));

        int stepLength = this->method->searchWord(searchString);
        curIndex += stepLength * 2;
        if(curIndex < resData.size()){ // 如果不是最后，就插入一个分隔符
            resData.insert(curIndex, 1, '/');
            curIndex ++;
        }

    }

    return resData;
}

结果验证

#include "TrieTree.h"
#include "DataSet.h"
using namespace std;

int main () {
    auto myDataSet = new DataSet<TrieTree>;
    myDataSet->insertData("data.txt");
    while(true){
        cout << "请输入分句的句子：";
        string divSentence;
        cin >> divSentence;
        cout << myDataSet->searchData(divSentence) << endl;
    }

    return 0;
}

使用情况如下：

请输入分句的句子：苦涩的沙吹痛脸庞的感觉
苦涩/的/沙/吹/痛/脸庞/的/感觉
请输入分句的句子：像父亲的责骂母亲的哭泣永远难忘记
像/父亲/的/责骂/母亲/的/哭泣/永远/难忘/记
请输入分句的句子：年少的我喜欢一个人在海边
年少/的/我/喜欢/一个/人/在/海边
请输入分句的句子：卷起裤管光着脚丫踩在沙滩上
卷起/裤管/光/着/脚丫/踩/在/沙滩/上
请输入分句的句子：总是幻想海洋的尽头有另一个世界
总是/幻想/海洋/的/尽头/有/另一/个/世界

更改已有前向算法，使其支持后向算法

在上一节中我们通过字典树实现了前向算法中的快速匹配，但是我们的任务中还需要我们完成后向算法，那么应该怎么办呢？我们还是需要从原理开始思考：

前向算法和后向算法的差异在哪里？

前向是保持前面的不同，从后往前删除进行匹配，后向是后面不动从前往后删除进行匹配；前向是从前往后找，后向是从后往前找。
为什么字典树在前向时能够快速查询？

因为每一大次查询，前缀完全相同

那么在看到上卖弄的差异后，问题就迎刃而解了：

在压入数据集时以及在查询数据集时，倒着压入、倒着查询不就完全一样了么？

那么在代码层面：

DataSet类中insert前对字符串进行翻转
DataSet类中查询前进行翻转，且需要重新写一套移动方法

更改类的定义

/**
 * 用于描述数据集
 */
template<class T>
class DataSet {
private:
     T* method; // 需要由外部注入，用于更换方法
public:
    DataSet(); // 构造函数
    ~DataSet(); // 析构函数

    void insertData(char* filename, bool rev=false); // 给出数据集的地址，插入数据集
    string searchData(string &sentence, bool rev=false); // 给出句子，进行解析
private:
    string doFMM(string &sentence);
    string doBMM(string &sentence);
};

为了保持原有的调用不变，我们为函数加入默认值。

更改insertData实现

非常简单，就是在插入前进行翻转

/**
 * 给出数据集的地址，插入数据集
 * @tparam T 分词器
 * @param filename 文件名，用于引导程序找到数据集
 */
template<class T>
void DataSet<T>::insertData(char *filename, bool rev) {

    // 重定向输入
    freopen(filename, "r", stdin);
    string num, word;
    while(cin>> num >> word){
        if(rev) reverse(word.begin(), word.end());// 如果需要反转，那么就在插入前进行翻转
        this->method->insertWord(word);
    }
    cin.clear(); // 清空EOF
    freopen("CON", "r", stdin); // 重定向回控制台
}

更改searchData实现(基本上重新写一套)

将serachData改为分发器

为了让这个函数好看一点，我们就将反转的和不反转的分离开来写，把原来的入口函数当作一个分发器来用：

/**
 * 进行查询，给出一个纯中文字符串，返回一个分句后的字符串
 * @tparam T 分词器
 * @param sentence 被分词的句子
 * @param rev 选择是正向还是反向，为true时选择反向，默认为false选择正向
 * @return 分词后的句子
 */
template<class T>
string DataSet<T>::searchData(string &sentence, bool rev) {

    string resData = "";

    switch(rev){
        case true: resData = this->doBMM(sentence); break;
        case false: resData = this->doFMM(sentence); break;
        default: cout << "rev type error !" << endl; break;
    }

    return resData;
}

实现doFMM

那么原来的正向就转移到doFMM函数中：

/**
 * 进行查询，给出一个纯中文字符串，返回一个分句后的字符串
 * @tparam T 分词器
 * @param sentence 被分词的句子
 * @return 分词后的句子
 */
template<class T>
string DataSet<T>::doFMM(string &sentence) {
    string resData = sentence.substr(0, sentence.size()); // 用于返回的字符串

    string searchString;
    int curIndex = 0;
    while(curIndex < resData.size()){
        int surplusLength = resData.size() - curIndex;
        searchString = resData.substr(curIndex, min(WORD_MAX_LENGTH, surplusLength));

        int stepLength = this->method->searchWord(searchString);
        curIndex += stepLength * 2;
        if(curIndex < resData.size()){ // 如果不是最后，就插入一个分隔符
            resData.insert(curIndex, 1, '/');
            curIndex ++;
        }

    }

    return resData;
}

验证原有功能

验证原有功能未被打乱(使用以前的代码)：

请输入分句的句子：我是你爹
我是/你/爹
请输入分句的句子：苦涩的沙吹在脸庞的感觉
苦涩/的/沙/吹/在/脸庞/的/感觉

增加doBMM

/**
 * 后向匹配算法
 * @tparam T 分词器
 * @param sentence 被分词的句子
 * @return 分词后的句子
 */
template<class T>
string DataSet<T>::doBMM(string &sentence) {
    string resData = sentence.substr(0, sentence.size()); // 用于返回的字符串
    string checkData = sentence.substr(0, sentence.size()); // 用于检验的的字符串
    reverse(checkData.begin(), checkData.end());// 反转

    string searchString;
    int curIndex = resData.size();
    int checkIndex = 0;
    while(checkIndex < checkData.size()){
        // 探测当前步长，在最大词长和当前剩余空间中取最小
        int surplusLength = checkData.size() - checkIndex;
        searchString = checkData.substr(checkIndex, min(WORD_MAX_LENGTH, surplusLength));

        // 计算最长匹配
        int stepLength = this->method->searchWord(searchString);
        checkIndex += stepLength * 2;
        curIndex -= stepLength * 2;
        if(curIndex > 0){ // 如果不是最后，就插入一个分隔符
            resData.insert(curIndex, 1, '/');
        }
    }

    return resData;

}

验证

循环不写推出clion一直提醒我是死循环，烦死了，于是加了一个退出：

#include "TrieTree.h"
#include "DataSet.h"
using namespace std;

int main () {
    auto myDataSet = new DataSet<TrieTree>;
    myDataSet->insertData(R"(C:\Users\wangsy\Desktop\NLPHW2\data.txt)", true);
    while(true){
        cout << "请输入分句的句子（输入quit以退出）：";
        string divSentence;
        cin >> divSentence;
        if(divSentence == "quit") break;
        cout << myDataSet->searchData(divSentence, true) << endl;
    }

    return 0;
}

结果如下：

请输入分句的句子：苦涩的沙吹痛脸庞的感觉
苦涩/的/沙/吹/痛/脸庞/的/感觉
请输入分句的句子：像父亲的责骂母亲的哭泣永远难忘记
像/父亲/的/责骂/母亲/的/哭泣/永远/难/忘记
请输入分句的句子：年少的我喜欢一个人在海边
年少/的/我/喜欢/一/个人/在/海边
请输入分句的句子：卷起裤管光着脚丫踩在沙滩上
卷起/裤管/光/着/脚丫/踩/在/沙滩/上
请输入分句的句子：总是幻想海洋的尽头有另一个世界
总是/幻想/海洋/的/尽头/有/另/一个/世界
请输入分句的句子：

懒得实现二分和map的了，看懂这个那些不是问题。

许可证

使用mitlicense，如果想要引用代码，需要将该license的全部内容一并携带。

相关标签： c++ 自然语言处理数据结构算法

上一篇： clojure-基本语法-函数定义

下一篇： clojure-基本语法-字符串类型

基于字典树的前向/后向分词器

NLPHW2——基于字典树的前向/后向分词器

什么是前向分词器？

前向分词器的简单实现及其存在的问题

基于字典树的前向分词设计与实现

树的节点

树的构建

数据成员

成员函数

析构函数与构造函数

插入单词

将字符串转化为数组

向Trie树中插入字符串

在树中查询字符串

简单测试：

为字典树添加读取文件的功能

实现构造函数与析构函数

通过分词器添加数据集

给出被分词的语句，进行分词

结果验证

更改已有前向算法，使其支持后向算法

更改类的定义

更改insertData实现

更改searchData实现(基本上重新写一套)

将serachData改为分发器

实现doFMM

验证原有功能

增加doBMM

验证

许可证

C#实现前向最大匹、字典树（分词、检索）的示例代码

基于字典树的前向/后向分词器

C#实现前向最大匹、字典树（分词、检索）的示例代码