欧美一区二区三区老妇人-欧美做爰猛烈大尺度电-99久久夜色精品国产亚洲a-亚洲福利视频一区二区

TrieTree介紹及其C#實現(xiàn)

作者：Tony Qu

創(chuàng)新互聯(lián)建站長期為上1000家客戶提供的網(wǎng)站建設(shè)服務(wù)，團(tuán)隊從業(yè)經(jīng)驗10年，關(guān)注不同地域、不同群體，并針對不同對象提供差異化的產(chǎn)品和服務(wù)；打造開放共贏平臺，與合作伙伴共同營造健康的互聯(lián)網(wǎng)生態(tài)環(huán)境。為涪城企業(yè)提供專業(yè)的成都做網(wǎng)站、成都網(wǎng)站建設(shè)，涪城網(wǎng)站改版等技術(shù)服務(wù)。擁有10余年豐富建站經(jīng)驗和眾多成功案例,為您定制開發(fā)。

 

在自然語言處理（NLP）研究中，NGram是最基本但也是最有用的一種比對方式，這里的N是需要比對的字符串的長度，而今天我介紹的TrieTree，正是和NGram密切相關(guān)的一種數(shù)據(jù)結(jié)構(gòu)，有人稱之為字典樹。TrieTree簡單的說是一種多叉樹，每個節(jié)點保存一個字符，這么做的好處是當(dāng)我們要做NGram比對時，只需要直接從樹的根節(jié)點開始沿著某個樹叉遍歷下去，就能完成比對；如果沒找到，停止本次遍歷。這話講得有些抽象，我們來看一個實際的例子。

假設(shè)我們現(xiàn)在詞庫里面有以下一些詞：

上海市
上海灘
上海人
上海公司
北京
北斗星
楊柳
楊浦區(qū)

Trie Tree介紹及其C#實現(xiàn)

如圖所示：掛在根節(jié)點上的字有上、北、楊，

如果我們現(xiàn)在對“上海市楊浦區(qū)”這個詞做3gram就有上海市、海市楊、市楊浦、楊浦區(qū)，現(xiàn)在我們要知道哪些詞是能夠被這個字典識別的，通常我們可以用NGram來做分詞。有了這顆樹，我們只需要依次取每個字符，從根開始進(jìn)行比對，比如上海市，我們能夠匹配 上->海->市，這個路徑，所以匹配；比如海市楊，由于沒有“海”字掛在根節(jié)點上，所以停止；市楊浦也無法匹配；最終匹配楊浦區(qū)，得到 楊->浦->區(qū) 這個路徑，匹配。

最終我們可以把“上海市楊浦區(qū)”切分為 上海市|楊浦區(qū)。

盡管TrieTree要比普通字符串?dāng)?shù)組節(jié)省很多時間，但這并不是沒有代價的，因為你要先根據(jù)字典構(gòu)建這棵樹，這個代價并不低，當(dāng)然對于某個應(yīng)用來說一旦TrieTree構(gòu)建完成就可以重復(fù)使用，所以針對大規(guī)模比對來說，性能提升還是很客觀的。

下面是TrieTree的C#實現(xiàn)。

   public class TrieTree
    {
        TrieNode _root = null;

        private TrieTree()
        {
            _root = new TrieNode(char.MaxValue,0);
            charCount = 0;
        }
        static TrieTree _instance = null;
        public static TrieTree GetInstance()
        {
            if (_instance == null)
            {
                _instance = new TrieTree();
            }
            return _instance;
        }
        public TrieNode Root 
        {
            get { return _root; }
        }
        public void AddWord(char ch)
        {
            TrieNode newnode=_root.AddChild(ch);
            newnode.IncreaseFrequency();
            newnode.WordEnded = true;
        }
        int charCount;
        public void AddWord(string word)
        {
            if (word.Length == 1)
            {
                AddWord(word[0]);
                charCount++;
            }
            else
            { 
                char[] chars=word.ToCharArray();
                TrieNode node = _root;
                charCount += chars.Length;
                for (int i = 0; i < chars.Length; i++)
                {
                    TrieNode newnode=node.AddChild(chars[i]);
                    newnode.IncreaseFrequency();
                    node = newnode;
                }
                node.WordEnded = true;
            }
        }
        public int GetFrequency(char ch)
        {
            TrieNode matchedNode = _root.Children.FirstOrDefault(n => n.Character == ch);
            if (matchedNode == null)
            {
                return 0;
            }
            return matchedNode.Frequency;             
        }
        public int GetFrequency(string word)
        {
            if (word.Length == 1)
            {
                return GetFrequency(word[0]); 
            }
            else
            {
                char[] chars = word.ToCharArray();
                TrieNode node = _root;
                for (int i = 0; i < chars.Length; i++)
                {
                    if (node.Children == null)
                        return 0;
                    TrieNode matchednode = node.Children.FirstOrDefault(n => n.Character == chars[i]);
                    if (matchednode == null)
                    {
                        return 0;
                    }
                    node = matchednode;
                }
                if (node.WordEnded == true)
                    return node.Frequency;
                else
                    return -1;
            }
        }
    }

這里我們使用了單例模式，因為TrieTree類似緩存，不需要重復(fù)創(chuàng)建。下面是TreeNode的實現(xiàn)：

    public class TrieNode
    {
        public TrieNode(char ch,int depth)
        {
            this.Character=ch;
            this._depth=depth;
        }


        public char Character;

        int _depth;
        public int Depth
        {
            get{return _depth;}
        }

        TrieNode _parent=null;
        public TrieNode Parent 
        {
            get { return _parent; }
            set { _parent = value; }
        }

        public bool WordEnded = false;


        HashSet<TrieNode> _children=null;
        public HashSet<TrieNode> Children
        {
            get { return _children; }
        }

        public TrieNode GetChildNode(char ch)
        {
            if (_children != null)
                return _children.FirstOrDefault(n => n.Character == ch);
            else
                return null;
        }

        public TrieNode AddChild(char ch)
        {
            TrieNode matchedNode=null;
            if (_children != null)
            {
                matchedNode = _children.FirstOrDefault(n => n.Character == ch);
            }
            if (matchedNode != null)    //found the char in the list
            {
                //matchedNode.IncreaseFrequency();
                return matchedNode;
            }
            else
            {   //not found
                TrieNode node = new TrieNode(ch, this.Depth + 1);
                node.Parent = this;
                //node.IncreaseFrequency();
                if (_children == null)
                    _children = new HashSet<TrieNode>();
                _children.Add(node);
                return node;
            }
        }

        int _frequency = 0;
        public int Frequency
        {
            get { return _frequency; }
        }

        public void IncreaseFrequency()
        {
            _frequency++;
        }

        public string GetWord()
        { 
            TrieNode tmp=this;
            string result = string.Empty;
            while(tmp.Parent!=null) //until root node
            {
                result = tmp.Character + result;
                tmp = tmp.Parent;
            }
            return result;
        }

        public override string ToString()
        {
            return Convert.ToString(this.Character);
        }
    }

最后提供一個能工作的演示代碼，供大家參考，點擊這里下載。

名稱欄目：TrieTree介紹及其C#實現(xiàn)
本文URL：http://chinadenli.net/article42/jgghec.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供品牌網(wǎng)站設(shè)計、App設(shè)計、網(wǎng)站內(nèi)鏈、網(wǎng)站排名、響應(yīng)式網(wǎng)站、網(wǎng)站建設(shè)

廣告

聲明：本網(wǎng)站發(fā)布的內(nèi)容（圖片、視頻和文字）以用戶投稿、用戶轉(zhuǎn)載內(nèi)容為主，如果涉及侵權(quán)請盡快告知，我們將會在第一時間刪除。文章觀點不代表本網(wǎng)站立場，如需處理請聯(lián)系客服。電話：028-86922220；郵箱：631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載，或轉(zhuǎn)載時需注明來源： 創(chuàng)新互聯(lián)

成都做網(wǎng)站