Quel est le meilleur algorithme pour faire correspondre deux chaînes contenant moins de 10 mots en écriture latine?

Je compare les titres de chansons, en utilisant un script latin (bien que pas toujours), mon objective est un algorithme qui donne un score élevé si les deux titres de chanson semblent avoir le même titre et un score très faible s’ils n’ont rien en commun.

Maintenant, je devais déjà coder (Java) pour écrire cela en utilisant Lucene et un RAMDirectory – toutefois, utiliser Lucene simplement pour comparer deux chaînes est trop lourd et par conséquent trop lent. Je suis maintenant passé à l’utilisation de https://github.com/nickmancol/simmesortingcs qui comporte de nombreux algorithmes permettant de comparer deux chaînes:

https://github.com/nickmancol/simmesortingcs/tree/master/src/main/java/ac/shef/wit/simmesortingcs/similaritymesortingcs

BlockDistance ChapmanLengthDeviation ChapmanMatchingSoundex ChapmanMeanLength ChapmanOrderedNameCompoundSimilarity CosineSimilarity DiceSimilarity EuclideanDistance InterfaceSsortingngMesortingc JaccardSimilarity Jaro JaroWinkler Levenshtein MatchingCoefficient MongeElkan NeedlemanWunch OverlapCoefficient QGramsDistance SmithWaterman SmithWatermanGotoh SmithWatermanGotohWindowedAffine Soundex 

mais je ne suis pas très versé dans ces algorithmes et quel serait un bon choix?

Je pense que Lucene utilise CosineSimilarity sous une forme ou une autre. C’est donc mon sharepoint départ, mais je pense qu’il pourrait y avoir quelque chose de mieux.

Plus précisément, l’algorithme doit fonctionner avec des chaînes courtes et comprendre le concept de mots, c’est-à-dire que les espaces doivent être traités de manière spécifique. Une bonne correspondance des caractères latins est essentielle, mais une bonne correspondance avec d’autres scripts tels que le coréen et le chinois est également pertinente, mais je pense qu’il faudrait un algorithme différent en raison de la manière dont ils traitent les espaces.

Ils sont tous bons. Ils travaillent sur différentes propriétés de chaînes et ont différentes propriétés de correspondance. Ce qui fonctionne le mieux pour vous dépend de ce dont vous avez besoin.

J’utilise JaccardSimilarity pour faire correspondre les noms. J’ai choisi le JaccardSimilarity parce qu’il était assez rapide et que, pour les chaînes courtes, il excellait dans l’appariement des noms avec des fautes de frappe courantes tout en dégradant rapidement le score pour toute autre chose. Donne un poids supplémentaire aux espaces. Il est également insensible à l’ordre des mots. J’avais besoin de ce comportement parce que l’impact d’un faux positif était beaucoup plus important que pour un faux négatif, les espaces pouvaient être des fautes de frappe mais pas souvent et l’ordre des mots n’était pas si important.

Notez que cela a été fait en combinaison avec un simplificateur qui supprime les non-diacritiques et un mappeur qui mappe les caractères restants à la plage z. Cela passe par une normalisation qui normalise tous les symboles de séparateur de mots dans un seul espace. Enfin, les noms sont analysés pour choisir les initiales, les préfixes et les suffixes. Ceci parce que les noms ont une structure et un format assez résistants à la comparaison de chaînes.

Pour faire votre choix, vous devez dresser une liste des critères que vous souhaitez, puis rechercher un algorithme répondant à ces critères. Vous pouvez également créer un ensemble de tests raisonnablement volumineux et exécuter tous les algorithmes de cet ensemble de tests pour voir quels sont les compromis en termes de temps, de nombre de positifs, de faux positifs, de faux négatifs et de négatifs, ainsi que les classes d’erreurs que votre système doit gérer. ect, ect.

Si vous n’êtes toujours pas sûr de votre choix, vous pouvez également configurer votre système pour qu’il permute les algorithmes de comparaison exacts au moment de l’exécution. Cela vous permet de faire un test AB et de voir quel algorithme fonctionne le mieux dans la pratique.

TLDR; L’algorithme que vous voulez dépend de ce dont vous avez besoin. Si vous ne savez pas ce dont vous avez besoin, assurez-vous de pouvoir le changer plus tard et faire des tests à la volée.

Vous devez probablement résoudre un problème de correction chaîne à chaîne . L’algorithme de distance Levenshtein est implémenté dans de nombreuses langues . Avant de l’exécuter, je supprimerais tous les espaces de la chaîne, car ils ne contiennent aucune information sensible, mais peuvent influer sur la différence de deux chaînes. Les arbres de préfixes de recherche de chaînes sont également utiles, vous pouvez également regarder dans cette direction. Par exemple ici ou ici . A déjà été discuté sur SO . Si les espaces sont tellement importants dans votre cas, atsortingbuez-leur un poids plus important.

Chaque algorithme va se concentrer sur un aspect similaire, mais légèrement différent, des deux chaînes. Honnêtement, cela dépend entièrement de ce que vous essayez d’accomplir. Vous dites que l’algorithme doit comprendre les mots, mais devrait-il également comprendre les interactions entre ces mots? Sinon, vous pouvez diviser chaque chaîne en fonction des espaces et comparer chaque mot de la première chaîne à chaque mot de la seconde. S’ils partagent un mot, le facteur de communité des deux chaînes devrait augmenter.

De cette façon, vous pouvez créer votre propre algorithme qui se concentre uniquement sur ce qui vous préoccupe. Si vous souhaitez tester un autre algorithme créé par quelqu’un d’autre, vous pouvez trouver des exemples en ligne et parsingr vos données pour vérifier l’exactitude de la similitude estimée entre chacun.

Je pense que http://jtmt.sourceforge.net/ serait un bon sharepoint départ.

Intéressant. Avez-vous pensé à une sorte de radix?

http://en.wikipedia.org/wiki/Radix_sort

Le concept à la base du sorting de base est qu’il s’agit d’un algorithme de sorting d’entiers non comparatif qui sortinge les données avec des clés d’entier en les regroupant par chiffres. Si vous convertissez votre chaîne en un tableau de caractères composé d’un nombre ne dépassant pas 3 chiffres, votre k = 3 (nombre maximal de chiffres) et vous n = le nombre de chaînes à comparer. Cela va sortinger les premiers chiffres de toutes vos chaînes. Ensuite, vous aurez un autre facteur s = la longueur de la plus longue chaîne. le pire des scénarios pour sortinger serait 3 * n * s et le meilleur des cas serait (3 + n) * s. Découvrez quelques exemples de sorting de chaînes pour les chaînes ici:

http://algs4.cs.princeton.edu/51radix/LSD.java.html

http://users.cis.fiu.edu/~weiss/dsaajava3/code/RadixSort.java

Avez-vous jeté un coup d’oeil à la distance de levenshtein?

 int org.apache.commons.lang.SsortingngUtils.getLevenshteinDistance(Ssortingng s, Ssortingng t) 

Trouvez la distance de Levenshtein entre deux cordes.

Il s’agit du nombre de modifications nécessaires pour modifier une chaîne en une autre, chaque modification étant une modification d’un seul caractère (suppression, insertion ou substitution).

L’implémentation précédente de l’algorithme de distance Levenshtein était de http://www.merriampark.com/ld.htm

Chas Emerick a écrit une implémentation en Java, qui évite une erreur OutOfMemoryError qui peut se produire lorsque mon implémentation Java est utilisée avec de très grandes chaînes. Cette implémentation de l’algorithme de distance Levenshtein provient de http://www.merriampark.com/ldjava.htm

Quoi qu’il en soit, je suis curieux de savoir ce que vous choisissez dans ce cas!

Je me demande si vous n’essayez pas de réinventer la roue. Certains systèmes de gestion de firebase database offrent des services / fonctionnalités conçus pour ce type de tâches.

Par exemple, Oracle Text

MODIFIER:

Attendez! Vous allez comparer les titres des chansons et vous n’utilisez PAS de firebase database? C’est intéressant. Pourquoi ne l’avez-vous pas ajouté dans votre question initiale? Parce que plus de 90% des applications indussortingelles utilisent une sorte de firebase database. Et peu importe la twig dans laquelle vous vous trouvez: fabrication, médecine, dissortingbution, divertissement, finances, …

Et même si vous n’utilisez pas encore de firebase database, vous devriez envisager de l’utiliser. Ces jours-ci, il y a toutes sortes de dbms. Ils viennent dans toutes les saveurs: relationnel, orienté object; binary ou XML; intégré ou autonome; multifile ou singlefile. Pour être honnête, si vous n’utilisez pas de firebase database, il est difficile de vous prendre au sérieux.

Mais si vous utilisez une firebase database Oracle pour stocker vos chansons. Oracle Text est alors la meilleure solution pour résoudre votre problème.

Et si vous utilisez une firebase database, il est parfaitement logique de laisser les dbms effectuer les calculs à votre place. Ce sera presque toujours plus rapide que d’extraire d’abord les données.

Pourquoi Oracle Text (par exemple) est supérieur aux algorithmes auto-implémentés: Oracle a une notion de “thèmes”, par exemple, il sait que le mot “politique” est lié à “élections”. Pour ce faire, il utilise une base de connaissances. (Il suffit de lire la documentation et vous serez surpris) . Vous passeriez des années à le développer à partir de zéro.