1 테라 바이트의 텍스트를 구문 분석하고 각 단어의 발생 횟수를 효율적으로 계산
최근에 나는 다음을 수행해야하는 모든 언어로 알고리즘을 만드는 인터뷰 질문을 보았습니다.
- 1TB의 콘텐츠 읽기
- 해당 콘텐츠에서 반복되는 각 단어를 계산합니다.
- 가장 자주 발생하는 상위 10 개 단어 나열
이에 대한 알고리즘을 만드는 가장 좋은 방법을 알려주시겠습니까?
편집하다:
좋습니다. 콘텐츠가 영어로되어 있다고 가정 해 보겠습니다. 해당 콘텐츠에서 가장 자주 나오는 상위 10 개 단어를 어떻게 찾을 수 있습니까? 내 다른 의심은 의도적으로 고유 한 데이터를 제공하는 경우 버퍼가 힙 크기 오버플로와 함께 만료된다는 것입니다. 우리는 그것도 처리해야합니다.
인터뷰 답변
이 작업은 너무 복잡하지 않고 흥미 롭기 때문에 좋은 기술 토론을 시작할 수있는 좋은 방법입니다. 이 작업을 수행하려는 내 계획은 다음과 같습니다.
- 공백과 구두점을 구분 기호로 사용하여 입력 데이터를 단어로 분할
- 단어의 마지막 글자를 나타내는 노드에서 업데이트 된 카운터 로 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
}
여기에서는 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
여기에서 많은 것은 지정되지 않은 몇 가지 사항에 달려 있습니다. 예를 들어,이 작업을 한 번 시도하고 있습니까, 아니면 정기적이고 지속적으로이를 수행 할 시스템을 구축하려고합니까? 입력을 제어 할 수 있습니까? 우리는 모두 단일 언어 (예 : 영어)로 된 텍스트를 다루고 있습니까? 아니면 여러 언어로 표현되는 (그렇다면 몇 개)?
이는 다음과 같은 이유로 중요합니다.
- 데이터가 단일 하드 드라이브에서 시작되는 경우 병렬 카운팅 (예 : 맵 축소)은 아무런 효과가 없습니다. 병목 현상은 디스크의 전송 속도가 될 것입니다. 더 빨리 계산할 수 있도록 더 많은 디스크에 복사하는 것은 하나의 디스크에서 직접 계산하는 것보다 느립니다.
- 정기적으로이 작업을 수행하도록 시스템을 설계하는 경우 대부분의 강조점은 실제로 하드웨어에 있습니다. 특히 대역폭을 늘리기 위해 많은 디스크를 병렬로 사용하고 최소한 CPU.
- 아무리 많은 텍스트를 읽고 있더라도 처리해야하는 개별 단어의 수에는 제한이 있습니다. 테라 바이트 단위의 영어 텍스트가 있더라도 수십억 개의 텍스트를 볼 수는 없습니다. 영어로 다른 단어. 빠른 확인을 위해 Oxford English Dictionary는 약 600,000 단어를 영어로 나열합니다.
- 실제 단어는 언어마다 분명히 다르지만 언어 당 단어 수는 거의 일정하므로 작성하는지도의 크기는 표현되는 언어 수에 따라 크게 달라집니다.
그것은 대부분 얼마나 많은 언어를 표현할 수 있는지에 대한 질문을 남깁니다. 지금은 최악의 경우를 가정 해 보겠습니다. ISO 639-2에는 485 인간 언어에 대한 코드가 있습니다. 언어 당 평균 700,000 개의 단어와 단어 당 10 바이트의 UTF-8이라는 평균 단어 길이를 가정 해 보겠습니다.
단순한 선형 목록으로 저장하기 만하면 지구상의 모든 언어로 된 모든 단어를 6GB 미만의 8 바이트 주파수 카운트와 함께 저장할 수 있습니다. 대신 Patricia trie와 같은 것을 사용한다면, 아마도 그 모든 언어에 대해 확신 할 수는 없지만 최소한 3 기가 바이트 이하로 축소 할 계획을 세울 수 있을 것입니다 .
이제 현실은 우리가 그곳의 여러 곳에서 숫자를 거의 과대 평가했다는 것입니다. 꽤 많은 언어가 상당한 수의 단어를 공유하고, 많은 (특히 오래된) 언어는 아마도 영어보다 단어가 적을 것입니다. 목록에서, 아마도 서면 양식이 전혀없는 일부가 포함 된 것 같습니다.
요약 : 거의 모든 합리적으로 새로운 데스크톱 / 서버에는지도를 완전히 RAM에 저장할 수있는 충분한 메모리가 있으며 더 많은 데이터가이를 변경하지 않습니다. 병렬로 연결된 디스크 하나 (또는 몇 개)의 경우 어쨌든 I / O 바운드가 될 것이므로 병렬 카운팅 (등)은 아마도 순 손실이 될 것입니다. 다른 최적화가 많은 것을 의미하기 전에 병렬로 수십 개의 디스크가 필요할 것입니다.
이 작업에 대해 맵 축소 방식을 시도 할 수 있습니다 . 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 요소가 포함되어 있는지 확인하는 것입니다. 완료되면 힙에 상위 K 요소가 포함됩니다.
더 확장 가능한 (머신이 적 으면 더 느리지 만) 대안은 map-reduce 정렬 기능을 사용하고 발생에 따라 데이터를 정렬하고 상위 K를 grep하는 것입니다.
이것에 대해 주목할 세 가지.
특히 : 파일이 메모리에 저장하기에 너무 크며, 단어 목록 (잠재적으로)이 메모리에 저장하기에 너무 크며, 32 비트 정수에 대해 너무 클 수 있습니다.
이러한주의 사항을 통과 한 후에는 간단해야합니다. 이 게임은 잠재적으로 큰 단어 목록을 관리하고 있습니다.
더 쉬운 경우 (머리가 회전하지 않도록).
"65K RAM과 1MB 파일이있는 Z-80 8 비트 시스템을 실행 중입니다 ..."
똑같은 문제.
요구 사항에 따라 다르지만 약간의 오류를 감당할 수 있다면 스트리밍 알고리즘 과 확률 데이터 구조 는 매우 시간과 공간 효율적이고 구현하기가 매우 간단하기 때문에 흥미로울 수 있습니다. 예를 들면 다음과 같습니다.
- 헤비 타자 (예 : 공간 절약), 상위 n 개의 가장 자주 사용되는 단어에만 관심이있는 경우
- 모든 단어에 대한 예상 카운트를 얻기위한 최소 카운트 스케치
이러한 데이터 구조에는 매우 적은 상수 공간 만 필요합니다 (정확한 양은 허용 할 수있는 오류에 따라 다름).
이러한 알고리즘에 대한 훌륭한 설명은 http://alex.smola.org/teaching/berkeley2012/streams.html 을 참조하십시오 .
DAWG ( wikipedia 및 자세한 내용이 포함 된 C # 작성) 를 사용하고 싶습니다 . 리프 노드에 카운트 필드를 추가하는 것은 간단하고 메모리가 효율적이며 조회에 매우 적합합니다.
편집 : 단순히 사용을 시도했지만 Dictionary<string, int>? 어디 <string, int> 단어 수를 나타냅니다? 너무 일찍 최적화하려고하십니까?
편집자 주 :이 게시물은 원래이 위키피디아 기사에 링크되었으며 , DAWG라는 용어의 또 다른 의미에 관한 것으로 보입니다. 효율적인 근사 문자열 일치를 위해 한 단어의 모든 하위 문자열을 저장하는 방법입니다.
다른 솔루션은 SQL 테이블을 사용 하여 시스템이 데이터를 최대한 잘 처리하도록 할 수 있습니다. 먼저 word컬렉션의 각 단어에 대해 단일 필드가있는 테이블을 만듭니다 .
그런 다음 쿼리를 사용하십시오 (구문 문제로 죄송합니다. SQL이 녹슬 었습니다-실제로는 의사 코드입니다).
SELECT DISTINCT word, COUNT(*) AS c FROM myTable GROUP BY word ORDER BY c DESC
일반적인 아이디어는 먼저 모든 단어가 포함 된 테이블 (디스크에 저장 됨)을 생성 한 다음 쿼리를 사용하여 계산하고 정렬 (word,occurances)하는 것입니다. 그런 다음 검색된 목록에서 상위 K를 가져올 수 있습니다.
모두에게 : SQL 문에 구문이나 기타 문제가있는 경우 : 자유롭게 편집하십시오.
첫째, 저는 최근에야 Trie 데이터 구조를 "발견"했으며 zeFrenchy의 답변은 제가 속도를 높이는 데 큰 도움이되었습니다.
댓글에서 여러 사람이 성능을 개선하는 방법에 대해 제안하는 것을 보았지만 이는 사소한 조정일 뿐이므로 실제 병목 현상 인 ConcurrentDictionary를 여러분과 공유 할 것이라고 생각했습니다.
저는 스레드 로컬 스토리지를 가지고 놀아보고 싶었고 귀하의 샘플은 저에게 그렇게 할 수있는 좋은 기회를주었습니다. 그리고 몇 가지 사소한 변경 후 스레드 당 사전을 사용하고 Join () 후 사전을 결합하면 성능이 ~ 30 % 향상되었습니다. (8 개의 스레드에서 20MB를 100 번 처리하는 작업은 내 상자에서 ~ 48 초에서 ~ 33 초로 단축되었습니다.)
코드는 아래에 붙여넣고 승인 된 답변에서 많이 변경되지 않았 음을 알 수 있습니다.
추신 : 평판 점수가 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
}
빠른 일반 알고리즘으로 나는 이것을 할 것입니다.
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
Well, personally, I'd split the file into different sizes of say 128mb, maintaining two in memory all the time while scannng, any discovered word is added to a Hash list, and List of List count, then I'd iterate the list of list at the end to find the top 10...
Well the 1st thought is to manage a dtabase in form of hashtable /Array or whatever to save each words occurence, but according to the data size i would rather:
- Get the 1st 10 found words where occurence >= 2
- Get how many times these words occure in the entire string and delete them while counting
- Start again, once you have two sets of 10 words each you get the most occured 10 words of both sets
- Do the same for the rest of the string(which dosnt contain these words anymore).
You can even try to be more effecient and start with 1st found 10 words where occurence >= 5 for example or more, if not found reduce this value until 10 words found. Throuh this you have a good chance to avoid using memory intensivly saving all words occurences which is a huge amount of data, and you can save scaning rounds (in a good case)
But in the worst case you may have more rounds than in a conventional algorithm.
By the way its a problem i would try to solve with a functional programing language rather than OOP.
The method below will only read your data once and can be tuned for memory sizes.
- Read the file in chunks of say 1GB
- For each chunk make a list of say the 5000 most occurring words with their frequency
- Merge the lists based on frequency (1000 lists with 5000 words each)
- Return the top 10 of the merged list
Theoretically you might miss words, althoug I think that chance is very very small.
Storm is the technogy to look at. It separates the role of data input (spouts ) from processors (bolts). The chapter 2 of the storm book solves your exact problem and describes the system architecture very well - http://www.amazon.com/Getting-Started-Storm-Jonathan-Leibiusky/dp/1449324010
Storm is more real time processing as opposed to batch processing with Hadoop. If your data is per existing then you can distribute loads to different spouts and spread them for processing to different bolts .
This algorithm also will enable support for data growing beyond terabytes as the date will be analysed as it arrives in real time.
Very interesting question. It relates more to logic analysis than coding. With the assumption of English language and valid sentences it comes easier.
You don't have to count all words, just the ones with a length less than or equal to the average word length of the given language (for English is 5.1). Therefore you will not have problems with memory.
As for reading the file you should choose a parallel mode, reading chunks (size of your choice) by manipulating file positions for white spaces. If you decide to read chunks of 1MB for example all chunks except the first one should be a bit wider (+22 bytes from left and +22 bytes from right where 22 represents the longest English word - if I'm right). For parallel processing you will need a concurrent dictionary or local collections that you will merge.
Keep in mind that normally you will end up with a top ten as part of a valid stop word list (this is probably another reverse approach which is also valid as long as the content of the file is ordinary).
Try to think of special data structure to approach this kind of problems. In this case special kind of tree like trie to store strings in specific way, very efficient. Or second way to build your own solution like counting words. I guess this TB of data would be in English then we do have around 600,000 words in general so it'll be possible to store only those words and counting which strings would be repeated + this solution will need regex to eliminate some special characters. First solution will be faster, I'm pretty sure.
http://en.wikipedia.org/wiki/Trie
여기 자바 http://algs4.cs.princeton.edu/52trie/TrieST.java.html 의 타이어 구현이 있습니다.
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));
}
}
'Nice programing' 카테고리의 다른 글
| JS : 자식 창이 닫힐 때 듣기 (0) | 2021.01.10 |
|---|---|
| XCode 4에서 특정 코드 줄로 이동하려면 어떻게합니까? (0) | 2021.01.10 |
| AWS EC2 Ubuntu Ubuntu 12.04.1 LTS : deb 명령을 찾을 수 없음 (0) | 2021.01.10 |
| 불씨 링크에 수업 추가 (0) | 2021.01.10 |
| Gnome 터미널의 배경 설정을 재정의하는 Vim 색 구성표 (0) | 2021.01.10 |