namespace ns_searcher {
	class searcher {
	private:
		ns_index::index* _index; // 建立索引的类

	public:
        // 初始化接口
        // 在搜索之前需要先建立索引. 这个接口就是建立索引用的
		void initSearcher(const std::string& input) {}

		// 搜索接口
		// 搜索需要实现什么功能?
        // 搜索需要接收字符串, 然后针对字符串进行分词 再根据分词在索引中进行查找
		// 首先参数部分需要怎么实现?
		// 参数部分, 需要接收需要搜索的句子或关键字, 还需要一个输出型参数 用于输出查找结果
		//  查找结果我们使用jsoncpp进行序列化和反序列化
		void search(const std::string& query, std::string* jsonString) {}

namespace ns_index {

	// 用于正排索引中 存储文档内容
	typedef struct docInfo {
		std::string _title;	  // 文档标题
		std::string _content; // 文档去标签之后的内容
		std::string _url;	  // 文档对应官网url
		std::size_t _docId;	  // 文档id
	} docInfo_t;

	// 用于倒排索引中 记录关键字对应的文档id和权重
	typedef struct invertedElem {
		std::size_t _docId;	   // 文档id
		std::string _keyword;  // 关键字
		std::uint64_t _weight; // 搜索此关键字, 此文档id 所占权重

		invertedElem() // 权重初始化为0
			: _weight(0) {}
	} invertedElem_t;

	// 关键字的词频
	typedef struct keywordCnt {
		std::size_t _titleCnt;	 // 关键字在标题中出现的次数
		std::size_t _contentCnt; // 关键字在内容中出现的次数

		keywordCnt()
			: _titleCnt(0)
			, _contentCnt(0) {}
	} keywordCnt_t;

	// 倒排拉链
	typedef std::vector<invertedElem_t> invertedList_t;

	class index {
	private:
		// 正排索引使用vector, 下标天然是 文档id
		std::vector<docInfo_t> forwardIndex;
		// 倒排索引 使用 哈希表, 因为倒排索引 一定是 一个keyword 对应一组 invertedElem拉链
		std::unordered_map<std::string, invertedList_t> invertedIndex;

		// 单例模式设计
		index() {}

		index(const index&) = delete;
		index& operator=(const index&) = delete;

		static index* _instance; // 单例
		static std::mutex _mtx;

	public:
		// 获取单例
		static index* getInstance() {
			if (nullptr == _instance) {
				_mtx.lock();
				if (nullptr == _instance) {
					_instance = new index;
				}
				_mtx.unlock();
			}

			return _instance;
		}
		
        // 通过关键字 检索倒排索引, 获取对应的 倒排拉链
		invertedList_t* getInvertedList(const std::string& keyword) {}

		// 通过倒排拉链中 每个倒排元素中存储的 文档id, 检索正排索引, 获取对应文档内容
		docInfo_t* getForwardIndex(std::size_t docId) {}

		// 根据parser模块处理过的 所有文档的信息
		// 提取文档信息, 建立 正排索引和倒排索引
		// input 为 ./data/output/raw
		bool buildIndex(const std::string& input) {}

	private:
		// 对一个文档建立正排索引
		docInfo_t* buildForwardIndex(const std::string& file) {}
        // 对一个文档建立倒排索引
		bool buildInvertedIndex(const docInfo_t& doc) {}
	};
	// 单例相关
	index* index::_instance = nullptr;
	std::mutex index::_mtx;
}

void initSearcher(const std::string& input) {
    // 搜索前的初始化操作
    // search类成员 ns_index::index* _index 获取单例
    _index = ns_index::index::getInstance();
    std::cout << "获取单例成功 ..." << std::endl;
    
    // 建立索引
    _index->buildIndex(input);
    std::cout << "构建正排索引、倒排索引成功 ..." << std::endl;
}

typedef struct invertedElemOut {
    std::size_t _docId;
    std::uint64_t _weight;
    std::vector<std::string> _keywords;
} invertedElemOut_t;

// 搜索接口
// 首先参数部分需要怎么实现?
// 参数部分, 需要接收需要搜索的句子或关键字, 还需要一个输出型参数 用于输出查找结果
//  查找结果我们使用jsoncpp进行序列化和反序列化
// search() 具体需要实现的功能:
//  1. 对接收的句子或关键词进行分词
//  2. 根据分词, 在倒排索引中查找到所有分词的倒排拉链 并汇总其中的 invertedElem, 然后根据相关性进行排序
//  4. 然后再遍历所有的 invertedElem, 根据 invertedElem中存储的 文档id, 在正排索引中获取到文档内容
//  5. 然后将获取到的文档内容使用jsoncpp 进行序列化, 存储到输出型参数中
// 直到遍历完invertedElem
void search(const std::string& query, std::string* jsonString) {
    // 1. 对需要搜索的句子或关键词进行分词
    std::vector<std::string> keywords;
    ns_util::jiebaUtil::cutString(query, &keywords);

    // 统计文档用, 因为可能存在不同的分词 在倒排索引中指向同一个文档的情况
    // 如果不去重, 会重复展示
    std::unordered_map<std::size_t, invertedElemOut_t> invertedElemOutMap;
    // 2. 根据分词获取倒排索引中的倒排拉链, 并汇总去重 invertedElem
    for (std::string word : keywords) {
        boost::to_lower(word);

        ns_index::invertedList_t* tmpInvertedList = _index->getInvertedList(word);
        if (nullptr == tmpInvertedList) {
            // 没有这个关键词
            continue;
        }

        for (auto& elem : *tmpInvertedList) {
            // 遍历倒排拉链, 根据文档id 对invertedElem 去重
            auto& item = invertedElemOutMap[elem._docId]; // 在map中获取 或 创建对应文档id的 invertedElem
            item._docId = elem._docId;
            item._weight += elem._weight;
            // 权重需要+= 是因为多个关键词指向了同一个文档 那么就说明此文档的与搜索内容的相关性更高
      		// 就可以将多个关键字关于此文档的权重相加, 表示搜索相关性高
            // 最好也将 此文档相关的关键词 也存储起来, 因为在客户端搜索结果中, 可能需要对网页中有的关键字进行高亮
            // 但是 invertedElem 的第三个成员是 单独的一个string对象, 不太合适
            // 所以, 可以定义一个与invertedElem 相似的, 但是第三个成员是一个 vector 的类, 比如 invertedElemOut
            item._keywords.push_back(elem._keyword);
            // 此时就将当前invertedElem 去重到了 invertedElemMap 中
        }
    }
    
    // vector 存储 文档id相关信息, 方便排序
    std::vector<invertedElemOut_t> allInvertedElemOut;
    // 出循环之后, 就将搜索到的 文档的 id、权重和相关关键词 存储到了 invertedElemMap
    // 然后将文档的相关信息 invertedElemOut 都存储到 vector 中
    for (const auto& elemOut : invertedElemOutMap) {
        // map中的second: elemOut, 在执行此操作之后, 就没用了
        // 所以使用移动语义, 防止发生拷贝
        allInvertedElemOut.push_back(std::move(elemOut.second));
    }

    // 执行到这里, 可以搜索到的文档id 权重 和 相关关键词的信息, 已经都在allInvertedElemOut 中了.
    // 但是, 还不能直接 根据文档id 在正排索引中检索
    // 因为, 此时如果直接进行文档内容的索引, 在找到文档内容之后, 就要直接进行序列化并输出了. 而客户端显示的时候, 反序列化出来的文档顺序, 就是显示的文档顺序
    // 但是现在找到的文档还是乱序的. 还需要将allInvertedElemOut中的相关文档, 通过_weight 进行倒序排列
    // 这样, 序列化就是按照倒序排列的, 反序列化也会如此, 显示同样如此
    std::sort(allInvertedElemOut.begin(), allInvertedElemOut.end(),
              [](const invertedElemOut_t& elem1, const invertedElemOut_t& elem2) {
                  return elem1._weight > elem2._weight;
              });

    // 排序之后, allInvertedElemOut中 文档的排序就是降序了
    // 然后 通过遍历此数组, 获取文档id, 根据id获取文档在正排索引中的内容
    // 然后再将 所有内容序列化
    Json::Value root;
    for (auto& elemOut : allInvertedElemOut) {
        // 通过Json::Value 对象, 存储文档内容
        Json::Value elem;
        // 通过elemOut._docId 获取正排索引中 文档的内容信息
        ns_index::docInfo_t* doc = _index->getForwardIndex(elemOut._docId);
        // elem赋值
        elem["url"] = doc->_url;
        elem["title"] = doc->_title;
        // 关于文档的内容, 搜索结果中是不展示文档的全部内容的, 应该只显示包含关键词的摘要, 点进文档才显示相关内容
        // 而docInfo中存储的是文档去除标签之后的所有内容, 所以不能直接将 doc._content 存储到elem对应key:value中
        elem["desc"] = getDesc(doc->_content, elemOut._keywords[0]); // 只根据第一个关键词来获取摘要
        // for Debug
        // 这里有一个bug, jsoncpp 0.10.5.2 是不支持long或long long 相关类型的, 所以需要转换成 double
        // 这里转换成 double不会有什么影响, 因为这两个参数只是本地调试显示用的.
        elem["docId"] = (double)doc->_docId;
        elem["weight"] = (double)elemOut._weight;

        root.append(elem);
    }

    // 序列化完成之后将相关内容写入字符串
    // for Debug 用 styledWriter
    Json::StyledWriter writer;
    *jsonString = writer.write(root);
}

std::string getDesc(const std::string& content, const std::string& keyword) {
    // 如何获取摘要呢?
    // 我们尝试获取正文中 第一个keyword 的前50个字节和后100个字节的内容 作为摘要
    const std::size_t prevStep = 50;
    const std::size_t nextStep = 100;

    // 获取正文中 第一个 keyword 的位置
    std::size_t pos = content.find(keyword);
    if (pos == std::string::npos)
        return "keyword does not exist!";

    std::size_t begin = 0;
    std::size_t end = content.size() - 1;

    // 获取前50字节 和 后100字节的迭代器位置
    if (pos > begin + prevStep)
        begin += (pos - prevStep);
    if (pos + nextStep < end)
        end = pos + nextStep;

    if (begin >= end)
        return "nothing!";

    // 获取摘要
    std::string desc;
    if (content.begin() + begin > content.begin())
        desc = "...";
    desc += content.substr(begin, end - begin);
    if (content.begin() + end < content.end())
        desc += "...";

    return desc;
}

#include <iostream>
#include "util.hpp"
#include "index.hpp"
#include "searcher.hpp"

const std::string& rawPath = "./data/output/raw";

int main() {
	ns_searcher::searcher searcher;
	searcher.initSearcher(rawPath);

	std::string query;
	std::string json_string;

	char buffer[1024];
	while (true) {
		std::cout << "Please Enter You Search Query# ";
		fgets(buffer, sizeof(buffer) - 1, stdin);
		buffer[strlen(buffer) - 1] = 0;
		query = buffer;
		searcher.search(query, &json_string);
		std::cout << json_string << std::endl;
	}

	return 0;
}

std::string getDesc(const std::string& content, const std::string& keyword) {
    // 如何获取摘要呢?
    // 我们尝试获取正文中 第一个keyword 的前50个字节和后100个字节的内容 作为摘要
    const std::size_t prevStep = 50;
    const std::size_t nextStep = 100;
    // 获取正文中 第一个 keyword 的位置

    // std::size_t pos = content.find(keyword);
    // if (pos == std::string::npos)
    //     return "keyword does not exist!";
    // 直接这样处理, 会出现一个问题:
    // keyword是有大小写的. 倒排索引中查找 我们实现的是忽略大小写, 所以可以找到文档
    // 而 string::find() 是区分大小写的查找, 可能无法在内容中找到对应的关键词
    // string容器也没有提供不区分大小写的查找方法
    // 此时, 可以用std::search()
    // std::search(it1, it2, it3, it4, pred);
    // 可以在[it1, it2)中 查找第一个[it3, it4)(词语)的出现位置.
    // 并且, 如果使用第5个参数, 就可以传入 带有两个参数的仿函数, 这两个参数就是需要比较的字符
    // 可以在仿函数内设置这两个字符的比较方式
    // 最终会返回找到的找到的单次第一个字符位置的迭代器, 否则返回it2
    auto iter = std::search(content.begin(), content.end(), keyword.begin(), keyword.end(),
                            [](int x, int y) {
                                return std::tolower(x) == std::tolower(y);
                            });
    if (iter == content.end())
        return "keyword does not exist!";
    std::size_t pos = std::distance(content.begin(), iter);

    std::size_t begin = 0;
    std::size_t end = content.size() - 1;

    // 获取前50字节 和 后100字节的迭代器位置
    if (pos > begin + prevStep)
        begin += (pos - prevStep);
    if (pos + nextStep < end)
        end = pos + nextStep;

    if (begin >= end)
        return "nothing!";

    // 获取摘要
    std::string desc;
    if (content.begin() + begin > content.begin())
        desc = "...";
    desc += content.substr(begin, end - begin);
    if (content.begin() + end < content.end())
        desc += "...";

    return desc;
}

const char* const DICT_PATH = "./cppjiebaDict/jieba.dict.utf8";
const char* const HMM_PATH = "./cppjiebaDict/hmm_model.utf8";
const char* const USER_DICT_PATH = "./cppjiebaDict/user.dict.utf8";
const char* const IDF_PATH = "./cppjiebaDict/idf.utf8";
const char* const STOP_WORD_PATH = "./cppjiebaDict/stop_words.utf8";

class jiebaUtil {
    private:
    cppjieba::Jieba _jieba;
    std::unordered_map<std::string, bool> _stopKeywordMap;

    jiebaUtil()
        : _jieba(DICT_PATH, HMM_PATH, USER_DICT_PATH, IDF_PATH, STOP_WORD_PATH) {}

    jiebaUtil(const jiebaUtil&) = delete;
    jiebaUtil& operator=(const jiebaUtil&) = delete;

    static jiebaUtil* _instance;

    private:
    // 主要是为了支持 消除停止词的分词
    // 也就是需要将停止词, 写入到 map中
    bool initJiebaUtil() {
        // 首先按行读取文件 const char* const STOP_WORD_PATH = "./cppjiebaDict/stop_words.utf8"
        std::ifstream stopFile(STOP_WORD_PATH, std::ios::in);
        if (!stopFile.is_open()) {
            return false;
        }

        std::string line;
        while (std::getline(stopFile, line)) {
            _stopKeywordMap.insert({line, true});
        }

        stopFile.close();

        return true;
    }
    
    void noStopHelper(const std::string& src, std::vector<std::string>* out) {
        _jieba.CutForSearch(src, *out);
        // 遍历out 查询是否为停止词 是则删除
        // 需要注意迭代器失效的问题
        for (auto iter = out->begin(); iter != out->end();) {
            std::string word = *iter;
            boost::to_lower(word);
            // 这里要注意, 函数的第一个参数 src 传入的一般是文档原文 或 搜索内容的原文
            // 原文内容都是区分大小写的, 也就是说这里的iter指向的分词都是有大小写之分的
            // 而jieba库提供的停用词都是小写的, 也就是说_stopKeywordMap内存储的内容都是小写的
            // 如果拿着有大小写之分的分词, 在停用词表中查找, 是查找不到的. 
            // 所以在查找之前, 要先将iter指向的分词 小写化, 然后再在停用词表中找
            auto stopIt = _stopKeywordMap.find(word);
            if (stopIt != _stopKeywordMap.end())
                // 注意接收erase的返回值 防止出现迭代器失效问题
                iter = out->erase(iter);
            else
                iter++;
        }
    }

    public:
    static jiebaUtil* getInstance() {
        static std::mutex mtx;
        if (nullptr == _instance) {
            mtx.lock();
            if (nullptr == _instance) {
                _instance = new jiebaUtil;
                _instance->initJiebaUtil(); // 初始化单例
            }
            mtx.unlock();
        }

        return _instance;
    }

    // 分词: 不消除停止词的版本
    void cutString(const std::string& src, std::vector<std::string>* out) {
        _jieba.CutForSearch(src, *out);
    }
    // 分词: 消除停止词的版本
    void cutStringNoStop(const std::string& src, std::vector<std::string>* out) {
        noStopHelper(src, out);
    }
};
jiebaUtil* jiebaUtil::_instance;

// 关于分词 使用 cppjieba 中文分词库
bool buildInvertedIndex(const docInfo_t& doc) {
    // 用来映射关键字 和 关键字的词频
    std::unordered_map<std::string, keywordCnt_t> keywordsMap;
    ns_util::jiebaUtil* jiebaIns = ns_util::jiebaUtil::getInstance();
    
    // 标题分词
    std::vector<std::string> titleKeywords;
    jiebaIns->cutStringNoStop(doc._title, &titleKeywords); // 去除停用词分词
    // ns_util::jiebaUtil::cutString(doc._title, &titleKeywords);
    // 标题词频统计 与 转换 记录
    for (auto keyword : titleKeywords) {
        boost::to_lower(keyword);		  // 关键字转小写
        keywordsMap[keyword]._titleCnt++; // 记录关键字 并统计标题中词频
        // unordered_map 的 [], 是用来通过keyword值 访问value的. 如果keyword值已经存在, 则返回对应的value, 如果keyword值不存在, 则会插入keyword并创建对应的value
    }

    // 内容分词
    std::vector<std::string> contentKeywords;
    jiebaIns->cutStringNoStop(doc._content, &contentKeywords); // 去除停用词分词
    // ns_util::jiebaUtil::cutString(doc._content, &contentKeywords);
    // 内容词频统计 与 转换 记录
    for (auto keyword : contentKeywords) {
        boost::to_lower(keyword);			// 关键字转小写
        keywordsMap[keyword]._contentCnt++; // 记录关键字 并统计内容中词频
    }

    // 这两个const 变量是用来计算 关键字在文档中的权重的.
    // 并且, 关键字出现在标题中  文档与关键字的相关性大概率是要高的, 所以 可以把titleWeight 设置的大一些
    const int titleWeight = 40;
    const int contentWeight = 1;
    // 分词并统计词频之后, keywordsMap 中已经存储的当前文档的所有关键字, 以及对应的在标题 和 内容中 出现的频率
    // 就可以遍历 keywordsMap 获取关键字信息, 构建 invertedElem 并添加到 invertedIndex中 关键词的倒排拉链 invertedList中了
    for (auto& keywordInfo : keywordsMap) {
        invertedElem_t item;
        item._docId = doc._docId;		   // 本文档id
        item._keyword = keywordInfo.first; // 关键字
        item._weight = keywordInfo.second._titleCnt * titleWeight + keywordInfo.second._contentCnt * contentWeight;

        // 上面构建好了 invertedElem, 下面就要将 invertedElem 添加到对应关键字的 倒排拉链中, 构建倒排索引
        invertedList_t& list = invertedIndex[keywordInfo.first]; // 获取关键字对应的倒排拉链
        list.push_back(std::move(item));
    }

    return true;
}

void search(const std::string& query, std::string* jsonString) {
    // 1. 对需要搜索的句子或关键词进行分词
    std::vector<std::string> keywords;
    ns_util::jiebaUtil* jiebaIns = ns_util::jiebaUtil::getInstance();

    jiebaIns->cutString(query, &keywords); // 不去除停用词分词
    // ns_util::jiebaUtil::cutString(query, &keywords);
    
    // 统计文档用, 因为可能存在不同的分词 在倒排索引中指向同一个文档的情况
    // 如果不去重, 会重复展示
    std::unordered_map<std::size_t, invertedElemOut_t> invertedElemOutMap;
    // 2. 根据分词获取倒排索引中的倒排拉链, 并汇总去重 invertedElem
    for (std::string word : keywords) {
        boost::to_lower(word);

        ns_index::invertedList_t* tmpInvertedList = _index->getInvertedList(word);
        if (nullptr == tmpInvertedList) {
            // 没有这个关键词
            continue;
        }

        for (auto& elem : *tmpInvertedList) {
            // 遍历倒排拉链, 根据文档id 对invertedElem 去重
            auto& item = invertedElemOutMap[elem._docId]; // 在map中获取 或 创建对应文档id的 invertedElem
            item._docId = elem._docId;
            item._weight += elem._weight;
            item._keywords.push_back(elem._keyword);
            // 此时就将当前invertedElem 去重到了 invertedElemMap 中
        }
    }

    // vector 存储 文档相关信息, 方便排序
    std::vector<invertedElemOut_t> allInvertedElemOut;
    // 出循环之后, 就将搜索到的 文档的 id、权重和相关关键词 存储到了 invertedElemMap
    // 然后将文档的相关信息 invertedElemOut 都存储到 vector 中
    for (const auto& elemOut : invertedElemOutMap) {
        // map中的second: elemOut, 在执行此操作之后, 就没用了
        // 所以使用移动语义, 防止发生拷贝
        allInvertedElemOut.push_back(std::move(elemOut.second));
    }

    std::sort(allInvertedElemOut.begin(), allInvertedElemOut.end(),
              [](const invertedElemOut_t& elem1, const invertedElemOut_t& elem2) {
                  return elem1._weight > elem2._weight;
              });

    // 然后 通过遍历此数组, 获取文档id, 根据id获取文档在正排索引中的内容
    // 然后再将 所有内容序列化
    Json::Value root;
    for (auto& elemOut : allInvertedElemOut) {
        // 通过Json::Value 对象, 存储文档内容
        Json::Value elem;
        // 通过elemOut._docId 获取正排索引中 文档的内容信息
        ns_index::docInfo_t* doc = _index->getForwardIndex(elemOut._docId);
        // elem赋值
        elem["url"] = doc->_url;
        elem["title"] = doc->_title;
        // 关于文档的内容, 搜索结果中是不展示文档的全部内容的, 应该只显示包含关键词的摘要, 点进文档才显示相关内容
        // 而docInfo中存储的是文档去除标签之后的所有内容, 所以不能直接将 doc._content 存储到elem对应key:value中
        elem["desc"] = getDesc(doc->_content, elemOut._keywords[0]); // 只根据第一个关键词来获取摘要
        // for Debug
        // 这里有一个bug, jsoncpp 0.10.5.2 是不支持long或long long 相关类型的, 所以需要转换成 double
        // 这里转换成 double不会有什么影响, 因为这两个参数只是本地调试显示用的.
        elem["docId"] = (double)doc->_docId;
        elem["weight"] = (double)elemOut._weight;

        root.append(elem);
    }

    // 序列化完成之后将相关内容写入字符串
    // for Debug 用 styledWriter
    Json::StyledWriter writer;
    *jsonString = writer.write(root);
}

❯ pwd
/home/July/gitCode/gitHub/Boost-Doc-Searcher
❯ tree -L 3
.
├── cppjieba
│   ├── DictTrie.hpp
│   ├── ...(jieba库相关头文件)
│   └── Unicode.hpp
├── cppjiebaDict
│   ├── hmm_model.utf8
│   ├── ...(jieba库提供的分词库)
│   └── user.dict.utf8
├── data
│   ├── input
│   │   ├── about.html
│   │   ├── ...(Boost库文档文件)
│   │   └── yap.html
│   └── output
│       └── raw
├── index.hpp
├── LICENSE
├── makefile
├── parser.cc
├── README.md
├── searcher.hpp
├── serverDebug.cc
└── util.hpp

63 directories, 279 files

// util.hpp 一般定义一些通用的宏定义、工具函数等

#pragma once

#include <boost/algorithm/string/case_conv.hpp>
#include <iostream>
#include <unordered_map>
#include <vector>
#include <string>
#include <fstream>
#include <mutex>
#include <boost/algorithm/string.hpp>
#include "cppjieba/Jieba.hpp"

namespace ns_util {
    class fileUtil {
    public:
        // readFile 用于读取指定文本文件的内容, 到string输出型参数中
        static bool readFile(const std::string& filePath, std::string* out) {
            // 要读取文件内容, 就要先打开文件
            // 1. 以读取模式打开文件
            std::ifstream in(filePath, std::ios::in);
            if (!in.is_open()) {
                // 打卡文件失败
                std::cerr << "Failed to open " << filePath << "!" << std::endl;
                return false;
            }

            // 走到这里打开文件成功
            // 2. 读取文件内, 并存储到out中
            std::string line;
            while (std::getline(in, line)) {
                *out += line;
            }

            in.close();

            return true;
        }
    };

    class stringUtil {
    public:
        static bool split(const std::string& file, std::vector<std::string>* fileResult, const std::string& sep) {
            // 使用 boost库中的split接口, 可以将 string 以指定的分割符分割, 并存储到vector<string>输出型参数中
            boost::split(*fileResult, file, boost::is_any_of(sep), boost::algorithm::token_compress_on);
            // boost::algorithm::token_compress_on 表示压缩连续的分割符

            if (fileResult->empty()) {
                return false;
            }

            return true;
        }
    };

    const char* const DICT_PATH = "./cppjiebaDict/jieba.dict.utf8";
    const char* const HMM_PATH = "./cppjiebaDict/hmm_model.utf8";
    const char* const USER_DICT_PATH = "./cppjiebaDict/user.dict.utf8";
    const char* const IDF_PATH = "./cppjiebaDict/idf.utf8";
    const char* const STOP_WORD_PATH = "./cppjiebaDict/stop_words.utf8";

    class jiebaUtil {
    private:
        cppjieba::Jieba _jieba;
        std::unordered_map<std::string, bool> _stopKeywordMap;

        jiebaUtil()
            : _jieba(DICT_PATH, HMM_PATH, USER_DICT_PATH, IDF_PATH, STOP_WORD_PATH) {}

        jiebaUtil(const jiebaUtil&) = delete;
        jiebaUtil& operator=(const jiebaUtil&) = delete;

        static jiebaUtil* _instance;

    private:
        void noStopHelper(const std::string& src, std::vector<std::string>* out) {
            _jieba.CutForSearch(src, *out);
            // 遍历out 查询是否为停止词 是则删除
            // 需要注意迭代器失效的问题
            for (auto iter = out->begin(); iter != out->end();) {
                std::string word = *iter;
                boost::to_lower(word);
                auto stopIt = _stopKeywordMap.find(word);
                // auto stopIt = _stopKeywordMap.find(*iter);
                if (stopIt != _stopKeywordMap.end()) {
                    // 注意接收erase的返回值 防止出现迭代器失效问题
                    iter = out->erase(iter);
                }
                else {
                    iter++;
                }
            }
        }

        // 主要是为了支持 消除停止词的分词
        // 也就是需要将停止词, 写入到 map中
        bool initJiebaUtil() {
            // 首先按行读取文件 const char* const STOP_WORD_PATH = "./cppjiebaDict/stop_words.utf8"
            std::ifstream stopFile(STOP_WORD_PATH, std::ios::in);
            if (!stopFile.is_open()) {
                return false;
            }

            std::string line;
            while (std::getline(stopFile, line)) {
                _stopKeywordMap.insert({line, true});
            }

            stopFile.close();

            return true;
        }

    public:
        static jiebaUtil* getInstance() {
            static std::mutex mtx;
            if (nullptr == _instance) {
                mtx.lock();
                if (nullptr == _instance) {
                    _instance = new jiebaUtil;
                    _instance->initJiebaUtil();
                }
                mtx.unlock();
            }

            return _instance;
        }

        // 分词: 不消除停止词的版本
        void cutString(const std::string& src, std::vector<std::string>* out) {
            _jieba.CutForSearch(src, *out);
        }
        // 分词: 消除停止词的版本
        void cutStringNoStop(const std::string& src, std::vector<std::string>* out) {
            noStopHelper(src, out);
        }
    };
    jiebaUtil* jiebaUtil::_instance;
    // cppjieba::Jieba jiebaUtil::jieba(DICT_PATH, HMM_PATH, USER_DICT_PATH, IDF_PATH, STOP_WORD_PATH);
}

// 本代码是 建立索引相关的接口
// 索引 是用来快速搜索的
// parser模块, 已经将所有文档内容处理好, 并存储到了 data/output/raw 中
// 索引的建立, 就是通过获取 已经处理好的文档内容 来建立的
// 项目中, 需要分别建立正排索引和倒排索引
// 正排索引, 是从文档id 找到文件内容的索引
// 倒排索引, 是从关键词 找到关键词所在文档id 的索引

// 首先第一个问题:
// 正排索引中 文件内容该如何表示?
// 其实在parser模块中, 已经有过相关的处理了, 即用结构体(docInfo) 成员为: title、content、url
// 不过, 在建立索引时, 文档在索引中 应该存在一个文档id.

// 正排索引结构
// 正排索引 可以通过文档id找到文件内容. 那么 正排索引可以用 vector 建立, vector 存储docInfo结构体 那么数组下标就天然是 文档id

// 倒排索引结构
// 倒排索引 需要通过关键字 找到包含关键字的文档id, 文档id 对应正排索引中的下标, 所以需要先建立正排索引, 再建立倒排索引
// 由于可能多个文档包含相同的关键字, 倒排索引更适合 keyword:value 结构存储. 所以 可以使用 unordered_map
// 并且, 同样因为关键字可能找到多个文档, value的类型就 可以是存储着文档id的vector, 称为倒排拉链

// 倒排索引中, 通过关键字找到的 倒排拉链中 不应该仅仅是文档id的数据.
// 因为倒排索引的查找结果是关乎到查找结果的显示顺序的. 所以 还需要知道对应文档id 在本次搜索的权重.
// 所以, 最好将文档id和权重结合起来, 构成一个结构体(invertedElem)存储.
// 不过, 不需要 先将所有文档的正排索引建立完成之后 再建立倒排索引. 可以先给 某文档建立正排索引之后, 直接对此文档建立倒排索引

#pragma once

#include <iostream>
#include <fstream>
#include <utility>
#include <vector>
#include <string>
#include <unordered_map>
#include <mutex>
#include "util.hpp"

namespace ns_index {

    // 用于正排索引中 存储文档内容
    typedef struct docInfo {
        std::string _title;   // 文档标题
        std::string _content; // 文档去标签之后的内容
        std::string _url;     // 文档对应官网url
        std::size_t _docId;   // 文档id
    } docInfo_t;

    // 用于倒排索引中 记录关键字对应的文档id和权重
    typedef struct invertedElem {
        std::size_t _docId;    // 文档id
        std::string _keyword;  // 关键字
        std::uint64_t _weight; // 搜索此关键字, 此文档id 所占权重

        invertedElem() // 权重初始化为0
            : _weight(0) {}
    } invertedElem_t;

    // 关键字的词频
    typedef struct keywordCnt {
        std::size_t _titleCnt;   // 关键字在标题中出现的次数
        std::size_t _contentCnt; // 关键字在内容中出现的次数

        keywordCnt()
            : _titleCnt(0)
            , _contentCnt(0) {}
    } keywordCnt_t;

    // 倒排拉链
    typedef std::vector<invertedElem_t> invertedList_t;

    class index {
    private:
        // 正排索引使用vector, 下标天然是 文档id
        std::vector<docInfo_t> forwardIndex;
        // 倒排索引 使用 哈希表, 因为倒排索引 一定是 一个keyword 对应一组 invertedElem拉链
        std::unordered_map<std::string, invertedList_t> invertedIndex;

        // 单例模式设计
        index() {}

        index(const index&) = delete;
        index& operator=(const index&) = delete;

        static index* _instance; // 单例
        static std::mutex _mtx;

    public:
        // 获取单例
        static index* getInstance() {
            if (nullptr == _instance) {
                _mtx.lock();
                if (nullptr == _instance) {
                    _instance = new index;
                }
                _mtx.unlock();
            }

            return _instance;
        }

        // 通过关键字 检索倒排索引, 获取对应的 倒排拉链
        invertedList_t* getInvertedList(const std::string& keyword) {
            // 先找 关键字 所在迭代器
            auto iter = invertedIndex.find(keyword);
            if (iter == invertedIndex.end()) {
                std::cerr << keyword << " have no invertedList!" << std::endl;
                return nullptr;
            }

            // 找到之后
            return &(iter->second);
        }

        // 通过倒排拉链中 每个倒排元素中存储的 文档id, 检索正排索引, 获取对应文档内容
        docInfo_t* getForwardIndex(std::size_t docId) {
            if (docId >= forwardIndex.size()) {
                std::cerr << "docId out range, error!" << std::endl;
                return nullptr;
            }

            return &forwardIndex[docId];
        }

        // 根据parser模块处理过的 所有文档的信息
        // 提取文档信息, 建立 正排索引和倒排索引
        // input 为 ./data/output/raw
        bool buildIndex(const std::string& input) {
            // 先以读取方式打开文件
            std::ifstream in(input, std::ios::in);
            if (!in.is_open()) {
                std::cerr << "Failed to open " << input << std::endl;
                return false;
            }

            std::size_t count = 0;

            std::string line;
            while (std::getline(in, line)) {
                // 按照parser模块的处理, getline 一次读取到的数据, 就是一个文档的: title\3content\3url\n
                docInfo_t* doc = buildForwardIndex(line); // 将一个文档的数据 建立到索引中
                if (nullptr == doc) {
                    std::cerr << "Failed to buildForwardIndex for " << line << std::endl;
                    continue;
                }

                // 文档建立正排索引成功, 接着就通过 doc 建立倒排索引
                if (!buildInvertedIndex(*doc)) {
                    std::cerr << "Failed to buildInvertedIndex for " << line << std::endl;
                    continue;
                }

                count++;
                if (count % 50 == 0)
                    std::cout << "当前已经建立的索引文档: " << count << std::endl;
            }

            return true;
        }

    private:
        // 对一个文档建立正排索引
        docInfo_t* buildForwardIndex(const std::string& file) {
            // 一个文档的 正排索引的建立, 是将 title\3content\3url (file) 中title content url 提取出来
            // 构成一个 docInfo_t doc
            // 然后将 doc 存储到正排索引vector中
            std::vector<std::string> fileResult;
            const std::string sep("\3");
            // stringUtil::split() 字符串通用工具接口, 分割字符串
            ns_util::stringUtil::split(file, &fileResult, sep);

            docInfo_t doc;
            doc._title = fileResult[0];
            doc._content = fileResult[1];
            doc._url = fileResult[2];

            // 因为doc是需要存储到 forwardIndex中的, 存储之前 forwardIndex的size 就是存储之后 doc所在的位置
            doc._docId = forwardIndex.size();

            forwardIndex.push_back(std::move(doc));

            return &forwardIndex.back();
        }

        // 对一个文档建立倒排索引
        // 倒排索引是用来通过关键词定位文档的.
        // 倒排索引的结构是 std::unordered_map<std::string, invertedList_t> invertedIndex;
        // keyword值就是关键字, value值则是关键字所映射到的文档的倒排拉链
        // 对一个文档建立倒排索引的原理是:
        //  1. 首先对文档的标题 和 内容进行分词, 并记录分词
        //  2. 分别统计整理标题分析的词频 和 内容分词的词频
        //     统计词频是为了可以大概表示关键字在文档中的 相关性.
        //     在本项目中, 可以简单的认为关键词在文档中出现的频率, 代表了此文档内容与关键词的相关性. 当然这是非常肤浅的联系, 一般来说相关性的判断都是非常复杂的. 因为涉及到词义 语义等相关分析.
        //     每个关键字 在标题中出现的频率 和 在内容中出现的频率, 可以记录在一个结构体中. 此结构体就表示关键字的词频
        //  3. 使用 unordered_map<std::string, wordCnt_t> 记录关键字与其词频
        //  4. 通过遍历记录关键字与词频的 unordered_map, 构建 invertedElem: _docId, _keyword, _weight
        //  5. 构建了关键字的invertedElem 之后, 再将关键词的invertedElem 添加到在 invertedIndex中 关键词的倒排拉链 invertedList中
        // 注意, 搜索引擎一般不区分大小写, 所以可以将分词出来的所有的关键字, 在倒排索引中均以小写的形式映射. 在搜索时 同样将搜索请求分词出的关键字小 写化, 在进行检索. 就可以实现搜索不区分大小写.

        // 关于分词 使用 cppjieba 中文分词库
        bool buildInvertedIndex(const docInfo_t& doc) {
            // 用来映射关键字 和 关键字的词频
            std::unordered_map<std::string, keywordCnt_t> keywordsMap;
            ns_util::jiebaUtil* jiebaIns = ns_util::jiebaUtil::getInstance();

            // 标题分词
            std::vector<std::string> titleKeywords;
            jiebaIns->cutStringNoStop(doc._title, &titleKeywords);
            // jiebaIns->cutString(doc._title, &titleKeywords);
            // 标题词频统计 与 转换 记录
            for (auto keyword : titleKeywords) {
                boost::to_lower(keyword);         // 关键字转小写
                keywordsMap[keyword]._titleCnt++; // 记录关键字 并统计标题中词频
                                                  // unordered_map 的 [], 是用来通过keyword值 访问value的. 如果keyword值已经存在, 则返回对应的value, 如果keyword值不存在, 则会插入keyword并创建对应的value
            }

            // 内容分词
            std::vector<std::string> contentKeywords;
            jiebaIns->cutStringNoStop(doc._content, &contentKeywords);
            // jiebaIns->cutString(doc._content, &contentKeywords);
            // 内容词频统计 与 转换 记录
            for (auto keyword : contentKeywords) {
                boost::to_lower(keyword);           // 关键字转小写
                keywordsMap[keyword]._contentCnt++; // 记录关键字 并统计内容中词频
            }

            // 这两个const 变量是用来计算 关键字在文档中的权重的.
            // 并且, 关键字出现在标题中  文档与关键字的相关性大概率是要高的, 所以 可以把titleWeight 设置的大一些
            const int titleWeight = 40;
            const int contentWeight = 1;
            // 分词并统计词频之后, keywordsMap 中已经存储的当前文档的所有关键字, 以及对应的在标题 和 内容中 出现的频率
            // 就可以遍历 keywordsMap 获取关键字信息, 构建 invertedElem 并添加到 invertedIndex中 关键词的倒排拉链 invertedList中了
            for (auto& keywordInfo : keywordsMap) {
                invertedElem_t item;
                item._docId = doc._docId;          // 本文档id
                item._keyword = keywordInfo.first; // 关键字
                item._weight = keywordInfo.second._titleCnt * titleWeight + keywordInfo.second._contentCnt * contentWeight;

                // 上面构建好了 invertedElem, 下面就要将 invertedElem 添加到对应关键字的 倒排拉链中, 构建倒排索引
                invertedList_t& list = invertedIndex[keywordInfo.first]; // 获取关键字对应的倒排拉链
                list.push_back(std::move(item));
            }

            return true;
        }
    };
    // 单例相关
    index* index::_instance = nullptr;
    std::mutex index::_mtx;
}

// 本文件实现 搜索相关接口

// 本项目中的搜索, 是根据输入的关键词:
//  1. 先对关键词进行分词
//  2. 然后通过分词, 在倒排索引中进行检索, 检索到相关的倒排拉链
//  3. 然后再通过倒排拉链中 倒排元素的对应文档id, 在正排索引中获取文件内容

// 不过在正式开始搜索之前, 要先构建索引
// 而索引的构建, 在整个程序中只需要构建一次, 所以可以将索引设计为单例模式
#pragma once

#include <algorithm>
#include <cctype>
#include <iostream>
#include <iterator>
#include <string>
#include <vector>
#include <unordered_map>
#include <algorithm>
#include <boost/algorithm/string.hpp>
#include <jsoncpp/json/json.h>
#include "util.hpp"
#include "index.hpp"

namespace ns_searcher {
    typedef struct invertedElemOut {
        std::size_t _docId;
        std::uint64_t _weight;
        std::vector<std::string> _keywords;
    } invertedElemOut_t;

    class searcher {
    private:
        ns_index::index* _index; // 建立索引的类

        ns_util::jiebaUtil* _jiebaIns;

    public:
        void initSearcher(const std::string& input) {
            // 搜索前的初始化操作
            // 获取单例
            _index = ns_index::index::getInstance();
            _jiebaIns = ns_util::jiebaUtil::getInstance();

            std::cout << "获取单例成功 ..." << std::endl;
            // 建立索引
            _index->buildIndex(input);
            std::cout << "构建正排索引、倒排索引成功 ..." << std::endl;
        }

        // 搜索接口
        // 搜索需要实现什么功能?
        // 首先参数部分需要怎么实现?
        // 参数部分, 需要接收需要搜索的句子或关键字, 还需要一个输出型参数 用于输出查找结果
        //  查找结果我们使用jsoncpp进行序列化和反序列化
        // search() 具体需要实现的功能:
        //  1. 对接收的句子或关键词进行分词
        //  2. 根据分词, 在倒排索引中查找到所有分词的倒排拉链 汇总 的 invertedElem, 并根据相关性进行排序
        //  4. 然后再遍历所有的 invertedElem, 根据 invertedElem中存储的 文档id, 在正排索引中获取到文档内容
        //  5. 然后将获取到的文档内容使用jsoncpp 进行序列化, 存储到输出型参数中
        // 直到遍历完invertedElem
        void search(const std::string& query, std::string* jsonString) {
            // 1. 对需要搜索的句子或关键词进行分词
            std::vector<std::string> keywords;

            _jiebaIns->cutString(query, &keywords);
            // _jiebaIns->cutStringNoStop(query, &keywords);
            // ns_util::jiebaUtil::cutString(query, &keywords);

            // std::vector<invertedElemOut_t> allInvertedElemOut;
            // std::vector<ns_index::invertedElem_t> allInvertedElem;

            // 统计文档用, 因为可能存在不同的分词 在倒排索引中指向同一个文档的情况
            // 如果不去重, 会重复展示
            // std::unordered_map<std::size_t, ns_index::invertedElem_t> invertedElemMap;
            std::unordered_map<std::size_t, invertedElemOut_t> invertedElemOutMap;
            // 2. 根据分词获取倒排索引中的倒排拉链, 并汇总去重 invertedElem
            for (std::string word : keywords) {
                boost::to_lower(word);

                ns_index::invertedList_t* tmpInvertedList = _index->getInvertedList(word);
                if (nullptr == tmpInvertedList) {
                    // 没有这个关键词
                    continue;
                }

                for (auto& elem : *tmpInvertedList) {
                    // 遍历倒排拉链, 根据文档id 对invertedElem 去重
                    auto& item = invertedElemOutMap[elem._docId]; // 在map中获取 或 创建对应文档id的 invertedElem
                    item._docId = elem._docId;
                    item._weight += elem._weight;
                    // 权重需要+= 是因为多个关键词指向了同一个文档 那么就说明此文档的与搜索内容的相关性更高
                    // 所以, 就可以将多个关键字关于此文档的权重相加, 表示搜索相关性高
                    // 最好还将 此文档相关的关键词 也存储起来, 因为在客户端搜索结果中, 需要对网页中有的关键字进行高亮
                    // 但是 invertedElem 的第三个成员是 单独的一个string对象, 不太合适
                    // 所以, 可以定义一个与invertedElem 相似的, 但是第三个成员是一个 vector 的类, 比如 invertedElemOut
                    item._keywords.push_back(elem._keyword);
                    // 此时就将当前invertedElem 去重到了 invertedElemMap 中
                }
            }

            // vector 存储 文档相关信息, 方便排序
            std::vector<invertedElemOut_t> allInvertedElemOut;
            // 出循环之后, 就将搜索到的 文档的 id、权重和相关关键词 存储到了 invertedElemMap
            // 然后将文档的相关信息 invertedElemOut 都存储到 vector 中
            for (const auto& elemOut : invertedElemOutMap) {
                // map中的second: elemOut, 在执行此操作之后, 就没用了
                // 所以使用移动语义, 防止发生拷贝
                allInvertedElemOut.push_back(std::move(elemOut.second));
            }

            // 执行到这里, 可以搜索到的文档id 权重 和 相关关键词的信息, 已经都在allInvertedElemOut 中了.
            // 但是, 还不能直接 根据文档id 在正排索引中检索
            // 因为, 此时如果直接进行文档内容的索引, 在找到文档内容之后, 就要直接进行序列化并输出了. 而客户端显示的时候, 反序列化出来的文档顺序, 就是显示的文档顺序
            // 但是现在找到的文档还是乱序的. 还需要将allInvertedElemOut中的相关文档, 通过_weight 进行倒序排列
            // 这样, 序列化就是按照倒序排列的, 反序列化也会如此, 显示同样如此
            std::sort(allInvertedElemOut.begin(), allInvertedElemOut.end(),
                      [](const invertedElemOut_t& elem1, const invertedElemOut_t& elem2) {
                          return elem1._weight > elem2._weight;
                      });

            // 排序之后, allInvertedElemOut 中文档的排序就是倒序了
            // 然后 通过遍历此数组, 获取文档id, 根据id获取文档在正排索引中的内容
            // 然后再将 所有内容序列化
            Json::Value root;
            for (auto& elemOut : allInvertedElemOut) {
                // 通过Json::Value 对象, 存储文档内容
                Json::Value elem;
                // 通过elemOut._docId 获取正排索引中 文档的内容信息
                ns_index::docInfo_t* doc = _index->getForwardIndex(elemOut._docId);
                // elem赋值
                elem["url"] = doc->_url;
                elem["title"] = doc->_title;
                // 关于文档的内容, 搜索结果中是不展示文档的全部内容的, 应该只显示包含关键词的摘要, 点进文档才显示相关内容
                // 而docInfo中存储的是文档去除标签之后的所有内容, 所以不能直接将 doc._content 存储到elem对应key:value中
                elem["desc"] = getDesc(doc->_content, elemOut._keywords[0]); // 只根据第一个关键词来获取摘要
                // for Debug
                // 这里有一个bug, jsoncpp 0.10.5.2 是不支持long或long long 相关类型的, 所以需要转换成 double
                // 这里转换成 double不会有什么影响, 因为这两个参数只是本地调试显示用的.
                elem["docId"] = (double)doc->_docId;
                elem["weight"] = (double)elemOut._weight;

                root.append(elem);
            }

            // 序列化完成之后将相关内容写入字符串
            // for Debug 用 styledWriter
            Json::StyledWriter writer;
            *jsonString = writer.write(root);
        }

        std::string getDesc(const std::string& content, const std::string& keyword) {
            // 如何获取摘要呢?
            // 我们尝试获取正文中 第一个keyword 的前50个字节和后100个字节的内容 作为摘要
            const std::size_t prevStep = 50;
            const std::size_t nextStep = 100;
            // 获取正文中 第一个 keyword 的位置

            // std::size_t pos = content.find(keyword);
            // if (pos == std::string::npos)
            //  return "keyword does not exist!";
            // 直接这样处理, 会出现一个问题:
            // keyword是有大小写的. 倒排索引中查找 我们实现的是忽略大小写, 所以可以找到文档
            // 而 string::find() 是区分大小写的查找, 可能无法在内容中找到对应的关键词
            // string容器也没有提供不区分大小写的查找方法
            // 此时, 可以用std::search()
            // std::search(it1, it2, it3, it4, pred);
            // 可以在[it1, it2)中 查找第一个[it3, it4)(词语)的出现位置.
            // 并且, 如果使用第5个参数, 就可以传入 带有两个参数的仿函数, 这两个参数就是需要比较的字符
            // 可以在仿函数内设置这两个字符的比较方式
            // 最终会返回找到的找到的单次第一个字符位置的迭代器, 否则返回it2

            auto iter = std::search(content.begin(), content.end(), keyword.begin(), keyword.end(),
                                    [](int x, int y) {
                                        return std::tolower(x) == std::tolower(y);
                                    });
            if (iter == content.end())
                return "keyword does not exist!";
            std::size_t pos = std::distance(content.begin(), iter);

            std::size_t begin = 0;
            std::size_t end = content.size() - 1;

            // 获取前50字节 和 后100字节的迭代器位置
            if (pos > begin + prevStep)
                begin += (pos - prevStep);
            if (pos + nextStep < end)
                end = pos + nextStep;

            if (begin >= end)
                return "nothing!";

            // 获取摘要
            std::string desc;
            if (pos <= begin + prevStep)
                desc = "...";
            desc += content.substr(begin, end - begin);
            if (pos + nextStep < end)
                desc += "...";

            return desc;
        }
    };
}