Генерация комбинаций подстрок из строки

Question

Я пытаюсь создать все возможные комбинации слогов для данного слова.Процесс определения слога здесь не уместен, но генерация всех комбинаций создает мне проблему.Я думаю, что это возможно сделать рекурсивно в несколько строк, я думаю (хотя любой другой способ подходит), но у меня возникают проблемы с его работой.Кто-нибудь может помочь?

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

Попробуйте начать с этого:

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;

Возвращает:

Помогает ли это начать хотя бы с начала?

---

РЕДАКТИРОВАТЬ: Я подумал немного об этой проблеме и придумал эту пару запросов:

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;

Теперь query вернуть это:

Дайте мне знать, если это прибито сейчас.

Answer 2

Обычно проблемы такого типа решаются с помощью Пытается . Я буду основывать свою реализацию Trie на Как создать Trie в C # (но обратите внимание, что я переписал его).

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 - это строка, которая вас интересует, parts будет содержать список списков возможных слогов (возможно, было бы правильнее сделать это List<string[]>, но это довольно легко сделать. Вместо этого из parts.Add(new List<string>(currentParts)); напишите parts.Add(currentParts.ToArray()); и измените все List<List<string>> на List<string[]>.

Я добавлю вариант ответа на загадку, который там намного быстрее, чем его, потому что он отбрасывает неправильные слоги сразу, а не фильтрует их позже. Если вам это нравится, вы должны дать ему +1, потому что без его идеи этот вариант был бы невозможен. Но обратите внимание, что это все еще взломать. «Правильное» решение заключается в использовании 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();

Объяснение:

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

Мы вычисляем все возможные слоги слова, от длины 1 до длины слова - 1, и проверяем, является ли это слогом. Мы отсеивали непосредственно неслоги. Полное слово в слоге будет проверено позже.

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

Ищем слоги оставшейся части строки

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

И мы связываем найденные слоги с «текущим» слогом. Обратите внимание, что мы создаем много бесполезных массивов. Если в результате мы получим IEnumerable<IEnumerable<string>>, мы можем забрать это ToArray.

(мы могли бы переписать много строк вместе, удалив множество let, например

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

но мы не будем делать это для ясности)

И мы объединяем «текущий» слог с найденными слогами.

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

Здесь мы могли бы немного перестроить запрос, чтобы не использовать это Concat и создавать пустые массивы, но это было бы немного сложно (мы могли бы переписать всю лямбда-функцию как isSyllable(t) ? new[] { new string[] { t } }.Concat(oldLambdaFunction) : oldLambdaFunction)

В конце концов, если все слово является слогом, мы добавляем все слово как слог. В противном случае мы Concat пустой массив (поэтому нет Concat)

Answer 3

Если честно, у вас могут быть проблемы с масштабированием, я не уверен, насколько велик ваш набор данных, но решение, основанное на простом «это слог?»вам нужно будет вызывать вашу процедуру «обнаружения слогов» примерно 0 (n * n) для каждого слова, где n = количество символов в слове (если это бессмысленно, это означает, что для больших наборов данных это может быть медленным!),Это не учитывает масштабируемость алгоритма обнаружения, который также может замедляться при добавлении большего количества слогов.,Я знаю, что вы сказали, что ваш процесс определения того, что такое слог или нет, не имеет отношения к делу, но, допустим, вы можете изменить его, чтобы он работал больше как автодополнение, т.е. передавал начало слога и просил рассказать вам все слоги.что возможно с этого момента будет гораздо более масштабируемым.Обратите внимание на его замену trie , если производительность выходит из-под контроля.