Trie樹使用實例

bingchen 發布于2019-08-16 10:40 / 1573人閱讀

摘要：序本文簡單介紹下中的的使用。樹樹，又稱字典樹，單詞查找樹或者前綴樹，是一種用于快速檢索的多叉樹結構。應用經常被搜索引擎系統用于文本詞頻統計。使用輸出數據結構之樹

序

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

Trie樹

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

應用
經常被搜索引擎系統用于文本詞頻統計。同時，它也是很多算法和復雜數據結構的基礎，如后綴樹，AC自動機等

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

缺點
如果系統中存在大量字符串且這些字符串基本沒有公共前綴，則相應的trie樹將非常消耗內存，這也是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

數據結構之Trie樹

文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。

轉載請注明本文地址：http://m.specialneedsforspecialkids.com/yun/70226.html

javascript 前綴Trie

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

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

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

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

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

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

摘要：壓縮前綴樹其實就是將所有只有一個子節點的節點合并成一個，以減少沒有意義的類似鏈表式的鏈接。然后我們開始遍歷這個前綴樹。 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
如何快速實現高并發短文檢索

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

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