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

Question

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

Спасибо

Answer 1

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

Answer 2

Если вы можете простить за каламбур, "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

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

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

Answer 3

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

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

Answer 4

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

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

Answer 5

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

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

Answer 6

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

Answer 7

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