Repository navigation
[RFC]: Hamming distance between two strings #836
Description
Description
This RFC proposes adding a function to calculate the Hamming distance between two strings.
The function should have the following signature (a: string, b: string): number.
The function should take two strings as arguments and return the Hamming distance between them. The Hamming distance is defined as the number of characters that have to be changed to convert one string to the other. Since it only allows substitutions, it can only be used to compare strings of the same length.
Additionally, in order to account for code points and grapheme clusters, we should add separate packages for dealing with each, as the underlying algorithms are likely to differ. We then can provide a more general API which unifies the underlying algorithms. Accordingly, we should create the following packages:
-
@stdlib/string/base/distances/hamming: compares UTF-16 code units. -
@stdlib/string/base/distances/hamming-code-points: compares Unicode code points. -
@stdlib/string/base/distances/hamming-grapheme-clusters: compares grapheme clusters (i.e., visual characters)
Once the above are completed, we can add
-
@stdlib/string/distances/hamming: unifies the above "base" packages and provides an option for specifying the computation "mode" (i.e.,code_units,code_points, orgrapheme_clusters, withgrapheme_clustersbeing the default).
Related Issues
Related issues #151.
Questions
No.
Other
No.
Checklist
- I have read and understood the Code of Conduct.
- Searched for existing issues and pull requests.
- The issue name begins with
RFC:.
Activity
Ahtaxam commentedon Apr 30, 2023
kgryte commentedon Jul 15, 2023
feat: add Hamming distance between two strings
feat: add `string/base/distances/hamming` (#1166)
marsian83 commentedon Feb 29, 2024
Hi, I would like to work on this
Can I be assgined this
kgryte commentedon Feb 29, 2024
@marsian83 Sure. Would you be open to working on
@stdlib/string/base/distances/hamming-code-points?kgryte commentedon Feb 29, 2024
Note that the UTF-16 code unit implementation has already been added. The code points implementation should iterate over Unicode code points (e.g., most Unicode characters and some emoji). You can find other code points implementation in the
string/base/*namespace.marsian83 commentedon Mar 1, 2024
Sure, I'll see how these work.
Thanks for the reference
mayankkamboj47 commentedon Mar 2, 2024
@kgryte Hello ! Can I work on the grapheme clusters part ?
kgryte commentedon Mar 2, 2024
@mayankkamboj47 Sure. You'll probably want to rely on
next-grapheme-cluster-breakin order to derive string indices for the purpose of comparing substrings.Pratik772846 commentedon Mar 5, 2024
@kgryte @Planeshifter If noone is working on @stdlib/string/base/distances/hamming-code-points, can i work on it?
JayPokale commentedon Mar 19, 2024
@kgryte I created a pull request for Hamming distance between Unicode characters (#1948 ). Can you please review it.
Looking forward for your reply.
JayPokale commentedon Mar 27, 2024
Hello there, can someone please review PR #1948 on
@stdlib/string/base/distances/hamming-code-points.MynameisSanskar commentedon Nov 8, 2024
Hi @kgryte,
I am interested in contributing to the Hamming distance feature for comparing Unicode code points in the
@stdlib/string/base/distances/hamming-code-pointspackage. Could you please assign this task to me?Looking forward to your guidance and feedback!
Thank you!``
Anant1004 commentedon Nov 10, 2024
Hello, everyone ! I'm interested in contributing to the Hamming distance feature. I noticed that parts of the implementation for different comparison modes (UTF-16 code units, Unicode code points, and grapheme clusters) have been discussed and some PRs have been submitted. Could someone please update me on the current status of this issue and let me know if there are any open tasks I could help with? Thank you !
kgryte commentedon Nov 18, 2024
@MynameisSanskar @Anant1004 As tracked in the OP, calculating the distance between two strings when comparing code points has not been completed. Initial attempt to add support can be found in #1948, but that PR stalled.