Convoluție (informatică)

De la Wikipedia, enciclopedia liberă
Salt la: Navigare, căutare

În informatică, în specifical în limbajele formale, convoluția (câteodată numită și zip) este o funcție care pune în corespondență o listă de caractere dintr-o secvență cu o secvență de liste de caractere.

Definiție[modificare | modificare sursă]

Fie Σ un alfabet și # un simbol care nu aparține lui Σ.

Fie x1x2... x|x|, y1y2... y|y|, z1z2... z|z|, ... n cuvinte (adică n secvențe finite) de elemente din Σ. Fie \ell lungimea celui mai lung cuvânt, adică maximul dintre |x|, |y|, |z|, ... .

Convoluția acestor cuvinte este o secvență finită de n caractere din (Σ ∪ {#}), adică un element din ((\Sigma\cup\{\# \})^n)^*:

 (x_1,y_1,\ldots)(x_2,y_2,\ldots)\ldots(x_\ell,y_\ell,\ldots),

în care, pentru oricare index i > |w|, wi este #.

Convoluția celor x, y, z, ... elemente este notatată prin conv( x, y, z, ...), zip( x, y, z, ...) sau xyz ⋆ ...

Inversa convoluției este câteodată notată cu unzip.

O variantă a operației de convoluție este definită de:

 (x_1,y_1,\ldots)(x_2,y_2,\ldots)\ldots(x_{\underline{\ell}},y_{\underline{\ell}},\ldots)

în care \underline{\ell} este lungimea minimă a cuvintelor din listă. Acest mod de definire a convoluției elimină folosirea elementului \#, dar distruge informația conținută de elementele cu lungime mai mare decât \underline{\ell}.


Exemplu[modificare | modificare sursă]

Convoluția cuvintelor cum, diez, am este:

 (c,d,a)(u,i,m)(m,e,\#)(\#,z,\#)


Format:Planetmath