存储流数据

Question

假设流数据(即每10分钟1000万串)，那么存储串的快速和存储器有效的方法是什么，使得如果两个串具有完全相同的字符但顺序不同，则它们只被存储一次。

我有一个解决方案来确定两个字符串是否满足这个标准，它在O(n)时间内工作，并基于构建每个字符串中字符的频率直方图并检查这些直方图是否相同。但这并不能很好地工作，因为每个新字符串都必须与( <= 10M)存储的字符串进行比较。我可以假设，如果我们将每个字符串存储为直方图，然后根据它们的大小将它们分成不同的块，这可以使事情变得更有效率，但这仍然会有巨大的时间复杂度。就时间而言，理想的解决方案是拥有一个完美的散列函数，它对直方图输入进行操作(字符串："cacao“->直方图："a2:c2:o1")

Answer 1

如果字符串足够短，那么比较排序的字符串可能比比较直方图更快(值得检查)。请注意，排序只执行一次。只需将排序后的字符串放入某种映射中:散列映射、树映射等

Answer 2

我可以想象，一个稍微定制的trie版本实际上应该是您感兴趣的。

好处：

• 在trie
• 中查找字符串的出现情况需要O(m)时间插入字符串的最坏情况性能为O(k)
• 如果您想要跟踪特定部分出现的次数，可以增加每个节点以在到达终端字符串时递增(这样您就可以跟踪终端"thou“、”track“等的出现)

缺点：

• This可以是内存密集型；您需要存储每个单词的每个字符，以及绘制到不同短语和每个单词的链接