最近我遇到了一个面试问题，用任何语言创建一个算法，它应该执行以下操作
- 读取 1 TB 的内容
- 计算该内容中每个重复出现的单词
- 列出出现频率最高的 10 个单词
您能否让我知道为此创建算法的最佳方法？
编辑：
好的，假设内容是英文的。我们如何找到该内容中出现频率最高的前 10 个单词？我的另一个疑问是，如果他们故意提供唯一数据，那么我们的缓冲区将因堆大小溢出而过期。我们也需要处理。
问问题
14955 次
16 回答
65
面试答案
这个任务很有趣，不太复杂，因此是开始良好技术讨论的好方法。我完成这项任务的计划是：
- 将输入数据拆分为单词，使用空格和标点符号作为分隔符
- 将找到的每个单词输入到Trie结构中，并在表示单词的最后一个字母的节点中更新计数器
- 遍历完全填充的树以查找具有最高计数的节点
在采访的背景下……我会通过在白板或纸上画树来展示Trie的想法。从空开始，然后基于包含至少一个重复单词的单个句子构建树。说“猫捉老鼠”。最后展示如何遍历树以找到最高计数。然后，我将证明这棵树如何提供良好的内存使用、良好的单词查找速度（尤其是在许多单词相互派生的自然语言的情况下）以及适用于并行处理。
在黑板上画
演示
下面的 C# 程序在 4 核至强 W3520 上在 75 秒内处理 2GB 的文本，最多使用 8 个线程。性能约为每秒 430 万字，但输入解析代码并不理想。使用Trie 结构存储单词，在处理自然语言输入时，内存不是问题。
笔记：
- 从Gutenberg 项目获得的测试文本
- 输入解析代码假定换行符并且非常次优
- 标点符号和其他非单词的去除做得不是很好
- 处理一个大文件而不是几个小文件将需要少量代码来开始读取文件内指定偏移量之间的线程。
using System;
using System.Collections.Generic;
using System.Collections.Concurrent;
using System.IO;
using System.Threading;
namespace WordCount
{
class MainClass
{
public static void Main(string[] args)
{
Console.WriteLine("Counting words...");
DateTime start_at = DateTime.Now;
TrieNode root = new TrieNode(null, '?');
Dictionary<DataReader, Thread> readers = new Dictionary<DataReader, Thread>();
if (args.Length == 0)
{
args = new string[] { "war-and-peace.txt", "ulysees.txt", "les-miserables.txt", "the-republic.txt",
"war-and-peace.txt", "ulysees.txt", "les-miserables.txt", "the-republic.txt" };
}
if (args.Length > 0)
{
foreach (string path in args)
{
DataReader new_reader = new DataReader(path, ref root);
Thread new_thread = new Thread(new_reader.ThreadRun);
readers.Add(new_reader, new_thread);
new_thread.Start();
}
}
foreach (Thread t in readers.Values) t.Join();
DateTime stop_at = DateTime.Now;
Console.WriteLine("Input data processed in {0} secs", new TimeSpan(stop_at.Ticks - start_at.Ticks).TotalSeconds);
Console.WriteLine();
Console.WriteLine("Most commonly found words:");
List<TrieNode> top10_nodes = new List<TrieNode> { root, root, root, root, root, root, root, root, root, root };
int distinct_word_count = 0;
int total_word_count = 0;
root.GetTopCounts(ref top10_nodes, ref distinct_word_count, ref total_word_count);
top10_nodes.Reverse();
foreach (TrieNode node in top10_nodes)
{
Console.WriteLine("{0} - {1} times", node.ToString(), node.m_word_count);
}
Console.WriteLine();
Console.WriteLine("{0} words counted", total_word_count);
Console.WriteLine("{0} distinct words found", distinct_word_count);
Console.WriteLine();
Console.WriteLine("done.");
}
}
#region Input data reader
public class DataReader
{
static int LOOP_COUNT = 1;
private TrieNode m_root;
private string m_path;
public DataReader(string path, ref TrieNode root)
{
m_root = root;
m_path = path;
}
public void ThreadRun()
{
for (int i = 0; i < LOOP_COUNT; i++) // fake large data set buy parsing smaller file multiple times
{
using (FileStream fstream = new FileStream(m_path, FileMode.Open, FileAccess.Read))
{
using (StreamReader sreader = new StreamReader(fstream))
{
string line;
while ((line = sreader.ReadLine()) != null)
{
string[] chunks = line.Split(null);
foreach (string chunk in chunks)
{
m_root.AddWord(chunk.Trim());
}
}
}
}
}
}
}
#endregion
#region TRIE implementation
public class TrieNode : IComparable<TrieNode>
{
private char m_char;
public int m_word_count;
private TrieNode m_parent = null;
private ConcurrentDictionary<char, TrieNode> m_children = null;
public TrieNode(TrieNode parent, char c)
{
m_char = c;
m_word_count = 0;
m_parent = parent;
m_children = new ConcurrentDictionary<char, TrieNode>();
}
public void AddWord(string word, int index = 0)
{
if (index < word.Length)
{
char key = word[index];
if (char.IsLetter(key)) // should do that during parsing but we're just playing here! right?
{
if (!m_children.ContainsKey(key))
{
m_children.TryAdd(key, new TrieNode(this, key));
}
m_children[key].AddWord(word, index + 1);
}
else
{
// not a letter! retry with next char
AddWord(word, index + 1);
}
}
else
{
if (m_parent != null) // empty words should never be counted
{
lock (this)
{
m_word_count++;
}
}
}
}
public int GetCount(string word, int index = 0)
{
if (index < word.Length)
{
char key = word[index];
if (!m_children.ContainsKey(key))
{
return -1;
}
return m_children[key].GetCount(word, index + 1);
}
else
{
return m_word_count;
}
}
public void GetTopCounts(ref List<TrieNode> most_counted, ref int distinct_word_count, ref int total_word_count)
{
if (m_word_count > 0)
{
distinct_word_count++;
total_word_count += m_word_count;
}
if (m_word_count > most_counted[0].m_word_count)
{
most_counted[0] = this;
most_counted.Sort();
}
foreach (char key in m_children.Keys)
{
m_children[key].GetTopCounts(ref most_counted, ref distinct_word_count, ref total_word_count);
}
}
public override string ToString()
{
if (m_parent == null) return "";
else return m_parent.ToString() + m_char;
}
public int CompareTo(TrieNode other)
{
return this.m_word_count.CompareTo(other.m_word_count);
}
}
#endregion
}
这里是跨 8 个线程处理相同的 20MB 文本 100 次的输出。
Counting words...
Input data processed in 75.2879952 secs
Most commonly found words:
the - 19364400 times
of - 10629600 times
and - 10057400 times
to - 8121200 times
a - 6673600 times
in - 5539000 times
he - 4113600 times
that - 3998000 times
was - 3715400 times
his - 3623200 times
323618000 words counted
60896 distinct words found
于 2012-09-12T21:57:53.453 回答
24
这里很大程度上取决于一些尚未指定的事情。例如，我们是尝试做一次，还是尝试建立一个系统来定期和持续地做这件事？我们对输入有任何控制权吗？我们是在处理全部使用一种语言（例如英语）的文本还是代表多种语言（如果是，有多少种）？
这些很重要，因为：
- 如果数据从单个硬盘驱动器开始，并行计数（例如，map-reduce）不会有任何真正的好处——瓶颈将是磁盘的传输速度。将副本复制到更多磁盘以便我们可以更快地计数将比直接从一个磁盘计数要慢。
- 如果我们要设计一个系统来定期执行此操作，那么我们的大部分重点实际上是在硬件上——具体来说，有很多并行磁盘以增加我们的带宽，并且至少更接近于跟上中央处理器。
- 无论您阅读多少文本，您需要处理的离散单词的数量都是有限的——无论您有 1 TB 甚至 1 PB 的英文文本，您都不会看到数十亿的不同的英语单词。快速检查一下，牛津英语词典列出了大约 600,000 个英语单词。
- 虽然不同语言之间的实际单词明显不同，但每种语言的单词数量大致是恒定的，因此我们构建的地图的大小将在很大程度上取决于所代表的语言数量。
这主要留下了可以表示多少种语言的问题。目前，让我们假设最坏的情况。ISO 639-2 有 485 种人类语言的代码。假设每种语言平均有 700,000 个单词，并且每个单词的平均单词长度为 10 个字节的 UTF-8。
只是存储为简单的线性列表，这意味着我们可以将地球上每种语言的每个单词以及 8 字节的频率计数存储在略小于 6 GB 的空间中。如果我们改用 Patricia trie 之类的东西，我们可能至少可以计划缩小一些 - 很可能是 3 GB 或更少，尽管我对所有这些语言的了解还不够，无法完全确定。
现在，现实情况是，我们几乎可以肯定地高估了那里许多地方的数字——相当多的语言共享相当多的单词，许多（尤其是较老的）语言的单词可能比英语少，并且浏览一下列表中，似乎包含了一些可能根本没有书面形式的内容。
总结：几乎任何相当新的桌面/服务器都有足够的内存来将地图完全保存在 RAM 中——更多的数据不会改变这一点。对于一个（或几个）并行磁盘，无论如何我们都会受到 I/O 限制，因此并行计数（等等）可能是净损失。在任何其他优化意义重大之前，我们可能需要并行处理数十个磁盘。
于 2012-08-30T15:28:28.590 回答
15
您可以为此任务尝试使用map-reduce方法。map-reduce 的优势在于可扩展性，因此即使对于 1TB、10TB 或 1PB，同样的方法也可以使用，并且您无需做很多工作来修改算法以适应新的比例。该框架还将负责在集群中的所有机器（和核心）之间分配工作。
首先 - 创建(word,occurances)对。
伪代码将是这样的：
map(document):
for each word w:
EmitIntermediate(w,"1")
reduce(word,list<val>):
Emit(word,size(list))
其次，您可以通过对对的单次迭代轻松找到出现次数最高的那些，该线程解释了这个概念。主要思想是保持前 K 个元素的最小堆，并在迭代时 - 确保堆始终包含到目前为止看到的前 K 个元素。完成后 - 堆包含前 K 个元素。
一个更具可扩展性（如果你的机器很少的话会更慢）的替代方案是你使用 map-reduce 排序功能，并根据出现次数对数据进行排序，然后只需 grep 前 K。
于 2012-08-30T05:31:15.273 回答
9
为此需要注意三件事。
具体来说：文件太大而无法保存在内存中，单词列表（可能）太大而无法保存在内存中，对于 32 位 int 而言，字数可能太大。
一旦你通过了这些警告，它应该是直截了当的。游戏正在管理可能很大的单词列表。
如果它更容易（防止你的头旋转）。
“您正在运行一台 Z-80 8 位机器，具有 65K 的 RAM 和一个 1MB 的文件......”
同样的问题。
于 2012-08-30T05:27:20.850 回答
5
It depends on the requirements, but if you can afford some error, streaming algorithms and probabilistic data structures can be interesting because they are very time and space efficient and quite simple to implement, for instance:
- Heavy hitters (e.g., Space Saving), if you are interested only in the top n most frequent words
- Count-min sketch, to get an estimated count for any word
Those data structures require only very little constant space (exact amount depends on error you can tolerate).
See http://alex.smola.org/teaching/berkeley2012/streams.html for an excellent description of these algorithms.
于 2012-09-16T06:37:24.900 回答
3
我很想使用 DAWG（维基百科和包含更多详细信息的 C# 文章）。在叶子节点上添加一个计数字段非常简单，有效的内存并且在查找方面表现非常好。
编辑：虽然你试过简单地使用 aDictionary<string, int>吗？>哪里<string, int代表单词和计数？也许您尝试过早地进行优化？
编者注：这篇文章最初链接到这篇维基百科文章，这似乎是关于术语 DAWG 的另一种含义：一种存储一个单词的所有子字符串的方法，用于有效的近似字符串匹配。
于 2012-09-13T05:17:18.203 回答
2
另一种解决方案可能是使用SQL表，并让系统尽可能好地处理数据。word首先为集合中的每个单词创建具有单个字段的表。
然后使用查询（对不起语法问题，我的 SQL 生锈了 - 这实际上是一个伪代码）：
SELECT DISTINCT word, COUNT(*) AS c FROM myTable GROUP BY word ORDER BY c DESC
总体思路是先生成一个包含所有单词的表（存储在磁盘上），然后使用查询(word,occurances)为您进行计数和排序。然后，您可以从检索到的列表中取出前 K 个。
致所有人：如果我在 SQL 语句中确实有任何语法或其他问题：请随时编辑
于 2012-08-30T06:22:49.447 回答
2
首先，我最近才“发现” Trie 数据结构，而 zeFrenchy 的回答非常适合让我加快速度。
我确实在评论中看到有几个人就如何提高其性能提出了建议，但这些只是微小的调整，所以我想我会与你分享我发现的真正瓶颈...... ConcurrentDictionary。
我想尝试使用线程本地存储，您的示例给了我一个很好的机会来做到这一点，经过一些小的更改，每个线程使用一个字典，然后在 Join() 看到性能提高 ~30% 之后组合字典（在我的机器上，跨 8 个线程处理 20MB 100 次从 ~48 秒到 ~33 秒）。
代码粘贴在下面，您会注意到与批准的答案没有太大变化。
PS 我没有超过 50 个声望点，所以我不能把它放在评论中。
using System;
using System.Collections.Generic;
using System.IO;
using System.Linq;
using System.Text;
using System.Threading;
namespace WordCount
{
class MainClass
{
public static void Main(string[] args)
{
Console.WriteLine("Counting words...");
DateTime start_at = DateTime.Now;
Dictionary<DataReader, Thread> readers = new Dictionary<DataReader, Thread>();
if (args.Length == 0)
{
args = new string[] { "war-and-peace.txt", "ulysees.txt", "les-miserables.txt", "the-republic.txt",
"war-and-peace.txt", "ulysees.txt", "les-miserables.txt", "the-republic.txt" };
}
List<ThreadLocal<TrieNode>> roots;
if (args.Length == 0)
{
roots = new List<ThreadLocal<TrieNode>>(1);
}
else
{
roots = new List<ThreadLocal<TrieNode>>(args.Length);
foreach (string path in args)
{
ThreadLocal<TrieNode> root = new ThreadLocal<TrieNode>(() =>
{
return new TrieNode(null, '?');
});
roots.Add(root);
DataReader new_reader = new DataReader(path, root);
Thread new_thread = new Thread(new_reader.ThreadRun);
readers.Add(new_reader, new_thread);
new_thread.Start();
}
}
foreach (Thread t in readers.Values) t.Join();
foreach(ThreadLocal<TrieNode> root in roots.Skip(1))
{
roots[0].Value.CombineNode(root.Value);
root.Dispose();
}
DateTime stop_at = DateTime.Now;
Console.WriteLine("Input data processed in {0} secs", new TimeSpan(stop_at.Ticks - start_at.Ticks).TotalSeconds);
Console.WriteLine();
Console.WriteLine("Most commonly found words:");
List<TrieNode> top10_nodes = new List<TrieNode> { roots[0].Value, roots[0].Value, roots[0].Value, roots[0].Value, roots[0].Value, roots[0].Value, roots[0].Value, roots[0].Value, roots[0].Value, roots[0].Value };
int distinct_word_count = 0;
int total_word_count = 0;
roots[0].Value.GetTopCounts(top10_nodes, ref distinct_word_count, ref total_word_count);
top10_nodes.Reverse();
foreach (TrieNode node in top10_nodes)
{
Console.WriteLine("{0} - {1} times", node.ToString(), node.m_word_count);
}
roots[0].Dispose();
Console.WriteLine();
Console.WriteLine("{0} words counted", total_word_count);
Console.WriteLine("{0} distinct words found", distinct_word_count);
Console.WriteLine();
Console.WriteLine("done.");
Console.ReadLine();
}
}
#region Input data reader
public class DataReader
{
static int LOOP_COUNT = 100;
private TrieNode m_root;
private string m_path;
public DataReader(string path, ThreadLocal<TrieNode> root)
{
m_root = root.Value;
m_path = path;
}
public void ThreadRun()
{
for (int i = 0; i < LOOP_COUNT; i++) // fake large data set buy parsing smaller file multiple times
{
using (FileStream fstream = new FileStream(m_path, FileMode.Open, FileAccess.Read))
using (StreamReader sreader = new StreamReader(fstream))
{
string line;
while ((line = sreader.ReadLine()) != null)
{
string[] chunks = line.Split(null);
foreach (string chunk in chunks)
{
m_root.AddWord(chunk.Trim());
}
}
}
}
}
}
#endregion
#region TRIE implementation
public class TrieNode : IComparable<TrieNode>
{
private char m_char;
public int m_word_count;
private TrieNode m_parent = null;
private Dictionary<char, TrieNode> m_children = null;
public TrieNode(TrieNode parent, char c)
{
m_char = c;
m_word_count = 0;
m_parent = parent;
m_children = new Dictionary<char, TrieNode>();
}
public void CombineNode(TrieNode from)
{
foreach(KeyValuePair<char, TrieNode> fromChild in from.m_children)
{
char keyChar = fromChild.Key;
if (!m_children.ContainsKey(keyChar))
{
m_children.Add(keyChar, new TrieNode(this, keyChar));
}
m_children[keyChar].m_word_count += fromChild.Value.m_word_count;
m_children[keyChar].CombineNode(fromChild.Value);
}
}
public void AddWord(string word, int index = 0)
{
if (index < word.Length)
{
char key = word[index];
if (char.IsLetter(key)) // should do that during parsing but we're just playing here! right?
{
if (!m_children.ContainsKey(key))
{
m_children.Add(key, new TrieNode(this, key));
}
m_children[key].AddWord(word, index + 1);
}
else
{
// not a letter! retry with next char
AddWord(word, index + 1);
}
}
else
{
if (m_parent != null) // empty words should never be counted
{
m_word_count++;
}
}
}
public int GetCount(string word, int index = 0)
{
if (index < word.Length)
{
char key = word[index];
if (!m_children.ContainsKey(key))
{
return -1;
}
return m_children[key].GetCount(word, index + 1);
}
else
{
return m_word_count;
}
}
public void GetTopCounts(List<TrieNode> most_counted, ref int distinct_word_count, ref int total_word_count)
{
if (m_word_count > 0)
{
distinct_word_count++;
total_word_count += m_word_count;
}
if (m_word_count > most_counted[0].m_word_count)
{
most_counted[0] = this;
most_counted.Sort();
}
foreach (char key in m_children.Keys)
{
m_children[key].GetTopCounts(most_counted, ref distinct_word_count, ref total_word_count);
}
}
public override string ToString()
{
return BuildString(new StringBuilder()).ToString();
}
private StringBuilder BuildString(StringBuilder builder)
{
if (m_parent == null)
{
return builder;
}
else
{
return m_parent.BuildString(builder).Append(m_char);
}
}
public int CompareTo(TrieNode other)
{
return this.m_word_count.CompareTo(other.m_word_count);
}
}
#endregion
}
于 2015-10-20T19:16:17.677 回答
1
作为一种快速的通用算法，我会这样做。
Create a map with entries being the count for a specific word and the key being the actual string.
for each string in content:
if string is a valid key for the map:
increment the value associated with that key
else
add a new key/value pair to the map with the key being the word and the count being one
done
然后你可以在地图中找到最大值
create an array size 10 with data pairs of (word, count)
for each value in the map
if current pair has a count larger than the smallest count in the array
replace that pair with the current one
print all pairs in array
于 2012-08-30T05:30:24.367 回答
0
下面的方法只会读取一次您的数据，并且可以针对内存大小进行调整。
- 以 1GB 为单位读取文件
- 对于每个块，列出 5000 个出现频率最高的单词及其频率
- 根据频率合并列表（1000 个列表，每个列表 5000 个单词）
- 返回合并列表的前 10 名
理论上你可能会漏词，虽然我认为这个机会非常非常小。
于 2012-09-11T09:28:50.837 回答
0
Storm 是值得关注的技术。它将数据输入（spouts）的角色与处理器（bolts）分开。风暴书的第2章解决了你的确切问题，并且很好地描述了系统架构 - http://www.amazon.com/Getting-Started-Storm-Jonathan-Leibiusky/dp/1449324010
与 Hadoop 的批处理相比，Storm 是更实时的处理。如果您的数据是现有的，那么您可以将负载分配到不同的 spout 并将它们传播到不同的 bolts 进行处理。
该算法还将支持超过 TB 的数据，因为日期将在实时到达时进行分析。
于 2012-09-16T19:59:18.387 回答
0
那么第一个想法是以哈希表/数组或其他任何形式管理数据库以保存每个单词的出现，但根据数据大小，我宁愿：
- 获取出现次数 >= 2 的第 10 个找到的单词
- 获取这些单词在整个字符串中出现的次数并在计数时删除它们
- 重新开始，一旦你有两组 10 个单词，你会得到两组中出现次数最多的 10 个单词
- 对字符串的其余部分（不再包含这些单词）执行相同的操作。
您甚至可以尝试提高效率，从第一个找到的 10 个单词开始，例如出现次数 >= 5 或更多，如果没有找到，则减少此值，直到找到 10 个单词。通过这个，您有一个很好的机会避免使用内存密集保存所有出现的单词，这是大量数据，并且您可以节省扫描轮次（在一个好的情况下）
但在最坏的情况下，您可能比传统算法有更多的轮次。
顺便说一句，这是一个问题，我会尝试使用函数式编程语言而不是 OOP 来解决。
于 2012-08-30T05:41:18.050 回答
0
非常有趣的问题。它更多地涉及逻辑分析而不是编码。随着英语语言和有效句子的假设，它变得更容易。
您不必计算所有单词，只需计算长度小于或等于给定语言平均单词长度的单词（英语为 5.1）。因此，您不会有记忆问题。
至于读取文件，您应该选择并行模式，通过操作空格的文件位置来读取块（您选择的大小）。例如，如果您决定读取 1MB 的块，则除第一个块之外的所有块都应该更宽一些（左起 +22 个字节，右起 +22 个字节，其中 22 代表最长的英文单词 - 如果我是对的）。对于并行处理，您将需要一个并发字典或将合并的本地集合。
请记住，通常您最终会得到前十名作为有效停用词列表的一部分（这可能是另一种反向方法，只要文件的内容是普通的，它也有效）。
于 2012-09-16T21:45:20.487 回答
0
好吧，就个人而言，我会将文件拆分为不同大小的文件，例如 128mb，在扫描时始终在内存中保留两个，任何发现的单词都将添加到哈希列表中，并且列表计数，然后我会迭代列表的列表在最后找到前 10 名...
于 2012-08-30T05:45:51.403 回答
0
尝试考虑特殊的数据结构来解决此类问题。在这种情况下，特殊类型的树（例如尝试以特定方式存储字符串）非常有效。或者第二种方法来构建自己的解决方案，比如计算单词。我猜这 TB 的数据是英文的，那么我们通常有大约 600,000 个单词，所以可以只存储这些单词并计算哪些字符串会重复 + 这个解决方案需要正则表达式来消除一些特殊字符。第一个解决方案会更快，我很确定。
http://en.wikipedia.org/wiki/Trie
这是 java
http://algs4.cs.princeton.edu/52trie/TrieST.java.html中轮胎的实现
于 2014-10-09T12:39:46.753 回答
0
MapReduce
WordCount 可以通过使用 hadoop 的 mapreduce 有效地实现。
https://hadoop.apache.org/docs/r1.2.1/mapred_tutorial.html#Example%3A+WordCount+v1.0
通过它可以解析大文件。它使用集群中的多个节点来执行此操作。
public void map(LongWritable key, Text value, OutputCollector<Text, IntWritable> output, Reporter reporter) throws IOException {
String line = value.toString();
StringTokenizer tokenizer = new StringTokenizer(line);
while (tokenizer.hasMoreTokens()) {
word.set(tokenizer.nextToken());
output.collect(word, one);
}
}
public static class Reduce extends MapReduceBase implements Reducer<Text, IntWritable, Text, IntWritable> {
public void reduce(Text key, Iterator<IntWritable> values, OutputCollector<Text, IntWritable> output, Reporter reporter) throws IOException {
int sum = 0;
while (values.hasNext()) {
sum += values.next().get();
}
output.collect(key, new IntWritable(sum));
}
}
于 2017-07-23T07:47:27.817 回答