Question

How to perform high‑performance reversible text compression using a word dictionary in PHP

Answer 1

/*
    =====================================================================
    High‑Performance Reversible Text Compression Using a Word Dictionary
    ---------------------------------------------------------------------
    This program compresses text by replacing repeated words with tokens
    like @0, @1, @2... and stores each unique word in a dictionary.

    The compressed text is fully reversible.

    WHY THIS VERSION IS FAST (PHP):
    -------------------------------
    • Uses associative arrays for O(1) average lookup.
    • Uses indexed arrays for compact dictionary storage.
    • Uses manual scanning instead of regex (much faster).
    • Clean, idiomatic, modern PHP design.

    OUTPUT EXAMPLE:
        Original:      this is is a test test compression string string test
        Compressed:    @0 @1 @1 @2 @3 @3 @4 @5 @5 @3
        Decompressed:  this is is a test test compression string string test
    =====================================================================
*/


// ---------------------------------------------------------------------
// Dictionary structure: indexed array + associative array
// ---------------------------------------------------------------------
class WordDictionary {
    public array $words = [];      // index → word
    public array $indexMap = [];   // word → index
}


// ---------------------------------------------------------------------
// Find or add a word to the dictionary (O(1) average)
// ---------------------------------------------------------------------
function findOrAdd(WordDictionary $dict, string $word): int {
    if (isset($dict->indexMap[$word])) {
        return $dict->indexMap[$word];
    }

    $newIndex = count($dict->words);
    $dict->words[] = $word;
    $dict->indexMap[$word] = $newIndex;

    return $newIndex;
}


// ---------------------------------------------------------------------
// Compress text into @ID tokens
// ---------------------------------------------------------------------
function compress(string $input, WordDictionary $dict): string {
    $out = '';
    $len = strlen($input);
    $i = 0;

    while ($i < $len) {

        $c = $input[$i];

        // Pass punctuation/spaces directly
        if (!ctype_alnum($c)) {
            $out .= $c;
            $i++;
            continue;
        }

        // Extract word
        $start = $i;
        while ($i < $len && ctype_alnum($input[$i])) {
            $i++;
        }

        $word = substr($input, $start, $i - $start);

        // Get dictionary index
        $id = findOrAdd($dict, $word);

        // Write token
        $out .= '@' . $id;
    }

    return $out;
}


// ---------------------------------------------------------------------
// Decompress @ID tokens back into original text
// ---------------------------------------------------------------------
function decompress(string $compressed, WordDictionary $dict): string {
    $out = '';
    $len = strlen($compressed);
    $i = 0;

    while ($i < $len) {

        $c = $compressed[$i];

        // Token?
        if ($c === '@') {
            $i++;
            $id = 0;

            // Parse digits
            while ($i < $len && ctype_digit($compressed[$i])) {
                $id = $id * 10 + (ord($compressed[$i]) - ord('0'));
                $i++;
            }

            if ($id >= 0 && $id < count($dict->words)) {
                $out .= $dict->words[$id];
            }
        }
        else {
            // Pass punctuation/spaces
            $out .= $c;
            $i++;
        }
    }

    return $out;
}


// ---------------------------------------------------------------------
// Main
// ---------------------------------------------------------------------
$original =
    "this is is a test test compression string string test " .
    "this is a test compression";

$dict = new WordDictionary();

$compressed = compress($original, $dict);
$decompressed = decompress($compressed, $dict);

echo "Original:      \"$original\"\n";
echo "Compressed:    \"$compressed\"\n";
echo "Decompressed:  \"$decompressed\"\n\n";

echo "Dictionary:\n";
foreach ($dict->words as $i => $word) {
    echo "  @$i => $word\n";
}



/*
run:

Original:      "this is is a test test compression string string test this is a test compression"
Compressed:    "@0 @1 @1 @2 @3 @3 @4 @5 @5 @3 @0 @1 @2 @3 @4"
Decompressed:  "this is is a test test compression string string test this is a test compression"

Dictionary:
  @0 => this
  @1 => is
  @2 => a
  @3 => test
  @4 => compression
  @5 => string

*/

 

70+ SQL courses for beginners and professionals