Correspond à une abréviation comme "ccd", "bbq", "phd" etc à la chaîne la plus similaire d'un ensemble de chaînes

Question

J'ai une liste d'abréviations comme "ccd", "bbq", "phd" etc.

Par exemple, nous allons prendre "barbecue", nous essayons de cartographier cette abréviation à une liste de chaînes,

nation barbecue - La réponse réelle devrait être ce

BBQ Smoke and Grill

bière et Bakes Portes

Comment décider à quelle chaîne appartient l'abréviation. J'ai essayé d'utiliser la mise en correspondance de chaînes via KMP et l'algorithme Longest Common Subsequence avec un ajout supplémentaire d'ajouter plus de valeur aux chaînes qui ont été trouvées plus tôt.

Existe-t-il une structure de données pouvant aider ou un algorithme pouvant traiter de tels cas?

Merci!

Answer 1

Ahh, problème de coréférence. Ma spécialité.

Une manière de voir cela est un problème de correction d'orthographe dans un dictionnaire. Ce que vous voulez, c'est avoir deux composants, une métrique de distance d'édition comme noté par j_random_hacker ET un dictionnaire qui liste toutes les abréviations acceptées. Vous voudrez peut-être inclure un nombre dans le dictionnaire afin que les formes longues plus communes comptent plus.

Le modèle de distance d'édition va être déterminé en fonction d'une métrique d'évaluation. Il y a un bon tutoriel sur la vérification orthographique à http://alias-i.com/lingpipe/demos/tutorial/querySpellChecker/read-me.html

Vous ne comptez pas utiliser un modèle de langage pour évaluer les modifications, mais il vous mis en place pour les indicateurs de performance, la distance d'édition, etc ...

Breck

Clarification pour la question de suivi:

Vos mesures dépendront des performances du système. Vous regardez ce que le système a eu raison, ce qui s'est mal passé et vous modifiez ensuite la distance d'édition pour mieux modéliser ce que vous voulez. Donc, le score du dictionnaire peut être si la phrase est dans ou hors du dictionnaire. Je commençais par le premier caractère avec un score de -1 par mot dans la phrase et -1 pour les mots de fonction sautés dans la phrase comme 'et', -5 pour sauter une lettre dans l'acronyme. Donc, "bbq", en regardant le dictionnaire peut être apparié à "Beer and Bakes Gates" avec un score de -8 (-1 + -1 + -1 + -5)

"Barbeque Nation" aura besoin de modifications ce score mieux. Ainsi, une lettre dans le même mot obtient des scores de -5 et le mot sauté est -6,5 (-,5 + - .5 + - .5 + -5), ce qui est un meilleur score. Ces coûts d'édition doivent être équilibrés sur l'ensemble de formation que vous avez qui devrait être plusieurs milliers d'exemples si vous voulez une généralité.