镇江做网站哪家公司好,做企业网站需要什么文件,市场营销策划方案ppt,太仓建设网站在游戏中经常会有需要玩家输入一些内容的功能#xff0c;例如聊天#xff0c;命名等#xff0c;这款游戏只有在存档时辉用到命名功能#xff0c;所以这个过滤也只是一个实验性的功能#xff0c;我们将使用AC自动机来实现#xff0c;这是在我们把“csdn”这个词设置为屏蔽… 在游戏中经常会有需要玩家输入一些内容的功能例如聊天命名等这款游戏只有在存档时辉用到命名功能所以这个过滤也只是一个实验性的功能我们将使用AC自动机来实现这是在我们把“csdn”这个词设置为屏蔽词后的效果 目录
一、敏感词词典的处理
二、搭建AC自动机
1.自动机节点的数据机构
2.加载词典
3.建立字典树
4.建立失配指针
三、替换字符串中的敏感词 一、敏感词词典的处理 我们是从别的地方找的开源词典所以要做一下筛选首先我们要去重然后去除所有的标点符号空格和其他无关字符然后同时去掉长度为1的字符因为其会在AC自动机中表现的过于严格
wifstream InputTxt;
wofstream OutputTxt;
//词典的路径这里是单独开了一个程序所以和后面项目里相关代码用到的路径不同
InputTxt.open(Dict.txt, ios::out);
//使用宽字符串读入
wstring Word;
mapwstring, boolWords;
while (getline(InputTxt,Word))
{//去重if (Words.find(Word) Words.end()){//去掉短字但这里对中文无效因为一个中文字长度大概率不为1if (Word.size() 1)continue;for (auto It1 : Word){//统一成小写if (iswupper(It1)){It1 towlower(It1);}//去除字符 if (iswpunct(It1)||iswblank(It1)||iswspace(It1)){Word.erase(It1);It1--;} }//记录这个词处理完毕Words[Word] true;}
}
InputTxt.close();
OutputTxt.open(Dict.txt, ios::out);
//将处理完的词重新写入词典
for (auto It: Words)
{OutputTxt It.first endl;
}
二、搭建AC自动机 AC自动机就是在字典树的基础上加入了类似于KMP的失配指针当匹配串在树上失配时会回溯到某个上一层的节点该节点的所有父节点即前缀和失配节点的所有父节点的后缀形成最大匹配使多模匹配的效率达到近似O(匹配串长度)
1.自动机节点的数据机构 因为我们要将匹配到的敏感词替换成*所以相比于一般的自动机节点要在每个词的末尾记录这个词的长度同时因为不止26个字母所以也用红黑树替代了数组
class FSensitiveWordFilterStruct
{
public:FSensitiveWordFilterStruct()default;explicit FSensitiveWordFilterStruct(const wchar_tInputCharacter):Character(InputCharacter){};//字符wchar_t Character{#};//匹配的字符串的长度int Length{0};//子节点TMapwchar_t,std::shared_ptrFSensitiveWordFilterStructChildNode;//失配指针FSensitiveWordFilterStruct* FailPointer{this};
}; 然后我们在游戏实例中声明自动机的根节点
//屏蔽词过滤器树根
std::shared_ptr FSensitiveWordFilterStructSensitiveWordFilterRoot; 在游戏启动时初始化AC自动机用到的函数后面一个一个讲
UAstromutateGameInstance::UAstromutateGameInstance()
{//加载词典LoadTXTFile(/Movies/Dict.txt);//实例化自动机根节点SensitiveWordFilterRootstd::make_sharedFSensitiveWordFilterStruct(FSensitiveWordFilterStruct());//将词典中的词添加到树上for(const autoIt:*SensitiveWords){AddWordToSensitiveWordTree(It);}//建立失配指针InitializeSensitiveWordTree();
}
2.加载词典 这里我们把词典作为txt文件放在Movies文件夹下因为该文件夹中的所有文件都会被原封不动的打包我们将所有敏感词存到一个TArray中
//声明敏感词词典
TSharedPtrTArrayFString SensitiveWords;
auto UAstromutateGameInstance::LoadTXTFile(const FString Path)-void
{//获取词典路径FString Temp{FPaths::ProjectContentDir()Path};//实例化词典数组SensitiveWordsMakeSharedTArrayFString(TArrayFString());//加载所有词FFileHelper::LoadFileToStringArray(*SensitiveWords,*Temp);UE_LOG(LogTemp,Warning,TEXT(SensitiveWords loade %d Words),SensitiveWords-Num());
}
3.建立字典树 从根节点开始遍历模式串如果当前点没有当前字符对应的子节点就创建之然后无论有无都移动到该子节点
auto UAstromutateGameInstance::AddWordToSensitiveWordTree(const FString InputString) const-void
{//获取根节点FSensitiveWordFilterStruct* TempSensitiveWordFilterRoot.get();//遍历模式串中的每一个字符for(const autoIt:InputString){wchar_t CurrentChar{It};//如果当前点没有对应的子节点就添加之if(!Temp-ChildNode.Contains(CurrentChar)){Temp-ChildNode.Add(CurrentChar,std::make_sharedFSensitiveWordFilterStruct(FSensitiveWordFilterStruct(CurrentChar)));}TempTemp-ChildNode[CurrentChar].get();}//将词的长度记录在词尾Temp-LengthInputString.Len();
}
4.建立失配指针 因为失配指针指向的节点一定在当前点的上层所以我们进行bfs首先将根节点的所有直连的子节点的失配指针指向根节点因为这些点的上层节点只有根节点。然后对于一个失配点如果其父节点的失配指针指向的点的子节点中有和该失配点相同的点则失配点的失配指针指向该点否则指向根节点
auto UAstromutateGameInstance::InitializeSensitiveWordTree() const - void
{//bfs队列std::queuestd::shared_ptrFSensitiveWordFilterStructQueue;//将深度为1的点的失配指针指向根节点for(autoIt:SensitiveWordFilterRoot-ChildNode){It.Value-FailPointerSensitiveWordFilterRoot.get();Queue.push(std::make_sharedFSensitiveWordFilterStruct(*It.Value));}while(!Queue.empty()){std::shared_ptrFSensitiveWordFilterStruct CurrentNodeQueue.front();Queue.pop();//遍历所有子节点for(autoIt:CurrentNode-ChildNode){//父节点的失配指针指向的节点是否含有匹配的子节点if(!CurrentNode-FailPointer-ChildNode.Contains(It.Key)){It.Value-FailPointerSensitiveWordFilterRoot.get();}else{It.Value-FailPointerCurrentNode-FailPointer-ChildNode[It.Key].get();}Queue.push(std::make_sharedFSensitiveWordFilterStruct(*It.Value));}}
}
三、替换字符串中的敏感词 首先我们将玩家输入的字符串使用字典中字符串同样的方法进行处理去除符号和空格全部转为小写然后遍历其每一个字符不匹配就按失配指针移动匹配就检查是否是词尾如果是的话根据记录的词的长度算出这个词的区间将这个居间内的所有字符替换成*该操作不会影响到后面的匹配最后将字符串还原成原来有符号和空格的格式并返回
auto UAstromutateGameInstance::ReplaceSensitiveWords(const FString RawString)-FString
{FString Result{};//对玩家输入的字符串进行处理for(const autoIt:RawString){if(iswpunct(It)||iswblank(It)||iswspace(It))continue;if(isupper(It))Resulttowlower(It);elseResultIt;}FSensitiveWordFilterStruct* Temp{SensitiveWordFilterRoot.get()};//遍历匹配串的每一个字符for(int i0;iResult.Len();i){wchar_t CurrentChar{Result[i]};//如果失配就一直回溯直到根节点while(!Temp-ChildNode.Contains(CurrentChar)Temp!SensitiveWordFilterRoot.get()){TempTemp-FailPointer;}//仍然适配就结束这个字符的搜索if(!Temp-ChildNode.Contains(CurrentChar)){TempSensitiveWordFilterRoot.get();continue;}//移动到匹配的节点TempTemp-ChildNode[CurrentChar].get();FSensitiveWordFilterStruct* Temp2{Temp};//遍历匹配到的所有词while(Temp2!SensitiveWordFilterRoot.get()){if(Temp2-Length){//根据长度算出该词其实位置for(int ji-Temp2-Length1;ji;j){Result[j]*;}}Temp2Temp2-FailPointer;}}//将处理完的字符串还原成输入的格式FString TrueResult{RawString};int CurrentIndex{0};for(autoIt:TrueResult){if(iswpunct(It)||iswblank(It)||iswspace(It))continue;if(iswupper(It)iswlower(Result[CurrentIndex])){continue;}ItResult[CurrentIndex];}return TrueResult;
}
