objective-c - 打印文件中最常用的单词(字符串)Objective-C

Question

objective-c 的新手，需要帮助来解决这个问题:

写一个有两个参数的函数:

• 1 一个表示文本文档的字符串

• 2 一个整数，提供要返回的项目数。实现该函数，使其返回按词频排序的字符串列表，最常出现的词在前。使用您的最佳判断来决定单词的分隔方式。您的解决方案应该在 O(n) 时间内运行，其中 n 是文档中的字符数。像对生产/商业系统一样实现此功能。您可以使用任何标准数据结构。

到目前为止我尝试了什么(正在进行的工作):`//正在进行的函数

// -(NSString *) wordFrequency:(int)itemsToReturn  inDocument:(NSString *)textDocument ;
//  Get the desktop directory (where the text document is)

NSURL *desktopDirectory = [[NSFileManager defaultManager] URLForDirectory:NSDesktopDirectory inDomain:NSUserDomainMask appropriateForURL:nil create:NO error:nil];

 //  Create full path to the file
 NSURL *fullPath = [desktopDirectory URLByAppendingPathComponent:@"document.txt"];

 //  Load the string
 NSString *content = [NSString stringWithContentsOfURL:fullPath encoding:NSUTF8StringEncoding error:nil];
 //  Optional code for confirmation - Check that the file is here and print its content to the console
 //  NSLog(@" The string is:%@", content);

 // Create an array with the words contain in the string
  NSArray *myWords = [content componentsSeparatedByString:@" "];

 //  Optional code for confirmation - Print content of the array to the console
 //  NSLog(@"array: %@", myWords);
 //  Take an NSCountedSet of objects in an array and order those objects by their object count then returns a sorted array, sorted in descending order by the count of the objects.

  NSCountedSet *countedSet = [[NSCountedSet alloc] initWithArray:myWords];
  NSMutableArray *dictArray = [NSMutableArray array];
  [countedSet enumerateObjectsUsingBlock:^(id obj, BOOL *stop) {
  [dictArray addObject:@{@"word": obj,
                               @"count": @([countedSet countForObject:obj])}];
    }];

  NSLog(@"Words sorted by count: %@", [dictArray sortedArrayUsingDescriptors:@[[NSSortDescriptor sortDescriptorWithKey:@"count" ascending:NO]]]);
 }
return 0;
 }

Answer 1

这是 ma​​p-reduce 的经典工作。我对 Objective-C 非常熟悉，但据我所知 - 这些概念在其中很容易实现。

第一个 map-reduce 正在计算出现的次数。
这一步基本上就是把元素按照单词分组，然后统计。

map(text):
   for each word in text:
       emit(word,'1')
reduce(word,list<number>):
    emit (word,sum(number))

使用 map-reduce 的另一种方法是使用迭代计算和 HashMap ，它是一个计算每个单词出现次数的直方图。

在你有了一个数字和出现的列表之后，你所要做的就是从中找出前 k 个。这在这个线程中得到了很好的解释:Store the largest 5000 numbers from a stream of numbers .
在这里，“比较器”是#occurances of each word，如上一步计算的那样。

基本思想是使用一个最小堆，并在其中存储 k 个第一个元素。
现在，迭代剩余的元素，如果新元素大于顶部(堆中的最小元素)，则移除顶部并用新元素替换它。

最后，您有一个包含 k 个最大元素的堆，并且它们已经在堆中 - 因此它们已经排序(虽然顺序相反，但处理起来相当容易) .

复杂度为 O(nlogK)

要实现 O(n + klogk)，您可以使用 selection algorithm而不是min-heap方案得到top-k，然后对检索到的元素进行排序。