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

Question

我找到了很多关于模糊匹配的链接,将一个字符串与另一个字符串进

我有一个非常长的字符串,它是一个文档和一个子字符串.子字符串来自原始文档,但已被多次转换,因此可能引入了奇怪的工件,例如此处的空格,字符串.子字符串将匹配原始文档中文本的一部分99%或更多.我不匹配以查看此字符串是哪个文档,我试图在文档中找到字符串开始的索引.

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

我认为通过删除除字符串和子字符串中的az之外的所有字符来比较差异,然后使用压缩字符串时生成的索引将压缩字符串中的索引转换为真实文档中的索引.这种情况很好用,其中差异是空格和标点符号,但只要一个字母不同就失败了.

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

Answer 1

你可以试试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

显然,可能有许多改进,可能是必要的!一些顶部:

1. 处理文档一次并将结果存储在数据库中.
2. 确定初始检查的字符串的可用长度,在尝试匹配整个片段之前首先处理该初始子字符串.
3. 跟进之前的那个长度的预先计算的起始片段.

Answer 2

这取决于可能出现在子字符串中的工件。在更简单的情况下，它们不属于[a-z]您可以使用解析子字符串，然后Regexp#match在文档上使用：

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

（这里，由于我们没有在正则表达式中设置任何括号，因此我们在 的第一个（完全匹配）元素上使用beginand 。end0MatchData

如果您只对起始位置感兴趣，可以使用=~运算符：

start_pos = document =~ re