PHP / MySQL - найти элементы, которые имеют похожие или совпадающие свойства

Question

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

Порядок свойств также должен быть принят во внимание, поэтому свойства в начале более важны, чем свойства в конце.

Например:

Элемент 1 - A, B, C, D, E

Элемент 2 - A, B, C, D, E

будет соответствовать 100%

Элемент 1 - A, B, C, D, E

Элемент 2 - B, C, A, D, E

Это не будет идеальным совпадением, поскольку свойства находятся в другом порядке

поз. 1 - A, B, C, D, E

поз. 2 - F, G, H, I, A

Будет низким совпадением, так как только одно свойство одинаково и находится в позиции 5

Этот алгоритм будет работать для тысяч и тысяч записей, поэтому он должен быть высокопроизводительным и эффективным. Любые мысли о том, как я мог бы сделать это в PHP / MySQL быстро и эффективно?

Я рассматривал Левенштейн , но, насколько я могу судить, это также будет рассматривать расстояние между двумя совершенно разными словами с точки зрения правописания. Не кажется идеальным для этого сценария, если я просто неправильно его использую ..

Возможно, это может быть сделано исключительно в MySQL, возможно, с использованием полнотекстового поиска или чего-то еще.

Это похоже на хорошее решение , хотя и не предназначенное для этого сценария. Возможно, бинарное сравнение может быть использовано каким-то образом?

Answer 1

Я бы закодировал значение порядка и свойства в число.Числа имеют преимущество быстрых сравнений.

Это общая идея, и, возможно, все еще потребуется некоторая работа, но я надеюсь, что это поможет каким-то образом.

вычисление числа (некоторая форма хэша)для каждого свойства и умножьте число, представляющее порядок появления свойства для элемента.

скажем, у item1 есть 3 свойства A, B и C.

hash (A) = 123, hash(B) = 345, хэш (C) = 456

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

(hash (A) * 1000,00) + (hash (B) * 1,000) + (hash (C) * 1) = someval

величина множителя может быть изменена для отражения вашего набора данных.вам нужно будет определить хэш-функцию.может быть, soundex?

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

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

HTH.

edit: пример дляпроверка совпадений

с учетом item1 (abc) и item2 (abc).вычисленный хэш элементов будет равен.это лучший вариант развития событий.дальнейшие вычисления не требуются.

с учетом item1 (abc) и item2 (dea).вычисленный хэш элементов не равен.перейти к разбивке хэшей свойств ...

скажем, хеш-таблица для свойств a = 1, b = 2, c = 3, d = 4, e = 5 с 10 ^ n для множителя.вычисленный хеш для item1 равен 123, а item2 равен 451, разбейте вычисленный хеш для каждого свойства и сравните для всех комбинаций свойств по одному для каждого item1 (который становится item1 (1 2 3)) и item2 (который становится item2 (4 5 1))).затем вычислите балл.

другой способ посмотреть на это - сравнить свойства одно за другим, за исключением того, что на этот раз вы играете с числами вместо фактических строковых значений

Answer 2

Вы можете черпать вдохновение (или расплющивать алгоритмы) из различных выравниваний последовательностей алгоритмов, таких как Smith-Waterman .Действительно, то, что вы ищете, похоже, является описанием выравнивания последовательности.Я, однако, не уверен, возможно ли вообще сделать это как запрос SQL.