Lunes 8:45pm, luego de un largo día de trabajo abres el navegador y buscas la información habitual:
como preparo la cena ...
¡Clic! 0.20 s después, con 2.560 millones de resultados en frente de ti, comienza la búsqueda por una comida apropiada
¡Clic!
¡Clic!
¡Clic! y al cabo de unos segundos ya estás listo para ir a preparar la cena.
¡Espera un momento!
¿Tardar menos de un minuto para encontrar la información que se desea dentro de 2 560 000 resultados?
Bueno, el propósito de esta entrada no es explicar la cantidad de ordenadores necesarios para lograr tal rapidez, algoritmos de caché, base de datos ni tampoco hablar del pago de la factura de luz de un buscador como ese. El objetivo de este artículo es mostrar una de las técnicas más básicas pero sin embargo más importante cuando se quiere alcanzar la mayor relevancia posible.
No es necesario conocimientos previos de programación para aprovechar esta entrada, pero ayudaría mucho. Si piensas seguir el artículo al pie, al menos deberás tener instalado una versión de ruby >= 1.9.2 e instalar una gema que programé específicamente para este artículo:
gem install estem
para más información visita:
https://github.com/MaG21/estem
Stemming
Es una técnica que consiste en reducir a la raíz una palabra, dicha palabra puede ser una palabra derivada o estar en su forma conjugada
p . ej. supón que tienes dos fragmentos de textos, la palabra clave
pescadería y deseas saber cuál podría ser el más relevante de los dos.
primer fragmento
La pescadería es el lugar donde venden pescados atrapados por los pescadores. El pescador es la persona que atrapa el pescado.
segundo fragmento
Por este medio le informamos que cerraremos la pescadería Mar. Por favor perdone los inconvenientes que esto podría causar, nuestra prioridad es abrir la pescadería lo más pronto posible.
Una persona ingenua haría una búsqueda por palabras clave contra esos dos fragmentos, a continuación un modelo en ruby de como se vería una búsqueda por palabras claves común y corriente:
~ $ irb
irb(main):001:0> frag1 = "La pescadería es..."
irb(main):002:0> frag2 = "Por este medio l..."
irb(main):003:0> st = "\033[47m\033[1;31m"
irb(main):004:0> en = "\033[m"
irb(main):005:0> re = /pescadería/
irb(main):006:0? idx = 0
irb(main):007:0> [frag1,frag2].each do|txt|
irb(main):008:1* ret = txt.gsub(re,"#{st}\\&#{en}")
irb(main):009:1> puts "Fragmento #{idx+=1}\n#{ret}\n"
irb(main):010:1> end
Fragmento 1
La pescadería es el lugar donde venden pescados atrapados por
los pescadores. El pescador es la persona que atrapa el pescado.
Fragmento 2
Por este medio le informamos que cerraremos la pescadería Mar. Por
favor perdone los inconvenientes que esto podría causar, nuestra
prioridad es abrir la pescadería lo más pronto posible.
Según los resultados, el segundo fragmento es el que más coincidencias posee y por ende, para este criterio de búsqueda, el más relevante. Sin duda el segundo fragmento es el
menos relevante, pues aunque una persona explícitamente desee la información del segundo fragmento, con esa sola palabra clave sería ilógico entregar un resultado tan alejado del significado de la misma. Si la persona desea obtener lo que busca, simplemente deberá entregar más de una palabra clave
p. ej. el nombre de la pescadería.
Veamos como se vería el resultado de la búsqueda anterior, aplicando otro criterio de búsqueda a partir de raíces gramaticales, dichas raíces si no lo son, son muy parecidas a los
lexemas y son el resultado de aplicar la técnica del
Stemming a una palabra. Continuando con la sesión de irb anterior, tenemos:
irb(main):011:0> require 'estem'
irb(main):012:0> re = %r{\b#{'pescadería'.es_stem}[a-zA-ZáéíóúüÁÉÍÓÚÜÑñ]++}
irb(main):013:0? idx = 0
irb(main):014:0> [frag1,frag2].each do|txt|
irb(main):015:1* ret = txt.gsub(re,"#{st}\\&#{en}")
irb(main):016:1> puts "Fragmento #{idx+=1}\n#{ret}\n"
irb(main):017:1> end
Fragmento 1
La pescadería es el lugar donde venden pescados atrapados por
los pescadores. El pescador es la persona que atrapa el pescado.
Fragmento 2
Por este medio le informamos que cerraremos la pescadería Mar. Por
favor perdone los inconvenientes que esto podría causar, nuestra
prioridad es abrir la pescadería lo más pronto posible.
A simple vista se puede ver que el primer fragmento es el más relevante, y sin duda lo es. Ahora te podrías estar preguntando ¿Qué pasó? Bueno no mucho en realidad, simplemente se cargo la gema, se aplicó
Stemming a la palabra pescadería y se utilizó dicho resultado junto con una expresión regular para agarrar, por así decirlo, las palabras que concuerden.
Palabras vacías
Las palabras vacías o en inglés
stop words, son palabras que la mayor parte de las veces no aportan un nivel de relevancia mayor, son palabras que por su propio significado y alta frecuencia estropean las búsquedas
p. ej. tu, yo, el, ellos, para, contra, con, de. Para el español opino que es una lista muy numerosa. Si deseas una lista exhaustiva de palabras vacías, por favor visita la siguiente dirección, donde Martin Porter nos ofrece una gran cantidad:
http://snowball.tartarus.org/algorithms/spanish/stop.txt
Veamos un ejemplo funcional:
primer fragmento
Por favor, note que algunos baños son únicamente para mujeres.
Le pedimos que sea cuidadoso. Gracias por cooperar.
segundo fragmento
Un animal herbívoro es aquel que se alimenta de las plantas,
árboles, arbustos y hierbas.
Aplicando todo lo que se ha visto hasta ahora, nos queda un programa de prueba como este:
#!/usr/bin/env ruby
# encoding: UTF-8
# URL: newbieshell.blogspot.com
require 'estem'
require 'getoptlong'
EQU = {'a' => '[aAáÁ]', 'e' => '[eEéÉ]','i' => '[iIíÍ]','o' => '[oOóÓ]','u' => '[uUúÚ]',
'á' => '[áÁaA]', 'é' => '[éÉeE]','í' => '[íÍiI]','ó' => '[óÓoO]','ú' => '[úÚuU]',
'ü' => '[üÜuU]', 'Á' => '[áÁaA]','É' => '[éÉeE]','Í' => '[íÍiI]','Ó' => '[óÓoO]',
'Ú' => '[úÚuU]', 'Ü' => '[üÜuU]','Ñ' => '[ñÑ]','ñ' => '[ñÑ]'}
STOPWORDS = ['por', 'de', 'los', 'que', 'mucho',
'algunos', 'son', 'el', 'ellos', 'qué']
$stopwords = false
def get_words(string)
# I am in love with ruby, look:
ret = if $stopwords
string.scan(/[a-zA-ZáéíóúüÁÉÍÓÚÜÑñ]+/) - STOPWORDS
else
string.scan(/[a-zA-ZáéíóúüÁÉÍÓÚÜÑñ]+/)
end
ret.collect { |w| w.es_stem }
end
def make_es_regexp(string)
words = get_words(string)
re_words = words.collect do|w|
w.each_char.collect do|c|
'aeiouAEIOUáéíóúüÁÉÍÓÚÜÑñ'.include?(c) ? EQU[c] : c
end.join()
end
Regexp.new("(?<![a-záéíóúüÁÉÍÓÚÜÑñ])(#{re_words.join('|')})[a-záéíóúüÁÉÍÓÚÜÑñ]*", Regexp::IGNORECASE)
end
begin
opt = GetoptLong.new(['--stop-words', GetoptLong::NO_ARGUMENT])
opt.quiet = true
$stopwords = true if opt.get
rescue
$stderr.puts "Opción inválida"
exit
end
# Estas dos cadenas de caracteres se utilizan para darle color
# a los resultados encontrados. NOTA necesita una terminal ANSI
st = "\033[47m\033[1;31m"
en = "\033[m"
frag1 = <<EOF
Por favor, note que algunos baños son únicamente para mujeres.
Le pedimos que sea cuidadoso. Gracias por cooperar.
EOF
frag2 = <<EOF
Un animal herbívoro es aquel que se alimenta de las plantas,
árboles, arbustos o hierbas.
EOF
# búsqueda: "por qué algunos animales son herbívoros?"
re = make_es_regexp("por qué algunos animales son herbívoros?")
[frag1,frag2].each do|text|
puts text.gsub(re,"#{st}\\&#{en}"), "\n\n"
end
Ahora ejecutemos el ejemplo, las palabras de búsqueda para este ejemplo son:
por qué algunos animales son herbívoros?
~$ ruby search.rb
Por favor, note que algunos baños son únicamente para mujeres.
Le pedimos que sea cuidadoso. Gracias por cooperar.
Un animal herbívoro es aquel que se alimenta de las plantas,
árboles, arbustos o hierbas.
El texto más irrelevante que alguien se pueda imaginar para esta búsqueda es el primer fragmento, pero gracias a las palabras vacías toma relevancia falsa. Ejecutemos el programa y esta vez, quitando las palabras vacías:
~$ ruby search.rb --stop-words
Por favor, note que algunos baños son únicamente para mujeres.
Le pedimos que sea cuidadoso. Gracias por cooperar.
Un animal herbívoro es aquel que se alimenta de las plantas,
árboles, arbustos o hierbas.
Como se ve, remover las palabras vacías de los términos de búsquedas, tiene sus beneficios, pero también tiene sus desventajas, de las cuales no hemos hablado, la más notable es que no se podrán realizar
búsquedas por frase, algo un poco más complejo si se quiere hacer bien.
Conclusión
Si tienes intenciones de adentrarte en el mundo de la extracción de
información, existen muchos acercamientos que podrían ser de interés y
no se mencionaron, p. ej. un acercamiento estadístico, utilizando el
teorema de Bayes; un acercamiento tomando en cuenta el momento de la consulta, si es
hora de comida o una hora de trabajo; búsqueda geolocalizadas; búsquedas
sentimentales o por supuesto, una combinación de todos esos
acercamientos.
Sin duda faltan muchos pequeños detalles por tomar en cuenta, pero con lo mencionado anteriormente, es suficiente para entender un poco acerca de los buscadores, y si se cuenta con los conocimientos necesarios de programación, cualquier persona sería capaz de programar un algoritmo de búsqueda superior a una innumerable cantidad de paginas web allá afuera.
La brevedad es difícil de alcanzar y sin cuidado complica lo que se quiere simplificar en primer lugar. Ten cuidado con la codificación de los textos que manejas; Se organizado; clasifica la información e Intenta ejecutar todo lo que se presenta aquí.
Referencias
- Spanish Stemming Algorithm, Martin Porter
Enlaces Útiles
- Lista de palabras vacias
- https://github.com/MaG21/estem
- IMG, Enlace directo a la página del autor de la imagen de la portada.
