Алгоритм Python и tfidf, сделать это быстрее? - PullRequest
Новая
       3

Алгоритм Python и tfidf, сделать это быстрее?

5 голосов
/ 27 августа 2011

Я реализую алгоритм tf-idf в веб-приложении, использующем Python, однако он работает крайне медленно.Что я в основном делаю:

1) Создаю 2 словаря:

  • Первый словарь: ключ (идентификатор документа), значение (список всех найденных слов (включая повторные) в документе)
  • Второй словарь;ключ (идентификатор документа), значение (набор, содержащий уникальные слова документа)

Теперь есть запрос пользователя на получение результатов tfidf документа d.Что я делаю:

2) Зацикливание на уникальных словах второго словаря для документа d, и для каждого уникального слова w получим:

2.1) tf Score (сколько раз wпоявляется в d: зацикливание списка слов первого словаря документа)

2.2) оценка df (сколько документов содержит w: зацикливание набора слов всех документов (второй словарь) ипроверьте, содержится ли w).Я использую набор, так как кажется, что он быстрее проверяет, содержит ли набор слово по сравнению со списком.

Шаг 2.2 очень медленный.Например, имея 1000 документов, а для документа с 2313 уникальными словами, вывод результатов занимает около 5 минут.

Есть ли другой способ сделать шаг 2.2 быстрее?Являются ли словари медленными для повторения?

Ответы [ 2 ]

5 голосов
/ 27 августа 2011

Что ж, вы должны каким-то образом переосмыслить и перестроить способ хранения ваших данных или, другими словами, реализовать «ортодоксальную» версию вашего «инвертированного индекса».

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

Единственная структура, которая вам нужна - это вложенный словарь, подобный этому 

{ "term1" : { "DF" : x, "some_doc_id" : tf , "some_other_doc_id" : tf, etc  } ,
  "term2" : ...
  etc..
}

корректно обновляется каждый раз, когда вы «кормите» свой корпус.

И, конечно же, держите где-нибудь свой корпус ...

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

3 голосов
/ 27 августа 2011

Это академическая работа или вы делаете это для производства?Если вы внедряете для производства, почему бы не использовать что-то уже доступное (например, http://code.google.com/p/tfidf/)? С другой стороны, если вы делаете это как учебное упражнение, я мог бы все же взглянуть на существующую реализацию, чтобы увидетьчто они делают по-другому (если вообще что-то).

Я бы также предложил использовать cProfile для профилирования вашего кода, чтобы увидеть, где расходы.

...