Свертка (информатика) - Convolution (computer science)

В Информатика, конкретно формальные языки, свертка (иногда называемый застегивать) - функция, отображающая кортеж из последовательности в последовательность из кортежи. Это название «застежка-молния» происходит от действия молния в том, что он перемежает две ранее не пересекающиеся последовательности. Обратная функция распаковать который выполняет деконволюцию.

Пример

Учитывая три слова Кот, рыбы и быть где |Кот| 3, |рыбы| 4 и |быть| равно 2. Пусть ${\displaystyle \ell }$ обозначают длину самого длинного слова, которое рыбы; ${\displaystyle \ell =4}$. Свертка Кот, рыбы, быть тогда 4 набора элементов:

${\displaystyle (c,f,b)(a,i,e)(t,s,\#)(\#,h,\#)}$

куда # это символ не в исходном алфавите. В Haskell это усекает до самой короткой последовательности ${\displaystyle {\underline {\ell }}}$, куда ${\displaystyle {\underline {\ell }}=2}$:

zip3 "Кот" "рыбы" "быть"- [('c', 'f', 'b'), ('a', 'i', 'e')]

Определение

Пусть Σ - алфавит, # символ не в Σ.

Позволять Икс₁Икс₂... Икс_|Икс|, у₁у₂... у_|у|, z₁z₂... z_|z|, ... быть п слова (т.е. конечный последовательности ) элементов Σ. Позволять ${\displaystyle \ell }$ обозначают длину самого длинного слова, т.е. максимум из |Икс|, |у|, |z|, ... .

Свертка этих слов представляет собой конечную последовательность п-наборы элементов из (Σ ∪ {#}), т.е. элемент из ${\displaystyle ((\Sigma \cup \{\#\})^{n})^{*}}$:

${\displaystyle (x_{1},y_{1},\ldots )(x_{2},y_{2},\ldots )\ldots (x_{\ell },y_{\ell },\ldots )}$,

где для любого индекса я > |ш|, ш_я является #.

Свертка х, у, z, ... обозначается conv ( х, у, z, ...), zip ( х, у, z, ...) или же Икс ⋆ у ⋆ z ⋆ ...

Обратный к свертке иногда обозначают unzip.

Вариант операции свертки определяется следующим образом:

${\displaystyle (x_{1},y_{1},\ldots )(x_{2},y_{2},\ldots )\ldots (x_{\underline {\ell }},y_{\underline {\ell }},\ldots )}$

куда ${\displaystyle {\underline {\ell }}}$ это минимум длина входных слов. Это позволяет избежать использования прилегающего элемента. ${\displaystyle \#}$, но уничтожает информацию об элементах входных последовательностей за пределами ${\displaystyle {\underline {\ell }}}$.

В языках программирования

Свертка функции часто доступны в языки программирования, часто называемый застегивать. В Лисп -диалект можно просто карта желаемую функцию по желаемым спискам, карта является вариативный в Лиспе, поэтому он может принимать произвольное количество списков в качестве аргумента. Пример из Clojure:^[1]

;; nums содержит бесконечный список чисел (0 1 2 3 ...)(def числа (классифицировать))(def десятки [10 20 30])(def имя "Алиса");; Чтобы свернуть (0 1 2 3 ...) и [10 20 30] в вектор, вызовите для них `map vector '; то же самое со списком(карта вектор числа десятки)           ; ⇒ ([0 10] [1 20] [2 30])(список карт числа десятки)             ; ⇒ ((0 10) (1 20) (2 30))(карта ул. числа десятки)              ; ⇒ ("010" "120" "230");; `map 'обрезается до самой короткой последовательности; обратите внимание на отсутствие  c и  e из "Алисы"(карта вектор числа десятки имя) ; ⇒ ([0 10  A] [1 20  l] [2 30  i])(карта ул. числа десятки имя)    ; ⇒ («010A» «120l» «230i»);; Чтобы распаковать, примените `вектор карты 'или` список карт'(применить список карт (карта вектор числа десятки имя));; ⇒ ((0 1 2) (10 20 30) ( A  l  i))

В Common Lisp:

(defпараметр числа '(1 2 3))(defпараметр десятки '(10 20 30))(defпараметр имя "Алиса")(mapcar #'список числа десятки);; ⇒ ((1 10) (2 20) (3 30))(mapcar #'список числа десятки (принуждать имя 'список));; ⇒ ((1 10 #  A) (2 20 #  l) (3 30 #  i)) - обрезает самый короткий список;; Расстегивает(подать заявление #'mapcar #'список (mapcar #'список числа десятки (принуждать имя 'список)));; ⇒ ((1 2 3) (10 20 30) (#  A #  l #  i))

Такие языки как Python обеспечить zip () функция, более старая версия (Python 2. *) разрешила отображение Никто над списками, чтобы получить аналогичный эффект.^[2] zip () в сочетании с * оператор распаковывает список:^[2]

>>> числа = [1, 2, 3]>>> десятки = [10, 20, 30]>>> имя = 'Алиса'>>> застегнутый = застегивать(числа, десятки)>>> застегнутый[(1, 10), (2, 20), (3, 30)] >>> застегивать(*застегнутый) # распаковать[(1, 2, 3), (10, 20, 30)]>>> zipped2 = застегивать(числа, десятки, список(имя))>>> zipped2 # zip, обрезается по самому короткому[(1, 10, 'A'), (2, 20, 'l'), (3, 30, 'i')] >>> застегивать(*zipped2) # распаковать[(1, 2, 3), (10, 20, 30), ('A', 'l', 'i')]>>> # отображение с `None 'не усекает; устарело в Python 3. *>>> карта(Никто,числа, десятки, список(имя))[(1, 10, 'A'), (2, 20, 'l'), (3, 30, 'i'), (None, None, 'c'), (None, None, 'e') ]

Haskell имеет метод свертки последовательностей, но требует определенной функции для каждого арность (застегивать для двух последовательностей, zip3 на троих и т. д.),^[3] аналогично функциираспаковать и разархивировать3 доступны для распаковки:

- nums содержит бесконечный список чисел [1, 2, 3, ...] числа = [1..]десятки = [10, 20, 30]имя = "Алиса"застегивать числа десятки- ⇒ [(1,10), (2,20), (3,30)] - zip, обрезает бесконечный списокраспаковать $ застегивать числа десятки- ⇒ ([1,2,3], [10,20,30]) - разархивироватьzip3 числа десятки имя- ⇒ [(1,10, 'A'), (2,20, 'l'), (3,30, 'i')] - zip, усекаетразархивировать3 $ zip3 числа десятки имя- ⇒ ([1,2,3], [10,20,30], «Али») - разархивировать

Сравнение языков

Список языков с поддержкой свертки:

Почтовый индекс на разных языках

Язык	Почтовый индекс	Zip 3 списка	Почтовый индекс п списки	Примечания
Clojure	(список карт list1 list2) (вектор карты list1 list2)	(список карт list1 list2 list3) (вектор карты list1 list2 list3)	(список карт list1 … список) (вектор карты list1 … список)	Останавливается после длины самого короткого списка.
Common Lisp	(список mapcar # ' list1 list2)	(список mapcar # ' list1 list2 list3)	(список mapcar # ' list1 ... список)	Останавливается после длины самого короткого списка.
D	zip (диапазон1,диапазон2) диапазон1.zip (диапазон2)	zip (диапазон1,диапазон2,диапазон3) диапазон1.zip (диапазон2, диапазон3)	zip (диапазон1,…,диапазонN) диапазон1.zip (…, диапазонN)	Политика остановки по умолчанию является самой короткой и может быть опционально предоставлена ​​как самая короткая, самая длинная или требующая такой же длины.[4] Вторая форма является примером UFCS.
F #	List.zip list1 list2 Seq.zip источник1 источник2 Array.zip array1 array2	List.zip3 list1 list2 list3 Seq.zip3 источник1 источник2 источник3 Array.zip3 array1 array2 array3
Haskell	застегивать list1 list2	zip3 list1 list2 list3	застегиватьп list1 … список	zipn за п > 3 доступно в модуле Data.List. Останавливается после окончания самого короткого списка.
Python	zip (list1, list2)	zip (list1, list2, list3)	zip (list1, …, список)	zip () и карта() (3.x) останавливается после окончания самого короткого списка, тогда как карта() (2.x) и itertools.zip_longest () (3.x) расширяет более короткие списки с помощью Никто Предметы
Рубин	list1.zip (list2)	list1.zip (list2, list3)	list1.zip (list1, .., список)	Когда список, выполняемый на (list1), короче, чем списки, которые заархивированы, результирующий список имеет длину list1. Если список1 длиннее, для заполнения отсутствующих значений используются нулевые значения.[5]
Scala	list1.zip (list2)			Если одна из двух коллекций длиннее другой, ее оставшиеся элементы игнорируются. [6]

Распаковать на разных языках

Язык	Разархивировать	Распаковать 3 кортежа	Разархивировать п кортежи	Примечания
Clojure	(применить вектор карты сверточный список)	(применить вектор карты сверточный список)	(применить вектор карты сверточный список)
Common Lisp	(применить # список 'mapcar #' сверточный список)	(применить # список 'mapcar #' сверточный список)	(применить # список 'mapcar #' сверточный список)
F #	List.unzip list1 list2 Seq.unzip источник1 источник2 Array.unzip array1 array2	List.unzip3 list1 list2 list3 Seq.unzip3 источник1 источник2 источник3 Array.unzip3 array1 array2 array3
Haskell	распаковать сверточный список	разархивировать3 сверточный список	распаковатьп сверточный список	распаковать за п > 3 доступно в модуле Data.List.
Python	zip (*convvlist)	zip (*convvlist)	zip (*convvlist)

Смотрите также

• Карта (функция высшего порядка)

Рекомендации

1. карта из ClojureDocs
2. карта (функция, итерация, ...) из раздела Встроенные функции из документации Python v2.7.2
3. zip :: [a] -> [b] -> [(a, b)] из Prelude, Базовые библиотеки
4. http://dlang.org/phobos/std_range.html#zip
5. http://www.ruby-doc.org/core-2.0/Array.html#method-i-zip
6. https://www.scala-lang.org/api/current/scala/collection/IterableOps.html#zip [B] (это: scala.collection.IterableOnce [B]): CC [(A @ scala.annotation.unchecked.uncheckedVariance, B)]

Эта статья включает материал свертки по PlanetMath, который находится под лицензией Лицензия Creative Commons Attribution / Share-Alike.