[patch] Fuzzy (approximate) string searching

[joshdoe]

I think it would be useful to enable a fuzzy (approximate) string search. We could use something like the ​Levenshtein distance for this. In the past I found several Java implementations for this, which I should link to here. We'd need to allow the user to choose whether or not to use fuzzy searching, ideally on a per-word basis, and to adjust how approximate the match has to be (the edit distance). I believe this should belong in core, but could be in a plugin, using a keyword like fuzzy, perhaps in utilsplugin2.

[simon04]

JOSM has already a Levenshtein distance implementation (see SimilarNamedWays).

[joshdoe]

Replying to simon04:

JOSM has already a Levenshtein distance implementation (see SimilarNamedWays).

I didn't realize that, though I should have. I'd like to move that function out of SimilarNamedWays.java​. I think I should put it in something like tools/TextUtils.java, and create an interface like the following to allow for other implementations of string distance (inspired by ​SimMetrics):

public interface InterfaceStringMetric {
    // 0 - no match, 1 - perfect match
    public float getSimilarity(String string1, String string2);
    public float getUnNormalisedSimilarity(String string1, String string2);
}

The remaining question is how such a fuzzy search is made? Possibly prepending the search term with a special character, like ~string, or be more verbose and require a "special target", like fuzzy:string?

[skyper]

Replying to joshdoe:

Replying to simon04:

JOSM has already a Levenshtein distance implementation (see SimilarNamedWays).

I didn't realize that, though I should have. I'd like to move that function out of SimilarNamedWays.java​. I think I should put it in something like tools/TextUtils.java, and create an interface like the following to allow for other implementations of string distance (inspired by ​SimMetrics):

Taking #3733 into account it should not belong to SimilarNamedWays.java​ as this function hopefully will use a different search in future.

[joshdoe]

extract levenshtein code to StringMetrics

[joshdoe]

I've attached a patch which extracts the Levenshtein code, allowing for use in the conflation plugin and other code, such as with fuzzy matching. I'm not sure the implementation is the best, so I'd appreciate a second look.

[simon04]

What about:

• having StringMetric as abstract class (representing the current interface) and being the only outer visible class
• use StringMetric.getByName/forName in the code (as in SimilarNamedWays)

What is the intention of the getSimilarity method?

[joshdoe]

Replying to simon04:

What about:

• having StringMetric as abstract class (representing the current interface) and being the only outer visible class
• use StringMetric.getByName/forName in the code (as in SimilarNamedWays)

I'd like to keep the interface (leaves open the possibility of plugins providing implementations), but I agree that users shouldn't have to carry around an instance, so maybe something like getSimilarityByName(String string1, String string2, String method).

What is the intention of the getSimilarity method?

getSimilarity is normalized from 0 to 1 so metrics can be easily swapped (not all metrics use a simple edit distance, i.e. number of characters changed). getUnNormalizedSimilarity is provided for those who know what the raw similarity measure means.

[simon04]

Replying to joshdoe:

so maybe something like getSimilarityByName(String string1, String string2, String method).

Or .getStringMetricByName(String method).getSimilarity(...)

To understand the aim of this modularization better: Should external plugins be able to provide an alternative String similarity measure for say SimilarNamedWays?

[joshdoe]

updates

[joshdoe]

Replying to simon04:

Replying to joshdoe:

so maybe something like getSimilarityByName(String string1, String string2, String method).

Or .getStringMetricByName(String method).getSimilarity(...)

Much better, done in new patch.

To understand the aim of this modularization better: Should external plugins be able to provide an alternative String similarity measure for say SimilarNamedWays?

I think plugins should be able to register alternative metrics, which core or other plugins can use, just like with projections. Though I haven't implemented such registering yet, let's wait for more than one implementation. :)

[stoecker]

@simon04: What's the status of this patch?

[stoecker]

see also #3733.

What is the status of this?

[bastiK]

I may have overlooked something, but it seems this patch does not contain any essential changes. I would prefer not to move the function to a separate class, unless there is a good reason for it. I.e. first provide alternative implementations, a GUI to switch these implementations, etc.

Then we can still organize the code, this is really the easiest part.