Lee vzdálenost - Lee distance

v teorie kódování, Lee vzdálenost je vzdálenost mezi dvěma struny ${displaystyle x_ {1} x_ {2} tečky x_ {n}}$ a ${displaystyle y_ {1} y_ {2} tečky y_ {n}}$ stejné délky n přes q-ary abeceda {0, 1, …, q - 1} velikosti q ≥ 2.

Je to metrický, definováno jako

{displaystyle sum _ {i = 1} ^ {n} min (| x_ {i} -y_ {i} | ,, q- | x_ {i} -y_ {i} |).}

^[1]

Zvažování abecedy jako skupiny přísad Z_q, Leeova vzdálenost mezi dvěma samostatnými písmeny ${displaystyle x}$ a ${displaystyle y}$ je délka nejkratší cesty v Cayleyův graf (což je kruhové, protože skupina je cyklická) mezi nimi.^[2]

Li ${displaystyle q = 2}$ nebo ${displaystyle q = 3}$ vzdálenost Lee se shoduje s Hammingova vzdálenost, protože obě vzdálenosti jsou 0 pro dva jednotlivé stejné symboly a 1 pro dva jednotlivé nerovné symboly. Pro ${displaystyle q> 3}$ už tomu tak není, vzdálenost Lee může být větší než 1.

The metrický prostor indukovaný Leeho vzdáleností je diskrétní analog eliptický prostor.^[1]

Příklad

Li q = 6, pak Leeova vzdálenost mezi 3140 a 2543 je 1 + 2 + 0 + 3 = 6.

Historie a aplikace

Vzdálenost Lee je pojmenována po C. Y. Lee. Aplikuje se na fázi modulace zatímco Hammingova vzdálenost se používá v případě ortogonální modulace.

The Berlekampův kód je příklad kódu v Lee metrice.^[3] Dalšími významnými příklady jsou Kód Preparata a Kód Kerdock; tyto kódy jsou nelineární, když se uvažuje nad polem, ale jsou lineární přes prsten.^[4]

Existuje také a Šedá izometrie (váha chránící bijekce) mezi ${displaystyle mathbb {Z} _ {4}}$ s Lee váha a ${displaystyle mathbb {Z} _ {2} ^ {2}}$ s Hammingova hmotnost.^[4]

Reference

^ ^A ^b Deza, Elena; Deza, Michel (2014), Slovník vzdáleností (3. vyd.), Elsevier, str. 52, ISBN 9783662443422
^ Blahut, Richard E. (2008). Algebraické kódy na úsečkách, rovinách a křivkách: Inženýrský přístup. Cambridge University Press. p.108. ISBN 978-1-139-46946-3.
^ Roth, Ron (2006). Úvod do teorie kódování. Cambridge University Press. p.314. ISBN 978-0-521-84504-5.
^ ^A ^b Greferath, Marcus (2009). „Úvod do teorie prstencového lineárního kódování“. V Sala, Massimiliano; Mora, Teo; Perret, Ludovic; Sakata, Shojiro; Traverso, Carlo (eds.). Gröbnerovy báze, kódování a kryptografie. Springer Science & Business Media. p.220. ISBN 978-3-540-93806-4.

Lee, C. Y. (1958), „Některé vlastnosti nonbinary kódy opravující chyby ", Transakce IRE na teorii informací, 4 (2): 77–82, doi:10.1109 / TIT.1958.1057446
Berlekamp, Elwyn R. (1968), Algebraická teorie kódování, McGraw-Hill
Voloch, Jose Felipe; Walker, Judy L. (1998). "Lee Weights of Codes z eliptických křivek". v Vardy, Alexander (vyd.). Kódy, křivky a signály: Společná vlákna v komunikaci. Springer Science & Business Media. ISBN 978-1-4615-5121-8.

[Deza-1] A ^b Deza, Elena; Deza, Michel (2014), Slovník vzdáleností (3. vyd.), Elsevier, str. 52, ISBN 9783662443422

[Blahut2008-2] Blahut, Richard E. (2008). Algebraické kódy na úsečkách, rovinách a křivkách: Inženýrský přístup. Cambridge University Press. p.108. ISBN 978-1-139-46946-3.

[Roth2006-3] Roth, Ron (2006). Úvod do teorie kódování. Cambridge University Press. p.314. ISBN 978-0-521-84504-5.

[Greferath2009-4] A ^b Greferath, Marcus (2009). „Úvod do teorie prstencového lineárního kódování“. V Sala, Massimiliano; Mora, Teo; Perret, Ludovic; Sakata, Shojiro; Traverso, Carlo (eds.). Gröbnerovy báze, kódování a kryptografie. Springer Science & Business Media. p.220. ISBN 978-3-540-93806-4.

[1]

[2]

[3]

[4]

Struny
Řetězcová metrika	Přibližná shoda řetězce Bitapový algoritmus Vzdálenost Damerau – Levenshtein Upravit vzdálenost Gestaltová shoda Hammingova vzdálenost Vzdálenost Jaro – Winkler Lee vzdálenost Levenshtein automat Levenshteinova vzdálenost Wagner – Fischerův algoritmus
Algoritmus prohledávání řetězců	Algoritmus Apostolico – Giancarlo Algoritmus vyhledávání řetězců Boyer – Moore Algoritmus Boyer – Moore – Horspool Algoritmus Knuth – Morris – Pratt Algoritmus Rabin – Karp
Vyhledávání více řetězců	Aho – Corasick Algoritmus Commentz-Walter
Regulární výraz	Porovnání motorů s regulárním výrazem Pravidelná gramatika Thompsonova konstrukce Nedeterministický konečný automat
Sekvenční zarovnání	Hirschbergův algoritmus Algoritmus Needleman – Wunsch Smith – Watermanův algoritmus
Datová struktura	DAFSA Pole přípon Příponový automat Příponový strom Zobecněný příponový strom Lano Ternární vyhledávací strom Trie
jiný	Analýza Porovnávání vzorů Shoda komprimovaného vzoru Nejdelší společná posloupnost Nejdelší běžný podřetězec Těžba sekvenčních vzorů Třídění