2012-11-10 82 views
3

similar_text在試圖重寫PHP的similar_text算法我已經嘗試了幾種不同的方法。所有這些都取得了中等成功但最終失敗重寫PHP在斯卡拉

第一次嘗試:我試圖剛剛從PHP源代碼重寫它。 C對指針的優雅使用使得在Scala中看起來不可能實現的同樣精確的實現變得乾淨利落。

第二次嘗試:我試圖從Java功能有人張貼在PHP similar_text() in java改寫它。不幸的是,這個函數在Java中不起作用,所以不要將它移植到Scala。

三(電流)的嘗試:我目前正在試圖在此JavaScript實現轉化爲斯卡拉:http://phpjs.org/functions/similar_text/。我之前在JavaScript中使用過它,它似乎正常工作。我的翻譯(下)到斯卡拉不能正常工作。它可以讓你在1或2個相似度指標內,但它通常不是100%的PHP相應結果。

def similartext(first:String,second:String) : Int = { 
    if (first == null || second == null) { 
    0 
    } 

    var pos1:Int = 0 
    var pos2:Int = 0 
    var max:Int = 0 
    var sum:Int = 0 
    var l:Int = 0 

    val firstLength:Int = first.length 
    val secondLength:Int = second.length 

    for (p <- 0 until firstLength) { 
    for (q <- 0 until secondLength) { 
     while(p+l < firstLength && q+l < secondLength && (first.charAt(p+l) == second.charAt(q+l))) { 
     if (l > max) { 
      println("[" + p + "," + q + "," + l + "]" + first.charAt(p+l) + " | " + second.charAt(q+l)) 
      max = l 
      pos1 = p 
      pos2 = q 
      } 
     l += 1 
     } 
    } 
    } 

    sum = max; 

    if (sum > 0) { 
    if (pos1 > 0 && pos2 > 0) { 
     sum += similartext(first.substring(0, pos2), second.substring(0, pos2)) 
    } 

    if ((pos1 + max < firstLength) && (pos2 + max < secondLength)) { 
     sum += similartext(first.substring(pos1 + max, (pos1 + max) + (firstLength - pos1 - max)), second.substring(pos2 + max, (pos2 + max) + (secondLength - pos2 - max))) 
    } 
    } 

    sum; 
} 

測試:

(Scala)val st = similartext("apple","aple") Yields 3 
(PHP)$similar = similar_text("apple","aple"); Yields 4 

(Scala)val st = similartext("starbucks","stharducks") Yields 8 
(PHP)$similar = similar_text("starbucks","stharducks"); Yields 8 

(Scala)val st = similartext("hello earth!","hello world!") Yields 10 
(PHP)$similar = similar_text("hello earth!","hello world!"); Yields 8 

有沒有人有什麼錯誤這裏有什麼想法?

回答

5

這裏有一個提示:在JavaScript版本,尤其是最後一個行的字符線28非常密切關注。這就是你的實現不同的地方。 (你也不要重置l爲每對指數爲零,但是這不是最重要的問題。)

這裏有一個var不含斯卡拉版,順便說一句:

def similarText(x: String, y: String): Int = { 
    val indices = for { 
    (s, p) <- x.tails.zipWithIndex 
    (t, q) <- y.tails.zipWithIndex 
    l = ((s zip t) takeWhile Function.tupled(_ == _)).size 
    } yield (p, q, l) 
    val (pos1, pos2, max) = indices.maxBy(_._3) 

    if (max == 0) max else max + 
    similarText(x take pos1, y take pos2) + 
    similarText(x drop (pos1 + max), y drop (pos2 + max)) 
} 

這是相當不錯的 - 我相信你可以很容易地使它更加簡潔和高效。

並且額外的信用:JavaScript版本中存在一個錯誤 - 例如"aabcd""abcabcd",結果將不會與PHP(或我的)相同。

+0

太謝謝你了。這不僅指出了該方法中的一個(兩個)明顯的缺陷,還爲我在Scala上分析和改進提供了一些很好的代碼。大約兩天前我剛開始使用Scala,所以這是一個巨大的幫助。附:當我接觸到它時,我會再次查看JS代碼並找出你正在談論的錯誤。我相信這與跳過第一個字符比較有關,但這只是我的頭頂而沒有再次審查。 – Commander

+0

JavaScript錯誤實際上比這更無聊!我不願讓你浪費任何時間尋找它,因爲它只是一個錯字,所以讓我知道你是否希望我添加一個更直接的答案。 –