勤能补拙,Expter

成都游戏Coder,记录游戏开发过程的笔记和心得!

一个关键字过滤算法

      经常某些论坛,或者软件中对某些字符串进行了关键字过滤, 一般代替为*号,一般的算法是利用strstr算法,即使是string的find子串算法复杂度也是(N*log(n)),并非kmp算法,也非bm查找子串算法。
     对于一组关键字过滤,特别是对于一组字符串多,且长度不规律的字符串过滤算法完全是有必要的。
   
    网上对于关键字过滤算法较多,且实现方法较多,本文主要介绍基于一种把关键字转换为Unicode,然后对关键字的字符或者单个关键字hash求值。算法复杂度为O(n).
   对于汉字的hash值的求法,因为是Unicode编码是16位,哈希求值:

  /// 求汉字的哈希值
long HashFun(wchar_t  word)
{
 BYTE l 
= LOBYTE(word);
 
int  h = HIBYTE(word);

 
long num = h << 8 ;
 num 
+=l;
 
return num;
}



    基本算法思想;
   1.建立2个过滤关键字数组:数组1:为单个字符  数组2:为2个或者多个字符
   2.求出数组1,2的hash值,数组2的hash值只求出前2个字符的hash值即可。
   3.扫描待检测的文本,然后每次取2个字符,查找数组2是否有匹配,如果没有则查找数组1。。。。  查找为O(1)

  主要代码如下:


/*
   File :  WordFilter.cpp 
   brief:  关键字过滤程序,复杂度为O(n),线性
   Author: Expter
   Data  : 2009/06/30

   对汉字或者字符进行哈希算法,先转换为unicode编码,然后求其hash值。

   主要算法为:
   1.建立2个过滤关键字数组:数组1:为单个字符  数组2:为2个或者多个字符
   2.求出数组1,2的hash值,数组2的hash值只求出前2个字符的hash值即可。
   3.扫描待检测的文本,然后每次取2个字符,查找数组2是否有匹配,如果没有则查找数组1。。。。  查找为O(1)


   不足:
   不能很好的分词。过滤不是很准确,每次只能1,2个词的过滤。
*/

#include 
<stdlib.h>
#include 
<iostream>
#include 
<map>
#include 
<vector>
#include 
<string>
#include 
<windows.h>
#include 
<wchar.h>  
#include 
<iosfwd>
using namespace std;

wchar_t des1 [
5][2= { L"",L"",L"",L"",L""};
wchar_t des2 [
3][5= { L"用汉", L"的啥" ,L"测试啊"};
wchar_t src[]  
= { L"这个原来是打算的啥子东西用汉字只是一个是不是测试"};


/// 求汉字的哈希值
long HashFun(wchar_t  word)
{
    BYTE l 
= LOBYTE(word);
    
int  h = HIBYTE(word);

    
long num = h << 8 ;
    num 
+=l;
    
return num;
}


long HashFun(wchar_t * word)
{
    
return HashFun(word[0])*10 + HashFun(word[1]);
}



void  ParamVer(map<long,int> hashmp , wchar_t *src , int i)
{
    
long val = HashFun(src[i+1]);
    
if(hashmp[val] == 1)
    
{
        src[i
+1= L'*';
    }

}

void  VmAlorgthm(map<long,int> hashmp,wchar_t *src)
{
    
long val = 0;
    
int  m = wcslen(src) ;
    
// O(n);
    for(int i = 0 ; i < m-1  ; i ++)
    
{
        
if( HashFun(src[i]) != L'*')
        
{
            val 
= HashFun(src[i]) + HashFun(src[i+1]);
            
if( hashmp[val] == 1)
            
{
                src[i] 
= L'*';
                src[i
+1=L'*';
            }

            
else
            
{
                val 
= HashFun(src[i]);
                
if(hashmp[val] == 1)
                
{
                    src[i] 
= L'*';
                }

                
else
                
{
                    ParamVer(hashmp,src,i);
                }

            }

        }

        
else
        
{
            ParamVer(hashmp,src,i
+1);
        }

    }

    ParamVer(hashmp,src,m
-1);
}



int _tmain(int argc, _TCHAR* argv[])
{
    wcout.imbue(locale(
"chs"));     
    typedef map
<long,int> HASHMAP;

    cout 
<<" 需要过滤文本: ";
    wcout
<< src <<endl;
    cout 
<<" 过滤关键字 : " ;
    
for(int i = 0 ;i < 5; i++)
        wcout 
<< des1[i][0<<" ";
    wcout 
<<endl;
    cout 
<<" 过滤关键词 : " ;
    
for(int i = 0 ;i < 3; i++)
        wcout 
<< des2[i] <<" ";
    wcout 
<<endl;

    
long  val = 0;

    HASHMAP hash_map;
    
/// 字 hash
    for(int i = 0 ; i < 5 ; i++)
    
{
        val 
= HashFun(des1[i][0]);
        hash_map[val] 
= 1;
    }

    
/// 词 hash
    for(int i =0 ; i < 3 ; i++)
    
{
        val 
= HashFun(des2[i]);
        hash_map[val] 
= 1;
    }

    
    VmAlorgthm(hash_map,src);
    
    cout 
<<"\n-------------------------------------------------------------\n"
        
<<" 过滤后的文本: ";
    wcout
<< src <<endl;

    
return 0;
}

posted on 2009-07-12 22:07 expter 阅读(4056) 评论(4)  编辑 收藏 引用 所属分类: 其他学习笔记算法与数据结构

评论

# re: 一个关键字过滤算法[未登录] 2009-07-13 11:33 megax

用hash,对于词组来说本身就有不确定性  回复  更多评论   

# re: 一个关键字过滤算法 2009-07-14 00:42 XXOO

我一般是先把词组排序,然后对每个字进行二分法这样。或者也可以HASH
  回复  更多评论   

# re: 一个关键字过滤算法 2009-07-14 12:37 戴尔电脑

看了有点帮助!!  回复  更多评论   

# re: 一个关键字过滤算法[未登录] 2009-07-20 09:10 cc

你这个hashfun有干活吗?传进去的值没有变化啊  回复  更多评论   


只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理