Зиппинг (информатика)

Эта статья о функции сопоставления данных. Информацию об архивировании в пользовательских программах см. в разделе «Сжатие файлов» .

В информатике , сжатие это функция которая отображает кортеж ​ последовательностей ​ в последовательность кортежей . — Это название «zip» происходит от действия застежки -молнии, заключающейся в том, что она чередует две ранее непересекающиеся последовательности. Обратная функция — unzip .

Пример

Учитывая три слова кот , рыба и быть где | кот | 3, | рыба | равно 4 и | быть | равно 2. Пусть $\ell$ обозначают длину самого длинного слова — « рыба» ; $\ell =4$. Тогда молния cat , fish , be состоит из 4 кортежей элементов:

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

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

zip3 "cat" "fish" "be"
-- [('c','f','b'),('a','i','e')]

Определение

Пусть Σ — алфавит , # ​​— символ, не входящий в Σ.

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

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

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

где для любого индекса i > | ш | , w _i — это #.

Почтовый индекс x, y, z, ... обозначается zip( x, y, z, ... ) или x ⋆ y ⋆ z ⋆ ...

Обратное к zip иногда обозначается как unzip.

Вариант операции zip определяется:

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

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

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

Zip Функции часто доступны в языках программирования , их часто называют почтовый индекс . В диалектах Lisp можно просто сопоставить нужную функцию с нужными списками, В Лиспе карта является вариативной , поэтому в качестве аргумента может принимать произвольное количество списков. Пример из Clojure :

;; `nums' contains an infinite list of numbers (0 1 2 3 ...)
(def nums (range))
(def tens [10 20 30])
(def firstname "Alice")

;; To zip (0 1 2 3 ...) and [10 20 30] into a vector, invoke `map vector' on them; same with list
(map vector nums tens)           ; ⇒ ([0 10] [1 20] [2 30])
(map list nums tens)             ; ⇒ ((0 10) (1 20) (2 30))
(map str nums tens)              ; ⇒ ("010" "120" "230")

;; `map' truncates to the shortest sequence; note missing \c and \e from "Alice"
(map vector nums tens firstname) ; ⇒ ([0 10 \A] [1 20 \l] [2 30 \i])
(map str nums tens firstname)    ; ⇒ ("010A" "120l" "230i")

;; To unzip, apply `map vector' or `map list'
(apply map list (map vector nums tens firstname))
;; ⇒ ((0 1 2) (10 20 30) (\A \l \i))

В Общем Лиспе :

(defparameter nums '(1 2 3))
(defparameter tens '(10 20 30))
(defparameter firstname "Alice")

(mapcar #'list nums tens)
;; ⇒ ((1 10) (2 20) (3 30))

(mapcar #'list nums tens (coerce firstname 'list))
;; ⇒ ((1 10 #\A) (2 20 #\l) (3 30 #\i)) — truncates on shortest list

;; Unzips
(apply #'mapcar #'list (mapcar #'list nums tens (coerce firstname 'list)))
;; ⇒ ((1 2 3) (10 20 30) (#\A #\l #\i))

Такие языки, как Python, предоставляют функция zip() . zip() в сочетании с * оператор разархивирует список:

>>> nums = [1, 2, 3]
>>> tens = [10, 20, 30]
>>> firstname = 'Alice'

>>> zipped = list(zip(nums, tens))
>>> zipped
[(1, 10), (2, 20), (3, 30)]

>>> list(zip(*zipped)) # unzip
[(1, 2, 3), (10, 20, 30)]

>>> zipped2 = list(zip(nums, tens, list(firstname)))
>>> zipped2 # zip, truncates on shortest
[(1, 10, 'A'), (2, 20, 'l'), (3, 30, 'i')] 
>>> list(zip(*zipped2)) # unzip
[(1, 2, 3), (10, 20, 30), ('A', 'l', 'i')]

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

-- nums contains an infinite list of numbers [1, 2, 3, ...] 
nums = [1..]
tens = [10, 20, 30]
firstname = "Alice"

zip nums tens
-- ⇒ [(1,10), (2,20), (3,30)] — zip, truncates infinite list
unzip $ zip nums tens
-- ⇒ ([1,2,3], [10,20,30]) — unzip

zip3 nums tens firstname
-- ⇒ [(1,10,'A'), (2,20,'l'), (3,30,'i')] — zip, truncates
unzip3 $ zip3 nums tens firstname
-- ⇒ ([1,2,3], [10,20,30], "Ali") — unzip

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

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

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

Язык	Почтовый индекс	Заархивировать 3 списка	Заархивировать ​ списки	Примечания
Часовня	zip ( итер1 итер2 )	zip ( iter1 iter2 iter3 )	zip ( iter1 ... itern )	Форма каждого итератора, ранг и экстенты в каждом измерении должны быть идентичными.
Кложур	(список карт list1 list2 ) (вектор карты list1 list2 )	(список карт list1 list2 list3 ) (вектор карты list1 list2 list3 )	(список карт list1 … listn ) (вектор карты list1 … слушайте )	Останавливается после длины самого короткого списка.
Общий Лисп	(mapcar #'list list1 list2)	(mapcar #'list list1 list2 list3)	(mapcar #'list list1 ... listn)	Останавливается после длины самого короткого списка.
Д	zip( диапазон1 , диапазон2 ) диапазон1 .zip( диапазон2 )	zip( диапазон1 , диапазон2 , диапазон3 ) диапазон1 .zip(диапазон2, диапазон3)	zip( диапазон1 , …, диапазонN ) диапазон1 .zip(…, диапазонN)	Политика остановки по умолчанию является самой короткой и может быть дополнительно указана как самая короткая, самая длинная или требующая одинаковой длины. Вторая форма является примером UFCS .
Ф#	Список.zip список1 список2 Seq.zip источник1 источник2 Array.zip массив1 массив2	Список.zip3 список1 список2 список3 Seq.zip3 исходный1 исходный2 исходный3 Array.zip3 массив1 массив2 массив3
Хаскелл	zip- лист1 список2	zip3 список1 список2 список3	zip n list1 … слушать	zipn для n > 3 доступен в модуле Data.List . Останавливается после того, как заканчивается кратчайший список.
Питон	zip( список1 , список2 )	zip( список1 , список2 , список3 )	zip( список1 , …, прослушать )	zip() и map() (3.x) останавливается после того, как заканчивается кратчайший список, тогда как карта() (2.x) и itertools.zip_longest() (3.x) расширяет более короткие списки с помощью Нет предметов
Руби	список1 .zip( список2 )	список1 .zip( список2 , список3 )	список1 .zip( список1 , .., списокn )	Если список, который выполняется (список1), короче, чем списки, которые архивируются, результирующий список имеет длину списка1. Если список1 длиннее, для заполнения недостающих значений используются нулевые значения.
Скала	список1 .zip( список2 )			Если одна из двух коллекций длиннее другой, остальные ее элементы игнорируются.

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

Язык	Разархивировать	Разархивируйте 3 кортежа	Разархивируйте n кортежей	Примечания
Кложур	(применить векторный zip-лист карты )	(применить векторный zip-лист карты )	(применить векторный zip-лист карты )
Общий Лисп	(apply #'mapcar #'list ziplist)	(apply #'mapcar #'list ziplist)	(apply #'mapcar #'list ziplist)
Ф#	List.unzip список1 список2 Seq.unzip источник1 источник2 Array.unzip массив1 массив2	List.unzip3 список1 список2 список3 Seq.unzip3 исходный1 исходный2 исходный3 Array.unzip3 массив1 массив2 массив3
Хаскелл	разархивировать почтовый список	распаковать 3 zip-листа	разархивировать и заархивировать список	unzipn для n > 3 доступен в модуле Данные.Список .
Питон	zip(* zipvlist )	zip(* zipvlist )	zip(* zipvlist )

См. также

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