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

我发现了很多关于模糊匹配的链接，将一个字符串与另一个字符串进行比较，看看哪个字符串的相似度得分最高。

我有一个很长的字符串（一个文档）和一个子字符串。子字符串来自原始文档，但已被转换多次，因此可能会引入奇怪的工件，例如这里有一个空格，那里有一个破折号。子字符串将与原始文档中的文本部分匹配 99% 或更多。我无法匹配该字符串来自哪个文档，我试图在该字符串开始的文档中找到索引。

如果字符串相同，因为没有引入随机错误，我会使用document.index(substring)，但是如果只有一个字符差异，则此操作会失败。

我认为可以通过删除字符串和子字符串中除 a-z 之外的所有字符进行比较，然后使用压缩字符串时生成的索引将压缩字符串中的索引转换为真实文档中的索引来解决差异。当差异是空格和标点符号时，这种方法效果很好，但一旦有一个字母不同，它就会失败。

文档通常是几页到一百页，子串从几句话到几页。

你可以尝试一下匹配。它可以作为 ruby​​ gem 提供，虽然我已经很长时间没有使用模糊逻辑了，但它看起来有你需要的东西。 amatch的主页是：https://github.com/flori/amatch https://github.com/flori/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. 继上一篇之后， 预先计算起始片段 那个长度。