Hashtables над большими наборами слов на естественном языке

Question

Я пишу программу на python для анализа обзоров фильмов в униграмме (и в конечном итоге в биграмме и т. Д.).Цель состоит в том, чтобы создать векторы функций для подачи в libsvm.У меня есть 50 000 нечетных уникальных слов в моем векторе функций (что мне кажется довольно большим, но я относительно уверен, что я прав в этом).

Я использую реализацию словаря Python в качестве хеш-таблицы для сохраненияотслеживать новые слова по мере их поступления, но я замечаю огромное замедление после обработки первых 1000 нечетных документов.Буду ли я иметь более высокую эффективность (учитывая распределение естественного языка), если я использую несколько меньших хэш-таблиц / словарей, или это будет то же самое / хуже?

Дополнительная информация:

Данные разбиты на1500 или около того документов, по 500 слов в каждом.В каждом документе содержится от 100 до 300 уникальных слов (относительно всех предыдущих документов).

Мой текущий код:

#processes each individual file, tok == filename, v == predefined class
def processtok(tok, v):
    #n is the number of unique words so far, 
    #reference is the mapping reference in case I want to add new data later
    #hash is the hashtable
    #statlist is the massive feature vector I'm trying to build
    global n
    global reference
    global hash
    global statlist
    cin=open(tok, 'r')
    statlist=[0]*43990
    statlist[0] = v
    lines = cin.readlines()
    for l in lines:
        line = l.split(" ")
        for word in line:
            if word in hash.keys():
                if statlist[hash[word]] == 0:
                    statlist[hash[word]] = 1
            else:
                hash[word]=n
                n+=1
                ref.write('['+str(word)+','+str(n)+']'+'\n')
                statlist[hash[word]] = 1
    cin.close()
    return statlist

Также имейте в виду, что мои входные данные составляют около 6 МБи мои выходные данные около 300 МБ.Я просто поражен тем, сколько времени это занимает, и я чувствую, что он не должен замедляться так резко, как работает.

Замедление: первые 50 документов занимают около 5 секунд, последние 50 занимаютоколо 5 минут.

Answer 1

@ ThatGuy сделал исправление, но на самом деле не сказал вам этого:

Основной причиной вашего замедления является линия

if word in hash.keys():

, который кропотливо составляет список всех ключей, а затем кропотливо ищет в этом списке слово. Требуемое время пропорционально количеству ключей, то есть количеству найденных уникальных слов. Вот почему он начинается быстро и становится все медленнее и медленнее.

Все, что вам нужно, это if word in hash:, что в 99,9999999% случаев занимает время, не зависящее от количества ключей - одна из основных причин, по которой вам нужно диктовать.

Не справиться и с statlist[hash[word]]. Кстати, фиксированный размер в statlist=[0]*43990 нуждается в объяснении.

Больше проблем

Проблема A: Либо (1) ваш код подвергся искажению отступов при публикации, либо (2) hash никогда не будет обновляться этой функцией. Проще говоря, если word нет в hash, т.е. когда вы впервые его видите, абсолютно ничего не происходит. Оператор hash[word] = n (ЕДИНСТВЕННЫЙ код, который обновляет hash) НЕ выполняется. Так что ни слова не будет в hash.

Похоже, этот блок кода нужно сместить влево на 4 столбца, чтобы он выровнялся по внешнему if:

else:
    hash[word]=n
    ref.write('['+str(word)+','+str(n)+']'+'\n')
    statlist[hash[word]] = 1

Проблема B: Нет кода для обновления n (предположительно, количество уникальных слов на данный момент).

Я настоятельно рекомендую вам принять столько предложений, которые мы с @ThatGuy сделали, сколько вы пожелаете, вырвать все вещи global, исправить свой код, добавить несколько выражений для печати в заметных точках, и запустите его, скажем, 2 документа в каждой из 3 строк, по 4 слова в каждой. Убедитесь, что он работает правильно. Затем запустите его на большом наборе данных (с подавленными отпечатками). В любом случае вы можете регулярно выводить статистику (например, количество документов, строк, слов, уникальных слов, истекшее время и т. Д.).

Другая проблема

Проблема C: Я упомянул об этом в комментарии к ответу @ ThatGuy, и он согласился со мной, но вы не упомянули, что подняли его:

>>> line = "foo bar foo\n"
>>> line.split(" ")
['foo', 'bar', 'foo\n']
>>> line.split()
['foo', 'bar', 'foo']
>>>

Использование вами .split ("") приведет к ложным "словам" и исказит вашу статистику, включая количество уникальных слов, которые у вас есть . Вы вполне можете найти необходимость изменить это жестко закодированное магическое число.

Я снова говорю: Нет кода, который обновляет n в функции . Выполнение hash[word] = n кажется очень странным, даже если n обновляется для каждого документа.

Answer 2

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

Вот мое предположение о том, что вы хотите:

def processtok(tok, v):
    global n
    global reference
    global hash
    cin=open(tok, 'rb')
    for l in cin:
        line = l.split(" ")
        for word in line:
            if word in hash:
                hash[word] += 1
            else:
                hash[word] = 1
                n += 1
                ref.write('['+str(word)+','+str(n)+']'+'\n')

    cin.close()
    return hash

Обратите внимание, что это означает, что вам больше не нужен символ "n", так как вы можете узнать это с помощью len (n).

Answer 3

Я не думаю, что словарь Python как-то связан с вашим замедлением. Особенно, когда вы говорите, что записей около 100. Я надеюсь, что вы имеете в виду Insertion и Retrival, которые оба O (1) в словаре. Проблема может заключаться в том, что вы не используете iterators (или загружаете ключ, пары значений по одному) при создании словаря и загружаете все слова в память. В этом случае замедление происходит из-за потребления памяти.