사용자 도구

사이트 도구


kb:slangfilter

욕설 필터링

온라인 게임을 제작하다보면 필히 만나는 문제 중에 하나가 욕설 필터링이다. 하지만 욕설 필터링이 게임에 큰 영향을 미쳐서는 안 되기 때문에 될 수 있는 한 컴팩트하고 빠르게 짜는 것이 좋다.

기본적인 아이디어는 각종 비속어 문자열을 트리로 만들자이다. 알다시피 문자열은 끝에 '0'이 붙은 바이트 값의 연속이다. 이 바이트 값을 이용해 가지를 만들어 나가는 방식으로 트리를 만들면 꽤 빠른 속도(O(N))로 비속어를 검색할 수 있다.

소스

SlangFilter.h
//////////////////////////////////////////////////////////////////////////////
/// \file SlangFilter.h
/// \author excel96
/// \date 2003.7.15
///
/// 비속어 필터링을 위한 모듈이다.
///
/// \todo 유니코드를 지원해야하는가...?
//////////////////////////////////////////////////////////////////////////////
 
#ifndef __SLANGFILTER_H__
#define __SLANGFILTER_H__
 
//////////////////////////////////////////////////////////////////////////////
/// \class SlangFilter
/// \brief 비속어 필터링 클래스
/// 
/// 이 클래스는 입력된 비속어를 트리로 만들어 가지고 있는다. 비속어 문자열의 
/// 한 바이트, 한 바이트가 노드를 이루게 된다. 예를 들어, "fuck"이란 단어와 
/// "fucking"이란 단어가 입력되었다면 대강 다음과 같은 모양을 가지게 된다.
///
/// <pre>
/// f(f) - u(f) - c(f) - k(t) - i(f) - n(f) - g(t)
/// </pre>
/// 
/// 옆의 f, t는 SlangNode 클래스의 bLeafNode 멤버 변수와 매치되는 값인데,
/// t일 때, 이 노드가 한 단어의 끝임을 말한다. 즉 fuck이란 단어도 있고,
/// "fucking"이란 단어도 있음을 말한다. 위의 트리에 "fox"란 단어도 비속어로
/// 입력되었다면 다음과 같은 모양이 될 것이다.
///
/// <pre>
/// f(f) + u(f) - c(f) - k(t) - i(f) - n(f) - g(t)
///      |
///      + o(f) - x(t)
/// </pre>
/// 
/// 이런 식으로 트리를 구성해두면, 비속어 데이터베이스가 아무리 커도
/// 비속어 포함 여부를 문자열 길이의 O(N)으로 검사할 수 있다.
//////////////////////////////////////////////////////////////////////////////
 
class SlangFilter
{
private:
    struct IMPL;
    IMPL* m_pImpl; ///< 내부 데이터 PIMPL
 
 
public:
    SlangFilter(); /// 생성자
    ~SlangFilter(); /// 소멸자
 
 
public:
    /// \brief 비속어를 '*'로 치환한 문장을 리턴한다.
    std::string filter(const std::string& original) const;
 
    /// \brief 해당하는 문장이 비속어를 포함하고 있는지의 여부를 리턴한다.
    bool hasSlang(const std::string& original) const;
 
    /// \brief 비속어를 추가한다.
    void addSlang(const std::string& slang);
 
 
private:
    /// \brief 해당하는 문장의 첫 바이트부터 비속어가 포함되어있는지 검사한다.
    size_t match(const std::string& text) const;
 
    /// \brief 해당하는 글자가 문장 부호인지 검사한다.
    bool isPunctutation(char c) const;
};
 
#endif //__SLANGFILTER_H__
SlangFilter.cpp
//////////////////////////////////////////////////////////////////////////////
/// \file SlangFilter.cpp
/// \author excel96
/// \date 2003.7.15
///
/// 비속어 필터링을 위한 모듈이다.
//////////////////////////////////////////////////////////////////////////////
 
#include "SlangFilter.h"
#include "FunctionObject.h"
 
//////////////////////////////////////////////////////////////////////////////
/// \class SlangNode
/// \brief 비속어 트리를 구성하는 노드 클래스.
///
/// 자식 노드의 구분은 비트값으로 이루어진다.
//////////////////////////////////////////////////////////////////////////////
 
class SlangNode : public stdext::hash_map<size_t, SlangNode*>
{
DECLARE_NONCOPYABLE(SlangNode)
 
private:
    bool m_bLeafNode; ///< 이 노드가 단어의 끝이 될 수 있는가?
 
 
public:
    /// \brief 생성자
    SlangNode() : m_bLeafNode(false) {}
 
    /// \brief 소멸자
    ~SlangNode() { 
        /* 모든 자식 노드를 삭제 */
        DESTROY_ALL_OBJECT_2((*this));  
    }
 
 
public:
    /// \brief 비트값을 이용해 해당하는 자식 노드를 찾는다.
    /// \param idx 찾고자 하는 자식 노드의 비트값
    /// \return SlangNode* 해당하는 자식 노드가 존재할 경우 그 노드의 
    /// 포인터를 반환하고, 존재하지 않을 경우 NULL을 반환한다.
    SlangNode* findChild(size_t idx) const
    {
        Assert(idx < 256);
        const_iterator itr(find(idx));
        return itr != end() ? itr->second : NULL;
    }
 
    /// \brief 해당하는 비트값의 자식 노드를 추가한다.
    /// \param idx 추가하고자 하는 자식 노드의 비트값
    /// \return SlangNode* 새로 생성한 자식 노드의 포인터
    SlangNode* addChild(size_t idx)
    {
        Assert(idx < 256);
 
        // 해당하는 자식이 없을 경우, 새로운 노드를 생성해서 추가한다.
        iterator itr(find(idx));
        if (itr == end()) itr = insert(value_type(idx, new SlangNode)).first;
 
        return itr->second;
    }
 
    /// \name 단어의 끝 여부를 반환/설정
    /// \{ 
    bool isLeafNode() const { return m_bLeafNode; }
    void setLeafNode(bool value) { m_bLeafNode = value; }
    /// \} 
};
 
 
//////////////////////////////////////////////////////////////////////////////
/// \struct SlangFilter::IMPL
/// \brief SlangFilter 클래스 내부 데이터 구조체
//////////////////////////////////////////////////////////////////////////////
struct SlangFilter::IMPL
{
    SlangNode* pRoot; ///< 최상위 노드
 
    static const string s_Punctuations; ///< 문장 부호들
 
    IMPL() : pRoot(new SlangNode) { AssertPtr(pRoot); }
    ~IMPL() { SAFE_DELETE(pRoot); }
};
 
/// 문장 부호들
const string SlangFilter::IMPL::s_Punctuations = " `~!@#$%^&*()-_=+\\|[{]};:'\",<.>/?";
 
 
//////////////////////////////////////////////////////////////////////////////
/// \brief 생성자
//////////////////////////////////////////////////////////////////////////////
SlangFilter::SlangFilter()
: m_pImpl(new IMPL)
{
}
 
//////////////////////////////////////////////////////////////////////////////
/// \brief 소멸자
//////////////////////////////////////////////////////////////////////////////
SlangFilter::~SlangFilter()
{
    SAFE_DELETE(m_pImpl);
}
 
//////////////////////////////////////////////////////////////////////////////
/// \brief 비속어를 '*'로 치환한 문장을 리턴한다.
/// 
/// \param original 원래 문장
/// \return std::string 비속어가 '*'로 치환된 문장
//////////////////////////////////////////////////////////////////////////////
std::string SlangFilter::filter(const std::string& original) const
{
    std::string text(original);
 
    for (size_t i=0; i<original.size();)
    {
        size_t size = match(original.substr(i, original.size() - i));
        if (size > 0)
        {
            text.replace(i, size, std::string(size, '*'));
            i += size;
        }
        else
        { 
            // 현재 지점에서 비속어가 발견되지 않았을 때, 
            // 한글이라면 2바이트씩, 아니라면 1바이트씩 넘어간다.
            i += original[i] & 0x80 ? 2 : 1;
        }
    }
 
    return text;
}
 
//////////////////////////////////////////////////////////////////////////////
/// \brief 해당하는 문장이 비속어를 포함하고 있는지의 여부를 리턴한다.
/// 
/// \param original 조사하고자하는 문장
/// \return bool 비속어를 포함하고 있을 경우 true를 반환한다.
//////////////////////////////////////////////////////////////////////////////
bool SlangFilter::hasSlang(const std::string& original) const
{
    for (size_t i=0; i<original.size(); i++)
    {
        if (match(original.substr(i, original.size() - i)) > 0)
            return true;
    }
 
    return false;
}
 
//////////////////////////////////////////////////////////////////////////////
/// \brief 비속어를 추가한다.
/// \param slang 비속어에는 문장 부호가 포함되어 있지 않아야 한다.
//////////////////////////////////////////////////////////////////////////////
void SlangFilter::addSlang(const std::string& slang)
{
    // 단어의 길이는 256바이트로 제한. 특별한 이유는 없다. 그냥 256바이트를 
    // 넘어가는 욕은 입력 자체가 뭔가 꼬인 거라고 생각했기 때문이다.
    // 또한 단어에 문장부호가 포함되어 있는 경우에는 추가하지 않는다.
    // match() 함수를 보면, 알겠지만 문장 부호는 비교 대상으로 취급하지 않기
    // 위해서이다. (예를 들어 "바...보" 같은 욕을 검출하기 위해!)
    if (slang.size() > 256 ||
        slang.find_first_of(IMPL::s_Punctuations) != std::string::npos)
        return;
 
    // char를 size_t로 바로 변환시키면 음수값일 경우 콩가루 변환이 일어난다.
    // 어쩔 수 없이 unsigned char로 먼저 변환한 뒤에 size_t로 변환시킨다.
    unsigned char buf[256+1] = {0, };
    _snprintf((char*)buf, sizeof(buf)-1, "%s", slang.c_str());
    buf[sizeof(buf)-1] = 0;
 
    // 단어의 모든 바이트를 iteration하면서, 그에 따른 트리를 생성한다.
    SlangNode* pCurrent = m_pImpl->pRoot;
    for (size_t i=0; i<slang.size(); i++)
    {
        // 자식 노드를 추가
        pCurrent = pCurrent->addChild((size_t)buf[i]);
    }
 
    // 단어의 끝이 되는 노드는 flag로 표시를 해두어야한다.
    pCurrent->setLeafNode(true);
}
 
//////////////////////////////////////////////////////////////////////////////
/// \brief 해당하는 문장의 첫 바이트부터 비속어가 포함되어있는지 검사한다.
/// \param text 검사하고자 하는 문장.
/// \return size_t 비속어가 포함되어 있을 경우에는 그 비속어의 길이를 
/// 리턴한다. 포함되어 있지 않을 경우에는 0을 리턴한다.
//////////////////////////////////////////////////////////////////////////////
size_t SlangFilter::match(const std::string& text) const
{
    if (text.empty()) return 0;
    if (isPunctutation(text[0])) return 0;
 
    SlangNode* pCurrent = m_pImpl->pRoot;
    size_t i = 0;
 
    while (i < text.size())
    {
        // 현재 바이트가 문장 부호일 경우에는 그냥 continue한다.
        // 비속어 사이사이에 문장 부호를 넣은 경우를 검색하기 위해서이다.
        if (isPunctutation(text[i]))
        {
            i++;
            continue;
        }
 
        // 자식 노드 중에 현재 바이트와 일치하는 값으로 이어지는 것을 찾는다.
        size_t idx = (size_t)((unsigned char)text[i]);
        pCurrent = pCurrent->findChild(idx);
 
        // 더 이상 이어지는 노드가 없다는 말은 현재의 바이트들과 일치하는
        // 단어가 노드 트리 상에 존재하지 않는다는 말이다.
        if (pCurrent == NULL) return 0;
 
        // 필터링해야하는 단어다!
        if (pCurrent->isLeafNode()) return i + 1;
 
        i++;
    }
 
    return 0;
}
 
//////////////////////////////////////////////////////////////////////////////
/// \brief 해당하는 글자가 문장 부호인지 검사한다.
/// \param c 검사하려는 글자
/// \return bool 해당하는 글자가 문장 부호일 경우에는 true를 반환한다.
//////////////////////////////////////////////////////////////////////////////
bool SlangFilter::isPunctutation(char c) const
{
    return IMPL::s_Punctuations.find(c) != std::string::npos;
}

kb/slangfilter.txt · 마지막으로 수정됨: 2014/11/08 13:38 (바깥 편집)