sábado, 29 de mayo de 2010

SpellChecker en Ruby

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  


No hay comentarios: