Ускорьте сравнение текста (векторов объектов) с пространственными функциями MySQL - PullRequest
Новая
       36

Ускорьте сравнение текста (векторов объектов) с пространственными функциями MySQL

1 голос
/ 22 сентября 2009

У меня есть функция, которая берет два массива, содержащих токены / слова двух текстов, и выдает значение сходства косинусов, которое показывает связь между обоими текстами.

Функция принимает массив $ tokensA (0 => дом, 1 => велосипед, 2 => человек) и массив $ tokensB (0 => велосипед, 1 => дом, 2 => автомобиль) и вычисляет сходство, которое возвращается как значение с плавающей запятой. 

function cosineSimilarity($tokensA, $tokensB) {
    $a = $b = $c = 0;
    $uniqueTokensA = $uniqueTokensB = array();
    $uniqueMergedTokens = array_unique(array_merge($tokensA, $tokensB));
    foreach ($tokensA as $token) $uniqueTokensA[$token] = 0;
    foreach ($tokensB as $token) $uniqueTokensB[$token] = 0;
    foreach ($uniqueMergedTokens as $token) {
        $x = isset($uniqueTokensA[$token]) ? 1 : 0;
        $y = isset($uniqueTokensB[$token]) ? 1 : 0;
        $a += $x * $y;
        $b += $x;
        $c += $y;
    }
    return $b * $c != 0 ? $a / sqrt($b * $c) : 0;
}

Если я хочу сравнить 75 текстов друг с другом, мне нужно сделать 5625 отдельных сравнений, чтобы все тексты сравнивались друг с другом.

Можно ли использовать пространственные столбцы MySQL для уменьшения количества сравнений?

Я не хочу говорить о своей функции или о способах сравнения текстов. Просто о сокращении количества сравнений.

Пространственные столбцы MySQL

  • Вы создаете пространственные столбцы с помощью: CREATE TABLE abc (clmnName TYPE)
  • возможные типы перечислены здесь
  • здесь - как я выбираю данные позже [например, MultiPointFromText () или AsText ()]
  • Вы вставляете значения следующим образом: INSERT INTO clmnName VALUES (GeomFromText ('POINT (1 1)')) *

Но как вы используете это для моей проблемы?

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

Ответы [ 2 ]

1 голос
/ 22 сентября 2009

Хотя R-Trees в целом может индексировать данные с произвольным числом измерений, MySQL пространственные возможности ограничены только типами Geometry (2 измерения).

Если ваши векторы 2 -мерны и , вы можете их нормализовать, затем выполните следующее:

  • Разделите круг на двойное число углов, соответствующее вашим разностям
  • Найти MBR векторов с заданной разницей косинусов от центра каждого сектора
  • Найти все векторы в MBR
  • Делайте точную фильтрацию для точной разницы.

В этом случае, однако, будет лучше просто предварительно рассчитать угол значения и индексировать его простым B-Tree индексом.

1 голос
/ 22 сентября 2009

На самом деле у вас есть только 75 * 74/2 = 2775 сравнений. Вы сравниваете каждое слово с 74 другими, но вам не нужно сравнивать слово1 со словом2 и снова слово2 со словом1. Таким образом, это дает половину сравнений меньше .

...