Skip to content

Instantly share code, notes, and snippets.

@ArrayIterator

ArrayIterator/Lzw.js

Last active July 14, 2020 04:04
Show Gist options
  • Save ArrayIterator/dd83f87bca5dcea3c35dacd336fe580d to your computer and use it in GitHub Desktop.
Save ArrayIterator/dd83f87bca5dcea3c35dacd336fe580d to your computer and use it in GitHub Desktop.
Download ZIP

Revisions

  1. ArrayIterator revised this gist Jul 14, 2020. 1 changed file with 1 addition and 1 deletion.
    2 changes: 1 addition & 1 deletion Lzw.php
    View file
    Original file line number Diff line number Diff line change
    @@ -66,7 +66,7 @@ public function decompress(string $compressed) : string
    $i = 1;
    for (; $i < $length; $i++) {
    $current = $this->substr($compressed, $i, 1);
    $currCode = mb_ord($current);
    $currCode = $this->ord($current);
    if ($currCode < 256) {
    $phrase = $current;
    } else {
  2. ArrayIterator revised this gist Jul 10, 2020. 1 changed file with 2 additions and 1 deletion.
    3 changes: 2 additions & 1 deletion Lzw.js
    View file
    Original file line number Diff line number Diff line change
    @@ -11,10 +11,11 @@
    }
    win.lzw = {
    compress: function (e) {
    e = convert_compat_string(e).split('');
    e = convert_compat_string(e);
    if (e.length < 2) {
    return e;
    }
    e = e.split('');
    var currChar,
    dict = {},
    out = '',
  3. ArrayIterator created this gist Jul 10, 2020.
    71 changes: 71 additions & 0 deletions Lzw.js
    View file
    Original file line number Diff line number Diff line change
    @@ -0,0 +1,71 @@
    /*!
    * @link https://en.wikipedia.org/wiki/Lempel%E2%80%93Ziv%E2%80%93Welch
    * @license MIT
    */
    (function(win) {
    function convert_compat_string(e) {
    if (e === undefined || e === null || typeof e === 'boolean') {
    e = e ? '1' : '';
    }
    return String(e);
    }
    win.lzw = {
    compress: function (e) {
    e = convert_compat_string(e).split('');
    if (e.length < 2) {
    return e;
    }
    var currChar,
    dict = {},
    out = '',
    phrase = e[0],
    code = 256,
    i = 1;
    for (; i < e.length; i++) {
    currChar = e[i];
    if (dict[phrase + currChar] !== undefined) {
    phrase += currChar;
    } else {
    out += (phrase.length > 1 ? String.fromCharCode(dict[phrase]) : phrase[0]);
    dict[phrase + currChar] = code;
    code++;
    phrase = currChar;
    }
    }
    e = null;
    dict = dict[phrase];
    out += (dict !== undefined && phrase.length > 1 ? String.fromCharCode(dict) : phrase);
    return out;
    },
    decompress: function (e) {
    e = convert_compat_string(e);
    if (e.length < 2) {
    return e;
    }
    var currCode,
    dict = {},
    currChar = e[0],
    oldPhrase = currChar,
    out = currChar,
    code = 256,
    phrase,
    i = 1;
    for (; i < e.length; i++) {
    currCode = e[i].charCodeAt(0);
    if (currCode < 256) {
    phrase = e[i];
    } else {
    phrase = dict[currCode] ? dict[currCode] : (oldPhrase + currChar);
    }
    out += phrase;
    currChar = phrase.charAt(0);
    dict[code] = oldPhrase + currChar;
    code++;
    oldPhrase = phrase;
    }

    e = dict = null;
    return out;
    }
    };
    })(self);
    109 changes: 109 additions & 0 deletions Lzw.php
    View file
    Original file line number Diff line number Diff line change
    @@ -0,0 +1,109 @@
    <?php
    declare(strict_types=1);

    namespace ArrayIterator\App\Data\Compression;

    /**
    * Class Lzw
    * @package ArrayIterator\App\Data\Compression
    * @link https://en.wikipedia.org/wiki/Lempel%E2%80%93Ziv%E2%80%93Welch
    * @license MIT
    */
    class Lzw
    {
    /**
    * @param string $uncompressed
    * @return string
    */
    public function compress(string $uncompressed) : string
    {
    $length = $this->strLen($uncompressed);
    if ($length < 2) {
    return $uncompressed;
    }

    $currChar = null;
    $dict = [];
    $out = '';
    $phrase = $this->substr($uncompressed, 0, 1);
    $code = 256;
    $i = 1;
    for (; $i < $length; $i++) {
    $currChar = $this->substr($uncompressed, $i, 1);
    if (isset($dict[$phrase . $currChar])) {
    $phrase .= $currChar;
    } else {
    $out .= ($this->strLen($phrase) > 1 ? $this->chr($dict[$phrase]) : $this->substr($phrase, 0, 1));
    $dict[$phrase . $currChar] = $code;
    $code++;
    $phrase = $currChar;
    }
    }

    $uncompressed = null;
    $dict = $dict[$phrase]??null;
    $out .= ($dict !== null && $this->strLen($phrase) > 1 ? $this->chr($dict) : $phrase);
    return $out;
    }

    /**
    * @param string $compressed
    * @return string
    */
    public function decompress(string $compressed) : string
    {
    $length = $this->strLen($compressed);
    if ($length < 2) {
    return $compressed;
    }
    $currCode = null;
    $dict = [];
    $currChar = $this->substr($compressed, 0, 1);
    $oldPhrase = $currChar;
    $out = $currChar;
    $code = 256;
    $phrase = null;
    $i = 1;
    for (; $i < $length; $i++) {
    $current = $this->substr($compressed, $i, 1);
    $currCode = mb_ord($current);
    if ($currCode < 256) {
    $phrase = $current;
    } else {
    $phrase = isset($dict[$currCode]) ? $dict[$currCode] : ($oldPhrase . $currChar);
    }

    $out .= $phrase;
    $currChar = $this->substr($phrase, 0, 1);
    $dict[$code] = $oldPhrase . $currChar;
    $code++;
    $oldPhrase = $phrase;
    }

    return $out;
    }

    /*!
    | MB STRING
    ---------------------------------------------------------------- */

    protected function substr(string $string, $start, ?int $length = null)
    {
    return mb_substr($string, $start, $length, 'UTF-8');
    }

    protected function strLen(string $string)
    {
    return mb_strlen($string, 'UTF-8');
    }

    protected function ord(string $string)
    {
    return mb_ord($string, 'UTF-8');
    }

    protected function chr(int $code)
    {
    return mb_chr($code, 'UTF-8');
    }
    }