經(jīng)常某些論壇，或者軟件中對某些字符串進(jìn)行了關(guān)鍵字過濾, 一般代替為*號，一般的算法是利用strstr算法，即使是string的find子串算法復(fù)雜度也是(N*log(n))，并非kmp算法，也非bm查找子串算法。
對于一組關(guān)鍵字過濾，特別是對于一組字符串多，且長度不規(guī)律的字符串過濾算法完全是有必要的。
網(wǎng)上對于關(guān)鍵字過濾算法較多，且實(shí)現(xiàn)方法較多，本文主要介紹基于一種把關(guān)鍵字轉(zhuǎn)換為Unicode，然后對關(guān)鍵字的字符或者單個關(guān)鍵字hash求值。算法復(fù)雜度為O(n).
對于漢字的hash值的求法，因?yàn)槭荱nicode編碼是16位，哈希求值:
/**//// 求漢字的哈希值
long HashFun(wchar_t word)
{
BYTE l = LOBYTE(word);
int h = HIBYTE(word);
long num = h << 8 ;
num +=l;
return num;
}
基本算法思想;
1.建立2個過濾關(guān)鍵字?jǐn)?shù)組:數(shù)組1：為單個字符 數(shù)組2：為2個或者多個字符
2.求出數(shù)組1，2的hash值，數(shù)組2的hash值只求出前2個字符的hash值即可。
3.掃描待檢測的文本，然后每次取2個字符，查找數(shù)組2是否有匹配，如果沒有則查找數(shù)組1。。。。 查找為O(1)
主要代碼如下:
/**//*
File : WordFilter.cpp
brief: 關(guān)鍵字過濾程序，復(fù)雜度為O(n)，線性
Author: Expter
Data : 2009/06/30
對漢字或者字符進(jìn)行哈希算法，先轉(zhuǎn)換為unicode編碼，然后求其hash值。
主要算法為:
1.建立2個過濾關(guān)鍵字?jǐn)?shù)組:數(shù)組1：為單個字符 數(shù)組2：為2個或者多個字符
2.求出數(shù)組1，2的hash值，數(shù)組2的hash值只求出前2個字符的hash值即可。
3.掃描待檢測的文本，然后每次取2個字符，查找數(shù)組2是否有匹配，如果沒有則查找數(shù)組1。。。。 查找為O(1)
不足:
不能很好的分詞。過濾不是很準(zhǔn)確，每次只能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"這個原來是打算的啥子?xùn)|西用漢字只是一個是不是測試"};
/**//// 求漢字的哈希值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 <<" 過濾關(guān)鍵字 : " ;
for(int i = 0 ;i < 5; i++)
wcout << des1[i][0] <<" ";
wcout <<endl;
cout <<" 過濾關(guān)鍵詞 : " ;
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;
}