Project

General

Profile

Feature #10882

Provide Levenshtein distance implementation as part of stdlib

Added by yuki24 (Yuki Nishijima) over 4 years ago. Updated over 4 years ago.

Status:
Open
Priority:
Normal
Assignee:
-
Target version:
-
[ruby-core:68216]

Description

Levenshtein distance algorithm has been used by Rubygems, Bundler, did_you_mean and Rails and I think it's popular enough to provide it as part of Ruby's stdlib. It still seems a bit too high-level though, but definitely useful (e.g. adding "did you mean?" to rake).

API-wise, I would like to propose something like the following, but I'm totally open to hear the core team's opinions as I'm not sue if this is great.

require 'distance'

Distance.levenshtein(str1, str2)

It would also be interesting to have #distance method on String:

"word".distance("other")

which is implemented as:

def distance(str, algorithm = :levenshtein)
  # calculate the distance here.
end

so it can allow to change the algorythm when we add more (e.g. Jaro–Winkler distance).

History

Updated by kou (Kouhei Sutou) over 4 years ago

How about implementing did_you_mean feature by a plugin of Rake? (I don't know Rake supports plugin. Sorry.)
You can use text gem in the plugin.

Updated by shevegen (Robert A. Heiler) over 4 years ago

I would like to see this too - Levensthein distance is used a lot in Bioinformatics to calculate the edit distance between two sequences (in ruby, thus, two strings) - three operations are Edit, Replace, Delete (+1, -1, change information at that position).

I have no particular strong feeling about the name (e. g. distance) though perhaps it should be

require 'math/distance'

or something like that?

Also available in: Atom PDF