1

我正在处理传入的文本流。例如 美国、英国、中国、俄罗斯、美国、英国、中国、法国、德国。

我需要将它们分解为 3 个单词（或者可能是 n 个单词）的序列，并分析哪个序列的频率最高。在上述情况下，美国、英国、中国的序列出现了两次。所以它的频率最高。

此外，我需要索引所有序列的频率。我曾尝试使用 C++ stl map 来部分解决一些问题，但我认为该解决方案并不优雅。原因是唯一索引m个唯一词，在使用 stl map 的 3 个词序列中，数学如下，

ixmxm + jxm + k

i, j, k 是每个单词的整数映射。

上述解决方案的问题在于连续的文本流，我们不知道唯一词的总数或 m。任何人都可以提出更好的算法吗？

4

3 回答 3

2

我认为你最好使用某种映射或三元组哈希表，因为这样你只存储实际发生的三元组，而使用数组你可以为所有可能的三元组腾出空间。如果您看到 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)。然而，它并不是很实用。

于 2013-08-29T03:43:11.050 回答
0

另一种选择是使用 anstd::string作为地图的键。每个键可以是 3 个单词的串联。这样，您可以唯一地定义每个三元组，而无需知道m.

但是，您必须为 2 个字符串实现一个顺序运算符，并将其作为映射声明的第三个参数传递，如本线程中所述：std::string as a key in std::map using a compare operator .

希望能帮助到你！

于 2013-08-29T03:58:22.733 回答
0 
map<vector<unsigned int>, unsigned int> sequenceFrequency;
vector<unsigned int> codedWord;

void MapSequenceFrequency(unsigned int key0, unsigned int key1, unsigned int key2)
{
    codedWord[0] = key0;
    codedWord[1] = key1;
    codedWord[2] = key2;

    map<vector<unsigned int>, unsigned int>::iterator it;

    if (sequenceFrequency.find(codedWord) == sequenceFrequency.end())
        sequenceFrequency[codedWord] = 0;
    else
        sequenceFrequency[codedWord]++;
}
于 2013-08-30T14:49:30.217 回答