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




string fuzzy-search (4)

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

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

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

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

Документ обычно состоит из нескольких страниц до ста страниц и подстроки от нескольких предложений до нескольких страниц.

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

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

Есть также драгоценный камень, который объединяет StrikeAMatch (реализацию коэффициента Кости на биграммах на уровне персонажа) и расстояние Левенштейна для поиска совпадений: fuzzy_match

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

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

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

Это зависит от артефактов, которые могут оказаться в подстроке. В более простом случае, когда они не являются частью [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. Вы можете попробовать их. Я сам заинтересован, поэтому, если вы уже знаете это или попробуете, было бы полезно, если вы оставите свой комментарий.




ruby   string   fuzzy-search  


fuzzy-search