Diviser une chaîne en une séquence de mots

Question

Récemment, je suis tombé sur la question d'entretien suivante :

Étant donné une chaîne de caractères en entrée et un dictionnaire de mots, implémentez une méthode qui découpe la chaîne en entrée en une chaîne de mots séparés par des espaces provenant du dictionnaire que pourrait utiliser un moteur de recherche pour la fonction "Vouliez-vous dire ?" Par exemple, une entrée de "applepie" devrait donner une sortie de "apple pie".

Je n'arrive pas à trouver une solution optimale en termes de complexité. Est-ce que quelqu'un a des suggestions sur la manière de faire cela de manière efficace ?

Answer 1

Il semble que la question soit exactement mon problème d'entretien, jusqu'à l'exemple que j'ai utilisé dans le post sur The Noisy Channel. Content que vous ayez aimé la solution. Je suis assez sûr que vous ne pourrez pas battre la solution de programmation dynamique / mémorisation en O(n^2) que je décris pour les pires performances.

Vous pouvez faire mieux en pratique si votre dictionnaire et votre entrée ne sont pas pathologiques. Par exemple, si vous pouvez identifier en temps linéaire les sous-chaînes de la chaîne d'entrée dans le dictionnaire (par exemple, avec un arbre préfixe) et si le nombre de telles sous-chaînes est constant, alors le temps global sera linéaire. Bien sûr, cela suppose beaucoup de choses, mais les données réelles sont souvent beaucoup plus agréables qu'un pire cas pathologique.

Il existe également des variations amusantes du problème pour le rendre plus difficile, telles que l'énumération de toutes les segmentation valides, la génération d'une meilleure segmentation basée sur une certaine définition de meilleur, la gestion d'un dictionnaire trop volumineux pour tenir en mémoire et la gestion de segmentations inexactes (par exemple, la correction des fautes d'orthographe). N'hésitez pas à commenter sur mon blog ou à me contacter pour un suivi.

Answer 2

Ce lien décrit ce problème comme une question d'entrevue parfaite et propose plusieurs méthodes pour le résoudre. En gros, cela implique le backtracking récursif. À ce niveau, cela produirait une complexité O(2^n). Une solution efficace utilisant la mémorisation pourrait réduire ce problème à O(n^2).

Answer 3

En utilisant python, nous pouvons écrire deux fonctions, la première segment renvoie la première segmentation d'un morceau de texte contigu en mots en utilisant un dictionnaire ou None si aucune segmentation n'est trouvée. Une autre fonction segment_all renvoie une liste de toutes les segmentations trouvées. Le pire cas de complexité est O(n**2) où n est la longueur de la chaîne d'entrée en caractères.

La solution présentée ici peut être étendue pour inclure des corrections orthographiques et une analyse de bigrammes pour déterminer la segmentation la plus probable.

def memo(func):
    '''
    Applique une simple mémoïsation à une fonction
    '''
    cache = {}
    def closure(*args):
        if args in cache:
            v = cache[args]
        else:
            v = func(*args)
            cache[args] = v
        return v
    return closure

def segment(text, words):
    '''
    Renvoie le premier match qui est la segmentation de 'text' en mots
    '''
    @memo
    def _segment(text):
        if text in words: return text
        for i in xrange(1, len(text)):
            prefix, suffix = text[:i], text[i:]
            segmented_suffix = _segment(suffix)
            if prefix in words and segmented_suffix:
                return '%s %s' % (prefix, segmented_suffix)
        return None
    return _segment(text)

def segment_all(text, words):
    '''
    Renvoie une liste complète de matches qui sont la segmentation de 'text' en mots
    '''
    @memo
    def _segment(text):
        matches = []
        if text in words: 
            matches.append(text)
        for i in xrange(1, len(text)):
            prefix, suffix = text[:i], text[i:]
            segmented_suffix_matches = _segment(suffix)
            if prefix in words and len(segmented_suffix_matches):
                for match in segmented_suffix_matches:
                    matches.append('%s %s' % (prefix, match))
        return matches 
    return _segment(text)

if __name__ == "__main__":    
    string = 'cargocultscience'
    words = set('car cargo go cult science'.split())
    print segment(string, words)
    # >>> car go cult science
    print segment_all(string, words)
    # >>> ['car go cult science', 'cargo cult science']

Answer 4

Une option serait de stocker tous les mots anglais valides dans un trie. Une fois que vous avez fait cela, vous pouvez commencer à parcourir le trie à partir de la racine vers le bas, en suivant les lettres dans la chaîne. Chaque fois que vous trouvez un nœud marqué comme un mot, vous avez deux options:

1. Couper l'entrée à ce point, ou
2. Continuer à étendre le mot.

Vous pouvez prétendre avoir trouvé une correspondance une fois que vous avez découpé l'entrée en un ensemble de mots qui sont tous légaux et n'ont plus de caractères restants. Comme à chaque lettre vous avez soit une option forcée (soit vous construisez un mot qui n'est pas valide et vous devez arrêter - soit vous pouvez continuer à étendre le mot) soit deux options (diviser ou continuer), vous pourriez implémenter cette fonction en utilisant une récursivité exhaustive:

PartitionWords(lettersLeft, wordSoFar, wordBreaks, trieNode):
    // Si vous avez parcouru le trie, ce chemin échoue.
    si le trieNode est nul, retourne.

    // Si ce nœud trie est un mot, envisagez ce qui se passe si vous divisez
    // le mot ici.
    si trieNode.isWord:
        // S'il ne reste plus d'entrée, vous avez terminé et avez une partition.
        si lettersLeft est vide, affichez wordBreaks + wordSoFar et retourne

        // Sinon, essayez de diviser ici.
        PartitinWords(lettersLeft, "", wordBreaks + wordSoFar, trie root)

    // Sinon, consommez la lettre suivante et continuez:
    PartitionWords(lettersLeft.substring(1), wordSoFar + lettersLeft[0], 
                   wordBreaks, trieNode.child[lettersLeft[0])

Dans le pire des cas pathologiques, cela listera toutes les partitions de la chaîne, ce qui peut être exponentiellement long. Cependant, cela se produit uniquement si vous pouvez partitionner la chaîne de nombreuses façons commençant toutes par des mots anglais valides, et cela est peu probable en pratique. Si la chaîne a de nombreuses partitions, nous pourrions passer beaucoup de temps à les trouver, cependant. Par exemple, considérez la chaîne "dotheredo." Nous pouvons la diviser de nombreuses façons:

do the redo
do the red o
doth ere do
dot here do
dot he red o
dot he redo

Pour éviter cela, vous voudrez peut-être instituer une limite du nombre de réponses que vous signalez, peut-être deux ou trois.

Comme nous interrompons la récursivité lorsque nous parcourons le trie, si nous essayons une division qui ne laisse pas le reste de la chaîne valide, nous le détecterons assez rapidement.

J'espère que cela vous aidera!

Answer 5

import java.util.*;

class Position {
    int indexTest,no;
    Position(int indexTest,int no)
    {
        this.indexTest=indexTest;
        this.no=no;
    } } class RandomWordCombo {
    static boolean isCombo(String[] dict,String test)
    {
        HashMap> dic=new HashMap>();
        Stack pos=new Stack();
        for(String each:dict)
        {
            if(dic.containsKey(""+each.charAt(0)))
            {
                //System.out.println("=========it is here");
                ArrayList temp=dic.get(""+each.charAt(0));
                temp.add(each);
                dic.put(""+each.charAt(0),temp);
            }
            else
            {
                ArrayList temp=new ArrayList();
                temp.add(each);
                dic.put(""+each.charAt(0),temp);
            }
        }
        Iterator it = dic.entrySet().iterator();
    while (it.hasNext()) {
        Map.Entry pair = (Map.Entry)it.next();
        System.out.println("key: "+pair.getKey());
        for(String str:(ArrayList)pair.getValue())
        {
            System.out.print(str);
        }
    }
        pos.push(new Position(0,0));
        while(!pos.isEmpty())
        {
            Position position=pos.pop();
            System.out.println("position index: "+position.indexTest+" no: "+position.no);
            if(dic.containsKey(""+test.charAt(position.indexTest)))
            {
                ArrayList strings=dic.get(""+test.charAt(position.indexTest)); 
                if(strings.size()>1&&position.no

`

J'ai résolu un problème similaire. Cette solution renvoie vrai ou faux si la chaîne donnée est une combinaison de mots du dictionnaire. Il peut être facilement converti pour obtenir une chaîne séparée par des espaces. Sa complexité moyenne est de O(n), où n est le nombre de mots du dictionnaire dans la chaîne donnée.

`