Как я могу выполнить нечеткое подстроку в Ruby?

Я нашел много ссылок о нечетком сопоставлении, сравнивая одну строку с другой и видя, что получает самый высокий балл подобия.

У меня есть очень длинная строка, которая является документом и подстрокой. Подстрока была взята из оригинального документа, но была преобразована несколько раз, поэтому могли появиться странные артефакты, такие как пространство здесь, тире там. Подстрока будет соответствовать разделу текста в оригинальном документе 99% или более. Я не согласен, чтобы увидеть, из какого документа эта строка, я пытаюсь найти индекс в документе, где начинается строка.

Если строка была идентичной, потому что случайная ошибка не была введена, я использовал бы document.index(substring), однако это не удается, если есть даже одна разница символов.

Я думал, что разница будет учтена, удалив все символы, кроме az, как в строке, так и подстроке, сравните, а затем используйте индекс I, сгенерированный при сжатии строки, чтобы преобразовать индекс в сжатой строке в индекс в реальный документ. Это работало хорошо, где разница была пробелом и пунктуацией, но как только одна буква отличается, она не удалась.

Документ, как правило, составляет от нескольких страниц до ста страниц, а подстрока - от нескольких предложений до нескольких страниц.

Ответы

Ответ 1

Вы можете попробовать 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

Очевидно, что возможны многочисленные улучшения и, возможно, необходимы! Немного сверху:

Обработать документ один раз и сохранить результаты, возможно, в базе данных.
Определить используемую длину строки для начальной проверки, процесс против первой начальной подстроки прежде чем пытаться сопоставить весь фрагмент.
Следуя предыдущему, предварительно рассчитать начальные фрагменты эта длина.

Ответ 2

Вы должны посмотреть на реализацию StrikeAMatch, описанную здесь: Лучший алгоритм ранжирования сходства для строк переменной длины

Вместо того, чтобы полагаться на какое-то строковое расстояние (т.е. количество изменений между двумя строками), это смотрит на пары пар символов. Чем больше пар символов встречается в каждой строке, тем лучше совпадение. Он отлично работает для нашего приложения, где мы ищем заголовки с неправильной/переменной длиной в текстовом файле.

Также есть жемчужина, которая сочетает в себе StrikeAMatch (реализация Коэффициент кости на персональных биграммах) и расстояние Левенштейна для поиска совпадений: https://github.com/seamusabshere/fuzzy_match

Ответ 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

Ответ 4

Это зависит от артефактов, которые могут оказаться в подстроке. В более простом случае, когда они не являются частью [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, мы используем begin и end в первом (полном) элементе 0 MatchData.

Если вас интересует только начальная позиция, вы можете использовать оператор =~:

start_pos = document =~ re

Ответ 5

Я не использовал ни одного из них, но я нашел несколько библиотек, просто выполнив поиск "diff" в rubygems.org. Все они могут быть установлены жемчужиной. Возможно, вы захотите попробовать их. Я сам заинтересован, поэтому, если вы уже знаете об этом или если вы попробуете их, было бы полезно, если вы оставите свой комментарий.