levenshteinDistance does not support unicode characters

Abierto
#307 0 comentarios 0 reacciones 0 asignados Ver en GitHub

Nadie ha tomado este issue todavía.

Evaluación

Dificultad
2/5
Tiempo estimado
1-3 horas
Aptitud para principiantes
45/100
Tipo de issue
Error
Claridad
Bien especificado
Estado de actividad
Estancado
Stack tecnológico
javascript
Área
devtools

Línea de trabajo

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.

Escrito por el modelo de indexación a partir del texto del issue.

Descripción

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))

Lenguaje dominante
JavaScript
Estrellas
197k
Forks
31k
Sin PR fusionados en 30 d

Guía de contribución

Abrir la guía de contribución

Primeros pasos

  1. Lee el issue completo y luego la guía de contribución del proyecto.
  2. Comenta en el issue que vas a ocuparte — evita que dos personas hagan lo mismo.
  3. Haz un fork del repositorio y trabaja en una rama.
  4. Abre un pull request que haga referencia al número del issue.

Más de trekhleb/javascript-algorithms

Todos los issues de trekhleb/javascript-algorithms

Issues similares

Más issues de JavaScript

Recibe los nuevos issues en tu correo

Un resumen breve de issues de GitHub para principiantes.