c# - C# での再帰を使用した文字列/文字フォント マッピング

Answer 1

私は貪欲なアルゴリズムでそれにアプローチします。このようなもの：

    // warning, untested
    public String Translate(String s, Dictionary<String, String> mapping)
    {
        String result = "";
        if (RecurTranslate(s, mapping, ref result))
            return result;

        throw new Exception("No translation");
    }

    private bool RecurTranslate(String s, Dictionary<String, String> mapping, ref String result)
    {
        if (s.Length == 0)
            return true;

        for (int prefixLen = s.Length; prefixLen > 0; --prefixLen)
        {
            String prefix = s.Substring(0, prefixLen);
            String trans;
            if (mapping.TryGetValue(prefix, out trans))
            {
                if (RecurTranslate(s.Substring(prefixLen), mapping, ref result))
                {
                    result = trans + result;
                    return true;
                }
            }
            else if (prefixLen == 1)
            {   // this branch allows a character to stand for itself
                if (RecurTranslate(s.Substring(prefixLen), mapping, ref result))
                {
                    result = prefix + result;
                    return true;
                }
            }
        }

        return false;
    }

これは、可能な限り最大の一致を探して、前から開始します。データによっては、他のアプローチの方が良い場合があります。たとえば、マッピングを長さ順に調べて最長の一致を見つけ、そこから分割します。

    private bool RecurTranslate2(String s, Dictionary<String, String> mapping, ref String result)
    {
        if (s.Length == 0)
            return true;

        foreach (var entry in mapping.Where(e => e.Key.Length <= s.Length).OrderByDescending(e => e.Key.Length))
        {
            if (s.Contains(entry.Key))
            {   // split into a before and after
                int idx = s.IndexOf(entry.Key);
                String before = s.Substring(0, idx);
                String after = s.Substring(idx + entry.Key.Length);
                String bRes = "", aRes = "";
                if (RecurTranslate2(before, mapping, ref bRes) && RecurTranslate2(after, mapping, ref aRes))
                {
                    result = aRes + entry.Value + bRes;
                    return true;
                }
            }
        }

        return false;
    }

最後に、これらの方法を組み合わせて遊ぶこともできます。ある長さのしきい値に達するまで RecurTranslate2 を使用してから、RecurTranslate に切り替えます。

コメントへの対応: 失敗したルックアップについては、新しい else ブランチを参照してください

Answer 2

おそらく音素を使用して、この問題に別の方法でアプローチします。あなたが欲しいのは変換するプロセスです

英語のテキスト->英語の音素->各音素（または組み合わせ）のヒンディー語表現->ヒンディー語の音訳文字列。

音素シンセサイザーへのオープンソース文字列の1つはeSpeakです。この方法を使用すると、ライブラリから音素のみを取得できます（ウェーブバッファを破棄します）。次に、英語の音素をスキャンして、地図からヒンディー語の断片を選びます。

注：英語の特定の文字列を標準の音素マップに変換する任意のライブラリを選択できます。eSpeakは私が以前に見たものにすぎません。

この方法はより良い結果をもたらすはずであり、私にはこの問題の「自然な」解決策であるように思われます。

お役に立てれば！

Answer 3

再帰バージョン - O(2^(string.Length-1)) - 大きな文字列では実行しないでください

[Test]
    public void StringSplit()
    {

        var splits = AllPossibleSplits("hello".Select(c => c.ToString()).ToList());

        Assert.AreEqual(16, splits.Count);
        Assert.AreEqual("hello", splits.First().First());
        Assert.AreEqual("hello".Length, splits.Last().Count());
    }

    private List<List<string>> AllPossibleSplits(List<string> source)
    {

        if (source.Count == 0)
        {
            return new List<List<string>>();
        }
        if (source.Count == 1)
        {
            return new List<List<string>> { source };
        }
        var firstTwoJoined = new List<string> { source[0] + source[1] };
        firstTwoJoined.AddRange(source.Skip(2));

        var justFirst = new List<string> { source[0] };
        var withoutFirst = AllPossibleSplits(source.Skip(1).ToList());

        var result = new List<List<string>>();
        result.AddRange(AllPossibleSplits(firstTwoJoined));
        result.AddRange(withoutFirst.Select(list => justFirst.Concat(list).ToList()));

        return result;
    }