사용자 도구

사이트 도구


kb:slangfilter

차이

문서의 선택한 두 판 사이의 차이를 보여줍니다.

차이 보기로 링크

kb:slangfilter [2014/11/08 13:38] (현재)
줄 1: 줄 1:
 +====== 욕설 필터링 ======
 +온라인 게임을 제작하다보면 필히 만나는 문제 중에 하나가 욕설 필터링이다. 하지만 욕설 필터링이 게임에 큰 영향을 미쳐서는 안 되기 때문에 될 수 있는 한 컴팩트하고 빠르게 짜는 것이 좋다.
 +
 +기본적인 아이디어는 각종 비속어 문자열을 트리로 만들자이다. 알다시피 문자열은 끝에 '​0'​이 붙은 바이트 값의 연속이다. 이 바이트 값을 이용해 가지를 만들어 나가는 방식으로 트리를 만들면 꽤 빠른 속도(O(N))로 비속어를 검색할 수 있다.
 +
 +
 +====== 소스 ======
 +<file cpp 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__
 +</​file>​
 +
 +<file cpp 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;​
 +}
 +</​file>​
 +
 +----
 +  * see also [[SuffixTree]]
  
kb/slangfilter.txt · 마지막으로 수정됨: 2014/11/08 13:38 (바깥 편집)