燙傷：兩兩比較字符串？

Question

用滾燙的，我需要：

1. 由前3個字符
2. 比較使用edit-distance指標（http://en.wikipedia.org/wiki/Edit_distance）
3. 寫在CSV文件會導致在每一個組中的所有對字符串，其中記錄string; string; distance組字符串字段

要我使用map組字符串和groupBy如下面的例子：

import cascading.tuple.Fields 
import com.twitter.scalding._ 

class Scan(args: Args) extends Job(args) { 
    val output = TextLine("tmp/out.txt") 

    val wordsList = List(
    ("aaaa"), 
    ("aaabb"), 
    ("aabbcc"), 
    ("aaabccdd"), 
    ("aaabbccdde"), 
    ("aaabbddd"), 
    ("bbbb"), 
    ("bbbaaa"), 
    ("bbaaabb"), 
    ("bbbcccc"), 
    ("bbbddde"), 
    ("ccccc"), 
    ("cccaaa"), 
    ("ccccaabbb"), 
    ("ccbbbddd"), 
    ("cdddeee") 
    ) 

    val orderedPipe = 
    IterableSource[(String)](wordsList, ('word)) 
     .map('word -> 'key){word:String => word.take(3)} 
    .groupBy('key) {_.toList[String]('word -> 'x) } 
     .debug 
     .write(output) 
} 

結果我得到：現在

['aaa', 'List(aaabbddd, aaabbccdde, aaabccdd, aaabb, aaaa)'] 
['aab', 'List(aabbcc)'] 
['bba', 'List(bbaaabb)'] 
['bbb', 'List(bbbddde, bbbcccc, bbbaaa, bbbb)'] 
['ccb', 'List(ccbbbddd)'] 
['ccc', 'List(ccccaabbb, cccaaa, ccccc)'] 
['cdd', 'List(cdddeee)'] 

，在這個例子中，我需要comute字符串編輯距離，在此列表aaa鍵：

List(aaabbddd, aaabbccdde, aaabccdd, aaabb, aaaa) 

下一步所有在此列表中帶有'bbb'鍵的字符串：

List(bbbddde, bbbcccc, bbbaaa, bbbb) 

等

要計算每個組中所有字符串之間的編輯距離，我需要用我自己的函數替換toList，我該怎麼做？還有我該如何將我的功能結果寫入CSV文件？

謝謝！

更新

如何燙傷Pipe得到List？

toList剛剛返回另一個Pipe，所以我不能使用它：

val orderedPipe = 
    IterableSource[(String)](wordsList, ('word)) 
     .map('word -> 'key){word:String => word.take(3)} 
     .groupBy('key) {_.toList[String]('word -> 'x) } 
     .combinations(2) //---ERROR! Pipe has no such method! 
     .debug 
     .write(output) 

Answer 1

可以在wikipedia描述來計算的編輯距離：

def editDistance(a: String, b: String): Int = { 

    import scala.math.min 

    def min3(x: Int, y: Int, z: Int) = min(min(x, y), z) 

    val (m, n) = (a.length, b.length) 

    val matrix = Array.fill(m + 1, n + 1)(0) 

    for (i <- 0 to m; j <- 0 to n) { 

     matrix(i)(j) = if (i == 0) j 
         else if (j == 0) i 
         else if (a(i-1) == b(j-1)) matrix(i-1)(j-1) 
         else min3(
           matrix(i - 1)(j) + 1, 
           matrix(i)(j-1) + 1, 
           matrix(i - 1)(j - 1) + 1) 
    } 

    matrix(m)(n) 
} 

爲了找到配對編輯距離列表中的元素：

def editDistances(list: List[String]) = { 

    list.combinations(2).toList.map(x => (x(0), x(1), editDistance(x(0), x(1)))) 
} 

使用這GROUPBY：

val orderedPipe = 
     IterableSource[(String)](wordsList, ('word)) 
     .map('word -> 'key){word:String => word.take(3)} 
     .groupBy('key) {_.mapList[String, List[(String, String, Int)]]('word -> 'x)(editDistances)} 
     .debug 
     .write(output)  

至於寫入csv格式而言，你可以簡單地使用com.twitter.scalding.Csv類。

write(Csv(outputFile))