1

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

{'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）操作）之外，还有什么更好的方法吗？

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

4

4 回答 4

2

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

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

于 2013-04-13T04:14:28.457 回答
1

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

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

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

但是，如果我用 C 之类的低级语言编写此代码，我可能会将目标词放入 trie，并跟踪每个输入字符的 trie。只要在 trie 中没有匹配，就可以刷新到当前单词的末尾；这很可能在所有不匹配的单词中很早就发生，甚至可能在它们的第一个字符上发生。尽管 trie 通常需要比散列映射更多的存储空间（甚至可能需要比 BST 更多的存储空间），但也有存储压缩技术（如果您可以提前设置数据结构）并且能够提前停止检查单词可能是赢。

于 2013-04-13T04:19:42.300 回答
1

好吧，您正在寻找的算法至少与您正在阅读的令牌数量是线性的（因为充其量您将对流中的每个令牌执行恒定数量的操作），所以有'那里不会有任何改进，因为我假设您的输入流中没有特殊的冗余或模式（我们可以滥用它们来提高效率）。

至于映射，最有效的解决方案可能是映射键上的二叉搜索树——对于 n 个项目的映射，我们只需将每个标记与 log n 个不同的键进行比较。

如果对你的问题没有任何进一步的限制，我怀疑你会得到比这更有效的方法——m 个令牌和 n 个键值对的映射的最坏情况复杂度 O(m log n)。

这很不错，但不是很棒；如此重要的问题：有什么方法可以利用您的数据？

于 2013-04-13T01:52:14.870 回答
0

其他人提到了二进制搜索和哈希映射。我怀疑有一个稍微快一点的方法，因为你不关心内存使用的效率。对您要查找的数据进行桶排序并与之进行比较。这应该会加快比较速度——而不是散列完整的输入然后匹配，它总是在寻找一个完全匹配的。

鉴于地图，{ABC, ABD, DEF, GH}您的数据结构看起来像......

pos:                     1                   2
     0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6   <-- slot 26 is reserved for 
val: A 0 0 D 0 0 G 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0       "end of map token"
     |     |     |
     B     E     H   <-- sub buckets don't show all buckets as in the top level, but they
    / \    |     |       are all there.
   C   D   F     END
  /    |    \
END   END   END

扩展您接受的完整字符集，或每个字节 255 个可能的值。然后，当您获得输入时，您可以测试每个字符。



示例 1：

Input: ABC
    1: look up location 'Z' - 'A' = 0
    2: is there anything in this bucket? yes
    3: look in sub-buckets.  
    4: Is there anything in the 'Z'- 'B' bucket? yes
    5: look in sub buckets.
    6: Is there anything in the 'Z' - 'C' bucket? yes
    7: look in sub-buckets
    8: reached end of input token.  Is end of map bucket is marked? yes
    9: match found



示例 2：

Input: ABCD  (input token longer than closest match in map)
    1: look up location 'Z' - 'A' = 0
    2: is there anything in this bucket? yes
    3: look in sub-buckets.  
    4: Is there anything in the 'Z'- 'B' bucket? yes
    5: look in sub buckets.
    6: Is there anything in the 'Z' - 'C' bucket? yes
    7: look in sub-buckets
    8: Is there anything in the 'Z' - 'D' bucket? no
    9: match not found



示例 3：

Input: ABE
    1: look up location 'Z' - 'A' = 0
    2: is there anything in this bucket? yes
    3: look in sub-buckets.  
    4: Is there anything in the 'Z'- 'B' bucket? yes
    5: look in sub buckets.
    6: Is there anything in the 'Z' - 'E' bucket? no
    7: match found

于 2013-04-13T14:47:17.677 回答