替换无限流中出现的标记的高效算法

Question

给出一个字符串映射，如下所示：

{'ABC': 'BCD', 'key': 'book',........}

和无限的文本流，例如：

"Sally had a key and a book with the ABC..."

将字符串映射中与键匹配的每个令牌替换为其相应值的有效算法是什么？

输出：

"Sally had a book and a book with the BCD..."

除了简单地拆分传入的令牌并查询字符串映射以进行容纳( O(1)操作)，还能做得更好吗？

代码将驻留在get服务器上--用户获得转换后的输出越快越好。

Answer 1

如果使用Aho-Corasick string matching algorithm，则无需将文本拆分为标记即可完成此操作。只需让叶节点上的输出状态返回替换字符串。

这可能比将文本拆分为标记更快，因为您不必管理字符串。它是一个字符接一个字符的。比使用哈希表查找快多少是你必须测试的东西。这也比简单的哈希表查找更难实现。

Answer 2

那么，您正在寻找的算法将至少是线性的，就您正在读取的标记的数量而言(因为在最好的情况下，您将对流中的每个标记执行固定数量的操作)，因此不会有任何改进，因为我假设您的输入流中没有特殊的冗余或模式(我们可以利用它来提高效率)。

对于映射，最有效的解决方案可能是对映射的键进行二进制搜索树--对于n个项的映射，我们只需将每个令牌与log n个不同的键进行比较。

如果对您的问题没有任何进一步的限制，我怀疑您还能获得比这更高的效率--对于m个令牌和n个键值对的映射，最坏情况下的复杂度为O(m log n)。

这很好，但不是很棒；所以重要的问题是:有什么方法可以利用您的数据吗？

Answer 3

我猜您实际上是在寻找某种高级语言的有效解决方案(node.js？python?)；一般来说，如果您正在使用这样一种语言，建议您使用该语言本身支持的数据结构，在Python中是一个字典，在Javascript中是一个对象。你可能已经知道了。

如果您是用低级语言编写的，那么您可能希望选择一种不涉及为每个单词构造不必要的字符串对象的优化，假设绝大多数单词都不会受到替换的影响。要做到这一点，一种方法是使用逐个字符的散列算法，并在读取输入字符时进行计算，每次开始一个新词时重新设置。当您到达单词末尾时，您可以检查平均O(1)时间，以确定某个目标是否具有该散列值。如果没有，请继续阅读。只要保留当前单词，就可以定期将输入缓冲区刷新到输出。

如果目标很长(情况可能并非如此)，则可以通过同时存储目标字符串的前缀(或一些前缀)的散列值来避免保留当前单词。然后，当您的输入缓冲区耗尽时，您可以检查当前散列值是否与适当长度的前缀之一的散列值匹配。偶尔检查此表单也可以解决基于故意创建散列冲突的DoS攻击(尽管在您的情况下，这不是什么问题；攻击者所能做的就是强制您对每个单词进行全文比较；他们无法将自己的单词添加到散列表中。)

但是，如果我使用像C这样的低级语言编写这段代码，我可能会将目标单词放入trie中，并跟踪每个输入字符的trie。一旦trie中没有匹配，您就可以刷新到当前单词的末尾；这很可能在所有不匹配的单词中很早就发生，甚至可能是在它们的第一个字符上。尽管trie通常比hash map需要更多的存储空间(甚至可能需要比BST更多的存储空间)，但是有一些存储压缩技术(如果您可以提前设置数据结构)，并且提前停止检查单词的能力可能是一种优势。