烫伤：两两比较字符串？

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))