如何将实现无空格字符串分词的Python算法转换为C#

第一行生成wordcost的代码 #

这行代码的作用是基于齐普夫定律构建单词成本字典，单词出现频率越高，对应的成本值越低：

• 输入的words是按使用频率从高到低排序的单词列表
• i是单词在列表中的索引（从0开始计数）
• 对每个单词k，计算成本公式为log((i+1)*log(单词总数量))，最终存入字典，键为单词，值为对应成本。

第二行best_match函数的代码 #

这是动态规划的核心逻辑，入参是当前处理到的字符串位置i，返回值是一个二元组：(最小匹配成本, 匹配到的单词长度)：

• 首先取cost数组中[max(0, i - 最大单词长度), i)区间的片段，倒序后带索引遍历得到候选集
• 对每个候选，计算「前序匹配成本c + 当前子串对应的单词成本（如果子串不在单词字典中，就取极大值作为惩罚）」
• 遍历所有候选后返回成本最小的那组结果。

你需要提前准备按频率从高到低排序的单词表文件words-by-frequency.txt，每个单词占一行即可。以下是完整代码：

using System;
using System.Collections.Generic;
using System.IO;
using System.Linq;

public static class WordSplitter
{
    private static readonly Dictionary<string, double> _wordCost;
    private static readonly int _maxWordLength;

    static WordSplitter()
    {
        // 加载单词表并初始化成本字典
        var words = File.ReadAllLines("words-by-frequency.txt")
            .Select(line => line.Trim())
            .Where(line => !string.IsNullOrEmpty(line))
            .ToList();
        
        int totalWordCount = words.Count;
        double logTotal = Math.Log(totalWordCount);
        _wordCost = new Dictionary<string, double>();
        
        for (int i = 0; i < words.Count; i++)
        {
            _wordCost[words[i]] = Math.Log((i + 1) * logTotal);
        }

        _maxWordLength = words.Max(w => w.Length);
    }

    public static string InferSpaces(string input)
    {
        if (string.IsNullOrEmpty(input))
            return string.Empty;

        List<double> cost = new List<double> { 0 };

        // 本地函数对应Python的best_match
        (double matchCost, int matchLength) BestMatch(int i)
        {
            int start = Math.Max(0, i - _maxWordLength);
            // 取cost对应区间倒序，带索引遍历
            var candidates = cost.Skip(start).Take(i - start).Reverse().Select((c, k) => (c, k));
            
            double minCost = double.MaxValue;
            int bestLength = 1;
            foreach (var (c, k) in candidates)
            {
                int substrStart = i - k - 1;
                int substrLength = k + 1;
                string substr = input.Substring(substrStart, substrLength);
                
                double currentCost = c + (_wordCost.TryGetValue(substr, out double wordCost) 
                    ? wordCost 
                    : double.MaxValue);

                if (currentCost < minCost)
                {
                    minCost = currentCost;
                    bestLength = substrLength;
                }
            }

            return (minCost, bestLength);
        }

        // 构建成本数组
        for (int i = 1; i <= input.Length; i++)
        {
            var (c, _) = BestMatch(i);
            cost.Add(c);
        }

        // 回溯得到拆分结果
        List<string> result = new List<string>();
        int pos = input.Length;
        while (pos > 0)
        {
            var (c, k) = BestMatch(pos);
            result.Add(input.Substring(pos - k, k));
            pos -= k;
        }

        result.Reverse();
        return string.Join(" ", result);
    }

    // 测试用例
    public static void Main()
    {
        Console.WriteLine(InferSpaces("helloworld")); // 输出 hello world
        Console.WriteLine(InferSpaces("thequickbrownfoxjumpsoverthelazydog"));
    }
}

内容的提问来源于stack exchange，提问作者lorenzl94