4

目标：

编写一个带有两个参数的函数：(1) 表示文本文档的字符串和 (2) 提供要返回的项目数的整数。实现该函数，使其返回按词频排序的字符串列表，首先出现最频繁的词。使用您的最佳判断来决定如何分隔单词。您的解决方案应该在 O(n) 时间内运行，其中 n 是文档中的字符数。

我的想法是，在最坏的情况下，函数的输入可能是文档中的单词总数，从而将问题减少到按单词的频率排序。这让我认为如果我使用比较排序方法，时间复杂度的下限将是 O (n log n)。所以，我的想法是最好的方法是实现计数排序。这是我的代码。

我想让你告诉我我的分析是否正确，我已经用我对时间复杂度的想法对代码进行了注释，但它肯定是不正确的。这段代码的实际时间和空间复杂度是多少？另外，我想知道这实际上是否是一种好方法，是否有任何替代方法可以在实践中使用。 

### n is number of characters in string, k is number of words ###
def word_frequencies(string, n)
  words = string.split(/\s/)  # O(n)
  max = 0
  min = Float::INFINITY
  frequencies = words.inject(Hash.new(0)) do |hash,word|  # O(k)
    occurrences = hash[word] += 1                     # O(1)
    max = occurrences if occurrences > max            # O(1)
    min = occurrences if occurrences < min            # O(1)
    hash;                                             # O(1)  
  end

  ### perform a counting sort ###
  sorted = Array.new(max + words.length)

  delta = 0

  frequencies.each do |word, frequency|   #O(k)
    p word + "--" + frequency.to_s
    index = frequency
    if sorted[index]
      sorted[index] = sorted[index].push(word)  # ??? I think O(1).
    else
      sorted[index] = [word]                    # O(1)
    end
  end

  return sorted.compact.flatten[-n..-1].reverse   
  ### Compact is O(k).  Flatten is O(k).  Reverse is O(k). So O(3k)
end

### Total --- O(n + 5k) = O(n).  Correct? 
### And the space complexity is O(n) for the hash + O(2k) for the sorted array.  
### So total O(n).


text = "hi hello hi my name is what what hi hello hi this is a test test test test hi hi hi what hello these are some words these these"

p word_frequencies(text, 4)
4

3 回答 3

3

两种方式：

def word_counter(string, max)
  string.split(/\s+/)
        .group_by{|x|x}
        .map{|x,y|[x,y.size]} 
        .sort_by{|_,size| size} # Have to sort =/
        .last(max)
end

def word_counter(string, max)

  # Create a Hash and a List to store values in.
  word_counter, max_storage = Hash.new(0), []

  #Split the string an and add each word to the hash:
  string.split(/\s+/).each{|word| word_counter[word] += 1}

  # Take each word and add it to the list (so that the list_index = word_count)
  # I also add the count, but that is not really needed
  word_counter.each{|key, val| max_storage[val] = [*max_storage[val]] << [key, val]}

  # Higher count will always be at the end, remove nils and get the last "max" elements.
  max_storage.compact.flatten(1).last(max)

end
于 2013-11-12T09:34:56.477 回答
2

一个想法如下：

  1. 您已经在构建一个给出给定单词频率的哈希图。
  2. 现在遍历这个哈希映射并创建一个反向“哈希集”。那是给定频率的一组单词。
  3. 找到最大频率并输出该频率的单词集。
  4. 减少它，并检查哈希集中的单词。
  5. 继续这样做直到所需的单词数。

该算法的顺序应为 O(f)，其中 f 是任何单词的最大频率。任何单词的最大频率最多应为 n，其中 n 是所需的字符数。

于 2013-11-12T09:15:40.050 回答
1

示例，快速方法:)

#assuming you read from the file and get it to a string called str

h = {}
arr = str.split("\n")
arr.each do |i|
  i.split(" ").each do |w|
    if h.has_key[w]
      h[w] += 1
    else
      h[w] = 1
    end
  end
end
Hash[h.sort_by{|k, v| v}.reverse]

这可行，但可以改进。

于 2013-11-12T07:08:34.100 回答