1 개요
온라인 게임을 제작하다보면 필히 만나는 문제 중에 하나가 욕설 필터링이다. 하지만 욕설 필터링이 게임에 큰 영향을 미쳐서는 안 되기 때문에 될 수 있는 한 컴팩트하고 빠르게 짜는 것이 좋다.
기본적인 아이디어는 각종 비속어 문자열을 트리로 만들자이다. 알다시피 문자열은 끝에 '0'이 붙은 바이트 값의 연속이다. 이 바이트 값을 이용해 가지를 만들어 나가는 방식으로 트리를 만들면 꽤 빠른 속도(O(N))로 비속어를 검색할 수 있다.
2 소스
//////////////////////////////////////////////////////////////////////////////
/// \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;
}
SeriousMoin v1 (koMoinMoin 1.0a4 Modified)
