如何在Ruby中进行模糊子串匹配？
我找到了很多关于模糊匹配的链接，将一个字符串与另一个字符串进
我有一个非常长的字符串，它是一个文档和一个子字符串。 子字符串来自原始文档，但已被多次转换，因此可能引入了奇怪的工件，例如此处的空格，字符串。 子字符串将匹配原始文档中文本的一部分99％或更多。 我不匹配以查看此字符串是哪个文档，我试图在文档中找到字符串开始的索引。
如果字符串是相同的，因为没有引入随机错误，我会使用document.index(substring) ，但如果有一个字符差异，则会失败。
我认为通过删除字符串和子字符串中除az以外的所有字符来比较差异，然后使用压缩字符串时生成的索引将压缩字符串中的索引转换为真实文档中的索引。 这种情况很好用，其中差异是空格和标点符号，但只要一个字母不同就失败了。
该文档通常是几页到一百页，而子串从几个句子到几页。
你可以试试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
显然，可能有许多改进，可能是必要的！ 顶部的几个：
- 处理文档一次并将结果存储在数据库中。
- 确定初始检查的字符串的可用长度，在尝试匹配整个片段之前首先处理该初始子字符串。
- 跟进前一个，预先计算该长度的起始片段。
一个简单的就是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实现： 针对可变长度字符串的更好的相似性排序算法
这个人不是依赖某种字符串距离（即两个字符串之间的变化次数），而是查看字符对模式。 每个字符串中出现的字符对越多，匹配就越好。 它对我们的应用程序非常有效，我们在纯文本文件中搜索错误类型/可变长度标题。
还有一个gem结合了StrikeAMatch（ Dice系数在字符级别的双字母系统上的实现）和Levenshtein距离来寻找匹配： https ： //github.com/seamusabshere/fuzzy_match
它取决于最终可能在子字符串中的工件。 在更简单的情况下，它们不是[az]一部分，您可以使用解析子字符串，然后在文档上使用Regexp#match ：
document = 'Ulputat non nullandigna tortor dolessi illam sectem laor acipsus.' substr = "tortor - dolessi _%&# +illam" re = Regexp.new(substr.split(/[^az]/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安装。 你可能想尝试一下。 我自己很感兴趣，所以如果你已经知道这些或者你试过它们，那么如果你留下你的评论会很有帮助。
- DIFF
- DIFF-LCS
- 不同
- difflcs
- pretty_diff
- diffy
- kronk
- khtmldiff
- GDIFF
- ruby_diff
- TDIFF
- diffrenderer
- diffplex
- dbdiff
- diff_dirs
- rsyncdiff
- wdiff
- diff4all
- davidtrogers-htmldiff
- 爱德华- htmldiff
- diff2xml
- dirdiff
- rrdiff
- 引入nokogiri-DIFF
- 漂亮-DIFF
- easy_diff
- smartdiff