Je viens d'écrire du code pour une correspondance de chaîne approximative. Je voudrais comparer mon algorithme naïf à une implémentation plus mature exécutée sur la JVM. Aucune suggestion?Bibliothèque d'expressions régulières approchée pour Java?
J'ai trouvé ces réponses ailleurs sur ce site pour des problèmes similaires.
Commons Lang a une implémentation de Levenshtein distance.
http://commons.apache.org/lang/api-release/org/apache/commons/lang/StringUtils.htmlCommons Codec a une implémentation de soundex et metaphone.
http://commons.apache.org/codec/api-release/org/apache/commons/codec/language/Soundex.html
http://commons.apache.org/codec/api-release/org/apache/commons/codec/language/Metaphone.html
(source)
Lucene (http://lucene.apache.org/) met également en œuvre distance d'édition Levenshtein.
(source: zarawesome)
Merci, Gunslinger. La distance Levenshtein par rapport à StringUtils sera utile pour une comparaison directe des performances. –
Il arrive si je réinventé cette roue il y a plusieurs années - dans un programme FORTRAN sur un ordinateur central :)
Quand je fièrement dit à d'autres personnes sur Internet au sujet de mon algorithme, ils ont ri et me montra les deux (quatre?) grands noms dans ce domaine:
Ce sont des algorithmes permettant de comparer d'énormes séquences de chaînes similaires. La mémoire requise est d'environ m + n, où m et n sont les tailles des chaînes, et la durée d'exécution est d'environ m * n.
Gunslinger47 mentionne Levenshtein, Soundex et Metaphone. Levenshtein est aussi un moyen puissant de calculer les distances de corde, mais il est mieux adapté au texte "normal". Soundex et Metaphone calculent une courte chaîne destinée à encoder le son de la corde quand elle est parlée par un humain ... ils deviennent inefficaces après environ 3 syllabes, ils sont vraiment destinés à des mots dans le langage humain plutôt que des chaînes de génomes.
EDIT
Oups, je viens de trouver mes 4 grands noms au bas de l'article que vous avez cité. Donc vous êtes déjà au courant d'eux. Je pense que si vous recherchez ces noms et "Java" devrait vous trouver des implémentations. Here's the first one I found.
Est-ce que "approximatif" est un terme technique dont je n'ai jamais entendu parler, ou votre code est-il juste "approximativement correct"? –
Si c'est pour la bioinformatique, vous réinventez des roues compliquées. – msw
@Carl Smotricz Par approximation, je veux dire que les deux chaînes sont approximativement appariées si elles se trouvent à une certaine distance d'édition les unes des autres. Voir, par exemple, http://en.wikipedia.org/wiki/Approximate_string_matching. –