辉用到命名功能所以这个过滤也只是一个实验性的功能我们将使用AC自动机来实现这是在我们把“csdn”这个词设置为屏蔽词后的效果

二、搭建AC自动机

我们是从别的地方找的开源词典所以要做一下筛选首先我们要去重然后去除所有的标点符号空格和其他无关字符然后同时去掉长度为1的字符因为其会在AC自动机中表现的过于严格

wifstream

//词典的路径这里是单独开了一个程序所以和后面项目里相关代码用到的路径不同

ios::out);

Words.end()){//去掉短字但这里对中文无效因为一个中文字长度大概率不为1if

(Word.size()

(iswpunct(It1)||iswblank(It1)||iswspace(It1)){Word.erase(It1);It1--;}

true;}

AC自动机就是在字典树的基础上加入了类似于KMP的失配指针当匹配串在树上失配时会回溯到某个上一层的节点该节点的所有父节点即前缀和失配节点的所有父节点的后缀形成最大匹配使多模匹配的效率达到近似O(匹配串长度)

因为我们要将匹配到的敏感词替换成*所以相比于一般的自动机节点要在每个词的末尾记录这个词的长度同时因为不止26个字母所以也用红黑树替代了数组

class

public:FSensitiveWordFilterStruct()default;explicit

FSensitiveWordFilterStruct(const

wchar_tInputCharacter):Character(InputCharacter){};//字符wchar_t

Length{0};//子节点TMapwchar_t,std::shared_ptrFSensitiveWordFilterStructChildNode;//失配指针FSensitiveWordFilterStruct*

FailPointer{this};

FSensitiveWordFilterStructSensitiveWordFilterRoot;

UAstromutateGameInstance::UAstromutateGameInstance()

{//加载词典LoadTXTFile(/Movies/Dict.txt);//实例化自动机根节点SensitiveWordFilterRootstd::make_sharedFSensitiveWordFilterStruct(FSensitiveWordFilterStruct());//将词典中的词添加到树上for(const

autoIt:*SensitiveWords){AddWordToSensitiveWordTree(It);}//建立失配指针InitializeSensitiveWordTree();

2.加载词典

这里我们把词典作为txt文件放在Movies文件夹下因为该文件夹中的所有文件都会被原封不动的打包我们将所有敏感词存到一个TArray中

//声明敏感词词典

UAstromutateGameInstance::LoadTXTFile(const

FString

Temp{FPaths::ProjectContentDir()Path};//实例化词典数组SensitiveWordsMakeSharedTArrayFString(TArrayFString());//加载所有词FFileHelper::LoadFileToStringArray(*SensitiveWords,*Temp);UE_LOG(LogTemp,Warning,TEXT(SensitiveWords

loade

从根节点开始遍历模式串如果当前点没有当前字符对应的子节点就创建之然后无论有无都移动到该子节点

auto

UAstromutateGameInstance::AddWordToSensitiveWordTree(const

FString

{//获取根节点FSensitiveWordFilterStruct*

TempSensitiveWordFilterRoot.get();//遍历模式串中的每一个字符for(const

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

{//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

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

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

CurrentIndex{0};for(autoIt:TrueResult){if(iswpunct(It)||iswblank(It)||iswspace(It))continue;if(iswupper(It)iswlower(Result[CurrentIndex])){continue;}ItResult[CurrentIndex];}return

TrueResult;