Trouver des mots de dictionnaire

Et comment allez-vous décider comment diviser les choses? Regardez autour du web et vous trouverez des exemples d'URL qui s'est avérée avoir d'autres significations.

En supposant que vous n'aviez pas eu les capitales à continuer, que feriez-vous avec ces (ceux qui vous viendront à l'esprit actuellement, Je sais qu'il y en a plus.): xxx

La dernière est particulièrement problématique car la partie gênante est de deux mots fonctionnant ensemble mais n'est pas un mot composé, le sens change complètement lorsque Vous le cassez.

Donc, donné un mot, est-ce un mot composé, composé de deux autres mots anglais? Vous pouvez avoir une sorte de table de recherche pour tous ces mots composés, mais si vous examinez simplement les candidats et essayez de faire correspondre des mots anglais, vous obtiendrez de faux positifs.

EDIT: Semble comme si je vais devoir aller à fournir quelques exemples. Les mots que je pensais inclure: xxx

Voici un code Python pour essayer de faire le point. Obtenez vous-même un dictionnaire sur le disque et go: xxx

Je ne suis pas sûr de combien de temps ou de fréquence que vous devez faire cela (est-ce une opération ponctuelle? quotidiennement? hebdomadaire?) Mais vous allez évidemment vouloir une recherche de dictionnaire rapide et pondéré.

Vous voudrez également avoir un mécanisme de résolution de conflit, peut-être une file d'attente latérale pour résoudre manuellement les conflits sur les tuples qui ont plusieurs significations possibles.

Je regarderais TRAIES . En utilisant un, vous pouvez trouver efficacement (et poids) vos préfixes, qui sont précisément ce que vous rechercherez.

Vous devrez construire vous-même des essais d'une bonne source de dictionnaire et de peser les nœuds sur des mots complets pour vous fournir un mécanisme de bonne qualité pour référence.

Il suffit de brainstorming ici, mais si vous savez que votre jeu de données consiste principalement en des duples ou des triplés, vous pouvez probablement vous échapper avec plusieurs recherches trempotées, par exemple «SPIC», puis «EJET», puis constatez que les deux résultats ont un Score faible, abandonnant dans "Spice" et "Jet", où les deux essais donneraient un bon résultat combiné entre les deux.

Je envisagerais également d'utiliser une analyse de fréquence sur les préfixes les plus courants jusqu'à une limite arbitraire ou dynamique, par exemple. filtrer «le» ou «un» ou «dans» et pondérer ces conséquences.

Cela ressemble à un problème amusant, bonne chance!

Il me semble qu'il y a un nombre relativement petit de sous-chaînes (longueur minimale 2) de tout mot composé raisonnable. Par exemple, pour "SPICEJET", je reçois:

'sp', 'pi', 'ic', 'ce', 'ej', 'je', 'et',
'spi', 'pic', 'ice', 'cej', 'eje', 'jet',
'spic', 'pice', 'icej', 'ceje', 'ejet',
'spice', 'picej', 'iceje', 'cejet',
'spicej', 'piceje', 'icejet',
'spiceje' 'picejet'

L'existence de mots pourrait être faite avec une trie, ou plus simplement avec un ensemble (c'est-à-dire une table de hachage). Compte tenu d'une fonction appropriée, vous pouvez faire: xxx

essentiellement, essayez simplement les différents points de pause pour voir si nous pouvons faire des mots. La récursion signifie qu'il va revenir en arrière jusqu'à ce qu'une scission réussie soit trouvée.

Bien sûr, cela peut ne pas trouver les scissions que vous voulez. Vous pouvez modifier cela pour renvoyer toutes les divisions possibles (au lieu de simplement le premier trouvé), puis faites une sorte de somme pondérée, peut-être, de préférer des mots courants sur des mots rares.

Une question similaire a été posée récemment: algorithme de séparateur de mots . Si vous vouliez limiter le nombre de scissions, vous garderiez une trace du nombre de scissions dans chacun des tuples (donc au lieu d'une paire, d'un triple).

J'utiliserais l'algorithme suivant.

1. commencez par la liste triée des mots se diviser et une liste triée de mots refusés (dictionnaire).

2. créer une liste de résultats d'objets qui devrait stocker: mot restant et liste de mots appariés.

3. remplir la liste des résultats avec les mots se diviser comme des mots restants.

4. marche dans le tableau des résultats et le dictionnaire simultanément - toujours augmenter le moins du moins de la deux, d'une manière similaire à la Fusionner l'algorithme. De cette façon, vous pouvez comparer tout le possible correspondant paires en une seule passe.

5. Chaque fois que vous trouvez un match, c'est-à-dire un Mot de mots divisé qui commence par un mot de dictionnaire, remplacer le Parole de dictionnaire assorti et le partie restante dans la liste des résultats. Vous devez prendre en compte multiples possibles.

6. Chaque fois que la partie restante est vide, Vous avez trouvé un résultat final.

7. Chaque fois que vous ne trouvez pas de match sur le "côté gauche", en d'autres termes, Chaque fois que vous augmentez le résultat pointeur en raison d'aucun match, supprimer l'élément de résultat correspondant. Cette mot n'a pas de matchs et ne peut pas être Split.

8. une fois que vous arrivez au bas de la Listes, vous aurez une liste de résultats partiels. Répéter la boucle Jusqu'à ce que cela soit vide - allez au point 4.

Si l'objectif est de trouver la "la plus grande rupture possible pour l'entrée" comme vous avez répondu, l'algorithme pourrait être assez simple si vous utilisez une théorie graphique. Vous prenez le mot composé et faites un graphique avec un sommet avant et après chaque lettre. Vous aurez un sommet pour chaque index de la chaîne et un passé à la fin. Ensuite, vous trouvez tous les mots légaux de votre dictionnaire qui sont des substrings du mot composé. Ensuite, pour chaque sous-chaîne légale, ajoutez un bord avec poids 1 au graphique reliant le sommet avant la première lettre de la sous-chaîne avec le sommet après la dernière lettre de la sous-chaîne. Enfin, utilisez un algorithme de chemin le plus court pour trouver le chemin avec le moins de bords entre le premier et le dernier sommet.

Le pseudo code est quelque chose comme ceci: p>

parseWords(compoundWord)
    # Make the graph
    graph = makeGraph()
    N = compoundWord.length
    for index = 0 to N
        graph.addVertex(i)

    # Add the edges for each word
    for index = 0 to N - 1
        for length = 1 to min(N - index, MAX_WORD_LENGTH)
            potentialWord = compoundWord.substr(index, length)
            if dictionary.isElement(potentialWord)
                graph.addEdge(index, index + length, 1)

    # Now find a list of edges which define the shortest path
    edges = graph.shortestPath(0, N)

    # Change these edges back into words.
    result = makeList()
    for e in edges
        result.add(compoundWord.substr(e.start, e.stop - e.start + 1))
    return result

Cela peut être un problème très difficile et il n'y a pas de solution générale simple (il peut y avoir des heuristiques qui fonctionnent pour les petits sous-ensembles).

Nous sommes confrontés exactement à ce problème en chimie où les noms sont composés par la concaténation des morphèmes. Un exemple est: p> xxx pré>

où les morphèmes sont: p> xxx pré>

Nous abordons cela via automate et entropie maximale et le code est disponible sur Sourceforge P> xxx pré>

mais être averti que cela prendra du travail. P>

Nous rencontrons parfois une ambiguïté et trouvez toujours un bon moyen de le signaler . P>

Distinguer entre Penisland et Penisland nécessiterait des heuristiques spécifiques au domaine. L'interprétation probable dépendra du corpus utilisé - aucun problème linguistique n'est indépendant du domaine ou des domaines analysés. p>

comme un autre exemple, la chaîne p> xxx pré>

peut être analysée comme p> xxx pré>

ou p >

week night