1

Scalding では、次のことを行う必要があります。

  1. 文字列フィールドを最初の 3 文字でグループ化する
  2. edit-distanceメトリックを使用して、すべてのグループのすべてのペアの文字列を比較します ( http://en.wikipedia.org/wiki/Edit_distance )
  3. レコードがある CSV ファイルに結果を書き込みますstring; string; distance

文字列をグループ化するには、次の例のように mapandを使用します。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)']

aaaさて、この例では、このリストのキーを持つ文字列の編集距離を計算する必要があります。

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

このリストの「bbb」キーを持つすべての文字列の次:

List(bbbddde, bbbcccc, bbbaaa, bbbb)

等

独自の関数に置き換える必要があるすべてのグループのすべての文字列間の編集距離を計算するにはtoList、どうすればよいですか? また、関数の結果を CSV ファイルに書き込むにはどうすればよいですか?

ありがとう！

アップデート

Listスカルディングからの入手方法はPipe？

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

1 に答える 1

1

編集距離は、ウィキペディアで説明されているように計算できます。

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

于 2014-07-15T16:30:58.887 に答える