FilesExpand file tree

 master

/

HEncoder.java

Copy path

Blame

More file actions

Blame

More file actions

Latest commit

 

History

History

History

108 lines (86 loc) · 2.32 KB

 master

/

HEncoder.java

Copy path

Top

File metadata and controls

• Code
• Blame

108 lines (86 loc) · 2.32 KB

Raw

Copy raw file

Download raw file

Open symbols panel

Edit and raw actions

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

34

35

36

37

38

39

40

41

42

43

44

45

46

47

48

49

50

51

52

53

54

55

56

57

58

59

60

61

62

63

64

65

66

67

68

69

70

71

72

73

74

75

76

77

78

79

80

81

82

83

84

85

86

87

88

89

90

91

92

93

94

95

96

97

98

99

100

101

102

103

104

105

106

107

108

import java.util.ArrayList;

import java.util.Comparator;

import java.util.HashMap;

public class HEncoder {

public HashMap<Character, String> encoder = new HashMap<>(); // in order to encode

public HashMap<String, Character> decoder = new HashMap<>(); // in order to decode

private static class Node {

Character ch;

Integer freq;

Node left;

Node right;

public static final Nodecomparator Ctor = new Nodecomparator();

public static class Nodecomparator implements Comparator<Node> {

@Override

public int compare(Node o1, Node o2) {

return o2.freq - o1.freq;

}

}

}

public HEncoder(String feeder) {

// 1. freq map

HashMap<Character, Integer> freqmap = new HashMap<>();

for (int i = 0; i < feeder.length(); ++i) {

char ch = feeder.charAt(i);

if (freqmap.containsKey(ch)) {

freqmap.put(ch, freqmap.get(ch) + 1);

} else {

freqmap.put(ch, 1);

}

}

// 2. prepare the heap from keyset

genericheap<Node> heap = new genericheap<Node>(Node.Ctor);

ArrayList<Character> k = new ArrayList<>(freqmap.keySet());

for (Character c : k) {

Node n = new Node();

n.ch = c;

n.left = null;

n.right = null;

n.freq = freqmap.get(c);

heap.add(n);

}

// 3.Prepare tree, remove two , merge, add it back

Node fn = new Node();

while (heap.size() != 1) {

Node n1 = heap.removeHP();

Node n2 = heap.removeHP();

fn = new Node();

fn.freq = n1.freq + n2.freq;

fn.left = n1;

fn.right = n2;

heap.add(fn);

}

// 4. traverse

traverse(heap.removeHP(), "");

}

private void traverse(Node node, String osf) {

if (node.left == null && node.right == null) {

encoder.put(node.ch, osf);

decoder.put(osf, node.ch);

return;

}

traverse(node.left, osf + "0");

traverse(node.right, osf + "1");

}

// compression work done here

public String compress(String str) {

String rv = "";

for (int i = 0; i < str.length(); ++i) {

rv += encoder.get(str.charAt(i));

}

return rv;

}

//in order to decompress

public String decompress(String str) {

String s = "";

String code = "";

for (int i = 0; i < str.length(); ++i) {

code += str.charAt(i);

if (decoder.containsKey(code)) {

s += decoder.get(code);

code = "";

}

}

return s;

}

}