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)