scalaテキスト編集距離アルゴリズム実装

481 ワード

距離の定義を編集:
編集距離は、Levenshtein距離とも呼ばれ、2つの文字列の間で、1つから別の文字に変換するのに必要な最小限の編集操作回数を指します.ライセンスの編集操作には、1つの文字を別の文字に置き換え、1つの文字を挿入し、1つの文字を削除することが含まれます.例えばeebaをabac:1に変換する.eba(最初のeを削除する)2.aba(残りのeをaに置き換える)3.abac(最後にcを挿入する)だからeebaとabacの編集距離は3ロシアの科学者Vladimir Levenshteinが1965年にこの概念を提出したことだ.
コード実装:
def editDist(s1:String, s2:String):Int ={
    val s1_length = s1.length+1
    val s2_length = s2.length+1
    val matrix=Array.ofDim[Int](s1_length,s2_length)
    for(i