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

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

1) Создайте 2 словаря:

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

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

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

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

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

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

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


python dictionary tf-idf
person D T    schedule 27.08.2011    source источник
comment
Вы должны профилировать его, чтобы быть уверенным, где тратится время. Затем опубликуйте эту часть кода в виде небольшого автономного рабочего примера.   -  person Tom Zych    schedule 27.08.2011
comment
Мы не экстрасенсы; мы не можем сказать вам, что не так с кодом, пока вы его не опубликуете.   -  person Karl Knechtel    schedule 28.08.2011
comment
@ Том Спасибо, я уже знаю, что занимает больше всего времени.   -  person D T    schedule 28.08.2011
comment
@Karl Просто взглянув на мои структуры данных и обработав их, вы сможете понять, что я делаю, нет необходимости публиковать код.   -  person D T    schedule 28.08.2011

Ответы (2)


arrow_upward
5
arrow_downward

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

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

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

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

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

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

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

person hymloth    schedule 27.08.2011
comment
Спасибо за ваш ответ! Эта структура выглядит красиво, попробую! - person D T; 28.08.2011
comment
Это сработало! Я настроил сервер, который выполняет первичную обработку заполнения словарной структуры, которую вы мне сказали, а затем отвечает на запросы клиентов. Я могу получить результаты почти в реальном времени! Спасибо!!! - person D T; 28.08.2011

arrow_upward
3
arrow_downward

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

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

person Demian Brecht    schedule 27.08.2011
comment
Спасибо за ответ, я думаю, это можно рассматривать как академический проект. Я уже обнаружил, что наиболее трудоемкой частью является расчет df. - person D T; 28.08.2011