スカラ文字列の類似度

Question

文字列間の類似度を計算し、すべての一意の文字列を与えるScalaコードがあります。

val filtered = z.reverse.foldLeft((List.empty[String],z.reverse)) { 
    case ((acc, zt), zz) => 
     if (zt.tail.exists(tt => similarity(tt, zz) < threshold)) acc 
     else zz :: acc, zt.tail 
    }._1 

私はここで何が起こっているかを説明してみましょう：

これは空の文字列（結果を蓄積する）と（の逆）から開始し、逆に入力データに対する倍数を使用しています残りの入力データ（これと比較する - 「z-tail」の場合はztというラベルが付けられています）。

倍そしてちょうど既存の一致がある場合

（それ自体または任意の以前のエントリと比較されませんので）、残りのデータの尾に対する各エントリをチェックし、データを循環、アキュムレータ（accとラベル付けされています）は通過できます。そうでない場合は、現在のエントリ（zz）をアキュムレータに追加します。この更新されたアキュムレータは、「残りの」文字列（zt.tail）の末尾とペアになって、比較対象の縮小セットを確実にします。

最後に、必要な残りの文字列と空のリスト（比較対象の文字列はありません）のリストを作成します。その結果、最初のものが結果として得られます。

第1回、第4回、第8回の文字列が似ている場合、問題は最初の繰り返しのようです。私は第1文字列のみを取得しています。その代わりに、私は（第1、第4、第8）のセットを取得する必要があります、次に2番目、5番目、14番目と21番目の文字列が似ている場合は、（2番目、5番目、14番目、21番目）のセットを取得する必要があります。

Answer 1

あなたが正しく理解していれば、結果はList[List[String]]で、今はList[String]ではなく、それぞれの項目が類似した文字列のリスト（右）であることを望みます。

もしそうなら - あなたはスキップ - あなたがもし（真の）枝を入力して、ちょうどaccを返す場合にも、同様の値が（を失っているように私は、これを達成するであろう、あなたの実装に些細な変化を見ることができませんあなたは決してそれを再び見ることはありません）。あなたの考えに基づき

1. が、追加scannedはalready-のリストであるfoldLeft結果の型、としてフォーム(acc, zt, scanned)の3組を使用して：私は考えることができる

   2つの解決策スキャンされたアイテム。 Aおそらく、遅いがはるかに簡単な解決策は、類似文字列のちょうどgroupByグループになり

   val filtered = z.reverse.foldLeft((List.empty[List[String]],z.reverse,List.empty[String])) { 
       case ((acc, zt, scanned), zz) => 
       val hasSimilarPreceeding = zt.tail.exists { tt => similarity(tt, zz) < threshold } 
       val similarFollowing = scanned.collect { case tt if similarity(tt, zz) < threshold => tt } 
       (if (hasSimilarPreceeding) acc else (zz :: similarFollowing) :: acc, zt.tail, zz :: scanned) 
   }._1 
   

2. ：：私たちは同様の要素を先行しているいない要素を見つけたとき、我々は彼らに戻って参照することができますこの方法

   val alternative = z.groupBy(s => z.collect { 
       case other if similarity(s, other) < threshold => other 
   }.toSet).values.toList 
   

このすべてその機能を前提としています

f(a: String, b: String): Boolean = similarity(a, b) < threshold 

は可換性で推移的です。：

// strings are similar if they start with the same character 
def similarity(s1: String, s2: String) = if (s1.head == s2.head) 0 else 100 

val threshold = 1 
val z = List("aa", "ab", "c", "a", "e", "fa", "fb") 

をし、両方のオプションは同じ結果を生む：

• f(a, b) && f(a. c)は、両方の実装をテストするにはf(b, c)
• f(a, b)場合にのみ

f(b, a)場合、私が使用していることを意味し

List(List(aa, ab, a), List(c), List(e), List(fa, fb))