algorithm - Algoritmos aproximados de concordancia de cadenas
algoritmos string matching (7)
Aquí en el trabajo, a menudo necesitamos encontrar una cadena de la lista de cadenas que sea la coincidencia más cercana a alguna otra cadena de entrada. Actualmente, estamos usando el algoritmo Needleman-Wunsch. El algoritmo a menudo devuelve una gran cantidad de falsos positivos (si establecemos el puntaje mínimo demasiado bajo), a veces no encuentra una coincidencia cuando debería (cuando el puntaje mínimo es demasiado alto) y, la mayoría de las veces, necesitamos verificar los resultados a mano. Pensamos que deberíamos probar otras alternativas.
¿Tienes alguna experiencia con los algoritmos? ¿Sabes cómo los algoritmos se comparan entre sí?
Realmente agradecería algunos consejos.
PD: Estamos codificando en C #, pero no debería importarle, estoy preguntando sobre los algoritmos en general.
Oh, lo siento, olvidé mencionar eso.
No, no lo estamos usando para unir datos duplicados. Tenemos una lista de cadenas que estamos buscando, la llamamos lista de búsqueda. Y luego tenemos que procesar textos de varias fuentes (como fuentes RSS, sitios web, foros, etc.) - extraemos partes de esos textos (hay conjuntos enteros de reglas para eso, pero eso es irrelevante) y tenemos que hacer coincidir aquellos en contra de la lista de búsqueda. Si la cadena coincide con una de las cadenas en la lista de búsqueda, necesitamos hacer un procesamiento adicional de la cosa (que también es irrelevante).
No podemos realizar la comparación normal, porque las cadenas extraídas de las fuentes externas, la mayoría de las veces, incluyen algunas palabras adicionales, etc.
De todos modos, no es para la detección de duplicados.
Algoritmos alternativos a observar son agrep ( entrada de Wikipedia en agrep ), algoritmos de combinación de secuencias biológicas FASTA y BLAST . Estos son casos especiales de emparejamiento aproximado de cadenas , también en la reposición de algoritmos de Stony Brook . Si puede especificar las formas en que las cadenas difieren entre sí, probablemente podría centrarse en un algoritmo personalizado. Por ejemplo, aspell usa una variante de distancia "soundslike" (soundex-metaphone) en combinación con una distancia de "teclado" para acomodar a los malos deletreado y a los tipos malos por igual.
De acuerdo, Needleman-Wunsch (NW) es un alineador clásico extremo a extremo ("global") de la literatura bioinformática. Hace mucho tiempo estaba disponible como "alinear" y "alinear" en el paquete FASTA. La diferencia era que la versión "0" no era tan tendenciosa como para evitar las brechas terminales, lo que a menudo permitía favorecer las coincidencias internas de alta calidad más fácilmente. Smith-Waterman, sospecho que usted sabe, es un alineador local y es la base original de BLAST. FASTA también tenía su propio alineador local que era ligeramente diferente. Todos estos son esencialmente métodos heurísticos para estimar la distancia de Levenshtein relevante para una métrica de puntuación para pares de caracteres individuales (en bioinformática, a menudo dada por Dayhoff / "PAM", Henikoff y Henikoff u otras matrices y generalmente reemplazada por algo más simple y más razonablemente reflectante de reemplazos en la morfología de la palabra lingüística cuando se aplica al lenguaje natural).
No seamos preciados con las etiquetas: la distancia de Levenshtein, como se menciona en la práctica al menos, es básicamente la distancia de edición y hay que estimarla porque no es factible calcularla en general, y es costoso calcularla exactamente incluso en casos especiales interesantes: el agua se pone muy rápido allí, y así tenemos métodos heurísticos de larga y buena reputación.
Ahora en cuanto a su propio problema: hace varios años, tuve que verificar la exactitud de las lecturas de ADN cortas contra la secuencia de referencia que se sabe que es correcta y se me ocurrió algo que llamé "alineaciones ancladas".
La idea es tomar su conjunto de cadenas de referencia y "digerirlo" al encontrar todas las ubicaciones donde se produce una subcadena de N caracteres dada. Elija N para que la tabla que compile no sea demasiado grande, pero también para que las subcadenas de longitud N no sean demasiado comunes. Para alfabetos pequeños como bases de ADN, es posible obtener un hash perfecto en cadenas de N caracteres y hacer una tabla y encadenar las coincidencias en una lista vinculada de cada contenedor. Las entradas de la lista deben identificar la secuencia y la posición de inicio de la subcadena que se asigna al contenedor en cuya lista se encuentran. Estos son "anclajes" en la lista de cadenas a buscar en las que es probable que una alineación NW sea útil.
Al procesar una cadena de consulta, toma los N caracteres comenzando con una compensación K en la cadena de consulta, los pica, busca su contenedor y si la lista para ese contenedor no está vacía, entonces revisa todos los registros de la lista y realiza alineaciones entre la cadena de consulta y la cadena de búsqueda a la que se hace referencia en el registro. Al hacer estas alineaciones, alinea la cadena de consulta y la cadena de búsqueda en el anclaje y extrae una subcadena de la cadena de búsqueda que tiene la misma longitud que la cadena de consulta y que contiene ese anclaje en el mismo desplazamiento, K.
Si elige una longitud de anclaje suficientemente larga N, y un conjunto razonable de valores de compensación K (pueden distribuirse a lo largo de la cadena de consulta o restringirse a compensaciones bajas), debe obtener un subconjunto de posibles alineaciones y, a menudo, ganadores más claros. Por lo general, querrá usar el alineador NW menos parecido al final del align0.
Este método intenta aumentar NW un poco al restringir su entrada y esto tiene una ganancia de rendimiento porque haces menos alineaciones y están más a menudo entre secuencias similares. Otra cosa buena que hacer con su alineador NW es permitir que se rinda después de cierta cantidad o longitud de espacio para reducir costos, especialmente si usted sabe que no verá o no le interesarán las coincidencias de calidad mediana.
Finalmente, este método se usó en un sistema con alfabetos pequeños, con K restringido a las primeras 100 posiciones en la cadena de consulta y con cadenas de búsqueda mucho más grandes que las consultas (las lecturas de ADN fueron alrededor de 1000 bases y las cadenas de búsqueda estaban en el orden de 10000, así que estaba buscando coincidencias de subcadenas aproximadas justificadas por una estimación de distancia de edición específicamente). La adaptación de esta metodología al lenguaje natural requerirá una reflexión cuidadosa: se pierde en el tamaño del alfabeto pero se gana si las cadenas de búsqueda y las cadenas de búsqueda tienen una longitud similar.
De cualquier manera, permitir que más de un anclaje de diferentes extremos de la cadena de consulta se use simultáneamente podría ser útil para filtrar los datos alimentados a NW. Si hace esto, prepárese para enviar cadenas superpuestas que contengan uno de los dos anclajes al alineador y luego reconcilie las alineaciones ... o posiblemente modifique NW para enfatizar la mayor parte de las anclas durante una alineación usando la modificación de penalizaciones durante el alineamiento. ejecución del algoritmo
Espero que esto sea útil o al menos interesante.
Estamos utilizando el método de distancia de Levenshtein para buscar clientes duplicados en nuestra base de datos. Funciona bastante bien.
Para ampliar la respuesta de Cd-MaN, parece que estás enfrentando un problema de normalización. No es obvio cómo manejar puntajes entre alineaciones con longitudes variables.
Dado lo que le interesa, es posible que desee obtener valores p para su alineación. Si está usando Needleman-Wunsch, puede obtener estos valores p usando las estadísticas de Karlin-Altschul http://www.ncbi.nlm.nih.gov/BLAST/tutorial/Altschul-1.html
BLAST puede alinear localmente y evaluarlos usando estas estadísticas. Si le preocupa la velocidad, esta sería una buena herramienta para usar.
Otra opción es usar HMMER. HMMER utiliza modelos de perfil de Markov ocultos para alinear secuencias. Personalmente, creo que este es un enfoque más poderoso ya que también proporciona información posicional. http://hmmer.janelia.org/
Para minimizar los desajustes debidos a ligeras variaciones o errores de ortografía, he usado el algoritmo de Metaphone, luego la distancia de Levenshtein (escalada a 0-100 como una coincidencia porcentual) en las codificaciones de Metaphone para una medida de cercanía. Eso parece haber funcionado bastante bien.
Relacionado con la distancia de Levenstein: es posible que desee normalizar dividiendo el resultado con la longitud de la cadena más larga, de modo que siempre obtenga un número entre 0 y 1 y para que pueda comparar la distancia de un par de cadenas de una manera significativa. manera (la expresión L (A, B)> L (A, C) - por ejemplo - no tiene sentido a menos que usted normalice la distancia).