Глобальные оптимальные строковые подстановки

Question

Я ищу некоторые указатели для записи функции (назовем ее replaceGlobal), которая берет входную строку и сопоставление подстрок с заменяющими значениями и применяет эти сопоставления, чтобы максимально возможное количество символов из строка ввода заменяется. Например:

replaceGlobal("abcde", { 
    'a' -> 'w', 
    'abc' -> 'x', 
    'ab' -> 'y', 
    'cde' -> 'z' 
}) 

вернется "yz" путем применения 'ab' -> 'y' и 'cde' -> 'z'.

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

Жадный подход дает неоптимальные результаты (показанные здесь Javascript):

"abcde".replace(/(abc|cde|ab|a)/g, function(x) { 
    return { 
     'a': 'w', 
     'abc': 'x', 
     'ab': 'y', 
     'cde': 'z' 
    }[x]; 
}); 

возвращается 'xde'

Любые мысли о хорошей отправной точкой здесь?

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

/------x------------\ 
    /-----y------\  \ 
/---w--\  \  \ /-------z------\ 
0 -----> a ----> b -----> c -----> d ----> e ----> $ 

, где края вдоль позвоночника имеют стоимость 1, но остальные края имеют нулевое значение.

Но это может быть слишком сложным.

Answer 1

Мне кажется, что dynamic programming - это путь. Это связано с ограничением:

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

В частности, у вас есть некоторые случайные строки АБВГДЕЖА в качестве входных данных. Теперь вы применяете какое-то правило для замены некоторой средней части, например de -> x. Теперь у вас есть аЬс х фг, где только (меньшие подзадачи) строки, которые вы теперь разрешено манипулировать являются абв и фг. И для повторяющихся подстрок вы можете использовать memoization.

Answer 2

основы Тиммерманс @ Matt комментариев и оригинальная идея DAG, вот что я придумал в Javascript в качестве первой попытки (я больше заинтересован в алгоритме сам, чем какая-либо конкретная реализация языка):

const replaceGlobal = (str, dict) => { 
    let open = []; // set of substitutions being actively explored 
    let best = { value: [], weight: 0 }; // optimal path info 

    // For each character in the input string, left to right 
    for (let c of str) { 
     // Add new nodes to `open` for all `substitutions` that 
     // start with `c` 
     for (let entry of dict) 
      if (entry.match[0] === c) 
       open.push({ 
        value: best.value.concat(entry.sub), 
        rest: entry.match, 
        weight: best.weight 
       }); 

     // Add current character onto best path 
     best.value.push(c); 
     ++best.weight; 

     // For each `open` path, try to match against the current character 
     let new_open = []; 
     for (let o of open) { 
      if (o.rest[0] === c) { 
       if (o.rest.length > 1) { // still more to match 
        new_open.push({ 
         rest: o.rest.slice(1), 
         value: o.value, 
         weight: o.weight 
        }); 
       } else { // full match found 
        if (o.weight < best.weight) 
         best = o; 
       } 
      } 
     } 
     open = new_open; 
    } 
    return best.value.join(''); 
}; 

Какой будет использоваться:

replaceGlobal('abcde', [ 
    { match: 'a', sub: 'w' }, 
    { match: 'abc', sub: 'x' }, 
    { match: 'ab', sub: 'y' }, 
    { match: 'cde', sub: 'z' } 
])) === 'yz' 

он проходит несколько простых модульных тестов, но я могу быть видом что-то глупо, и это все еще кажется более сложным, чем это необходимо.

Вы также можете сделать dict три символа, чтобы облегчить поиск матчей (и сделать то же самое с open). Даже с trie, я считаю, что этот подход все равно будет O(str.length * dict.length).