Changeset 1126

Timestamp:

Nov 12, 2010, 12:08:07 PM (10 years ago)

Author:

t.w.abma@…

Message:

• initial fuzzy logic incorporated in Importer service

Location:

trunk/grails-app

Files:

• controllers/dbnp/importer/ImporterController.groovy (modified) (1 diff)
• services/dbnp/importer/ImporterService.groovy (modified) (1 diff)

trunk/grails-app/controllers/dbnp/importer/ImporterController.groovy

@@ -39 +39 @@
 
     def index = {
+        //String.metaClass.mostSimilarTo = { ImporterService.mostSimilar(delegate, it) }
+
         //session.import_referer = request.forwardURI
         // should do a check what is in the url, strip it?

trunk/grails-app/services/dbnp/importer/ImporterService.groovy

@@ -507 +507 @@
     }
 
+    // classes for fuzzy string matching
+    // <FUZZY MATCHING>
+    static def similarity(l_seq, r_seq, degree=2) {
+        def l_histo = countNgramFrequency(l_seq, degree)
+        def r_histo = countNgramFrequency(r_seq, degree)
+
+        dotProduct(l_histo, r_histo) /
+        Math.sqrt(dotProduct(l_histo, l_histo) *
+            dotProduct(r_histo, r_histo))
+    }
+
+    static def countNgramFrequency(sequence, degree) {
+        def histo = [:]
+        def items = sequence.size()
+
+        for (int i = 0; i + degree <= items; i++)
+        {
+            def gram = sequence[i..<(i + degree)]
+            histo[gram] = 1 + histo.get(gram, 0)
+        }
+        histo
+    }
+
+    static def dotProduct(l_histo, r_histo) {
+        def sum = 0
+        l_histo.each { key, value ->
+            sum = sum + l_histo[key] * r_histo.get(key, 0)
+        }
+        sum
+    }
+
+    static def stringSimilarity (l_str, r_str, degree=2) {
+        similarity(l_str.toLowerCase().toCharArray(),
+            r_str.toLowerCase().toCharArray(),
+            degree)
+    }
+
+    static def mostSimilar(pattern, candidates, threshold=0) {
+        def topScore = 0
+        def bestFit = null
+
+        candidates.each { candidate ->
+            def score = stringSimilarity(pattern, candidate)
+            if (score > topScore) {
+                topScore = score
+                bestFit = candidate
+            }
+        }
+
+        if (topScore < threshold)
+        bestFit = null
+
+        bestFit
+    }
+    // </FUZZY MATCHING>
+
 }