C＃中使用递归的字符串/字符字体映射

Question

我正在创建一个字体映射程序，我要映射2种不同语言的字体。

例如，Arial Font（英语）中的A将与Kruti Dev Font（Hindi）中的अ对应。

我有这样创造了这个转换在数据库：

Native_Font  |  Foreign_Language_Font 
------------------------------------------- 
     A  |    अ 
     B  |    बी 

如果转换是为角色只限于它是确定。阅读本地字体的每个字符并在外文字体中查找其匹配字符。 （我已经做到了）

但是现在我必须为字符串做这也是真正的问题开始。

如果在数据库中提供了一个字符串，则将其完全转换。但是如果它的转换不存在，那么找一个少于一个字符的转换。

一个例子是

在数据库

Native_Font  |  Foreign_Language_Font 
------------------------------------------- 
    Cha   |    चा 
    r   |    र 
    t   |    ट 

和字Chart给出翻译。

1. 它会首先尝试转换全字Chart。如果它的映射发现一次。
2. 但是，如果它找不到Chart的直接转换，然后去Char。如果它的映射发现给予一次，然后找到t

各自的性格等

Chart 

Char t 

Cha rt 
Cha r t 

Ch art 
Ch ar t 
Ch a r t 

C hart 
C har t 
C ha r t 
C h a r t 

而且如果没有找到映射，应通过本地字体字符代替。怎么做？我相信应该使用递归。但是如何？

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。

回应的评论：对于未能查找

Answer 2

递归版本 - 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; 
    } 

Answer 3

见新else分支我想不同的解决这个问题，可能使用phonemes。你想要的是一个过程，转换为

英文文本 - >英文音素 - >每个音素（或组合）的印地语表示 - >印地文音译字符串。

音素合成器的一个开源字符串是eSpeak。使用this方法，您只能从库中获取音素（放弃波形缓冲区）。现在扫描英文音素并从地图中选取印地文片段。

注：您可以选择转换以英文标准音素地图给定的字符串任何库，eSpeak时仅仅是一个我以前

这个方法应该得到更好的结果可以看出，似乎对我成为这个问题的“自然”解决方案。

希望这会有所帮助！