Como encontrar resultados semelhantes e classificar por semelhança?

Descobri que a distância Levenshtein pode ser boa quando você está pesquisando uma string completa em outra string completa, mas quando você está procurando palavras-chave dentro de uma string, esse método não retorna (às vezes) os resultados desejados. Além disso, a função SOUNDEX não é adequada para outros idiomas além do inglês, por isso é bastante limitada. Você pode se safar com o LIKE, mas é realmente para pesquisas básicas. Você pode querer pesquisar outros métodos de pesquisa para o que deseja alcançar. Por exemplo:

Você pode usar Lucene como base de pesquisa para seus projetos. É implementado na maioria das principais linguagens de programação e é bastante rápido e versátil. Este método é provavelmente o melhor, pois não apenas procura substrings, mas também transposição de letras, prefixos e sufixos (todos combinados). No entanto, você precisa manter um índice separado (usar CRON para atualizá-lo de um script independente de vez em quando funciona).

Ou, se você quiser uma solução MySQL, a funcionalidade de texto completo é muito boa e certamente mais rápida que um procedimento armazenado. Se suas tabelas não são MyISAM, você pode criar uma tabela temporária e realizar sua pesquisa de texto completo:

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 ;

Use um gerador de dados para gerar alguns dados aleatórios se você não quiser se incomodar em criá-los você mesmo...

** OBSERVAÇÃO ** :o tipo de coluna deve ser latin1_bin para realizar uma pesquisa com distinção entre maiúsculas e minúsculas em vez de não diferenciar maiúsculas de minúsculas com latin1 . Para strings unicode, eu recomendaria utf8_bin para maiúsculas e minúsculas e utf8_general_ci para pesquisas que não diferenciam maiúsculas de minúsculas.

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`;

Leia mais sobre isso na página de referência da API MySQL

A desvantagem disso é que ele não procurará a transposição de letras ou palavras "semelhantes, soa como".

** ATUALIZAÇÃO **

Usando o Lucene para sua pesquisa, você simplesmente precisará criar um cron job (todos os hosts da web têm esse "recurso") onde este trabalho simplesmente executará um script PHP (por exemplo, "cd /path/to/script; php searchindexer.php" ) que atualizará os índices. A razão é que a indexação de milhares de "documentos" (linhas, dados, etc.) pode levar vários segundos, até minutos, mas isso é para garantir que todas as pesquisas sejam realizadas o mais rápido possível. Portanto, convém criar um trabalho de atraso para ser executado pelo servidor. Pode ser durante a noite, ou na próxima hora, isso é com você. O script PHP deve ser algo assim:

$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

Então, é basicamente assim que você pesquisa (pesquisa básica):

$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.
}

Aqui estão ótimos sites sobre o Lucene em Java , PHP e .Net .

Em conclusão cada método de pesquisa tem seus próprios prós e contras:

Você mencionou Pesquisa Sphinx e parece muito bom, desde que você possa fazer o deamon rodar em seu host.
Zend Lucene requer um cron job para reindexar o banco de dados. Embora seja bastante transparente para o usuário, isso significa que quaisquer novos dados (ou dados excluídos!) nem sempre estão sincronizados com os dados em seu banco de dados e, portanto, não serão exibidos imediatamente na pesquisa do usuário.
A pesquisa do MySQL FULLTEXT é boa e rápida, mas não oferece todo o poder e flexibilidade das duas primeiras.

Por favor, sinta-se à vontade para comentar se eu esqueci/perdi alguma coisa.