JavaScript - Starting with the basics - Case Study: Data Structure Selection(Building the Huffman Code, Huffman coding of a DNA)

Think Perl 6

開発環境

• macOS Sierra - Apple (OS)
• Emacs (Text Editor)
• JavaScript (プログラミング言語)
• Node.js, Safari(JavaScript エンジン)
• Learning JavaScript [邦訳](参考書籍)

Think Perl 6: How to Think Like a Computer Scientist (Laurent Rosenfeld(著)、Allen B. Downey(著)、Oreilly & Associates Inc)の Part 1(Starting with the basics)、Chapter 11(Case Study: Data Structure Selection)の Building the Huffman Code、Exercise 11-9: Huffman coding of a DNA:1、2、3、4.を JavaScript で取り組んでみる。

Exercise 11-9: Huffman coding of a DNA:1、2、3、4.

2147-0.txt

コード(Emacs)

HTML5

<pre id="output0"></pre>
<input id="file0" type="file">

<button id="run0">run</button>
<button id="clear0">clear</button>

<script src="sample9.js"></script>

JavaScript

let btn0 = document.querySelector('#run0'),
    btn1 = document.querySelector('#clear0'),
    pre0 = document.querySelector('#output0'),
    input_file0 = document.querySelector('#file0'),
    p = (x) => pre0.textContent += x + '\n',
    range = (start, end, step=1) => {
        let result = [];

        for (let i = start; i < end; i += 1) {
            result.push(i);
        }
        return result;
    },
    pObj = (obj) => Object.keys(obj).forEach((k) => p(`${k}: ${obj[k]}`));

let reader = new FileReader(),
    encodeMorseHuffmanTable = (s, huffmanTable) =>
    s.split('')
    .map((letter) => huffmanTable[letter])
    .join(''),
    decodeMorseHuffmanTable = (s, huffmanTable) => {
        let result = '',
            table = {},
            morse = '';
        
        Object.keys(huffmanTable)
            .forEach((letter) => table[huffmanTable[letter]] = letter);

        s.split('')
            .forEach((letter) => {
                morse += letter;
                if (table[morse]) {
                    result += table[morse];
                    morse = '';
                }
            });

        return result;
    };

reader.onload = () => {
    p('3.');
    let s = reader.result;
        frequency = {};

    s.split('')
        .forEach((c) => {
            if (frequency[c]) {
                frequency[c] += 1;
            } else {
                frequency[c] = 1;
            }
        });

    let frequencyArray = Object.keys(frequency)
        .map((k) => {
            return {letter:k, n:frequency[k]}
        })
        .sort((x, y) => x.n - y.n),
        huffmanTree = {};

    for (;frequencyArray.length > 2;) {
        let a = frequencyArray.shift(),
            b = frequencyArray.shift(),
            t = a.letter + b.letter,
            o = {letter:t, n:a.n + b.n}

        huffmanTree[a.letter] = `[${t}].`;
        huffmanTree[b.letter] = `[${t}]-`;
        frequencyArray.push(o);
        frequencyArray.sort((x, y) => x.n - y.n);
    }
    let a = frequencyArray.shift(),
        b = frequencyArray.shift(),
        t = a.letter + b.letter,
        o = {letter:t, n:a.n + b.n}

    huffmanTree[a.letter] = `.`;
    huffmanTree[b.letter] = `-`;
    
    let huffmanTable = {};

    Object.keys(frequency)
        .filter((x) => x.length === 1)
        .forEach((letter) => {
            let result = '';
                val = huffmanTree[letter];

            for (;val.length > 1;) {
                result =  val[val.length - 1]+ result;
                val = huffmanTree[val.substring(1, val.length - 2)];
            }
            
            huffmanTable[letter] = val + result;
        });
    let encoded = encodeMorseHuffmanTable(s, huffmanTable);
    p(encoded);

    p('4.');
    let decoded = decodeMorseHuffmanTable(encoded, huffmanTable);

    p(decoded === s);
};

input_file0.onchange = () => reader.readAsText(input_file0.files[0]);

let output = () => {
    p('1.');
    let dna = 'CCTATCCTCGACTCCAGTCCA',
        frequency = {};

    dna.split('')
        .forEach((c) => {
            if (frequency[c]) {
                frequency[c] += 1;
            } else {
                frequency[c] = 1;
            }
        });

    let frequencyArray = Object.keys(frequency)
        .map((k) => {
            return {letter:k, n:frequency[k]}
        })
        .sort((x, y) => x.n - y.n),
        huffmanTree = {};

    for (;frequencyArray.length > 2;) {
        let a = frequencyArray.shift(),
            b = frequencyArray.shift(),
            t = a.letter + b.letter,
            o = {letter:t, n:a.n + b.n}

        huffmanTree[a.letter] = `[${t}].`;
        huffmanTree[b.letter] = `[${t}]-`;
        frequencyArray.push(o);
        frequencyArray.sort((x, y) => x.n - y.n);
    }
    let a = frequencyArray.shift(),
        b = frequencyArray.shift(),
        t = a.letter + b.letter,
        o = {letter:t, n:a.n + b.n}

    huffmanTree[a.letter] = `.`;
    huffmanTree[b.letter] = `-`;
    
    pObj(huffmanTree);

    let huffmanCode = {};

    Object.keys(frequency)
        .filter((x) => x.length === 1)
        .forEach((letter) => {
            let result = '';
                val = huffmanTree[letter];

            for (;val.length > 1;) {
                result =  val[val.length - 1]+ result;
                val = huffmanTree[val.substring(1, val.length - 2)];
            }
            
            huffmanCode[letter] = val + result;
        });
    pObj(huffmanCode);

    p('2.');
    let s = 'think perl 6, think python, think javascript';

    frequency = {};

    s.split('')
        .forEach((c) => {
            if (frequency[c]) {
                frequency[c] += 1;
            } else {
                frequency[c] = 1;
            }
        });

    frequencyArray = Object.keys(frequency)
        .map((k) => {
            return {letter:k, n:frequency[k]}
        })
        .sort((x, y) => x.n - y.n),
    
    huffmanTree = {};

    for (;frequencyArray.length > 2;) {
        let a = frequencyArray.shift(),
            b = frequencyArray.shift(),
            t = a.letter + b.letter,
            o = {letter:t, n:a.n + b.n}

        huffmanTree[a.letter] = `[${t}].`;
        huffmanTree[b.letter] = `[${t}]-`;
        frequencyArray.push(o);
        frequencyArray.sort((x, y) => x.n - y.n);
    }
    a = frequencyArray.shift(),
    b = frequencyArray.shift(),
    t = a.letter + b.letter,
    o = {letter:t, n:a.n + b.n}

    huffmanTree[a.letter] = `.`;
    huffmanTree[b.letter] = `-`;
    
    pObj(huffmanTree);

    huffmanCode = {};

    Object.keys(frequency)
        .filter((x) => x.length === 1)
        .forEach((letter) => {
            let result = '';
                val = huffmanTree[letter];

            for (;val.length > 1;) {
                result =  val[val.length - 1]+ result;
                val = huffmanTree[val.substring(1, val.length - 2)];
            }
            
            huffmanCode[letter] = val + result;
        });
    pObj(huffmanCode);
};
let clear = () => pre0.textContent = '';

btn0.onclick = output;
btn1.onclick = clear;

output();