Algoritmus Sardinas – Patterson - Sardinas–Patterson algorithm

v teorie kódování, Algoritmus Sardinas – Patterson je klasický algoritmus pro určení v polynomiální čas zda daný kód s proměnnou délkou je jedinečně dekódovatelný, pojmenovaný podle Augusta Alberta Sardinase a George W. Pattersona, kteří jej publikovali v roce 1953.^[1] Algoritmus provádí systematické hledání řetězce, který připouští dva různé rozklady na kódová slova. Tak jako Knuth zprávy, algoritmus byl znovuobjeven asi o deset let později, v roce 1963 Floyd, navzdory skutečnosti, že to bylo v té době již dobře známé v teorii kódování.^[2]

Myšlenka algoritmu

Zvažte kód ${displaystyle {, amapsto 1, bmapsto 011, cmapsto 01110, dmapsto 1110, emapsto 10011,}}$. Tento kód, který je založen na příkladu Berstel,^[3] je příklad kódu, který není jednoznačně dekódovatelný, protože řetězec

011101110011

lze interpretovat jako posloupnost kódových slov

01110 – 1110 – 011,

ale také jako posloupnost kódových slov

011 – 1 – 011 – 10011.

Tímto způsobem jsou dány dva možné dekódování tohoto kódovaného řetězce cdb a kotě.

Obecně lze kódové slovo najít podle následujícího nápadu: V prvním kole vybereme dvě kódová slova ${displaystyle x_ {1}}$ a ${displaystyle y_ {1}}$ takhle ${displaystyle x_ {1}}$ je předpona z ${displaystyle y_ {1}}$, to znamená,${displaystyle x_ {1} w = y_ {1}}$ pro nějakou „visící příponu“ ${displaystyle w}$. Pokud se člověk pokusí jako první ${displaystyle x_ {1} = 011}$ a ${displaystyle y_ {1} = 01110}$, visící přípona je ${displaystyle w = 10}$. Pokud se nám podaří najít dvě sekvence ${displaystyle x_ {2}, ldots, x_ {p}}$ a ${displaystyle y_ {2}, ldots, y_ {q}}$ takových kódových slov${displaystyle x_ {2} cdots x_ {p} = wy_ {2} cdots y_ {q}}$, pak jsme hotovi: Potom řetězec ${displaystyle x = x_ {1} x_ {2} cdots x_ {p}}$ lze alternativně rozložit jako ${displaystyle y_ {1} y_ {2} cdots y_ {q}}$, a našli jsme požadovaný řetězec, který má alespoň dva různé rozklady na kódová slova.

Ve druhém kole vyzkoušíme dva různé přístupy: první pokus je hledat kódové slovo, které má w jako předpona. Pak získáme novou visící příponu w ', pomocí kterého můžeme pokračovat v hledání. Pokud se nakonec setkáme s visící příponou, která je sama o sobě kódovým slovem (nebo prázdné slovo ), pak se hledání ukončí, protože víme, že existuje řetězec se dvěma rozklady. Druhým pokusem je hledat kódové slovo, které je samo o sobě předponou w. V našem příkladu máme ${displaystyle w = 10}$a sekvence 1 je kódové slovo. Můžeme tedy také pokračovat s w '= 0 jako nová visící přípona.

Přesný popis algoritmu

Algoritmus je nejpohodlněji popsán pomocí kvocientů formální jazyky. Obecně platí, že pro dvě sady řetězců D a N, (levý) kvocient ${displaystyle N ^ {- 1} D}$ je definována jako zbytková slova získaná z D odstraněním nějaké předpony v N. Formálně, ${displaystyle N ^ {- 1} D = {, ymid xyin D ~ {extrm {and}} ~ xin N,}}$. Teď nech ${displaystyle C}$ označte (konečnou) sadu kódových slov v daném kódu.

Algoritmus postupuje v kolech, kde v každém kole udržujeme nejen jednu visící příponu, jak je popsáno výše, ale (konečnou) množinu všech potenciálních visících přípon. Počínaje kulatým ${displaystyle i = 1}$, sada potenciálních visících přípon bude označena ${displaystyle S_ {i}}$. Sady ${displaystyle S_ {i}}$ jsou definovány indukčně jak následuje:

${displaystyle S_ {1} = C ^ {- 1} Csetminus {varepsilon}}$. Tady symbol ${displaystyle varepsilon}$ označuje prázdné slovo.

${displaystyle S_ {i + 1} = C ^ {- 1} S_ {i} šálek S_ {i} ^ {- 1} C}$, pro všechny ${displaystyle igeq 1}$.

Algoritmus počítá množiny ${displaystyle S_ {i}}$ v rostoucím pořadí ${displaystyle i}$. Jakmile jeden z ${displaystyle S_ {i}}$ obsahuje slovo z C nebo prázdné slovo, pak algoritmus končí a odpovídá, že daný kód není jednoznačně dekódovatelný. Jinak jednou sada ${displaystyle S_ {i}}$se rovná dříve nalezené množině ${displaystyle S_ {j}}$ s ${displaystyle j$, pak by algoritmus vstoupil v zásadě do nekonečné smyčky. Místo nekonečného pokračování odpovídá, že daný kód je jednoznačně dekódovatelný.

Ukončení a správnost algoritmu

Protože všechny sady ${displaystyle S_ {i}}$ jsou sady přípon konečné sady kódových slov, existuje pouze konečně mnoho různých kandidátů ${displaystyle S_ {i}}$. Jelikož návštěva jedné ze sad podruhé způsobí zastavení algoritmu, algoritmus nemůže pokračovat donekonečna, a proto musí vždy vypovědět. Přesněji řečeno, celkový počet visících přípon, které algoritmus považuje, se maximálně rovná součtu délek kódových slov ve vstupu, takže algoritmus běží v polynomiální čas jako funkce této vstupní délky. Použitím a příponový strom pro urychlení srovnání mezi každou visící příponou a kódovými slovy může být čas algoritmu ohraničen O (nk), kde n je celková délka kódových slov a k je počet kódových slov.^[4] Algoritmus lze implementovat pomocí stroje pro porovnávání vzorů. ^[5] Algoritmus lze také implementovat tak, aby běžel na a nedeterministický Turingův stroj který používá pouze logaritmický prostor; problém testování jedinečné dešifrovatelnosti je NL-kompletní, takže tento vázaný prostor je optimální.^[6]

Důkaz, že algoritmus je opravit, tj. že vždy dává správnou odpověď, najdete v učebnicích u Salomaa^[7] a Berstel a kol.^[8]

Viz také

• Kraftova nerovnost v některých případech poskytuje rychlý způsob, jak vyloučit možnost, že daný kód je jednoznačně dekódovatelný.
• Předčíslí kódy a blokové kódy jsou důležité třídy kódů, které jsou jednoznačně dekódovatelné podle definice.
• Časová osa teorie informace

Poznámky

Reference

• Berstel, Jean; Perrin, Dominique; Reutenauer, Christophe (2010). Kódy a automaty. Encyklopedie matematiky a její aplikace. 129. Cambridge: Cambridge University Press. ISBN  978-0-521-88831-8. Zbl  1187.94001.
• Berstel, Jean; Reutenauer, Christophe (2011). Nekomutativní racionální řady s aplikacemi. Encyklopedie matematiky a její aplikace. 137. Cambridge: Cambridge University Press. ISBN  978-0-521-19022-0. Zbl  1250.68007.
• Knuth, Donald E. (Prosinec 2003). „Robert W Floyd, in memoriam“. Novinky SIGACT. 34 (4): 3–13. doi:10.1145/954092.954488.
• Rodeh, M. (1982). Msgstr "Rychlý test jedinečné dešifrovatelnosti na základě stromů přípon (Corresp.)". Transakce IEEE na teorii informací. 28 (4): 648–651. doi:10.1109 / TIT.1982.1056535.CS1 maint: ref = harv (odkaz).
• Apostolico, A .; Giancarlo, R. (1984). Msgstr "Implementace stroje pro porovnávání vzorů s rychlým testem jedinečné dešifrování". Dopisy o zpracování informací. 18 (3): 155–158. doi:10.1016/0020-0190(84)90020-6.CS1 maint: ref = harv (odkaz).
• Rytter, Wojciech (1986). "Prostorová složitost jedinečného problému dešifrovatelnosti". Dopisy o zpracování informací. 23 (1): 1–3. doi:10.1016/0020-0190(86)90121-3. PAN  0853618.CS1 maint: ref = harv (odkaz).
• Salomaa, Arto (1981). Klenoty teorie formálního jazyka. Pitman Publishing. ISBN  0-273-08522-0. Zbl  0487.68064.
• Sardinas, August Albert; Patterson, George W. (1953), „Nezbytná a dostatečná podmínka pro jedinečný rozklad kódovaných zpráv“, Záznam úmluvy z HNĚV. Národní shromáždění z roku 1953, část 8: Teorie informací, str. 104–108.

Další čtení

• Robert G. Gallager: Informační teorie a spolehlivá komunikace. Wiley, 1968