亚洲精品久久久中文字幕-亚洲精品久久片久久-亚洲精品久久青草-亚洲精品久久婷婷爱久久婷婷-亚洲精品久久午夜香蕉

更多QQ空间微信QQ好友腾讯朋友复制链接
您的位置:首頁/技術文章
文章詳情頁

Java 實現LZ78壓縮算法的示例代碼

【字号: 作者:豬豬瀏覽:84日期:2022-08-13 10:17:23
LZ78 壓縮算法的 Java 實現1、壓縮算法的實現

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

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); }}

測試結果如下

Java 實現LZ78壓縮算法的示例代碼

4、Python 版本的實現代碼

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壓縮算法內容請搜索好吧啦網以前的文章或繼續瀏覽下面的相關文章希望大家以后多多支持好吧啦網!

標簽: Java
相關文章:
主站蜘蛛池模板: 国产精品亚洲片夜色在线 | 78m成人亚洲 | 嫩草视频在线观看免费 | 99这里只有精品66视频 | 免费一级特黄a | 岛国片欧美一级毛片 | 欧美成人亚洲高清在线观看 | 国产在线xvideos | 欧美亚洲三级 | 做a小视频| 亚洲国产美女 | 国产精品久久久久久亚洲小说 | 久久免费99精品久久久久久 | 成人免费片 | 免费一级毛片不卡不收费 | 久久综合图片 | 欧美精品午夜毛片免费看 | 久草亚洲视频 | 国产玖玖玖精品视频 | 精品在线91 | 免费看三级黄色片 | 成人在线视频观看 | 亚洲免费一 | 蜜桃视频一区二区三区四区 | 久久国产乱子伦精品免费强 | 久99久热只有精品国产99 | 这里有精品 | 国产精品无码久久综合网 | 色片在线播放 | 国产成人亚洲精品一区二区在线看 | 亚洲美日韩| 亚洲精品二区 | 中国一级特黄特爽刺激大片 | 成人在线精品 | 国产在线一卡 | 亚洲免费网| 国产精品高清在线观看 | 日韩亚洲欧美一区噜噜噜 | 欧美成人亚洲高清在线观看 | 啪啪激情综合 | 嫩草免费视频 |