0

我正在实现一个 splaytree 来保存单词及其频率，并选择创建一个 Pair 类来保存每个单词频率（键值）对。也就是说，splaytree 的每个节点都持有一对 Pair 类。Pair 类如下所示：

public class SplayEntry<K, V> implements Comparable<SplayEntry<K, V>>{

public K word;
public V frequency;

public SplayEntry(K word, V frequency) {
    this.word = word;
    this.frequency = frequency;
}
getters, setters, hashCode, equals, compareTo etc...

Splaytree：

public class SplayTree<AnyType extends Comparable<? super AnyType>> {

public SplayTree( )
{
    nullNode = new BinaryNode<AnyType>( null );
    nullNode.left = nullNode.right = nullNode;
    root = nullNode;
}

并且有 BinaryNode 类。

我遇到的问题是如何将每个单词和频率对放入树中，并检查该对是否已经存在，如果存在，将频率提高一倍。我逐行读取文本文件并将每一行拆分为单词，然后执行 countWords() 方法，该方法现在一团糟：

    public void countWords(String line) {
    line = line.toLowerCase();
    String[] words = line.split("\\P{L}+");
    SplayEntry<String, Integer> entry = new SplayEntry<String, Integer>(null, null);
    for (int i = 0, n = words.length; i < n; i++) {
        Integer occurances = 0;
        entry.setWord(words[i]);
        entry.setFrequency(occurances);

        if (tree.contains(entry.equals(entry)) && entry.getFrequency() == 0) {
            occurances = 1;

        } else {
            int value = occurances.intValue();
            occurances = new Integer(value + 1);
            entry.setFrequency(occurances);
        }

        entry = new SplayEntry<String, Integer>(words[i], occurances);
        tree.insert(entry);
    }
}

我知道这并没有真正起作用，我需要帮助来弄清楚我应该如何实例化 SplayEntry 类以及以什么顺序？我还希望该方法对于 words 数组中的每个单词，检查它是否存在于树内（包含）的 SplayEntry 中，如果该单词是新单词，则频率将为 1，否则频率将为是+1。最后，我只是将新的 SplayEntry 添加到 Splaytree 中，然后将其放入适当的节点中。

现在我只是因为在同一段代码上工作了太多时间而不是必要的时间而使自己感到困惑，我非常感谢一些可以引导我朝着正确方向前进的指针！

如果我没有说清楚，请告诉我。

4

1 回答 1

1

我建议使用展开树的标准实现，即没有计数器，并有一个单独HashMap的频率。这不会牺牲复杂性，因为对展开树的操作是 O(log n)，而对 a 的操作HashMap是 O(1)。为了保持封装和不变量，您可以将两者放在一个更大的类中，该类公开所需的操作。

于 2011-10-12T22:24:29.573 回答