quarta-feira, 28 de abril de 2010

Lucene Search

Para quem precisa disponibilizar um mecanismo de busca para um site, que permita indexação de conteúdos em diversos formatos (PDF, ODT, DOC, registros de banco de dados, etc.), a solução Lucene Search, da Apache Foundation (http://lucene.apache.org/) supre eficientemente essa demanda.

Nesse post, pretendo mostrar, de forma sucinta, como o recurso de indexação e busca pode ser implementado com Lucene Search, usando um framework JEE, no caso, o JBoss Seam (http://seamframework.org), ou outro qualquer de interesse do desenvolvedor.
Primeiro, é preciso permitir que as suas entidades (JPA ou Hibernate) tenham a capacidade de gerar informações de índice (metadados), que serão gravados em disco, a cada vez que um dado for alterado no banco. Haverá, é lógico, uma preocupação sobre quais campos da entidade (digamos, o tipo Pessoa será indexado unicamente pelo campo str_nome da tabela pessoa) serão indexados. Para configurar os eventos do Lucene Search, de forma que eventos de escrita no banco atualizem os "listenes" do Lucene, é preciso configurar o arquivo "ejb-jar.xml" ou o "hibernate.cfg.xml", com os seguintes itens de configuração:

<property name="hibernate.search.default.indexBase"> value="./lucene_indexes/"/>
<property name="hibernate.ejb.event.post-insert" value="org.hibernate.search.event.FullTextIndexEventListener"/>
<property name="hibernate.ejb.event.post-update" value="org.hibernate.search.event.FullTextIndexEventListener"/>
<property name="hibernate.ejb.event.post-delete" value="org.hibernate.search.event.FullTextIndexEventListener"/>

No caso, a propriedade "hibernate.search.default.indexBase" configura o diretório onde serão gravados os índices. É permitido usar diretórios relativos, como no caso acima, que configura o diretório de índices para o caminho lucene_indexes, que será referenciado dentro do path atual configurado para esse contexto. Dependendo do servidor de aplicação, o diretório "." pode referenciar o diretório server, do diretório padrão de instalação do JBoss, ou o server/default/deploy. Caso não exista o diretório acima, será automaticamente criado (criará o diretório server/default/deploy/lucene_indexes).
Outro passo importante é copiar as bibliotecas do Lucene e do Hibernate Search (que serão adicionados no arquivo MANIFEST.MF, no diretório META-INF):
lucene-core.jar
hibernate-search.jar
hibernate-commons-annotations.jar
hibernate-annotations.jar
lucene-highlighter-2.1.0.jar

Após isso, é necessário inserir as anotações específicas do Lucene e do Hibernate Search. A primeira indicará, na declaração da sua classe POJO (JPA/Hibernate) que ela será indexada:

@Entity
@Indexed
@Table(name = "relator", schema = "juris")
public class Relator implements java.io.Serializable {
...
É preciso marcar o campo da entidade que representa o índice. Na verdade, qualquer campo único pode ser usado. A anotação DocumentId apenas ajudará o Lucene a garantir a unicidade dos registros:
@Id
@DocumentId
@Column(name = "id_relator", unique = true, nullable = false)
public short getIdRelator() {
return this.idRelator;
}

Dentro da definição dessa entidade, agora é necessário especificar quais campos são indexados, e como eles serão indexados:
@Column(name = "str_nome_relator", length = 500)
@Length(max = 500)
@Field(index=Index.TOKENIZED,store=Store.YES,
analyzer= @Analyzer(impl = BrazilianAnalyzer.class))
public String getStrNomeRelator() {
return this.strNomeRelator;
}
Nesse ponto, cabem algumas explicações: o parâmetro index permite dizer se o campo será quebrado em tokens (trechos de caracteres), ou será tratado como uma sequência única. No caso, por ser um campo String composto por nome e sobrenome do relator, é aconselhável usar a constante Index.TOKENIZED. O parâmetro store diz se o campo será armazenado em arquivo, e pode ser visualizado através da ferramenta Luke (http://code.google.com/p/luke/). Essa ferramenta, por sinal, é muito útil para estudar a forma com que o Lucene gera os índices em arquivo, permitindo simular buscas usando diferentes analizadores semânticos de linguagens.

O outro parâmetro (analyzer) permite definir um analizador semântico diferente do Inglês. No caso, existe um BrazilianAnalyzer, e isso é muito importante, pois o tratamento sobre caracteres acentuados, por exemplo, é viabilizado através dos analizadores. Caso um analizador adequado não seja usado, internamente o Lucene pode ignorar caracteres acentuados, por exemplo, como se fossem símbolos inválidos. Ademais, o analizador específico para a linguagem que você utiliza para armazenar dados permite que uma busca por "Abraão" ou "Abraao" retorne o mesmo resultado. O recurso de internacionalização dos Analyzers permite ignorar detalhes de acentuação, melhorando a qualidade da busca.

Agora, já é possível fazer uma busca, usando o trecho a seguir:
try
{
QueryParser parser =
new MultiFieldQueryParser( new String[] {
"strNomeRelator"
},
new BrazilianAnalyzer() );
Query luceneQuery = parser.parse(nome_relator);

FullTextQuery ftq = entityManager.createFullTextQuery(luceneQuery
,Relator.class);
} catch (ParseException exc) {
}

Na chamado a classe MultiFieldQueryParser, nós passaremos como parâmetro: o campo que foi indexado, e que será buscado agora; e o analizador utilizado (BrazilianAnalyzer). Normalmente, pode-se passar null para o analyzer, pois ele já foi configurado na entidade Relator. Dessa forma, nós ainda não criamos a Query Lucene, apenas criamos um "criador de Queries Lucene". A seguir, nós chamamos o método parse, herdado da classe ancestral QueryParser, passando como parâmetro o valor que se quer buscar (por exemplo, a variável String nome_relator poderia conter "José", pois queríamos buscar por José na base). Com a query em mão, criaremos a FullTextQuery, essa sim que fará a busca propriamente dita na base de índices.

Para retornar a lista de registros encontrados, devemos chamar:

List<relator> resultPrimary = ftq.getResultList();

No próximo post, veremos como executar outras funções, como: marcar os hits encontrados, procurar em múltiplas tabelas, etc.

Marcadores: , , , , , , ,

sábado, 16 de agosto de 2008

Google Treasure Hunt 3: Busca em Profundidade (Depth-First Search)

Esse é outro problema do Google Treasure Hunt que eu resolvi. Esse foi o mais fácil de todos, e realmente não era necessário nenhum conhecimento de programação. Tenha-se em mente apenas que o não uso de programação para resolvê-lo não é de modo algum divertido! Tente ensinar seu computador a fazê-lo por você… O problema que eu obtive no Google foi o seguinte:

“Below is a diagram of a computer network. The nodes are hosts on the network, and the lines between them are links. A packet is sent out from host P with a destination of 4.229.231.150. Which nodes does the packet pass through on its way to the destination? (include start and final node in your answer)”

O diagrama para o modelo da rede acima foi fornecido na forma da tabela de roteamento a seguir:

A 26.40.28.17 75.174.216.140 => 126.186.188.58 26.40.28.17 => 17.100.195.84 4.229.231.0/24 => 75.174.216.140 13.157.234.26

B 13.157.234.26 76.246.145.72 => 53.12.68.161 126.186.188.58 => 75.174.216.140 53.12.68.0/24 => 26.40.28.17 17.100.195.84

C 53.12.68.161 75.174.216.140 => 219.88.219.35 229.23.61.42 => 13.157.234.26 17.100.195.0/24 => 103.19.57.145 126.186.188.58

D 103.19.57.145 86.60.122.237 => 86.60.122.237 117.146.177.141 => 53.12.68.161 229.23.61.0/24 => 219.88.219.35 212.222.1.12

E 4.229.231.150 4.229.231.150 => 103.19.57.145 54.35.7.207 => 54.35.7.207 126.186.188.0/24 => 199.223.210.72 229.23.61.42

F 54.35.7.207 4.229.231.150 => 229.23.61.42 13.157.234.26 => 199.223.210.72 26.40.28.0/24 => 4.229.231.150 86.60.122.237

G 86.60.122.237 229.23.61.42 => 54.35.7.207 13.157.234.26 => 103.19.57.145 103.19.57.0/24 => 212.222.1.12 219.88.219.35

H 212.222.1.12 126.186.188.58 => 219.88.219.35 75.174.216.140 => 86.60.122.237 103.19.57.0/24 => 103.19.57.145 229.23.61.42

I 229.23.61.42 4.229.231.150 => 4.229.231.150 117.146.177.141 => 54.35.7.207 126.186.188.0/24 => 199.223.210.72 212.222.1.12

J 199.223.210.72 53.12.68.161 => 229.23.61.42 4.229.231.150 => 54.35.7.207 219.88.219.0/24 => 219.88.219.35 4.229.231.150

K 219.88.219.35 4.229.231.150 => 199.223.210.72 17.100.195.84 => 212.222.1.12 126.186.188.0/24 => 86.60.122.237 103.19.57.145

L 117.146.177.141 4.229.231.150 => 219.88.219.35 117.146.177.141 => 126.186.188.58 26.40.28.0/24 => 76.246.145.72 75.174.216.140

M 75.174.216.140 199.223.210.72 => 13.157.234.26 4.229.231.150 => 117.146.177.141 126.186.188.0/24 => 17.100.195.84 26.40.28.17

N 17.100.195.84 4.229.231.150 => 26.40.28.17 219.88.219.35 => 13.157.234.26 17.100.195.0/24 => 75.174.216.140 76.246.145.72

O 76.246.145.72 4.229.231.150 => 17.100.195.84 86.60.122.237 => 126.186.188.58 13.157.234.0/24 => 53.12.68.161 117.146.177.141

P 126.186.188.58 13.157.234.26 => 53.12.68.161 4.229.231.150 => 76.246.145.72 103.19.57.0/24 => 26.40.28.17 117.146.177.141

Como você talvez tenha suposto, o primeiro símbolo é o ID do nó de rede, seguido por seu número IP. A seguir, você tem uma sequência de 3 regras de roteamento, o pode ver se essa regra em específico serve para o pacote entrante (incoming packet, ou pacote de rede no estágio de ingresso ao roteador). O ultimo número IP nos dá a rota padrão (“default route”), apenas no caso em que esse nó não encontrou nenhuma regra de roteamento que coubesse para um dado pacote (a rota padrão é como um “else” após uma sequência de “IF”s...).No caso do pacote chegar à rota padrão, esse pacote será direcionado para o host definido pelo endereço IP na última coluna da tabela acima.

Criei uma solução em C++, que usa um método de busca em profundidade para buscar por um caminho válido saindo de um dado nó para outro no modelo de rede do problema. Minha idéia foi fazer a função de busca em profundidade (em ingles, “depth-first search”) andar de nó em nó (nós são rotulados como: A, B, C, etc.), iterando sobre cada uma das regras da tabela de roteamento, e procurando por cada uma dessas regras que possa rotear adequadamente o pacote através da rede. A função abaixo é auto-explicável:

bool RoutingTable::routeTo( string node, string* resp )

{

bool do_it_again = true;

RoutingEntry rentry = findRouteEntry( node );

if ( rentry.doneThis() )

return false;

resp->append( rentry.getId() );

if ( rentry.getAddress().compare(getFinalDestination()) == 0 ) {

return false;

}

vector<RoutingRule> routing_rules = rentry.getRules();

vector<RoutingRule>::iterator i;

rentry.markThis(true);

// go through each of the routing rules

for ( i = routing_rules.begin(); ( i != routing_rules.end() ) &&

do_it_again; i++ )

{

if ( (*i).canRoute(getFinalDestination()) ) {

do_it_again = routeTo( (*i).getRedirection(), resp );

} // if

} // for

rentry.markThis(false);

// no rules; asks the default gateway…

if ( do_it_again )

{

do_it_again = routeTo( rentry.getDefaultRoute().getRedirection(),

resp );

}

return do_it_again;

}

Nessa solução usei apenas a STL do C++, ou C++ Standard Template Library (STL). Todos os nós são armazenados em estruturas como elementos de um vector, e são localizadas por símbolos de ID (A, B, C, etc.), ou por números IP (método findRouteEntry()). Cada nó tem a sua própria estrutura “Rules” (que você pode obter chamando getRules()). Uma vez processadas, cada uma dessas regras pode apontar para um outro nó da tabela, e a função routeTo pode atuar de forma recursiva sobre uma dada regra. Se nenhuma regra suficiente para combiner com o pacote for encontrada, a função routeTo é chamada sobre o nó retornado pela chamada a getDefaultRoute:

// no rules; asks the default gateway…

if ( do_it_again )

{

do_it_again = routeTo( rentry.getDefaultRoute().getRedirection(),

resp );

}

As chamadas para a função markThis() são para evitar recursões infinitas (iterar sobre os mesmos nós, de uma forma circular e muitas vezes irreversível, levando ao esgotamento de recursos computacionais). A semântica é simples: markThis(true), quando o código precisar entrar numa “regão crítca”, e markThis(false) quando tiver saído da região crítica.

Você conseguiria encontrar a diferença entre o método de roteamento que eu formulei para o que é implementado por roteadores de rede de verdade (de fabricantes como Cisco)? Talvez meus posts anteriores com questões da certificação CCNA da Cisco possam ajudar...

Marcadores: , , , , ,