Java中關於字典樹的算法實現
字典樹(前綴樹)算法實現
前言
字典樹,又稱單詞查找樹,是一個典型的 一對多的字符串匹配算法。“一”指的是一個模式串,“多”指的是多個模板串。字典樹經常被用來統計、排序和保存大量的字符串。它利用字符串的公共前綴來減少查詢時間,最大限度地減少無謂的字符串比較。
字典樹有3個基本性質:
- 根節點不包含字符,其餘的每個節點都包含一個字符;
- 從根節點到某一節點,路徑上經過的字符連接起來,為該節點對應的字符串;
- 每個節點的所有子節點包含的字符都不相同。
pass
參數:代表從這個點經過的單詞數量。root根即就是整棵樹有多少單詞。
end
參數: 代表在這個點結束的單詞有幾個。例如: 上圖有兩個 hello,在o結點的end參數就是2。
實現的基本功能: 增刪查。
算法解析
首先是結點的參數:
public class Node { public int pass; public int end; public Node[] nexts; //下一個字母的地址 public Node() { pass = 0; end = 0; nexts = new Node[26]; //這裡我們就以小寫字母為例 } }
下面就是基本功能的實現:
import java.util.Scanner; public class Main { public static void main(String[] args) { String[] arr = {"hello", "hello"}; Trie root = new Trie(); for (int i = 0; i < arr.length; i++) { root.addWord(arr[i]); } //root.delWord("hello"); Scanner sc = new Scanner(System.in); String s = sc.nextLine(); if (root.searchWord(s) != 0) { System.out.println("該字典樹有這個" + s + " 單詞"); } } public static class Node { public int pass; public int end; public Node[] nexts; //下一個字母的地址 public Node() { pass = 0; end = 0; nexts = new Node[26]; } } public static class Trie { private Node root; public Trie() { root = new Node(); } //增加 public void addWord(String str) { char[] arr = str.toCharArray(); root.pass++; Node node = root; for (char s : arr) { int index = s - 'a'; //以相應的ASCII碼值差值,進行數組的下標存儲 if (node.nexts[index] == null) { node.nexts[index] = new Node(); } node = node.nexts[index]; node.pass++; //經過這個結點,pass就加1 } node.end++; } //刪除 public void delWord(String str) { //刪除之前,應該查詢一下這顆樹有沒有這個單詞 while (searchWord(str) != 0) { char[] arr = str.toCharArray(); Node node = root; node.pass--; for (int i = 0; i < str.length(); i++) { int index = arr[i] - 'a'; node = node.nexts[index]; node.pass--; } node.end--; } } //查找 public int searchWord(String str) { if (str == null) { return 0; } char[] arr = str.toCharArray(); Node node = root; for (int i = 0; i < str.length(); i++) { int index = arr[i] - 'a'; if (node.nexts[index] == null) { return 0; } node = node.nexts[index]; } return node.end; //返回最後那一個結點的end值即可 } } }
到此這篇關於Java中關於字典樹的算法實現的文章就介紹到這瞭,更多相關Java 字典樹內容請搜索WalkonNet以前的文章或繼續瀏覽下面的相關文章希望大傢以後多多支持WalkonNet!
推薦閱讀:
- 詳解Java中字典樹(Trie樹)的圖解與實現
- 詳解Java中AC自動機的原理與實現
- Java數據結構之AC自動機算法的實現
- Java反轉數組輸出實例代碼
- Java數據結構之KMP算法詳解以及代碼實現