Traitement chaine de caractère: chaine avoisinante

[Argorate]

Bonjour,

J'aimerais savoir si quelqu'un avais une piste pour m'aider.
Je veux faire une fonction PHP qui fait l'équivalent de strstr() sur les chaines de caractères mais en trouvant également les chaines ressemblant a celle de base
EX: si on cherche toto et qu'on trouve tata, on le sort quand même en résultat.

Comment pourrait on faire? peut être avec des expressions régulières mais l'algorithme lui même reste assez flou, vous en savez peut être plus sur le sujet?

Toutes idées sera la bienvenue.

merci.

[Tryounette]

Salut,

Une première piste qui pourrait t'aider, utiliser l'algorithme Levenshtein http://fr.php.net/manual/fr/function.levenshtein.php

Je l'utilise et c'est pas mal.

[My Hotel]

Regarde soundex (existe en PHP et SQL).

[Argorate]

Effectivement c'est pas mal, surtout en O(n*m).

Y a un ami qui m'a donné ces liens justement, au cas où ça intéresse qqun d'autre: (dont certains ont été cité ici même)
http://fr.php.net/manual/fr/function.similar-text.php
http://fr.php.net/manual/fr/function.levenshtein.php
http://fr.php.net/manual/fr/function.soundex.php

Je vais voir tout ça, thx

[Anthor]

Je t'avais proposé soundex, je vois que tu as continué vers Levenstein. ^^ Je ne pense pas que tu trouveras mieux.

Ici tu pourras trouver une implémentation pour une version francisé de soundex : http://sqlpro.developpez.com/cours/soundex/#L4

[Argorate]

Bon voilà j'ai fini mon petit module qui recherche les chaines voisines, ça marche super sauf que...

Je suis obligé de découper en mot pour appliquer la fonction levenshtein()
Partant de là, c'est la merde.

Car lorsque je recherche le mot "ligne" dans le texte suivant:

$malignequiestsuper = 'trop bien cette ligne dans la quel il y a masuperline';

il va me trouver le mot ligne qu'une fois... et il ne trouvera donc pas ni "ligne", ni "line" qui sont caché si on peut dire dans le texte.

Si vous avez une idée?

EDIT:

bon en version très simplifié, j'ai ça:

Code PHP :

<?php 

function recherche($ligne, $chaine_recherche, &$resultat)

{

    $phrase = explode(' ', $ligne);

    

    //pour chaque mot dans la phrase (ou ligne)

    foreach($phrase as $mot)

    {

        //verif que la chaine n'est pas plus grande que 255 caractere sinon la fonction bug

        if(strlen($mot) < 256)

        {

            //je cherche avec une "precision" de 3

            if(levenshtein($chaine_recherche, $mot) <= 3) $resultat++;

        }

    }

} 

[Allwise]

Pour chaque mot, si le mot est plus long que le mot cible,
tu compares les x 1ères lettres du mot recherché, ou $x = strlen(cible)+$delta. $delta c'est le nombre max de lettres que le mot à comparer peut avoir en plus par rapport au mot cible.

Et tant que t'es pas arrivé au bout de la chaine, tu te déplaces d'un caractères. Donc t'auras un truc genre
$boutDeMot = substr($mot, $i, strlen($cible)+$delta+$i);

Faudra que tu fasses en sorte que tu ne sortes pas des limites de la longueur du mot dans lequel tu recherches la cible.

[Argorate]

Je me demande au niveau de la complexité asymptotique au sens du plus mauvais cas ce que ça va donner^^
A mon avis ça sera très long car je ne fais pas la recherche que dans un fichier.
Mon algo va faire: chercher dans chaque sous-mot de chaque mot de chaque ligne de chaque fichier de chaque dossier a partir d'un dossier source définit au démarrage...

Mais je vais essayé ça