解析1 TB的文本并有效地计算每个单词的出现次数

Question

解析1 TB的文本并有效地计算每个单词的出现次数

VIR*_*IRA 54 c# algorithm

最近我遇到了一个面试问题,用任何语言创建一个算法,应该做到以下几点

阅读1 TB的内容
计算该内容中每个重新识别单词的计数
列出前10个最常出现的单词

你能告诉我为这个创建算法的最佳方法吗？

编辑:

好吧,让我们说内容是英文的.我们如何找到该内容中最常出现的前10个单词？我的另一个疑问是,如果他们故意提供唯一数据,那么我们的缓冲区将在堆大小溢出时到期.我们也需要处理它.

Answer 1

zeF*_*chy 62

面试答案

这项任务很有意思,而不是太复杂,所以这是开展良好技术讨论的好方法.我解决这项任务的计划是:

使用空格和标点符号作为分隔符,以单词形式分割输入数据
将每个找到的单词输入Trie结构,并在表示单词最后一个字母的节点中更新计数器
遍历完全填充的树以查找具有最高计数的节点

在采访的背景下......我会通过在纸板或纸上画树来展示Trie的想法.从空开始,然后根据包含至少一个重复单词的单个句子构建树.说"猫可以抓住老鼠".最后展示如何遍历树以找到最高计数.然后,我将证明这个树如何提供良好的内存使用,良好的单词查找速度(特别是在自然语言的情况下,许多单词彼此派生),并且适合于并行处理.

画在板上

绘制示例trie

演示

下面的C#程序在4核xeon W3520上以75秒的速度通过2GB文本,最多可以输出8个线程.性能大约是每秒430万字,而不是最优的输入解析代码.使用Trie结构存储单词时,在处理自然语言输入时内存不是问题.

笔记:

从古腾堡项目获得的测试文本
输入解析代码假定换行并且非常不理想
删除标点符号和其他非单词并不是很好
处理一个大文件而不是几个较小的文件需要少量代码才能开始读取文件中指定偏移量之间的线程.

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
}

Run Code Online (Sandbox Code Playgroud)

这里的输出来自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

Run Code Online (Sandbox Code Playgroud)

@zeFrenchy 多酷啊！这是我第一次听说特里树！这是一种非常酷的存储单词总和的方式！我也刚刚从下面的一个答案中读到了 DAWG，这带来了下一个问题：Trie 树和 DAWG 之间有什么区别？ (3认同)

Answer 2

Jer*_*fin 24

这里有很多东西取决于一些尚未指定的东西.例如,我们正在努力做这一次,还是我们试图建立一个系统,这样做定期和持续的基础上？我们对输入有任何控制吗？我们是处理所有单一语言的文本(例如,英语)还是代表多种语言(如果是,有多少语言)？

这些因为:

如果数据在单个硬盘驱动器上启动,并行计数(例如map-reduce)将不会产生任何真正的好处 - 瓶颈将是来自磁盘的传输速度.将副本复制到更多磁盘以便我们可以更快地计数将比直接从一个磁盘计数更慢.
如果我们设计一个系统来定期执行此操作,我们的大部分重点都放在硬件上 - 特别是,并行放置大量磁盘以增加带宽,并至少更接近于跟上中央处理器.
无论你正在阅读多少文字,你需要处理的离散词的数量是有限的 - 你是否有一个甚至一PB的英文文本的TB,你不会看到像数十亿的不同的英文单词.快速检查一下,牛津英语词典列出了大约600,000个英文单词.
尽管语言之间的实际单词明显不同,但每种语言的单词数量大致不变,因此我们构建的地图的大小将在很大程度上取决于所代表的语言数量.

这主要留下了可以表示多少种语言的问题.目前,让我们假设最糟糕的情况.ISO 639-2具有485种人类语言的代码.假设每种语言平均有700,000个单词,平均单词长度为每个单词10个字节的UTF-8.

只是存储为简单的线性列表,这意味着我们可以存储地球上每种语言的每个单词以及8字节的频率计数,略小于6千兆字节.如果我们使用类似Patricia trie的东西,我们可能会计划至少在某种程度上缩小 - 很可能达到3千兆字节或更少,尽管我对所有这些语言都不太了解.

现在,现实是我们几乎肯定高估了那里的许多地方的数字 - 相当多的语言共享相当数量的单词,许多(特别是较旧的)语言可能比英语少,并且浏览了列表,看起来有些可能根本没有书面形式.

简介:几乎任何合理的新桌面/服务器都有足够的内存来将地图完全保存在RAM中 - 更多的数据不会改变它.对于并行的一个(或几个)磁盘,我们无论如何都要进行I/O绑定,因此并行计数(等等)可能是净损失.在任何其他优化意味着很多之前,我们可能需要并行数十个磁盘.

+1用于进行系统分析.面试问题总是存在,他们想知道什么？你可以编程或者你可以设计一个系统. (3认同)

Answer 3

ami*_*mit 14

您可以尝试使用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))

Run Code Online (Sandbox Code Playgroud)

其次,你可以通过成对的单次迭代轻松找到具有topK最高出现率的那些,这个线程解释了这个概念.主要思想是保存前K个元素的最小堆,并在迭代时 - 确保堆始终包含到目前为止看到的前K个元素.完成后 - 堆包含前K个元素.

更具可扩展性(如果您的机器很少,则速度较慢)另一种选择是使用map-reduce排序功能,并根据出现情况对数据进行排序,然后只刷顶部K.

+1提到头部获得前十名 (2认同)
Map reduce是一种全新的方法，可能并不是他们想在面试问题中真正听到的。除非您也可以解释，HOW mapreduce实际可行。可以使用3行perl代码或6行C ++来实现此问题。如果用于许多处理器上的缩放，Map reduce实际上只是一件好事。这个问题的1 TB是，因此您不可能全部都放入内存... (2认同)
我不知道为什么你坚持使用函数式语言.我也可以用C或任何其他语言实现它的精确算法.问题是如何将数据从地图处理到reduce步骤.然后,您需要找到一种有效的方法.我在C中使用散列图,标记循环和评估循环的天真实现实际上是一种map reduce.但答案是指地图减少,如果你打算在面试中玩那张牌,你最好知道地图和减少步骤之间的位是如何工作的.当你开始拥有多台机器时会很有趣. (2认同)