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

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

17 голосов
/ 23 мая 2011

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

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

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

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

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

Ответы [ 5 ]

5 голосов
/ 23 мая 2011

Вы можете попробовать 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. Вслед за предыдущим предварительно рассчитать начальные фрагменты этой длины.
3 голосов
/ 29 марта 2015

Простым является 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
2 голосов
/ 22 августа 2013

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

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

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

1 голос
/ 23 мая 2011

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

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

...