Issue #10882 has been updated by Mrlaura (QUANG NGUYEN). Hi Yuki, Kouhei, Robert, and the Ruby maintainers, First, thank you for raising this proposal. I think the original observation remains relevant: Levenshtein distance is a relatively small algorithm with applications across many independent Ruby projects, including spelling correction, search, bioinformatics, data cleaning, and approximate string matching. I also appreciate the discussion about whether the functionality belongs in the standard library or should remain available through specialized gems. After looking at Ruby's existing implementation in DidYouMean, I would like to add a few considerations that may help clarify what a reusable public Levenshtein API should provide. The main question, in my view, is not whether Ruby can calculate Levenshtein distance. It already can. The more interesting question is whether Ruby should expose a stable, documented, reusable edit-distance API, and what guarantees such an API should make. ## 1. Ruby already has an internal Levenshtein implementation The DidYouMean library contains a Levenshtein implementation under: `lib/did_you_mean/levenshtein.rb` The implementation exposes a `distance` method internally, but the module is marked with `:nodoc:`. DidYouMean's SpellChecker also uses Jaro-Winkler similarity and Levenshtein distance as separate stages of its suggestion process. That is useful existing functionality, but I would distinguish an internal implementation detail from a public API intended for arbitrary Ruby applications. An internal implementation can reasonably optimize for its particular callers. A general-purpose API needs a more explicit contract covering: - The definition of one sequence element. - Supported edit operations. - Return-value semantics. - Unicode handling. - Performance guarantees. - Threshold-based comparisons. - Edge cases and error behavior. Reusing the existing implementation may be possible, but promoting it directly to a stable public API would deserve a review of these contracts. ## 2. Prefer an explicit namespace over a generic String#distance method The original proposal considers: ```ruby require "distance" Distance.levenshtein(str1, str2) ``` It also suggests: ```ruby "word".distance("other") ``` I would lean toward the first approach, or another explicitly named and opt-in namespace. The name `String#distance` is convenient, but it does not communicate which distance model is being used. That becomes important as soon as an application introduces: - Levenshtein distance. - Damerau-Levenshtein distance. - Hamming distance. - Weighted edit distance. - Jaro similarity. - Jaro-Winkler similarity. Some of these algorithms return edit costs, while others commonly return normalized similarity scores. Their values are not necessarily interchangeable. For example, a raw Levenshtein distance of 2 is not semantically equivalent to a Jaro-Winkler similarity of 0.82. An explicit API such as: ```ruby Distance.levenshtein(a, b) ``` makes the chosen operation immediately visible. It also avoids adding a very general method name to every String instance. I would favor a small initial API over a broad abstraction that attempts to support every possible string similarity metric. ## 3. The Unicode representation problem should be defined before implementation One important question that did not receive much attention in the original discussion is: **What exactly counts as one character in the distance calculation?** For ASCII strings, this distinction is rarely visible. For Unicode text, however, byte sequences, Unicode code points, and extended grapheme clusters are different units. Consider: ```ruby text = "รฉ" text.bytesize # 2 text.codepoints.length # 1 text.grapheme_clusters.length # 1 ``` Now consider a canonically equivalent representation: ```ruby text = "e\u0301" text.bytesize # 3 text.codepoints.length # 2 text.grapheme_clusters.length # 1 ``` Both strings may appear identical to a user, but they have different underlying code-point sequences. A code-point-based Levenshtein implementation calculates a distance of 2 between these two representations. A grapheme-based implementation operating on the original, unnormalized clusters calculates a distance of 1. After NFC normalization, both representations become identical and their distance becomes 0. All three results can be explained by the chosen comparison model. This does not mean one implementation is necessarily incorrect. It means the sequence representation and normalization policy must be defined. Ruby already provides useful APIs such as: - `String#codepoints` - `String#each_codepoint` - `String#grapheme_clusters` - `String#each_grapheme_cluster` - `String#unicode_normalize` These could support different explicit comparison models without requiring the core edit-distance recurrence to change. ## 4. A small reference implementation illustrates the distinction Here is a simple unit-cost Levenshtein implementation that accepts arrays of arbitrary comparable elements. It is intended as a correctness reference, not as a proposal to replace Ruby's optimized internal implementation. ```ruby def levenshtein_units(a, b) a, b = b, a if b.length > a.length previous = (0..b.length).to_a a.each_with_index do |left, i| current = [i + 1] b.each_with_index do |right, j| cost = left == right ? 0 : 1 current << [ previous[j + 1] + 1, current[j] + 1, previous[j] + cost ].min end previous = current end previous[-1] end ``` This calculates standard Levenshtein distance using insertion, deletion, and substitution, each with unit cost. Its time complexity is O(mn), while auxiliary space is O(min(m,n)). For ordinary strings: ```ruby a = "kitten" b = "sitting" levenshtein_units( a.codepoints, b.codepoints ) # 3 ``` For canonically equivalent Unicode strings: ```ruby a = "รฉ" b = "e\u0301" levenshtein_units( a.codepoints, b.codepoints ) # 2 levenshtein_units( a.grapheme_clusters, b.grapheme_clusters ) # 1 ``` After NFC normalization: ```ruby a = a.unicode_normalize(:nfc) b = b.unicode_normalize(:nfc) levenshtein_units( a.grapheme_clusters, b.grapheme_clusters ) # 0 ``` This illustrates how the same Levenshtein recurrence can operate over different sequence units. For a general-purpose Ruby API, I think the critical design decision is whether to expose these choices directly or provide a well-documented default with more specialized processing left to callers. ## 5. Mathematical Unicode characters expose another interesting case Unicode compatibility characters introduce a different class of comparison problem. Consider: `ABC` `๐๐๐` The second string contains mathematical bold Unicode characters. These are not simply ordinary Latin characters displayed using a different CSS font. They are different Unicode code points. A code-point-based Levenshtein calculation returns: ```ruby a = "ABC" b = "๐๐๐" levenshtein_units( a.codepoints, b.codepoints ) # 3 ``` After NFKC compatibility normalization: ```ruby a = a.unicode_normalize(:nfkc) b = b.unicode_normalize(:nfkc) levenshtein_units( a.codepoints, b.codepoints ) # 0 ``` The distance algorithm has not changed. Only the input representation has changed. This distinction matters in: - Search and indexing. - Duplicate detection. - Usernames and profile text. - Mathematical notation. - Document comparison. - Unicode-styled text. - Multilingual text processing. However, I would not recommend applying NFKC automatically in a general-purpose edit-distance API. Compatibility normalization deliberately removes distinctions that may be meaningful in certain applications. A better design may be to keep normalization explicit and let callers choose the appropriate transformation before comparison. For a detailed discussion of the interaction between Unicode normalization, extended grapheme clusters, and edit distance, the following technical reference may be useful: https://www.levenshtein.net/unicode-and-grapheme-safe-levenshtein ## 6. Threshold-aware distance could be a valuable optimization Another question concerns performance when the caller only wants to know whether two strings are sufficiently similar. For example: "Does the edit distance between these strings exceed 3?" A standard dynamic programming implementation calculates the complete distance even when the caller only requires a threshold decision. An API could optionally support a maximum edit distance: ```ruby Distance.levenshtein( "kitten", "sitting", max_distance: 3 ) ``` One possible contract would return the exact distance if it is at most the threshold, and `nil` otherwise. The exact return-value convention would need discussion, particularly to distinguish an exceeded threshold from an invalid input. Several safe optimizations are possible. **Length-difference filtering** For standard unit-cost Levenshtein distance: `distance(a, b) >= abs(length(a) - length(b))` If the length difference already exceeds the threshold, the calculation can terminate immediately. **Banded dynamic programming** When the maximum permitted distance is small, the implementation can avoid evaluating cells that cannot participate in a valid alignment within the threshold. **Early termination** A correctly implemented threshold-aware dynamic programming algorithm can abandon a candidate when the remaining computation cannot produce a distance within the permitted bound. These techniques can be valuable for spelling correction, approximate search, and large candidate sets. They also raise an API-design question: Should threshold-aware comparison be part of the initial public API, or should it be introduced later as a separate operation? For background on correctness, memory optimization, and bounded Levenshtein computation, this implementation-oriented reference may be useful: https://www.levenshtein.net/levenshtein-implementations ## 7. A public API should have an explicit correctness test suite If a reusable implementation is considered for the standard library, I would suggest a focused test suite covering both ordinary edit-distance behavior and Unicode representation issues. **Basic correctness** - Identical strings return 0. - Empty strings return the length of the nonempty sequence. - One insertion has cost 1. - One deletion has cost 1. - One substitution has cost 1. - Symmetry is preserved. - The triangle inequality holds for standard unit-cost Levenshtein distance. **Standard examples** - `kitten` versus `sitting`: distance 3. - `flaw` versus `lawn`: distance 2. - `Saturday` versus `Sunday`: distance 3. **Algorithm distinction** - `ab` versus `ba`: standard Levenshtein distance 2. This last example is useful because Damerau-Levenshtein permits adjacent transpositions, while ordinary Levenshtein does not. **Unicode behavior** - Precomposed versus decomposed accented characters. - Supplementary-plane Unicode characters. - Emoji sequences with zero-width joiners. - Grapheme clusters containing combining marks. - Mathematical compatibility characters. - Strings with different but compatible encodings. - Invalid byte sequences and explicitly defined encoding errors. **Performance and resource safety** - Highly unequal input lengths. - Empty input on either side. - Large strings with a small distance threshold. - Very long strings requiring a bounded-memory implementation. - Comparisons against a simple full-matrix reference implementation. For optimized implementations, differential testing against a straightforward reference algorithm would be particularly useful. ## 8. Keep the initial public API deliberately small Although there are many opportunities for extensions, I would prefer a minimal and stable first interface. For example: ```ruby require "distance" Distance.levenshtein(a, b) ``` With a clearly documented contract specifying: - Standard unit-cost Levenshtein distance. - Insertion, deletion, and substitution only. - Exact integer return value. - A defined sequence unit. - No implicit Unicode normalization. - Explicit behavior for unsupported encodings. - Predictable memory characteristics. Features such as weighted costs, different sequence units, normalization policies, edit scripts, and maximum-distance limits could be considered separately. There is also a reasonable alternative: keep string-specific comparison in a dedicated library rather than expanding Ruby's standard library. The trade-off deserves explicit discussion. A standard-library API offers consistency and discoverability. A specialized gem offers more flexibility for algorithm variants, Unicode policies, and performance experimentation. The existence of an internal implementation in DidYouMean provides a useful starting point, but it does not automatically settle that architectural question. ## Final thoughts I think this feature request remains interesting because Levenshtein distance sits at the intersection of several important areas of software engineering. It is simultaneously: - A well-defined dynamic programming algorithm. - A reusable sequence-distance metric. - A foundation for spelling correction and approximate matching. - A practical example of why Unicode representation matters. - A building block for search, indexing, and bioinformatics. The central design question is not simply where to place the implementation. It is whether Ruby can provide a public contract that clearly defines what is being compared, which operations are permitted, and what callers can rely on across Ruby versions. I would be interested in hearing whether the maintainers see value in a small, namespaced API built around standard unit-cost Levenshtein distance, with Unicode normalization and more specialized comparison models remaining explicit responsibilities of callers. For transparency, I contribute to the technical resources at Levenshtein.net referenced above. The links are included for the specific implementation and Unicode comparison details discussed here, not as proposed dependencies. Thank you again for the original proposal and for the work already done in Ruby's text-processing ecosystem. ---------------------------------------- Feature #10882: Provide Levenshtein distance implementation as part of stdlib https://bugs.ruby-lang.org/issues/10882#change-119464 * Author: yuki24 (Yuki Nishijima) * Status: Open ---------------------------------------- [Levenshtein distance algorithm](http://en.wikipedia.org/wiki/Levenshtein_distance) 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](https://github.com/ruby/rake/pull/29)). 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. ```ruby require 'distance' Distance.levenshtein(str1, str2) ``` It would also be interesting to have `#distance` method on `String`: ```ruby "word".distance("other") ``` which is implemented as: ```ruby 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](http://en.wikipedia.org/wiki/Jaro%E2%80%93Winkler_distance)). -- https://bugs.ruby-lang.org/