En informática , específicamente en lenguajes formales , la convolución (a veces denominada zip ) es una función que mapea una tupla de secuencias en una secuencia de tuplas . Esta cremallera de nombre se deriva de la acción de una cremallera en el sentido de que entrelaza dos secuencias anteriormente disjuntas. La función inversa es descomprimir, que realiza una deconvolución.
Ejemplo
Dadas las tres palabras gato , pez y estar donde | gato | es 3, | pescado | es 4 y | ser | es 2. Vamosdenotar la longitud de la palabra más larga que es pez ;. La convolución de cat , fish , be es entonces 4 tuplas de elementos:
donde # es un símbolo que no está en el alfabeto original. En Haskell, esto se trunca a la secuencia más corta., dónde :
zip3 "gato" "pez" "ser" - [('c', 'f', 'b'), ('a', 'i', 'e')]
Definición
Sea Σ un alfabeto , # un símbolo no en Σ.
Sea x 1 x 2 ... x | x | , y 1 y 2 ... y | y | , z 1 z 2 ... z | z | , ... ser n palabras (es decir, secuencias finitas ) de elementos de Σ. Dejardenotar la longitud de la palabra más larga, es decir, el máximo de | x |, | y |, | z |, ....
La convolución de estas palabras es una secuencia finita de n -tuplas de elementos de (Σ ∪ {#}) , es decir, un elemento de:
- ,
donde para cualquier índice i > | w | , el w i es #.
La convolución de x, y, z, ... se denota conv ( x, y, z, ... ), zip ( x, y, z, ... ) o x ⋆ y ⋆ z ⋆ ...
La inversa a la convolución a veces se denomina descomprimir.
Una variación de la operación de convolución se define por:
dónde es la longitud mínima de las palabras de entrada. Evita el uso de un elemento contiguo, pero destruye información sobre elementos de las secuencias de entrada más allá .
En lenguajes de programación
Las funciones de convolución suelen estar disponibles en lenguajes de programación , a menudo denominados zip . En los dialectos Lisp uno puede simplemente mapear la función deseada sobre las listas deseadas, map es variable en Lisp por lo que puede tomar un número arbitrario de listas como argumento. Un ejemplo de Clojure : [1]
;; `nums 'contiene una lista infinita de números (0 1 2 3 ...) ( def nums ( rango )) ( def decenas [ 10 20 30 ]) ( def firstname " Alice " );; Para convolucionar (0 1 2 3 ...) y [10 20 30] en un vector, invoque 'map vector' sobre ellos; lo mismo con la lista ( vector de mapa números decenas ) ; ⇒ ([0 10] [1 20] [2 30]) ( lista de mapas números decenas ) ; ⇒ ((0 10) (1 20) (2 30)) ( mapa str nums decenas ) ; ⇒ ("010" "120" "230");; 'map' se trunca a la secuencia más corta; nota que faltan \ cy \ e de "Alicia" ( mapa vectorial nums decenas apellido ) ; ⇒ ([0 10 \ A] [1 20 \ l] [2 30 \ i]) ( mapa str nums decenas apellido ) ; ⇒ ("010A" "120l" "230i");; Para descomprimir, aplicar `mapa vectorial 'o` mapa de la lista' ( solicitar lista de mapas ( mapa vectorial nums decenas apellido )) ;; ⇒ ((0 1 2) (10 20 30) (\ A \ l \ i))
En Common Lisp :
( defparameter nums ' ( 1 2 3 )) ( defparameter diez ' ( 10 20 30 )) ( defparameter firstname "Alice" )( mapcar # ' lista números decenas ) ;; ⇒ ((1 10) (2 20) (3 30))( Mapcar # ' lista nums decenas ( coaccionar apellido ' lista )) ;; ⇒ ((1 10 # \ A) (2 20 # \ l) (3 30 # \ i)) - trunca en la lista más corta;; Baja la cremallera ( aplicar # ' mapcar #' lista ( mapcar # ' lista nums decenas ( coaccionar firstname ' lista ))) ;; ⇒ ((1 2 3) (10 20 30) (# \ A # \ l # \ i))
Los lenguajes como Python proporcionan una Función zip () , versión anterior (Python 2. *) permitida la asignación Ninguno sobre listas para obtener un efecto similar. [2]zip () junto con el * operador descomprime una lista: [2]
>>> nums = [ 1 , 2 , 3 ] >>> decenas = [ 10 , 20 , 30 ] >>> Nombre = 'Alice'>>> comprimido = zip ( números , decenas ) >>> comprimido [(1, 10), (2, 20), (3, 30)]>>> zip ( * comprimido ) # descomprimir [(1, 2, 3), (10, 20, 30)]>>> zipped2 = zip ( nums , decenas , list ( firstname )) >>> zipped2 # zip, trunca en el más corto [(1, 10, 'A'), (2, 20, 'l'), (3, 30, 'i')] >>> zip ( * zipped2 ) # descomprimir [(1, 2, 3), (10, 20, 30), ('A', 'l', 'i')]>>> # el mapeo con 'Ninguno' no se trunca; obsoleto en Python 3. * >>> mapa ( Ninguno , nums , decenas , lista ( Nombre )) [(1, 10, 'A'), (2, 20, 'l'), (3, 30, 'i '), (Ninguno, Ninguno,' c '), (Ninguno, Ninguno,' e ')]
Haskell tiene un método de convolucionar secuencias pero requiere una función específica para cada aridad ( zip para dos secuencias, zip3 para tres, etc.), [3] de manera similar, las funciones descomprimir y Unzip3 están disponibles para descomprimir:
- nums contiene una lista infinita de números [1, 2, 3, ...] nums = [ 1 .. ] decenas = [ 10 , 20 , 30 ] firstname = "Alice"zip nums decenas - ⇒ [(1,10), (2,20), (3,30)] - zip, trunca la lista infinita descomprimir $ zip nums decenas - ⇒ ([1,2,3], [10 , 20,30]) - descomprimirZIP3 nums decenas Nombre - ⇒ [(1,10, 'A'), (2,20, 'l'), (3,30, 'i')] - zip, trunca unzip3 $ ZIP3 nums decenas Nombre - ⇒ ([1,2,3], [10,20,30], "Ali") - descomprimir
Comparación de idiomas
Lista de idiomas por soporte de convolución:
Idioma | Cremallera | Listas Zip 3 | Zip n listas | Notas |
---|---|---|---|---|
Clojure | (lista de mapas lista1 lista2 ) (mapa de vectores lista1 lista2 ) | (mapa lista lista1 lista2 lista3 ) (mapa vector lista1 lista2 lista3 ) | (lista de mapas lista1 … listan ) (mapa de vectores lista1 … listan ) | Se detiene después de la longitud de la lista más corta. |
Lisp común | (mapcar # 'list list1 list2 ) | (mapcar lista # ' lista1 lista2 list3 ) | (mapcar # 'list list1 ... listn ) | Se detiene después de la longitud de la lista más corta. |
D | zip ( rango1 , rango2 ) rango1 .zip ( rango2 ) | zip ( rango1 , rango2 , rango3 ) rango1 .zip (rango2, rango3) | zip ( rango1 ,…, rangoN ) rango1 .zip (…, rangoN) | La política de detención se establece de forma predeterminada en la más corta y, opcionalmente, se puede proporcionar como más corta, más larga o que requiera la misma longitud. [4] La segunda forma es un ejemplo de UFCS . |
F# | List.zip lista1 lista2 Seq.zip Source1 source2 Array.zip array1 matriz2 | List.zip3 lista1 lista2 list3 Seq.zip3 Source1 source2 source3 Array.zip3 array1 matriz2 array3 | ||
Haskell | zip list1 list2 | ZIP3 lista1 lista2 list3 | zip n list1 … listn | zipn para n > 3 está disponible en el módulo Data.List . Se detiene cuando termina la lista más corta. |
Pitón | zip ( lista1 , lista2 ) | zip ( lista1 , lista2 , lista3 ) | zip ( list1 ,…, listn ) | zip () y map () (3.x) se detiene después de que finaliza la lista más corta, mientras que mapa () (2.x) y itertools.zip_longest () (3.x) extiende las listas más cortas con Ninguno elementos |
Rubí | list1 .zip ( list2 ) | list1 .zip ( lista2 , lista3 ) | list1 .zip ( list1 , .., listn ) | Cuando la lista que se está ejecutando en (list1) es más corta que las listas que se están comprimiendo, la lista resultante es la longitud de list1. Si lista1 es más larga, se utilizan valores nulos para completar los valores faltantes [5] |
Scala | list1 .zip ( list2 ) | Si una de las dos colecciones es más larga que la otra, los elementos restantes se ignoran. [6] |
Idioma | Abrir la cremallera | Descomprime 3 tuplas | Descomprimir n tuplas | Notas |
---|---|---|---|---|
Clojure | (aplicar convlist de vector de mapa ) | (aplicar convlist de vector de mapa ) | (aplicar convlist de vector de mapa ) | |
Lisp común | (aplicar # 'mapcar #' lista convlist ) | (aplicar # 'mapcar #' lista convlist ) | (aplicar # 'mapcar #' lista convlist ) | |
F# | List.unzip lista1 lista2 Seq.unzip Source1 source2 Array.unzip array1 matriz2 | List.unzip3 lista1 lista2 list3 Seq.unzip3 Source1 source2 source3 Array.unzip3 array1 matriz2 array3 | ||
Haskell | descomprimir convlist | unzip3 convlist | descomprimir n convlist | descomprimir para n > 3 está disponible en el módulo Lista de datos . |
Pitón | zip (* convvlist ) | zip (* convvlist ) | zip (* convvlist ) |
Ver también
Referencias
- ^ mapa de ClojureDocs
- ^ a b mapa (función, iterable, ...) de la sección Funciones integradas de la documentación de Python v2.7.2
- ^ zip :: [a] -> [b] -> [(a, b)] de Prelude, Bibliotecas básicas
- ^ http://dlang.org/phobos/std_range.html#zip
- ^ http://www.ruby-doc.org/core-2.0/Array.html#method-i-zip
- ^ https://www.scala-lang.org/api/current/scala/collection/IterableOps.html#zip [B] (que: scala.collection.IterableOnce [B]): CC [([email protected] .unchecked.uncheckedVariance, B)]
Este artículo incorpora material de convolution en PlanetMath , que tiene la licencia Creative Commons Attribution / Share-Alike License .