从字符串生成子字符串的组合

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

通常此类问题可以使用 尝试 来解决。我将基于如何创建特里树来实现特里树在 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，但是很容易做到这一点，而不是 parts.Add(new List(currentParts)); 编写。 parts.Add(currentParts.ToArray()); 并将所有 List> 更改为 List 我将添加一个 Enigmativity 响应的变体，它实际上比他的更快，因为它会立即丢弃

错误的音节，而不是稍后过滤它们。如果您喜欢它，您应该给他一个。 +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)

我们计算 a 的所有可能的音节。单词，从长度 1 到单词的长度 - 1 并检查它是否是音节。我们直接剔除非音节。稍后将检查作为音节的完整单词。

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

我们搜索字符串剩余部分的音节

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

，并将找到的音节与“当前”音节链接起来。请注意，我们正在创建许多无用的数组。如果我们接受 IEnumerable> 作为结果，我们可以拿走这个 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 并创建空数组，但这会有点复杂（我们可以将整个 lambda 函数重写为 isSyllable(t) ? new[] { new string[] { t } }.Concat(oldLambdaFunction) : oldLambdaFunction)

最后，如果整个单词是一个音节，我们将整个单词添加为一个音节音节。否则我们Concat一个空数组（所以没有Concat）

Answer 3

说实话，您可能在扩展此数据时遇到问题，我不确定您的数据集有多大，但基于简单的“这是aa音节吗？”的解决方案您需要为每个单词调用大约 0(n*n) 的“音节检测”例程，其中 n = 单词中的字符数（如果这没有意义，则意味着对于大型数据集来说它可能会很慢！） 。这没有考虑到检测算法的可扩展性，当您添加更多音节时，检测算法也可能会变慢。 .

我知道您说过识别什么是音节或不是音节的过程是不相关的，但是可以说您可以更改它以使其更像自动完成功能，即传递音节的开头并让它告诉你从这一点起所有可能的音节将更具可扩展性。如果性能失控，请考虑将其替换为 trie 。