Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- class Node {
- constructor(val) {
- this.value = val;
- this.child = [];
- }
- addLeft(node) {this.child[0] = node}
- addRight(node) {this.child[1] = node}
- }
- function count(str) {
- // strの中のそれぞれの文字の出現回数をカウントする
- const counter = new Map();
- for (const s of str) counter.set(s, counter.has(s) ? counter.get(s) + 1 : 0);
- return [...counter.entries()];
- }
- function createHuffmanTree(pairs) {
- // pairs:= [['a', 2], ['b', 2], ...]
- pairs = pairs.map(item => [new Node(item[0]), item[1]]);
- while (pairs.length > 1) {
- let min1 = 0, min2 = 1; // min1は最小要素のインデックス、min2は二番目へのインデックス
- if (pairs[min1][1] > pairs[min2][1]) [min1, min2] = [min2, min1];
- for (let i = 2, _i = pairs.length; i < _i; i++) {
- if (pairs[i][1] < pairs[min1][1]) {
- [min1, min2] = [i, min1];
- } else if (pairs[i][1] < pairs[min2][1]) {
- min2 = i;
- }
- }
- const parent = new Node(null);
- parent.addLeft(pairs[min1][0]);
- parent.addRight(pairs[min2][0]);
- if (min1 > min2) [min1, min2] = [min2, min1]; // 下でpairsからmin1、min2の要素を取り除くときにspliceを使うため、必要なら入れ替え
- pairs.push([parent, pairs[min1][1] + pairs[min2][1]]);
- pairs.splice(min2, 1); pairs.splice(min1, 1);
- }
- return pairs[0][0];
- }
- function HuffmanCoding(tree, dic = {}, s = '') {
- if (tree.value !== null) dic[tree.value] = s;
- if (tree.child[0]) dic = HuffmanCoding(tree.child[0], dic, s + '0');
- if (tree.child[1]) dic = HuffmanCoding(tree.child[1], dic, s + '1');
- return dic;
- }
- const test = 'Lorem ipsum dolor sit amet, consectetur adipiscing elit';
- const huffmanCode = HuffmanCoding(createHuffmanTree(count(test)));
- console.log(huffmanCode);
- console.log([...test].map(s => huffmanCode[s]).join(''));
- console.log(([...test].map(s => huffmanCode[s]).join('').length / 8) + 'byte');
- Another Scripts from here :
- http://bit.ly/2g63Tj5
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement