Estoy utilizando Ferret para las búsquedas (Full text search) escrita en Ruby y C inspirada en Apache Lucene que está escrita en Java.
No encontré por ninguna parte la implementación de SpellChecker para Ferret(si realmente existe entonces me ayudó para entender mejor Lucene :-) ), así es que tomé el código de Lucene SpellChecker en java (versión 2.4.1) buscando también inspiración :-)
No está al 100%, ya que por ahora no considera la frecuencia, sólo considera la distancia de Levenshtein, pero para una primera versión del proyecto en el que la uso es suficiente (www.buskauto.com).
La implementación es la misma que en Lucene:
* se crean ngramas de las palabras para el diccionario.
* luego para sugerir una o más palabras se crean los ngramas de la palabra con error
* se buscan en el diccionario las palabras que coincidan con algún ngrama.
* y se prioriza por la distancia de Levenshtein con respecto a la palabra con error.
Se utiliza así:
dir = Store::RAMDirectory.new()
@spell = SpellChecker::SpellChecker.new(dir)
@spell.indexDictionary(reader, :texto)
@spell.suggestSimilar(word, 3, indexReader, field, false)
A continuación el código:
require 'ferret'
require 'text'
class String
attr_accessor :___distance
attr_accessor :___freq
end
module SpellChecker
include Ferret
class SpellChecker
def initialize(spellIndex)
@spellIndex = spellIndex
writer = Index::IndexWriter.new(:dir => @spellIndex)
writer.close
@searcher = Search::Searcher.new(@spellIndex)
end
def indexDictionary(reader, term)
writer = Index::IndexWriter.new(:dir => @spellIndex, :analyzer => Analysis::WhiteSpaceAnalyzer.new)
writer.field_infos.add_field(:word, :store => :yes)
reader.terms(term).each{|word,b|
if word.length >= 3 and !exist(word)
doc = createDocument(word)
writer << doc
end
}
writer.optimize
writer.close
@searcher.close
@searcher = Search::Searcher.new(@spellIndex)
end
def suggestSimilar(word, numSug, ir, field, more_popular)
freq = 0
if ir and field
freq = field.respond_to?("collect") ? field.collect{|f| ir.doc_freq(f, word)}.max : ir.doc_freq(field, word)
end
#freq = (ir and field) ? ir.doc_freq(field, word) : 0
goal_freq = (more_popular and ir and field) ? freq : 0
query = Search::BooleanQuery.new
hash = createDocument(word)
hash.each do |key, gram|
add(query, key, gram)
end
min = 0.5
pq = Utils::PriorityQueue.new(numSug) {|a, b| a.___distance > b.___distance}
top_docs = @searcher.search(query)
top_docs.hits.each do |hit|
sug_word = @searcher[hit.doc][:word]
next if sug_word.eql?(word)
sug_word.___distance = 1.0 - (Text::Levenshtein.distance(sug_word, word) / [word.size, sug_word.size].max.to_f)
next if sug_word.___distance < min
if ir and field
sug_word.___freq = field.respond_to?("collect") ? field.collect{|f| ir.doc_freq(f, sug_word)}.max : ir.doc_freq(field, sug_word)
next if (more_popular and goal_freq > sug_word.___freq) or sug_word.___freq < 1
end
pq.insert(sug_word)
min = pq.top.___distance if pq.size == numSug
end
a = Array.new(pq.size)
a.collect{|x| pq.pop }
end
def add(bq, name, value)
if value.respond_to?("each")
value.each{|v|
tq = Search::TermQuery.new(name, v)
bq.add_query(tq, :should)
}
else
tq = Search::TermQuery.new(name, value)
bq.add_query(tq, :should)
end
end
def createDocument(word)
doc = {:word => word}
doc = addGram(word, doc)
end
def addGram(word, doc)
len = word.length
ng1 = getMin(len)
ng2 = getMax(len)
ng1.upto(ng2) do |ng|
key = "gram" + ng.to_s
doc[key] = Array.new
gend = nil
0.upto(len - ng) do |i|
gram = word[i..i+ng-1]
doc[key] << gram
doc["start" + ng.to_s] = gram if i == 0
gend = gram;
end
doc["end" + ng.to_s] = gend if gend
end
doc
end
def getMin(l)
if l > 5
3
elsif l == 5
2
else
1
end
end
def getMax(l)
if l > 5
4
elsif l == 5
3
else
2
end
end
def exist(word)
@searcher.doc_freq(:word, word) > 0
end
end
sábado, 29 de mayo de 2010
SpellChecker en Ruby
Suscribirse a:
Entradas (Atom)