通過多路搜索樹提高檢索速度

package com.wretchant.lz78;import java.util.*;/** 多路英文單詞查找樹 */class Trie { private TrieNode root; public Trie() {root = new TrieNode();root.wordEnd = false; } public void insert(String word) {TrieNode node = root;for (int i = 0; i < word.length(); i++) { Character c = word.charAt(i); if (!node.childdren.containsKey(c)) {node.childdren.put(c, new TrieNode()); } node = node.childdren.get(c);}node.wordEnd = true; } public boolean search(String word) {TrieNode node = root;for (int i = 0; i < word.length(); i++) { Character c = word.charAt(i); if (!node.childdren.containsKey(c)) {return false; } node = node.childdren.get(c);}return node.wordEnd; }}class TrieNode { Map<Character, TrieNode> childdren; boolean wordEnd; public TrieNode() {childdren = new HashMap<Character, TrieNode>();wordEnd = false; }}/** 編碼表 */class Output { private Integer index; private Character character; Output(Integer index, Character character) {this.index = index;this.character = character; } public Integer getIndex() {return index; } public Character getCharacter() {return character; }}class LZencode { @FunctionalInterface interface Encode {List<Output> encode(String message); } /** 構建多路搜索樹 */ static Trie buildTree(Set<String> keys) {Trie trie = new Trie();keys.forEach(trie::insert);return trie; } public static final Encode ENCODE = message -> {// 構建壓縮后的編碼表List<Output> outputs = new ArrayList<>();Map<String, Integer> treeDict = new HashMap<>();int mLen = message.length();int i = 0;while (i < mLen) { Set<String> keySet = treeDict.keySet(); // 生成多路搜索樹 Trie trie = buildTree(keySet); char messageI = message.charAt(i); String messageIStr = String.valueOf(messageI); // 使用多路樹進行搜索 if (!trie.search(messageIStr)) {outputs.add(new Output(0, messageI));treeDict.put(messageIStr, treeDict.size() + 1);i++; } else if (i == mLen - 1) {outputs.add(new Output(treeDict.get(messageIStr), ’ ’));i++; } else {for (int j = i + 1; j < mLen; j++) { String substring = message.substring(i, j + 1); String str = message.substring(i, j); // 使用多路樹進行搜索 if (!trie.search(substring)) {outputs.add(new Output(treeDict.get(str), message.charAt(j)));treeDict.put(substring, treeDict.size() + 1);i = j + 1;break; } if (j == mLen - 1) {outputs.add(new Output(treeDict.get(substring), ’ ’));i = j + 1; }} }}return outputs; };}2、解壓縮算法的實現

package com.wretchant.lz78;import java.util.HashMap;import java.util.List;import java.util.Map;public class LZdecode { @FunctionalInterface interface Decode {/** @param outputs 編碼表 @return 解碼后的字符串 */String decode(List<Output> outputs); } /** 根據編碼表進行解碼 */ public static final Decode DECODE = (List<Output> outputs) -> {StringBuilder unpacked = new StringBuilder();Map<Integer, String> treeDict = new HashMap<>();for (Output output : outputs) { Integer index = output.getIndex(); Character character = output.getCharacter(); if (index == 0) {unpacked.append(character);treeDict.put(treeDict.size() + 1, character.toString());continue; } String term = '' + treeDict.get(index) + character; unpacked.append(term); treeDict.put(treeDict.size() + 1, term);}return unpacked.toString(); };}3、測試和使用

package com.wretchant.lz78;import java.io.InputStream;import java.util.List;import java.util.Scanner;import java.util.function.ToIntFunction;public class LZpack { public static final ToIntFunction<List<Output>> DICT_PRINT = outputs -> {outputs.forEach(output -> { System.out.println('index :' + output.getIndex() + ' char :' + output.getCharacter());});return 1; }; public static void main(String[] args) {Scanner scanner = new Scanner(System.in);System.out.println('Please input text ');String input = scanner.nextLine();LZencode.Encode encode = LZencode.ENCODE;List<Output> outputs = encode.encode(input);DICT_PRINT.applyAsInt(outputs); }}

測試結果如下

def compress(message): tree_dict, m_len, i = {}, len(message), 0 while i < m_len:# case Iif message[i] not in tree_dict.keys(): yield (0, message[i]) tree_dict[message[i]] = len(tree_dict) + 1 i += 1# case IIIelif i == m_len - 1: yield (tree_dict.get(message[i]), ’’) i += 1else: for j in range(i + 1, m_len):# case IIif message[i:j + 1] not in tree_dict.keys(): yield (tree_dict.get(message[i:j]), message[j]) tree_dict[message[i:j + 1]] = len(tree_dict) + 1 i = j + 1 break# case IIIelif j == m_len - 1: yield (tree_dict.get(message[i:j + 1]), ’’) i = j + 1def uncompress(packed): unpacked, tree_dict = ’’, {} for index, ch in packed:if index == 0: unpacked += ch tree_dict[len(tree_dict) + 1] = chelse: term = tree_dict.get(index) + ch unpacked += term tree_dict[len(tree_dict) + 1] = term return unpackedif __name__ == ’__main__’: messages = [’ABBCBCABABCAABCAAB’, ’BABAABRRRA’, ’AAAAAAAAA’] for m in messages:pack = compress(m)unpack = uncompress(pack)print(unpack == m)

到此這篇關于Java 實現LZ78壓縮算法的文章就介紹到這了,更多相關Java LZ78壓縮算法內容請搜索好吧啦網以前的文章或繼續瀏覽下面的相關文章希望大家以后多多支持好吧啦網！