C#實(shí)現(xiàn)前向最大匹、字典樹(分詞、檢索)的示例代碼
場景:現(xiàn)在有一個(gè)錯(cuò)詞庫,維護(hù)的是錯(cuò)詞和正確詞對(duì)應(yīng)關(guān)系。比如:錯(cuò)詞“我門”對(duì)應(yīng)的正確詞“我們”。然后在用戶輸入的文字進(jìn)行錯(cuò)詞校驗(yàn),需要判斷輸入的文字是否有錯(cuò)詞,并找出錯(cuò)詞以便提醒用戶,并且可以顯示出正確詞以便用戶確認(rèn),如果是錯(cuò)詞就進(jìn)行替換。
首先想到的就是取出錯(cuò)詞List放在內(nèi)存中,當(dāng)用戶輸入完成后用錯(cuò)詞List來foreach每個(gè)錯(cuò)詞,然后查找輸入的字符串中是否包含錯(cuò)詞。這是一種有效的方法,并且能夠?qū)崿F(xiàn)。問題是錯(cuò)詞的數(shù)量比較多,目前有10多萬條,將來也會(huì)不斷更新擴(kuò)展。所以pass了這種方案,為了讓錯(cuò)詞查找提高速度就用了字典樹來存儲(chǔ)錯(cuò)詞。
字典樹
Trie樹,即字典樹,又稱單詞查找樹或鍵樹,是一種樹形結(jié)構(gòu),是一種哈希樹的變種。典型應(yīng)用是用于統(tǒng)計(jì)和排序大量的字符串(但不僅限于字符串),所以經(jīng)常被搜索引擎系統(tǒng)用于文本詞頻統(tǒng)計(jì)。它的優(yōu)點(diǎn)是:最大限度地減少無謂的字符串比較。
Trie的核心思想是空間換時(shí)間。利用字符串的公共前綴來降低查詢時(shí)間的開銷以達(dá)到提高效率的目的。
通常字典樹的查詢時(shí)間復(fù)雜度是O(logL),L是字符串的長度。所以效率還是比較高的。而我們上面說的foreach循環(huán)則時(shí)間復(fù)雜度為O(n),根據(jù)時(shí)間復(fù)雜度來看,字典樹效率應(yīng)該是可行方案。
字典樹原理
根節(jié)點(diǎn)不包含字符,除根節(jié)點(diǎn)外每一個(gè)節(jié)點(diǎn)都只包含一個(gè)字符; 從根節(jié)點(diǎn)到某一節(jié)點(diǎn),路徑上經(jīng)過的字符連接起來,為該節(jié)點(diǎn)對(duì)應(yīng)的字符串; 每個(gè)節(jié)點(diǎn)的所有子節(jié)點(diǎn)包含的字符都不相同。
比如現(xiàn)在有錯(cuò)詞:“我門”、“旱睡”、“旱起”。那么字典樹如下圖
其中紅色的點(diǎn)就表示詞結(jié)束節(jié)點(diǎn),也就是從根節(jié)點(diǎn)往下連接成我們的詞。
實(shí)現(xiàn)字典樹:
public class Trie { private class Node { /// <summary> /// 是否單詞根節(jié)點(diǎn) /// </summary> public bool isTail = false; public Dictionary<char, Node> nextNode; public Node(bool isTail) { this.isTail = isTail; this.nextNode = new Dictionary<char, Node>(); } public Node() : this(false) { } } /// <summary> /// 根節(jié)點(diǎn) /// </summary> private Node rootNode; private int size; private int maxLength; public Trie() { this.rootNode = new Node(); this.size = 0; this.maxLength = 0; } /// <summary> /// 字典樹中存儲(chǔ)的單詞的最大長度 /// </summary> /// <returns></returns> public int MaxLength() { return maxLength; } /// <summary> /// 字典樹中存儲(chǔ)的單詞數(shù)量 /// </summary> public int Size() { return size; } /// <summary> /// 獲取字典樹中所有的詞 /// </summary> public List<string> GetWordList() { return GetStrList(this.rootNode); } private List<string> GetStrList(Node node) { List<string> wordList = new List<string>(); foreach (char nextChar in node.nextNode.Keys) { string firstWord = Convert.ToString(nextChar); Node childNode = node.nextNode[nextChar]; if (childNode == null || childNode.nextNode.Count == 0) { wordList.Add(firstWord); } else { if (childNode.isTail) { wordList.Add(firstWord); } List<string> subWordList = GetStrList(childNode); foreach (string subWord in subWordList) { wordList.Add(firstWord + subWord); } } } return wordList; } /// <summary> /// 向字典中添加新的單詞 /// </summary> /// <param name="word"></param> public void Add(string word) { //從根節(jié)點(diǎn)開始 Node cur = this.rootNode; //循環(huán)遍歷單詞 foreach (char c in word.ToCharArray()) { //如果字典樹節(jié)點(diǎn)中沒有這個(gè)字母,則添加 if (!cur.nextNode.ContainsKey(c)) { cur.nextNode.Add(c, new Node()); } cur = cur.nextNode[c]; } cur.isTail = true; if (word.Length > this.maxLength) { this.maxLength = word.Length; } size++; } /// <summary> /// 查詢字典中某單詞是否存在 /// </summary> /// <param name="word"></param> /// <returns></returns> public bool Contains(string word) { return Match(rootNode, word); } /// <summary> /// 查找匹配 /// </summary> /// <param name="node"></param> /// <param name="word"></param> /// <returns></returns> private bool Match(Node node, string word) { if (word.Length == 0) { if (node.isTail) { return true; } else { return false; } } else { char firstChar = word.ElementAt(0); if (!node.nextNode.ContainsKey(firstChar)) { return false; } else { Node childNode = node.nextNode[firstChar]; return Match(childNode, word.Substring(1, word.Length - 1)); } } } }
測試下:
現(xiàn)在我們有了字典樹,然后就不能以字典樹來foreach,字典樹用于檢索。我們就以用戶輸入的字符串為數(shù)據(jù)源,去字典樹種查找是否存在錯(cuò)詞。因此需要對(duì)輸入字符串進(jìn)行取詞檢索。也就是分詞,分詞我們采用前向最大匹配。
前向最大匹配
我們分詞的目的是將輸入字符串分成若干個(gè)詞語,前向最大匹配就是從前向后尋找在詞典中存在的詞。
例子:我們假設(shè)maxLength= 3,即假設(shè)單詞的最大長度為3。實(shí)際上我們應(yīng)該以字典樹中的最大單詞長度,作為最大長度來分詞(上面我們的字典最大長度應(yīng)該是2)。這樣效率更高,為了演示匹配過程就假設(shè)maxLength為3,這樣演示的更清楚。
用前向最大匹配來劃分“我們應(yīng)該早睡早起” 這句話。因?yàn)槲沂清e(cuò)詞匹配,所以這句話我改成“我門應(yīng)該旱睡旱起”。
第一次:取子串 “我門應(yīng)”,正向取詞,如果匹配失敗,每次去掉匹配字段最后面的一個(gè)字。
“我門應(yīng)”,掃描詞典中單詞,沒有匹配,子串長度減 1 變?yōu)椤拔议T”。
“我門”,掃描詞典中的單詞,匹配成功,得到“我門”錯(cuò)詞,輸入變?yōu)椤皯?yīng)該旱”。
第二次:取子串“應(yīng)該旱”
“應(yīng)該旱”,掃描詞典中單詞,沒有匹配,子串長度減 1 變?yōu)椤皯?yīng)該”。
“應(yīng)該”,掃描詞典中的單詞,沒有匹配,輸入變?yōu)椤皯?yīng)”。
“應(yīng)”,掃描詞典中的單詞,沒有匹配,輸入變?yōu)椤霸摵邓薄?/p>
第三次:取子串“該旱睡”
“該旱睡”,掃描詞典中單詞,沒有匹配,子串長度減 1 變?yōu)椤霸摵怠薄?/p>
“該旱”,掃描詞典中的單詞,沒有匹配,輸入變?yōu)椤霸摗薄?/p>
“該”,掃描詞典中的單詞,沒有匹配,輸入變?yōu)椤昂邓怠薄?/p>
第四次:取子串“旱睡旱”
“旱睡旱”,掃描詞典中單詞,沒有匹配,子串長度減 1 變?yōu)椤昂邓薄?/p>
“旱睡”,掃描詞典中的單詞,匹配成功,得到“旱睡”錯(cuò)詞,輸入變?yōu)椤霸缙稹薄?/p>
以此類推,我們得到錯(cuò)詞 我們/旱睡/旱起。
因?yàn)槲沂墙Y(jié)合字典樹匹配錯(cuò)詞所以一個(gè)字也可能是錯(cuò)字,則匹配到單個(gè)字,如果只是分詞則上面的到一個(gè)字的時(shí)候就應(yīng)該停止分詞了,直接字符串長度減1。
這種匹配方式還有后向最大匹配以及雙向匹配,這個(gè)大家可以去了解下。
實(shí)現(xiàn)前向最大匹配,這里后向最大匹配也可以一起實(shí)現(xiàn)。
public class ErrorWordMatch { private static ErrorWordMatch singleton = new ErrorWordMatch(); private static Trie trie = new Trie(); private ErrorWordMatch() { } public static ErrorWordMatch Singleton() { return singleton; } public void LoadTrieData(List<string> errorWords) { foreach (var errorWord in errorWords) { trie.Add(errorWord); } } /// <summary> /// 最大 正向/逆向 匹配錯(cuò)詞 /// </summary> /// <param name="inputStr">需要匹配錯(cuò)詞的字符串</param> /// <param name="leftToRight">true為從左到右分詞,false為從右到左分詞</param> /// <returns>匹配到的錯(cuò)詞</returns> public List<string> MatchErrorWord(string inputStr, bool leftToRight) { if (string.IsNullOrWhiteSpace(inputStr)) return null; if (trie.Size() == 0) { throw new ArgumentException("字典樹沒有數(shù)據(jù),請(qǐng)先調(diào)用 LoadTrieData 方法裝載字典樹"); } //取詞的最大長度 int maxLength = trie.MaxLength(); //取詞的當(dāng)前長度 int wordLength = maxLength; //分詞操作中,處于字符串中的當(dāng)前位置 int position = 0; //分詞操作中,已經(jīng)處理的字符串總長度 int segLength = 0; //用于嘗試分詞的取詞字符串 string word = ""; //用于儲(chǔ)存正向分詞的字符串?dāng)?shù)組 List<string> segWords = new List<string>(); //用于儲(chǔ)存逆向分詞的字符串?dāng)?shù)組 List<string> segWordsReverse = new List<string>(); //開始分詞,循環(huán)以下操作,直到全部完成 while (segLength < inputStr.Length) { //如果剩余沒分詞的字符串長度<取詞的最大長度,則取詞長度等于剩余未分詞長度 if ((inputStr.Length - segLength) < maxLength) wordLength = inputStr.Length - segLength; //否則,按最大長度處理 else wordLength = maxLength; //從左到右 和 從右到左截取時(shí),起始位置不同 //剛開始,截取位置是字符串兩頭,隨著不斷循環(huán)分詞,截取位置會(huì)不斷推進(jìn) if (leftToRight) position = segLength; else position = inputStr.Length - segLength - wordLength; //按照指定長度,從字符串截取一個(gè)詞 word = inputStr.Substring(position, wordLength); //在字典中查找,是否存在這樣一個(gè)詞 //如果不包含,就減少一個(gè)字符,再次在字典中查找 //如此循環(huán),直到只剩下一個(gè)字為止 while (!trie.Contains(word)) { //如果最后一個(gè)字都沒有匹配,則把word設(shè)置為空,用來表示沒有匹配項(xiàng)(如果是分詞直接break) if (word.Length == 1) { word = null; break; } //把截取的字符串,最邊上的一個(gè)字去掉 //從左到右 和 從右到左時(shí),截掉的字符的位置不同 if (leftToRight) word = word.Substring(0, word.Length - 1); else word = word.Substring(1); } //將分出匹配上的詞,加入到分詞字符串?dāng)?shù)組中,正向和逆向不同 if (word != null) { if (leftToRight) segWords.Add(word); else segWordsReverse.Add(word); //已經(jīng)完成分詞的字符串長度,要相應(yīng)增加 segLength += word.Length; } else { //沒匹配上的則+1,丟掉一個(gè)字(如果是分詞 則不用判斷word是否為空,單個(gè)字也返回) segLength += 1; } } //如果是逆向分詞,對(duì)分詞結(jié)果反轉(zhuǎn)排序 if (!leftToRight) { for (int i = segWordsReverse.Count - 1; i >= 0; i--) { //將反轉(zhuǎn)的結(jié)果,保存在正向分詞數(shù)組中 以便最后return 同一個(gè)變量segWords segWords.Add(segWordsReverse[i]); } } return segWords; } }
這里使用了單例模式用來在項(xiàng)目中共用,在第一次裝入了字典樹后就可以在其他地方匹配錯(cuò)詞使用了。
這個(gè)是結(jié)合我具體使用,簡化了些代碼,如果只是分詞的話就是分詞那個(gè)實(shí)現(xiàn)方法就行了。最后分享就到這里吧,如有不對(duì)之處,請(qǐng)加以指正。
到此這篇關(guān)于C#實(shí)現(xiàn)前向最大匹、字典樹(分詞、檢索)的示例代碼的文章就介紹到這了,更多相關(guān)C# 前向最大匹、字典樹內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家!
相關(guān)文章
Unity UI實(shí)現(xiàn)拖拽旋轉(zhuǎn)
這篇文章主要為大家詳細(xì)介紹了Unity UI實(shí)現(xiàn)拖拽旋轉(zhuǎn),文中示例代碼介紹的非常詳細(xì),具有一定的參考價(jià)值,感興趣的小伙伴們可以參考一下2021-06-06基于C#實(shí)現(xiàn)端口掃描器(單線程和多線程)
本文主要介紹了基于C#分別通過單線程和多線程實(shí)現(xiàn)端口掃描,文中通過示例代碼介紹的非常詳細(xì),具有一定的參考價(jià)值,感興趣的小伙伴們可以參考一下2021-12-12使用Spire.Barcode程序庫生成二維碼的實(shí)例解析
這篇文章主要介紹了使用Spire.Barcode程序庫生成二維碼的相關(guān)資料,非常不錯(cuò),具有參考借鑒價(jià)值,需要的朋友可以參考下2016-12-12c#泛型學(xué)習(xí)詳解 創(chuàng)建線性鏈表
Visual C# 2.0 的一個(gè)最受期待的(或許也是最讓人畏懼)的一個(gè)特性就是對(duì)于泛型的支持。這篇文章將告訴你泛型用來解決什么樣的問題,以及如何使用它們來提高你的代碼質(zhì)量,還有你不必恐懼泛型的原因2014-01-01C#實(shí)現(xiàn)單例模式的幾種方法總結(jié)
這篇文章主要介紹了C#實(shí)現(xiàn)單例模式的幾種方法,文中通過示例代碼介紹的非常詳細(xì),對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值,需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧2021-01-01