Формула расстояния Левенштейна в CoffeeScript? - PullRequest
Новая
       35

Формула расстояния Левенштейна в CoffeeScript?

8 голосов
/ 10 июля 2011

Я пытаюсь создать или найти реализацию CoffeeScript для формулы расстояния Левенштейна, иначе редактирующей расстояние.Вот то, что я имею до сих пор, любая помощь вообще будет высоко ценится. 

levenshtein = (s1,s2) ->
    n = s1.length
    m = s2.length
    if n < m
        return levenshtein(s2, s1) 
    if not s1 
        return s2.length
    previous_row = [s2.length + 1]
    for c1, i in s1
        current_row = [i + 1]
        for c2, j in s2
            insertions = previous_row[j + 1] + 1
            deletions = current_row[j] + 1
            substitutions = previous_row[j] # is this unnescessary?-> (c1 != c2)
            current_row.push(Math.min(insertions,deletions,substitutions))
        previous_row = current_row
    return previous_row[previous_row.length-1]
#End Levenshetein Function

Кстати: я знаю, что этот код является неправильным на многих уровнях, я рад получить любую и всю конструктивную критику.Просто хочу улучшить и выяснить эту формулу!

CodeEdit1: исправлены ошибки, на которые указал Тревор, текущий код, приведенный выше, включает эти изменения

Обновление: вопрос, который я задаю, - как сделатьмы делаем Левенштейна в CoffeeScript?

Вот «шаги» для алгоритма расстояния Левенштейна, чтобы помочь вам увидеть то, что я пытаюсь выполнить.

Шаги 1
Установите n в качестведлина с.Установите m, чтобы быть длиной t.Если n = 0, верните m и выйдите.Если m = 0, вернуть n и выйти.Построить матрицу, содержащую 0..m строк и 0..n столбцов.

2
Инициализировать первую строку в 0..n.Инициализируйте первый столбец как 0..m.

3 Изучите каждый символ s (i от 1 до n).

4 Изучите каждый символ t (j от 1 до m).

5 Если s [i] равно t [j], стоимость равна 0. Если s [i] не равна t [j], стоимость равна 1.

6 Setячейка d [i, j] матрицы равна минимуму: a.Ячейка сразу выше плюс 1: d [i-1, j] + 1. b.Клетка слева направо плюс 1: d [i, j-1] + 1. c.Ячейка по диагонали выше и слева плюс стоимость: d [i-1, j-1] + стоимость.

7 После завершения шагов итерации (3, 4, 5, 6) расстояниенаходится в ячейке d [n, m].

источник: http://www.merriampark.com/ld.htm

1 Ответ

5 голосов
/ 10 июля 2011

На этой странице (ссылка на которую вы упомянули) предлагает реализацию алгоритма расстояния Левенштейна на JavaScript. Исходя из того, что вы написали, и кода, вот моя версия CoffeeScript: 

LD = (s, t) ->
  n = s.length
  m = t.length
  return m if n is 0
  return n if m is 0

  d       = []
  d[i]    = [] for i in [0..n]
  d[i][0] = i  for i in [0..n]
  d[0][j] = j  for j in [0..m]

  for c1, i in s
    for c2, j in t
      cost = if c1 is c2 then 0 else 1
      d[i+1][j+1] = Math.min d[i][j+1]+1, d[i+1][j]+1, d[i][j] + cost

  d[n][m]

Кажется, что это выдерживает легкое тестирование, но дайте мне знать, если есть какие-либо проблемы.

...