記錄做敏感匹配算法的過程。
介紹
敏感詞屏蔽是很多內(nèi)容網(wǎng)站都需要做的事情，而根據(jù)公安提供的敏感詞列表尔觉，具體格式如下：
從上圖可以看出舆绎，敏感詞分為三類：動詞、名詞虹蓄、專屬詞語，三種敏感詞匹配的方式也有些不同。
專屬詞語是只要出現(xiàn)就需要屏蔽魄眉，例如：今天中午我不知道吃什么了。如果中午是一個專屬敏感詞的話闷袒，那么這段話中的中午就需要被屏蔽掉了坑律。
動詞和名詞是需要組合才能進行匹配的，并且同一分類下的動名詞都可以進行組合囊骤，如前面的圖中就能組合出：動詞1名詞1晃择、動詞1名詞2、動詞2名詞1也物、動詞2名詞2....,匹配的方式則是組合起來之后和專屬敏感詞一致宫屠，而組合之后的敏感詞個數(shù)則是：動詞個數(shù)V * 名詞個數(shù)N（V * N）。
說到這里滑蚯，可能很快就會得出一個解決方法浪蹂。
#1
由于動名詞最后的匹配方式是將動詞和名詞組合起來再進行匹配的，那么我們可以將所以分類的動名詞組合起來告材，然后放入緩存中坤次，這樣就能大大節(jié)省在匹配敏感詞的過程中進行重復(fù)組合動名詞的開銷。而根據(jù)公安提供的詞庫创葡，最終得到的敏感詞個數(shù)為：40k+浙踢，其中專屬詞：5.3k，動名詞組合：40k,那么此時的敏感詞列表格式如下：
['專屬詞1','專屬詞2','專屬詞3'....,'動名詞組合1','動名詞組合2','動名詞組合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;
}
以上這種方式雖然很簡單的就能匹配出銘感詞灿渴，但是性能極差洛波，即使我們已經(jīng)將所有的動名詞組合放入緩存中，省去了一部分的計算開銷骚露，但是敏感詞的數(shù)組大小卻依然是40k+的大小蹬挤，也就意味著每次都需要循環(huán)40k+次才能校驗完成。并且以上代碼使用了IndexOf默認方法棘幸，性能遠不如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)在這種方式雖然在性能上有提升，但是時間復(fù)雜度依然沒有降低吨悍。我們再回過來仔細看這張圖
我們將所有的動名詞進行組合的時候扫茅，即是對所有的敏感詞進行了全量的匹配，但是真的需要這么做嗎育瓜？如果將匹配的拆分為原來的動名詞的話葫隙，匹配的過程如下圖：
按照我們之前的全量匹配，B4會和A1躏仇、A2恋脚、A3、A4...D4都進行匹配焰手，但是在拆分動名詞的情況下糟描，B4沒有包含A,視乎根本沒有必要再和A1進行匹配，因為A包含于A1书妻、A2船响、A3...，若B4不包含A驻子，即B4也不包含A1灿意、A2、A3...崇呵，同理B4若不包含C,也就不會包含C1、C2馅袁、C3...域慷。那么這樣的話，匹配過程如下圖：
#2
根據(jù)上面的結(jié)論汗销，如果匹配內(nèi)容不包含動詞犹褒，那么就無需匹配當前動詞和名詞組合的敏感詞，所以緩存的銘感詞列表數(shù)據(jù)結(jié)構(gòu)需要更改為如下：
[
{
"CategoryName":"分類1",
"SensitiveList":["專屬敏感詞1","專屬敏感詞2"...],
"VerbList":
[
{
"Word":"動詞1",
"CombList":["動詞1名詞1","動詞1名詞2","動詞1名詞3"...]
},
{
"Word":"動詞2",
"CombList":["動詞2名詞1","動詞2名詞2","動詞2名詞3"...]
}
]
},
{
"CategoryName":"分類2",
"SensitiveList":["專屬敏感詞1","專屬敏感詞2"...],
"VerbList":
[
{
"Word":"動詞1",
"CombList":["動詞1名詞1","動詞1名詞2","動詞1名詞3"...]
},
{
"Word":"動詞2",
"CombList":["動詞2名詞1","動詞2名詞2","動詞2名詞3"...]
}
]
}
]
CategoryName 分類名稱
SensitiveList 專屬敏感詞
VerbList 動詞列表
CombList 動名詞組合列表
代碼如下
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);
}
}
//動詞匹配
foreach (var verb in sen.VerbList)
{
// 如果匹配的內(nèi)容中包含了動詞
if (txt.Contains(verb.Word))
{
//進行下一步的動名詞組合匹配
for (int i = 0; i < verb.CombList.Count; i++)
{
var combstr = verb.CombList[i];
//如果匹配存在動名組合詞
if (txt.Contains(combstr))
{
//添加動詞
senlist.Add(verb.Word);
//添加名詞
senlist.Add(combstr.Replace(verb.Word,""));
}
}
}
}
}
return senlist;
}
這樣一來弛针，遍歷的數(shù)組長度將大大減少叠骑，時間復(fù)雜度也得到了降低，但是這就是最好的辦法了嗎削茁？
我們來看一下現(xiàn)在匹配過程：
當前的數(shù)據(jù)結(jié)構(gòu)由于對敏感詞進行了分類宙枷，所以在匹配的時候最多會出現(xiàn)三層循環(huán)，并且其中不同的分類中間可能存在著相同的動詞茧跋，這些數(shù)據(jù)的結(jié)構(gòu)是冗余的慰丛。
#3
為了保證敏感詞只匹配一次，并減少循環(huán)的復(fù)雜度瘾杭。我們可以將數(shù)據(jù)結(jié)構(gòu)改為如下：
專屬敏感詞诅病，字典存儲，key為專屬敏感詞
{
"專屬敏感詞1" : "",
"專屬敏感詞1" : "",
....
}
動詞和動名詞組合，字典存儲贤笆，key為動詞
{
"動詞1" : ["動詞1名詞1","動詞1名詞2",,"動詞1名詞2"...],
"動詞1" : ["動詞1名詞1","動詞1名詞2",,"動詞1名詞2"...],
}
原本的數(shù)組結(jié)構(gòu)都改為了字典蝇棉，使用字典可以保證專屬敏感詞或者動詞不會因為在不同的分類中出現(xiàn)重復(fù)，這樣可以簡化數(shù)據(jù)的結(jié)構(gòu)芥永，并且使用兩個字典來存儲專屬敏感詞和動名詞银萍，將可以將匹配的循環(huán)縮小到兩層，降低匹配過程中的時間復(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);
}
}
//動詞匹配
foreach (var verb in verbDic.Keys())
{
// 如果匹配的內(nèi)容中包含了動詞
if (txt.Contains(verb))
{
var combList = verbDic[verb];
foreach(var comb in combList)
{
//動名詞組合匹配
if (txt.Contains(comb))
{
senlist.Add(comb);
}
}
}
}
return senlist;
}
匹配的過程如下圖：
以上就是對敏感詞匹配過程的理解贴唇，啟發(fā)于降低時間復(fù)雜度這一詞，如有更好的方法飞袋，歡迎在下面留言戳气。
