我正在处理传入的文本流。例如 美国、英国、中国、俄罗斯、美国、英国、中国、法国、德国。
我需要将它们分解成 3 个词(或可能是 n 个词)的序列,然后分析哪个序列的出现频率最高。在上述情况下,序列 USA, UK, China 出现了两次。所以频率最高。
此外,我需要索引所有序列的频率。我曾尝试使用 C++ STL map 部分解决部分问题,但我认为解决方案并不优雅。原因是使用 STL 映射在 3 个单词序列中唯一索引 m 个唯一单词,数学如下,
i x m x m + j x m + k
i, j, k 是每个单词的整数映射。
上述解决方案的问题是在连续的文本流中,我们不知道唯一单词的总数或 m。谁能提出更好的算法?
最佳答案
我认为您最好使用某种映射或三元组哈希表,因为那样您只存储实际出现的三元组,而使用数组可以为所有可能的三元组腾出空间。如果您看到 n 个单词,它们可能都是不同的,在这种情况下,您存储了大约 n 个三元组 - 但是包含 n 个不同单词的所有三元组的数组的大小为 n^3。
出于好奇,存在从非负整数对到非负整数的双射映射。其中一个是 (a,b)->(a+b)(a+b+1)/2 + b 映射 (0, 0) (0, 1) (1, 0) (0, 2) (1 , 1) (2,1) ... 到 0, 1, 2, 3, 4, 5, .. - 将其视为通过将它们写在正方形中然后向下对角线编号来对对进行编号。您可以使用它两次将数字的三元组映射到一个数字:(a, b, c) -> ((a, b), c)。然而,它并不是很实用。
关于c++ - 在流中查找单词序列频率的最佳算法是什么,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/18501784/