Algos pour Convolution et FFT

Bonjour à tous,

je suis en train d'implémenter des algorithmes dans le cadre d'un travail sur le Pattern Matching with Don't Cares (en français la recherche de motif dans un texte avec un caractère "joker")
Ce domaine utilise énormément de calcul de FFT et de convolution malheureusement je dois dire que je patauge un peu là dedans :oops:

Par exemple, je suis plongé dans l'algorithme de Kalai http://people.cs.uchicago.edu/~kalai/PAPERS/dontcare.ps. Celui-ci indique qu'il faut calculer une somme de produit à l'aide de FFT:

soit une chaine de caractères: X=x1....xn et une chaine d'entier R=r1....rm (m<n)
il faut calculer:

Code:

---

Somme de i=1 à m de: x_{j-1+i}r_{i}

---

où pourrais-je trouver une librairie (ou un algo) me permettant de résoudre ce genre de calcul? Toutes les implémentations de FFT que j'ai pu trouver sur le net servent à traiter des signaux et des échantillonages. J'ai bien compris le lien qui existe entre la multiplication de grands entiers et le calcul de FFT (http://en.wikipedia.org/wiki/Multiplication_algorithm mais je ne vois pas comment l'adapter à mon problème :(

merci d'avance à ceux qui pourront m'aider :)

PS: je code ces algos en c++

Pour la FFT, cherche du côté de FFTW.
Pourquoi veux-tu faire une multiplication avec FFT ? Cela permet de gagner en vitesse, OK, mais avant, il vaut mieux que ton algorithme fonctionne ! Donc fais une multiplication normale et utilise l'algo de Strassen après.

Citation:

---

Envoyé par Miles

Pour la FFT, cherche du côté de FFTW.
Pourquoi veux-tu faire une multiplication avec FFT ? Cela permet de gagner en vitesse, OK, mais avant, il vaut mieux que ton algorithme fonctionne ! Donc fais une multiplication normale et utilise l'algo de Strassen après.

---

ben en fait c'est pas moi qui le veut c'est celui qui a inventé l'algorithme :P
C'est sur que c'est pas forcément utile pour de simples multiplications, mais c'est surtout pour améliorer la complexité finale de la méthode.

En ce qui concerne l'algo de Strassen dont tu me parles, y a t il un endroit ou je pourrais le trouver déja implémenté?

merci d'avance

Non, mais si tu relis le lien sur la multiplication que tu as mis, tu verras qu'il y a un Strassen.
Le gars qui a inventé l'algorithme n'a mis une multiplication comme celle-ci que pour réduire sa complexité, mais pour un début, il a commencé par une version sans cette optimisation afin de véirifier que tout marche. Tu peux donc faire exactement la même chose et t'occuper de mettre la multplication dedans apèrs, une fois que tout fonctionnera.

merci :)
l'algorithme fonctionne bien en utilisant la multiplication basique.

Maintenant j'aimerais bien pouvoir implémenter la méthode par FFT, je vais essayer en regardant la méthode de Strassen, mais si quelqu'un est déja passé par là et peux m'éviter de perdre de précieux jours je lui en serai éternellement reconnaissant (l'échéance de mon travail arrive à grand pas :cry: )

FFTW est la librairie de FFT la plus utilisée. Elle est peut-être un peu complexe au début mais elle dispose de nombreux algos de FFT. Elle est aussi très rapide.
Il existe pour cette librairie des projets VC++ ainsi que des .lib déjà compilés.
http://www.fftw.org/