Member Avatar for nisaa15
nisaa15 0 Newbie Poster

Just wondering if there can be a raw ASCII input where the same token (e.g 257 = at) appears numerous times (say 100) in the compressed output?

what ever the solution is whats the reasoning behind it?

Cheers

  • 1 Contributor
  • 0 Replies
  • 121 Views

Dani AI

Generated

Short answer: yes. Once the compressor has learned a substring (your example where the two‑letter string "at" becomes a dictionary entry), every later match of that exact substring can be emitted as the same dictionary code. If the input contains that substring many times, the same output token can appear many times (even dozens or hundreds), subject only to how the dictionary is managed by the implementation.

How it happens (in plain terms): LZW scans left-to-right, keeping a current match W. For each next symbol K it tests W+K. If W+K is in the table, it extends W. If not, it emits the code for W, adds W+K as a new table entry, and starts over with W=K. Because the encoder emits the code for the longest matched substring, once a substring has been promoted to a table entry every subsequent match of that substring will produce that code.

A short pseudocode summary:

initialize table with all single symbols
w = first input symbol
for each k in remaining input:
  if w+k in table:
    w = w+k
  else:
    output(table[w])
    add table entry for w+k
    w = k
output(table[w])

Practical caveats: many implementations use limited table size (e.g., 12-bit max) and either stop adding entries or clear the table when full; that can cause numeric codes to be reused later. Also, because LZW greedily matches the longest substring, overlapping repeats can yield different emitted sequences than non-overlapping repeats. For debugging, inspect the encoder dictionary as it runs: you will then see exactly when a code is created and why it appears repeatedly in the output.

Be a part of the DaniWeb community

We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.