Deseo crear una difusa algoritmo de búsqueda.
Sin embargo, después de horas de investigación realmente estoy luchando.

Quiero crear un algoritmo que realiza una búsqueda aproximada en una lista de nombres de las escuelas.

Esto es lo que he visto hasta el momento:

La mayoría de mis investigaciones seguir apuntando a «cadena de métricas» en Google y Stackoverflow, tales como:

  • Distancia de Levenshtein
  • Damerau-distancia de Levenshtein
  • Needleman–Wunsch algoritmo

Sin embargo esto sólo le da una puntuación de cómo similar 2 cadenas. La única manera en que puedo pensar de la aplicación como un algoritmo de búsqueda es realizar una búsqueda lineal y ejecución de la cadena de métrica algoritmo para cada una de las cuerdas y la devolución de las cadenas con puntuaciones por encima de un cierto umbral. (Al principio yo tenía mis cadenas almacenadas en un árbol trie, pero obviamente, esto no me ayuda aquí!)

Aunque esto no es una mala idea para listas pequeñas, sería problemático para las listas con digamos 100.000 nombres, y el usuario ha realizado muchas consultas.

Otro algoritmo he mirado es el corrector método, donde se acaba de hacer una búsqueda de todas las posibles faltas de ortografía. Sin embargo, esto también es altamente ineficiente, ya que requiere de más de 75.000 palabras para una palabra de longitud 7 y la cantidad de errores de sólo 2.

Lo que necesito?

Puede alguien por favor, me sugieren un buen eficiente aproximada algoritmo de búsqueda. con:

  • Nombre del algoritmo
  • Cómo funciona o un enlace a cómo funciona
  • Pro y los contras y cuándo es mejor utilizar (opcional)

Entiendo que todos los algoritmos tienen sus pros y sus contras y no hay mejor algoritmo.

  • Mira esto, a ver si ayuda: stackoverflow.com/questions/491148/…
  • Los buenos son complicados, así que usted puede ser que desee considerar un off-the-shelf aplicación como Lucene.
  • Es posible crear un árbol Ternario con un método de búsqueda que calcula la distancia de edición sobre la marcha a medida que se desciende en el árbol. No es fácil, pero he hecho un antes y funciona.
InformationsquelleAutor Yahya Uddin | 2015-09-01

4 Comentarios

  1. 33

    Teniendo en cuenta que estamos tratando de hacer una búsqueda aproximada en una lista de nombres de escuela, no creo que quiera ir tradicionales de similitud de cadenas como la distancia de Levenshtein. Mi suposición es que usted está tomando la entrada de un usuario (ya sea de entrada de teclado o hablado por teléfono), y desea encontrar rápidamente la coincidencia de la escuela.

    Distancia métricas decir que el parecido entre dos cadenas se basan en las sustituciones, deleciones e inserciones. Pero los algoritmos realmente no dicen nada acerca de que tan similares son las cadenas son como palabras en un lenguaje humano.

    Considerar, por ejemplo, las palabras «smith», «smythe,» y «hirió». Puedo ir de «smythe» a «smith» en dos pasos:

    smythe -> smithe -> smith
    

    Y de «hirió» a «smith» en dos pasos:

    smote -> smite -> smith
    

    Así que los dos tienen la misma distancia como cadenas, pero como palabras, son significativamente diferentes. Si alguien le dijera (lenguaje hablado) que él estaba buscando «Symthe la Universidad,» que le es casi seguro decir, «Oh, creo que te refieres Smith.» Pero si alguien dice «Hirió a la Universidad,» usted no tiene ninguna idea de lo que estaba hablando.

    Lo que usted necesita es un fonética algoritmo como Soundex o Metaphone. Básicamente, los algoritmos de romper una palabra en fonemas y crear una representación de cómo la palabra se pronuncia en la lengua hablada. A continuación, puede comparar el resultado frente a un conocido de la lista de palabras para encontrar una coincidencia.

    Tal sistema sería mucho más rápido que utilizando una distancia métrica. Considere la posibilidad de que con una distancia métrica, es necesario comparar la entrada del usuario con cada palabra de la lista para obtener la distancia. Que es computacionalmente costoso y los resultados, como he demostrado con «smith» y «hirió» puede ser ridículamente malo.

    El uso de un algoritmo fonético, se crea el fonema representación de cada una de sus palabras conocidas y colocarlo en un diccionario (un hash mapa o posiblemente un trie). Que un único costo de inicio. A continuación, cuando el usuario introduce un término de búsqueda, se crea el fonema representación de su entrada y la busque en el diccionario. Que es mucho más rápido y produce resultados mucho mejores.

    Considerar también que cuando la gente escribe mal los nombres propios, que son casi siempre la primera letra a la derecha, y más a menudo que no pronunciar la palabra suena como la real palabra de lo que ellos estaban tratando de hechizo. Si ese es el caso, entonces la fonética, los algoritmos son definitivamente el camino a seguir.

    • Esto se ve bien. Gran sugerencia! Un problema que tengo es que no hay ningún intento de verificación para accidental mistypes por la pulsación de una tecla adyacente por ejemplo, hacer clic en «s» en lugar de «a». Hay un camino medio. [También Metaphone 3 siendo comercial es un poco de una put off]. Pero buena sugerencia nonethe menos
    • Yo no se preocupe demasiado acerca de Metaphone 3 siendo comercial. Soundex funciona bastante bien. No he usado Metaphone, así que no puedo decir lo bien que funciona.
    • Esperando que el algoritmo lo suficientemente resistente como para notar una equivocado letra (‘l’ para la ‘s’ o ‘s’ para ‘a’, etc.) es más difícil. Sospecho que si el algoritmo devuelve ningún resultado, o devuelto completamente inadecuado de los resultados, el usuario se daría cuenta de su error y corregirlo. Sin embargo, puede hacer un enfoque híbrido. Crear un trie de todos los nombres y su búsqueda si la fonética algoritmo devuelve nada o muy poco. Miren cómo Scrabble y otros juegos de palabras son capaces de rellenar en letras que faltan o decirle lo que las palabras pueden ser hechos a partir de una bolsa de cartas, etc.
    • Si la respuesta resuelve tu problema, se consideraría la posibilidad de marcar como aceptado?
  2. 5

    Estás confuso, borroso de los algoritmos de búsqueda de la aplicación: una búsqueda aproximada de una palabra puede devolver 400 resultados de todas las palabras que han distancia de Levenshtein de, digamos, 2. Pero, para que el usuario tiene para mostrar sólo la parte superior 5-10.

    De la implementación sabio, podrás pre-proceso de todas las palabras en el diccionario y guardar los resultados en una base de datos. El popular palabras (y sus fuzzy-le gusta) será guardado en la memoria caché de la capa de modo que usted no tiene que golpear a la DB para cada solicitud.

    Usted puede agregar una IA capa que se añade el más común de los errores de ortografía y agregarlos a la base de datos. Y etc.

    • Cuando usted dice «procesarlos» mis palabras, ¿cómo puedo hacer eso sin la consulta. Levenshtein sólo puede ser calculado en contra de la cadena de consulta, creo que debe ser dado por el usuario
    • no tome nada fuera de su contexto 🙂 me escribió: «pre-proceso de todas las palabras en el diccionario» (el «diccionario» en este aspecto puede ser una lista de todas las escuelas y todas las opciones de las cadenas que han distancia de Levenshtein de 1-2) este es un proceso largo que te quedarás sin conexión y por el tiempo que hayas terminado, tendrás todas las conexiones entre las palabras en el diccionario almacenado en usted DB.
    • Así que esto es básicamente «corrector de método». Por desgracia, como se menciona en la pregunta, este enfoque es altamente ineficiente en términos de memoria (a pesar de ser eficiente en términos de cómputo) ya que se requiere de más de 75.000 entradas para una palabra de longitud 7. Ahora, si yo tuviera 100.000 entradas, que sería una ingente cantidad de registros. Por no hablar de que la mayoría de los nombres de escuela exceden de 7 caracteres.
    • no es muy ineficiente en términos de memoria, es muy ineficiente en términos de almacenamiento. Usted debe decidir lo que se desea almacenar en caché basado en la mayoría de los casos. Y cierto, siempre hay un trade-off. Tal vez usted no está buscando a utilizar algoritmos fuzzy para empezar, y si ese es el caso de Jim sugerencia podría satisfacer mejor!
    • Lo sentimos, el almacenamiento es a lo que me refería
  3. 3

    Escribí un artículo acerca de cómo he implementado una búsqueda aproximada:

    https://medium.com/@Srekel/implementing-a-fuzzy-search-algorithm-for-the-debuginator-cacc349e6c55

    La aplicación está en Github y es de dominio público, por lo que se sienten libres para echar un vistazo.

    https://github.com/Srekel/the-debuginator/blob/master/the_debuginator.h#L1856

    Los fundamentos de la misma es: Dividir todas las cadenas que usted va a estar buscando en partes. Así que si usted tiene caminos, entonces «C:\documents\lol.txt» es tal vez «C», «documentos», «lol», «txt».

    Asegurarse de que usted minúsculas estas cadenas para asegurarse de que usted es insensible a mayúsculas-minúsculas. (Tal vez sólo lo hacen si la cadena de búsqueda es todo en minúsculas).

    A continuación, coincide con la cadena de búsqueda en contra de esto. En mi caso quiero para que coincida con el mismo independientemente del orden, por lo que «loldoc» sería todavía coincide con la ruta de arriba aunque «lol» viene después de «doc».

    La coordinación de las necesidades que tienen algún gol a ser bueno. La parte más importante creo que es consecutivo coincidente, por lo que el más caracteres directamente después de uno a otro partido, el mejor. Así que el «doc» es mejor que «dcm».

    Entonces es probable que usted desee dar puntuación adicional para un partido que está en el inicio de una parte. Así que usted consigue más puntos para el «doc» de «ocu».

    En mi caso también me dan más puntos para que coincida con el final de una parte.

    Y, por último, puede que desee considerar la posibilidad de dar puntos extra para que coincida con el última parte(s). Esto se hace para que la coincidencia del nombre de archivo/final puntuaciones más altas que las carpetas que conducen a ella.

  4. 2

    Un algoritmo simple para «una especie de búsqueda difusa»

    Para ser honesto, en algunos casos, la búsqueda de equivalencias es en su mayoría inútiles y creo que un simple algoritmo puede mejorar el resultado de la búsqueda, mientras que proporciona la sensación de que todavía estamos realizando una búsqueda aproximada.

    Aquí es mi caso de uso: Filtrado de una lista de países de «búsqueda Difusa».

    La lista con la que estaba trabajando, tenía dos países que comienzan con Z: Zambia y Zimbabwe.

    Yo estaba usando Fusejs.

    En este caso, al introducir la aguja «zam», el conjunto de resultados fue con 19 partidos y el más relevante para cualquier ser humano (Zambia) en la parte inferior de la lista. Y la mayoría de los otros países en el resultado hasta no tener la letra » z » en su nombre.

    Esta fue para una aplicación móvil donde puedes elegir un país de una lista. Se suponía que iba a ser tanto como cuando tienes que elegir un contacto de los contactos del teléfono. Puede filtrar la lista de contactos introduciendo algunas término en el cuadro de búsqueda.

    Mi humilde opinión, este tipo de limitaciones en el contenido para la búsqueda de que no deben ser tratados de una manera que tienen las personas que preguntan «¿qué diablos?!?».

    Se podría sugerir para ordenar por más relevantes del partido. Pero eso está fuera de la cuestión en este caso, ya que el usuario siempre tiene que visualmente encontrar el «Punto de Interés» en la lista reducida. Tenga en cuenta que se supone que esta es una herramienta de filtrado, no un motor de búsqueda «a la de Google». Por lo que el resultado debe ser ordenados de una manera predecible. Y antes de filtrado, la clasificación fue alfabético. Así que la lista filtrada debe ser sólo una ordenada alfabéticamente subconjunto de la lista original.

    Así que se me ocurrió el siguiente algoritmo …

    1. Agarrar la aguja … en este caso: zam
    2. Insertar el .* patrón al principio y al final de la aguja
    3. Insertar el .* patrón entre cada letra de la aguja
    4. Realizar una Regex búsqueda en el pajar el uso de la nueva aguja que ahora es .*z.*a.*m.*

    En este caso, el usuario será mucho resultado esperado por la búsqueda de todo lo que tiene de alguna manera las letras z, a y m que aparecen en este orden. Todas las letras de las agujas estará presente en los partidos en el mismo orden.

    Esto coincidirá también con los nombres de países como Mozambique … que es perfecto.

    Simplemente creo que a veces, no debemos tratar de matar una mosca con un bazooka.

Dejar respuesta

Please enter your comment!
Please enter your name here