Calendário do advento symfony dia vinte e um: Motor de Busca

Anteriormente no symfony

Com integração AJAX, web services, feed RSS, um leque completo de funcionalidade de gerenciamento, e um número de usuários crescente, askeet tem quase tudo que uma aplicação web 2.0 precisa ter. A comunidade symfony debateu sobre o que poderia ser adicionado, a fim fazer o askeet uma aplicação matadora.

Algumas das sugestões incluíram as características que foram planeadas inicialmente. Outros concerniram pequenas adições, e que serão adicionadas provavelmente logo depois da liberação 1.0. Askeet almejou ser uma aplicação viva e de código fonte aberto, e você pode abrir tickets ou propor evoluções no sistema trac do askeet. E você pode contribuir com correções(patches) e adaptações ou estender a aplicação como desejar. Mas por favor espere alguns dias, para que o askeet tenha mais alguma surpresas para você antes do natal.

Como construir um motor de busca?

A sugestão mais popular para o dia 21 foi o motor de busca.

Se a extensão Zserach (uma implementação em PHP da Lucene search engine para o Apache) já havia sido liberado pela Zend, esta seria uma parte do bolo para ser implementado. Infelizmente, a Zend parece examinar demais ao invés de lançar o seu framework PHP, então nos precisamos encontrar outra solução.

Integrando uma biblioteca estrangeira (como por exemplo, mnoGoSearch) provavelmente teríamos mais de uma hora, e varias adaptações seriam necessárias para obter um bom resultado para o conteúdo especifico do askeet. A bibliotecas estrangeiras de busca Plus, é frequentemente dependente da plataforma da base de dados, e não são código fonte aberto, e isto é algo que nós não queremos para o askeet.

O database MYSQL oferece uma indexação de completa de texto e busca para conteúdo de texto, mas é restrito a tabelas MyISAM. Novamente, baseado nosso motor de busca em um componente especifico de um database limita as possibilidades de uso da aplicação do askeet, e no queremos fazer tudo para preservar a larga compatibilidade.

A única alternativa que nos resta é desenvolver uma busca por texto completo por nos mesmos. E nos temos menos de uma hora, então vamos começar.

Índice de palavras

O primeiro passo para construir um índice de busca. O índice pode ser como um índice de tabela, indexando todas as ocorrências de uma palavra em particular. Por exemplo, se a questão #34 tem as seguintes características:

Título: Qual é o melhor signo Zodíaco para meu filho? Corpo: Meu esposo não se importa com o signo zodíaco para nosso próximo filho, mas nós já temos uma menina de câncer e um menino de aries, and they get along with each other like hell. Minha sogra não expressou nenhuma preferência, então eu estou completamente livre para escolher o signo zodíaco do nosso próximo bebe. O que você acha? * Tags: zodíaco, vida real, família, criança, signo, astrologia, signos

Um índice deve ser criado para listar as palavras da questão, para então o motor de busca encontra-lo.

Tabela de índice

O índice se parece com:

id | word | count ----|-----------|------ 34 | signo | 4 34 | zodíaco | 4 34 | criança | 2 34 | hell | 1 34 | ... | ...

Um nova tabela SearchIndex é adicionada ao schema.xml do askeet antes de reconstruir o modelo: 

[xml]
<table name="ask_search_index" phpName="SearchIndex">
  <column name="question_id" type="integer" />
  <foreign-key foreignTable="ask_question" onDelete="cascade">
    <reference local="question_id" foreign="id"/>
  </foreign-key>
  <column name="word" type="varchar" size="255" />
  <index name="word_index">
    <index-column name="word" />
  </index>
  <column name="weight" type="integer" />
</table>

O atributo onDelete assegura-se que quando uma deleção de uma questão é feita, todos os registro da tabela SearchIndex relacionados a questão também serão, como explanado ontem

Separando frases em palavras

O índice da entrada que será usado para construir o índice é um jogo das sentenças (questões, títulos e corpo). O que é necessitado eventualmente é uma lista das palavras. Isto significa que nós precisamos separar as sentenças em palavras, ignorando toda pontuação, números, e colocando todas as palavras em caixa baixa. A função PHP str_word_count() fará o truque: 

[php]
// split into words
$words = str_word_count(strtolower($phrase), 1);
...

Stop words

Algumas palavras, como "a," "of," "the," "I,", "it", "you," e "and" ("um/uma," "de," "o," "Eu,", "ele", "você," e "e"), serão ignoradas quando indexarmos algum conteúdo de texto. Isto é porque elas não valor distintivo, aparecem em quase todo índice do texto, retardam uma busca e fazem-na retornam muitos resultados ruins, que não têm nada da pergunta do usuário. São conhecidas como stop words. As stop words são especificas a uma dada linguagem.

Para o motor de busca do symfony, vamos usar uma lista customizada de stop words. Adicione o seguinte método a classe askeet/lib/myTools.class.php: 

[php]
public static function removeStopWordsFromArray($words)
{
  $stop_words = array(
    'i', 'me', 'my', 'myself', 'we', 'our', 'ours', 'ourselves', 'you', 'your', 'yours', 
    'yourself', 'yourselves', 'he', 'him', 'his', 'himself', 'she', 'her', 'hers', 
    'herself', 'it', 'its', 'itself', 'they', 'them', 'their', 'theirs', 'themselves', 
    'what', 'which', 'who', 'whom', 'this', 'that', 'these', 'those', 'am', 'is', 'are', 
    'was', 'were', 'be', 'been', 'being', 'have', 'has', 'had', 'having', 'do', 'does', 
    'did', 'doing', 'a', 'an', 'the', 'and', 'but', 'if', 'or', 'because', 'as', 'until', 
    'while', 'of', 'at', 'by', 'for', 'with', 'about', 'against', 'between', 'into', 
    'through', 'during', 'before', 'after', 'above', 'below', 'to', 'from', 'up', 'down', 
    'in', 'out', 'on', 'off', 'over', 'under', 'again', 'further', 'then', 'once', 'here', 
    'there', 'when', 'where', 'why', 'how', 'all', 'any', 'both', 'each', 'few', 'more', 
    'most', 'other', 'some', 'such', 'no', 'nor', 'not', 'only', 'own', 'same', 'so', 
    'than', 'too', 'very',
  );


return array_diff($words, $stop_words); }

Stemming

A primeira coisa que você deve observar na pergunta do exemplo dado acima é que as palavras que têm o mesmo radical devem ser vistas como únicas. Crianças deve aumentar o peso de criança, como signo deve aumentar signos. Então antes de indexar as palavras, temos que reduzir ao seu divisor maior, isto em vocabulários lingüísticos é chamado de stem, ou "a base da palavra incluindo afixos derivacional mas morfemas não inflexional, isto é a parte da palavra que remanesce não mudada com a inflexão".

Existem algumas regras para transformar uma palavra em seu radical, e estas regras são todas dependentes da linguagem. Uma da melhores técnicas de stemming para o Inglês é chamada the Porter Stemming Algorithm e, nos somos muito 'sortudos', ele foi portado para o PHP5 e é de código aberto e está niponizável em tartarus.org.

A classe PorterStemmer prove um método ::stem($word), isto é perfeito para nossa necessidade. Então vamos escrever um método estático em myTools.class.php, isto direciona a frase em um array ao 'stem words': 

  [php]
  public static function stemPhrase($phrase)
  {
    // split into words
    $words = str_word_count(strtolower($phrase), 1);

    // ignore stop words
    $words = myTools::removeStopWordsFromArray($words);

    // stem words
    $stemmed_words = array();
    foreach ($words as $word)
    {
      // ignore 1 and 2 letter words
      if (strlen($word) <= 2)
      {
        continue;
      }

      $stemmed_words[] = PorterStemmer::stem($word, true);
    }

    return $stemmed_words;
  }

Claro que você precisa colocar o PorterStemmer.class.php dentro de algum diretório em askeet/lib/ para que funcione.

Recuperando o pesa das palavras

O resultado da pesquisa deve aparecer de acordo com a relevância As questões mais relacionadas com a palavra digitada pelo usuário devem aparecer primeiro. Mas como traduziremos esta ideia de relevância no algoritmo? Vamos escrever alguns princípios básicos:

*Se a palavra procurada aparecer no título da questão, esta questão aparecer acima no resultado do em detrimento de uma em que a palavra só aparece no corpo.

  • Se a palavra pesquisada aparece duas vezes no conteúdo da questão, o resultado da busca deve mostrar esta pergunta antes de outra onde a palavra aparece somente uma vez.

Isso é porque nós necessitamos dar o peso às palavras de acordo com a parte da pergunta em que ela vêm. Como os fatores do peso têm que ser facilmente acessíveis, para fazê-los variar se quisermos para ajuste fino de nosso algoritmo do motor de busca, o colocaremos em um arquivo de configuração (askeet/apps/frontend/config/app.yml): 

all:
  ...

  search:
    body_weight:         1
    title_weight:        2
    tag_weight:          3

A fim aplicar o peso a uma palavra, nós repetimos simplesmente o índice de uma string tantas vezes o fator do peso de sua origem: 

[php]
...
// question body
$raw_text =  str_repeat(' '.strip_tags($question->getHtmlBody()), sfConfig::get('app_search_body_weight'));

// question title
$raw_text .= str_repeat(' '.$question->getTitle(), sfConfig::get('app_search_title_weight'));
...

O peso básico das palavras será dado por seu número de ocorrências no texto. A função PHP `array_count_values() nos ajudará nisto: 

[php]
...
// phrase stemming
$stemmed_words = myTools::stemPhrase($raw_text);

// unique words with weight
$words = array_count_values($stemmed_words);

Atualizando o índice

O índice deve ser atualizado quando uma questão, tag ou pergunta é adicionado. A arquitetura MVC torna isto fácil de ser feito, e você já viu como sobrescrever o método save() em uma classe de modelo com a transação, por exemplo durante o dia quatro. Então o que é mostrado a seguir não é surpresa para você. Abra o arquivo askeet/lib/model/Question.php e adicione: 

[php]
public function save($con = null)
{
  $con = sfContext::getInstance()->getDatabaseConnection('propel');
  try
  {
    $con->begin();


$ret = parent::save($con); $this->updateSearchIndex();
$con->commit();
return $ret; } catch (Exception $e) { $con->rollback(); throw $e; } }
public function updateSearchIndex() { // delete existing SearchIndex entries about the current question $c = new Criteria(); $c->add(SearchIndexPeer::QUESTION_ID, $this->getId()); SearchIndexPeer::doDelete($c);
// create a new entry for each of the words of the question foreach ($this->getWords() as $word => $weight) { $index = new SearchIndex(); $index->setQuestionId($this->getId()); $index->setWord($word); $index->setWeight($weight); $index->save(); } } 

public function getWords()
{
  // body
  $raw_text =  str_repeat(' '.strip_tags($this->getHtmlBody()), sfConfig::get('app_search_body_weight'));


// title $raw_text .= str_repeat(' '.$this->getTitle(), sfConfig::get('app_search_title_weight'));
// title and body stemming $stemmed_words = myTools::stemPhrase($raw_text);
// unique words with weight $words = array_count_values($stemmed_words);
// add tags $max = 0; foreach ($this->getPopularTags(20) as $tag => $count) { if (!$max) { $max = $count; }
$stemmed_tag = PorterStemmer::stem($tag);
if (!isset($words[$stemmed_tag])) { $words[$stemmed_tag] = 0; } $words[$stemmed_tag] += ceil(($count / $max) * sfConfig::get('app_search_tag_weight')); }
return $words; }

Nós também temos que atualizar o índice da pergunta cada vez que uma Tag é adicionada, então sobrescreva o método save() e do modelo da Tag 

[php]
public function save($con = null)
{
  $con = sfContext::getInstance()->getDatabaseConnection('propel');
  try
  {
    $con->begin();


$ret = parent::save($con); $this->getQuestion()->updateSearchIndex();
$con->commit();
return $ret; } catch (Exception $e) { $con->rollback(); throw $e; } }

Teste o indexador

O índice está pronto para ser processado. Inicialize-o pela popularização da base de dados novamente: 

$ php batch/load_data.php

Você pode inspecionar a tabela SearchIndex para checar se o índice está bem:

id | word | weight ---|------------|------- 10 | blog | 6 9 | offer | 4 8 | girl | 3 8 | rel | 3 8 | activ | 3 10 | activ | 3 9 | present | 3 9 | reallif | 3 11 | test | 3 12 | test | 3 13 | test | 3 8 | shall | 3 8 | tonight | 2 8 | girlfriend | 2 .. | ..... | ..

A função de busca

AND ou OR?

No queremos que a função gerencie ambas as pesquisas 'AND' e 'OR'. Por exemplo, se um usuário digita 'family zodiac', ele deve escolher entre a opção onde aparece as duas palavras ('AND'), ou todas as questões onde aparece ao menos uma das palavras ('OR'). O problema é que estas duas opções conduzem à queries diferentes: 

[sql]
// OR query    
SELECT DISTINCT question_id, COUNT(*) AS nb, SUM(weight) AS total_weight
FROM ask_search_index
WHERE (word = "family" OR word = "zodiac")
GROUP BY question_id
ORDER BY nb DESC, total_weight DESC

// AND query    
SELECT DISTINCT question_id, COUNT(*) AS nb, SUM(weight) AS total_weight
FROM ask_search_index
WHERE (word = "family" OR word = "zodiac")
GROUP BY question_id
HAVING nb = 2
ORDER BY nb DESC, total_weight DESC

Obrigado a keyword HAVING (explanada, por exemplo em w3schools), a query 'AND' é uma linha apenas maior que a 'OR'. Como o GROUP BY está na coluna do id, e porque há somente uma ocorrência no índice para uma palavra dada em uma pesquisa, se um question_id for retornado duas vezes, é porque a query combina o termo “família” e “zodiac”. Puro, não é?

O método de pesquisa

Para a pesquisa funcionar, nós necessitamos aplicar o mesmo tratamento à frase de busca ao conteúdo, de modo que as palavras incorporadas pelo usuário sejam reduzidas ao mesmo tipo da haste que se encontra no índice. Desde que retorna um jogo das perguntas sem nenhum foreign constraint, decidimos executá-lo como um método do objeto QuestionPeer.

O resultado da pesquisa precisa ser paginado. Como nós usamos um pedido complexo, o objeto sfPropelPager não pode ser empregado aqui, então vamos fazer uma paginação manual, usando um offset.

Esta é mais uma dica para relembrar: askeet é feito para trabalhar com universos (este é o assunto do tutorial do dia dezoito. Isto significa que uma função de busca deve somente retornar as perguntas etiquetadas com o app_permanent_tag atual se o usuário estiver navegando no askeet em um universo.

Todas estas condições fazem a query SQL ligeiramente mais dificil de ler, mas não muito diferente da descrita abaixo: 

[php]
public static function search($phrase, $exact = false, $offset = 0, $max = 10)
{
  $words    = array_values(myTools::stemPhrase($phrase));
  $nb_words = count($words);

  if (!$words)
  {
    return array();
  }

  $con = sfContext::getInstance()->getDatabaseConnection('propel');

  // define the base query
  $query = '
      SELECT DISTINCT '.SearchIndexPeer::QUESTION_ID.', COUNT(*) AS nb, SUM('.SearchIndexPeer::WEIGHT.') AS total_weight
      FROM '.SearchIndexPeer::TABLE_NAME;


if (sfConfig::get('app_permanent_tag')) { $query .= ' WHERE '; } else { $query .= ' LEFT JOIN '.QuestionTagPeer::TABLE_NAME.' ON '.QuestionTagPeer::QUESTION_ID.' = '.SearchIndexPeer::QUESTION_ID.' WHERE '.QuestionTagPeer::NORMALIZED_TAG.' = ? AND '; }
$query .= ' ('.implode(' OR ', array_fill(0, $nb_words, SearchIndexPeer::WORD.' = ?')).') GROUP BY '.SearchIndexPeer::QUESTION_ID;
// AND query? if ($exact) { $query .= ' HAVING nb = '.$nb_words; }
$query .= ' ORDER BY nb DESC, total_weight DESC';
// prepare the statement $stmt = $con->prepareStatement($query); $stmt->setOffset($offset); $stmt->setLimit($max); $placeholder_offset = 1; if (sfConfig::get('app_permanent_tag')) { $stmt->setString(1, sfConfig::get('app_permanent_tag')); $placeholder_offset = 2; } for ($i = 0; $i < $nb_words; $i++) { $stmt->setString($i + $placeholder_offset, $words[$i]); } $rs = $stmt->executeQuery(ResultSet::FETCHMODE_NUM); 

  // Manage the results
  $questions = array();
  while ($rs->next())
  {
    $questions[] = self::retrieveByPK($rs->getInt(1));
  }

  return $questions;
}

O método retorna uma lista de objetos Question, ordenados pela pertinência

O formulario de busca

O formulário da busca tem que estar sempre disponível, então a colocaremos na barra lateral. Como temos duas barras laterais distintas, devem incluir o mesmo partial: 

[php]
// add to defaultSuccess.php and questionSuccess.php in askeet/apps/frontend/modules/sidebar/templates/
<h2>find it</h2>
<?php include_partial('question/search') ?>

// create the following askeet/apps/frontend/modules/question/templates/_search.php fragment
<?php echo form_tag('@search_question') ?>    
  <?php echo input_tag('search', htmlspecialchars($sf_params->get('search')), array('style' => 'width: 150px')) ?>&nbsp;
  <?php echo submit_tag('search it', 'class=small') ?>
  <?php echo checkbox_tag('search_all', 1, $sf_params->get('search_all')) ?>&nbsp;<label for="search_all" class="small">search with all words</label>
</form>

Busca pela barra lateral

As regras @search_question devem ser definidas em routing.yml: 

search_question:
  url:   /search/*
  param: { module: question, action: search }

Você sabe o que esta ação question/search faz? Quase nada, desde que a maioria do trabalho é feito pelo método QuestionPeer::search() descrito abaixo: 

[php]
public function executeSearch ()
{
  if ($this->getRequestParameter('search'))
  {
    $this->questions = QuestionPeer::search($this->getRequestParameter('search'), $this->getRequestParameter('search_all', false), ($this->getRequestParameter('page', 1) - 1) * sfConfig::get('app_search_results_max'), sfConfig::get('app_search_results_max'));
  }
  else
  {
    $this->redirect('@homepage');
  }
}

A ação tem que traduzir um parâmetro do pedido da página em um offset para o método ::search(). O app_search_results_max é o numero de resultados por pagina, e como usual, é um parâmetro da aplicação definido no arquivo do app.yml: 

all:
  search:
    results_max:         10

Mostrar o resultado da busca

A parte a mais dura do trabalho está feita, nós apenas temos que mostrar o resultado em askeet/apps/frontend/modules/question/templates/searchSuccess.php. Como nós não executamos os paginadores reais, o molde não tem nenhuma informação sobre o número total dos resultados. Os paginadores indicarão apenas 'mais resultados' no final da lista do resultado se o número dos resultados igualar o máximo dos resultados por a página: 

[php]
<?php use_helpers('Global') ?>

<h1>questions matching "<?php echo htmlspecialchars($sf_params->get('search')) ?>"</h1>

<?php foreach($questions as $question): ?>
  <?php include_partial('question/question_block', array('question' => $question)) ?>
<?php endforeach ?>

<?php if ($sf_params->get('page') > 1 && !count($questions)): ?>
  <div>There is no more result for your search.</div>
<?php elseif (!count($questions)): ?>
  <div>Sorry, there is no question matching your search terms.</div>
<?php endif ?>

<?php if (count($questions) == sfConfig::get('app_search_results_max')): ?>
  <div class="right">
    <?php echo link_to('more results &raquo;', '@search_question?search='.$sf_params->get('search').'&page='.($sf_params->get('page', 1) + 1)) ?>
  </div>
<?php endif ?>

Ah, sim, esta é a surpresa final. Nós refatoramos um pouco os templates da query para criar um bloco da questão '_question_block.php', como o código é reusado em mais de um lugar. Olhe este fragmento no repositório de fonte, não há nada de novo nele, Mas nos ajuda a manter o código limpo.

resultado de busca

Nos vemos amanha

Vimos em aproximadamente uma hora como construir um bom Search Engine, perfeitamente adaptado as nossas necessidades. Ele é leve, rápido e eficiente. Retorna resultados pertinentes. Você gostaria de integrar uma biblioteca externa para fazer o mesmo trabalho?

Se não, você provavelmente está começando a pensar de forma symfony. Se você não entendeu este tutorial, você pode provavelmente adicionar ao Search Engine a indexação das respostas a uma pergunta. Questões e sugestões são bem vindas no askeet fórum. E sobretudo, não crie uma nova pergunta no askeet se uma similar já existe: Agora existe um motor de busca, você não tem desculpas!