Как изменить алгоритм Дамерау-Левенштейна, чтобы он также включал начальный индекс и конечный индекс большей подстроки? - PullRequest
Новая
       10

Как изменить алгоритм Дамерау-Левенштейна, чтобы он также включал начальный индекс и конечный индекс большей подстроки?

1 голос
/ 20 февраля 2012

Вот мой код: 

#http://en.wikipedia.org/wiki/Damerau%E2%80%93Levenshtein_distance
# used for fuzzy matching of two strings
# for indexing, seq2 must be the parent string
  def dameraulevenshtein(seq1, seq2)
      oneago = nil
      min = 100000000000 #index
      max = 0 #index
      thisrow = (1..seq2.size).to_a + [0]
      seq1.size.times do |x|
          twoago, oneago, thisrow = oneago, thisrow, [0] * seq2.size + [x + 1]
          seq2.size.times do |y|
              delcost = oneago[y] + 1
              addcost = thisrow[y - 1] + 1
              subcost = oneago[y - 1] + ((seq1[x] != seq2[y]) ? 1 : 0)
              thisrow[y] = [delcost, addcost, subcost].min
              if (x > 0 and y > 0 and seq1[x] == seq2[y-1] and seq1[x-1] == seq2[y] and seq1[x] != seq2[y])
                  thisrow[y] = [thisrow[y], twoago[y-2] + 1].min
              end
          end
      end
      return thisrow[seq2.size - 1], min, max
  end

Должно быть какое-то время, чтобы получить начальный и конечный индекс подстроки seq1 с родительской строкой seq2, верно?

Я не совсем уверен, как работает этот алгоритм, даже после прочтения вики-статьи о нем. Я имею в виду, я понимаю объяснение наивысшего уровня, так как оно находит вставку, удаление и разницу транспонирования (строки во втором цикле) ... но кроме этого. Я немного растерялся.

Вот пример того, что я хотел бы сделать с этим (^): 

substring = "hello there"
search_string = "uh,\n\thello\n\t there"

индексы должны быть: 

  start: 5
  end:   18 (last char of string)

В идеале строка search_string никогда не будет изменена. Но, я думаю, я мог бы убрать все пробельные символы (так как их всего .. 3? \ N \ r и \ t) сохранить индексы каждого пробельного символа, получить индексы моей подстроки, а затем повторно добавьте символы пробела, убедившись, что компенсировали индексы подстроки, поскольку я сместил их с символами пробела, которые изначально были там. - но если бы все это можно было сделать одним и тем же методом, это было бы удивительно, поскольку алгоритм уже O (n ^ 2) .. = (

В какой-то момент я бы хотел, чтобы только символы пробела разделяли подстроку (s1) ... но по одной вещи за раз

1 Ответ

1 голос
/ 20 февраля 2012

Я не думаю, что этот алгоритм является правильным выбором для того, что вы хотите сделать.Алгоритм просто вычисляет расстояние между двумя строками с точки зрения количества модификаций, которые необходимо выполнить, чтобы превратить одну строку в другую.Если мы переименуем вашу функцию в dlmatch для краткости и вернем только расстояние, то у нас будет: 

dlmatch("hello there", "uh, \n\thello\n\t there"
=> 7

, означающее, что вы можете преобразовать одну строку в другую за 7 шагов (фактически, удалив семь символов из второго).Проблема в том, что 7 шагов - это довольно большая разница: 

dlmatch("hello there", "panda here"
=> 6

Это фактически означает, что слова "привет там" и "здесь панда" ближе, чем в первом примере.

Еслито, что вы пытаетесь сделать, это «найти подстроку, которая в основном соответствует», я думаю, что вы застряли с алгоритмом O (n ^ 3), когда вы передаете первую строку в ряд подстрок второй строки, а затем выбираетеподстрока, которая предоставляет вам наиболее близкое совпадение.

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

...