Convoluție (informatică)

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

În informatică, în special î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 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 :

,

î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:

în care 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 .


Exemplu[modificare | modificare sursă]

Convoluția cuvintelor cum, diez, am este:


Format:Planetmath