Подобие косинуса Векторов, с <O (n^2) сложность

Question

Подобие косинуса Векторов, с <O (n^2) сложность

Осмотрев этот сайт для подобных проблем, я нашел это: http://math.nist.gov/javanumerics/jama/ и это: http://sujitpal.blogspot.com/2008/09/ir-math-with-java-similarity-measures.html

Однако это кажется ими выполненными в O (n^2). Я делал некоторую кластеризацию документов и заметил, что этот уровень сложности не был выполним при контакте даже с маленькими наборами документа. Данный, для скалярного произведения, нам только нужны векторные условия, содержавшиеся в обоих векторах, должно быть возможно поместить векторы в дерево и таким образом вычислить скалярное произведение с n сложностью журнала n, где n является самым низким количеством уникальных условий в 1 из этих 2 документов.

Я пропускаю что-то? Существует ли библиотека Java, которая делает это?

спасибо

7

java algorithm information-retrieval

задан Ash 27 July 2010 в 18:07

2 ответа

Другие вопросы по тегам:

java algorithm information-retrieval

Похожие вопросы:

score 2 · Answer 1

Hashmap - это хорошо, но он может занять много памяти.

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

i = 0
j = 0
result = 0
while i < length(vec1) && j < length(vec2):
  if vec1[i].key == vec2[j].key:
    result = result + vec1[i].value * vec2[j].value
  else if vec1[i].key < vec2[j].key:
    i = i + 1
  else
    j = j + 1

score 2 · Answer 2

Если вы сохраняете векторные элементы в хэш-таблице, поиск в любом случае будет только log n, не так ли? Переберите все ключи в меньшем документе и посмотрите, существуют ли они в большем ..?