Dictionary Encoding (Lossless) for Comma-Separated Words

Problem: Dictionary Encoding (Lossless Compression) for Comma-Separated Words

Implement lossless dictionary compression for an input string whose words are separated by commas ,.

The encoding process must:

• Associate every distinct word with an index in a dictionary.
• Substitute each occurrence in the input sequence with that word's dictionary index.

Provide these two functions:

1. encode(input_string) -> compressed_string
2. decode(compressed_string) -> original_string

The implementation must satisfy the following requirements:

• decode may use only the value produced by encode; it must not depend on external or global state.
• For every valid string s, decode(encode(s)) must reproduce s exactly.
• The encoded value must have this form:
  • compressed_string = <dictionary_part> + ":" + <index_part>
  • dictionary_part contains distinct words separated by commas, listed according to their first occurrence.
  • index_part contains the corresponding 0-based dictionary index for every word in the original sequence, with indices separated by commas.

Example

Input:

"USA,USA,USA,USA,Mexico,Canada,Mexico,Mexico,Mexico"

input_string = USA,USA,USA,USA,Mexico,Canada,Mexico,Mexico,Mexico

USA,Mexico,Canada:0,0,0,0,1,2,1,1,1

Encoded output:

"USA,Mexico,Canada:0,0,0,0,1,2,1,1,1"

This is produced because:

• The dictionary portion is ['USA', 'Mexico', 'Canada'].
• The index portion is [0,0,0,0,1,2,1,1,1].

Constraints

• 1 <= number of words N <= 2 * 10^5; this includes inputs containing from 100,001 through 200,000 words.
• Every word consists of visible ASCII characters and excludes , and :.
• An empty input string "" must also be handled.

Function signatures (language-agnostic; Python acceptable)

• encode(input_string: str) -> str
• decode(compressed_string: str) -> str