levenshteinDistance does not support unicode characters

Ouverte
#307 0 commentaires 0 réactions 0 personnes assignées Voir sur GitHub

Personne n'a encore pris cette issue.

Évaluation

Difficulté
2/5
Temps estimé
1-3 heures
Accessibilité débutants
45/100
Type d'issue
Bug
Clarté
Clairement spécifiée
Activité
À l'abandon
Stack technique
javascript
Domaine
devtools

Piste de recherche

Start by locating the levenshteinDistance implementation and its existing tests. Reproduce the astral Unicode case from the issue, then add regression coverage for it and verify that the distance for '\u{1f431}' versus an empty string is 1.

Rédigé par le modèle d'indexation à partir du texte de l'issue.

Description

Details:

levenshteinDistance does not support unicode characters outside of the BMP range properly.
Step to reproduce: expect(levenshteinDistance('\u{1f431}', '')).toBe(1) // got 2

Fix

I can issue a PR with the fix https://github.com/dubzzz/javascript-algorithms/commit/856ba360134956cca2bed165929a4d4409537201

How did I find it?

Thanks to property based testing framework fast-check.
The property was the following:

import fc from 'fast-check';

fc.assert(
    fc.property(
      fc.fullUnicodeString(), fc.fullUnicodeString(),
      fc.fullUnicodeString(), fc.fullUnicodeString(),
      fc.fullUnicodeString(),
      (aBegin, aEnd, bBegin, bEnd, common) =>
        levenshteinDistance(aBegin + common + aEnd, bBegin + common + bEnd)
          <= Math.max([...aBegin].length, [...bBegin].length) + Math.max([...aEnd].length, [...bEnd].length)
    )
  )

Or:

for any a and b - strings
such that a = aBegin + common + aEnd and b = bBegin + common + bEnd
levenshteinDistance(a, b) is at most max(numChars(aBegin), numChars(bBegin)) + max(numChars(aEnd), numChars(bEnd))

Langage dominant
JavaScript
Étoiles
197k
Forks
31k
Aucune PR mergée en 30 j

Guide de contribution

Ouvrir le guide de contribution

Par où commencer

  1. Lisez l'issue en entier, puis le guide de contribution du projet.
  2. Signalez en commentaire que vous la prenez — cela évite que deux personnes fassent le même travail.
  3. Forkez le dépôt et travaillez sur une branche.
  4. Ouvrez une pull request qui référence le numéro de l'issue.

Autres issues de trekhleb/javascript-algorithms

Toutes les issues de trekhleb/javascript-algorithms

Issues similaires

Plus d'issues JavaScript

Recevez les nouvelles issues par e-mail

Un résumé court des issues GitHub adaptées aux débutants.