Расстояние Ли

В теории кодирования , то Ли расстояние является расстоянием между двумя строками и равной длиной п над д -ичного алфавитом {0, 1, ..., д - 1} размером Q ≥ 2. ${\ displaystyle x_ {1} x_ {2} \ dots x_ {n}}$ ${\ displaystyle y_ {1} y_ {2} \ dots y_ {n}}$

Это показатель , определяемый как

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

^[1]

Рассматривая алфавит как аддитивную группу Z _q , расстояние Ли между двумя отдельными буквами и является длиной кратчайшего пути в графе Кэли (который является круговым, поскольку группа циклическая) между ними. ^[2] ${\ displaystyle x}$ ${\ displaystyle y}$

Если или расстояние Ли совпадает с расстоянием Хэмминга , потому что оба расстояния равны 0 для двух одинаковых одинаковых символов и 1 для двух отдельных неравных символов. Поскольку это уже не так, расстояние Ли может стать больше 1. ${\ displaystyle q = 2}$ $q=3$ $q>3$

Метрическое пространство , индуцированное Ли расстояние является дискретным аналогом эллиптического пространства . ^[1]

Пример [ править ]

Если q = 6, то расстояние Ли между 3140 и 2543 равно 1 + 2 + 0 + 3 = 6.

История и применение [ править ]

Дистанция Ли названа в честь CY Lee . Он применяется для фазовой модуляции, в то время как расстояние Хэмминга используется в случае ортогональной модуляции.

Код Берлекампа является примером кода в метрике Ли. ^[3] Другие важные примеры являются код Препарата и Кердок коды ; эти коды нелинейны, когда рассматриваются над полем, но линейны над кольцом . ^[4]

Кроме того , существует Gray изометрии (биекция сохранения веса) между с Ли весом и с весом Хемминг . ^[4] $\mathbb {Z} _{4}$ $\mathbb {Z} _{2}^{2}$

Ссылки [ править ]

^ ^a ^b Деза, Елена; Деза, Мишель (2014), Словарь расстояний (3-е изд.), Elsevier, стр. 52, ISBN 9783662443422
^ Blahut, Ричард Э. (2008). Алгебраические коды на линиях, плоскостях и кривых: инженерный подход . Издательство Кембриджского университета. п. 108 . ISBN 978-1-139-46946-3.
^ Рот, Рон (2006). Введение в теорию кодирования . Издательство Кембриджского университета . п. 314 . ISBN 978-0-521-84504-5.
^ a b Греферат, Маркус (2009). «Введение в теорию линейного кодирования». В Сале, Массимилиано; Мора, Тео; Перре, Людовик; Саката, Сёдзиро; Траверсо, Карло (ред.). Основы Грёбнера, кодирование и криптография . Springer Science & Business Media . п. 220 . ISBN 978-3-540-93806-4.

Ли, CY (1958), "Некоторые свойства недвоичных кодов с исправлением ошибок ", IRE Сделка по теории информации , 4 (2): 77-82, DOI : 10,1109 / TIT.1958.1057446
Берлекамп, Элвин Р. (1968), алгебраическая теория кодирования , McGraw-Hill
Волоч, Хосе Фелипе; Уокер, Джуди Л. (1998). "Ли веса кодов из эллиптических кривых". В Варды, Александр (ред.). Коды, кривые и сигналы: общие темы в коммуникациях . Springer Science & Business Media. ISBN 978-1-4615-5121-8.

[Deza-1] Деза, Елена; Деза, Мишель (2014), Словарь расстояний (3-е изд.), Elsevier, стр. 52, ISBN 9783662443422

[Blahut2008-2] Blahut, Ричард Э. (2008). Алгебраические коды на линиях, плоскостях и кривых: инженерный подход . Издательство Кембриджского университета. п. 108 . ISBN 978-1-139-46946-3.

[Roth2006-3] Рот, Рон (2006). Введение в теорию кодирования . Издательство Кембриджского университета . п. 314 . ISBN 978-0-521-84504-5.

[Greferath2009-4] Греферат, Маркус (2009). «Введение в теорию линейного кодирования». В Сале, Массимилиано; Мора, Тео; Перре, Людовик; Саката, Сёдзиро; Траверсо, Карло (ред.). Основы Грёбнера, кодирование и криптография . Springer Science & Business Media . п. 220 . ISBN 978-3-540-93806-4.

[1]

vтеСтруны
Строковая метрика	Приблизительное соответствие строк Битап алгоритм Расстояние Дамерау – Левенштейна Изменить расстояние Сопоставление гештальт-паттернов Расстояние Хэмминга Расстояние Яро – Винклера Расстояние Ли Автомат Левенштейна Расстояние Левенштейна Алгоритм Вагнера – Фишера
Алгоритм поиска строки	Алгоритм Апостолико – Джанкарло Алгоритм поиска строки Бойера – Мура Алгоритм Бойера – Мура – Хорспула Алгоритм Кнута – Морриса – Пратта Алгоритм Рабина – Карпа
Поиск по нескольким строкам	Ахо-Корасик Алгоритм комментария-Вальтера
Регулярное выражение	Сравнение движков регулярных выражений Обычная грамматика Конструкция Томпсона Недетерминированный конечный автомат
Выравнивание последовательности	Алгоритм Хиршберга Алгоритм Нидлмана – Вунша Алгоритм Смита – Уотермана
Структура данных	DAFSA Массив суффиксов Суффикс-автомат Суффиксное дерево Обобщенное суффиксное дерево Веревка Тернарное дерево поиска Trie
Другой	Парсинг Сопоставление с образцом Сжатое сопоставление с образцом Самая длинная общая подпоследовательность Самая длинная общая подстрока Последовательный анализ паттернов Сортировка