5

要するに、ここでの質問に対する最初の回答をPython から C# に変換したいと思います。結合された単語を分割するための現在のソリューションは指数関数的であり、線形ソリューションが必要です。入力テキストにスペースがなく、大文字と小文字が一貫していると想定しています。

バックグラウンド

「wickedweather」などの結合された文字列を、C# を使用して「wicked weather」などの個別の単語に変換したいと考えています。指数時間を使用する再帰関数である実用的なソリューションを作成しましたが、これは私の目的には十分に効率的ではありません (少なくとも 100 個以上の結合された単語を処理する)。これまでに読んだ質問は参考になると思いますが、回答を Python から C# に翻訳することはできません。

私の現在の再帰的ソリューション

これは、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;
    }

ビタビ アルゴリズムの使用方法

アルゴリズムに提供するテキスト ファイル内の単語の位置に応じて確率が計算される、結合された文字列に対する最も可能性の高い解決策を導き出すアルゴリズムを作成したいと思います。ファイルが最初に英語で最も一般的な単語から始まり、次の行で 2 番目に一般的な単語というように、私の辞書で最も一般的でない単語まで続きます。ざっくりこんな感じ

  • の
  • なれ
  • と
  • ...
  • 弁護士

これは、私が使用したいテキストファイルの小さな例へのリンクです。 これは、私が使用したいはるかに大きなテキストファイルです

このファイル配置の背後にあるロジックは次のとおりです...

それらが Zipf の法則に従うと仮定するのは合理的です。つまり、単語のリストでランク n の単語は、およそ 1/(n log N) の確率を持ちます。ここで、N は辞書内の単語の数です。

Generic Human は、彼の優れた Python ソリューションで、これを私よりもはるかにうまく説明しています。問題に対する彼のソリューションを Python から C# に変換したいと考えていますが、これを試行するのに何時間も費やした後も、有効なソリューションを作成できませんでした。また、Viterbi アルゴリズムを使用した相対頻度は単語を分割する最良の方法ではないという考えにもオープンなままです。C# を使用してソリューションを作成するための他の提案はありますか?

4

2 に答える 2

2

書かれたテキストは文脈依存性が高く、マルコフ連鎖を使用して文構造をモデル化し、結合確率を推定することができます。残念ながら、文の構造は Viterbi の仮定を破っていますが、まだ望みはあります。Viterbi アルゴリズムは分枝限定最適化、別名「枝刈りされた動的計画法」(私が論文で示したもの) のケースであり、したがってコストがかかる場合でも-スプライシングの仮定が満たされない場合でも、コストの範囲を作成し、候補ソリューションの母集団を削減できます。しかし、ここではマルコフ連鎖を脇に置きましょう...確率が独立しており、それぞれが Zipf の法則に従うと仮定すると、知っておく必要があるのは、ビタビ アルゴリズムが加算コストの累積に作用するということです。

独立したイベントの場合、結合確率は個々の確率の積であり、負の対数確率がコストの適切な選択になります。

したがって、シングルステップのコストは-log(P)or log(1/P)which is log(index * log(N))which islog(index) + log(log(N))で、後者の項は定数です。

于 2016-12-07T22:41:34.297 に答える
2

Viterbi Algorithm についてはお手伝いできませんが、現在のアプローチについては 2 セント差し上げます。あなたのコードから、何が何でwordsあるかは正確にはわかりません。適切なデータ構造を選択しないと、これが実際のボトルネックになる可能性があります。直感として、最初Dictionary<char, HashSet<string>>はキーが各単語の最初の文字であるa を使用します。

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;
}

また、毎回ビルドを回避するために、ディスクにシリアル化することも検討します。

このようにどれだけ改善できるかはわかりませんが（現在の実装に関する完全な情報はありません）、ベンチマークして、改善が得られるかどうかを確認してください。

注: すべての単語が一貫して大文字と小文字が区別されていると想定しています。

于 2016-12-07T22:24:04.387 に答える