Comment mettre en œuvre un SIMPLE "Vous avez tapé ACB, voulez-vous dire ABC?"

Question

Je sais que ce n'est pas une question simple, donc si vous avez besoin de moi pour fournir plus d'informations sur la portée de celui-ci, faites le moi savoir. Il y a un tas de questions qui traitent presque du même problème (elles sont liées ici), mais jamais exactement la même avec le même genre de portée et d'objectif - du moins autant que je sache.

Contexte:

• Je dispose d'un fichier MP3 avec des balises ID3 pour le nom artiste et le titre de la chanson.
• J'ai deux tables artistes et chansons
• Les balises ID3 peuvent être légèrement (par exemple Mikaell Jacksonne)
• j'utilise ASP.NET + C# et une base de données MSSQL

Je dois synchroniser les MP3 avec la base de données. Signification:

1. L'utilisateur lance un script
2. Le script feuillette tous les fichiers MP3
3. Le script dit "Est 'Mikaell Jacksonne' 'Michael Jackson' OUI/NON"
4. L'utilisateur chercher et nous commençons plus

des exemples de ce que le système pourrait trouver:

Dans la base de données ...

SONGS = {"This is a great song title", "This is a song title"} 
ARTISTS = {"Michael Jackson"} 

Sorties ...

"This is a grt song title" did you mean "This is a great song title" ? 
"This is song title" did you mean "This is a song title" ? 
"This si a song title" did you mean "This is a song title" ? 
"This si song a title" did you mean "This is a song title" ? 
"Jackson, Michael" did you mean "Michael Jackson" ? 
"JacksonMichael" did you mean "Michael Jackson" ? 
"Michael Jacksno" did you mean "Michael Jackson" ? 

etc.

J'ai lu la documentation de ce /how-do-you-implement-a-did-you-mean et ce n'est pas exactement ce que J'ai besoin depuis que je ne veux pas vérifier un dictionnaire entier. Je ne peux pas non plus vraiment utiliser un service web car cela dépend beaucoup de ce que j'ai déjà dans ma base de données. Si possible, je voudrais également éviter de traiter avec distances et d'autres complicated things.

---

je pouvais utiliser le google api (ou quelque chose de similaire) pour le faire, ce qui signifie que le script va essayer la vérification orthographique et le tester avec la base de données, mais je pense qu'il pourrait y avoir une meilleure solution, car ma base de données fin être vraiment spécifique avec des chansons et des artistes étranges, rendant inutile la vérification orthographique.

Je pourrais aussi essayer quelque chose comme ce qui a été expliqué on this post, en utilisant Soundexfor c#. L'utilisation d'un correcteur d'orthographe standard ne fonctionnera pas car je n'utiliserai pas de mots, mais des noms et des «titres».

---

Ma question est: est-il un moyen simple relativement de le faire, et si oui, quel est-il?

Toute sorte d'aide serait appréciée.

Merci!

Answer 1

Ce que vous voulez, c'est un facteur de similarité. Essentiellement, vous voulez comparer vos entrées ("Micheal Jackson", par exemple) à vos valeurs attendues ("Michael Jackson"); Si vous attribuez une valeur de similarité très élevée à l'une de vos valeurs attendues, vous pouvez demander à l'utilisateur. Une façon de procéder consiste à hacher les valeurs attendues dans une table de hachage entièrement compacte. Si vous obtenez votre algorithme de hachage correctement (et oui, c'est le bit délicat), chaque entrée hachera la valeur attendue la plus proche; Une fois que vous avez trouvé la valeur attendue la plus proche, vous pouvez exécuter une évaluation de similarité par rapport à l'entrée et à la valeur attendue. Si vous êtes au-dessus d'un certain seuil, demandez à l'utilisateur.

Answer 2

Un système relativement simple mais relativement inexact serait de comparer les caractères des chaînes et de mesurer le nombre de caractères qui sont différents/manquants/ajoutés dans la chaîne de l'utilisateur. Si le nombre de caractères est assez faible (vous pouvez essayer de pondérer les différences en fonction de la distance clé [table de recherche]), demandez à l'utilisateur s'il s'agit d'une chaîne donnée

Answer 3

Ceci est une tâche non triviale. Découvrez Wikipedia pour plus d'informations sur les algorithmes qui traitent de cela. Vous avez déjà touché soundex, mais il y a d'autres transformations que vous cherchez ici.

Answer 4

Cela ressemble beaucoup à la création d'un vérificateur d'orthographe, ce qui est mieux fait avec un ternary search tree. Le lien utilise Java pour son exemple, mais la structure de données est la partie importante. La structure de données se comporte comme un Hash avec les propriétés mentionnées par McWafflestix.