Generando combinaciones de subcadenas de una cadena

Question

Estoy tratando de generar todas las combinaciones de sílabas posibles para una palabra dada. El proceso para identificar qué es una sílaba no es relevante aquí, pero es la generación de todas las combinaciones lo que me está dando un problema. Creo que probablemente sea posible hacerlo recursivamente en unas pocas líneas (aunque de cualquier otra manera está bien), pero estoy teniendo problemas para hacerlo funcionar. Alguien puede ayudar ?

// how to test a syllable, just for the purpose of this example 
    bool IsSyllable(string possibleSyllable) 
    { 
     return Regex.IsMatch(possibleSyllable, "^(mis|und|un|der|er|stand)$"); 
    } 

    List<string> BreakIntoSyllables(string word) 
    { 
     // the code here is what I'm trying to write 
     // if 'word' is "misunderstand" , I'd like this to return 
     // => {"mis","und","er","stand"},{ "mis","un","der","stand"} 
     // and for any other combinations to be not included 
    } 

Answer 1

trate de empezar con esto:

var word = "misunderstand"; 

Func<string, bool> isSyllable = 
    t => Regex.IsMatch(t, "^(mis|und|un|der|er|stand)$"); 

var query = 
    from i in Enumerable.Range(0, word.Length) 
    from l in Enumerable.Range(1, word.Length - i) 
    let part = word.Substring(i, l) 
    where isSyllable(part) 
    select part; 

Esto devuelve:

¿Eso ayuda a comenzar con al menos?

---

EDIT: He pensado un poco más acerca de este problema un vino con este par de consultas:

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; 

Ahora query de regreso este:

Avísame si eso está clavado ahora.

Answer 2

Normalmente este tipo de problemas se resuelve usando Tries. Voy a basar mi implementación de un Trie en How to create a trie in c# (pero tenga en cuenta que lo he reescrito).

var trie = new Trie(new[] { "un", "que", "stio", "na", "ble", "qu", "es", "ti", "onable", "o", "nable" }); 
//var trie = new Trie(new[] { "u", "n", "q", "u", "e", "s", "t", "i", "o", "n", "a", "b", "l", "e", "un", "qu", "es", "ti", "on", "ab", "le", "nq", "ue", "st", "io", "na", "bl", "unq", "ues", "tio", "nab", "nqu", "est", "ion", "abl", "que", "stio", "nab" }); 

var word = "unquestionable"; 

var parts = new List<List<string>>(); 

Split(word, 0, trie, trie.Root, new List<string>(), parts); 

// 

public static void Split(string word, int index, Trie trie, TrieNode node, List<string> currentParts, List<List<string>> parts) 
{ 
    // Found a syllable. We have to split: one way we take that syllable and continue from it (and it's done in this if). 
    // Another way we ignore this possible syllable and we continue searching for a longer word (done after the if) 
    if (node.IsTerminal) 
    { 
     // Add the syllable to the current list of syllables 
     currentParts.Add(node.Word); 

     // "covered" the word with syllables 
     if (index == word.Length) 
     { 
      // Here we make a copy of the parts of the word. This because the currentParts list is a "working" list and is modified every time. 
      parts.Add(new List<string>(currentParts)); 
     } 
     else 
     { 
      // There are remaining letters in the word. We restart the scan for more syllables, restarting from the root. 
      Split(word, index, trie, trie.Root, currentParts, parts); 
     } 

     // Remove the syllable from the current list of syllables 
     currentParts.RemoveAt(currentParts.Count - 1); 
    } 

    // We have covered all the word with letters. No more work to do in this subiteration 
    if (index == word.Length) 
    { 
     return; 
    } 

    // Here we try to find the edge corresponding to the current character 

    TrieNode nextNode; 

    if (!node.Edges.TryGetValue(word[index], out nextNode)) 
    { 
     return; 
    } 

    Split(word, index + 1, trie, nextNode, currentParts, parts); 
} 

public class Trie 
{ 
    public readonly TrieNode Root = new TrieNode(); 

    public Trie() 
    { 
    } 

    public Trie(IEnumerable<string> words) 
    { 
     this.AddRange(words); 
    } 

    public void Add(string word) 
    { 
     var currentNode = this.Root; 

     foreach (char ch in word) 
     { 
      TrieNode nextNode; 

      if (!currentNode.Edges.TryGetValue(ch, out nextNode)) 
      { 
       nextNode = new TrieNode(); 
       currentNode.Edges[ch] = nextNode; 
      } 

      currentNode = nextNode; 
     } 

     currentNode.Word = word; 
    } 

    public void AddRange(IEnumerable<string> words) 
    { 
     foreach (var word in words) 
     { 
      this.Add(word); 
     } 
    } 
} 

public class TrieNode 
{ 
    public readonly Dictionary<char, TrieNode> Edges = new Dictionary<char, TrieNode>(); 
    public string Word { get; set; } 

    public bool IsTerminal 
    { 
     get 
     { 
      return this.Word != null; 
     } 
    } 
} 

word es la cadena le interesa, parts contendrá la lista de listas de posibles sílabas (que probablemente sería más correcto para que sea un List<string[]>, pero es bastante fácil de hacerlo. En lugar de parts.Add(new List<string>(currentParts));parts.Add(currentParts.ToArray()); escribir y cambiar todo el List<List<string>>-List<string[]>.

voy a añadir una variante de la respuesta Enigmativity thas es más rápido que su theretically porque descarta sílabas equivocadas inmediatamente en lugar de post-filtrado de ellos más tarde. Si te gusta, usted debe dale un +1, porque sin su idea, este varian No sería posible. Pero tenga en cuenta que todavía es un truco. La solución "correcta" es en el uso de Trie (s) :-)

Func<string, bool> isSyllable = t => Regex.IsMatch(t, "^(un|que|stio|na|ble|qu|es|ti|onable|o|nable)$"); 

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

var parts = splitter(word).ToList(); 

Una explicación:

 from n in Enumerable.Range(1, t.Length - 1) 
     let s = t.Substring(0, n) 
     where isSyllable(s) 

Calculamos todas las posibles sílabas de una palabra, de longitud 1 a la longitud de la palabra - 1 y verifica si es una sílaba. Eliminamos directamente las no sílabas. La palabra completa como sílaba se verificará más tarde.

 let e = t.Substring(n) 
     let f = splitter(e) 

Buscamos las sílabas de la parte restante de la cadena

 from g in f 
     select (new[] { s }).Concat(g).ToArray() 

Y encadenar los sílabas que se encuentran con la sílaba "actual". Tenga en cuenta que estamos creando muchas matrices inútiles. Si aceptamos tener un IEnumerable<IEnumerable<string>> como resultado, podemos llevar este ToArray.

(podríamos reescribir muchas filas juntas, eliminando muchos let, como

 from g in splitter(t.Substring(n)) 
     select (new[] { s }).Concat(g).ToArray() 

pero no lo hará por claridad)

Y concatenar la sílaba "actual" con las sílabas que se encuentran .

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

Aquí podríamos reconstruir la consulta un poco para que no utilice este Concat y crear matrices vacías, pero sería un poco más complejo (podríamos reescribir toda la función lambda como isSyllable(t) ? new[] { new string[] { t } }.Concat(oldLambdaFunction) : oldLambdaFunction)

En al final, si la palabra completa es una sílaba, agregamos la palabra completa como sílaba.De lo contrario, Concat una matriz vacía (lo que no Concat)

Answer 3

Puede que tenga problemas para escalar esto, para ser sincero, no estoy seguro de cuán grande es su conjunto de datos, sino una solución basada en un simple '¿es esto una sílaba?' necesitarás llamar a tu rutina de "detección de sílabas" aproximadamente 0 (n * n) para cada palabra donde n = el número de caracteres en la palabra (si esto no tiene sentido, significa que es probable que sea lento para grandes conjuntos de datos). . Esto no tiene en cuenta la escalabilidad del algoritmo de detección, que también puede ralentizarse a medida que agrega más sílabas. .

Sé que has dicho que tu proceso para identificar qué es una sílaba o no no es relevante, pero digamos que puedes cambiarlo para que funcione más como autocompletado, es decir, pasar al principio de una sílaba y que diga todo las sílabas que son posibles a partir de este punto serían mucho más escalables. Eche un vistazo a reemplazarlo con un trie si el rendimiento se sale de control.