Как я могу сделать нечеткое сопоставление подстроки в Ruby?
string fuzzy-search (4)
Вы должны посмотреть на реализацию StrikeAMatch, подробно описанную здесь: лучший алгоритм ранжирования сходства для строк переменной длины
Вместо того, чтобы полагаться на какое-то расстояние между строками (то есть количество изменений между двумя строками), эта модель рассматривает шаблоны пар символов. Чем больше пар символов встречается в каждой строке, тем лучше совпадение. Это прекрасно работает для нашего приложения, где мы ищем опечатки / заголовки переменной длины в текстовом файле.
Есть также драгоценный камень, который объединяет StrikeAMatch (реализацию коэффициента Кости на биграммах на уровне персонажа) и расстояние Левенштейна для поиска совпадений: fuzzy_match
Я нашел много ссылок о нечетком сопоставлении, сравнивая одну строку с другой и видя, какой из них получает наивысшую оценку сходства.
У меня есть одна очень длинная строка, которая является документом, и подстрока. Подстрока взята из исходного документа, но несколько раз конвертировалась, поэтому могли появиться странные артефакты, такие как пробел здесь, тире там. Подстрока будет соответствовать фрагменту текста в исходном документе на 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
Очевидно, что существует множество возможных улучшений и, возможно, необходимых! Несколько от вершины:
- Обработайте документ один раз и сохраните результаты, возможно, в базе данных.
- Определите полезную длину строки для начальной проверки, обработайте сначала эту исходную подстроку, прежде чем пытаться сопоставить весь фрагмент.
- Вслед за предыдущим, предварительно рассчитать исходные фрагменты этой длины.
Это зависит от артефактов, которые могут оказаться в подстроке. В более простом случае, когда они не являются частью [az]
вы можете использовать синтаксический анализ подстроки, а затем использовать 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
первого (полного соответствия) элемента 0
MatchData
.
Если вас интересует только начальная позиция, вы можете использовать оператор =~
:
start_pos = document =~ re
Я не использовал ни одну из них, но я нашел некоторые библиотеки, просто выполнив поиск 'diff' на rubygems.org
. Все они могут быть установлены Gem. Вы можете попробовать их. Я сам заинтересован, поэтому, если вы уже знаете это или попробуете, было бы полезно, если вы оставите свой комментарий.