Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Fix Levenshtein distance calculation with match function. #4545

Merged
merged 4 commits into from
Jan 14, 2020

Conversation

danielmai
Copy link
Contributor

@danielmai danielmai commented Jan 10, 2020

Fixes #4494.

We try to be smart about calculating the Levenshtein distance by short-circuiting the calculation based on the max-allowed distance, but that ends up returning incorrect distances.

  • Remove max argument
  • Fix and update tests.

This change is Reviewable

@danielmai danielmai requested review from manishrjain and a team as code owners January 10, 2020 20:21
Copy link
Contributor

@martinmr martinmr left a comment

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Just one minor comment but it :lgtm:

Reviewed 2 of 2 files at r1.
Reviewable status: all files reviewed, 1 unresolved discussion (waiting on @danielmai and @manishrjain)


worker/match.go, line 32 at r1 (raw file):

// required to change one word into the other.
//
// This implemention is optimized to use O(min(m,n)) space and is based on the

Is this comment still true after the changes?

Copy link
Contributor

@martinmr martinmr left a comment

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

approved

Reviewable status: all files reviewed, 1 unresolved discussion (waiting on @danielmai and @manishrjain)

Copy link
Contributor Author

@danielmai danielmai left a comment

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Reviewable status: all files reviewed, 1 unresolved discussion (waiting on @manishrjain and @martinmr)


worker/match.go, line 32 at r1 (raw file):

Previously, martinmr (Martin Martinez Rivera) wrote…

Is this comment still true after the changes?

Yup, because the column array is created.

Copy link
Contributor

@campoy campoy left a comment

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Reviewed 2 of 2 files at r1.
Reviewable status: all files reviewed, 1 unresolved discussion (waiting on @manishrjain and @martinmr)

@danielmai danielmai merged commit ef2757c into master Jan 14, 2020
@danielmai danielmai deleted the danielmai/match-distance branch January 14, 2020 18:27
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
None yet
Development

Successfully merging this pull request may close these issues.

Match query on trigram list not working as expected
3 participants