記錄做敏感匹配算法的過程。
介紹
敏感詞屏蔽是很多內(nèi)容網(wǎng)站都需要做的事情，而根據(jù)公安提供的敏感詞列表，具體格式如下：
從上圖可以看出，敏感詞分為三類：動(dòng)詞、名詞、專屬詞語，三種敏感詞匹配的方式也有些不同。
專屬詞語是只要出現(xiàn)就需要屏蔽，例如：今天中午我不知道吃什么了。如果中午是一個(gè)專屬敏感詞的話，那么這段話中的中午就需要被屏蔽掉了。
動(dòng)詞和名詞是需要組合才能進(jìn)行匹配的，并且同一分類下的動(dòng)名詞都可以進(jìn)行組合，如前面的圖中就能組合出：動(dòng)詞1名詞1、動(dòng)詞1名詞2、動(dòng)詞2名詞1、動(dòng)詞2名詞2....,匹配的方式則是組合起來之后和專屬敏感詞一致，而組合之后的敏感詞個(gè)數(shù)則是：動(dòng)詞個(gè)數(shù)V * 名詞個(gè)數(shù)N（V * N）。
說到這里，可能很快就會(huì)得出一個(gè)解決方法。
#1
由于動(dòng)名詞最后的匹配方式是將動(dòng)詞和名詞組合起來再進(jìn)行匹配的，那么我們可以將所以分類的動(dòng)名詞組合起來，然后放入緩存中，這樣就能大大節(jié)省在匹配敏感詞的過程中進(jìn)行重復(fù)組合動(dòng)名詞的開銷。而根據(jù)公安提供的詞庫(kù)，最終得到的敏感詞個(gè)數(shù)為：40k+，其中專屬詞：5.3k，動(dòng)名詞組合：40k,那么此時(shí)的敏感詞列表格式如下：
['專屬詞1','專屬詞2','專屬詞3'....,'動(dòng)名詞組合1','動(dòng)名詞組合2','動(dòng)名詞組合3'....]
匹配算法如下：
public List<string> MatchingSensitive(List<string> senlist, string txt)
{
var returnlist = new List<string>();
foreach(var item in senlist)
{
if(txt.IndexOf(item))
{
returnlist.Add(item);
}
}
return returnlist;
}
以上這種方式雖然很簡(jiǎn)單的就能匹配出銘感詞，但是性能極差，即使我們已經(jīng)將所有的動(dòng)名詞組合放入緩存中，省去了一部分的計(jì)算開銷，但是敏感詞的數(shù)組大小卻依然是40k+的大小，也就意味著每次都需要循環(huán)40k+次才能校驗(yàn)完成。并且以上代碼使用了IndexOf默認(rèn)方法，性能遠(yuǎn)不如Contains，具體原因可以去看看IndexOf和Contains的源碼，所以我們需要把上面的代碼改為：
public List<string> MatchingSensitive(List<string> senlist, string txt)
{
var returnlist = new List<string>();
foreach(var item in senlist)
{
if(txt.Contains(item))
{
returnlist.Add(item);
}
}
return returnlist;
}
現(xiàn)在這種方式雖然在性能上有提升，但是時(shí)間復(fù)雜度依然沒有降低。我們?cè)倩剡^來仔細(xì)看這張圖
我們將所有的動(dòng)名詞進(jìn)行組合的時(shí)候，即是對(duì)所有的敏感詞進(jìn)行了全量的匹配，但是真的需要這么做嗎？如果將匹配的拆分為原來的動(dòng)名詞的話，匹配的過程如下圖：
按照我們之前的全量匹配，B4會(huì)和A1、A2、A3、A4...D4都進(jìn)行匹配，但是在拆分動(dòng)名詞的情況下，B4沒有包含A,視乎根本沒有必要再和A1進(jìn)行匹配，因?yàn)?code>A包含于A1、A2、A3...，若B4不包含A，即B4也不包含A1、A2、A3...，同理B4若不包含C,也就不會(huì)包含C1、C2、C3...。那么這樣的話，匹配過程如下圖：
#2
根據(jù)上面的結(jié)論，如果匹配內(nèi)容不包含動(dòng)詞，那么就無需匹配當(dāng)前動(dòng)詞和名詞組合的敏感詞，所以緩存的銘感詞列表數(shù)據(jù)結(jié)構(gòu)需要更改為如下：
[
{
"CategoryName":"分類1",
"SensitiveList":["專屬敏感詞1","專屬敏感詞2"...],
"VerbList":
[
{
"Word":"動(dòng)詞1",
"CombList":["動(dòng)詞1名詞1","動(dòng)詞1名詞2","動(dòng)詞1名詞3"...]
},
{
"Word":"動(dòng)詞2",
"CombList":["動(dòng)詞2名詞1","動(dòng)詞2名詞2","動(dòng)詞2名詞3"...]
}
]
},
{
"CategoryName":"分類2",
"SensitiveList":["專屬敏感詞1","專屬敏感詞2"...],
"VerbList":
[
{
"Word":"動(dòng)詞1",
"CombList":["動(dòng)詞1名詞1","動(dòng)詞1名詞2","動(dòng)詞1名詞3"...]
},
{
"Word":"動(dòng)詞2",
"CombList":["動(dòng)詞2名詞1","動(dòng)詞2名詞2","動(dòng)詞2名詞3"...]
}
]
}
]
CategoryName 分類名稱
SensitiveList 專屬敏感詞
VerbList 動(dòng)詞列表
CombList 動(dòng)名詞組合列表
代碼如下
public class SenEntity
{
public string CategoryName { get; set; }
public List<string> SensitiveList { get; set; }
public List<SenVerbEntity> VerbList { get; set; }
}
public class SenVerbEntity
{
public string Word { get; set; }
public List<string> CombList { get; set; }
}
public List<string> MatchingSensitive(List<SenEntity> list, string txt)
{
List<string> senlist = new List<string>();
foreach(var sen in list)
{
//專屬敏感詞匹配
foreach (var senstr in sen.SensitiveList)
{
if (txt.Contains(senstr))
{
senlist.Add(senstr);
}
}
//動(dòng)詞匹配
foreach (var verb in sen.VerbList)
{
// 如果匹配的內(nèi)容中包含了動(dòng)詞
if (txt.Contains(verb.Word))
{
//進(jìn)行下一步的動(dòng)名詞組合匹配
for (int i = 0; i < verb.CombList.Count; i++)
{
var combstr = verb.CombList[i];
//如果匹配存在動(dòng)名組合詞
if (txt.Contains(combstr))
{
//添加動(dòng)詞
senlist.Add(verb.Word);
//添加名詞
senlist.Add(combstr.Replace(verb.Word,""));
}
}
}
}
}
return senlist;
}
這樣一來，遍歷的數(shù)組長(zhǎng)度將大大減少，時(shí)間復(fù)雜度也得到了降低，但是這就是最好的辦法了嗎？
我們來看一下現(xiàn)在匹配過程：
當(dāng)前的數(shù)據(jù)結(jié)構(gòu)由于對(duì)敏感詞進(jìn)行了分類，所以在匹配的時(shí)候最多會(huì)出現(xiàn)三層循環(huán)，并且其中不同的分類中間可能存在著相同的動(dòng)詞，這些數(shù)據(jù)的結(jié)構(gòu)是冗余的。
#3
為了保證敏感詞只匹配一次，并減少循環(huán)的復(fù)雜度。我們可以將數(shù)據(jù)結(jié)構(gòu)改為如下：
專屬敏感詞，字典存儲(chǔ)，key為專屬敏感詞
{
"專屬敏感詞1" : "",
"專屬敏感詞1" : "",
....
}
動(dòng)詞和動(dòng)名詞組合，字典存儲(chǔ)，key為動(dòng)詞
{
"動(dòng)詞1" : ["動(dòng)詞1名詞1","動(dòng)詞1名詞2",,"動(dòng)詞1名詞2"...],
"動(dòng)詞1" : ["動(dòng)詞1名詞1","動(dòng)詞1名詞2",,"動(dòng)詞1名詞2"...],
}
原本的數(shù)組結(jié)構(gòu)都改為了字典，使用字典可以保證專屬敏感詞或者動(dòng)詞不會(huì)因?yàn)樵诓煌姆诸愔谐霈F(xiàn)重復(fù)，這樣可以簡(jiǎn)化數(shù)據(jù)的結(jié)構(gòu)，并且使用兩個(gè)字典來存儲(chǔ)專屬敏感詞和動(dòng)名詞，將可以將匹配的循環(huán)縮小到兩層，降低匹配過程中的時(shí)間復(fù)雜度。
匹配的代碼如下：
public List<string> MatchingSensitive(Dictionary<string,string> sensitiveDic,
Dictionary<string,List<string>> verbDic, string txt)
{
List<string> senlist = new List<string>();
//專屬敏感詞匹配
foreach(var sen in sensitiveDic.Keys())
{
if (txt.Contains(sen))
{
senlist.Add(sen);
}
}
//動(dòng)詞匹配
foreach (var verb in verbDic.Keys())
{
// 如果匹配的內(nèi)容中包含了動(dòng)詞
if (txt.Contains(verb))
{
var combList = verbDic[verb];
foreach(var comb in combList)
{
//動(dòng)名詞組合匹配
if (txt.Contains(comb))
{
senlist.Add(comb);
}
}
}
}
return senlist;
}
匹配的過程如下圖：
以上就是對(duì)敏感詞匹配過程的理解，啟發(fā)于降低時(shí)間復(fù)雜度這一詞，如有更好的方法，歡迎在下面留言。
