Konvoluce (počítačová věda) - Convolution (computer science)

tento článek případně obsahuje původní výzkum. Prosím vylepši to podle ověřování vznesené nároky a přidání vložené citace. Výroky sestávající pouze z původního výzkumu by měly být odstraněny. (Květen 2014) (Zjistěte, jak a kdy odstranit tuto zprávu šablony)

v počítačová věda konkrétně formální jazyky, konvoluce (někdy označované jako zip) je funkce, která mapuje a n-tice z sekvence do sekvence z n-tice. Tento název zip pochází z akce a zip v tom, že prokládá dvě dříve disjunktní sekvence. Zpětná funkce je rozbalit který provádí dekonvoluci.

Příklad

Vzhledem k těmto třem slovům kočka, Ryba a být kde |kočka| je 3, |Ryba| je 4 a |být| je 2. Nechť ${ displaystyle ell}$ označuje délku nejdelšího slova, které je Ryba; ${ displaystyle ell = 4}$. Konvoluce kočka, Ryba, být je pak 4 n-tice prvků:

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

kde # je symbol, který není v původní abecedě. v Haskell toto se zkrátí na nejkratší sekvenci ${ displaystyle { underline { ell}}}$, kde ${ displaystyle { underline { ell}} = 2}$:

zip3 "kočka" "Ryba" "být"- [('c', 'f', 'b'), ('a', 'i', 'e')]

Definice

Nechť Σ být abeceda, # symbol není v Σ.

Nechat X₁X₂... X_|X|, y₁y₂... y_|y|, z₁z₂... z_|z|, ... být n slova (tj. konečný sekvence ) prvků Σ. Nechat ${ displaystyle ell}$ označte délku nejdelšího slova, tj. maximum |X|, |y|, |z|, ... .

Konvoluce těchto slov je konečná posloupnost n-tuples of elements of (Σ ∪ {#}), tj. element of ${ displaystyle (( Sigma cup { # }) ^ {n}) ^ {*}}$:

${ displaystyle (x_ {1}, y_ {1}, ldots) (x_ {2}, y_ {2}, ldots) ldots (x _ { ell}, y _ { ell}, ldots)}$,

kde pro jakýkoli index i > |w|, w_i je #.

Konvoluce x, y, z, ... je označen konv ( x, y, z, ...), zip ( x, y, z, ...) nebo X ⋆ y ⋆ z ⋆ ...

Inverze ke konvoluci se někdy označuje rozbalením.

Varianta operace konvoluce je definována:

${ displaystyle (x_ {1}, y_ {1}, ldots) (x_ {2}, y_ {2}, ldots) ldots (x _ { underline { ell}}, y _ { underline { ell}}, ldots)}$

kde ${ displaystyle { podtržení { ell}}}$ je minimální délka zadávaných slov. Vyhýbá se použití sousedního prvku ${ displaystyle #}$, ale ničí informace o prvcích vstupních sekvencí dále ${ displaystyle { podtržení { ell}}}$.

V programovacích jazycích

Konvoluce funkce jsou často k dispozici v programovací jazyky, často označované jako zip. v Lisp - dialekty lze jednoduše mapa požadovanou funkci přes požadované seznamy, mapa je variadic v Lispu, takže to může trvat libovolný počet seznamů jako argument. Příklad z Clojure:^[1]

;; `nums 'obsahuje nekonečný seznam čísel (0 1 2 3 ...)(def čísla (rozsah))(def desítky [10 20 30])(def jméno "Alice");; Chcete-li konvolovat (0 1 2 3 ...) a [10 20 30] do vektoru, vyvolejte na ně „mapový vektor“; totéž se seznamem(vektorová mapa čísla desítky)           ; ⇒ ([0 10] [1 20] [2 30])(seznam map čísla desítky)             ; ⇒ ((0 10) (1 20) (2 30))(mapa str čísla desítky)              ; ⇒ ("010" "120" "230");; `mapa 'se zkrátí na nejkratší sekvenci; poznámka chybí  c a  e od „Alice“(vektorová mapa čísla desítky jméno) ; ⇒ ([0 10  A] [1 20  l] [2 30  i])(mapa str čísla desítky jméno)    ; ⇒ („010A“ „120l“ „230i“);; Pro rozbalení použijte `mapový vektor 'nebo` seznam map'(použít seznam map (vektorová mapa čísla desítky jméno));; ⇒ ((0 1 2) (10 20 30) ( A  l  i))

v Společný Lisp:

(defparametr čísla '(1 2 3))(defparametr desítky '(10 20 30))(defparametr jméno "Alice")(mapcar #'seznam čísla desítky);; ⇒ ((1 10) (2 20) (3 30))(mapcar #'seznam čísla desítky (donutit jméno 'seznam));; ⇒ ((1 10 #  A) (2 20 #  l) (3 30 #  i)) - zkrátí se na nejkratší seznam;; Rozepne(aplikovat #'mapcar #'seznam (mapcar #'seznam čísla desítky (donutit jméno 'seznam)));; ⇒ ((1 2 3) (10 20 30) (#  A #  l #  i))

Jazyky jako Krajta poskytnout a zip () funkce, starší verze (Python 2. *) povolila mapování Žádný přes seznamy, abyste získali podobný efekt.^[2] zip () ve spojení s * operátor rozbalí seznam:^[2]

>>> čísla = [1, 2, 3]>>> desítky = [10, 20, 30]>>> jméno = „Alice“>>> na zip = zip(čísla, desítky)>>> na zip[(1, 10), (2, 20), (3, 30)] >>> zip(*na zip) # rozbalte[(1, 2, 3), (10, 20, 30)]>>> 2 = zip(čísla, desítky, seznam(jméno))>>> 2 # zip, zkracuje na nejkratší[(1, 10, 'A'), (2, 20, 'l'), (3, 30, 'i')] >>> zip(*2) # rozbalte[(1, 2, 3), (10, 20, 30), ('A', 'l', 'i')]>>> # mapování s `None 'se nezkrátí; zastaralé v Pythonu 3. *>>> mapa(Žádný,čísla, desítky, seznam(jméno))[(1, 10, 'A'), (2, 20, 'l'), (3, 30, 'i'), (Žádný, Žádný, 'c'), (Žádný, Žádný, 'e') ]

Haskell má metodu konvoluce sekvencí, ale vyžaduje pro každou konkrétní funkci arity (zip pro dvě sekvence, zip3 pro tři atd.),^[3] podobně funkcerozbalit a rozbalit3 jsou k dispozici pro rozbalení:

- nums obsahuje nekonečný seznam čísel [1, 2, 3, ...] čísla = [1..]desítky = [10, 20, 30]jméno = "Alice"zip čísla desítky- ⇒ [(1,10), (2,20), (3,30)] - zip, zkrátí nekonečný seznamrozbalit $ zip čísla desítky- ⇒ ([1,2,3], [10,20,30]) - rozbaltezip3 čísla desítky jméno- ⇒ [(1,10, 'A'), (2,20, 'l'), (3,30, 'i')] - zip, zkrátí serozbalit3 $ zip3 čísla desítky jméno- ⇒ ([1,2,3], [10,20,30], „Ali“) - rozbalte

Porovnání jazyků

Seznam jazyků podporujících konvoluci:

Viz také

• Mapa (funkce vyššího řádu)

Reference

Tento článek včlení materiál od konvoluce dále PlanetMath, který je licencován pod Creative Commons Attribution / Share-Alike License.