17

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

我有一个很长的字符串，它是一个文档和一个子字符串。子字符串来自原始文档，但经过多次转换，因此可能引入了奇怪的伪影，例如这里的空格，那里的破折号。子字符串将匹配原始文档中的一段文本 99% 或更多。我不匹配以查看该字符串来自哪个文档，我正在尝试在文档中查找该字符串开始的索引。

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

我认为差异可以通过删除字符串和子字符串中除 az 之外的所有字符来解决，比较，然后使用我在压缩字符串时生成的索引将压缩字符串中的索引转换为真实文档中的索引. 这在空格和标点符号不同的情况下效果很好，但只要一个字母不同，它就会失败。

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

4

5 回答 5

5

你可以试试amatch。它可以作为 ruby​​ gem 使用，虽然我很长时间没有使用模糊逻辑，但它看起来有你需要的东西。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. 继上一个之后，预先计算该长度的起始片段。
于 2011-05-23T08:44:17.147 回答
3

一个简单的就是fuzzy_match

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

一个更详细的（虽然你不会从这个例子中说出来）是levenshein，它计算差异的数量。

require 'levenshtein' 
Levenshtein.distance('test', 'test')    # => 0
Levenshtein.distance('test', 'tent')    # => 1
于 2015-03-29T14:40:26.317 回答
2

您应该查看此处详细介绍的 StrikeAMatch 实现： A better similarity ranking algorithm for variable length strings

而不是依赖于某种字符串距离（即两个字符串之间的变化次数），这一点着眼于字符对模式。每个字符串中出现的字符对越多，匹配就越好。它对我们的应用程序非常有效，我们在纯文本文件中搜索输入错误/可变长度的标题。

还有一个 gem 结合了 StrikeAMatch（Dice在字符级二元组上的系数的实现）和 Levenshtein 距离来查找匹配项：https ://github.com/seamusabshere/fuzzy_match

于 2013-08-22T10:31:33.173 回答
1

这取决于最终可能出现在子字符串中的工件。在它们不属于您的更简单的情况下，[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

（这里，由于我们没有在正则表达式中设置任何括号，begin我们end在.0MatchData

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

start_pos = document =~ re
于 2011-05-23T07:07:00.280 回答
-2

我没有使用它们，但我只是通过在rubygems.org. 所有这些都可以通过 gem 安装。您可能想尝试一下。我自己很感兴趣，所以如果你已经知道这些或者如果你尝试过，如果你留下你的评论会很有帮助。

于 2011-05-23T07:53:29.197 回答