Как найти похожие результаты и отсортировать по сходству?

Ответ 1

Я выяснил, что расстояние Левенштейна может быть хорошим, когда вы ищете полную строку против другой полной строки, но когда вы ищете ключевые слова в строке, этот метод не возвращает (иногда) желаемых результатов. Кроме того, функция SOUNDEX не подходит для языков, отличных от английского, поэтому она весьма ограничена. Вы можете уйти с LIKE, но это действительно для базовых поисков. Вы можете захотеть взглянуть на другие методы поиска того, чего вы хотите достичь. Например:

Вы можете использовать Lucene в качестве базы поиска для своих проектов. Он реализован на большинстве основных языков программирования, и он будет довольно быстрым и универсальным. Этот метод, вероятно, лучший, поскольку он не только ищет подстроки, но и транспонирование, префиксы и суффиксы букв (все вместе). Тем не менее, вам нужно сохранить отдельный индекс (используя CRON для обновления его из независимого script один раз в то время работает).

Или, если вам нужно решение MySQL, полнотекстовая функциональность довольно хороша и, конечно, быстрее, чем хранимая процедура. Если ваши таблицы не являются MyISAM, вы можете создать временную таблицу, а затем выполнить полнотекстовый поиск:

CREATE TABLE IF NOT EXISTS `tests`.`data_table` (
  `id` int(10) unsigned NOT NULL AUTO_INCREMENT,
  `title` varchar(2000) CHARACTER SET latin1 NOT NULL,
  `description` text CHARACTER SET latin1 NOT NULL,
  PRIMARY KEY (`id`)
) ENGINE=InnoDB  DEFAULT CHARSET=utf8 COLLATE=utf8_bin AUTO_INCREMENT=1 ;

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

** ПРИМЕЧАНИЕ **: тип столбца должен быть latin1_bin, чтобы выполнить поиск с учетом регистра, а не регистр, нечувствительный к регистру latin1. Для строк unicode я бы рекомендовал utf8_bin для чувствительности к регистру и utf8_general_ci для поиска без учета регистра.

DROP TABLE IF EXISTS `tests`.`data_table_temp`;
CREATE TEMPORARY TABLE `tests`.`data_table_temp`
   SELECT * FROM `tests`.`data_table`;

ALTER TABLE `tests`.`data_table_temp`  ENGINE = MYISAM;

ALTER TABLE `tests`.`data_table_temp` ADD FULLTEXT `FTK_title_description` (
  `title` ,
  `description`
);

SELECT *,
       MATCH (`title`,`description`)
       AGAINST ('+so* +nullam lorem' IN BOOLEAN MODE) as `score`
  FROM `tests`.`data_table_temp`
 WHERE MATCH (`title`,`description`)
       AGAINST ('+so* +nullam lorem' IN BOOLEAN MODE)
 ORDER BY `score` DESC;

DROP TABLE `tests`.`data_table_temp`;

Подробнее об этом можно узнать на странице справочника API MySQL

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

** ОБНОВЛЕНИЕ **

Используя Lucene для поиска, вам просто нужно создать задание cron (все веб-хосты имеют эту "функцию" ), где это задание будет просто выполнять PHP script (ig "cd/path/to/script; php searchindexer.php" ), который обновит индексы. Причина в том, что индексирование тысяч "документов" (строк, данных и т.д.) Может занять несколько секунд, даже минут, но это необходимо для того, чтобы все поисковые запросы выполнялись как можно быстрее. Поэтому вам может потребоваться создать задание задержки, которое будет выполняться сервером. Это может быть на ночь, или в следующий час, это зависит от вас. PHP скрипт должен выглядеть примерно так:

$indexer = Zend_Search_Lucene::create('/path/to/lucene/data');

Zend_Search_Lucene_Analysis_Analyzer::setDefault(
  // change this option for your need
  new Zend_Search_Lucene_Analysis_Analyzer_Common_Utf8Num_CaseInsensitive()
);

$rowSet = getDataRowSet();  // perform your SQL query to fetch whatever you need to index
foreach ($rowSet as $row) {
   $doc = new Zend_Search_Lucene_Document();
   $doc->addField(Zend_Search_Lucene_Field::text('field1', $row->field1, 'utf-8'))
       ->addField(Zend_Search_Lucene_Field::text('field2', $row->field2, 'utf-8'))
       ->addField(Zend_Search_Lucene_Field::unIndexed('someValue', $someVariable))
       ->addField(Zend_Search_Lucene_Field::unIndexed('someObj', serialize($obj), 'utf-8'))
  ;
  $indexer->addDocument($doc);
}

// ... you can get as many $rowSet as you want and create as many documents
// as you wish... each document doesn't necessarily need the same fields...
// Lucene is pretty flexible on this

$indexer->optimize();  // do this every time you add more data to you indexer...
$indexer->commit();    // finalize the process

Затем это в основном, как вы ищите (основной поиск):

$index = Zend_Search_Lucene::open('/path/to/lucene/data');

// same search options
Zend_Search_Lucene_Analysis_Analyzer::setDefault(
   new Zend_Search_Lucene_Analysis_Analyzer_Common_Utf8Num_CaseInsensitive()
);

Zend_Search_Lucene_Search_QueryParser::setDefaultEncoding('utf-8');

$query = 'php +field1:foo';  // search for the word 'php' in any field,
                                 // +search for 'foo' in field 'field1'

$hits = $index->find($query);

$numHits = count($hits);
foreach ($hits as $hit) {
   $score = $hit->score;  // the hit weight
   $field1 = $hit->field1;
   // etc.
}

Вот отличные сайты о Lucene в Java, PHP и . Net.

В заключение у каждого метода поиска есть свои плюсы и минусы:

• Вы упомянули Sphinx search, и он выглядит очень хорошо, если вы можете сделать деамон на вашем веб-хосте.
• Zend Lucene требует задания cron для повторной индексации базы данных. Хотя это совершенно прозрачно для пользователя, это означает, что любые новые данные (или удаленные данные!) Не всегда синхронизируются с данными в вашей базе данных и поэтому не будут отображаться сразу при поиске пользователей.
• Поиск MySQL FULLTEXT хорош и быстр, но не даст вам всю мощь и гибкость первых двух.

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

Ответ 2

1. Сходство

Для Levenshtein в MySQL я нашел это, от www.codejanitor.com/wp/2007/02/10/levenshtein-distance-as-a-mysql-stored-function

SELECT 
    column, 
    LEVENSHTEIN(column, 'search_string') AS distance 
FROM table 
WHERE 
    LEVENSHTEIN(column, 'search_string') < distance_limit
ORDER BY distance DESC

2. Содержащий, нечувствительный к регистру

Используйте инструкцию LIKE MySQL, которая по умолчанию нечувствительна к регистру. % является подстановочным знаком, поэтому может быть любая строка до и после search_string.

SELECT 
    *
FROM 
    table
WHERE 
    column_name LIKE "%search_string%"

3. Содержащий, чувствительный к регистру

Руководство по MySQL помогает:

По умолчанию набор символов и сортировка - latin1 и latin1_swedish_ci, поэтому неважные сравнения строк по умолчанию нечувствительны к регистру. Это означает, что при поиске с col_name LIKE 'a%' вы получаете все значения столбцов, начинающиеся с A или a. Чтобы сделать этот регистр чувствительным, убедитесь, что один из операндов имеет чувствительную к регистру или двоичную сортировку. Например, если вы сравниваете столбец и строку, у которой есть набор символов latin1, вы можете использовать оператор COLLATE, чтобы заставить операнд иметь сортировку latin1_general_cs или latin1_bin...

Моя настройка MySQL не поддерживает latin1_general_cs или latin1_bin, но для меня было хорошо использовать сортировку utf8_bin, поскольку двоичный utf8 чувствителен к регистру:

SELECT 
    *
FROM 
    table
WHERE 
    column_name LIKE "%search_string%" COLLATE utf8_bin

2./3. отсортировано по Левенштейну Расстояние

SELECT 
    column, 
    LEVENSHTEIN(column, 'search_string') AS distance // for sorting
FROM table 
WHERE 
    column_name LIKE "%search_string%"
    COLLATE utf8_bin // for case sensitivity, just leave out for CI
ORDER BY
    distance
    DESC

Ответ 3

Кажется, что ваше определение сходства - это семантическое сходство. Поэтому, чтобы построить такую ​​функцию подобия, вы должны использовать семантические схожесть. Обратите внимание, что объем работы по этой проблеме может варьироваться от нескольких часов до нескольких лет, поэтому рекомендуется принять решение о объеме до начала работы. Я не выяснил, какие данные у вас есть, чтобы построить отношение подобия. Я предполагаю, что у вас есть доступ к набору данных документов и набору данных запросов. Вы можете начать с совпадения слов (например, условной вероятности). Вы быстро обнаружите, что получите список остановить слова, поскольку это связано с большинством слов просто потому, что они очень популярны, Использование лифта условной вероятности позаботится о словах остановки, но сделает отношение, подверженное ошибкам, небольшим числом (большинство ваших случаев). Вы можете попробовать Jacard, но поскольку он симметричен, будет много отношений, которые он не найдет. Тогда вы можете рассмотреть отношения, которые появляются только на небольшом расстоянии от базового слова. Вы можете (и должны) рассматривать базу отношений на общем корпусе (например, Википедию) и специфичные для пользователя (например, его электронные письма).

В скором времени у вас будет много мер сходства, когда все меры будут хорошими и будут иметь преимущество перед другими.

Чтобы объединить такие меры, я хотел бы свести проблему к проблеме классификации.

Вы должны создать набор данных paris слов и пометить их как "связанные". Чтобы создать большой помеченный набор данных, вы можете:

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

Затем используйте все меры, которые у вас есть как функции пар. Теперь вы находитесь в области контролируемой проблемы классификации. Создайте классификатор в наборе данных, оцененный в соответствии с вашими потребностями и получите меру подобия, которая соответствует вашим потребностям.