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

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

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 равным длине s. Установите 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 Установить ячейку 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


coffeescript edit-distance levenshtein-distance
person joe norton    schedule 09.07.2011    source источник
comment
Как мы делаем расстояние Левенштейна в CoffeeScript?   -  person joe norton    schedule 10.07.2011
comment
Три большие проблемы с вашим текущим кодом: 1) previouis_row — это опечатка, и 2) previous_row[-1] не будет работать, потому что CoffeeScript не использует отрицательные индексы (используйте previous_row[previous_row.length-1]), и 3) + (c1 != c2) добавляет либо true, либо false. Я опубликую более полный ответ, но вы должны сразу же исправить эти три вещи.   -  person Trevor Burnham    schedule 10.07.2011
comment
Кроме того, синтаксис CoffeeScript for...in заменяется value, index, а не наоборот. Таким образом, ваши петли должны быть for c1, i in s1 и for c2, j in s2.   -  person Trevor Burnham    schedule 10.07.2011
comment
Большое спасибо, Тревор. Я хочу, чтобы вы знали, что я с нетерпением жду печатной копии вашей будущей книги (не торопитесь!).   -  person joe norton    schedule 10.07.2011

Ответы (1)


arrow_upward
5
arrow_downward

Эта страница (ссылка на указанный вами ресурс) предлагает реализацию алгоритма расстояния Левенштейна на 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]

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

person Trevor Burnham    schedule 10.07.2011
comment
Тревор, это решение прекрасно работает. Я протестировал его на реализациях JavaScript, и он получил те же результаты. У меня есть один вопрос: почему мы используем переменные c1 и c2? Мне кажется, что он должен использовать переменные n и m, но это не работает. Почему это? - person joe norton; 11.07.2011
comment
@joe c1 и c2 — это фактические символы из строки. Если они различаются, то cost равно 1; в противном случае cost равно 0. - person Trevor Burnham; 11.07.2011
comment
Не CS, но вызываемый из него: 11958496" title="сортировать массив по расстоянию Левенштейна с лучшей производительностью в javascript"> stackoverflow.com/questions/11919065/ - person James Westgate; 30.11.2016