Para comentarle el contexto; Actualmente trabajo para la compañía avVenta en Costa Rica y como parte de un proyecto para uno de sus clientes, existía una implementación que toma un archivo con palabras vulgares o obscenas y realiza una búsqueda a fuerza bruta (O(n)), recorriendo todas las palabras hasta encontrar la ocurrencia de una de las palabras en el texto, el pseudo-stremmer que tiene este algoritmo, consiste en agregar palabras sobre el corpus de las obscenidades, pero cambiando por ejemplo las “o” por un “0” (cero), o la “a” por un (4), etc.
Me pregunte que desempeño tendría esta implementación contra la búsqueda vectorial y contra algoritmos de búsqueda de texto dentro de texto.
Además de un algoritmo “custom” que el cliente me facilito (valga decir que es el mas deficiente a nivel de resultados, sin embargo vale resaltar, el mismo tiene “stremmers” para diferentes lenguajes y soporte para búsqueda i18n), también hice una prueba con Apache Lucene (la implementación de un buscador vectorial Open de Apache, http://lucene.apache.org/java/docs/index.html), utilizando un Índice invertido en memoria, además utilice el algoritmo, que según leí es mas rápido de esta biblioteca (http://johannburkard.de/software/stringsearch/), el cual se basa en un hibrido de Boyer, Moore, Horspool, Raita, los resultados en milisegundos y orden descendiente los comparto a continuación.
{203=implementación basada en java.lang.String.contains (indexOf > -1)
2266=implementación basada en Apache Lucene
2312=implementacion basada en el stringsearch (http://johannburkard.de/software/stringsearch/),
11406=obscenityProfanityFilter, este fue un algoritmo propietario que me pasaron, el mismo que tiene los stremmer.
}
Valga decir que hice otros “Junit” (pruebillas de unidad) para determinar que la funcionalidad de los algoritmos fuera idéntica y en efecto, todos funcionan de la manera esperada.
Dudoso con los resultados, fui curioso e implemente el siguiente código:
String text = "Hello folkes jiji opa oop upa lupa as and tropes and listes and shomis and tepos";
String wordToSearch = "shomis";
int loop = 2000;
long millins = 0;
long totalElapse = 0;
int hit = 0;
StringSearch so = new BoyerMooreHorspoolRaita();
millins = System.currentTimeMillis();
for (int i = 0; i <>
if (text.contains(wordToSearch)) {
hit += 1;
}
}
wordToSearch = "upalupa";
for (int i = 0; i <>
if (text.contains(wordToSearch)) {
hit += 1;
}
}
totalElapse = System.currentTimeMillis() - millins;
System.out.println("Contains algo: " + totalElapse);
System.out.println(hit + " = " + loop);
// **********************
// **********************
// **********************
hit = 0;
wordToSearch = "shomis";
millins = System.currentTimeMillis();
for (int i = 0; i <>
if (so.searchString(text, wordToSearch)!= -1) {
hit += 1;
}
}
wordToSearch = "upalupa";
for (int i = 0; i <>
if (so.searchString(text, wordToSearch)!= -1) {
hit += 1;
}
}
totalElapse = System.currentTimeMillis() - millins;
System.out.println("StringSearch algo: " + totalElapse);
System.out.println(hit + " = " + loop);
El resultado:
Contains algo: 0
2000 = 2000
StringSearch algo: 15
2000 = 2000
Dejando de lado que la implementación de StringSearch permite utilizar “wildcard” y que quizá funcione mejor en colecciones grandes (esto es un supuesto), me pareció interesante compartir estos resultados con alguien que esta mas comprometido con el tema, como comprenderá el mercado nacional, nos proporciona poco espacio para jugar con este tipo de cosas muy interesantes y el conocimiento que no se refresca tienen a marchitarse un poco (lo cual es una pena).
......
Comentarios