En informática , la coincidencia aproximada de cadenas (a menudo denominada coloquialmente búsqueda de cadenas difusas ) es la técnica de encontrar cadenas que coincidan con un patrón aproximadamente (en lugar de exactamente). El problema de la coincidencia aproximada de cadenas se divide típicamente en dos subproblemas: encontrar coincidencias aproximadas de subcadenas dentro de una cadena dada y encontrar cadenas de diccionario que coincidan aproximadamente con el patrón.
Descripción general
La cercanía de una coincidencia se mide en términos del número de operaciones primitivas necesarias para convertir la cadena en una coincidencia exacta. Este número se denomina distancia de edición entre la cuerda y el patrón. Las operaciones primitivas habituales son: [1]
- inserción: cuna → co a t
- supresión: co a t → cot
- sustitución: co a t → co s t
Estas tres operaciones pueden generalizarse como formas de sustitución agregando un carácter NULO (aquí simbolizado por *) siempre que se haya eliminado o insertado un carácter:
- inserción: co * t → co a t
- supresión: co a t → co * t
- sustitución: co a t → co s t
Algunos comparadores aproximados también tratan la transposición , en la que se intercambian las posiciones de dos letras en la cadena, como una operación primitiva. [2]
- transposición: co st → co ts
Diferentes comparadores aproximados imponen diferentes restricciones. Algunos comparadores utilizan un único costo global no ponderado, es decir, el número total de operaciones primitivas necesarias para convertir la coincidencia al patrón. Por ejemplo, si el patrón es enrollado , el papel de aluminio se diferencia por una sustitución, los enrollamientos por una inserción, el aceite por una deleción y el potro por dos sustituciones. Si todas las operaciones cuentan como una sola unidad de costo y el límite se establece en uno, el papel de aluminio , las bobinas y el aceite contarán como coincidencias, mientras que el potro no.
Otros comparadores especifican el número de operaciones de cada tipo por separado, mientras que otros establecen un costo total pero permiten asignar diferentes pesos a diferentes operaciones. Algunos comparadores permiten asignaciones separadas de límites y pesos a grupos individuales en el patrón.
Formulación de problemas y algoritmos
Una posible definición del problema de coincidencia de cadenas aproximadas es la siguiente: Dada una cadena de patrón y una cadena de texto , encuentra una subcadena en T , que, de todas las subcadenas de T , tiene la distancia de edición más pequeño al patrón P .
Un enfoque de fuerza bruta sería calcular la distancia de edición a P para todas las subcadenas de T y luego elegir la subcadena con la distancia mínima. Sin embargo, este algoritmo tendría el tiempo de ejecución O ( n 3 m ).
Una mejor solución, propuesta por Sellers [3] , se basa en la programación dinámica . Utiliza una formulación alternativa del problema: para cada posición j en el texto T y cada posición i en el patrón P , calcule la distancia de edición mínima entre los i primeros caracteres del patrón,y cualquier subcadena de T que termina en la posición j .
Para cada posición j en el texto T , y cada posición i en el patrón P , ir a través de todas las subcadenas de T termina en la posición j , y determinar cuál de ellos tiene la distancia de edición mínima a los i primeros caracteres del patrón P . Escriba esta distancia mínima como E ( i , j ). Después de calcular E ( i , j ) para todo i y j , podemos encontrar fácilmente una solución al problema original: es la subcadena para la que E ( m , j ) es mínima ( siendo m la longitud del patrón P. )
Calcular E ( m , j ) es muy similar a calcular la distancia de edición entre dos cadenas. De hecho, podemos usar el algoritmo de cálculo de distancia de Levenshtein para E ( m , j ), la única diferencia es que debemos inicializar la primera fila con ceros y guardar la ruta de cálculo, es decir, si usamos E ( i - 1, j ), E ( i , j - 1) o E ( i - 1, j - 1) en el cálculo de E ( i , j ).
En la matriz que contiene los valores de E ( x , y ), luego elegimos el valor mínimo en la última fila, sea E ( x 2 , y 2 ), y seguimos la ruta de cálculo hacia atrás, de regreso a la fila número 0 . Si el campo llegamos a era E (0, y 1 ), entonces T [ y 1 + 1] ... T [ y 2 ] es una subcadena de T con la distancia de edición mínimo para el patrón P .
Calcular la matriz E ( x , y ) toma O ( mn ) tiempo con el algoritmo de programación dinámica, mientras que la fase de trabajo hacia atrás toma O ( n + m ) tiempo.
Otra idea reciente es la unión de similitudes. Cuando la base de datos coincidente se relaciona con una gran escala de datos, el tiempo O ( mn ) con el algoritmo de programación dinámica no puede funcionar dentro de un tiempo limitado. Entonces, la idea es, en lugar de calcular la similitud de todos los pares de cadenas, reducir el número de pares candidatos. Los algoritmos ampliamente utilizados se basan en la verificación de filtros, el hash, el hash sensible a la localidad (LSH), los intentos y otros algoritmos codiciosos y de aproximación. La mayoría de ellos están diseñados para adaptarse a algún marco (como Map-Reduce) para computar simultáneamente.
En línea versus fuera de línea
Tradicionalmente, los algoritmos de coincidencia de cadenas aproximadas se clasifican en dos categorías: en línea y fuera de línea. Con los algoritmos en línea, el patrón se puede procesar antes de la búsqueda, pero el texto no. En otras palabras, las técnicas en línea realizan búsquedas sin índice. Los primeros algoritmos para el emparejamiento aproximado en línea fueron sugeridos por Wagner y Fisher [4] y por Sellers [5] . Ambos algoritmos se basan en programación dinámica pero resuelven diferentes problemas. El algoritmo de Sellers busca aproximadamente una subcadena en un texto, mientras que el algoritmo de Wagner y Fisher calcula la distancia de Levenshtein , siendo apropiado solo para la búsqueda difusa del diccionario.
Las técnicas de búsqueda en línea se han mejorado repetidamente. Quizás la mejora más famosa es el algoritmo bitap (también conocido como algoritmo shift-or y shift-and), que es muy eficiente para cadenas de patrones relativamente cortas. El algoritmo Bitap es el corazón de la utilidad de búsqueda de Unix agrep . G. Navarro realizó una revisión de los algoritmos de búsqueda en línea. [6]
Aunque existen técnicas en línea muy rápidas, su rendimiento en grandes cantidades de datos es inaceptable. El preprocesamiento o la indexación del texto hace que la búsqueda sea mucho más rápida. Hoy, se han presentado una variedad de algoritmos de indexación. Entre ellos se encuentran árboles de sufijos [7] , árboles métricos [8] y métodos de n-gramas . [9] [10] Un estudio detallado de las técnicas de indexación que permite encontrar una subcadena arbitraria en un texto es proporcionado por Navarro et al. [11] Boytsov [12] ofrece un estudio computacional de métodos de diccionario (es decir, métodos que permiten encontrar todas las palabras del diccionario que coincidan aproximadamente con un patrón de búsqueda) .
Aplicaciones
Las aplicaciones comunes de la coincidencia aproximada incluyen la revisión ortográfica . [13] Con la disponibilidad de grandes cantidades de datos de ADN, el emparejamiento de secuencias de nucleótidos se ha convertido en una aplicación importante. [14] La coincidencia aproximada también se utiliza en el filtrado de spam . [15] La vinculación de registros es una aplicación común en la que se comparan registros de dos bases de datos dispares.
La coincidencia de cadenas no se puede utilizar para la mayoría de los datos binarios, como imágenes y música. Requieren diferentes algoritmos, como la toma de huellas acústicas .
Ver también
Referencias
- ↑ Baeza-Yates, R .; Navarro, G. (junio de 1996). "Un algoritmo más rápido para la coincidencia aproximada de cadenas". En Dan Hirchsberg; Gene Myers (eds.). Coincidencia de patrones combinatorios (CPM'96), LNCS 1075 . Irvine, CA. págs. 1–23. CiteSeerX 10.1.1.42.1593 .
- ^Baeza-Yates, R .; Navarro, G. "Correspondencia rápida aproximada de cadenas en un diccionario" (PDF) . Proc. SPIRE'98 . IEEE CS Press. págs. 14-22.
- ^Boytsov, Leonid (2011). "Métodos de indexación para la búsqueda aproximada de diccionarios: análisis comparativo". Revista de algoritmos experimentales . 16 (1): 1–91. doi : 10.1145 / 1963190.1963191 .
- ^Cormen, Thomas ; Leiserson, Rivest (2001). Introducción a los algoritmos (2ª ed.). Prensa del MIT. págs. 364–7. ISBN 978-0-262-03293-3.
- ^Galil, Zvi; Apostolico, Alberto (1997). Algoritmos de coincidencia de patrones . Oxford [Oxfordshire]: Oxford University Press. ISBN 978-0-19-511367-9.
- ^Gusfield, Dan (1997). Algoritmos sobre cadenas, árboles y secuencias: informática y biología computacional . Cambridge, Reino Unido: Cambridge University Press. ISBN 978-0-521-58519-4.
- ^Myers, G. (mayo de 1999). "Un algoritmo de vector de bits rápido para la coincidencia aproximada de cadenas basado en programación dinámica" (PDF) . Revista de la ACM . 46 (3): 395–415. doi : 10.1145 / 316542.316550 .
- 10.1.1.96.7225 . doi : 10.1145 / 375360.375365 . Navarro, Gonzalo (2001). "Una visita guiada para aproximar el emparejamiento de cuerdas". Encuestas de computación ACM . 33 (1): 31–88. CiteSeerX
- ^Navarro, Gonzalo; Baeza-Yates, Ricardo; Sutinen, Erkki; Tarhio, Jorma (2001). "Métodos de indexación para la correspondencia aproximada de cadenas" (PDF) . Boletín de ingeniería de datos IEEE . 24 (4): 19-27.
- ^Vendedores, Peter H. (1980). "La teoría y el cálculo de las distancias evolutivas: reconocimiento de patrones". Revista de algoritmos . 1 (4): 359–73. doi : 10.1016 / 0196-6774 (80) 90016-4 .
- ^Skiena, Steve (1998). Manual de diseño de algoritmos (1ª ed.). Saltador. ISBN 978-0-387-94860-7.
- ^Ukkonen, E. (1985). "Algoritmos de coincidencia aproximada de cadenas" . Información y control . 64 (1-3): 100-18. doi : 10.1016 / S0019-9958 (85) 80046-2 .
- ^Wagner, R .; Fischer, M. (1974). "El problema de la corrección de cuerda a cuerda". Revista de la ACM . 21 : 168–73. doi : 10.1145 / 321796.321811 .
- ^Zobel, Justin; Dardo, Philip (1995). "Encontrar coincidencias aproximadas en grandes léxicos". Práctica y experiencia de software . 25 (3): 331–345. CiteSeerX 10.1.1.14.3856 . doi : 10.1002 / spe.4380250307 .
enlaces externos
- Proyecto Flamingo
- Proyecto de procesamiento de consultas de similitud eficiente con avances recientes en la coincidencia aproximada de cadenas en función de un umbral de distancia de edición.
- StringMetric proyecta una biblioteca Scala de métricas de cadenas y algoritmos fonéticos
- Proyecto natural una biblioteca de procesamiento de lenguaje natural de JavaScript que incluye implementaciones de métricas de cadenas populares