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.

[iubito]

bon, juste un 'tit truc pour ceux qui tomberaient sur ce topic.

au moment de coller le create function dans phpMyAdmin (v 2.11), il faut ajouter une ligne avant

Code :

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

DELIMITER ;;

[mon_nom_est_personne]

hesite pas non plus a utiliser ce post pour nous tenir au courant de l'avancer de ton projet. Ou tout du moins me tenir au courant, ca m'interesse ce genre de truc

[iubito]

pas de soucis, j'te tiendrai au courant.

J'ai fait un premier test avec quelques mots en français, la longueur différente compte effectivemment.

Ce que je pourrais faire, pour optimiser, si dans la recherche on précise qu'on donne le début de la mélodie, parmi un choix de début/milieu/fin, dans ce cas, je pourrai chercher

Code :

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

1
2
3
4
LEVENSHTEIN(
   LEFT(contour_musical, strlen($cm_utilisateur)+5),
   $cm_utilisateur)
AS de

ça va ralentir la recherche, mais donner des meilleurs résultats, peu importe la longueur des mélodies enregistrées dans la base.

Aussi, un LIMIT n au lieu d'un WHERE de < x, ça donnera les n résultats les plus proches et évite les problèmes de calibrage

[mon_nom_est_personne]

C'est effectivement le probleme avec ce genre de programme. Je me rappelle j'avais un TP a la fac d'introduction a la distance d'edition et on travaille sur des sequences d'ADN donc plutot similaire a ton probleme. et en fait la technique optimale niveau resultat mais pas niveau vitesse c'etait de spliter la sequence en unite mimimal et d'y faire les recherches.

[iubito]

effectivemment, une recherche de séquence d'ADN c'est tout à fait du même genre.

qu'est-ce que tu splittes exactement ?

[mon_nom_est_personne]

par exemple tu as une sequence ADN

AGTCCCTGAAAA..........
longueur 10000 caracteres.
Mais on sais par exemple que les sequence adn on un sens que par groupe de 10 machin (desole je me rappel de leur nom mais pas de ce que c'est).
et bien au lieu de stoquer une string de 1 million de caractere tu stock 1000 * 10. comme ca tu peu preciser la position dans la sequence et quel sequence

[iubito]

ah oui je saisi l'histoire... ça marche pour de l'ADN (où on regroupe par 3, pour faire des codons, puis par 10 pour les acides animés - euh, mes cours ça remonte à 2000).

En musique on pourrait avoir les mesures (sur une partition, traits verticaux tous les n pulsations), mais quand on recherche une mélodie, on peut donner plusieurs mesures, la première et dernière pas forcément complète, et puis savoir s'il faut diviser par 2 (mesure binaire), 3 (ternaire -par exemple valse, mazurka), 4 (peut se confondre avec du 2), 5, 6, 7, 9, 10, 11, 12, ... 9+7, 7+7+11... (oui oui, il y a des rythmes tordus en musique des Balkans ! c'est ce qui fait tout leur charme)

Bon, j'vais attaquer le dev un de ses quatre, et on verra le résultat