全局最佳字符串替换

Question

我正在寻找一些指针来编写一个函数（我们称之为replaceGlobal），该函数接受输入字符串和子字符串到替换值的映射，并应用这些映射，以便替换输入字符串中尽可能多的字符。例如：

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

将通过应用'ab' -> 'y'和'cde' -> 'z'返回"yz"。

该函数将仅应用一轮替换，因此它不能替换一个值，然后将部分替换值用作另一个替换的一部分。

贪婪的方法会产生非最佳结果（在Javascript中显示）：

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

返回'xde'

对这里的良好起点有什么想法吗？

我认为问题归结为在加权 DAG 中找到成本最低的路径，该 DAG 由输入字符串作为脊柱和替换提供的其他边缘构建：

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

其中沿脊柱的边的成本为 1，但其他边的成本为 0。

但这可能使事情过于复杂。

Answer 1

在我看来

，动态编程是要走的路。这是由于限制：

该函数只会应用一轮替换，因此它不能 替换一个值，然后将部分替换值用作 另一个替代。

具体来说，假设你有一些随机字符串abcdefg作为输入。现在你应用一些规则来替换一些中间部分，比如 de -> x。现在你有abcx fg，其中你现在唯一允许操作的（较小的子问题）字符串是abc和fg。对于重复的子字符串，您可以利用记忆。

Answer 2

基于@Matt Timmermans的评论和最初的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执行相同的操作）。即使进行了尝试，我相信这种方法仍然会O(str.length * dict.length)。