String/Character Font Mapping using recursion in C#

Question

Я создаю программу отображения шрифтов, где я хочу отобразить 2 шрифта разных языков.

Для примера A в Arial Font (Английский) будет отображаться с अ в 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)) - Dont работать на больших строк

[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

я бы подойти к этой проблеме по-другому, возможно, с помощью phonemes.Что вы хотите - это процесс, который преобразует

Английский текст -> Английские фонетики -> Хинди-представления каждой фонемы (или комбинаций) -> хинди транслитерированная строка.

Одна строка с открытым исходным кодом для синтезатора phoneme - eSpeak. Используя метод this, вы можете получить только фономы из библиотеки (отбросить волновые буферы). Теперь сканируйте английские фонемы и выберите фрагменты хинди с карты.

Примечание: Вы можете выбрать любую библиотеку, которая преобразует заданную строку на английском языке на стандартной карте фонемы, озвучки только один, что я видел раньше

Этот метод должен дать лучшие результаты и, мне кажется, быть «естественным» решением этой проблемы.

Надеюсь, это поможет!