Aller au contenu

Messages recommandés

Posté(e)

salut à tous,

j'ai besoin de deux fonctions que je n'ai trouvé qu'en php:

 

levenshtein ( string $string1 , string $string2 [, int $cost_ins ] [, int $cost_rep ] [, int $cost_del ] )

similar_text ( string $first , string $second [, float &$percent ] )

 

mais je ne vois pas comment utiliser cette commande depuis lisp.

 

J'ai pu les tester avec un vieil environnement php (wamp)

 

J'ai bien suivi ces sujets:

langages

ou

avec même un navigateur

 

peut être qu'on trouve l'équivalent ailleurs ?

merci pour toute idée.

a+

gégé

----------------------------------------------------------------------

Site: https://www.g-eaux.fr

Blog: http://g-eaux.over-blog.com

Posté(e)

Bonjour,

 

La fonction levenshtein existe en common lisp, il ne doit pas être difficile de la réécrire en autolisp

(defun levenshtein-distance (str1 str2)
 "Calculates the Levenshtein distance between str1 and str2, returns an editing distance (int)."
 (let ((n (length str1))
       (m (length str2)))
   ;; Check trivial cases
   (cond ((= 0 n) (return-from levenshtein-distance m))
         ((= 0 m) (return-from levenshtein-distance n)))
   (let ((col (make-array (1+ m) :element-type 'integer))
         (prev-col (make-array (1+ m) :element-type 'integer)))
     ;; We need to store only two columns---the current one that
     ;; is being built and the previous one
     (dotimes (i (1+ m))
       (setf (svref prev-col i) i))
     ;; Loop across all chars of each string
     (dotimes (i n)
       (setf (svref col 0) (1+ i))
       (dotimes (j m)
         (setf (svref col (1+ j))
               (min (1+ (svref col j))
                    (1+ (svref prev-col (1+ j)))
                    (+ (svref prev-col j)
                       (if (char-equal (schar str1 i) (schar str2 j)) 0 1)))))
       (rotatef col prev-col))
     (svref prev-col m))))

Aide au téléchargement du cadastre dgfip-download-helper
Insertion de photos géolocalisées exif https://www.dropbox.com/s/gkf6o9ac2hxen97/exifscr.zip?dl=0
Script correction BUG SPDC V2, propriétaire département 21 et 22 : https://greasyfork.org/scripts/442400-spdcv2/code/SPDCV2.user.js

Posté(e)

Salut,

 

D'après ce que j'ai vu, pour la distance de Levenshtein, il semble que le plus efficient soit l'utilisation d'un tableau de dimension 2.

J'ai donc essayé de transcrire ce que j'ai trouvé en Visual LISP avec l'utilisation d'un safearray.

 

(defun LevenshteinDistance (str1 str2 / lst1 lst2 len1 len2 matrix i j cost)
 (vl-load-com)
 (setq lst1 (vl-string->list str1)
       len1 (length lst1)
       lst2 (vl-string->list str2)
       len2 (length lst2)
 )
 (cond
   ((zerop len1) len2)
   ((zerop len2) len1)
 )
 (setq matrix (vlax-make-safearray vlax-vbInteger (cons 0 len1) (cons 0 len2)))
 (setq i 0)
 (repeat (1+ len1)
   (vlax-safearray-put-element matrix i 0 i)
   (setq i (1+ i))
 )
 (setq j 0)
 (repeat (1+ len2)
   (vlax-safearray-put-element matrix 0 j j)
   (setq j (1+ j))
 )
 (setq i 1)
 (repeat len1
   (setq j 1)
   (repeat len2
     (setq cost (if (= (nth (1- i) lst1) (nth (1- j) lst2))
                  0
                  1
                )
     )
     (vlax-safearray-put-element
       matrix
       i
       j
       (min (1+ (vlax-safearray-get-element matrix (1- i) j))
            (1+ (vlax-safearray-get-element matrix i (1- j)))
            (+ (vlax-safearray-get-element matrix (1- i) (1- j)) cost)
       )
     )
     (setq j (1+ j))
   )
   (setq i (1+ i))
 )
 (vlax-safearray-get-element matrix len1 len2)
)

Gilles Chanteau - gileCAD - GitHub
Développements sur mesure pour AutoCAD

Posté(e)

Pour similar_text, tu peux utiliser LevenshteinDistance :

 

(defun Similarity (str1 str2)
 (- 1. (/ (float (LevenshteinDistance str1 str2)) (max (strlen str1) (strlen str2))))
)

Gilles Chanteau - gileCAD - GitHub
Développements sur mesure pour AutoCAD

Posté(e)

Bonjour,

Je découvre aujourd'hui cet algorithme levenshtein distance.En tant que néophyte complet, je me demandais si l'algorithme devait tenir compte des majuscules et minuscules pour fournir le résultat? Moi je dirais que non, mais je me trompe peut être ou c'est suivant l'analyse que l'on veut faire.

Un éclaircissement serait le bien venu, je n'ai pas trouvé de réponse sur le net.Les algorithmes en ligne sur le net donne le même résultat que celui de (gile), ils tiennent compte des majuscules et minuscules!

 

Choisissez un travail que vous aimez et vous n'aurez pas à travailler un seul jour de votre vie. - Confucius

Posté(e)

J'ai pensé (comme dans les implémentations que j'ai trouvé) qu'il était préférable de tenir compte de la casse par défaut, ce qui laisse toujours la possibilité d'appeler la fonction avec les arguments passés en majuscules pour l'ignorer.

 

(LevenshteinDistance (strcase str1) (strcase str2))

Gilles Chanteau - gileCAD - GitHub
Développements sur mesure pour AutoCAD

Posté(e)

Giles,

les 1ers tests m'ont l'air parfait pour ce dont j'ai besoin.

Pour le savoir faut que je mette en production.

Il s'agit de milliers de fichiers qu'on m’envoi,

j'avais fait une routine qui recherchais les doublons, mais les doublons c'était pas suffisant.

on peut avoir du "Recol_arpetaz.pdf" et du "REcol arpetaz 2018.pdf"

en fait c'est souvent le même fichier, qui est passé entres plusieurs mains qui l'ont renommé.

 

Pour apprivoiser ce type d'outil, il faut les confronter à la réalité, j'ai lancé le traitement, c'est long ...

 

j'ai vu que la version PHP permet de pondérer séparément les couts d'insertion, de remplacement et d'effacement,

avec un résultat assez rigolo, car elle choisi le cout minimal entre remplacement et effacement/insertion.

 

Pour tout le monde,

la question était "utiliser du php avec lisp" il semble bien que ce soit impossible, même si j'ai vu que l'on pouvait déboguer du php sous visual studio avec un plug-in.

 

Si on veut aller plus loin, il y a une API intéressante

disponible.

 

je vous tiens au jus

a+

gégé

----------------------------------------------------------------------

Site: https://www.g-eaux.fr

Blog: http://g-eaux.over-blog.com

Posté(e)

Une implémentation AutoLISP de similar_text plus proche des exemples que j'ai trouvé.

 

(defun similartext (str1 str2 / similarStr similarSum lst1 lst2)

 (defun similarStr (begin1 len1 begin2 len2 / pos1 pos2 len end1 end2 p q r pr qr isEqual)
   (setq pos1 begin1)
   (setq pos2 begin2)
   (setq len 0)
   (setq end1 (+ begin1 len1)
         end2 (+ begin2 len2)
   )
   (setq p begin1)
   (repeat len1
     (setq q begin2)
     (repeat len2
       (setq r 0
             pr p
             qr q
             isEqual T
       )
       (while (and (< pr end1)
                   (< qr end2)
                   isEqual
              )
         (if (= (nth pr lst1) (nth qr lst2))
           (setq r (1+ r))
           (setq isEqual nil)
         )
         (setq pr (1+ pr)
               qr (1+ qr)
         )
       )
       (if (< len r)
         (progn
           (setq len r)
           (setq pos1 p)
           (setq pos2 q)
         )
       )
       (setq q (1+ q))
     )
     (setq p (1+ p))
   )
   (list pos1 pos2 len)
 )

 (defun similarSum (begin1 len1 begin2 len2 / lst pos1 pos2 len sum e1 e2)
   (setq lst  (similarStr begin1 len1 begin2 len2)
         pos1 (car lst)
         pos2 (cadr lst)
         len  (caddr lst)
   )
   (setq sum len)
   (if (/= sum 0)
     (progn
       (if (and (< begin1 pos1) (< begin2 pos2))
         (setq sum (+ sum (similarSum begin1 (- pos1 begin1) begin2 (- pos2 begin2))))
       )
       (setq e1 (+ pos1 len)
             e2 (+ pos2 len)
       )
       (if (and (< e1 (+ begin1 len1)) (< e2 (+ begin2 len2)))
         (setq sum (+ sum (similarSum e1 (+ len1 begin1 (- e1)) e2 (+ len2 begin2 (- e2)))))
       )
     )
   )
   sum
 )

 (setq lst1 (vl-string->list str1)
       len1 (length lst1)
       lst2 (vl-string->list str2)
       len2 (length lst2)
 )
 (if (= 0 (+ len1 len2))
   '(0 0.0)
   (list
     (setq similar (similarSum 0 len1 0 len2))
     (/ (* similar 200.) (+ len1 len2))
   )
 )
)

Gilles Chanteau - gileCAD - GitHub
Développements sur mesure pour AutoCAD

Posté(e)

Gile,

Une implémentation AutoLISP de similar_text plus proche des exemples que j'ai trouvé.

tu es bien énigmatique !

quel est son avantage par rapport à l'autre ?

Commande: (similarity "SCAN1376_000" "SCAN1558_000")
0.75
Commande: (similartext "SCAN1376_000" "SCAN1558_000")
(9 75.0)
Commande: (similarity "PLANCHES 2 ET 3" "PLANCHES 5 ET 6")
0.866667
Commande: (similartext "PLANCHES 2 ET 3" "PLANCHES 5 ET 6")
(13 86.6667)

Tout est clair.

 

par contre: (ça je ne comprends pas)

Commande: (similarity (strcase "str1") (strcase "Str2dsffdsqfqsdfsdfsq"))
0.142857
Commande: (similartext (strcase "str1") (strcase "Str2dsffdsqfqsdfsdfsq"))
(3 24.0)

 

Pour l'application à mon cas concret, je suis cette fois un peu déçu, car les types similarités que j'ai trouvé,

(sur un type de fichier) sont clairement explicable, mais les fichiers bien différents:

 

Par exemple :

("PLANCHES 2 ET 3" "PLANCHES 5 ET 6")

("PLANCHES 1" "PLANCHES 4")

("SCAN1376_000" "SCAN1377_000" "SCAN1558_000" "SCAN1559_000")

 

mais j'ai encore beaucoup de recherches à faire ...

a+

gégé

----------------------------------------------------------------------

Site: https://www.g-eaux.fr

Blog: http://g-eaux.over-blog.com

Posté(e)

"Avantage" je ne sais pas mais, contrairement à similarity, similartext renvoie les mêmes résultats que ceux de cette page.

 

$ (setq s1 "PHP IS GREAT" s2 "WITH MYSQL")
"WITH MYSQL"
_$ (similarity s1 s2)
0.0833333
_$ (similarity s2 s1)
0.0833333
_$ (similartext s1 s2)
(3 27.2727)
_$ (similartext s2 s1)
(2 18.1818)

Gilles Chanteau - gileCAD - GitHub
Développements sur mesure pour AutoCAD

Créer un compte ou se connecter pour commenter

Vous devez être membre afin de pouvoir déposer un commentaire

Créer un compte

Créez un compte sur notre communauté. C’est facile !

Créer un nouveau compte

Se connecter

Vous avez déjà un compte ? Connectez-vous ici.

Connectez-vous maintenant
×
×
  • Créer...

Information importante

Nous avons placé des cookies sur votre appareil pour aider à améliorer ce site. Vous pouvez choisir d’ajuster vos paramètres de cookie, sinon nous supposerons que vous êtes d’accord pour continuer. Politique de confidentialité