time 
设为首页】【收藏本站
当前位置: 主页 > 程序设计 > C\C++\VC > C语言 > 一个关键字过滤算法

一个关键字过滤算法

时间:2009-09-20 23:31 点击:563次 字体:[ ]




    经常某些论坛,或者软件中对某些字符串进行了关键字过滤, 一般代替为*号,一般的算法是利用strstr算法,即使是string的find子串算法复杂度也是(N*log(n)),并非kmp算法,也非bm查找子串算法。

    对于一组关键字过滤,特别是对于一组字符串多,且长度不规律的字符串过滤算法完全是有必要的。

    网上对于关键字过滤算法较多,且实现方法较多,本文主要介绍基于一种把关键字转换为Unicode,然后对关键字的字符或者单个关键字hash求值。算法复杂度为O(n)。

    对于汉字的hash值的求法,因为是Unicode编码是16位,哈希求值:

一个关键字过滤算法_www.fengfly.com  /// 求汉字的哈希值
一个关键字过滤算法_www.fengfly.comlong HashFun(wchar_t  word)
一个关键字过滤算法_www.fengfly.com
{
一个关键字过滤算法_www.fengfly.com BYTE l 
= LOBYTE(word);
一个关键字过滤算法_www.fengfly.com 
int  h = HIBYTE(word);
一个关键字过滤算法_www.fengfly.com
一个关键字过滤算法_www.fengfly.com 
long num = h << 8 ;
一个关键字过滤算法_www.fengfly.com num 
+=l;
一个关键字过滤算法_www.fengfly.com 
return num;
一个关键字过滤算法_www.fengfly.com}

    基本算法思想;

    1.建立2个过滤关键字数组:数组1:为单个字符  数组2:为2个或者多个字符2.求出数组1,2的hash值,数组2的hash值只求出前2个字符的hash值即可。

    3.扫描待检测的文本,然后每次取2个字符,查找数组2是否有匹配,如果没有则查找数组1……  查找为O(1)

    主要代码如下:

一个关键字过滤算法_www.fengfly.com
一个关键字过滤算法_www.fengfly.com
/*
一个关键字过滤算法_www.fengfly.com   File :  WordFilter.cpp 
一个关键字过滤算法_www.fengfly.com   brief:  关键字过滤程序,复杂度为O(n),线性
一个关键字过滤算法_www.fengfly.com   Author: Expter
一个关键字过滤算法_www.fengfly.com   Data  : 2009/06/30
一个关键字过滤算法_www.fengfly.com
一个关键字过滤算法_www.fengfly.com   对汉字或者字符进行哈希算法,先转换为unicode编码,然后求其hash值。
一个关键字过滤算法_www.fengfly.com
一个关键字过滤算法_www.fengfly.com   主要算法为:
一个关键字过滤算法_www.fengfly.com   1.建立2个过滤关键字数组:数组1:为单个字符  数组2:为2个或者多个字符
一个关键字过滤算法_www.fengfly.com   2.求出数组1,2的hash值,数组2的hash值只求出前2个字符的hash值即可。
一个关键字过滤算法_www.fengfly.com   3.扫描待检测的文本,然后每次取2个字符,查找数组2是否有匹配,如果没有则查找数组1。。。。  查找为O(1)
一个关键字过滤算法_www.fengfly.com
一个关键字过滤算法_www.fengfly.com
一个关键字过滤算法_www.fengfly.com   不足:
一个关键字过滤算法_www.fengfly.com   不能很好的分词。过滤不是很准确,每次只能1,2个词的过滤。
一个关键字过滤算法_www.fengfly.com
*/

一个关键字过滤算法_www.fengfly.com#include 
<stdlib.h>
一个关键字过滤算法_www.fengfly.com#include 
<iostream>
一个关键字过滤算法_www.fengfly.com#include 
<map>
一个关键字过滤算法_www.fengfly.com#include 
<vector>
一个关键字过滤算法_www.fengfly.com#include 
<string>
一个关键字过滤算法_www.fengfly.com#include 
<windows.h>
一个关键字过滤算法_www.fengfly.com#include 
<wchar.h>  
一个关键字过滤算法_www.fengfly.com#include 
<iosfwd>
一个关键字过滤算法_www.fengfly.com
using namespace std;
一个关键字过滤算法_www.fengfly.com
一个关键字过滤算法_www.fengfly.comwchar_t des1 [
5][2= { L"",L"",L"",L"",L""};
一个关键字过滤算法_www.fengfly.comwchar_t des2 [
3][5= { L"用汉", L"的啥" ,L"测试啊"};
一个关键字过滤算法_www.fengfly.comwchar_t src[]  
= { L"这个原来是打算的啥子东西用汉字只是一个是不是测试"};
一个关键字过滤算法_www.fengfly.com
一个关键字过滤算法_www.fengfly.com
一个关键字过滤算法_www.fengfly.com
/// 求汉字的哈希值
一个关键字过滤算法_www.fengfly.comlong HashFun(wchar_t  word)
一个关键字过滤算法_www.fengfly.com
{
一个关键字过滤算法_www.fengfly.com    BYTE l 
= LOBYTE(word);
一个关键字过滤算法_www.fengfly.com    
int  h = HIBYTE(word);
一个关键字过滤算法_www.fengfly.com
一个关键字过滤算法_www.fengfly.com    
long num = h << 8 ;
一个关键字过滤算法_www.fengfly.com    num 
+=l;
一个关键字过滤算法_www.fengfly.com    
return num;
一个关键字过滤算法_www.fengfly.com}

一个关键字过滤算法_www.fengfly.com
一个关键字过滤算法_www.fengfly.com
long HashFun(wchar_t * word)
一个关键字过滤算法_www.fengfly.com
{
一个关键字过滤算法_www.fengfly.com    
return HashFun(word[0])*10 + HashFun(word[1]);
一个关键字过滤算法_www.fengfly.com}

一个关键字过滤算法_www.fengfly.com
一个关键字过滤算法_www.fengfly.com
一个关键字过滤算法_www.fengfly.com
void  ParamVer(map<long,int> hashmp , wchar_t *src , int i)
一个关键字过滤算法_www.fengfly.com
{
一个关键字过滤算法_www.fengfly.com    
long val = HashFun(src[i+1]);
一个关键字过滤算法_www.fengfly.com    
if(hashmp[val] == 1)
一个关键字过滤算法_www.fengfly.com    
{
一个关键字过滤算法_www.fengfly.com        src[i
+1= L'*';
一个关键字过滤算法_www.fengfly.com    }

一个关键字过滤算法_www.fengfly.com}

一个关键字过滤算法_www.fengfly.com
void  VmAlorgthm(map<long,int> hashmp,wchar_t *src)
一个关键字过滤算法_www.fengfly.com
{
一个关键字过滤算法_www.fengfly.com    
long val = 0;
一个关键字过滤算法_www.fengfly.com    
int  m = wcslen(src) ;
一个关键字过滤算法_www.fengfly.com    
// O(n);
一个关键字过滤算法_www.fengfly.com
    for(int i = 0 ; i < m-1  ; i ++)
一个关键字过滤算法_www.fengfly.com    
{
一个关键字过滤算法_www.fengfly.com        
if( HashFun(src[i]) != L'*')
一个关键字过滤算法_www.fengfly.com        
{
一个关键字过滤算法_www.fengfly.com            val 
= HashFun(src[i]) + HashFun(src[i+1]);
一个关键字过滤算法_www.fengfly.com            
if( hashmp[val] == 1)
一个关键字过滤算法_www.fengfly.com            
{
一个关键字过滤算法_www.fengfly.com                src[i] 
= L'*';
一个关键字过滤算法_www.fengfly.com                src[i
+1=L'*';
一个关键字过滤算法_www.fengfly.com            }

一个关键字过滤算法_www.fengfly.com            
else
一个关键字过滤算法_www.fengfly.com            
{
一个关键字过滤算法_www.fengfly.com                val 
= HashFun(src[i]);
一个关键字过滤算法_www.fengfly.com                
if(hashmp[val] == 1)
一个关键字过滤算法_www.fengfly.com                
{
一个关键字过滤算法_www.fengfly.com                    src[i] 
= L'*';
一个关键字过滤算法_www.fengfly.com                }

一个关键字过滤算法_www.fengfly.com                
else
一个关键字过滤算法_www.fengfly.com                
{
一个关键字过滤算法_www.fengfly.com                    ParamVer(hashmp,src,i);
一个关键字过滤算法_www.fengfly.com                }

一个关键字过滤算法_www.fengfly.com            }

一个关键字过滤算法_www.fengfly.com        }

一个关键字过滤算法_www.fengfly.com        
else
一个关键字过滤算法_www.fengfly.com        
{
一个关键字过滤算法_www.fengfly.com            ParamVer(hashmp,src,i
+1);
一个关键字过滤算法_www.fengfly.com        }

一个关键字过滤算法_www.fengfly.com    }

一个关键字过滤算法_www.fengfly.com    ParamVer(hashmp,src,m
-1);
一个关键字过滤算法_www.fengfly.com}

一个关键字过滤算法_www.fengfly.com
一个关键字过滤算法_www.fengfly.com
一个关键字过滤算法_www.fengfly.com
int _tmain(int argc, _TCHAR* argv[])
一个关键字过滤算法_www.fengfly.com
{
一个关键字过滤算法_www.fengfly.com    wcout.imbue(locale(
"chs"));     
一个关键字过滤算法_www.fengfly.com    typedef map
<long,int> HASHMAP;
一个关键字过滤算法_www.fengfly.com
一个关键字过滤算法_www.fengfly.com    cout 
<<" 需要过滤文本: ";
一个关键字过滤算法_www.fengfly.com    wcout
<< src <<endl;
一个关键字过滤算法_www.fengfly.com    cout 
<<" 过滤关键字 : " ;
一个关键字过滤算法_www.fengfly.com    
for(int i = 0 ;i < 5; i++)
一个关键字过滤算法_www.fengfly.com        wcout 
<< des1[i][0<<" ";
一个关键字过滤算法_www.fengfly.com    wcout 
<<endl;
一个关键字过滤算法_www.fengfly.com    cout 
<<" 过滤关键词 : " ;
一个关键字过滤算法_www.fengfly.com    
for(int i = 0 ;i < 3; i++)
一个关键字过滤算法_www.fengfly.com        wcout 
<< des2[i] <<" ";
一个关键字过滤算法_www.fengfly.com    wcout 
<<endl;
一个关键字过滤算法_www.fengfly.com
一个关键字过滤算法_www.fengfly.com    
long  val = 0;
一个关键字过滤算法_www.fengfly.com
一个关键字过滤算法_www.fengfly.com    HASHMAP hash_map;
一个关键字过滤算法_www.fengfly.com    
/// 字 hash
一个关键字过滤算法_www.fengfly.com    for(int i = 0 ; i < 5 ; i++)
一个关键字过滤算法_www.fengfly.com    
{
一个关键字过滤算法_www.fengfly.com        val 
= HashFun(des1[i][0]);
一个关键字过滤算法_www.fengfly.com        hash_map[val] 
= 1;
一个关键字过滤算法_www.fengfly.com    }

一个关键字过滤算法_www.fengfly.com    
/// 词 hash
一个关键字过滤算法_www.fengfly.com    for(int i =0 ; i < 3 ; i++)
一个关键字过滤算法_www.fengfly.com    
{
一个关键字过滤算法_www.fengfly.com        val 
= HashFun(des2[i]);
一个关键字过滤算法_www.fengfly.com        hash_map[val] 
= 1;
一个关键字过滤算法_www.fengfly.com    }

一个关键字过滤算法_www.fengfly.com    
一个关键字过滤算法_www.fengfly.com    VmAlorgthm(hash_map,src);
一个关键字过滤算法_www.fengfly.com    
一个关键字过滤算法_www.fengfly.com    cout 
<<"\n-------------------------------------------------------------\n"
一个关键字过滤算法_www.fengfly.com        
<<" 过滤后的文本: ";
一个关键字过滤算法_www.fengfly.com    wcout
<< src <<endl;
一个关键字过滤算法_www.fengfly.com
一个关键字过滤算法_www.fengfly.com    
return 0;
一个关键字过滤算法_www.fengfly.com}



本文地址 : http://www.fengfly.com/plus/view-77289-1.html
标签: 关键字 过滤算法
------分隔线----------------------------
最新评论 查看所有评论
发表评论 查看所有评论
请自觉遵守互联网相关的政策法规,严禁发布色情、暴力、反动的言论。
评价:
表情:
验证码:
本栏分类