如何在Ruby中进行模糊子串匹配？

只是无聊和混乱的想法,一个完全未优化和未经测试的黑客的解决方案如下：

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

显然有很多改进可能,可能是必要的！几个顶部：

>一次处理文档并存储结果,可能在一个数据库.>确定字符串的可用长度进行初步检查,处理最初的子串在尝试匹配整个之前分段.>跟随上一个,预先计算起始片段那个长度.