Сжатие (компьютерные науки)

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

Даны три слова cat , fish и be , где | cat | равно 3, | fish | равно 4 и | be | равно 2. Пусть обозначает длину самого длинного слова, которым является fish ; . ZIP-код cat , fish , be тогда равен 4 кортежам элементов:${\displaystyle \ell }$${\displaystyle \ell =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')]   

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

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

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

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

где для любого индекса i > | w | , w _i равно #.

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

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

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

${\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 }}}$

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

;; `nums' содержит бесконечный список чисел (0 1 2 3 ...) ( def nums ( range )) ( def tens [ 10 20 30 ]) ( def firstname "Alice" )     ;; Чтобы сжать (0 1 2 3 ...) и [10 20 30] в вектор, вызовите для них `map vector'; то же самое со списком ( 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' усекает до самой короткой последовательности; обратите внимание, что в "Alice" отсутствуют \c и \e ( map vector nums tens firstname ) ; ⇒ ([0 10 \A] [1 20 \l] [2 30 \i]) ( map str nums tens firstname ) ; ⇒ ("010A" "120l" "230i")      ;; Чтобы распаковать, примените `map vector' или `map list' ( apply map list ( map vector nums tens firstname )) ;; ⇒ ((0 1 2) (10 20 30) (\A \l \i))  

В Common Lisp :

( defparameter nums ' ( 1 2 3 )) ( defparameter tens ' ( 10 20 30 )) ( defparameter firstname "Alice" )          ( mapcar #' список чисел десятков ) ;; ⇒ ((1 10) (2 20) (3 30))   ( mapcar #' list nums tens ( coerce firstname 'list )) ;; ⇒ ((1 10 #\A) (2 20 #\l) (3 30 #\i)) — усечение по самому короткому списку      ;; Распаковывает ( apply #' mapcar #' list ( mapcar #' list nums tens ( coerce firstname 'list ))) ;; ⇒ ((1 2 3) (10 20 30) (#\A #\l #\i))         

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

>>> числа  =  [ 1 ,  2 ,  3 ] >>> десятки  =  [ 10 ,  20 ,  30 ] >>> имя  =  'Алиса'>>> сжато  =  список ( zip ( цифры ,  десятки )) >>> сжато [(1, 10), (2, 20), (3, 30)]>>> список ( zip ( * сжато ))  # распаковать [(1, 2, 3), (10, 20, 30)]>>> zipped2  =  list ( zip ( nums ,  tens ,  list ( firstname ))) >>> zipped2  # zip, усечение по кратчайшему [(1, 10, 'A'), (2, 20, 'l'), (3, 30, 'i')] >>> list ( zip ( * zipped2 ))  # распаковать [(1, 2, 3), (10, 20, 30), ('A', 'l', 'i')]

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

-- nums содержит бесконечный список чисел [1, 2, 3, ...] nums = [ 1 .. ] tens = [ 10 , 20 , 30 ] firstname = "Alice"        zip nums tens -- ⇒ [(1,10), (2,20), (3,30)] — zip, обрезает бесконечный список unzip $ zip nums tens -- ⇒ ([1,2,3], [10,20,30]) — unzip      zip3 числа десятки имя -- ⇒ [(1,10,'A'), (2,20,'l'), (3,30,'i')] — zip, усекает unzip3 $ zip3 числа десятки имя -- ⇒ ([1,2,3], [10,20,30], "Ali") — распаковать        

Список языков, поддерживаемых zip:

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