Index: trunk/src/org/openstreetmap/josm/data/validation/TestError.java =================================================================== --- trunk/src/org/openstreetmap/josm/data/validation/TestError.java (revision 7847) +++ trunk/src/org/openstreetmap/josm/data/validation/TestError.java (revision 7848) @@ -327,5 +327,5 @@ @Override public String toString() { - return "TestError [tester=" + tester + ", code=" + code + "]"; + return "TestError [tester=" + tester + ", code=" + code + ", message=" + message + "]"; } } Index: trunk/src/org/openstreetmap/josm/data/validation/tests/SimilarNamedWays.java =================================================================== --- trunk/src/org/openstreetmap/josm/data/validation/tests/SimilarNamedWays.java (revision 7847) +++ trunk/src/org/openstreetmap/josm/data/validation/tests/SimilarNamedWays.java (revision 7848) @@ -2,11 +2,16 @@ package org.openstreetmap.josm.data.validation.tests; +import static java.util.regex.Pattern.CASE_INSENSITIVE; +import static java.util.regex.Pattern.UNICODE_CASE; import static org.openstreetmap.josm.tools.I18n.tr; import java.awt.geom.Point2D; import java.util.ArrayList; +import java.util.Arrays; import java.util.HashMap; import java.util.List; import java.util.Map; +import java.util.regex.Matcher; +import java.util.regex.Pattern; import org.openstreetmap.josm.data.osm.OsmPrimitive; @@ -35,4 +40,6 @@ private MultiMap errorWays; + private ArrayList rules = new ArrayList(); + /** * Constructor @@ -41,4 +48,12 @@ super(tr("Similarly named ways"), tr("This test checks for ways with similar names that may have been misspelled.")); + + // FIXME: hardcode these rules for now. Replace them with preferences later + // See https://josm.openstreetmap.de/ticket/3733#comment:19 + addRegExprRule("\\d+", "0"); // Highway 66 + addRegExprRule("\\d+(st|nd|rd|th)", "0st"); // 3rd Ave + addRegExprRule("^[A-Z] ", "X"); // E Street + addSynonyms("east", "west", "north", "south"); + addSynonyms("first", "second", "third"); } @@ -78,6 +93,5 @@ } - int levenshteinDistance = getLevenshteinDistance(name, name2); - if (0 < levenshteinDistance && levenshteinDistance <= 2) { + if (similaryName(name, name2)) { List primitives = new ArrayList<>(2); primitives.add(w); @@ -98,5 +112,5 @@ * @return The distance between words */ - public int getLevenshteinDistance(String s, String t) { + public static int getLevenshteinDistance(String s, String t) { int[][] d; // matrix int n; // length of s @@ -150,3 +164,145 @@ return d[n][m]; } + + /** + * Add a regular expression rule. + * @param regExpr the regular expression to search for + * @param replacement a string to replace with, which should match the expression. + */ + public void addRegExprRule(String regExpr, String replacement) { + rules.add(new RegExprRule(regExpr, replacement)); + } + + /** + * Add a rule with synonym words. + * @param words words which are synonyms + */ + public void addSynonyms(String... words) { + for (String word : words) { + rules.add(new SynonymRule(word, words)); + } + } + + /** + * Check if two names are similar, but not identical. First both names will be "normalized". + * Afterwards the Levenshtein distance will be calculated.
+ * Examples for normalization rules:
+ * replaceAll("\\d+", "0")
+ * would cause similaryName("track 1", "track 2") = false, but similaryName("Track 1", "track 2") = true + * @param name first name to compare + * @param name2 second name to compare + * @return true if the normalized names are different but only a "little bit" + */ + public boolean similaryName(String name, String name2) { + // check plain strings + int distance = getLevenshteinDistance(name, name2); + boolean similar = distance>0 && distance<=2; + + // try all rules + for (NormalizeRule rule : rules) { + int levenshteinDistance = getLevenshteinDistance(rule.normalize(name), rule.normalize(name2)); + if (levenshteinDistance == 0) + // one rule results in identical names: identical + return false; + else if (levenshteinDistance <= 2) { + // 0 < distance <= 2 + similar = true; + } + } + return similar; + } + + public interface NormalizeRule { + + /** + * Normalize the string by replacing parts. + * @param name name to normalize + * @return normalized string + */ + String normalize(String name); + } + + public class RegExprRule implements NormalizeRule { + private final Pattern regExpr; + private final String replacement; + + public RegExprRule(String expression, String replacement) { + this.regExpr = Pattern.compile(expression); + this.replacement = replacement; + } + + @Override + public String normalize(String name) { + return regExpr.matcher(name).replaceAll(replacement); + } + + @Override + public String toString() { + return "replaceAll(" + regExpr + ", " + replacement + ")"; + } + } + + public class SynonymRule implements NormalizeRule { + + private final String[] words; + private final Pattern regExpr; + private final String replacement; + + public SynonymRule(String replacement, String[] words) { + this.replacement = replacement.toLowerCase(); + this.words = words; + + // build regular expression for other words (for fast match) + StringBuilder expression = new StringBuilder(); + int maxLength = 0; + for (int i = 0; i < words.length; i++) { + if (words[i].length() > maxLength) { + maxLength = words[i].length(); + } + if (expression.length() > 0) { + expression.append("|"); + } + expression.append(Pattern.quote(words[i])); + } + this.regExpr = Pattern.compile(expression.toString(), CASE_INSENSITIVE + UNICODE_CASE); + } + + @Override + public String normalize(String name) { + // find first match + Matcher matcher = regExpr.matcher(name); + if (!matcher.find()) + return name; + + int start = matcher.start(); + + // which word matches? + String part = ""; + for (int i = 0; i < words.length; i++) { + String word = words[i]; + part = name.substring(start, start + word.length()); + if (word.equalsIgnoreCase(part)) { + break; + } + } + + // replace the word + char[] newName = matcher.replaceFirst(replacement).toCharArray(); + + // adjust case (replacement is not shorter than matching word!) + int minLength = Math.min(replacement.length(), part.length()); + for (int i = 0; i < minLength; i++) { + if (Character.isUpperCase(part.charAt(i))) { + newName[start + i] = Character.toUpperCase(newName[start + i]); + } + } + + return new String(newName); + } + + @Override + public String toString() { + return "synonyms(" + replacement + ", " + Arrays.toString(words) + ")"; + } + } } Index: trunk/test/unit/org/openstreetmap/josm/data/validation/tests/SimilarNamedWaysTest.groovy =================================================================== --- trunk/test/unit/org/openstreetmap/josm/data/validation/tests/SimilarNamedWaysTest.groovy (revision 7848) +++ trunk/test/unit/org/openstreetmap/josm/data/validation/tests/SimilarNamedWaysTest.groovy (revision 7848) @@ -0,0 +1,107 @@ +// License: GPL. See LICENSE file for details. +package org.openstreetmap.josm.data.validation.tests + +import static org.junit.Assert.assertEquals + +import org.openstreetmap.josm.JOSMFixture +import org.openstreetmap.josm.data.coor.LatLon +import org.openstreetmap.josm.data.osm.DataSet +import org.openstreetmap.josm.data.osm.Node +import org.openstreetmap.josm.data.osm.Way +import org.openstreetmap.josm.data.validation.TestError + +class SimilarNamedWaysTest extends GroovyTestCase { + + SimilarNamedWays test = new SimilarNamedWays() + + @Override + void setUp() { + JOSMFixture.createUnitTestFixture().init(); + } + + public static List testWays(String namea, String nameb) { + def ds = new DataSet() + + def n00 = new Node(new LatLon(0, 0)) + def n10 = new Node(new LatLon(1, 0)) + def n20 = new Node(new LatLon(2, 0)) + def n30 = new Node(new LatLon(3, 0)) + def n40 = new Node(new LatLon(4, 0)) + + ds.addPrimitive(n00) + ds.addPrimitive(n10) + ds.addPrimitive(n20) + ds.addPrimitive(n30) + ds.addPrimitive(n40) + + def waya = new Way() + waya.addNode(n00) + waya.addNode(n10) + waya.addNode(n20) + waya.put("name", namea) + def wayb = new Way() + wayb.addNode(n20) + wayb.addNode(n30) + wayb.addNode(n40) + wayb.put("name", nameb) + + ds.addPrimitive(waya) + ds.addPrimitive(wayb) + + assert waya.isUsable() + assert wayb.isUsable() + + def t = new SimilarNamedWays() + t.startTest(null) + t.visit(waya) + t.visit(wayb) + return t.errors + } + + void testCombinations() { + assert testWays("Church Street", "Water Street").isEmpty() + assert !testWays("Main Street", "Maim Street").isEmpty() + assert !testWays("First Street", "Frist Street").isEmpty() + + assert testWays("1st Street", "2nd Street").isEmpty() + assert testWays("First Avenue", "Second Avenue").isEmpty() + assert testWays("West Main Street", "East Main Street").isEmpty() + assert testWays("A Street", "B Street").isEmpty() + } + + void checkSimilarity(String message, String name1, String name2, boolean expected) { + boolean actual = test.similaryName(name1, name2); + assertEquals(message, expected, actual); + } + + void testSimilarNames() { + checkSimilarity("same string", "Testname", "Testname", false); + checkSimilarity("different case", "Testname", "TestName", true); + checkSimilarity("typo", "Testname", "Testxame", true); + checkSimilarity("missing char", "Testname", "Testame", true); + checkSimilarity("additional char", "Testname", "Testxname", true); + checkSimilarity("2 changes", "Testname", "Tostxname", true); + checkSimilarity("3 changes", "Testname", "Tostxnam", false); + + // regular expression rule + checkSimilarity("same number", "track 1", "track 1", false); + checkSimilarity("different number", "track 1", "track 2", false); + checkSimilarity("different number length", "track 9", "track 10", false); + checkSimilarity("multiple numbers", "track 8 - 9", "track 10 - 11", false); + + checkSimilarity("1st and 2nd", "1st Street", "2nd Street", false); + checkSimilarity("1st case", "1St Street", "1st Street", true); + checkSimilarity("1st and 2nd case", "1St Street", "2nd Street", true); + checkSimilarity("3rd and 4th", "2rd Street", "4th Street", false); + + // synonyms + checkSimilarity("east and west", "East Foothill Drive", "West Foothill Drive", false); + checkSimilarity("east and west case", "east Foothill Drive", "West Foothill Drive", true); + checkSimilarity("first and second", "First Street", "Second Street", false); + checkSimilarity("first and second case", "First Street", "second Street", true); + checkSimilarity("first and second typo", "Forst Street", "Second Street", true); + checkSimilarity("first and second typo2", "First Street", "Socond Street", true); + checkSimilarity("first and second 2 changes", "First Street", "Soconds Street", true); + checkSimilarity("first and second 3 changes", "First Street", "Soconds Stret", false); + } +}