проблема распределения слов

Question

У меня есть большой файл слов ~ 100 Гб и ограниченная память 4 ГБ. Мне нужно рассчитать распределение слов из этого файла. Теперь один из вариантов состоит в том, чтобы разделить его на куски и отсортировать каждый кусок, а затем слить для вычисления распределения слов. Есть ли другой способ, которым это можно сделать быстрее? Одна идея состоит в том, чтобы пробовать, но не уверен, как реализовать его, чтобы вернуться к правильному решению.

Thanks

Answer 1

Вы можете построить структуру Trie, где каждый лист (и некоторые узлы) будет содержать текущий счетчик. Поскольку слова будут пересекаться друг с другом, 4 ГБ должно быть достаточным для обработки 100 ГБ данных.

Answer 2

Знаете ли вы, сколько слов у вас есть? если не много (т. е. сто тысяч), то вы можете передавать входные данные, определять слова и использовать хеш-таблицу для хранения счетчиков. после ввода выполняется просто пересечение результата.

Answer 3

Просто используйте файл DBM. Это хэш на диске. Если вы используете более свежие версии, вы можете использовать дерево B +, чтобы получить обход в порядке.

Answer 4

Наивно я бы просто создал хэш-таблицу, пока не достигнет определенного предела в памяти, а затем отсортировать ее в памяти и записать это. Наконец, вы можете выполнить n-way слияние каждого фрагмента. В лучшем случае у вас будет 100/4 кусков или около того, но, вероятно, намного меньше, если некоторые слова более распространены, чем другие (и как они группируются).

Другой вариант - использовать trie, который был построен для такого рода вещей. Каждый символ в строке становится ветвью в 256-way tree, а на листе у вас есть счетчик. Посмотрите структуру данных в Интернете.

Answer 5

Если вы простите за каламбур, «TRIE» это:

public class Trie : Dictionary<char, Trie> 
{ 
    public int Frequency { get; set; } 

    public void Add(string word) 
    { 
     this.Add(word.ToCharArray()); 
    } 

    private void Add(char[] chars) 
    { 
     if (chars == null || chars.Length == 0) 
     { 
      throw new System.ArgumentException(); 
     } 

     var first = chars[0]; 
     if (!this.ContainsKey(first)) 
     { 
      this.Add(first, new Trie()); 
     } 

     if (chars.Length == 1) 
     { 
      this[first].Frequency += 1; 
     } 
     else 
     { 
      this[first].Add(chars.Skip(1).ToArray()); 
     } 
    } 

    public int GetFrequency(string word) 
    { 
     return this.GetFrequency(word.ToCharArray()); 
    } 

    private int GetFrequency(char[] chars) 
    { 
     if (chars == null || chars.Length == 0) 
     { 
      throw new System.ArgumentException(); 
     } 

     var first = chars[0]; 
     if (!this.ContainsKey(first)) 
     { 
      return 0; 
     } 

     if (chars.Length == 1) 
     { 
      return this[first].Frequency; 
     } 
     else 
     { 
      return this[first].GetFrequency(chars.Skip(1).ToArray()); 
     } 
    } 
} 

Тогда вы можете позвонить код, как это:

var t = new Trie(); 

t.Add("Apple"); 
t.Add("Banana"); 
t.Add("Cherry"); 
t.Add("Banana"); 

var a = t.GetFrequency("Apple"); // == 1 
var b = t.GetFrequency("Banana"); // == 2 
var c = t.GetFrequency("Cherry"); // == 1 

Вы должны иметь возможность добавить код для обхода синтаксического дерева и возвращают плоский список слов и их частоты.

Если вы обнаружите, что это слишком сильно портит ваш предел памяти, я могу предложить вам «разделить и победить». Возможно, сканировать исходные данные для всех первых символов, а затем запускать trie отдельно по каждому, а затем объединять результаты после всех прогонов.

Answer 6

Почему бы не использовать реляционную БД? Процедура будет столь же просто, как:

1. Создать таблицу с word и count.
2. Создать индекс на word. В некоторых базах данных есть индекс слова (т. Е. Прогресс).
3. Do SELECT на этой таблице со словом.
4. Если слово существует, увеличьте счетчик.
5. В противном случае - добавьте его в таблицу.

Answer 7

Если вы используете python, вы можете проверить встроенную функцию iter. Он будет читать строки за строкой из вашего файла и не вызовет проблем с памятью. Вы не должны «возвращать» значение, а «уронить» его. Вот пример, который я использовал для чтения файла и получения векторных значений.

def __iter__(self): 
    for line in open(self.temp_file_name): 
     yield self.dictionary.doc2bow(line.lower().split())