algorithm - 用于替换无限流中 token 出现的高效算法

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..."

除了简单地拆分传入的 token 并查询字符串映射以进行包含(O(1) 操作)之外，还有什么办法可以做得更好吗？

代码将驻留在网络服务器上——用户获得转换输出的速度越快越好。

Answer 1

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

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