1
$\begingroup$

I'm working to filter a table of pairwise names (1.1 M rows) based on string distance algorithms. Most are names, though some are businesses.

Edit-based algorithms seem to be best, however in attempting to set a cutoff value for match vs. non-match, there is an issue with the length of the string. In a 16 character string, a score of 4 is usually a good match. But of course in a 4 character string, a score of 4 is a complete non-match.

What are good options for using a string distance algorithm, but scaling the scores relative to the length of the comparison strings? This doesn't seem to be built into any of the algorithms I've found.

Improve this question
$\endgroup$

1 Answer 1

Reset to default
2
$\begingroup$

You can use normalized edit distance, where you divide the edit distance by the length of the larger of the two strings. Whether this is better will depend on what you are trying to achieve.

There are many other techniques for fuzzy matching, which you might want to investigate. The Levenshtein edit distance is only a starting point.

Improve this answer
$\endgroup$
1
  • $\begingroup$ I've looked at qgram and heuristic methods as well and am currently evaluating which is best for my application - but I knew that without adjusting for string length, the edit distances were non-starters. Thanks! $\endgroup$
    – jzadra
    Apr 26, 2018 at 21:28

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.