如何在 C# 中实现 Viterbi 算法来拆分连接词？

Question

简而言之 - 我想将这里问题的第一个答案从 Python 转换为 C#。我目前拆分连接词的解决方案是指数级的，我想要一个线性解决方案。我假设输入文本中没有间距和一致的大小写。

背景

我希望使用 C# 将诸如“wickedweather”之类的连体字符串转换为单独的词，例如“wicked weather”。我已经创建了一个有效的解决方案，一个使用指数时间的递归函数，这对于我的目的来说根本不够有效（处理至少 100 多个连接词）。到目前为止，我已经阅读了这些问题，我认为这些问题可能会有所帮助，但我无法将他们的回答从 Python 转换为 C#。

• 如何拆分多个连接的单词？
• 需要帮助理解这个 Python Viterbi 算法
• 如何有效地从连续字符串中提取文字词？

我当前的递归解决方案

这适用于只想在 C# 中拆分几个单词（< 50）并且并不真正关心效率的人。

我当前的解决方案计算出所有可能的单词组合，找到最可能的输出并显示。我目前将最可能的输出定义为使用最长单个单词的输出 - 我更喜欢使用不同的方法。这是我当前的解决方案，使用递归算法。

static public string find_words(string instring)
    {
        if (words.Contains(instring)) //where words is my dictionary of words
        {
            return instring;
        }
        if (solutions.ContainsKey(instring.ToString()))
        {
            return solutions[instring];
        }

        string bestSolution = "";
        string solution = "";

        for (int i = 1; i < instring.Length; i++)
        {
            string partOne = find_words(instring.Substring(0, i));
            string partTwo = find_words(instring.Substring(i, instring.Length - i));
            if (partOne == "" || partTwo == "")
            {
                continue;
            }
            solution = partOne + " " + partTwo;
            //if my current solution is smaller than my best solution so far (smaller solution means I have used the space to separate words fewer times, meaning the words are larger)
            if (bestSolution == "" || solution.Length < bestSolution.Length) 
            {
                bestSolution = solution;
            }
        }
        solutions[instring] = bestSolution;
        return bestSolution;
    }

该算法依赖于条目文本中没有空格或其他符号（这里并不是真正的问题，我并不担心拆分标点符号）。在字符串中添加的随机附加字母可能会导致错误，除非我将字母表中的每个字母都存储为字典中的“单词”。这意味着“wickedweatherdykjs”将使用上述算法返回“wicked weather dykj s”，而我更喜欢“wicked weather dykjs”的输出。

我更新的指数解决方案：

    static List<string> words = File.ReadLines("E:\\words.txt").ToList(); 
    static Dictionary<char, HashSet<string>> compiledWords = buildDictionary(words);

    private void btnAutoSpacing_Click(object sender, EventArgs e)
    {
        string text = txtText.Text;
        text = RemoveSpacingandNewLines(text); //get rid of anything that breaks the algorithm
        if (text.Length > 150)
        {
            //possibly split the text up into more manageable chunks?
            //considering using textSplit() for this.
        }
        else 
        {
            txtText.Text = find_words(text);
        }
    }

    static IEnumerable<string> textSplit(string str, int chunkSize)
    {
        return Enumerable.Range(0, str.Length / chunkSize)
            .Select(i => str.Substring(i * chunkSize, chunkSize));
    }

    private static Dictionary<char, HashSet<string>> buildDictionary(IEnumerable<string> words)
    {
        var dictionary = new Dictionary<char, HashSet<string>>();

        foreach (var word in words)
        {
            var key = word[0];

            if (!dictionary.ContainsKey(key))
            {
                dictionary[key] = new HashSet<string>();
            }

            dictionary[key].Add(word);
        }

        return dictionary;
    }

    static public string find_words(string instring)
    {
        string bestSolution = "";
        string solution = "";

        if (compiledWords[instring[0]].Contains(instring))
        {
            return instring;
        }

        if (solutions.ContainsKey(instring.ToString()))
        {
            return solutions[instring];
        }

        for (int i = 1; i < instring.Length; i++)
        {
            string partOne = find_words(instring.Substring(0, i));
            string partTwo = find_words(instring.Substring(i, instring.Length - i));
            if (partOne == "" || partTwo == "")
            {
                continue;
            }
            solution = partOne + " " + partTwo;
            if (bestSolution == "" || solution.Length < bestSolution.Length)
            {
                bestSolution = solution;
            }
        }
        solutions[instring] = bestSolution;
        return bestSolution;
    }

我想如何使用维特比算法

我想创建一个算法来计算出最可能的连接字符串的解决方案，其中概率是根据我提供给算法的文本文件中单词的位置来计算的。假设文件首先从英语中最常用的单词开始，然后在下一行从第二个最常用的单词开始，依此类推，直到我的字典中最不常用的单词。它看起来大致是这样的

• 这
• 是
• 和
• ...
• 律师

这是我想使用的此类文本文件的一个小示例的链接。 这是我想使用的更大的文本文件

这个文件定位背后的逻辑如下...

可以合理地假设它们遵循 Zipf 定律，即单词列表中排名为 n 的单词的概率大约为 1/(n log N)，其中 N 是字典中的单词数。

Generic Human在他出色的 Python 解决方案中比我能更好地解释这一点。我想将他对问题的解决方案从 Python 转换为 C#，但是在花了很多时间尝试这个之后，我还没有能够产生一个有效的解决方案。我也仍然认为 Viterbi 算法的相对频率可能不是拆分单词的最佳方式，还有其他关于使用 C# 创建解决方案的建议吗？

Answer 1

无法帮助您使用维特比算法，但我会就您当前的方法给出两分钱。从你的代码来看，它并不完全清楚是什么words。如果您没有选择好的数据结构，这可能会成为真正的瓶颈。凭直觉，我最初会选择Dictionary<char, HashSet<string>>关键是每个单词的第一个字母的位置：

private static Dictionary<char, HashSet<string>> buildDictionary(IEnumerable<string> words)
{
    var dictionary = new Dictionary<char, HashSet<string>>();

    foreach (var word in words)
    {
        var key = word[0];

        if (!dictionary.ContainsKey(key))
        {
            dictionary[key] = new HashSet<string>();
        }

        dictionary[key].Add(word);
    }

    return dictionary;
}

我还考虑将其序列化到磁盘，以避免每次都构建它。

不确定您可以像这样做出多少改进（没有当前实施的完整信息），但对其进行基准测试并查看是否获得任何改进。

注意：我假设所有单词的大小写都是一致的。