Нахождение похожих числовых моделей в таблице

Question

Хорошо, давайте предположим, что у нас есть таблица members. Есть поле, которое называется, скажем, about_member. Там будет строка, как эта 1-1-2-1-2 для всех. Давайте предположим, что member_1 имеет эту строку 1-1-2-2-1, и он ищет, у кого есть похожая строка или как можно больше похожих. Например, если member_2 имеет строку 1-1-2-2-1, это будет совпадение на 100%, но если member_3 имеет такую ​​строку 2-1-1-2-1, это будет совпадение на 60% И это должно быть упорядочено по процентам совпадений. Какой самый оптимальный способ сделать это с MYSQL и PHP? Очень сложно объяснить, что я имею в виду, но, может быть, вы поняли, если нет, спросите меня. Спасибо.

Редактировать: Пожалуйста, дайте мне идеи без метода Левенштейна. Этот ответ получит награду. Благодарю. (награда будет объявлена, когда я смогу это сделать)

Answer 1

преобразует ваши числовые последовательности в битовые маски и использует BIT_COUNT (поиск по столбцу) в качестве функции подобия, в диапазоне от 0 (= 100% совпадение, строки равны) до [длина бита] (= 0%, строки совершенно разные).Чтобы преобразовать эту функцию подобия в процентное значение, используйте

100 * (bit_length - similarity) / bit_length

Например, «1-1-2-2-1» становится «00110» (при условии, что у вас только два состояния), 2-1-1-2-1 равно "10010", bit_count (00110 ^ 10010) = 2, длина бита = 5 и 100 * (5 - 2) / 5 = 60%.

Answer 2

Джава опубликовал эту идею изначально;вот моя попытка.

^ - это функция XOR.Он сравнивает 2 двоичных числа побитно и возвращает 0, если оба бита одинаковы, и 1 в противном случае.

    0 1 0 0 0 1 0 1 0 1 1 1  (number 1)
 ^  0 1 1 1 0 1 0 1 1 0 1 1  (number 2)
 =  0 0 1 1 0 0 0 0 1 1 0 0  (result)

Как это относится к вашей проблеме:

  // In binary...
  1111 ^ 0111 = 1000 // (1 bit out of 4 didn't match: 75% match)
  1111 ^ 0000 = 1111 // (4 bits out of 4 didn't match: 0% match)

  // The same examples, except now in decimal...
    15 ^    7 = 8  (1000 in binary) // (1 bit out of 4 didn't match: 75% match)
    15 ^    0 = 15 (1111 in binary) // (4 bits out of 4 didn't match: 0% match)

Какмы можем сосчитать эти биты в MySQL:

BIT_COUNT(b'0111') = 3 // Bit count of binary '0111'
BIT_COUNT(7) = 3       // Bit count of decimal 7 (= 0111 in binary)
BIT_COUNT(b'1111' ^ b'0111') = 1 // (1 bit out of 4 didn't match: 75% match)

Таким образом, чтобы получить сходство ...

// First we focus on calculating mismatch.
(BIT_COUNT(b'1111' ^ b'0111') / YOUR_TOTAL_BITS) = 0.25 (25% mismatch)
(BIT_COUNT(b'1111' ^ b'1111') / YOUR_TOTAL_BITS) = 0 (0% mismatch; 100% match)

// Now, getting the proportion of matched bits is easy
1 - (BIT_COUNT(b'1111' ^ b'0111') / YOUR_TOTAL_BITS) = 0.75 (75% match)
1 - (BIT_COUNT(b'1111' ^ b'1111') / YOUR_TOTAL_BITS) = 1.00 (100% match)

Если бы мы могли просто сделать ваше поле about_memberхранить данные в виде битов (и быть представлены целым числом), мы могли бы сделать все это легко!Вместо 1-2-1-1-1 используйте 0-1-0-0-0, но без тире.

Вот как PHP может помочь нам:

bindec('01000') == 8;
bindec('00001') == 1;
decbin(8) == '01000';
decbin(1) == '00001';

И, наконец, вот реализация:

// Setting a member's about_member property...
$about_member = '01100101';
$about_member_int = bindec($about_member);
$query = "INSERT INTO members (name,about_member) VALUES ($name,$about_member_int)";

// Getting matches...
$total_bits = 8; // The maximum length the member_about field can be (8 in this example)
$my_member_about = '00101100';
$my_member_about_int = bindec($my_member_about_int);
$query = "
    SELECT 
        *,
        (1 - (BIT_COUNT(member_about ^ $my_member_about_int) / $total_bits)) match 
    FROM members
    ORDER BY match DESC
    LIMIT 10";

Этот последний запрос выберет 10 членов, наиболее похожих на меня!

Теперь, если говорить кратко, с точки зрения непрофессионала,

Мы используем двоичный файл, потому что онделает вещи проще;двоичное число похоже на длинную линию выключателей света.Мы хотим сохранить нашу «конфигурацию выключателя света», а также найти членов, которые имеют наиболее похожие конфигурации.

Оператор ^, учитывая две конфигурации выключателя света, делает для нас сравнение.Результатом снова является серия переключателей;переключатель будет ON, если 2 исходных переключателя находились в разных положениях, и OFF, если они были в одинаковом положении.

BIT_COUNT говорит нам, сколько переключателей ON - даваянам подсчитать, сколько переключателей были разные.YOUR_TOTAL_BITS - это общее количество переключателей.

Но двоичные числа - это просто числа ... и поэтому строка из 1 и 0 на самом деле просто представляет число, подобное 133 или 94. Но это намного сложнееВизуализируйте нашу «конфигурацию выключателя света», если мы используем десятичные числа.Вот где появляются PHP decbin и bindec.

Узнайте больше о двоичной системе счисления.

Надеюсь, это поможет!

Answer 3

Очевидное решение - посмотреть на расстояние Левенштейна (в mysql нет встроенной реализации, но есть и другие доступные реализации, например, эта в pl / sql и некоторых расширениях), как обычно, как обычно. правильный способ решить эту проблему - правильно нормализовать данные.

Answer 4

Один из способов сделать это - вычислить расстояние Левенштейна между строкой поиска и полями about_member для каждого участника. Вот реализация функции как хранимой функции MySQL.

С этим вы можете сделать:

SELECT name, LEVENSHTEIN(about_member, '1-1-2-1-2') AS diff 
FROM members 
ORDER BY diff ASC

% сходства относится к diff;если diff=0, то это 100%, если diff это размер строки (минус количество тире), это 0%.

Answer 5

Прочитав пояснительные комментарии к исходному вопросу, расстояние Левенштейна - не тот ответ, который вы ищете .

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

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

Поместите каждый ответ в отдельный столбец (Ans1, Ans2, Ans3, Ans4, ....)

Предположим, вы ищете сходства с 1-2-1-2.

ВЫБЕРИТЕ имя пользователя, Abs (Ans1 - 1) + Abs (Ans2 - 2) + Abs (Ans3 - 1) + Abs (Ans4 - 2) в качестве разницы.пользователи по схожести с ответами 1-2-1-2, предполагая, что все вопросы взвешены равномерно.

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

Если вопросы всегда будут «да / нет», а количество ответов достаточно мало, чтобы все ответы можно было объединить в одно целое число, и все ответы были одинаково взвешены, тогда вы можете закодировать все ответы в одном столбце ииспользуйте BIT_COUNT как предложено.Это было бы более быстрой и более компактной реализацией.

Answer 6

Я бы пошел со встроенным similar_text() PHP.Кажется, это именно то, что вы хотите:

$percent = 0;
similar_text($string1, $string2, $percent);

echo $percent;

Работает, как и ожидал вопрос.

Answer 7

Если у вас не слишком много полей, вы можете создать индекс для целочисленного представления about_member.Затем вы можете найти 100% по точному совпадению в поле about_member, за которым следуют 80% совпадений при изменении 1 бита, 60% совпадений при изменении 2 битов и так далее.

Answer 8

Если вы представляете свои шаблоны ответов в виде битовых последовательностей, вы можете использовать формулу (100 * (bit_length - similarity) / bit_length).

Следуя приведенному выше примеру, когда мы конвертируем «1» в бит и «2» вбит в "1-1-2-2-1" становится 6 (как base-10, 00110 в двоичном виде), а "2-1-1-2-1" становится 18 (10010b) и т. д.

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

Вот пример сценария для запускапротив MySQL.

DROP TABLE IF EXISTS `test`;

CREATE TABLE `members` (
    `id` VARCHAR(16) NOT NULL ,
    `about_member` INT NOT NULL
) ENGINE = InnoDB;

INSERT INTO `members`
    (`id`, `about_member`)
VALUES
    ('member_1', '6'),
    ('member_2', '18');

SELECT 100 * ( 5 - BIT_COUNT( about_member ^ (
    SELECT about_member
    FROM members
    WHERE id = 'member_1' ) ) ) / 5
FROM members;

Волшебные 5 в скрипте - это количество ответов (длина_бита в приведенной выше формуле).Вы должны изменить его в соответствии с вашей ситуацией, независимо от того, сколько битов имеется в фактическом используемом типе данных, так как BIT_COUNT не знает, сколько байтов вы используете.

BIT_COUNT возвращает количество установленных битов иобъясняется в руководстве по MySQL .^ - это двоичный оператор XOR в MySQL.

Здесь сравнение ответов member_1 сравнивается с ответами всех, включая их собственные, что приводит к 100% соответствию, естественно.

Answer 9

Я бы выбрал подход Левенштейна , вы можете использовать его в MySQL или PHP .