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: , , , , ,

segunda-feira, 30 de junho de 2008

Google Treasure Hunt 2 - MapReduce?

Para resolver o Google Treasure Hunt 2, decidi usar um velho programa para busca de arquivos implementado em C++ usando multi-threading. Eu mudei algumas partes do código, só para garantir que possa fazer a busca pelos 2 padrões especificados no problema, e escolhi usar o framework Qt (da Trolltech) que tem algumas funções muito legais para lidar com arquivos, e isso é realmente verdade – você não precisa de mais nada, a não ser as classes QFile e QDir e derivadas delas.

Se você gosta de programação distribuída, talvez você já tenha ouvido falar no modelo MapReduce, desenvolvido pela Google (www.google.com). De acordo com Jeffrey Dean e Sanjay Ghemawat, em um artigo (“Distributed Programming with MapReduce) escrito para o interessante livro “Beautiful Code” (O’Reilly, 2007), MapReduce was developed as a way of simplifying the development of large-scale computations at Google.” (tradução: “O MapReduce foi desenvolvido como uma forma de simplicar o desenvolvimento de processamento em larga-escala no Google”) Acredito que esse problema proposto no Google Treasure Hunt não seja realmente um “processamento em larga-escala”, mas eu gostei da forma como o MapReduce funciona, e decidi aplicar esse conceito ao meu programa.

Aqui está o problema número 2 do Google Treasure Hunt:

Here is a random zip archive for you to download:
GoogleTreasureHunt08_14338682343771558225.zip

Unzip the archive, then process the resulting files to obtain a numeric result. You'll be taking the sum of lines from files matching a certain description, and multiplying those sums together to obtain a final result. Note that files have many different extensions, like '.pdf' and '.js', but all are plain text files containing a small number of lines of text.

Sum of line 4 for all files with path or name containing BCD and ending in .js
Sum of line 5 for all files with path or name containing foo and ending in .xml
Hint: If the requested line does not exist, do not increment the sum.

Multiply all the above sums together and enter the product below.
(Note: Answer must be an exact, decimal representation of the number.)

Se você der uma olhada no código fonte, existem 2 threads; o primeiro (Mapper) obtêm a lista de arquivos com um padrão de nomes fornecido (no meu caso, nomes contendo “BCD” e com extensão “.js”, ou contendo “foo” e terminando com “.xml”); o segundo thread (Reducer) utiliza a lista com nomes de arquivos do thread Mapper e faz uma outra busca mais profunda dentro de cada um dos arquivos pré-selecionados (para obter os valores de números nas linhas de número “4”). O principal método do Mapper é o seguinte:

bool FileSearchMap::depthFirstTraversal(const QString& currentDir)

{

QDir dirP(currentDir);

QString temp;

QString fileName;

QStringList entryP = dirP.entryList();

QStringListIterator entryL(entryP);

while (entryL.hasNext())

{

producerMutex.lock();

if (myFileCount == 5)

{

bufferNotFull.wait(&producerMutex);

} // if - mutex and signal

producerMutex.unlock();

fileName.clear();

temp = entryL.next();

if ((temp != ".") && (temp != ".."))

{

fileName = currentDir;

fileName.append('\\');

fileName.append(temp);

if (isDirectory(fileName))

{

depthFirstTraversal(fileName);

}

else

{

if (isRegular(fileName))

{

unsigned int ftype = 0;

if ( ( fileName.endsWith(".js") ) &&

( fileName.contains("BCD") ) )

ftype = TXT_FILE_PATTERN;

else if ( ( fileName.endsWith(".xml") ) &&

( fileName.contains("foo") ) )

ftype = XML_FILE_PATTERN;

if ( ftype != 0 )

{

DirEntry dentry( fileName, ftype );

queueMutex.lock();

textFiles.push(dentry);

queueMutex.unlock();

producerMutex.lock();

++myFileCount;

producerMutex.unlock();

bufferNotEmpty.wakeAll();

}

}

} // if - isDirectory / isRegular

} // if

} // while

return true;

}

O método acima sera chamado exatamente uma vez, a partir do método run da minha implementação do QThread no Mapper. Colocando o método depthFirstTraversal para rodar, primeiramente ele obtêm todos os arquivos do diretóro, chamando o método entryList, da classe QDir. Então um iterator é instanciado sobre a lista de arquivos anteriormente obtida, e, enquanto estiver iterando sobre os arquivos, e antes que qualquer coisa eu faço uma chamada à função wait da estrutura QWaitCondition: a wait condition é um tipo de variável de condição usada para sincronizar threads, interrompendo-o no caso de ter obtido 5 arquivos (claro, pode ser qualquer número que você queira). Porque obter exatamente 5 arquivos e interromper a execução, esperando para que a estrutura QWaitCondition seja liberada? Isso é usado de forma a criar um buffer com capacidade para 5 arquivos (no máximo), a partir do qual o thread Reducer pode iterar sobre cada um dos arquivos listados pelo thread Mapper, abrir cada um desses arquivos, e procurar pelo critério de busca dado. Dessa forma, o thread Reducer pode lidar apenas com uma lista de 5 arquivos, esgotá-la, e depois permitir que o Mapper preencha com mais alguns novos arquivos encontrados. Essa é a primeira regra usada para sincronizar os 2 threads: Mapper, comece a cobrir o buffer com os nomes dos arquivos encontrados, até que ele tenha 5 elementos. Daí, espere até que o Reducer consuma alguns desses arquivos, pois a partir disso você pode obter mais alguns arquivos. Faça isso até o fim dos tempos”. Agora, o thread Reducer, obtendo todos os arquivos que o Mapper consiga procurar:

void KeySearchReduce::run()

{

DirEntry dirEntry;

int cnt = 0;

do

{

prod->producerMutex.lock();

if (prod->myFileCount == 0)

{

prod->bufferNotEmpty.wait(&prod->producerMutex);

if (prod->isSearchDown())

{

prod->producerMutex.unlock();

return;

}

}

prod->producerMutex.unlock();

prod->queueMutex.lock();

dirEntry = prod->getFirstTextFile();

prod->queueMutex.unlock();

QFile infile(dirEntry.getFileName());

if (!infile.open(QIODevice::ReadOnly | QIODevice::Text) )

continue;

QString line;

unsigned int i = 0;

QTextStream in(&infile);

if ( dirEntry.getFileType() ==

FileSearchMap::TXT_FILE_PATTERN ) {

while (!in.atEnd())

{

line = in.readLine();

++i;

if ( i == 4 ) {

lineP2Count += atol(line.toLocal8Bit().constData());

++foundCount;

break;

}

} // while

} else if ( dirEntry.getFileType() ==

FileSearchMap::XML_FILE_PATTERN ) {

while (!in.atEnd())

{

line = in.readLine();

++i;

if ( i == 5 ) {

lineP1Count += atol(line.toLocal8Bit().constData());

++foundCount;

break;

}

} // while

} // if - getFileType()

infile.close();

prod->producerMutex.lock();

prod->myFileCount--;

prod->producerMutex.unlock();

prod->bufferNotFull.wakeAll();

} while (!prod->isSearchDown());

}

O Reducer na primeira linha do comando “do” diz o seguinte: Ei Mapper, você tem algum arquivo para que eu possa procurar pelo informação numérica na linha X? Caso você não tenha arquivo algum, eu esperarei um pouco, até que você tenha algo para mim...” Então, para cada arquivo que o thread Reducer processa, ele avisará ao Mapper, de forma a que ele possa alimentar mais o buffer. No caso do Mapper estiver dormindo em um buffer cheio com 5 elementos, ele será acordado e então recomeçará a cobrir o buffer com arquivos – isso é feito com uma chamada a prod->bufferNotFull.wakeAll(), encontrado no fim do loop principal do Reducer. A chamada a wakeAll faz com que todos os threads que estejam dormindo sobre essa variável de condição acordem imediatamente (ou quase). Com isso, o Mapper pode estar dormindo na linha bufferNotFull.wait(&producerMutex), no início do loop de busca, e essa chamada à função wakeAll a partir do Reducer pode liberar o bufferNotFull (uma instância do QWaitCondition), permitindo ao Mapper reiniciar o processo de completar o seu buffer de 5 elementos de novo. Tudo o que o Mapper tem que fazer é cobrir o buffer com nomes de arquivos.

Nós estamos lidando aqui com recursos compartilhados, e os mutexes são de uso obrigatório (veja as referências às instâncias de QMutex no código fonte) uma vez que essa aplicação é multithreaded, e não queremos que ocorram condições de corrida.

Colocando tudo junto:

FileSearchMap* mapper = new FileSearchMap;

KeySearchReduce* reducer = new KeySearchReduce;

mapper->setDirectory( dir );

reducer->setMapper( mapper );

mapper->start();

reducer->start();

mapper->wait();

reducer->wait();

long long a1, a2;

cout << argv[1] << " contains " <<>getFoundCount()

<< " files that contains " <<>getLineCount()

<< " lines for the pattern 1 ( " << (a1 = reducer->getLineP1Count()) <<

" ) and pattern 2 ( " << (a2 = reducer->getLineP2Count()) << " )." << endl;

long long response = a1*a2;

cout << "Response: (" <<>")" << endl;

Aqui, a chamada getLineP1Count() retorna a soma de todos os numeros na linha 4, nos arquivos com o primeiro padrão; e getLineP2Count() faz o mesmo para o padrão de busca 2.

Claro, dá pra resolver o problema todo sem usar capacidade de multithread, mas aí não tem graça! :)


Marcadores: , , , ,