Рассчитайте каждое вхождение слова в большом документе

Question

Мне было интересно, как я могу решить эту проблему с помощью какой структуры данных .. Кто-нибудь может объяснить это подробно ... !!Я думал использовать дерево.

Есть большой документ.Который содержит миллионы слов.Итак, как вы будете рассчитывать количество вхождений каждого слова оптимальным образом?

Этот вопрос был задан в Microsoft ... Любые предложения будут оценены .. !!

Answer 1

Я бы просто использовал хеш-карту (или словарь, поскольку это Microsoft;)) строк в целые числа. Для каждого слова ввода либо добавьте его в словарь, если оно новое, либо увеличьте его счет в противном случае. O (n) по длине входных данных, при условии, что реализация карты хеша приличная.

Answer 2

Использование словаря или набора хэшей приведет к o (n) в среднем .

Чтобы решить это за o (n) наихудший случай , a trie с небольшим изменением: добавьте счетчик для каждого представления слова в trie;Каждый раз, когда вставленное слово уже существует, увеличивайте его счетчик.

Если вы хотите напечатать все суммы в конце, вы можете сохранить счетчики в другом списке и ссылаться на него из дерева, вместо этого сохраняясчетчик в три.

Answer 3

Дерево не будет работать здесь.

Hashtable ht = new Hashtable();
// Read each word in the text in its order, for each of them:
if (ht.contains(oneWord))
{
    Integer I = (Integer) ht.get(oneWord));
    ht.put(oneWord, new Integer(I.intValue()+1));
}
else
{
     ht.put(oneWord, new Integer(1));
}

Answer 4

class IntValue
{
    public IntValue(int value)
    {
        Value = value;
    }
    public int Value;
}

static void Main(string[] args)
{
    //assuming document is a enumerator for the word in the document:

    Dictionary<string, IntValue> dict = new Dictionary<string, IntValue>();
    foreach (string word in document)
    {
        IntValue intValue;
        if(!dict.TryGetValue(word, out intValue))
        {
            intValue = new IntValue(0);
            dict.Add(word, intValue);
        }

        ++intValue.Value;
    }

    //now dict contains the counts
}