我发现很多关于模糊匹配的链接,将一个字符串与另一个字符串进行比较,看到哪个获得最高的相似性分数.
我有一个非常长的字符串,它是一个文档和一个子字符串.子串来自原始文档,但已被转换好几次,所以可能会引入奇怪的文物,比如这里的空格,破折号.子字符串将匹配原始文档中的一部分文本99％以上.我不匹配,看看这个字符串是从哪个文档,我试图在文档中找到字符串开始的索引.
如果字符串是相同的,因为没有引入随机错误,我将使用document.index(substring),但是如果还有一个字符差异,则失败.
我认为通过删除字符串和子字符串中除az之外的所有字符进行比较,比较,然后使用压缩字符串时生成的索引,将压缩字符串中的索引转换为真实文档中的索引.这一点在差异是空白和标点符号的情况下运行良好,但一旦一个字母不同,它就失败了.
该文档通常是几页到一百页,从几个句子到几页的子字符串.
解决方法
你可以试试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
显然有很多改进可能,可能是必要的！几个顶部：
>一次处理文档并存储结果,可能在一个数据库.>确定字符串的可用长度进行初步检查,处理最初的子串在尝试匹配整个之前分段.>跟随上一个,预先计算起始片段那个长度.