Cadena difusa de Java que coincide con los nombres

Solución:

Mientras miro este problema, noto un par de hechos clave en los que basar algunas mejoras:

Hechos y observaciones

1. Iteraciones máximas de 1000.
2. 15 para sonidos de distancia de Levenshtein De Verdad alto para mí.
3. Ya sabe, al observar los datos empíricamente, cómo debería verse su coincidencia aproximada (hay muchos casos de coincidencia aproximada y cada uno depende de por qué los datos son malos).
4. Al crear esta API similar a la que usted tiene, podría conectar muchos algoritmos, incluidos el suyo y otros como Soundex, en lugar de depender de uno solo.

Requisitos

He interpretado que su problema requiere las siguientes dos cosas:

1. Tú tienes PersonDO objetos que desea buscar mediante una clave que se basa en el nombre. Parece que quieres hacer esto porque necesitas un preexistente PersonDO 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 una “coincidencia aproximada” porque los datos entrantes no son puros. Para los propósitos de este algoritmo asumiremos que si un nombre “coincide”, siempre debe usar el mismo 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 funcionar para usted aquí).

Implementación

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

1. Limpieza: manipulación innecesaria del código hash.

No es necesario que usted mismo genere códigos hash. Esto confunde un poco el problema.

Simplemente está 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 invertir 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: cree una función de recuperación para realizar la búsqueda.

Dado que hemos cambiado la clave en el mapa, necesitamos cambiar la función de búsqueda. Construiremos esto como una mini-API. Si siempre supiéramos la clave exactamente (es decir, ID únicos), por supuesto, solo usaríamos Map.get. Entonces, comenzaremos con eso, pero como sabemos que necesitaremos agregar coincidencias aproximadas, agregaremos un contenedor donde esto pueda suceder:

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

3. Cree usted mismo un algoritmo de coincidencia difusa utilizando la puntuación.

Tenga en cuenta que, dado que está usando Guava, he usado algunas comodidades 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 puntuar un nombre genérico. Debemos puntuar el nombre y el apellido por separado, porque reduce el ruido. Por ejemplo, no nos importa si el nombre coincide con alguna parte del apellido: a menos que su nombre pueda estar accidentalmente en el campo de apellido o viceversa, lo cual debe tener en cuenta de manera intencional y no accidental (abordaremos esto 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 elegiremos la coincidencia más cercana más adelante. 15 caracteres agregados / editados / eliminados parece muy alto, y dado que hemos minimizado el problema del nombre / apellido en blanco al calificar los nombres por separado, probablemente ahora podríamos elegir un máximo de 3-4 si lo desea (calificando 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, puede conectar un tercero u otros algoritmos de coincidencia de palabras y aprovechar el conocimiento compartido de todos ellos.

Ahora, revisamos toda la lista y puntuamos cada nombre. Tenga en cuenta que he añadido un lugar para “retoques”. Los ajustes pueden incluir:

• Inversión: Si PersonDO es “Benjamin Franklin”, pero la hoja CSV puede contener “Franklin, Benjamin”, entonces querrá corregir los nombres invertidos. En este caso, probablemente querrá agregar un método checkForReversal que puntuaría el nombre al revés y tomaría esa puntuación si es significativamente más alta. Si coincidiera exactamente al revés, le daría una puntuación de 1.0.
• Abreviaturas: Es posible que desee darle a la puntuación un aumento adicional si el nombre / apellido coincide de manera idéntica y el otro es totalmente contenido en el candidato (o viceversa). Esto podría indicar una abreviatura, como “Samantha / Sam”.
• Apodos comunes: Puede agregar un conjunto de apodos conocidos (“Robert -> Bob, Rob, Bobby, Robby”) y luego puntuar el nombre de búsqueda contra todos ellos y obtener la puntuación más alta. Si coincide con alguno de estos, probablemente le daría una puntuación de 1.0.

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

Sigamos 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 todos los partidos (throws NoSuchElementException si no hay ninguno en la lista).

Posibles ajustes:

• Es posible que desee verificar si varios nombres obtuvieron puntajes muy cercanos e informar a los subcampeones (ver a continuación) o omitir la fila para la elección manual más adelante.
• Es posible que desee informar 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 la “confusión” de forma diferente.

Finalmente, notarás que findClosestMatch no solo devuelve una persona, devuelve un Match – Esto es para que podamos modificar el programa para tratar las coincidencias difusas de manera diferente a las coincidencias exactas.

Algunas cosas que probablemente quieras hacer con esto:

• Informar conjeturas: Guarde todos los nombres que coincidan en función de la falta de claridad en una lista para que pueda informarlos y puedan ser auditados más tarde.
• Validar primero: Es posible que desee agregar un control para encender y apagar, ya sea que realmente use las coincidencias difusas o simplemente las informe para que pueda analizar los datos antes de que ingresen.
• Defenesividad de los datos: Es posible que desee calificar cualquier modificación realizada en una coincidencia aproximada como “incierta”. Por ejemplo, puede no permitir “ediciones importantes” en un registro de persona si la coincidencia es imprecisa.

Conclusión

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

Construir esto en piezas como lo hice en el ejemplo anterior le permite iterar y ajustar fácilmente e incluso conectar bibliotecas de terceros para mejorar su puntuación en lugar de depender de ellas por completo, con fallas y todo.

1. ¿Utiliza su base de datos para realizar búsquedas? Usando expresión regular en su selección o uso LIKE operador

2. Analice su base de datos e intente construir un árbol de Huffman o una tabla de varios para realizar una búsqueda de valor-clave.

No existe la mejor solución, de todos modos tienes que lidiar con algún tipo de heurística. Pero puede buscar otra implementación de distancia de Levenshtein (o implementarla usted mismo). Esta implementación debe dar diferentes puntajes 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 en el teclado. Además, puede calcular dinámicamente el umbral de distancia máximo en función de la longitud de una cuerda.

Y tengo un consejo de rendimiento para ti. Cada vez que calcula la distancia de Levenshtein, se realizan n * m operaciones, donde norte y metro son longitudes de cuerdas. Hay un autómata de Levenshtein que se construye una vez y luego se evalúa muy rápido para cada cadena. Tenga cuidado, dado que NFA es muy costoso de evaluar, primero debe convertirlo a DFA.

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

---

---

Utiliza Nuestro Buscador