Repository: graphhopper/graphhopper
Pull request #893 (2016-12-02 00:01:24)

Jaro Winkler Point Hint Improvement
Switched from Levenshtein to Jaro Winkler for NameSimilarityEdgeFilter.


Patch:
diff --git a/NOTICE.md b/NOTICE.md
index 3b69e3da3..a5279ddef 100644
--- a/NOTICE.md
+++ b/NOTICE.md
@@ -11,6 +11,7 @@ The core module includes the following software:
  * XMLGraphics-Commons for CGIAR elevation files (Apache License)
  * Apache Commons Lang - we copied the implementation of the Levenshtein Distance (Apache License)
  * Apache Commons Collections - we copied parts of the BinaryHeap (Apache License)
+ * java-string-similarity - we copied the implementation of JaroWinkler (MIT license)
 
 reader-osm:
 
diff --git a/core/pom.xml b/core/pom.xml
index 71ff5ac35..36155ba7a 100644
--- a/core/pom.xml
+++ b/core/pom.xml
@@ -35,7 +35,7 @@
             <comments>A business-friendly OSS license</comments>
         </license>
     </licenses>
-    <dependencies>        
+    <dependencies>
         <dependency>
             <groupId>com.carrotsearch</groupId>
             <artifactId>hppc</artifactId>
diff --git a/core/src/main/java/com/graphhopper/debatty/java/stringsimilarity/JaroWinkler.java b/core/src/main/java/com/graphhopper/debatty/java/stringsimilarity/JaroWinkler.java
new file mode 100644
index 000000000..f73c51bf1
--- /dev/null
+++ b/core/src/main/java/com/graphhopper/debatty/java/stringsimilarity/JaroWinkler.java
@@ -0,0 +1,153 @@
+/*
+Copyright 2015 Thibault Debatty.
+
+Permission is hereby granted, free of charge, to any person obtaining a copy of this software and associated
+documentation files (the "Software"), to deal in the Software without restriction, including without limitation the
+rights to use, copy, modify, merge, publish, distribute, sublicense, and/or sell copies of the Software, and to permit
+persons to whom the Software is furnished to do so, subject to the following conditions:
+
+The above copyright notice and this permission notice shall be included in all copies or substantial portions of the
+Software.
+
+THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE
+WARRANTIES OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR
+COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR
+OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
+ */
+package com.graphhopper.debatty.java.stringsimilarity;
+
+import java.util.Arrays;
+
+/**
+ * This class is copied from: https://github.com/tdebatty/java-string-similarity/blob/master/src/main/java/info/debatty/java/stringsimilarity/JaroWinkler.java
+ * and slightly modified. *
+ *
+ * The Jaro–Winkler distance metric is designed and best suited for short
+ * strings such as person names, and to detect typos; it is (roughly) a
+ * variation of Damerau-Levenshtein, where the substitution of 2 close
+ * characters is considered less important then the substitution of 2 characters
+ * that a far from each other.
+ * Jaro-Winkler was developed in the area of record linkage (duplicate
+ * detection) (Winkler, 1990). It returns a value in the interval [0.0, 1.0].
+ * The distance is computed as 1 - Jaro-Winkler similarity.
+ * @author Thibault Debatty
+ */
+public class JaroWinkler {
+
+    private static final double DEFAULT_THRESHOLD = 0.7;
+    private static final int THREE = 3;
+    private static final double JW_COEF = 0.1;
+    private final double threshold;
+
+    /**
+     * Instantiate with default threshold (0.7).
+     *
+     */
+    public JaroWinkler() {
+        this.threshold = DEFAULT_THRESHOLD;
+    }
+
+    /**
+     * Instantiate with given threshold to determine when Winkler bonus should
+     * be used.
+     * Set threshold to a negative value to get the Jaro distance.
+     */
+    public JaroWinkler(final double threshold) {
+        this.threshold = threshold;
+    }
+
+    /**
+     * Returns the current value of the threshold used for adding the Winkler
+     * bonus. The default value is 0.7.
+     *
+     * @return the current value of the threshold
+     */
+    public final double getThreshold() {
+        return threshold;
+    }
+
+    /**
+     * Compute JW similarity.
+     */
+    public final double similarity(final String s1, final String s2) {
+        int[] mtp = matches(s1, s2);
+        float m = mtp[0];
+        if (m == 0) {
+            return 0f;
+        }
+        double j = ((m / s1.length() + m / s2.length() + (m - mtp[1]) / m))
+                / THREE;
+        double jw = j;
+
+        if (j > getThreshold()) {
+            jw = j + Math.min(JW_COEF, 1.0 / mtp[THREE]) * mtp[2] * (1 - j);
+        }
+        return jw;
+    }
+
+
+    /**
+     * Return 1 - similarity.
+     */
+    public final double distance(final String s1, final String s2) {
+        return 1.0 - similarity(s1, s2);
+    }
+
+    private int[] matches(final String s1, final String s2) {
+        String max, min;
+        if (s1.length() > s2.length()) {
+            max = s1;
+            min = s2;
+        } else {
+            max = s2;
+            min = s1;
+        }
+        int range = Math.max(max.length() / 2 - 1, 0);
+        int[] matchIndexes = new int[min.length()];
+        Arrays.fill(matchIndexes, -1);
+        boolean[] matchFlags = new boolean[max.length()];
+        int matches = 0;
+        for (int mi = 0; mi < min.length(); mi++) {
+            char c1 = min.charAt(mi);
+            for (int xi = Math.max(mi - range, 0),
+                 xn = Math.min(mi + range + 1, max.length()); xi < xn; xi++) {
+                if (!matchFlags[xi] && c1 == max.charAt(xi)) {
+                    matchIndexes[mi] = xi;
+                    matchFlags[xi] = true;
+                    matches++;
+                    break;
+                }
+            }
+        }
+        char[] ms1 = new char[matches];
+        char[] ms2 = new char[matches];
+        for (int i = 0, si = 0; i < min.length(); i++) {
+            if (matchIndexes[i] != -1) {
+                ms1[si] = min.charAt(i);
+                si++;
+            }
+        }
+        for (int i = 0, si = 0; i < max.length(); i++) {
+            if (matchFlags[i]) {
+                ms2[si] = max.charAt(i);
+                si++;
+            }
+        }
+        int transpositions = 0;
+        for (int mi = 0; mi < ms1.length; mi++) {
+            if (ms1[mi] != ms2[mi]) {
+                transpositions++;
+            }
+        }
+        int prefix = 0;
+        for (int mi = 0; mi < min.length(); mi++) {
+            if (s1.charAt(mi) == s2.charAt(mi)) {
+                prefix++;
+            } else {
+                break;
+            }
+        }
+        return new int[]{matches, transpositions / 2, prefix, max.length()};
+    }
+
+}
diff --git a/core/src/main/java/com/graphhopper/routing/util/NameSimilarityEdgeFilter.java b/core/src/main/java/com/graphhopper/routing/util/NameSimilarityEdgeFilter.java
index 35b53db2a..50a1f10d5 100644
--- a/core/src/main/java/com/graphhopper/routing/util/NameSimilarityEdgeFilter.java
+++ b/core/src/main/java/com/graphhopper/routing/util/NameSimilarityEdgeFilter.java
@@ -17,49 +17,67 @@
  */
 package com.graphhopper.routing.util;
 
+import com.graphhopper.debatty.java.stringsimilarity.JaroWinkler;
 import com.graphhopper.util.EdgeIteratorState;
 import com.graphhopper.apache.commons.lang3.StringUtils;
 
+import java.util.*;
 import java.util.regex.Pattern;
 
 /**
- * Abstract Class that defines the basis for NameSimilarity matching using an EdgeFilter.
+ * This class defines the basis for NameSimilarity matching using an EdgeFilter.
+ * The typical use-case is to match not the nearest edge in
+ * {@link com.graphhopper.storage.index.LocationIndex#findClosest(double, double, EdgeFilter)}
+ * but the match the edge which name is closest to the pointHint
+ *
+ * Names that are similar to each other are (n1 name1, n2 name2):
+ * <ul>
+ *     <li>n1 == n2</li>
+ *     <li>n1 is significant substring of n2, e.g: n1="Main Road", n2="Main Road, New York"</li>
+ *     <li>n1 and n2 contain a reasonable longest common substring, e.g.: n1="Cape Point / Cape of Good Hope", n2="Cape Point Rd, Cape Peninsula, Cape Town, 8001, Afrique du Sud"</li>
+ * </ul>
+ *
+ * We aim for allowing slight typos/differences of the substrings, without having too much false positives.
  *
  * @author Robin Boldt
  */
 public class NameSimilarityEdgeFilter implements EdgeFilter {
 
-    public static final int EXACT = 0;
-    public static final int LEVENSHTEIN = 1;
-    public static final int STRING_MATCHING_ALGO = LEVENSHTEIN;
-
-    private static final double LEVENSHTEIN_ACCEPT_FACTOR = .05;
+    private static final Pattern NON_WORD_CHAR = Pattern.compile("[^\\p{L}]+");
+    private final double JARO_WINKLER_ACCEPT_FACTOR = .79;
+    private final JaroWinkler jaroWinkler = new JaroWinkler();
 
     private final EdgeFilter edgeFilter;
-    private final String soughtName;
-    private static final Pattern nonWordCharacter = Pattern.compile("[^\\p{L}]+");
+    private final String pointHint;
 
-    public NameSimilarityEdgeFilter(EdgeFilter edgeFilter, String soughtName) {
+    public NameSimilarityEdgeFilter(EdgeFilter edgeFilter, String pointHint) {
         this.edgeFilter = edgeFilter;
-        this.soughtName = prepareName(soughtName);
+        this.pointHint = prepareName(pointHint == null ? "" : pointHint);
     }
 
     /**
      * Removes any characters in the String that we don't care about in the matching procedure
+     * TODO: Remove common street names like: street, road, avenue?
      */
-    private String prepareName(String name){
-        if(name == null){
-            name = "";
+    private String prepareName(String name) {
+        // TODO make this better, also split at ',' and others?
+        // TODO This limits the approach to certain 'western' languages
+        // \s = A whitespace character: [ \t\n\x0B\f\r]
+        String[] arr = name.split("\\s");
+        String tmp;
+        List<String> list = new ArrayList<>(arr.length);
+        for (int i = 0; i < arr.length; i++) {
+            tmp = NON_WORD_CHAR.matcher(arr[i].toLowerCase()).replaceAll("");
+            // Ignore matching short frases like, de, rue, st, etc.
+            if(!tmp.isEmpty() && tmp.length() > 3){
+                list.add(tmp);
+            }
         }
-
-        name = nonWordCharacter.matcher(name).replaceAll("");
-        name = name.toLowerCase();
-
-        return name;
+        return listToString(list);
     }
 
-    private String removeRelation(String edgeName){
-        if(edgeName != null && edgeName.contains(", ")){
+    private String removeRelation(String edgeName) {
+        if (edgeName != null && edgeName.contains(", ")) {
             edgeName = edgeName.substring(0, edgeName.lastIndexOf(','));
         }
         return edgeName;
@@ -67,37 +85,51 @@ public class NameSimilarityEdgeFilter implements EdgeFilter {
 
     @Override
     public final boolean accept(EdgeIteratorState iter) {
-        if(!edgeFilter.accept(iter)){
+        if (!edgeFilter.accept(iter)) {
             return false;
         }
 
-        // Don't check if PointHint is empty anyway
-        if(soughtName.isEmpty()){
+        if (pointHint.isEmpty()) {
             return true;
         }
 
         String name = iter.getName();
-
-        if(name == null || name.isEmpty()){
+        if (name == null || name.isEmpty()) {
             return false;
         }
 
         name = removeRelation(name);
-        name = prepareName(name);
-
-        switch (STRING_MATCHING_ALGO){
-            case LEVENSHTEIN:
-                return isLevenshteinSimilar(name);
-            case EXACT:
-            default:
-                return name.equals(soughtName);
-        }
+        String edgeName = prepareName(name);
+
+        return isJaroWinklerSimilar(pointHint, edgeName);
+    }
+
+    private boolean isJaroWinklerSimilar(String str1, String str2) {
+        double jwSimilarity = jaroWinkler.similarity(str1, str2);
+        // System.out.println(str1 + " vs. edge:" + str2 + ", " + jwSimilarity);
+        return jwSimilarity > JARO_WINKLER_ACCEPT_FACTOR;
+    }
 
+    private final String listToString(List<String> list){
+        StringBuilder b = new StringBuilder();
+        for (int i = 0; i<list.size(); i++) {
+            b.append(list.get(i));
+        }
+        return b.toString();
     }
 
-    private boolean isLevenshteinSimilar(String name){
-        int perfectDistance = (int) (Math.abs(soughtName.length()-name.length()) + Math.ceil(soughtName.length()*LEVENSHTEIN_ACCEPT_FACTOR));
-        int levDistance = StringUtils.getLevenshteinDistance(soughtName, name);
-        return levDistance <= perfectDistance;
+
+    private boolean isLevenshteinSimilar(String hint, String name) {
+        // too big length difference
+        if (Math.min(name.length(), hint.length()) * 4 < Math.max(name.length(), hint.length()))
+            return false;
+
+        // The part 'abs(pointHint.length - name.length)' tries to make differences regarding length less important
+        // Ie. 'hauptstraßedresden' vs. 'hauptstr.' should be considered a match, but 'hauptstraßedresden' vs. 'klingestraßedresden' should not match
+        int factor = 1 + Math.abs(hint.length() - name.length());
+        int levDistance = StringUtils.getLevenshteinDistance(hint, name);
+        // System.out.println(hint + " vs. edge:" + name + ", " + levDistance + " <= " + factor);
+        return levDistance <= factor;
     }
+
 }


Test patch:
diff --git a/core/src/test/java/com/graphhopper/routing/util/NameSimilarityEdgeFilterTest.java b/core/src/test/java/com/graphhopper/routing/util/NameSimilarityEdgeFilterTest.java
index 722236027..77e3b0a6e 100644
--- a/core/src/test/java/com/graphhopper/routing/util/NameSimilarityEdgeFilterTest.java
+++ b/core/src/test/java/com/graphhopper/routing/util/NameSimilarityEdgeFilterTest.java
@@ -19,6 +19,7 @@ package com.graphhopper.routing.util;
 
 import com.graphhopper.util.EdgeIteratorState;
 import com.graphhopper.util.GHUtility;
+import org.junit.Ignore;
 import org.junit.Test;
 
 import static junit.framework.TestCase.assertFalse;
@@ -31,7 +32,6 @@ public class NameSimilarityEdgeFilterTest {
 
     @Test
     public void testAccept() {
-
         EdgeFilter edgeFilter = new NameSimilarityEdgeFilter(new DefaultEdgeFilter(new CarFlagEncoder()), "Laufamholzstraße 154 Nürnberg");
         EdgeIteratorState edge = createTestEdgeIterator("Laufamholzstraße, ST1333");
         assertTrue(edgeFilter.accept(edge));
@@ -69,9 +69,125 @@ public class NameSimilarityEdgeFilterTest {
 
         edge = createTestEdgeIterator("Hauptstraße");
         assertTrue(edgeFilter.accept(edge));
+
+        edge = createTestEdgeIterator("Hauptstrasse");
+        assertTrue(edgeFilter.accept(edge));
+
+        edge = createTestEdgeIterator("Hauptstr.");
+        assertTrue(edgeFilter.accept(edge));
+
+    }
+
+    /**
+     * With Nominatim you should not use the "placename" for best results, otherwise the length difference becomes too big
+     */
+    @Test
+    public void testAcceptFromNominatim() {
+        EdgeFilter edgeFilter;
+        EdgeIteratorState edge;
+
+        edgeFilter = new NameSimilarityEdgeFilter(new DefaultEdgeFilter(new CarFlagEncoder()), "Wentworth Street, Caringbah South");
+        edge = createTestEdgeIterator("Wentworth Street");
+        assertTrue(edgeFilter.accept(edge));
+
+        edgeFilter = new NameSimilarityEdgeFilter(new DefaultEdgeFilter(new CarFlagEncoder()), "Zum Toffental, Altdorf bei Nürnnberg");
+        edge = createTestEdgeIterator("Zum Toffental");
+        assertTrue(edgeFilter.accept(edge));
     }
 
     @Test
+    public void testAcceptFromGoogleMapsGeocoding() {
+        EdgeFilter edgeFilter;
+        EdgeIteratorState edge;
+
+        edgeFilter = new NameSimilarityEdgeFilter(new DefaultEdgeFilter(new CarFlagEncoder()), "Rue Notre-Dame O Montréal");
+        edge = createTestEdgeIterator("Rue Dupré");
+        assertFalse(edgeFilter.accept(edge));
+
+        edge = createTestEdgeIterator("Rue Notre-Dame Ouest");
+        assertTrue(edgeFilter.accept(edge));
+
+        edgeFilter = new NameSimilarityEdgeFilter(new DefaultEdgeFilter(new CarFlagEncoder()), "227 Rue Saint-Antoine O, Montréal");
+        edge = createTestEdgeIterator("Rue Saint-Antoine O");
+        assertTrue(edgeFilter.accept(edge));
+
+        edge = createTestEdgeIterator("Rue Saint-Jacques");
+        assertFalse(edgeFilter.accept(edge));
+
+        edgeFilter = new NameSimilarityEdgeFilter(new DefaultEdgeFilter(new CarFlagEncoder()), "1025 Rue de Bleury, Montréal, QC H2Z 1M7");
+        edge = createTestEdgeIterator("Rue de Bleury");
+        assertTrue(edgeFilter.accept(edge));
+
+        edge = createTestEdgeIterator("Rue Balmoral");
+        assertFalse(edgeFilter.accept(edge));
+
+        // Modified Test from Below
+        edgeFilter = new NameSimilarityEdgeFilter(new DefaultEdgeFilter(new CarFlagEncoder()), "257 Main Road, Claremont, Cape Town, 7708, Afrique du Sud");
+        edge = createTestEdgeIterator("Main Road");
+        assertTrue(edgeFilter.accept(edge));
+
+        edgeFilter = new NameSimilarityEdgeFilter(new DefaultEdgeFilter(new CarFlagEncoder()), "Cape Point Rd, Cape Peninsula, Cape Town, 8001, Afrique du Sud");
+        edge = createTestEdgeIterator("Cape Point / Cape of Good Hope");
+        assertTrue(edgeFilter.accept(edge));
+
+        edgeFilter = new NameSimilarityEdgeFilter(new DefaultEdgeFilter(new CarFlagEncoder()), "Viale Puglie, 26, 20137 Milano, Italy");
+        edge = createTestEdgeIterator("Viale Puglie");
+        assertTrue(edgeFilter.accept(edge));
+    }
+
+    @Test
+    public void testAcceptMashup() {
+        EdgeFilter edgeFilter;
+        EdgeIteratorState edge;
+
+        edge = createTestEdgeIterator("Augustine Street");
+
+        // Google Maps
+        edgeFilter = new NameSimilarityEdgeFilter(new DefaultEdgeFilter(new CarFlagEncoder()), "Augustine St, Hunters Hill NSW 2110, Australia");
+        assertTrue(edgeFilter.accept(edge));
+
+        // Opencagedata
+        edgeFilter = new NameSimilarityEdgeFilter(new DefaultEdgeFilter(new CarFlagEncoder()), "Augustine Street, Sydney Neusüdwales 2110, Australien");
+        assertTrue(edgeFilter.accept(edge));
+
+        // Nominatim
+        edgeFilter = new NameSimilarityEdgeFilter(new DefaultEdgeFilter(new CarFlagEncoder()), "Augustine Street, Sydney, Municipality of Hunters Hill, Neusüdwales, 2111, Australien");
+        assertTrue(edgeFilter.accept(edge));
+
+    }
+
+    @Ignore
+    public void testThatShouldSucceed(){
+        EdgeFilter edgeFilter;
+        EdgeIteratorState edge;
+
+        // The Problem is that Rd vs Road is abreviated, if we have Road, it works
+        edgeFilter = new NameSimilarityEdgeFilter(new DefaultEdgeFilter(new CarFlagEncoder()), "257 Main Rd, Claremont, Cape Town, 7708, Afrique du Sud");
+        edge = createTestEdgeIterator("Main Road");
+        assertTrue(edgeFilter.accept(edge));
+
+        // Just too much difference Between Google Maps and OSM @ 32.121435,-110.857969
+        edgeFilter = new NameSimilarityEdgeFilter(new DefaultEdgeFilter(new CarFlagEncoder()), "7202 S Wilmot Rd, Tucson, AZ 85701");
+        edge = createTestEdgeIterator("South Wilmot Road");
+        assertTrue(edgeFilter.accept(edge));
+
+        // @ 37.307774,13.581259
+        edgeFilter = new NameSimilarityEdgeFilter(new DefaultEdgeFilter(new CarFlagEncoder()), "Via Manzoni, 50/52, 92100 Agrigento AG, Italy");
+        edge = createTestEdgeIterator("Via Alessandro Manzoni");
+        assertTrue(edgeFilter.accept(edge));
+
+        edgeFilter = new NameSimilarityEdgeFilter(new DefaultEdgeFilter(new CarFlagEncoder()), "Av. Juan Ramón Ramírez, 12, 02630 La Roda, Albacete, Spain");
+        edge = createTestEdgeIterator("Avenida Juan Ramón Ramírez");
+        assertTrue(edgeFilter.accept(edge));
+
+
+    }
+
+
+    /**
+     * We ignore Typos for now, most GeoCoders return pretty good results, we might allow some typos
+     */
+    @Ignore
     public void testAcceptWithTypos() {
         EdgeFilter edgeFilter = new NameSimilarityEdgeFilter(new DefaultEdgeFilter(new CarFlagEncoder()), "Laufamholzstraße 154 Nürnberg");
         EdgeIteratorState edge = createTestEdgeIterator("Laufamholzstraße, ST1333");
@@ -98,23 +214,25 @@ public class NameSimilarityEdgeFilterTest {
         assertTrue(edgeFilter.accept(edge));
 
         // Two Typos
-        edgeFilter = new NameSimilarityEdgeFilter(new DefaultEdgeFilter(new CarFlagEncoder()), "Hauptstrasi");
-        assertFalse(edgeFilter.accept(edge));
+        edgeFilter = new NameSimilarityEdgeFilter(new DefaultEdgeFilter(new CarFlagEncoder()), "Lauptstrase");
+        assertTrue(edgeFilter.accept(edge));
 
-        //TODO Maybe we should not allow matching too short strings here?
+        // We ignore too short Strings for now
+        /*
         // Distance - PerfectDistance = 1
         edgeFilter = new NameSimilarityEdgeFilter(new DefaultEdgeFilter(new CarFlagEncoder()), "z");
-        assertTrue(edgeFilter.accept(edge));
+        assertFalse(edgeFilter.accept(edge));
         // Distance - PerfectDistance = 1
         edgeFilter = new NameSimilarityEdgeFilter(new DefaultEdgeFilter(new CarFlagEncoder()), "az");
-        assertTrue(edgeFilter.accept(edge));
+        assertFalse(edgeFilter.accept(edge));
 
         // Distance - PerfectDistance = 2
         edgeFilter = new NameSimilarityEdgeFilter(new DefaultEdgeFilter(new CarFlagEncoder()), "xy");
         assertFalse(edgeFilter.accept(edge));
+        */
     }
 
-    private EdgeIteratorState createTestEdgeIterator(final String name){
+    private EdgeIteratorState createTestEdgeIterator(final String name) {
         return new GHUtility.DisabledEdgeIterator() {
 
             @Override