Trie樹使用實例

bingchen 發(fā)布于2019-08-16 10:40 / 1562人閱讀

摘要：序本文簡單介紹下中的的使用。樹樹，又稱字典樹，單詞查找樹或者前綴樹，是一種用于快速檢索的多叉樹結(jié)構(gòu)。應(yīng)用經(jīng)常被搜索引擎系統(tǒng)用于文本詞頻統(tǒng)計。使用輸出數(shù)據(jù)結(jié)構(gòu)之樹

序

本文簡單介紹下apache collection4中的PatriciaTrie的使用。

Trie樹

Trie樹，又稱字典樹，單詞查找樹或者前綴樹，是一種用于快速檢索的多叉樹結(jié)構(gòu)。

應(yīng)用
經(jīng)常被搜索引擎系統(tǒng)用于文本詞頻統(tǒng)計。同時，它也是很多算法和復(fù)雜數(shù)據(jù)結(jié)構(gòu)的基礎(chǔ)，如后綴樹，AC自動機等

優(yōu)點
最大限度地減少無謂的字符串比較，查詢效率比哈希表高。

缺點
如果系統(tǒng)中存在大量字符串且這些字符串基本沒有公共前綴，則相應(yīng)的trie樹將非常消耗內(nèi)存，這也是trie樹的一個缺點。

maven

        
            org.apache.commons
            commons-collections4
            4.1

使用

@Test
    public void testContains(){
        PatriciaTrie t = new PatriciaTrie();

        t.put("ronak", 100.0);
        t.put("ronald", 90.0);
        t.put("rat", 50.0);
        t.put("robert", 200.0);
        t.put("bat", 44.0);
        t.put("batman", 440.0);


        System.out.println(t.containsKey("ronak"));
        System.out.println(t.selectKey("ro"));
        System.out.println(t.prefixMap("r"));
        System.out.println(t.prefixMap("ro"));
        System.out.println(t.prefixMap("ron"));
    }

輸出

true
robert
{rat=50.0, robert=200.0, ronak=100.0, ronald=90.0}
{robert=200.0, ronak=100.0, ronald=90.0}
{ronak=100.0, ronald=90.0}

doc

數(shù)據(jù)結(jié)構(gòu)之Trie樹

文章版權(quán)歸作者所有，未經(jīng)允許請勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。

轉(zhuǎn)載請注明本文地址：http://specialneedsforspecialkids.com/yun/70226.html

相關(guān)文章

javascript 前綴Trie

摘要：很容易看出，前綴最壞情況下的查找也快過二叉搜索樹。這種壓縮后的被喚作前綴壓縮，或直接叫前綴樹，字典樹。最長公共前綴和的最長公共前綴是，遍歷字典樹到字母時，此時這些單詞的公共前綴是。引子前綴Trie, 又叫字符Tire, trie來自單詞retrieval, 一開始念作tree，后來改念try，畢竟它與樹是不一樣的東西。網(wǎng)上許多文章都搞混了trie與樹。 trie是通過邊來儲存字符...

xiaochao 2019-08-22 14:05 評論0 收藏0
Trie樹 php 實現(xiàn)敏感詞過濾

摘要：在樹中，每個節(jié)點表示一個狀態(tài)，每條邊表示一個字符，從根節(jié)點到葉子節(jié)點經(jīng)過的邊即表示一個詞條。查找一個詞條最多耗費的時間只受詞條長度影響，因此的查找性能是很高的，跟哈希算法的性能相當(dāng)。 Last-Modified: 2019年5月10日15:25:35 參考文章 c++ 使用map實現(xiàn)Trie樹關(guān)鍵詞過濾擴展，用于檢查一段文本中是否出現(xiàn)敏感詞，基于Double-Array Trie...

王笑朝 2019-07-01 12:46 評論0 收藏0
208-實現(xiàn) Trie (前綴樹)

摘要：前言前綴樹是一種很常用的數(shù)據(jù)結(jié)構(gòu)，例如我們常用的數(shù)據(jù)庫索引。而關(guān)于前綴樹的介紹，由于中國有關(guān)于前綴樹的教程，我就不班門弄斧了，我的答案也是參考教程的思路去解答，希望可以給大家一個參考。下面是原題目實現(xiàn)一個前綴樹，包含和這三個操作。前言前綴樹是一種很常用的數(shù)據(jù)結(jié)構(gòu)，例如我們常用的數(shù)據(jù)庫索引。而關(guān)于前綴樹的介紹，由于LeetCode中國有關(guān)于前綴樹的教程，我就不班門弄斧了，我的答案也是...

antyiwei 2019-08-19 10:50 評論0 收藏0
[Leetcode] Implement Trie 實現(xiàn)前綴樹

摘要：壓縮前綴樹其實就是將所有只有一個子節(jié)點的節(jié)點合并成一個，以減少沒有意義的類似鏈表式的鏈接。然后我們開始遍歷這個前綴樹。 Implement Trie Implement a trie with insert, search, and startsWith methods. Note: You may assume that all inputs are consist of lowe...

jsliang 2019-08-14 12:28 評論0 收藏0
如何快速實現(xiàn)高并發(fā)短文檢索

摘要：問龍哥，還有什么更好，更輕量級的方案么龍哥用樹，數(shù)據(jù)會膨脹文檔數(shù)標(biāo)題長度這么多，標(biāo)題越長，文檔數(shù)越多，內(nèi)存占用越大。一、需求緣起某并發(fā)量很大，數(shù)據(jù)量適中的業(yè)務(wù)線需要實現(xiàn)一個標(biāo)題檢索的功能：（1）并發(fā)量較大，每秒20w次（2）數(shù)據(jù)量適中，大概200w數(shù)據(jù)（3）是否需要分詞：是（4）數(shù)據(jù)是否實時更新：否二、常見潛在解決方案及優(yōu)劣（1）數(shù)據(jù)庫搜索法具體方法：將標(biāo)題數(shù)據(jù)存放在數(shù)據(jù)庫中，使用...

URLOS 2019-06-28 13:51 評論0 收藏0