levenshtein distance javascript

Cadena difusa de Java que coincide con los nombres

Question

Tengo un proceso de carga de datos CSV autónomo que codifiqué en Java que tiene que usar un poco de coincidencia de cadenas difusas. Definitivamente no es ideal, pero no tengo muchas opciones. Estoy emparejando con un nombre y apellido y caché todas las posibilidades al comienzo de una carrera. Después de encontrar la coincidencia, necesito que esa persona se oponga a varios lugares durante la ejecución. Objects.hashCode() el Objects.hashCode() de Objects.hashCode() para crear un hash a partir del nombre y el apellido.

El mecanismo de almacenamiento en caché se ve así:

Map<Integer,PersonDO> personCache = Maps.newHashMap();
for(PersonDO p: dao.getPeople()) {
    personCache.put(Objects.hashCode(p.getFirstName(),p.getLastName()), p);
}

La mayoría de las veces recibo aciertos con el nombre y el apellido, pero cuando falla, me estoy StringUtils.getLevenshteinDistance() del uso de StringUtils.getLevenshteinDistance() Apache para intentar igualarlo. Así es como va el flujo lógico coincidente:

    person = personCache.get(Objects.hashCode(firstNameFromCSV,lastNameFromCSV));
    if(person == null) {//fallback to fuzzy matching
        person = findClosetMatch(firstNameFromCSV+lastNameFromCSV);

    }

Este es el método findClosetMatch() :

private PersonDO findClosetMatch(String name) {
    int min = 15;//initial value
    int testVal=0;
    PersonDO matchedPerson = null;
    for(PersonDO person: personCache.values()) {
        testVal = StringUtils.getLevenshteinDistance(name,person.getFirstName()+person.getLastName());
        if( testVal < min ) {
            min = testVal;
            matchedPerson = person;
        }
    }
    if(matchedPerson == null) {
        throw new Exception("Unable to find person: " + name) 
    }
    return matchedPerson;
}

Esto funciona bien con errores de ortografía simples, errores tipográficos y nombres abreviados (es decir, Mike-> Michael), pero cuando pierdo por completo uno de los nombres entrantes en el caché, termino devolviendo una coincidencia positiva falsa. Para evitar que esto suceda, establezco el valor mínimo en findClosetMatch() en 15 (es decir, no más de 15 caracteres desactivados); Funciona la mayor parte del tiempo, pero aún tengo algunos errores de coincidencia: Mike Thompson golpea a Mike Thomas etc.

Además de encontrar una manera de obtener una clave principal en el archivo que se está cargando, ¿alguien ve una manera de mejorar este proceso? ¿Algún otro algoritmo coincidente que pueda ayudar aquí?

Answer 1

1. ¿Usa usted db para realizar la búsqueda? Usando expresiones regulares en su selección, o use el operador LIKE

2. Analice su base de datos e intente crear una tabla Huffman-tree o Varios para realizar una búsqueda de valor clave.

Answer 2

Cuando observo este problema, observo algunos datos clave para basar algunas mejoras en:

Hechos y observaciones

1. Max iteraciones de 1000.
2. 15 para Levenshtein la distancia me suena muy alta.
3. Usted sabe, al observar empíricamente los datos, cómo debería ser su coincidencia aproximada (existen muchos casos para la comparación difusa y cada uno depende de por qué los datos son malos).
4. Al construir esta API, puede conectar muchos algoritmos, incluidos el suyo y otros como Soundex , en lugar de depender de uno solo.

Requerimientos

He interpretado que su problema requiere las siguientes dos cosas:

1. Tiene objetos PersonDO que desea buscar a través de una clave que se basa en el nombre. Parece que desea hacer esto porque necesita un PersonDO preexistente de los cuales existe uno por nombre único , y el mismo nombre puede aparecer más de una vez en su ciclo / flujo de trabajo.
2. Necesita "coincidencia aproximada" porque los datos entrantes no son puros. Para los fines de este algoritmo, asumiremos que si un nombre "coincide", siempre debe usar la misma PersonDO (en otras palabras, el identificador único de una persona es su nombre, que obviamente no es el caso en la vida real, pero parece trabajar para ti aqui).

Implementación

A continuación, veamos algunas mejoras en su código:

1. Limpieza: manipulación de hashcode innecesaria.

No necesitas generar códigos hash por ti mismo. Esto confunde el tema un poco.

Simplemente estás generando un código hash para la combinación del nombre + apellido. Esto es exactamente lo que HashMap haría si le dieras la cadena concatenada como clave. Entonces, simplemente haga eso (y agregue un espacio, en caso de que queramos revertir el análisis primero / último de la clave más adelante).

Map<String, PersonDO> personCache = Maps.newHashMap();

public String getPersonKey(String first, String last) {
  return first + " " + last;
}

...
// Initialization code
for(PersonDO p: dao.getPeople()) {
    personCache.put(getPersonKey(p.getFirstName(), p.getLastName()), p);
}

2. Limpieza: construya una función de recuperación para realizar la búsqueda.

Como hemos cambiado la clave en el mapa, necesitamos cambiar la función de búsqueda. Vamos a construir esto como una mini-API. Si siempre supiéramos la clave exactamente (es decir, las ID únicas), por supuesto, solo Map.get . Así que comenzaremos con eso, pero como sabemos que tendremos que agregar una coincidencia aproximada, agregaremos una envoltura donde esto pueda suceder:

public PersonDO findPersonDO(String searchFirst, String searchLast) {
  return personCache.get(getPersonKey(searchFirst, searchLast));
}

3. Construye un algoritmo de coincidencia difusa usando puntuación.

Tenga en cuenta que ya que está utilizando Guava, he usado algunas conveniencias aquí ( Ordering , ImmutableList , Doubles , etc.).

Primero, queremos preservar el trabajo que hacemos para averiguar qué tan cerca está una coincidencia. Haz esto con un POJO:

class Match {
   private PersonDO candidate;
   private double score; // 0 - definitely not, 1.0 - perfect match

   // Add candidate/score constructor here
   // Add getters for candidate/score here

   public static final Ordering<Match> SCORE_ORDER =
       new Ordering<Match>() {
     @Override
     public int compare(Match left, Match right) {
       return Doubles.compare(left.score, right.score);
     }
   };
}

A continuación, creamos un método para calificar un nombre genérico. Deberíamos anotar nombres y apellidos por separado, porque reduce el ruido. Por ejemplo, no nos importa si el nombre de pila coincide con alguna parte del apellido, a menos que su nombre de pila se encuentre accidentalmente en el campo de apellido o viceversa, que debe tener en cuenta de manera intencional y no accidental (lo abordaremos más adelante) .

Tenga en cuenta que ya no necesitamos una "distancia máxima de levenshtein". Esto se debe a que los normalizamos a la longitud y más adelante elegiremos la coincidencia más cercana. 15 adiciones / ediciones / eliminaciones de 15 caracteres parece muy alto, y como hemos minimizado el problema del nombre / apellido en blanco al anotar los nombres por separado, probablemente ahora podríamos elegir un máximo de 3-4 si lo desea (anotar cualquier otra cosa como un 0 ).

// Typos on first letter are much more rare.  Max score 0.3
public static final double MAX_SCORE_FOR_NO_FIRST_LETTER_MATCH = 0.3;

public double scoreName(String searchName, String candidateName) {
  if (searchName.equals(candidateName)) return 1.0

  int editDistance = StringUtils.getLevenshteinDistance(
      searchName, candidateName);

  // Normalize for length:
  double score =
      (candidateName.length() - editDistance) / candidateName.length();

  // Artificially reduce the score if the first letters don''t match
  if (searchName.charAt(0) != candidateName.charAt(0)) {
    score = Math.min(score, MAX_SCORE_FOR_NO_FIRST_LETTER_MATCH);
  }

  // Try Soundex or other matching here.  Remember that you don''t want
  // to go above 1.0, so you may want to create a second score and
  // return the higher.

  return Math.max(0.0, Math.min(score, 1.0));
}

Como se mencionó anteriormente, usted podría agregar algoritmos de emparejamiento de palabras de terceros u otros y obtener conocimiento compartido de todos ellos.

Ahora, vamos a través de toda la lista y anotamos cada nombre. Tenga en cuenta que he añadido un lugar para "ajustes". Los ajustes pueden incluir:

• Reversión : si el PersonDO es "Benjamin Franklin", pero la hoja CSV puede contener "Franklin, Benjamin", entonces deberá corregir los nombres invertidos. En este caso, es probable que desee agregar un método checkForReversal que anote el nombre al revés y checkForReversal ese puntaje si es significativamente más alto. Si coincidiera exactamente a la inversa, le darías un puntaje de 1.0 .
• Abreviaturas : es posible que desee darle al puntaje un bono adicional si el nombre / apellido coincide de manera idéntica y el otro está completamente contenido en el candidato (o viceversa). Esto podría indicar una abreviatura. Es posible que desee dar un subsidio de Levenshtein de 1 a la cuenta de "Nick / Nicholas" o similar.
• Apodos comunes : puede agregar un conjunto de apodos conocidos ("Robert -> Bob, Rob, Bobby, Robby") y luego anotar el nombre de la búsqueda contra todos ellos y obtener la puntuación más alta. Si coincide con alguno de estos, probablemente le darías un puntaje de 1.0 .

Como puede ver, construir esto como una serie de API nos da ubicaciones lógicas para ajustar esto fácilmente al contenido de nuestro corazón.

Encendido con el algoritmo:

public static final double MIN_SCORE = 0.3;

public List<Match> findMatches(String searchFirst, String searchLast) {
  List<Match> results = new ArrayList<Match>();

  // Keep in mind that this doesn''t scale well.
  // With only 1000 names that''s not even a concern a little bit, but
  // thinking ahead, here are two ideas if you need to:
  // - Keep a map of firstnames.  Each entry should be a map of last names.
  //   Then, only iterate through last names if the firstname score is high
  //   enough.
  // - Score each unique first or last name only once and cache the score.
  for(PersonDO person: personCache.values()) {
    // Some of my own ideas follow, you can tweak based on your
    // knowledge of the data)

    // No reason to deal with the combined name, that just makes things
    // more fuzzy (like your problem of too-high scores when one name
    // is completely missing).
    // So, score each name individually.

    double scoreFirst = scoreName(searchFirst, person.getFirstName());
    double scoreLast = scoreName(searchLast, person.getLastName());

    double score = (scoreFirst + scoreLast)/2.0;

    // Add tweaks or alternate scores here.  If you do alternates, in most
    // cases you''ll probably want to take the highest, but you may want to
    // average them if it makes more sense.

    if (score > MIN_SCORE) {
      results.add(new Match(person, score));
    }
  }

  return ImmutableList.copyOf(results);
}

Ahora modificamos su findClosestMatch para obtener solo el más alto de todas las coincidencias (lanza la NoSuchElementException si no hay ninguna en la lista).

Posibles ajustes:

• Es posible que desee verificar si varios nombres obtuvieron puntajes muy cercanos, e informar al finalista (ver a continuación), u omitir la fila para la elección manual más adelante.
• Es posible que desee informar de cuántas otras coincidencias hubo (si tiene un algoritmo de puntuación muy ajustado).

Código:

public Match findClosestMatch(String searchFirst, String searchLast) {
  List<Match> matches = findMatch(searchFirst, searchLast);

  // Tweak here

  return Match.SCORE_ORDER.max(list);
}

.. y luego modificar nuestro getter original:

public PersonDO findPersonDO(String searchFirst, String searchLast) {
  PersonDO person = personCache.get(getPersonKey(searchFirst, searchLast));
  if (person == null) {
    Match match = findClosestMatch(searchFirst, searchLast);
    // Do something here, based on score.
    person = match.getCandidate();
  }
  return person;
}

4. Informe "borrosidad" de manera diferente.

Finalmente, notará que findClosestMatch no solo devuelve a una persona, sino que también devuelve una Match . Esto es para que podamos modificar el programa para tratar las coincidencias difusas de las coincidencias exactas.

Algunas cosas que probablemente quieras hacer con esto:

• Suposiciones del informe: guarde todos los nombres que coincidan en función de la falta de claridad en una lista para que pueda informarlos y auditarlos más tarde.
• Valide primero: es posible que desee agregar un control para activar y desactivar si realmente usa las coincidencias difusas o simplemente las reporta para que pueda masajear los datos antes de que ingresen.
• Definición de datos: es posible que desee calificar las ediciones realizadas en una coincidencia aproximada como "inciertas". Por ejemplo, podría rechazar cualquier "edición importante" de un registro de Persona si la coincidencia fue confusa.

Conclusión

Como puedes ver, no es demasiado código para hacerlo tú mismo. Es dudoso que alguna vez haya una biblioteca que prediga los nombres tan bien como usted pueda conocer los datos usted mismo.

Desarrollar esto en partes como lo he hecho en el ejemplo anterior le permitirá iterar y modificar fácilmente e incluso conectar bibliotecas de terceros para mejorar su puntuación en lugar de depender de ellas por completo: fallas y todo.

Answer 3

Esto es lo que hice con un caso de uso similar:

• Haga coincidir el nombre y el apellido por separado, esto hará una coincidencia más precisa y eliminará algunos de los falsos positivos:

distance("a b", "a c") is 33% max(distance("a", "a"), distance("b", "c")) is 100%

• Base su criterio de distancia min en la longitud de las cadenas de entrada, es decir, 0 es para cadenas más cortas que 2 símbolos, 1 es para cadenas más cortas que 3 símbolos.

int length = Math.min(s1.length(), s2.length);

int min;

if(length <= 2) min = 0; else
if(length <= 4) min = 1; else
if(length <= 6) min = 2; else
...

Estos dos deben trabajar para su entrada.

Answer 4

No hay la mejor solución, de todos modos tienes que lidiar con algún tipo de heurística. Pero puede buscar otra implementación a distancia de Levenshtein (o implementarla usted mismo). Esta implementación debe dar diferentes puntuaciones a diferentes operaciones de caracteres (inserción, eliminación) para diferentes personajes. Por ejemplo, puede dar puntuaciones más bajas para pares de caracteres que están cerca del teclado. Además, puede calcular dinámicamente el umbral de distancia máxima en función de la longitud de una cadena.

Y tengo un consejo de rendimiento para usted. Cada vez que calcula la distancia Levenshtein, se realizan operaciones n * m, donde n y m son longitudes de cadenas. Hay un autómata Levenshtein que construyes una vez y luego evalúas muy rápido para cada cadena. Tenga cuidado, ya que la evaluación de NFA es muy costosa, primero debe convertirla a DFA.

Quizás debas echarle un vistazo a Lucene . Espero que incluya todas las capacidades de búsqueda difusa que necesita. Incluso puede utilizar su búsqueda de texto completo DBMS, si es compatible. Por ejemplo, PostgreSQL soporta texto completo.