Поиск похожих шаблонов чисел в таблице

Первоначально идея Jawa была опубликована; вот моя попытка.

^ – функция 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 полем 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 членов, наиболее похожих на меня!

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

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

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

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

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

Подробнее о бинарной системе цифр.

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

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

 100 * (bit_length - similarity) / bit_length 

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

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

Один из способов сделать это – рассчитать расстояние Левенштейна между вашей поисковой строкой и полями 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%.

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

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

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

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

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

SELECT UserName, Abs (Ans1 – 1) + Abs (Ans2 – 2) + Abs (Ans3 – 1) + Abs (Ans4 – 2) как разница ORDER BY Difference ASC

Перечислит пользователей по сходству с ответами 1-2-1-2, при условии, что все вопросы будут взвешены равномерно.

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

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

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

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

Он работает, как ожидается.

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

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

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

Следуя приведенному примеру, когда мы конвертируем «1» s в бит, а «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 в скрипте – это количество ответов (бит_1 длина в формуле выше). Вы должны изменить его в соответствии с вашей ситуацией, независимо от того, сколько бит есть в используемом фактическом типе данных, поскольку BIT_COUNT не знает, сколько байтов вы используете.

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

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