Уменьшить строку, используя грамматические правила

Question

Я пытаюсь найти подходящий алгоритм DP для упрощения строки. Например, у меня есть строка a b a b и список правил

1. a b -> b
2. a b -> c
3. b a -> a
4. c c -> b

Цель состоит в том, чтобы получить все одиночные символы, которые могут быть получены от данную строку, используя эти правила. Для этого примера это будет b, c. Длина данной строки может быть до 200 символов. Не могли бы вы предложить эффективный алгоритм?

Правила всегда равны 2 -> 1. У меня есть идея создания дерева, корневой строке присваивается строка, и каждый ребенок является строкой после одного преобразования, но я не уверен, что это лучший способ.

Answer 1

Для проблемы DP вам всегда нужно понять, как вы можете построить ответ для большой проблемы с точки зрения меньших под-проблем. Предположим, что у вас есть функция simplify, которая вызывается с вводом длины n. Есть n-1 способы разделить входные данные в первой и последней части. Для каждого из этих разделов вы должны рекурсивно называть свою функцию simplify как для первой части, так и для последней части. Окончательный ответ для ввода длины n - это набор всех возможных комбинаций ответов для первой и последней части, которые разрешены правилами.

В Python, это может быть реализована следующим образом:

rules = {'ab': set('bc'), 'ba': set('a'), 'cc': set('b')} 
all_chars = set(c for cc in rules.values() for c in cc) 

@ memoize 
def simplify(s): 
    if len(s) == 1: # base case to end recursion 
     return set(s) 

    possible_chars = set() 

    # iterate over all the possible splits of s 
    for i in range(1, len(s)): 
     head = s[:i] 
     tail = s[i:] 

     # check all possible combinations of answers of sub-problems 
     for c1 in simplify(head): 
      for c2 in simplify(tail): 
       possible_chars.update(rules.get(c1+c2, set())) 

       # speed hack 
       if possible_chars == all_chars: # won't get any bigger 
        return all_chars 

    return possible_chars 

Быстрая проверка:

In [53]: simplify('abab') 
Out[53]: {'b', 'c'} 

Чтобы сделать это достаточно быстро для больших строк (чтобы избежать экспоненциального поведения), вы должны использовать memoize decorator. Это важный шаг в решении проблем DP, иначе вы просто делаете вычисление грубой силы. Еще одно крошечное ускорение можно получить, возвращаясь из функции, как только possible_chars == set('abc'), так как в этот момент вы уже уверены, что можете генерировать все возможные результаты.

Анализ времени работы: для ввода длины n, есть 2 подстроки длины n-1, 3 подстроки длины n-2 ..., п подстроки длины 1, в общей сложности O(n^2) подзадач. Из-за memoization функция вызывается не более одного раза для каждой подзадачи. Максимальное время работы для одной подзадачи - O(n) из-за for i in range(len(s)), поэтому общее время работы не более O(n^3).

Answer 2

Пусть N - длина заданной строки и R - количество правил.

Расширение дерева сверху вниз дает вычислительную сложность O (NR^N) в худшем случае (строка ввода типа aaa... и правила aa -> a).

Доказательство:

Корень дерева имеет (N-1) R детей, которые имеют (N-1) R^2 детей, ..., которые имеют (N-1) R^N детей (листья).Таким образом, общая сложность представляет собой O ((N-1) R + (N-1) R^2 + ... (N-1) R^N) = O (N (1 + R 2+ ... + R^N)) = (с использованием binomial theorem) = O (N (R + 1)^N) = O (NR^N).

Рекурсивного Java реализация этого наивного подхода:

public static void main(String[] args) { 
    Map<String, Character[]> rules = new HashMap<String, Character[]>() {{ 
     put("ab", new Character[]{'b', 'c'}); 
     put("ba", new Character[]{'a'}); 
     put("cc", new Character[]{'b'}); 
    }}; 
    System.out.println(simplify("abab", rules)); 
} 

public static Set<String> simplify(String in, Map<String, Character[]> rules) { 
    Set<String> result = new HashSet<String>(); 
    simplify(in, rules, result); 
    return result; 
} 

private static void simplify(String in, Map<String, Character[]> rules, Set<String> result) { 
    if (in.length() == 1) { 
     result.add(in); 
    } 
    for (int i = 0; i < in.length() - 1; i++) { 
     String two = in.substring(i, i + 2); 
     Character[] rep = rules.get(two); 
     if (rep != null) { 
      for (Character c : rep) { 
       simplify(in.substring(0, i) + c + in.substring(i + 2, in.length()), rules, result); 
      } 
     } 
    } 
} 

---

Bas Swinckels's O (RN 3 ^) реализация Java (с HashMap в качестве кэша запоминания):

public static Set<String> simplify2(final String in, Map<String, Character[]> rules) { 
    Map<String, Set<String>> cache = new HashMap<String, Set<String>>(); 
    return simplify2(in, rules, cache); 
} 

private static Set<String> simplify2(final String in, Map<String, Character[]> rules, Map<String, Set<String>> cache) { 
    final Set<String> cached = cache.get(in); 
    if (cached != null) { 
     return cached; 
    } 
    Set<String> ret = new HashSet<String>(); 
    if (in.length() == 1) { 
     ret.add(in); 
     return ret; 
    } 
    for (int i = 1; i < in.length(); i++) { 
     String head = in.substring(0, i); 
     String tail = in.substring(i, in.length()); 
     for (String c1 : simplify2(head, rules)) { 
      for (String c2 : simplify2(tail, rules, cache)) { 
       Character[] rep = rules.get(c1 + c2); 
       if (rep != null) { 
        for (Character c : rep) { 
         ret.add(c.toString()); 
        } 
       } 
      } 
     } 
    } 
    cache.put(in, ret); 
    return ret; 
} 

---

Выход в обоих подходах:

[b, c] 

Answer 3

Если вы читаете эти правила справа налево, они выглядят точно так же, как правила контекстной свободной грамматики и имеют в основном то же значение. Вы можете применить к вашим данным алгоритм синтаксического анализа снизу вверх, например Earley algorithm, а также подходящее стартовое правило; что-то вроде

start <- start a 
     | start b 
     | start c 

, а затем просто исследовать лес разбора для кратчайшей цепи start с. В худшем случае, конечно, остается O (n^3), но Эрли довольно эффективен в наши дни.

Вы также можете создавать парные леса, когда parsing with derivatives. Возможно, вы сможете эффективно проверить их на короткие цепочки start.