Sardinas-Patterson algoritmus működését valaki el tudja nekem magyarázni?

Az algoritmus leírása:

[link]

Hogy megértsd az algoritmust, a N⁻¹*D jelentését kéne először megérteni:

Azokat a D-ben lévő kódszavakat keressük, amiknek van prefixuma N-ben, és akkor a megoldás halmazba bekerül a kódszó a prefixum nélkül. Tehát ha van egy "y=xw" kódszó D-ben, ahol az "x" egy kódszó N-ben akkor "w" egy kódszó lesz N⁻¹*D-ben.

Például ha D-ben van olyan hogy 11000 és N-ben van olyan hogy 110, akkor N⁻¹*D-be bekerül a 00, mert "110"+"00"="11000".

Wikiről a példa:

A kódszavak listája C = {1, 011, 01110, 1110, 10011}

"e" üres kódszót jelent, tehát a szó önmaga prefixum is volt. Akkor van vége ha Sᵢ tartalmaz üres kódszót, vagy végtelen ciklusba keveredsz.

S₁ = C⁻¹*C ∖ {e} = {(1)110, (1)0011, (011)10} = {110, 0011, 10}

S₂ = C⁻¹*S₁ ∪ S₁⁻¹*C = {(1)10, (1)0} ∪ {(10)011} = {10, 0, 011}

S₃ = C⁻¹*S₂ ∪ S₂⁻¹*C = {(1)0, (011)} ∪ {(10)011, (0)11, (0)1110, (011), (011)10} = {0, e, 011, 11, 1110, 10}

Vége mert az S₃ tartalmaz üres (e) kódszót, nem dekódol egyedien.

Ha végtelen ciklusba keveredett volna mert Sᵢ = Sⱼ, i ≠ j akkor is vége lenne, de egyedien kódol.

Tehát az első lépés mindig:

S₁ = C⁻¹*C ∖ {e},

utána

Sᵢ₊₁ = C⁻¹*Sᵢ ∪ Sᵢ⁻¹*C,

amíg el nem érjük az egyik feltételt.