Discussion :

[iubito]

Salut

je vais faire sur mon site, une recherche de mélodies musicales à partir du contour mélodique, c'est-à-dire, pour une petite mélodie écrite, je vais noter
- U (up) quand la mélodie monte
- D (down) quand elle descend
- R (repeat) quand la note ne change pas (se répète)

Bref, je vais avoir des enregistrements avec des trucs un peu barbares comme par exemple DUUDDDURDRUUUU.

Le visiteur va chercher une mélodie (à voir comment il l'écrit avec son clavier), et je vais en calculer le contour pour faire ma recherche.

Si le contour cherché est présent dans la base (champ like '%chaine cherchée%') c'est bon. Mais j'aimerai sortir les résultats proches, qui ont entre une et n (à moi de déterminer jusqu'à combien j'autorise) lettres qui diffèrent (ex : un D au lieu d'un U, le premier D en moins, 3 U au lieu de 4 à la fin...)
J'aimerai savoir comment faire en MySQL, ou au pire en PHP (mais ça veut dire que je vais charger toute la table, c'est pas terrible) pour trouver les enregistrements presques similaires, et classer par résultat.

D'après ce que j'ai compris du FULLTEXT, c'est qu'il est capable de rechercher quand on a plusieurs mots, les textes qui les ont tous, puis en manque un, puis 2... On peut mettre aussi le joker * pour rechercher une partie d'un mot.
mais là dans mon cas, c'est un seul mot barbare qui peut être assez long.


Vais-je devoir construire en PHP, avant la requête SQL, tous les mots proche de celui recherché ? (mais comment déterminer le % de similitude ?
Ou existe-t'il une fonction miracle que je n'aurai point vu ?

Merci d'avance pour votre aide

[mon_nom_est_personne]

Y'a un truc qui va t'aider en php c'est l'algo 'distance d'edition' aussi appelle distance de levenshtein et utilisable en php grace a http://jp2.php.net/manual/fr/function.levenshtein.php.
en clair ca sert a quoi? a calculer la difference entre deux strings representee par un integer. plus il est grand plus les deux strings ont rien a voir.
Donc en gros tu fetch ta table, tu boucle est calcule le DE pour chaque chanson et tu ordonne de la plus petite a la plus grande et tu prend la premiere ligne.
perso je prendrais tout les petits genre tout les 0 et laisserais l'utilisateur choisir la bonne reponse et stockerais son pattern en base de donner pour apres faire de l'apprentissage supervise pour optimiser le tout.
sinon y'a un autre techniqu qui assure : mysql stored function

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
 
CREATE FUNCTION LEVENSHTEIN (s1 VARCHAR(255), s2 VARCHAR(255))
  RETURNS INT
    DETERMINISTIC
      BEGIN
        DECLARE s1_len, s2_len, i, j, c, c_temp, cost INT;
        DECLARE s1_char CHAR;
        DECLARE cv0, cv1 VARBINARY(256);
        SET s1_len = CHAR_LENGTH(s1), s2_len = CHAR_LENGTH(s2), cv1 = 0x00, j = 1, i = 1, c = 0;
        IF s1 = s2 THEN
          RETURN 0;
        ELSEIF s1_len = 0 THEN
          RETURN s2_len;
        ELSEIF s2_len = 0 THEN
          RETURN s1_len;
        ELSE
          WHILE j <= s2_len DO
            SET cv1 = CONCAT(cv1, UNHEX(HEX(j))), j = j + 1;
          END WHILE;
          WHILE i <= s1_len DO
            SET s1_char = SUBSTRING(s1, i, 1), c = i, cv0 = UNHEX(HEX(i)), j = 1;
            WHILE j <= s2_len DO
                SET c = c + 1;
                IF s1_char = SUBSTRING(s2, j, 1) THEN SET cost = 0; ELSE SET cost = 1; END IF;
                SET c_temp = CONV(HEX(SUBSTRING(cv1, j, 1)), 16, 10) + cost;
                IF c > c_temp THEN SET c = c_temp; END IF;
                SET c_temp = CONV(HEX(SUBSTRING(cv1, j+1, 1)), 16, 10) + 1;
                IF c > c_temp THEN SET c = c_temp; END IF;
                SET cv0 = CONCAT(cv0, UNHEX(HEX(c))), j = j + 1;
            END WHILE;
            SET cv1 = cv0, i = i + 1;
          END WHILE;
        END IF;
        RETURN c;
      END

comme ca tout ce que je viens de dire se limite a ecrire:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
 
'SELECT titre, contour_musical, LEVENSHTEIN(contour_musical,$cm_utilisateur) AS de FROM table WHERE contour_musical LIKE "%$cm_utilisateur%" ORDER BY de ASC

Et voila le travail, encore une fois, une bonne utilisation de mysql pown du brut force en php :-)

[iubito]

Salut et merci pour ta réponse, j'vais bosser ça !

Par contre, la requête reste avec un

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

contour_musical LIKE "%$cm_utilisateur%"

ça veut dire que ça ne va chercher que les entrées contenant exactement le cm_utilisateur avec éventuellement des choses avant et après ?

Ou alors la fonction magique LEVENSHTEIN va modifier le comportement du like ?
Dans ce cas, je ferai plutôt la requête :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
SELECT titre, contour_musical,
       LEVENSHTEIN(contour_musical,$cm_utilisateur) AS de
FROM table
WHERE de < x
ORDER BY de ASC

avec x proche de 0 à déterminer avec l'expérience, ou même laisser le choix à l'utilisateur recherche exacte / approximative / très approximative

[mon_nom_est_personne]

Le probleme avec la deuxieme solution c'est que tu vas appliquer le traitement a toute les lignes de ta table et non seulement a celle ou le patrons de l'utilisateur est present. ca veux dire que tu va perdre ton temps a traiter des lignes qui vont, quoi qu'il arrive, ne servir a rien. Donc utiliser le like sert surtout a optimiser le tout en reduisant le nombre de reponse candidate. Tu peu toutefois ajouter aussi la clause "AND de < x" ca sera mieux
Mais maintenant me viens une question a l'esprit : Quel est la taille de tes contours musicaux en base ? Car si en base tu as des patrons de 36 caracteres et que l'utilisateur saisi que des patrons de 6 caracteres ca fait des sacre distance. Malheureusement ce genre de systeme requiere beaucoup de test pour calibrer.

[iubito]

Je ne sais pas encore la taille, ça sera à voir à l'usage, déjà je réfléchis au fonctionnement, solutions possibles...

Ce qui m'embête avec le like, c'est que si l'utilisateur cherche
DUUDDDURDRUUUU
je ne pourrai pas trouver
DUDDDURDRUUUU (un U en moins vers le début)
et inversement.

Si je fais une recherche avec un like, si la chaîne cherchée est courte, alors pas la peine d'utiliser la super fonction, un like '%DURD%' devrait trouver plein d'occurences.

[mon_nom_est_personne]

oui effectivement dans ce cas c'est un peu braise. donc oui je pense que tu as tout a fait raison de pas utiliser le like.