Generowanie kombinacji podciągów z ciągu

Question

Próbuję wygenerować wszystkie możliwe kombinacje sylaby dla danego słowa. Proces identyfikacji sylaby nie jest tutaj istotny, ale generowanie wszystkich kombinacji daje mi problem. Myślę, że jest to prawdopodobnie możliwe do wykonania rekursywnie w kilku liniach, które myślę (chociaż w inny sposób jest w porządku), ale mam problem z uruchomieniem go. Czy ktoś może pomóc?

// 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

spróbuj uruchomić z tym:

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; 

Powrócisz:

Czy to pomaga na początku przynajmniej?

---

EDIT: Myślałem, że nieco dalej o tym problemie wymyślił tej pary zapytań:

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; 

Teraz query do tego:

daj mi znać jeśli to już przybite.

Answer 2

Zazwyczaj tego typu problemy rozwiązywane są za pomocą Tries. Opieram moją implementację Trie na How to create a trie in c# (ale zauważ, że przepisałem ją ponownie).

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 jest ciąg jesteś zainteresowany, parts będzie zawierać wykaz wykazów możliwych sylab (prawdopodobnie byłoby bardziej poprawne, aby to List<string[]>, ale jest to dość łatwo zrobić. Zamiast parts.Add(new List<string>(currentParts)); Napisać parts.Add(currentParts.ToArray()); i zmienić cały List<List<string>> do List<string[]>.

dodam wariant odpowiedzi Enigmativity thas jest theretically szybciej niż jego, ponieważ odrzuca błędne sylaby zamiast natychmiast po filtrując je później. Jeśli Ci się spodoba, należy daj mu +1, bo bez jego pomysłu ten warian nie byłoby to możliwe. Ale pamiętaj, że to wciąż hack. Rozwiązanie „prawo” jest w użyciu Trie (y) :-)

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(); 

Wyjaśnienie:

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

Mamy obliczyć wszystkie możliwe sylaby wyrazu, od długości 1 do długości słowo - 1 i sprawdź, czy to sylaba. Odsyłamy bezpośrednio nie-sylaby. Pełne słowo jako sylaba zostanie sprawdzone później.

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

przeszukujemy sylaby pozostałej części łańcucha

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

I ŁAŃCUCH znalezione sylaby z „aktualnym” sylaby. Zauważ, że tworzymy wiele bezużytecznych tablic. Jeśli przyjmiemy, że mamy IEnumerable<IEnumerable<string>>, możemy zabrać to ToArray.

(możemy przepisać wiele wierszy razem, usuwając wiele let, jak

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

ale nie zrobi to dla jasności)

I złączyć „bieżący” sylaby ze znalezionych sylab .

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

Tutaj możemy odbudować zapytania trochę tak, aby nie używać tego Concat i tworzenia pustych tablic, ale byłoby to trochę skomplikowane (możemy przepisać całą funkcję lambda jako isSyllable(t) ? new[] { new string[] { t } }.Concat(oldLambdaFunction) : oldLambdaFunction)

W koniec, jeśli całe słowo jest sylabą, dodajemy całe słowo jako sylabę.Inaczej Concat pustą tablicę (więc nie Concat)

Answer 3

Być może masz problemy ze skalowaniem tego, szczerze mówiąc, nie jestem pewien, jak duży jest twój zestaw danych, ale rozwiązanie oparte na prostym "czy to sylaba?" będziesz musiał wywołać swoją "sylabową wykrywalność" rutynowo około 0 (n * n) dla każdego słowa, gdzie n = liczba znaków w słowie (jeśli to nie ma znaczenia, oznacza to, że prawdopodobnie będzie wolne dla dużych zbiorów danych!) . Nie uwzględnia to skalowalności algorytmu wykrywania, który może również spowalniać w miarę dodawania kolejnych sylab. .

Wiem, że powiedziałeś, że Twój proces identyfikacji sylaby nie jest istotny, ale powiedzmy, że możesz go zmienić, aby działał bardziej jak autouzupełnianie, tj. Przekazywać na początku sylaby i informować o tym wszystkich. Sylaby, które są możliwe od tego miejsca, będą znacznie bardziej skalowalne. Rzuć okiem na zastąpienie go trie, jeśli wydajność wymknie się spod kontroli.