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

| 我发现了许多有关模糊匹配的链接，将一个字符串与另一个字符串进行比较，看看哪个字符串获得最高的相似性得分。我有一个很长的字符串，它是一个文档和一个子字符串。子字符串来自原始文档，但是已经转换了几次，因此可能会引入怪异的工件，例如此处的空格，此处的破折号。子字符串将匹配原始文档中文本的99％或更高的部分。我不匹配此字符串是从哪个文档开始的，我试图在文档中从该字符串开始的地方找到索引。如果由于未引入随机错误而导致字符串相同，则我将使用document.index(substring)，但是即使有一个字符差异，此操作也会失败。我认为，可以通过删除字符串和子字符串中除az以外的所有字符，进行比较，然后使用压缩字符串时生成的索引将压缩后的字符串中的索引转换为实际文档中的索引来解决差异。这在空白和标点符号之间的区别很不错，但是一旦一个字母不同，它就会失败。该文档通常是几页到一百页，子字符串从几句话到几页。

已邀请:

5 个回复

缮淳彼誊

您可以尝试搭配。它可以作为红宝石使用，尽管我已经很长时间没有使用模糊逻辑了，但是它看起来可以满足您的需求。 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

显然，可能有很多改进，而且可能有必要！顶一下：一次处理文档并存储结果，可能在数据库中。确定可用的字符串长度进行初步检查首先针对该初始子字符串在尝试匹配整个之前分段。跟进前一个，预先计算的起始片段那个长度。

寿柬窟年

一个简单的就是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

纤洞需匪

您应查看此处详细介绍的StrikeAMatch实现：可变长度字符串的一种更好的相似度排序算法而不是依赖某种字符串距离（即两个字符串之间的更改数量），该代码着眼于字符对模式。每个字符串中出现的字符对越多，匹配越好。它对于我们的应用程序非常有效，我们在纯文本文件中搜索错误键入/可变长度的标题。还有一个结合了StrikeAMatch（在字符级双字母上执行Dice系数的实现）和Levenshtein距离以查找匹配项的宝石：https://github.com/seamusabshere/fuzzy_match

逝媳蘑贩茄

这取决于可能出现在子字符串中的工件。如果它们不是[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

（这里，由于我们未在Regexp中设置任何括号，因此我们在MatchData的第一个（完全匹配）元素0上使用begin和end。如果仅对开始位置感兴趣，可以使用=~运算符：

start_pos = document =~ re

茬贺努充尽

我什么都没用，但我只是通过在rubygems.org中搜索\'diff \'而发现了一些库。所有这些都可以通过gem安装。您可能想尝试一下。我本人对此很感兴趣，因此，如果您已经知道这些或尝试使用它们，则留下您的评论会有所帮助。差异差异不同衍射 pretty_diff 困难的克朗 khtmldiff 格迪夫 ruby_diff 迪夫扩散器衍射 dbdiff diff_dirs rsyncdiff 威迪夫 diff4all davidtrogers-htmldiff edouard-htmldiff diff2xml 迪迪夫罗迪夫 Nokogiri-diff 漂亮差异 easy_diff smartdiff

要回复问题请先登录或注册

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

5 个回复

发起人

ruby

string

fuzzy_search

问题状态

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

与内容相关的链接

5 个回复

发起人

ruby

string

fuzzy_search

问题状态