淺析過濾敏感詞過濾算法(C++)

本文轉自淺析敏感詞過濾算法(C++)，自己也在其基礎上根據自己的情況做了一點修改。

為了提高查找效率，這裡将敏感詞用樹形結構存儲，每個節點有一個map成員，其映射關系為一個string對應一個WordNode。

比如敏感詞庫裡面有槍手、手槍、槍支彈藥這幾個詞，讀入後就變成了如下圖所示的樹狀結構。

STL::map是按照operator<比較判斷元素是否相同，以及比較元素的大小，然後選擇合适的位置插入到樹中。

下面主要實作了WordNode類，進行節點的插入以及查詢。

WordNode.h

class WordNode
{
private:
    friend class WordTree;
    typedef map<string, WordNode> _TreeMap;
    typedef map<string, WordNode>::iterator _TreeMapIterator;

    string m_character;
    _TreeMap m_map;
    WordNode* m_parent;

public:
    WordNode(string character);
    WordNode(){
        m_character = "";
    };
    string getCharacter() const{ return m_character; };
    WordNode* findChild(string& nextCharacter);
    WordNode* insertChild(string& nextCharacter);
};
           

WordNode.cpp

WordNode::WordNode(string character){
    if (character.size() == PACE)
    {
        m_character.assign(character);
    }
    else
        cout << "error" << endl;
}

WordNode* WordNode::findChild(string& nextCharacter){
    _TreeMapIterator TreeMapIt = m_map.find(nextCharacter);
    if (TreeMapIt == m_map.end())
    {
        return NULL;
    }
    else
    {
        return &TreeMapIt->second;
    }
}

WordNode* WordNode::insertChild(string& nextCharacter){
    if (!findChild(nextCharacter))
    {
        m_map.insert(pair<string,WordNode>(nextCharacter, WordNode(nextCharacter)));
        return &(m_map.find(nextCharacter)->second);
    }
    return NULL;
}
           

另外，

這裡的PACE原本是2，因為一個GBK漢字占兩個字元，而且原文中也說了如果需要考慮英文或中英文結合的情況，将PACE改為１。

不過我試過之後，覺得不管是中文、英文還是中英文，PACE為 1 都适用，結果都沒錯，隻不過中文的情況下每個節點的string都不再是一個完整的漢字，而是漢字的一個字元。

接下來實作這個tree，在建立WordNode樹時，以parent為根節點建立，一開始parent為m_emptyRoot，然後keyword按照規則添加到樹中，假設一開始m_emptyRoot為空，keyword為”敏感詞”，則會以”敏感詞”為一條分支建立成為一顆樹枝’敏’->’感’->’詞’,此後，若想再添加”敏感度”，由于”敏感詞”與”敏感度”的前兩個字相同，則會在’敏’->’感’->’詞’的基礎上，從字’感’開始新生長出一顆分支，即’敏’->’感’->’度’,這兩顆分支共用’敏’->’感’。

下面代碼實作了WordTree類，進行樹的構成及查詢。

WordTree.h

class WordTree
{
public:
    int count;
    WordNode* insert(string &keyword);
    WordNode* insert(const char* keyword);
    WordNode* find(string& keyword);
    WordTree(){ count = ; };

private:
    WordNode m_emptyRoot;
    int m_pace;
    WordNode* insert(WordNode* parent, string& keyword);
    WordNode* insertBranch(WordNode* parent, string& keyword);
    WordNode* find(WordNode* parent, string& keyword);
};
           

WordTree.cpp

WordNode* WordTree::insert(string &keyword){
    return insert(&m_emptyRoot, keyword);
}

WordNode* WordTree::insert(const char* keyword){
    string wordstr(keyword);
    return insert(wordstr);
}

WordNode* WordTree::find(string& keyword){
    return find(&m_emptyRoot,keyword);
}

WordNode* WordTree::insert(WordNode* parent, string& keyword){
    if (keyword.size() == )
    {
        return NULL;
    }
    string firstChar = keyword.substr(, PACE);
    WordNode* firstNode = parent->findChild(firstChar);
    if (firstNode == NULL)
    {
        return insertBranch(parent,keyword);
    }
    string restChar = keyword.substr(PACE, keyword.size());
    return insert(firstNode, restChar);
}

WordNode* WordTree::insertBranch(WordNode* parent, string& keyword){
    string firstChar = keyword.substr(, PACE);
    WordNode* firstNode = parent->insertChild(firstChar);
    if (firstNode != NULL)
    {
        string restChar = keyword.substr(PACE, keyword.size());
        if (!restChar.empty())
        {
            return insertBranch(firstNode, restChar);
        }
    }
    return NULL;
}

WordNode* WordTree::find(WordNode* parent, string& keyword){
    string firstChar = keyword.substr(, PACE);
    WordNode* firstNode = parent->findChild(firstChar);
    if (firstNode==NULL)
    {
        count = ;
        return NULL;
    }
    string restChar = keyword.substr(PACE, keyword.size());
    if (firstNode->m_map.empty())
    {
        return firstNode;
    }
    if (keyword.size()==PACE)
    {
        return NULL;
    }
    count++;
    return find(firstNode, restChar);
}
           

最後就是利用上述的Tree來實作敏感詞過濾，WordFilter::censor(string &source) 函數用來進行敏感詞過濾，source即輸入的字元串，如果source包含敏感詞，則用“**”替代掉。

WordFilter::load(const char* filepath) 函數通過檔案載入敏感詞，并建構WordTree，這裡我用的是txt檔案。

下面實作了WordFilter類。

WordFilter.h

class WordFilter
{
public:
    static WordFilter* pInstace;
    static WordFilter* sharedInstace();
    static void release();
private:
    WordTree m_tree;

public:
    void load(const char* filepath);
    void censor(string &source);
};
           

WordFilter.cpp

WordFilter* WordFilter::sharedInstace(){
    if (pInstace)
    {
        return pInstace;
    }
    pInstace = new WordFilter;
    return pInstace;
}
void WordFilter::release(){
    if (pInstace)
    {
        delete pInstace;
    }
    pInstace = NULL;
}

void WordFilter::load(const char* filepath){
    ifstream infile(filepath, ios::in);

    if (!infile)
    {
        cout << "open file error" << endl;
    }
    else
    {
        cout << "open file succeed" << endl;
        string read;
        while (getline(infile, read))
        {
#if (CC_TARGET_PLATFORM == CC_PLATFORM_ANDROID || CC_TARGET_PLATFORM == CC_PLATFORM_IOS)
            string s;
            s = read.substr(, read.length() - );
            m_tree.insert(s);
#endif
        }
    }

    infile.close();
}

void WordFilter::censor(string &source){
    int lenght = source.size();
    for (int i = ; i < lenght; i += )
    {
        string substring = source.substr(i, lenght - i);
        if (m_tree.find(substring) != NULL)
        {
            source.replace(i, (m_tree.count+), "**");
            lenght = source.size();
            cout << "source = " <<  source << endl;
        }
    }
}
           

這裡說明一點，本人是做Cocos2d-x手遊用戶端開發的，程式是要移植到安卓或者iOS平台上。當逐行讀取txt檔案中的敏感詞并構成樹的時候，getline(infile, read)函數得到的read字元串後面帶有結束符，比如“槍手\0”，這時跟我們需要檢測的字元串“…槍手…”就明顯不符合，這是檢測不出來的。這種情況我現在隻知道在安卓或者iOS平台存在，而在windows環境下VS中是不會出現這種問題的。是以我對讀取到的字元串做了處理，把最後一個字元也就是結束符去掉，再進行下一步操作。