¿Cómo puedo hacer una concordancia de subcadenas difusas en Ruby?

string fuzzy-search

Question

Encontré muchos enlaces sobre la coincidencia aproximada, comparando una cadena con otra y viendo cuál obtiene la mayor puntuación de similitud.

Tengo una cadena muy larga, que es un documento, y una subcadena. La subcadena proviene del documento original, pero se ha convertido varias veces, por lo que se podrían haber introducido artefactos extraños, como un espacio aquí, un guión allí. La subcadena coincidirá con una sección del texto en el documento original del 99% o más. No coincido para ver desde qué documento se encuentra esta cadena, estoy tratando de encontrar el índice en el documento donde comienza la cadena.

Si la cadena fuera idéntica porque no se introdujo ningún error aleatorio, usaría document.index(substring) , sin embargo, esto falla si hay incluso una diferencia de caracteres.

Pensé que la diferencia se tendría en cuenta al eliminar todos los caracteres excepto az en la cadena y en la subcadena, comparar y luego usar el índice que generé al comprimir la cadena para traducir el índice en la cadena comprimida al índice en el documento real . Esto funcionó bien donde la diferencia era el espacio en blanco y la puntuación, pero tan pronto como una letra es diferente, falló.

El documento consta normalmente de unas pocas páginas a cien páginas, y la subcadena de unas pocas oraciones a unas pocas páginas.

Answer 1

Debería ver la implementación de StrikeAMatch detallada aquí: Un algoritmo de clasificación de similitud mejor para cadenas de longitud variable

En lugar de depender de algún tipo de distancia de cadena (es decir, la cantidad de cambios entre dos cadenas), esta analiza los patrones de pares de caracteres. Cuantos más pares de caracteres aparezcan en cada cadena, mejor será la coincidencia. Ha funcionado maravillosamente para nuestra aplicación, donde buscamos encabezados de longitud variable o mal escritos en un archivo de texto plano.

También hay una gema que combina StrikeAMatch (una implementación del coeficiente de Dice en bigramas a nivel de caracteres) y la distancia de Levenshtein para encontrar coincidencias: fuzzy_match

Answer 2

Depende de los artefactos que pueden terminar en la subcadena. En el caso más simple en el que no forman parte de [az] , puede usar parse la subcadena y luego usar Regexp#match en el documento:

document = ''Ulputat non nullandigna tortor dolessi illam sectem laor acipsus.''
substr = "tortor - dolessi _%&#   +illam"

re = Regexp.new(substr.split(/[^a-z]/i).select{|e| !e.empty?}.join(".*"))
md = document.match re
puts document[md.begin(0) ... md.end(0)]
# => tortor dolessi illam

(Aquí, como no establecemos ningún paréntesis en el Regexp, utilizamos el begin y el end en el primer elemento 0 (coincidencia completa) de MatchData .

Si solo está interesado en la posición de inicio, puede usar el operador =~ :

start_pos = document =~ re

Answer 3

No utilicé ninguno de ellos, pero encontré algunas bibliotecas simplemente haciendo una búsqueda de ''diff'' en rubygems.org . Todos ellos pueden ser instalados por gema. Es posible que desee probarlos. Yo mismo estoy interesado, por lo que si ya los conoce o si los prueba, sería útil que deje su comentario.

• diff
• diff-lcs
• differ
• difflcs
• pretty_diff
• diffy
• kronk
• khtmldiff
• gdiff
• ruby_diff
• tdiff
• diffrenderer
• diffplex
• dbdiff
• diff_dirs
• rsyncdiff
• wdiff
• diff4all
• davidtrogers-htmldiff
• edouard-htmldiff
• diff2xml
• dirdiff
• rrdiff
• nokogiri-diff
• pretty-diff
• easy_diff
• smartdiff

Answer 4

Una simple es fuzzy_match

require ''fuzzy_match''
FuzzyMatch.new([''seamus'', ''andy'', ''ben'']).find(''Shamus'') #=> seamus

Una más elaborada (aunque no lo dirías en este ejemplo) es levenshein , que calcula el número de diferencias.

require ''levenshtein'' 
Levenshtein.distance(''test'', ''test'')    # => 0
Levenshtein.distance(''test'', ''tent'')    # => 1

Answer 5

Usted podría intentar amatch. Está disponible como una gema de rubí y, aunque no he trabajado con lógica difusa durante mucho tiempo, parece tener lo que necesitas. La página de inicio de amatch es: http://flori.github.com/amatch/ .

Solo aburrido y jugando con la idea, a continuación se incluye un hack de una solución completamente no optimizado y no probado:

include ''amatch''

module FuzzyFinder
  def scanner( input )
    out = [] unless block_given?
    pos = 0
    input.scan(/(/w+)(/W*)/) do |word, white|
      startpos = pos
      pos = word.length + white.length
      if block_given?
        yield startpos, word
      else
        out << [startpos, word]
      end
    end
  end

  def find( text, doc )
    index = scanner(doc)
    sstr = text.gsub(//W/,'''')
    levenshtein = Amatch::Levensthtein.new(sstr)
    minlen = sstr.length
    maxndx = index.length
    possibles = []
    minscore = minlen*2
    index.each_with_index do |x, i|
      spos = x[0]
      str = x[1]
      si = i
      while (str.length < minlen)
        i += 1
        break unless i < maxndx
        str += index[i][1]
      end
      str = str.slice(0,minlen) if (str.length > minlen)
      score = levenshtein.search(str)
      if score < minscore
        possibles = [spos]
        minscore = score
      elsif score == minscore
        possibles << spos
      end
    end
    [minscore, possibles]
  end
end

¡Obviamente hay numerosas mejoras posibles y probablemente necesarias! Unos pocos de la parte superior:

1. Procese el documento una vez y almacene los resultados, posiblemente en una base de datos.
2. Determine una longitud de cadena utilizable para una comprobación inicial, procese primero en esa subcadena inicial antes de intentar hacer coincidir todo el fragmento.
3. Siguiendo con el anterior, precalcule los fragmentos iniciales de esa longitud.