Side index in V.44 LZJH Data compression

[kamaldevkr]

Hi Team,

We are developing a library for V.44 LZJH Data compression in Packet method. We got the concept of side index and down index. Let a code word have valid side index and down index and a new "next character " detected (different from side index.), Then What will happens to "side index"

Whether the side-index field replaced by new side index ?

Or a New Side index will added to the node (Node will have 2 side indexes) ?

Any changes to down index ?

Let "ABCACAD" is the string to compress then "Side index" of code-word correspond to "A" point to "C" or "D" or Both ?

Thanks in advance,
KamalDev K R

[Shelwien]

Unfortunately this algorithm is patented, and patent is valid until at least 2024: https://patents.google.com/patent/US7016408B2/

So its hard to find source, I was only able to find this: https://github.com/resiprocate/resip...t/lzjh.asm#L78

Based on that, it seems that the dictionary tree is purely implementation-specific - the decoder doesn't use any tree,
and just adds new strings to the dictionary, constructed as dictionary_string + new_symbol.

So that tree is only used for matchfinding in the encoder, just as well its possible to implement a dumb comparison of lookahead bytes
with all strings in the dictionary.

Still, ITU V44 pdf says this:

The "down-index", if valid, points to a node that represents a string-segment that follows this string-segment.
The "side-index", if valid, points to a node that represents a string-segment at the same level as this string-segment

So, it looks like "side-index" forms a linked list of strings with same prefix, while "down-index" is a suffix pointer.

> Let a code word have valid side index and down index and a new "next character " detected
> (different from side index.), Then What will happens to "side index"

If this new symbol _follows_ this codeword, then its a suffix, and thus has to be added to suffix node's side-index list.

> Let "ABCACAD" is the string to compress then "Side index" of code-word correspond to "A" point to "C" or "D" or Both

AFAIU, it would be parsed like this: "A B C A CA D", with codewords "AB","BC","CA","CAD",
so down-index of "A" points to "AB", and "AB" has an empty side-index.

But with input "ABCAD" there would be codewords both for "AB" and "AD",
so "AB" would need a side-index that points to "AD".