4

有没有人知道如何使用内置collection.sort和comparator<string>界面按频率（从最小到最大）的顺序对单词列表进行排序？

我已经有一种方法可以获取文本文件中某个单词的计数。现在，我只需要创建一个方法来比较每个单词的计数，然后将它们放入按频率从最低到最高排序的列表中。

任何想法和提示将不胜感激。我在开始使用这种特定方法时遇到了麻烦。

public class Parser implements Comparator<String> {

    public Map<String, Integer> wordCount;

    void parse(String filename) throws IOException {
        File file = new File(filename);
        Scanner scanner = new Scanner(file);

        //mapping of string -> integer (word -> frequency)
        Map<String, Integer> wordCount = new HashMap<String, Integer>();

        //iterates through each word in the text file
        while(scanner.hasNext()) {
            String word = scanner.next();
            if (scanner.next()==null) {
                wordCount.put(word, 1);
            }
            else {
                wordCount.put(word, wordCount.get(word) + 1);;
                }
            }
            scanner.next().replaceAll("[^A-Za-z0-9]"," ");
            scanner.next().toLowerCase();
        }

    public int getCount(String word) {
        return wordCount.get(word);
    }

    public int compare(String w1, String w2) {
        return getCount(w1) - getCount(w2);
    } 

        //this method should return a list of words in order of frequency from least to   greatest
    public List<String> getWordsInOrderOfFrequency() {
        List<Integer> wordsByCount = new ArrayList<Integer>(wordCount.values());
        //this part is unfinished.. the part i'm having trouble sorting the word frequencies
        List<String> result = new ArrayList<String>();


    }
}
4

4 回答 4

7

首先，您的用法scanner.next()似乎不正确。next()每次调用时都会返回下一个单词并移动到下一个单词，因此以下代码：

if(scanner.next() == null){ ... }

并且

scanner.next().replaceAll("[^A-Za-z0-9]"," ");
scanner.next().toLowerCase();

会消耗然后扔掉的话。您可能想要做的是：

String word = scanner.next().replaceAll("[^A-Za-z0-9]"," ").toLowerCase();

在while循环的开头，以便对单词的更改保存在word变量中，而不仅仅是丢弃。

其次，wordCount地图的使用稍有破绽。您要做的是检查word地图中是否已经存在以决定要设置的字数。为此，scanner.next() == null您应该查看地图，而不是检查，例如：

if(!wordCount.containsKey(word)){
  //no count registered for the word yet
  wordCount.put(word, 1);
}else{
  wordCount.put(word, wordCount.get(word) + 1);
}

或者你可以这样做：

Integer count = wordCount.get(word);
if(count == null){
  //no count registered for the word yet
  wordCount.put(word, 1);
}else{
  wordCount.put(word, count+1);
}

我更喜欢这种方法，因为它更简洁，每个单词只进行一次地图查找，而第一种方法有时会进行两次查找。

现在，要按频率降序获取单词列表，您可以先将地图转换为列表，然后按照本文Collections.sort()中的建议应用。以下是适合您需求的简化版本：

static List<String> getWordInDescendingFreqOrder(Map<String, Integer> wordCount) {

    // Convert map to list of <String,Integer> entries
    List<Map.Entry<String, Integer>> list = 
        new ArrayList<Map.Entry<String, Integer>>(wordCount.entrySet());

    // Sort list by integer values
    Collections.sort(list, new Comparator<Map.Entry<String, Integer>>() {
        public int compare(Map.Entry<String, Integer> o1, Map.Entry<String, Integer> o2) {
            // compare o2 to o1, instead of o1 to o2, to get descending freq. order
            return (o2.getValue()).compareTo(o1.getValue());
        }
    });

    // Populate the result into a list
    List<String> result = new ArrayList<String>();
    for (Map.Entry<String, Integer> entry : list) {
        result.add(entry.getKey());
    }
    return result;
}

希望这可以帮助。

编辑： 按照@dragon66 的建议更改了比较功能。谢谢。

于 2012-04-15T04:36:00.760 回答
1

You can compare and extract ideas from the following:

public class FrequencyCount {

    public static void main(String[] args) {

        // read in the words as an array
        String s = StdIn.readAll();
        // s = s.toLowerCase();
        // s = s.replaceAll("[\",!.:;?()']", "");
        String[] words = s.split("\\s+");

        // sort the words
        Merge.sort(words);

        // tabulate frequencies of each word
        Counter[] zipf = new Counter[words.length];
        int M = 0;                                        // number of distinct words
        for (int i = 0; i < words.length; i++) {
            if (i == 0 || !words[i].equals(words[i-1]))   // short-circuiting OR
                zipf[M++] = new Counter(words[i], words.length);
            zipf[M-1].increment();
        }

        // sort by frequency and print
        Merge.sort(zipf, 0, M);                           // sorting a subarray
        for (int j = M-1; j >= 0; j--) {
            StdOut.println(zipf[j]);
        }
    }
}
于 2012-04-15T03:47:53.733 回答
1

一个解决方案，接近您的原始帖子，并按照 Torious 在评论中的建议进行更正和排序：

import java.util.*;

public class Parser implements Comparator <String> {

    public Map<String, Integer> wordCount;

    void parse ()
    {
        Scanner scanner = new Scanner (System.in);

        // don't redeclare it here - your attribute wordCount will else be shadowed
        wordCount = new HashMap<String, Integer> ();

        //iterates through each word in the text file
        while (scanner.hasNext ()) {
            String word = scanner.next ();
            // operate on the word, not on next and next of next word from Scanner
            word = word.replaceAll (" [^A-Za-z0-9]", " ");
            word = word.toLowerCase ();
            // look into your map:
            if (! wordCount.containsKey (word))
                wordCount.put (word, 1);
            else
                wordCount.put (word, wordCount.get (word) + 1);;
        }
    }

    public int getCount (String word) {
        return wordCount.get (word);
    }

    public int compare (String w1, String w2) {
        return getCount (w1) - getCount (w2);
    }

    public List<String> getWordsInOrderOfFrequency () {
        List<String> justWords = new ArrayList<String> (wordCount.keySet());
        Collections.sort (justWords, this);
        return justWords; 
    }

    public static void main (String args []) {
        Parser p = new Parser ();
        p.parse ();
        List<String> ls = p.getWordsInOrderOfFrequency ();
        for (String s: ls) 
            System.out.println (s);
    }
}
于 2012-04-16T03:40:51.950 回答
0

rodions 解决方案是一种泛型地狱，但我没有它更简单 - 只是不同。

最后，他的解决方案更短更好。

乍一看，TreeMap 可能是合适的，但它是按 Key 排序的，对按值排序没有帮助，而且我们不能切换 key-value，因为我们是按 key 查找的。

所以接下来的想法是生成一个HashMap，并使用Collections.sort，但是它不需要Map，只需要Lists进行排序。从一个 Map 中，有 entrySet，它产生另一个 Collection，它是一个 Set，而不是一个 List。那是我采取另一个方向的地方：

我实现了一个Iterator：我遍历entrySet，只返回值为1的Keys。如果值为2，我缓冲它们以备后用。如果 Iterator 用尽，我查看缓冲区，如果它不为空，我将使用缓冲区的迭代器，增加我寻找的最小值，并创建一个新的 Buffer。

Iterator/Iterable 对的优点是，可以通过简化的 for 循环获得值。

import java.util.*;

// a short little declaration :) 
public class WordFreq implements Iterator <Map.Entry <String, Integer>>, Iterable <Map.Entry <String, Integer>>
{
    private Map <String, Integer> counter;
    private Iterator <Map.Entry <String, Integer>> it;
    private Set <Map.Entry <String, Integer>> buf;
    private int maxCount = 1; 

    public Iterator <Map.Entry <String, Integer>> iterator () {
        return this;
    }

    // The iterator interface expects a "remove ()" - nobody knows why
    public void remove ()
    {
        if (hasNext ())
            next ();
    } 

    public boolean hasNext ()
    {
        return it.hasNext () || ! buf.isEmpty ();
    }

    public Map.Entry <String, Integer> next ()
    {
        while (it.hasNext ()) {
            Map.Entry <String, Integer> mesi = it.next ();
            if (mesi.getValue () == maxCount)
                return mesi;
            else
                buf.add (mesi);
        }
        if (buf.isEmpty ())
            return null;
        ++maxCount;
        it = buf.iterator (); 
        buf = new HashSet <Map.Entry <String, Integer>> ();     
        return next ();
    } 

    public WordFreq ()
    {
        it = fill ();
        buf = new HashSet <Map.Entry <String, Integer>> ();
        // The "this" here has to be an Iterable to make the foreach work
        for (Map.Entry <String, Integer> mesi : this)
        {
            System.out.println (mesi.getValue () + ":\t" + mesi.getKey ());
        }
    }

    public Iterator <Map.Entry <String, Integer>> fill ()
    {
        counter = new HashMap <String, Integer> ();
        Scanner sc = new Scanner (System.in);
        while (sc.hasNext ())
        {
            push (sc.next ());
        }
        Set <Map.Entry <String, Integer>> set = counter.entrySet ();
        return set.iterator ();
    }

    public void push (String word)
    {
        Integer i = counter.get (word);
        int n = 1 + ((i != null) ? i : 0); 
        counter.put (word, n);
    }

    public static void main (String args[])
    {
        new WordFreq ();
    }
}

由于我的解决方案是从标准输入读取的，因此您可以通过以下方式调用它：

cat WordFreq.java | java WordFreq
于 2012-04-15T05:57:53.697 回答