在实时数据流中找到前 k 个频繁词

Question

我正在尝试使用 java 树集来解决算法问题。

问题如下：

Find top k frequent words in realtime data stream.

Implement three methods for Topk Class:

TopK(k). The constructor.
add(word). Add a new word.
topk(). Get the current top k frequent words.

我的想法是使用哈希图来记住频率和树集作为缓冲区。

我的实现通过了大部分情况，除了一个：

TopK(10)
add("aw")
add("fb")
add("fb")
topk()

答案应该是 [fb,aw] 但现在是 [fb,aw, fb] 但是，我的代码通过了如下测试用例：

    TopK(10)
    add("iiiiii")
    add("fb")
    add("fb")
    topk()

和

TopK(10)
add("fb")
add("fb")
topk()

我不知道出了什么问题，所以我在调用比较器时打印了一些值。它给了我这个：

 aw aw
11111111
fb aw
33333333
fb aw
33333333
fb aw
222222222
fb aw
222222222

这意味着，第二个 "fb" 与 "aw" 进行了两次比较，比较完成。我花了几个小时进行调试，但到目前为止我一无所获。

这是我的实现：

public class TopK {
    int size;
    HashMap<String, Integer> map;
    TreeSet<String> seen;
    public TopK(int k) {
        // do intialization if necessary
        size = k;
        seen = new TreeSet<String>(new Comparator<String>(){
            @Override
            public int compare(String str1, String str2){
                System.out.println(str1 + " "+ str2);
                if (str1.equals(str2)){
                    System.out.println("11111111");
                    return 0;
                }
                // important !https://www.jiuzhang.com/qa/7646/
                // 128 以后integer就不同了
                int number1 = map.get(str1);
                int number2 = map.get(str2);
                if (number1 != number2){
                    System.out.println("222222222");
                    return map.get(str1) - map.get(str2);
                } else {
                    System.out.println("33333333");
                    return str2.compareTo(str1);
                }
            }
        });
        map = new HashMap<String, Integer>();
    }

    /*
     * @param word: A string
     * @return: nothing
     */
    public void add(String word) {
        // write your code here
        if (!map.containsKey(word)){
            map.put(word, 0);
        }
        map.put(word, map.get(word) + 1);

        if (seen.contains(word)){
            seen.remove(word);
            seen.add(word);
        } else {
            seen.add(word);
            if (seen.size() > size){
                seen.pollFirst();
            }
        }
    }

    /*
     * @return: the current top k frequent words.
     */
    public List<String> topk() {
        // Write your code here
        List<String> results = new ArrayList<String>();
        Iterator it = seen.iterator();
        while(it.hasNext()) {
             String str = (String)it.next();
             results.add(0, str);
        }
        return results;
    }
}

Answer 1

我们的第一个线索是那个案例：

aw
fb
fb

失败但是：

iiiii
fb
fb

成功。

这可能只是因为以下行：return str2.compareTo(str1); - 如果出现的次数按字符串比较的顺序不同（这很容易检查 - 请这样做）。

我能想到的唯一解释是 java TreeSet 的 contains 函数有 "optimization" 只搜索到元素应该在的位置 - 如果你有顺序和元素不在它应该在的地方然后将其视为 none 存在于 TreeSet 中（考虑应该对数组进行排序以检查 log(n) 中的数字运行但在所有数组上都没有 - 所以如果他存在于错误的位置，你会想念他的。

请注意，在检查 contains 函数之前，您 更改了元素应 的位置。因此，让我们看一下第 2 次迭代 - 我们在地图中的 fb 和 aw 的值为 1。在 TreeSet 上，它们是 [fb,aw]（因为字符串比较如前所述）。现在你改变地图并且 fb 的值为 2 -> 它应该在最后一个地方但是 contains 函数与 aw 比较并且认为它应该在它之后 - 但他是最后一个元素，所以它假设 fb 不存在，只需添加他 -> 这就是为什么你看到 2 比较 fb 和 aw - 一个用于 contain 和一个用于 add.

希望这是可以理解的....

在实时数据流中找到前 k 个频繁词

Find top k frequent words in real time data stream

java

algorithm

treeset