6
votes

Générer des combinaisons de substrings d'une chaîne

J'essaie de générer toutes les combinaisons de syllabes possibles pour un mot donné. Le processus d'identification de la syllabe n'est pas pertinente ici, mais c'est la génération de toutes les combinaisons qui me posent un problème. Je pense que cela est probablement possible de faire de manière récursive dans quelques lignes que je pense (bien que tout autre sens va bien), mais j'ai du mal à le faire fonctionner. Quelqu'un peut-il aider? XXX

string c# recursion combinations substring

1 commentaires

Vous devez utiliser Trie pour cataloguer vos syllabes. Ou vous pouvez utiliser Naiver Solutions :-)

3 Réponses :

4
votes

Normalement, ce type de problèmes est résolu en utilisant essaie . Je vais baser ma mise en œuvre d'une trie sur Comment créer une trie en C # (mais remarquez que je l'ai réécrit). xxx pré>

mot code> est la chaîne qui vous intéresse, pièces code> contiendra la liste des listes des syllabes possibles (ce serait probablement plus correct pour en faire une liste code>, mais c'est assez facile de le faire. Au lieu de Parts.Ajoud (nouvelle liste (CourantParts)); CODE> (CODE> Écrire parties.add (couranteParts.toarray.toarray ()); code> et modifier toutes les list > code> à Liste code >. p>

Je vais ajouter une variante de réponse d'énigmativité Thas Thas est de rien plus rapide que sa raison, car il élimine les mauvaises syllabes immédiatement au lieu de les filtrer ultérieurement. Si vous l'aimez, vous devriez lui donner un +1 , parce que sans son idée, cette variante ne serait pas possible. Mais notez que c'est toujours un hack. La solution "droite" consiste à utiliser Trie (S): -) P>

        .Concat(isSyllable(t) ? new[] { new string[] { t } } : new string[0][]);

0 commentaires

4
votes

Essayez de commencer avec ceci:

Func<string, IEnumerable<string[]>> splitter = null;
splitter =
    t =>
        from n in Enumerable.Range(1, t.Length - 1)
        let s = t.Substring(0, n)
        let e = t.Substring(n)
        from g in (new [] { new [] { e } }).Concat(splitter(e))
        select (new [] { s }).Concat(g).ToArray();

var query =
    from split in (new [] { new [] { word } }).Concat(splitter(word))
    where split.All(part => isSyllable(part))
    select split;

3 commentaires

Merci, cela semble prometteur, mais cela me donne une erreur de compilation à l'heure actuelle - "'System.Collections.Generic.Inumerable ' ne contient pas de définition pour" Démarrage "et aucune méthode d'extension" Démarrage ".

@mikel - ah, désolé pour ça. J'ai utilisé une méthode d'extension de cadre réactif. Je vais le réparer quand je reviens sur mon PC.

@Mikel - J'ai changé la requête pour utiliser des opérateurs standard.

0
votes

Vous avez peut-être des problèmes avec la mise à l'échelle pour être honnête, je ne suis pas sûr de la taille de votre ensemble de données, mais une solution basée sur une simple "est-ce une syllabe?" Vous devrez appeler votre routine "détection de syllabe" à peu près 0 (n * n) pour chaque mot où n = le nombre de caractères dans le mot (si cela n'a pas de sens, cela signifie que cela risque d'être lent pour les grands ensembles de données!) . Cela ne tient pas compte de l'évolutivité de l'algorithme de détection qui pourrait également ralentir lorsque vous ajoutez plus de syllabes. .

Je sais que vous avez dit votre processus d'identification de ce qui est une syllabe ou non n'est pas pertinente, mais disons que vous pouvez le changer pour que cela fonctionne plus comme une autocomplétion, c'est-à-dire passer au début d'une syllabe et vous indiquez que toutes les syllabes possibles à partir de ce point seraient beaucoup plus évolutives. Jetez un oeil à la remplacer par un Trie si la performance est hors de main.

0 commentaires