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

我发现很多关于模糊匹配的链接,将一个字符串与另一个字符串进行比较,看到哪个获得最高的相似性分数.

我有一个非常长的字符串,它是一个文档和一个子字符串.子串来自原始文档,但已被转换好几次,所以可能会引入奇怪的文物,比如这里的空格,破折号.子字符串将匹配原始文档中的一部分文本99％以上.我不匹配,看看这个字符串是从哪个文档,我试图在文档中找到字符串开始的索引.

如果字符串是相同的,因为没有引入随机错误,我将使用document.index(substring),但是如果还有一个字符差异,则失败.

我认为通过删除字符串和子字符串中除az之外的所有字符进行比较,比较,然后使用压缩字符串时生成的索引,将压缩字符串中的索引转换为真实文档中的索引.这一点在差异是空白和标点符号的情况下运行良好,但一旦一个字母不同,它就失败了.

该文档通常是几页到一百页,从几个句子到几页的子字符串.

解决方法

你可以试试amatch.它可以作为一个红宝石宝石,虽然我没有使用模糊逻辑很长一段时间,它看起来有你需要的. amatch的主页是： http://flori.github.com/amatch/.

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

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

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

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

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

解决方法

猜你在找的Ruby相关文章