8

レーベンシュタイン距離式のCoffeeScript実装、別名EditDistanceを作成または検索しようとしています。これが私がこれまでに持っているものです、どんな助けでも大いに感謝されるでしょう。

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：Trevorが指摘したエラーを修正しました。上記の現在のコードには、これらの変更が含まれています

更新：私が尋ねている質問は、CoffeeScriptでLevenshteinをどのように実行するかです。

これが、私が達成しようとしていることを理解するのに役立つレーベンシュタイン距離アルゴリズムの「ステップ」です。

手順
1nを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]を次の最小値に等しく設定します。プラス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

4

1 に答える 1

5

このページ（あなたが言及したリソースからリンクされている）は、レーベンシュタイン距離アルゴリズムの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]

軽いテストには耐えられるようですが、何か問題があれば教えてください。

于 2011-07-10T00:47:16.527 に答える